26-2023 Solutions

Detailed, step-by-step textbook-grade solutions with course theory links for the 4th Year 1st Semester Final Examination (2023).

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

Question 1 Solutions

1 a) Human Cognition Modeling Methods

According to the cognitive modeling approach, we must have a way of determining how human minds actually work. The three primary methods used to accomplish this are:

Introspection: Capturing our own thoughts as they occur (self-observation of cognitive processes).
Psychological Experiments: Observing a person performing specific cognitive tasks in controlled laboratory environments.
Brain Imaging: Using neuroimaging techniques (like fMRI, EEG, or PET scans) to observe the active physical brain during cognitive processing.

Theory: Intelligent Agents and Environments

1 b) Performance Measure vs. Utility Function

Differences:
- A Performance Measure is an external criterion (defined by the designer or an outside observer) used to evaluate the success of the agent's behavior in the environment. For example, a vacuum agent is judged by the amount of dirt it collects.
- A Utility Function is an internal evaluation metric used by the agent to map states to real numbers, representing how "happy" or preferred a state is. It allows the agent to make trade-offs between conflicting goals (e.g., speed vs. safety).
Why Problem Formulation follows Goal Formation: Goal formation defines the destination (what states are acceptable). Problem formulation is the process of deciding what actions and states to consider in service of achieving that goal. Without a goal, the agent has no criteria for identifying relevant states or actions, causing the search space to be infinitely large.

Theory: Problem Solving and Search

1 c) Search Equivalency Proofs

i. Breadth-first search (BFS) is a special case of uniform-cost search (UCS):
- Proof: UCS expands nodes in order of increasing path cost $g(n)$ . If the step cost $c(n, a, n')$ for every transition is set to a constant value $d > 0$ , the path cost of any node at depth $k$ becomes: $g(n) = k \cdot d$ Under these conditions, UCS will always expand nodes of depth $k$ before depth $k+1$ , which is the exact node expansion sequence of BFS.
ii. Depth-first search (DFS) is a special case of best-first tree search:
- Proof: Best-first tree search selects the node with the minimum evaluation value $f(n)$ from the open list. If we define: $f(n) = -depth(n)$ the deepest node in the tree will always have the lowest $f(n)$ score and will be expanded first. This matches DFS exactly.
iii. Uniform-cost search (UCS) is a special case of A search:*
- Proof: A* search evaluates nodes using $f(n) = g(n) + h(n)$ . If the heuristic function is set to zero for all nodes ( $h(n) = 0$ for all $n$ ), the evaluation function simplifies to: $f(n) = g(n)$ which is identical to the node evaluation metric of UCS.

Theory: Heuristic Functions and Optimality

Question 2 Solutions

2 a) Large-Scale n-Queens Constraint Satisfaction (CSP)

Backtracking Strategy for 1,000 Queens: Using simple backtracking has an exponential time complexity of $O(N!)$ $O (N!)$ , which is completely intractable. To solve $N=1000$ $N = 1000$ queens, we must combine backtracking with CSP heuristic improvements:
1. MRV (Minimum Remaining Values): Choose the column with the fewest remaining unthreatened rows to place the next queen (fail-first).
2. LCV (Least Constraining Value): Choose the row that rules out the fewest choices for queens in remaining columns (succeed-first).
3. Forward Checking: Propagate constraints after every queen placement, immediately backtracking if any column's domain becomes empty.
Solving 1 Million Queens in a Few Seconds: A systematic backtracking approach is impossible for 1 million queens due to exponential state expansion. Instead, we use a Local Search algorithm utilizing the Min-Conflicts heuristic:
1. Greedy Initialization: Place one queen per column randomly such that the initial conflicts are minimized.
2. Iterative Repair (Min-Conflicts):
  - While conflicts exist:
    - Select a conflicted queen (column) randomly.
    - Move the queen to a row in the same column that minimizes conflicts (ties broken randomly).
- Because the initialization step gets the board extremely close to a conflict-free layout, min-conflicts solves the remaining constraints in $O(N)$ expected steps, completing in under a second for $N=1,000,000$ .

Theory: Backtracking and Local Search for CSPs

2 b) Monte Carlo Tree Search (MCTS)

