27-2024 Solutions

This document provides complete, step-by-step solutions to the CSE-4101: Artificial Intelligence Final Examination questions.

Question 1 Solutions

1 (a) Heuristics & Admissibility

• Heuristic Definition: A heuristic function $h(n)$ estimates the cost of the cheapest path from the current node $n$ to a goal state. It incorporates domain-specific knowledge to guide the search algorithm toward the goal more efficiently than uninformed search.

• Admissibility: A heuristic is admissible if it never overestimates the actual cost to reach a goal. That is: $h(n) \le h^*(n) \quad \forall n$ where $h^*(n)$ represents the true optimal cost from node $n$ to the goal. Admissible heuristics are always optimistic about the remaining distance.

• Typical Examples:

  1. Manhattan Distance (in grid-world / 8-puzzle navigation): The sum of horizontal and vertical distances of tiles from their target positions.
  2. Straight-line Distance (in routing problems): The Euclidean distance from node $n$ to the coordinates of the goal node.

• Proof: Consistency $\implies$ Admissibility Let $c(n, a, n')$ be the step cost of transitioning from node $n$ to child node $n'$ via action $a$. A heuristic $h$ is consistent (or monotonic) if: $h(n) \le c(n, a, n') + h(n') \quad \forall n, n'$ and $h(G) = 0$ for any goal state $G$.

  We prove admissibility by induction on the number of steps $k$ on the optimal path from node $n$ to a goal $G$.

  • Base Case ($k=0$): If $n = G$, then $h(G) = 0 \le h^*(G) = 0$. Admissibility holds.
  • Inductive Step: Assume admissibility holds for all nodes with an optimal path of $k$ steps to the goal. Let $n$ be a node with an optimal path of $k+1$ steps, and let $n'$ be its immediate successor on that optimal path. By consistency: $h(n) \le c(n, a, n') + h(n')$ By our inductive hypothesis, since $n'$ is $k$ steps away from the goal: $h(n') \le h^*(n')$ Since $n'$ lies on the optimal path from $n$ to $G$, the optimal cost $h^*(n)$ satisfies: $h^*(n) = c(n, a, n') + h^*(n')$ Substituting the induction hypothesis back into the consistency inequality yields: $h(n) \le c(n, a, n') + h^*(n') = h^*(n)$ Thus, $h(n) \le h^*(n)$ for all nodes, proving that any consistent heuristic is admissible.

Theory: Heuristic Functions and Optimality

1 (b) A* Search

• A Search:* An informed search algorithm that selects the next node for expansion by minimizing the total evaluation function: $f(n) = g(n) + h(n)$ where $g(n)$ is the exact cost incurred to reach node $n$ from the start state, and $h(n)$ is the estimated cost from $n$ to the goal.
• Advantages:
  • Completeness: A* is guaranteed to find a solution if one exists, provided the branching factor is finite and the step costs are bounded away from zero ($c \ge \epsilon > 0$).
  • Optimality: A* is guaranteed to find the optimal path if $h(n)$ is admissible (for tree search) or consistent (for graph search).
  • Optimal Efficiency: No other optimal search algorithm expanding nodes from the start is guaranteed to expand fewer nodes than A* using the same heuristic.
• Disadvantages:
  • Space Complexity: $O(b^d)$ in the worst case (where $b$ is the branching factor and $d$ is the depth). Because it must keep all generated nodes in the Open List (priority queue) to maintain search paths, A* typically runs out of memory long before running out of time.
  • Time Complexity: $O(b^d)$ in the worst case, though it can be much lower with an extremely accurate heuristic.

Theory: A* Search and Extensions

1 (c) 8-Puzzle State-Space Search

• Heuristic ($h$): Number of misplaced tiles (excluding the blank tile -).
• Path Cost ($g$): $+1$ for each step/transition.
• Goal State:

  1  2  3
  8  -  4
  7  6  5

Let's trace the optimal search path step-by-step, showing the candidates at each expansion.

1. Start State: [2, 8, 3 / 1, 6, 4 / 7, -, 5], $g=0$, misplaced tiles $\{2, 8, 1, 6\}$, so $h=4$. $f = 0 + 4 = 4$.
2. Step 1: Slide 6 down into - (Move Up).
   • Successor State: [2, 8, 3 / 1, -, 4 / 7, 6, 5], $g=1$, misplaced tiles $\{2, 8, 1\}$, so $h=3$. $f = 1 + 3 = 4$.
3. Step 2: Slide 8 down into - (Move Up).
   • Successor State: [2, -, 3 / 1, 8, 4 / 7, 6, 5], $g=2$, misplaced tiles $\{2, 1, 8\}$, so $h=3$. $f = 2 + 3 = 5$.
4. Step 3: Slide 2 right into - (Move Left).
   • Successor State: [-, 2, 3 / 1, 8, 4 / 7, 6, 5], $g=3$, misplaced tiles $\{1, 8\}$, so $h=2$. $f = 3 + 2 = 5$.
5. Step 4: Slide 1 up into - (Move Down).
   • Successor State: [1, 2, 3 / -, 8, 4 / 7, 6, 5], $g=4$, misplaced tiles $\{8\}$, so $h=1$. $f = 4 + 1 = 5$.
6. Step 5: Slide 8 left into - (Move Right).
   • Goal State reached: [1, 2, 3 / 8, -, 4 / 7, 6, 5], $g=5$, misplaced tiles $=\emptyset$, so $h=0$. $f = 5 + 0 = 5$.

Theory: Informed Search and Heuristics

Question 2 Solutions

2 (a) Resolution Inference in First Order Logic (FOPL)

We want to prove that the set of clauses along with the negated goal leads to a contradiction, verifying that "Jack did not kill the cat" is true (or refuting that "Jack killed the cat" is true).

1. Convert Formulas to Conjunctive Normal Form (CNF)

• Formula A: $\forall x [\forall y \text{ Animal}(y) \implies \text{Loves}(x, y)] \implies [\exists y \text{ Loves}(y, x)]$

  1. Eliminate implication: $\forall x [ \neg(\forall y \neg\text{Animal}(y) \lor \text{Loves}(x, y)) \lor \exists y \text{ Loves}(y, x) ]$ $\forall x [ (\exists y \text{ Animal}(y) \land \neg\text{Loves}(x, y)) \lor \exists y \text{ Loves}(y, x) ]$
  2. Standardize variables: $\forall x [ (\exists y \text{ Animal}(y) \land \neg\text{Loves}(x, y)) \lor \exists w \text{ Loves}(w, x) ]$
  3. Skolemize (existential quantifiers inside universal quantifier $\forall x$): Let Skolem functions be $f(x)$ for $y$, and $g(x)$ for $w$. $\forall x [ (\text{Animal}(f(x)) \land \neg\text{Loves}(x, f(x))) \lor \text{Loves}(g(x), x) ]$
  4. Distribute $\lor$ over $\land$: $(\text{Animal}(f(x)) \lor \text{Loves}(g(x), x)) \land (\neg\text{Loves}(x, f(x)) \lor \text{Loves}(g(x), x))$
  5. Resulting Clauses:
     • Clause A1: $\text{Animal}(f(x)) \lor \text{Loves}(g(x), x)$
     • Clause A2: $\neg\text{Loves}(x, f(x)) \lor \text{Loves}(g(x), x)$

• Formula B: $\forall x [\exists z \text{ Animal}(z) \land \text{Kills}(x, z)] \implies [\forall y \neg\text{Loves}(y, x)]$

  1. Eliminate implication: $\forall x [ \neg(\exists z \text{ Animal}(z) \land \text{Kills}(x, z)) \lor \forall y \neg\text{Loves}(y, x) ]$ $\forall x [ \forall z (\neg\text{Animal}(z) \lor \neg\text{Kills}(x, z)) \lor \forall y \neg\text{Loves}(y, x) ]$
  2. Move quantifiers and drop: $\neg\text{Animal}(z) \lor \neg\text{Kills}(x, z) \lor \neg\text{Loves}(y, x)$
  3. Resulting Clause:
     • Clause B1: $\neg\text{Animal}(z) \lor \neg\text{Kills}(x, z) \lor \neg\text{Loves}(y, x)$

• Formula C: $\forall x \text{ Animal}(x) \implies \text{Loves}(\text{Jack}, x)$

  • Clause C1: $\neg\text{Animal}(w) \lor \text{Loves}(\text{Jack}, w)$ (using standardized variable $w$)

• Formula D: $\text{Kills}(\text{Jack}, \text{Tuna}) \lor \text{Kills}(\text{Curiosity}, \text{Tuna})$

  • Clause D1: $\text{Kills}(\text{Jack}, \text{Tuna}) \lor \text{Kills}(\text{Curiosity}, \text{Tuna})$

• Formula E: $\text{Cat}(\text{Tuna})$

  • Clause E1: $\text{Cat}(\text{Tuna})$

• Formula F: $\forall x \text{ Cat}(x) \implies \text{Animal}(x)$

  • Clause F1: $\neg\text{Cat}(v) \lor \text{Animal}(v)$ (using standardized variable $v$)

• Negated Goal ($\neg G$): We assume the goal is to prove "Jack did not kill the cat" (i.e. $\neg \text{Kills}(\text{Jack}, \text{Tuna})$). The negation of the goal is:

  • Clause G1: $\text{Kills}(\text{Jack}, \text{Tuna})$

2. Resolution Proof (Deriving Contradiction)

We resolve clauses to arrive at the empty clause ($\square$):

1. Resolve E1 ($\text{Cat}(\text{Tuna})$) with F1 ($\neg\text{Cat}(v) \lor \text{Animal}(v)$) under substitution $\{v / \text{Tuna}\}$:
   • R1: $\text{Animal}(\text{Tuna})$
2. Resolve B1 ($\neg\text{Animal}(z) \lor \neg\text{Kills}(x, z) \lor \neg\text{Loves}(y, x)$) with R1 ($\text{Animal}(\text{Tuna})$) and G1 ($\text{Kills}(\text{Jack}, \text{Tuna})$) under substitution $\{x / \text{Jack}, z / \text{Tuna}\}$:
   • R2: $\neg\text{Loves}(y, \text{Jack})$ (i.e., No one loves Jack)
3. Resolve A2 ($\neg\text{Loves}(x, f(x)) \lor \text{Loves}(g(x), x)$) with R2 ($\neg\text{Loves}(y, \text{Jack})$) under substitution $\{x / \text{Jack}, y / g(\text{Jack})\}$:
   • R3: $\neg\text{Loves}(\text{Jack}, f(\text{Jack}))$
4. Resolve A1 ($\text{Animal}(f(x)) \lor \text{Loves}(g(x), x)$) with R2 ($\neg\text{Loves}(y, \text{Jack})$) under substitution $\{x / \text{Jack}, y / g(\text{Jack})\}$:
   • R4: $\text{Animal}(f(\text{Jack}))$
5. Resolve C1 ($\neg\text{Animal}(w) \lor \text{Loves}(\text{Jack}, w)$) with R4 ($\text{Animal}(f(\text{Jack}))$) under substitution $\{w / f(\text{Jack})\}$:
   • R5: $\text{Loves}(\text{Jack}, f(\text{Jack}))$
6. Resolve R3 ($\neg\text{Loves}(\text{Jack}, f(\text{Jack}))$) with R5 ($\text{Loves}(\text{Jack}, f(\text{Jack}))$):
   • Empty Clause ($\square$)

Because we derived a contradiction from the negated goal (which assumed Jack did kill the cat), we have successfully proved that "Jack did not kill the cat" is True (and thus "Jack killed the cat" is False).

Theory: CNF Conversion and Resolution

2 (b) Fuzzy Expert Systems & Inference

Given inputs: Mean Delay ($x$) = 0.25 and Number of Servers ($y$) = 0.65.

1. Fuzzification (Calculate Degrees of Membership)

Using the membership function equations:

• Mean Delay ($x = 0.25$):

  • Very Small (VS): Vertices at $(0, 1.0)$ and $(0.3, 0.0)$. $\mu_{\text{VS}}(0.25) = \frac{0.3 - 0.25}{0.3 - 0} = \frac{0.05}{0.3} = \frac{1}{6} \approx 0.167$
  • Small (S): Vertices at $(0.1, 0.0)$, $(0.3, 1.0)$, and $(0.5, 0.0)$. $\mu_{\text{S}}(0.25) = \frac{0.25 - 0.1}{0.3 - 0.1} = \frac{0.15}{0.2} = 0.75$
  • Medium (M): Range starts at $0.4$, so $x = 0.25$ does not overlap. $\mu_{\text{M}}(0.25) = 0$

• Number of Servers ($y = 0.65$):

  • Small (S): Range ends at $0.3$, so $\mu_{\text{S}}(0.65) = 0$.
  • Medium (M): Vertices at $(0.3, 0.0)$, $(0.5, 1.0)$, and $(0.7, 0.0)$. $\mu_{\text{M}}(0.65) = \frac{0.7 - 0.65}{0.7 - 0.5} = \frac{0.05}{0.2} = 0.25$
  • Large (L): Vertices at $(0.6, 0.0)$, $(0.8, 1.0)$ and $(1.0, 1.0)$. $\mu_{\text{L}}(0.65) = \frac{0.65 - 0.6}{0.8 - 0.6} = \frac{0.05}{0.2} = 0.25$

2. Rule Evaluation (Applying Mamdani Min-inference)

We calculate the activation strength ($\alpha$) of each rule using $\min$ for the conjunction "AND":

• Rule 1: If Mean Delay is VS and Number of Servers is L, then Utilization is Low. $\alpha_1 = \min(\mu_{\text{VS}}(0.25), \mu_{\text{L}}(0.65)) = \min(0.167, 0.25) = 0.167 \implies \text{Low}$
• Rule 2: If Mean Delay is S and Number of Servers is M, then Utilization is Medium. $\alpha_2 = \min(\mu_{\text{S}}(0.25), \mu_{\text{M}}(0.65)) = \min(0.75, 0.25) = 0.25 \implies \text{Medium}$
• Rule 3: If Mean Delay is M and Number of Servers is S, then Utilization is High. $\alpha_3 = \min(\mu_{\text{M}}(0.25), \mu_{\text{S}}(0.65)) = \min(0, 0) = 0 \implies \text{High}$
• Rule 4: If Mean Delay is S and Number of Servers is S, then Utilization is High. $\alpha_4 = \min(\mu_{\text{S}}(0.25), \mu_{\text{S}}(0.65)) = \min(0.75, 0) = 0 \implies \text{High}$
• Rule 5: If Mean Delay is M and Number of Servers is M, then Utilization is Medium. $\alpha_5 = \min(\mu_{\text{M}}(0.25), \mu_{\text{M}}(0.65)) = \min(0, 0.25) = 0 \implies \text{Medium}$

3. Aggregation

Using $\max$ to combine multiple rules mapping to the same output:

• $\text{Low} = \alpha_1 = 0.167$
• $\text{Medium} = \max(\alpha_2, \alpha_5) = \max(0.25, 0) = 0.25$
• $\text{High} = \max(\alpha_3, \alpha_4) = 0$

4. Defuzzification (Weighted Average Method / Singleton Approximation)

Assuming standard center values for output membership functions (Low = 0.2, Medium = 0.6, High = 0.8): $z^* = \frac{\sum \mu_i \cdot z_i}{\sum \mu_i} = \frac{(0.167 \times 0.2) + (0.25 \times 0.6) + (0 \times 0.8)}{0.167 + 0.25}$ $z^* = \frac{0.0334 + 0.150}{0.417} = \frac{0.1834}{0.417} \approx 0.44$

The precise value of the repair utilization factor is 0.44.

Theory: Fuzzy Expert Systems

Question 3 Solutions

3 (a) 4-Queens with Backtracking and Forward Checking

• Variables: $Q_1, Q_2, Q_3, Q_4$ (representing rows of queens in columns 1, 2, 3, 4).
• Domains: $D_1 = D_2 = D_3 = D_4 = \{1, 2, 3, 4\}$.

Step-by-Step Execution Trace:

1. Assign $Q_1 = 1$.
   • Forward Checking (reduce domains of unassigned variables):
     • $Q_2$ cannot be in row 1 (same row) or row 2 (diagonal). $D_2 \leftarrow \{3, 4\}$.
     • $Q_3$ cannot be in row 1 or row 3 (diagonal). $D_3 \leftarrow \{2, 4\}$.
     • $Q_4$ cannot be in row 1 or row 4 (diagonal). $D_4 \leftarrow \{2, 3\}$.
2. Assign $Q_2 = 3$ (first available value in $D_2$).
   • Forward Checking:
     • $Q_3$ cannot be in row 3 (same row), row 2 (diagonal: $3 - 1$), or row 4 (diagonal: $3 + 1$).
     • Since $D_3$ was $\{2, 4\}$, removing 2 and 4 makes $D_3 \leftarrow \emptyset$.
   • Result: Forward checking triggers immediate backtracking because the domain of $Q_3$ became empty.
3. Backtrack and Try $Q_2 = 4$ (next value in $D_2$).
   • Forward Checking:
     • $Q_3$ cannot be in row 4 (same row) or row 3 (diagonal: $4 - 1$). $D_3 = \{2, 4\} \setminus \{3, 4\} \leftarrow \{2\}$.
     • $Q_4$ cannot be in row 4 (same row) or row 2 (diagonal: $4 - 2$). $D_4 = \{2, 3\} \setminus \{2, 4\} \leftarrow \{3\}$.
4. Assign $Q_3 = 2$ (only available value in $D_3$).
   • Forward Checking:
     • $Q_4$ cannot be in row 2 (same row) or row 3 (diagonal: $2 + 1$).
     • Since $D_4$ was $\{3\}$, removing 3 makes $D_4 \leftarrow \emptyset$.
   • Result: Backtrack! No more values for $Q_2$, so we backtrack to $Q_1$.
5. Assign $Q_1 = 2$ (next value in $D_1$).
   • Forward Checking:
     • $Q_2$ cannot be 2, 1 (diagonal: $2 - 1$), or 3 (diagonal: $2 + 1$). $D_2 \leftarrow \{4\}$.
     • $Q_3$ cannot be 2 or 4 (diagonal: $2 + 2$). $D_3 \leftarrow \{1, 3\}$.
     • $Q_4$ cannot be 2. $D_4 \leftarrow \{1, 3, 4\}$.
6. Assign $Q_2 = 4$ (only value in $D_2$).
   • Forward Checking:
     • $Q_3$ cannot be 4, or 3 (diagonal: $4 - 1$). $D_3 = \{1, 3\} \setminus \{3, 4\} \leftarrow \{1\}$.
     • $Q_4$ cannot be 4, or 2 (diagonal: $4 - 2$). $D_4 = \{1, 3, 4\} \setminus \{2, 4\} \leftarrow \{1, 3\}$.
7. Assign $Q_3 = 1$ (only value in $D_3$).
   • Forward Checking:
     • $Q_4$ cannot be 1, or 2 (diagonal: $1 + 1$). $D_4 = \{1, 3\} \setminus \{1, 2\} \leftarrow \{3\}$.
8. Assign $Q_4 = 3$.
   • Result: Search succeeds. Solution found: $[2, 4, 1, 3]$.

• Condition to Trigger Backtracking: Forward checking triggers backtracking when the domain of any unassigned variable is reduced to an empty set ($\emptyset$) during domain propagation.

Theory: Backtracking and Local Search for CSPs

3 (b) Heuristics & Scalability in CSPs

• i. Variable & Value Selection Heuristics:
  • Most Constrained Variable (Minimum Remaining Values - MRV): Choose the variable with the fewest remaining valid choices. This is a fail-first heuristic: it forces a failure as early as possible in the search tree if a branch is unviable, pruning large subtrees.
  • Least Constraining Value (LCV): Choose the value that rules out the fewest choices for neighboring variables in the constraint graph. This is a succeed-first heuristic: it maximizes flexibility for remaining variables to find a solution without backtracking.
• ii. Scalability and Efficiency:
  • Heuristic strategies (such as MRV, LCV, and degree heuristics) improve backtracking scalability by dynamically pruning dead-ends early, reducing the effective branching factor from exponential down to a manageable search depth.
  • For extreme scalability, exactness can be sacrificed using approximate / local search algorithms (e.g., Min-Conflicts, Simulated Annealing). These algorithms do not guarantee finding a solution or proving unsatisfiability but find high-quality approximate solutions in linear time $O(N)$ instead of exponential time.

Theory: Constraint Satisfaction Problems

Question 4 Solutions

4 (a) MDP Value Iteration

Value Iteration Equation: $U_{t+1}(s) = R(s) + \gamma \max_{a} \sum_{s'} T(s, a, s') U_t(s')$ Given: $\gamma = 0.9$, $R(s_1) = 1.2$, $R(s_2) = 2.5$. Let $U_0(s_1) = U_0(s_2) = 0$.

Iteration 1 ($t=1$)

$U_1(s_1) = 1.2 + 0.9(0) = 1.20$ $U_1(s_2) = 2.5 + 0.9(0) = 2.50$

Iteration 2 ($t=2$)

• State $s_1$:
  • $a_1$: Expected utility $= 0.6 \cdot U_1(s_1) + 0.4 \cdot U_1(s_2) = 0.6(1.20) + 0.4(2.50) = 0.72 + 1.00 = 1.72$
  • $a_2$: Expected utility $= 0.2 \cdot U_1(s_1) + 0.8 \cdot U_1(s_2) = 0.2(1.20) + 0.8(2.50) = 0.24 + 2.00 = 2.24$
  • $U_2(s_1) = 1.2 + 0.9 \cdot \max(1.72, 2.24) = 1.2 + 0.9(2.24) = 1.2 + 2.016 \approx 3.22$
• State $s_2$:
  • $a_1$: Expected utility $= 0.3 \cdot U_1(s_1) + 0.7 \cdot U_1(s_2) = 0.3(1.20) + 0.7(2.50) = 0.36 + 1.75 = 2.11$
  • $a_2$: Expected utility $= 0.1 \cdot U_1(s_1) + 0.9 \cdot U_1(s_2) = 0.1(1.20) + 0.9(2.50) = 0.12 + 2.25 = 2.37$
  • $U_2(s_2) = 2.5 + 0.9 \cdot \max(2.11, 2.37) = 2.5 + 0.9(2.37) = 2.5 + 2.133 \approx 4.63$

Iteration 3 ($t=3$)

• State $s_1$:
  • $a_1$: Expected utility $= 0.6(3.22) + 0.4(4.63) = 1.932 + 1.852 = 3.784$
  • $a_2$: Expected utility $= 0.2(3.22) + 0.8(4.63) = 0.644 + 3.704 = 4.348$
  • $U_3(s_1) = 1.2 + 0.9 \cdot \max(3.784, 4.348) = 1.2 + 0.9(4.348) = 1.2 + 3.9132 \approx 5.11$
  • Optimal Action at $s_1$: $a_2$
• State $s_2$:
  • $a_1$: Expected utility $= 0.3(3.22) + 0.7(4.63) = 0.966 + 3.241 = 4.207$
  • $a_2$: Expected utility $= 0.1(3.22) + 0.9(4.63) = 0.322 + 4.167 = 4.489$
  • $U_3(s_2) = 2.5 + 0.9 \cdot \max(4.207, 4.489) = 2.5 + 0.9(4.489) = 2.5 + 4.0401 \approx 6.54$
  • Optimal Action at $s_2$: $a_2$

4 (b) Q-learning vs. Value Iteration

• Equation Modification: Q-learning removes the transition probability $T(s, a, s')$ and the reward function $R(s)$ by learning directly from environmental samples (experience tuples $\langle s, a, r, s' \rangle$). The update rule is: $Q(s, a) \leftarrow Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$
• Key Differences:
  1. Transition Model: Value Iteration is model-based (requires knowing transition probabilities $T(s, a, s')$ and rewards $R(s)$). Q-learning is model-free (learns directly from interactions without a model of the environment).
  2. Type of Value Learned: Value Iteration learns state utilities $U(s)$. Q-learning learns action-values $Q(s, a)$ (the value of taking action $a$ in state $s$).
• Applications:
  • Value Iteration (Model-based): Used where full environmental dynamics are known (e.g., path planning on an exact map).
  • Q-learning (Model-free): Used in complex, unknown environments (e.g., training an agent to play video games from raw screen pixels).

Theory: MDPs and Reinforcement Learning

Question 5 Solutions

5 (a) Minimax Game Tree Evaluation

The Minimax algorithm evaluates game states in a two-player, zero-sum game. The Max player tries to maximize the score, while the Min player tries to minimize it.

• Min Level Evaluations:
  • $\text{Min}_1 = \min(8, 9, 3, 4, 5) = 3$
  • $\text{Min}_2 = \min(7, 1, 3, 8, 2) = 1$
  • $\text{Min}_3 = \min(4, 3, 9, 2, 2) = 2$
  • $\text{Min}_4 = \min(9, 1, 5, 6, 4) = 1$
  • $\text{Min}_5 = \min(2, 3, 7, 3, 8) = 2$
• Max (Root) Evaluation:
  • $\text{Root} = \max(\text{Min}_1, \text{Min}_2, \text{Min}_3, \text{Min}_4, \text{Min}_5) = \max(3, 1, 2, 1, 2) = 3$

The minimax value of the root node is 3. Max should choose the branch leading to the first Min node ($\text{Min}_1$).

5 (b) Alpha-Beta Pruning Tracing

Using $\alpha$ (Max's guaranteed minimum) and $\beta$ (Min's guaranteed maximum), initialized to $\alpha = -\infty, \beta = +\infty$.

1. Evaluate $\text{Min}_1$:
   • Leaves: 8, 9, 3, 4, 5. $\text{Min}_1$ value $= 3$.
   • Update root: $\alpha \leftarrow \max(-\infty, 3) = 3$.
2. Evaluate $\text{Min}_2$ (with bounds $\alpha = 3, \beta = +\infty$):
   • Leaf 7: $\beta \leftarrow \min(\infty, 7) = 7$.
   • Leaf 1: $\beta \leftarrow \min(7, 1) = 1$.
   • Pruning Condition: Since $\beta \le \alpha$ ($1 \le 3$), we prune the remaining leaves of this node.
   • Pruned: 3, 8, 2.
3. Evaluate $\text{Min}_3$ (with bounds $\alpha = 3, \beta = +\infty$):
   • Leaf 4: $\beta \leftarrow \min(\infty, 4) = 4$.
   • Leaf 3: $\beta \leftarrow \min(4, 3) = 3$.
   • Pruning Condition: Since $\beta \le \alpha$ ($3 \le 3$), we prune.
   • Pruned: 9, 2, 2.
4. Evaluate $\text{Min}_4$ (with bounds $\alpha = 3, \beta = +\infty$):
   • Leaf 9: $\beta \leftarrow \min(\infty, 9) = 9$.
   • Leaf 1: $\beta \leftarrow \min(9, 1) = 1$.
   • Pruning Condition: Since $\beta \le \alpha$ ($1 \le 3$), we prune.
   • Pruned: 5, 6, 4.
5. Evaluate $\text{Min}_5$ (with bounds $\alpha = 3, \beta = +\infty$):
   • Leaf 2: $\beta \leftarrow \min(\infty, 2) = 2$.
   • Pruning Condition: Since $\beta \le \alpha$ ($2 \le 3$), we prune immediately after the first leaf.
   • Pruned: 3, 7, 3, 8.

Theory: Minimax and Alpha-Beta Pruning

Question 6 Solutions

6 (a) Bayes Theorem Application

Given:

• $P(D) = 0.01$ (Probability of disease)
• $P(\sim D) = 0.99$ (Probability of no disease)
• $P(T|D) = 0.99$ (True positive rate)
• $P(\sim T| \sim D) = 0.95$ (True negative rate)
• $P(T| \sim D) = 1 - P(\sim T| \sim D) = 0.05$ (False positive rate)

1. Probability of disease given a positive test $P(D|T)$:

Using Bayes Theorem: $P(D|T) = \frac{P(T|D)P(D)}{P(T)}$ $P(T) = P(T|D)P(D) + P(T| \sim D)P(\sim D) = (0.99 \times 0.01) + (0.05 \times 0.99) = 0.0099 + 0.0495 = 0.0594$ $P(D|T) = \frac{0.0099}{0.0594} = \frac{1}{6} \approx 0.1667 \text{ (or 16.67\%)}$

2. Probability of no disease given a negative test $P(\sim D| \sim T)$:

$P(\sim D| \sim T) = \frac{P(\sim T| \sim D)P(\sim D)}{P(\sim T)}$ $P(\sim T) = 1 - P(T) = 1 - 0.0594 = 0.9406$ $P(\sim D| \sim T) = \frac{0.95 \times 0.99}{0.9406} = \frac{0.9405}{0.9406} \approx 0.9999 \text{ (or 99.99\%)}$

Theory: Decision Theory and Utility

6 (b) Hidden Markov Models (HMM)

i. HMM Graphical Formulation and Tuples

An HMM is formulated using the tuple $\lambda = (S, V, A, B, \pi)$:

• $S = \{A, B, C\}$: Set of hidden states.
• $V = \{X, Y\}$: Set of observable symbols.
• $A$: State transition probability matrix (defines probability of transitioning from state $S_i$ to $S_j$).
• $B$: Emission probability matrix (probability of emitting observation $V_k$ from state $S_i$).
• $\pi$: Initial state probability distribution.

ii. Initial State Distribution ($\pi = [0.5, 0.3, 0.2]$)

• Representation: The probability that the system starts in state $A$ is $0.5$, state $B$ is $0.3$, and state $C$ is $0.2$.
• Role of $\pi$: It anchors the probability calculations at step $t=1$. A highly biased initial distribution can steer the HMM's early predictions towards the highly probable state, requiring stronger emission evidence to override it.

iii. Markov Chain vs. HMM

• Difference: In a Markov Chain, the states are directly observable to the user. In a Hidden Markov Model, the states are "hidden" (latent), and we can only observe outputs (emissions) that are probabilistically generated by the hidden states.
• Markov Property: The state transition probability depends only on the current state and not on the history of states. In HMMs, this simplifies the calculations of the joint probability of state sequences.

iv. Three Fundamental Problems in HMM

1. Evaluation Problem: Given model $\lambda$ and observation sequence $O$, compute $P(O|\lambda)$. Resolved using the Forward or Backward Algorithm.
2. Decoding Problem: Given model $\lambda$ and observation sequence $O$, find the most likely hidden state sequence $S$. Resolved using the Viterbi Algorithm.
3. Learning Problem: Given observation sequence $O$, adjust model parameters $(A, B, \pi)$ to maximize $P(O|\lambda)$. Resolved using the Baum-Welch Algorithm (an Expectation-Maximization approach).

Question 7 Solutions

7 (a) Activation Functions & Gradient Behavior in Neural Networks

Analysis of Stages:

1. Stage 1 (Sigmoid):
   • Issue: Vanishing Gradient Problem. The Sigmoid function $\sigma(z) = \frac{1}{1 + e^{-z}}$ squeezes outputs to $[0, 1]$. Its derivative $\sigma'(z) = \sigma(z)(1 - \sigma(z))$ has a maximum value of $0.25$. As gradients are backpropagated through multiple layers, multiplying these small numbers causes the gradient to decay exponentially, slowing learning in early layers.
2. Stage 2 (ReLU):
   • Issue: Dying ReLU Problem. ReLU $f(z) = \max(0, z)$ has derivative $1$ for $z > 0$ and $0$ for $z < 0$. If a large gradient updates weights such that a neuron receives negative inputs across the entire dataset, its output and derivative become $0$. The neuron becomes inactive and ceases to update.
3. Stage 3 (Leaky ReLU / ELU):
   • Solution: Leaky ReLU $f(z) = \max(\alpha z, z)$ (where $\alpha \approx 0.01$) guarantees a small, non-zero gradient ($0.01$) for negative inputs, preventing neurons from dying while maintaining fast convergence.

Graphs & Derivatives:

   Sigmoid & Derivative             ReLU & Derivative           Leaky ReLU & Derivative
        1.0 |   _.-               1.0 |    /                         1.0 |    /
            | .-'                     |   /                              |   /
   f(z) 0.5 |/            f(z)        |  /              f(z)             |  /
            |                         | /                                | /
        0.0 +------           0.0 ----+------               0.0 ---------+------
             z                         z                             /   z
                                                                    /
        0.25|   _                     |                              |  
   f'(z)    |  / \        f'(z)   1.0 +-------          f'(z)    1.0 +-------
            | /   \                   |                              |
        0.0 +-------                  +------                        +------- 
                                      0.0                            0.01 ===

7 (b) Softmax & Cross-Entropy Calculation

Given logits: $z = [0.2, 2.5, 0.3]$. True Class = Car (Class 0).

1. Softmax Calculation

$P(y = c | z) = \frac{e^{z_c}}{\sum_j e^{z_j}}$

• $e^{0.2} \approx 1.221$

• $e^{2.5} \approx 12.182$

• $e^{0.3} \approx 1.350$

• Denominator sum $= 1.221 + 12.182 + 1.350 = 14.753$

• $P(\text{Car}) = 1.221 / 14.753 \approx \mathbf{0.083}$

• $P(\text{Bike}) = 12.182 / 14.753 \approx \mathbf{0.826}$

• $P(\text{Bus}) = 1.350 / 14.753 \approx \mathbf{0.091}$

2. One-hot encoded true label

$\mathbf{y}_{\text{true}} = [1, 0, 0]$

3. Cross-Entropy Loss

$L = - \sum_c y_c \ln(P_c) = -1 \cdot \ln(P(\text{Car})) = -\ln(0.0828) \approx \mathbf{2.491}$

4. Interpretation

The loss value is high ($2.491$) because the model predicted the incorrect class (Bike) with high confidence ($82.6\%$) while allocating only a $8.3\%$ probability to the correct class (Car). This penalty reflects the model being "confident and wrong."