i) Tracing Two Rollouts (40 and 20): Initially, the search tree is in the following state:
- $S_0: t_0=43, n_0=2$
- $S_1: t_1=25, n_1=1$
- $S_2: t_2=18, n_2=1$
Using UCB1 selection: $\text{UCB1}(S_i) = \frac{t_i}{n_i} + C \sqrt{\frac{\ln(N)}{n_i}}$
- Rollout 1: Both child nodes have been visited once. Exploitation value for $S_1 = 25/1 = 25$ $S_{1} = 25/1 = 25$ , and for $S_2 = 18/1 = 18$ $S_{2} = 18/1 = 18$ . For any standard exploration parameter $C$ $C$ , $\text{UCB1}(S_1) > \text{UCB1}(S_2)$ $UCB1 (S_{1}) > UCB1 (S_{2})$ since $25 > 18$ $25 > 18$ . We select $S_1$ .
  - Simulation from $S_1$ : Rollout yields value 40.
  - Backpropagation:
    - $n_1 \leftarrow n_1 + 1 = 2$
    - $n_0 \leftarrow n_0 + 1 = 3$
    - $t_1 \leftarrow t_1 + 40 = 65$
    - $t_0 \leftarrow t_0 + 40 = 83$
- Rollout 2: We re-evaluate UCB1 for both children with the new values ( $N = n_0 = 3$ $N = n_{0} = 3$ ):
  - $\text{UCB1}(S_1) = \frac{65}{2} + C \sqrt{\frac{\ln(3)}{2}} = 32.5 + C \cdot 0.741$
  - $\text{UCB1}(S_2) = \frac{18}{1} + C \sqrt{\frac{\ln(3)}{1}} = 18 + C \cdot 1.048$ For standard $C = \sqrt{2} \approx 1.414$ : $\text{UCB1}(S_1) \approx 32.5 + 1.05 = 33.55$ $\text{UCB1}(S_2) \approx 18 + 1.48 = 19.48$ Since $\text{UCB1}(S_1) > \text{UCB1}(S_2)$ , we select $S_1$ again.
  - Simulation from $S_1$ : Rollout yields value 20.
  - Backpropagation:
    - $n_1 \leftarrow n_1 + 1 = 3$
    - $n_0 \leftarrow n_0 + 1 = 4$
    - $t_1 \leftarrow t_1 + 20 = 85$
    - $t_0 \leftarrow t_0 + 20 = 103$
- Strategy Recommendation: We compare the final win-rate (exploitation) value: $\bar{X}_1 = \frac{85}{3} \approx 28.33$ $\bar{X}_2 = \frac{18}{1} = 18.00$ The optimal strategy is to select action $a_1$ .
ii) Rollout Process & Operation Count:
- A rollout is a simulation phase where moves are selected using a fast default policy (e.g. random actions) from the selected leaf node until a terminal state is reached.
- Operations count: With $D$ as the depth of rollout, we execute $D$ state transitions. Because the number of actions increases by 1 at each depth step, evaluating choices at depth $d$ requires scanning $k + d$ actions.
iii) Alpha-Beta Pruning vs. MCTS:
- Alpha-Beta Pruning: Relies on a static heuristic evaluation function to estimate the utility of cut-off states. It is highly sensitive to the quality of this function. If a reliable heuristic cannot be hand-crafted (e.g., in Go), it performs poorly.
- MCTS: Does not require a hand-crafted static evaluation function. It uses statistical simulation rollouts to estimate values. It scales well to high-branching factor games and handles stochastic transitions natively.

Theory: Monte Carlo Tree Search

Question 3 Solutions

3 a) Perceptron vs. Delta Rule & Softmax Loss

Perceptron Learning Rule vs. Delta Rule:
- Error Propagation: The Perceptron uses a discontinuous step threshold function; because its derivative is zero everywhere (except at 0 where it is undefined), standard backpropagation of error gradients is impossible. The Delta Rule uses a continuous and differentiable activation function (like sigmoid or linear), allowing the gradient of the error to be mathematically propagated using derivatives.
- Problem Suitability: The Perceptron is suitable only for classifying linearly separable problems. The Delta Rule is suitable for non-linearly separable problems as well, converging to a minimum mean squared error (MSE) linear boundary (regression line) without oscillating.
- Non-linear Separability: Neither a single perceptron nor a single delta-rule neuron can solve non-linearly separable problems (like XOR) directly without transforming inputs or stacking them into multi-layer networks.

Logits Softmax & Cross-Entropy Calculation

Given logits: $z = [5.5, 2.9, 3.2, 0.8]$ for classes $[A, B, C, D]$ .

Compute Softmax Probabilities: $P(y = c) = \frac{e^{z_c}}{\sum_j e^{z_j}}$ $P (y = c) = \frac{e ^{z_{c}}}{\sum _{j} e ^{z_{j}}}$
- $e^{5.5} \approx 244.692$
- $e^{2.9} \approx 18.174$
- $e^{3.2} \approx 24.533$
- $e^{0.8} \approx 2.226$
- Denominator Sum $= 244.692 + 18.174 + 24.533 + 2.226 = 289.625$
- $P(A) = \frac{244.692}{289.625} \approx \mathbf{0.845}$
- $P(B) = \frac{18.174}{289.625} \approx \mathbf{0.063}$
- $P(C) = \frac{24.533}{289.625} \approx \mathbf{0.085}$
- $P(D) = \frac{2.226}{289.625} \approx \mathbf{0.008}$
Encoding Scheme: One-hot encoding (class B $= [0, 1, 0, 0]$ ) is appropriate because the classes are categorical and have no ordinal relationship or hierarchy.
Cross-Entropy Loss (True class is B): $L = - \sum_c y_c \ln(P_c) = -\ln(P(B)) = -\ln(0.0627) \approx \mathbf{2.77}$
Performance Analysis: The loss of 2.77 is high. The model predicted Class A with high confidence ( $84.5\%$ ) but allocated only $6.3\%$ probability to the true class (B). The model is "confident and incorrect," indicating poor performance on this sample.

3 b) Backpropagation & Gradient Descent

i. Is Backpropagation an Optimization Algorithm?
- No, this is incorrect. Backpropagation is a gradient calculation algorithm, not an optimizer. It uses the Chain Rule to compute the partial derivatives of the loss function with respect to the weights ( $\frac{\partial L}{\partial w}$ ). The actual optimization (adjusting the weights) is performed by an optimizer like Gradient Descent.
- Gradient Descent Update: $w \leftarrow w - \eta \frac{\partial L}{\partial w}$
ii. Iteration vs. Epoch:
- In Batch Gradient Descent, a single iteration (parameter update) is exactly equal to one epoch (one pass over the entire dataset). This is because the batch size is equal to the size of the entire training set.
- For Stochastic Gradient Descent (SGD) (batch size $= 1$ ) and Mini-batch Gradient Descent (batch size $= M$ ), multiple iterations are required to complete a single epoch.

Question 4 Solutions

4 a) Logical Expressiveness

Propositional Logic: Low expressiveness. Can only represent specific, fixed boolean facts. Expressing the rules of chess requires individual variables for every piece/position/time combination (e.g. $P_{\text{white, pawn, e2, t=1}}$ ), totaling over $10^5$ pages.
First-Order Predicate Logic (FOPL): Higher expressiveness. Introduces objects, relations (predicates), functions, and quantifiers ( $\forall, \exists$ ). The rules of chess can be written in about 1 page by generalizing using variables (e.g. $\forall p, x, t \text{ Piece}(p) \land \text{At}(p, x, t) \implies \dots$ ).
Higher-Order Logic: Highest expressiveness. Allows quantifiers to range over relations and functions themselves (e.g. quantifying over all winning strategies).

Theory: Knowledge-Based Agents and Logic

4 b) Resolution Inference in First Order Logic (FOPL)

The solution to this resolution inference problem is identical to the 2024 exam resolution question. See the detailed CNF conversion and resolution refutation graph in:

Theory: CSE-4101 27-2024 Resolutions Solution

4 c) Fuzzy Inference Driving Speed

Given inputs: Temperature ( $T$ ) = $60\text{ F}^\circ$ and Cloud Cover ( $C$ ) = $30\%$ .

1. Fuzzification (Calculate Degrees of Membership)

Based on the membership function slopes in the fuzzy logic diagram:

Temperature ( $T = 60\text{ F}^\circ$ ):
- Cool: Triangle range $(30, 50, 70)$ . $\mu_{\text{Cool}}(60) = \frac{70 - 60}{70 - 50} = \frac{10}{20} = 0.5$
- Warm: Triangle range $(50, 70, 90)$ . $\mu_{\text{Warm}}(60) = \frac{60 - 50}{70 - 50} = \frac{10}{20} = 0.5$
Cloud Cover ( $C = 30\%$ ):
- Sunny: Trapezoid ending at $50\%$ (1.0 from $0$ to $20$ , linear down to $50$ ). $\mu_{\text{Sunny}}(30\%) = \frac{50 - 30}{50 - 20} = \frac{20}{30} \approx 0.67$
- Partly Cloudy (Cloudy): Triangle range $(20, 50, 80)$ . $\mu_{\text{Cloudy}}(30\%) = \frac{30 - 20}{50 - 20} = \frac{10}{30} \approx 0.33$

2. Rule Evaluation (Mamdani Inference)

Rule 1: Sunny $\land$ Warm $\implies$ Fast (using $\min$ for conjunction): $\alpha_1 = \min(\mu_{\text{Sunny}}(30\%), \mu_{\text{Warm}}(60)) = \min(0.67, 0.5) = 0.5 \implies \text{Fast}$
Rule 2: Cloudy $\land$ Cool $\implies$ Slow: $\alpha_2 = \min(\mu_{\text{Cloudy}}(30\%), \mu_{\text{Cool}}(60)) = \min(0.33, 0.5) = 0.33 \implies \text{Slow}$

3. Defuzzification (Weighted Average / Singleton Method)

Assuming standard singleton values for Speed: Slow = 30 mph, Fast = 70 mph: $z^* = \frac{\sum \alpha_i \cdot z_i}{\sum \alpha_i} = \frac{(0.33 \times 30) + (0.5 \times 70)}{0.33 + 0.5} = \frac{9.9 + 35.0}{0.83} \approx \mathbf{54.1\text{ mph}}$

The precise driving speed is 54.1 mph.

Theory: Fuzzy Expert Systems

Question 5 Solutions

5 a) Markov Property in MDPs

Transition Probability Definition: The probability of transitioning to state $s_{t+1}$ depends only on the current state $s_t$ and action $a_t$ : $P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)$
Complexity Simplification: Without the Markov Property, the state representation must contain the history of all visited states and actions to accurately predict the next state. The state space would expand exponentially to $O(|S|^T)$ (where $T$ is time steps), making MDP calculations intractable. With the Markov Property, the complexity remains polynomial in $|S|$ .
Non-Markovian Scenario: Blackjack played without reshuffling. The probability of drawing a card depends on the history of cards drawn from the shoe, not just the current sum.

5 b) Q-Learning Calculations

Q-update formula: $Q(s, a) \leftarrow Q(s, a) + \alpha \left[ R(s, a) + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$ Given: $\alpha = 0.1, \gamma = 0.9$ . State 4 is the goal state ( $\max_{a'} Q(4, a') = 0$ ).

i. Update Step Calculations

Assuming standard linear grid transitions (taking Action A moves right $s \rightarrow s+1$ , B moves left $s \rightarrow s-1$ , C stays $s \rightarrow s$ ):

State 1, Action A (transitions to State 2):
- $\max_{a'} Q(2, a') = \max(Q(2, A), Q(2, B), Q(2, C)) = \max(0.0, -1.0, 0.5) = 0.5$
- $Q(1, A) \leftarrow -0.5 + 0.1 \left[ 1.0 + 0.9(0.5) - (-0.5) \right] = -0.5 + 0.1 [ 1.95 ] = \mathbf{-0.305}$
State 2, Action B (transitions to State 1):
- $\max_{a'} Q(1, a') = \max(Q(1, A), Q(1, B), Q(1, C)) = \max(-0.5, -0.2, 1.0) = 1.0$
- $Q(2, B) \leftarrow -1.0 + 0.1 \left[ 0.0 + 0.9(1.0) - (-1.0) \right] = -1.0 + 0.1 [ 1.90 ] = \mathbf{-0.810}$
State 3, Action C (transitions to State 3 under stay, or State 4 if C is go-to-goal):
- If C stays in State 3: $\max_{a'} Q(3, a') = \max(5.0, 0.0, -1.0) = 5.0$ . $Q(3, C) \leftarrow -1.0 + 0.1 \left[ -1.0 + 0.9(5.0) - (-1.0) \right] = -1.0 + 0.1 [ 4.5 ] = \mathbf{-0.550}$
- If C transitions to State 4 (Goal): $\max_{a'} Q(4, a') = 0.0$ . $Q(3, C) \leftarrow -1.0 + 0.1 \left[ -1.0 + 0.9(0) - (-1.0) \right] = -1.0 + 0.1 [ 0 ] = \mathbf{-1.000}$

ii. Greedy Policy Selection

We select the action that maximizes Q-value in each state ( $\pi(s) = \arg\max_{a} Q(s, a)$ ):

State 1: $\max(Q(1,A), Q(1,B), Q(1,C)) = \max(-0.305, -0.2, 1.0) = 1.0 \implies$ Action C
State 2: $\max(0.0, -0.81, 0.5) = 0.5 \implies$ Action C
State 3: $\max(5.0, 0.0, -0.55) = 5.0 \implies$ Action A
State 4: $\max(0.0, 0.0, 0.0) = 0.0 \implies$ Action A, B, or C

iii. $\epsilon$ -Greedy Policy Impact

Impact: $\epsilon$ -greedy balances exploration (probability $\epsilon$ of taking a random action) and exploitation (probability $1-\epsilon$ of selecting the greedy action).
Calculation Effect: In Q-learning, the target calculation uses the maximum future Q-value ( $\max_{a'} Q(s', a')$ ) which is off-policy and is unaffected by the exploration value $\epsilon$ . However, if we were using SARSA (on-policy), the target action $a'$ would be chosen using $\epsilon$ -greedy, directly altering the calculations.

Theory: MDPs and Reinforcement Learning

Question 6 Solutions

6 a) Decision Tree with Binary Attributes

Maximal Number of Leaf Nodes: Since we have $k$ binary attributes, we can split along any path at most $k$ times. This forms a full binary tree. The maximal number of leaves is: $\text{Leaves}_{\max} = 2^k$
Maximum Possible Depth: $\text{Depth}_{\max} = k$ (Since each attribute can be split only once along any path, the tree cannot exceed depth $k$ ).

6 b) Decision Tree with Continuous Attributes

Maximal Number of Leaf Nodes: Continuous attributes can be split multiple times along a path using different thresholds. However, we cannot split the data beyond placing each individual sample in its own leaf. Thus, the maximum leaf nodes is bounded by the number of samples: $\text{Leaves}_{\max} = N$
Maximum Possible Depth: In the worst-case scenario where each split isolates exactly 1 sample, the maximum depth is: $\text{Depth}_{\max} = N - 1$

6 c) Hierarchical Clustering Depth

Maximal depth for Binary Data: Single-link hierarchical clustering merges clusters step-by-step. The maximum depth of the resulting dendrogram occurs when clusters are merged in a chain (one-by-one). With $N$ samples, this forms an unbalanced binary tree of depth: $\text{Depth}_{\max} = N - 1$
Maximal depth for Continuous Data: The merging tree structure logic is identical. Thus: $\text{Depth}_{\max} = N - 1$

Question 7 Solutions

7 a) Bayesian Learning Terms

Subjective Probability: The measure of a person's degree of belief or confidence that a given event will occur, based on personal judgment or background experience, rather than frequency statistics.
Conditional Independence: Two variables $X$ and $Y$ are conditionally independent given $Z$ if: $P(X, Y \mid Z) = P(X \mid Z) P(Y \mid Z)$
When is Bayesian Learning Appropriate? It is appropriate when:
1. We have reliable prior knowledge of the domain (priors).
2. The observations are noisy, incomplete, or probabilistic.
3. We want to update model parameters incrementally as new data arrives (posterior updates).

7 b) Meningitis Bayes Theorem

Given:

$P(\text{StiffNeck} \mid \text{Meningitis}) = 0.50$
$P(\text{Meningitis}) = 1/50000 = 0.00002$
$P(\text{StiffNeck}) = 1/20 = 0.05$

We want to find $P(\text{Meningitis} \mid \text{StiffNeck})$ : $P(\text{Meningitis} \mid \text{StiffNeck}) = \frac{P(\text{StiffNeck} \mid \text{Meningitis}) P(\text{Meningitis})}{P(\text{StiffNeck})}$ $P(\text{Meningitis} \mid \text{StiffNeck}) = \frac{0.50 \times 0.00002}{0.05} = \frac{0.00001}{0.05} = 0.0002 \text{ (or } 0.02\%\text{)}$

The probability of having meningitis given a stiff neck is 0.02% (or $\frac{1}{5000}$ ).

Theory: Decision Theory and Utility

$P(\text{toothache} \lor \text{catch}) = 0.108 + 0.012 + 0.072 + 0.016 + 0.064 + 0.144 = 0.416$
$P(\text{cavity} \land (\text{toothache} \lor \text{catch})) = 0.108 + 0.012 + 0.072 = 0.192$ $P(\text{cavity} \mid \text{toothache} \lor \text{catch}) = \frac{0.192}{0.416} \approx \mathbf{0.4615 \text{ (or 46.15\%)}}$