26-2023

Question 1

1 a) "If we are going to say that a given program thinks like a human, we must have some way of determining how humans think. We need to get inside the actual workings of human minds." — Which methods, according to the cognitive modeling approach, may we use to accomplish this? [4.5]

b) The utility function and the performance measure both assess how well an agent is performing. Explain the difference(s) between the two. Explain why problem formulation must follow the goal formation. [4.5]

c) Prove each of the following statements or give a counterexample. [5]

• i. Breadth-first search is a special case of uniform-cost search.
• ii. Depth-first search is a special case of best-first tree search.
• iii. Uniform-cost search is a special case of A* search.

---

Question 2

2 a) In this question, we focus on solving a large-scale n-queen Constraint Satisfaction Problem (CSP). The initial task involves detailing a strategy for solving the problem with 1000 queens using the backtracking algorithm. Furthermore, we seek to address the solution for a million-queen CSP. Considering the crucial roles of initial queen placement and memory management, efficient approaches are presumed available to mitigate these challenges. Given these provisions, outline an algorithm capable of solving the million-queen problem in approximately a few seconds, or explain why achieving such a solution is impractical.
Note: Omit pseudo-code; focus on discussing the core concept briefly. [2+2]

b)

$\text{Figure: Question 2(b)}$ $\text{For } S_0: t_0 = 43, n_0 = 2$ $\text{For } S_1: t_1 = 25, n_1 = 1$ $\text{For } S_2: t_2 = 18, n_2 = 1$

• i) For an adversarial search setting, you are given the above snapshot of the running calculation of the MCTS method. Starting from this point, you need to proceed with the method and complete two more rollouts (i.e., 40 and 20), and then find out the strategy. Note that, if you are to make a random choice always prefer the right node, and with the increase in game tree depth, the action choices for each node increase by 1. [6+2+2]
• ii) Briefly describe the process of a rollout and mention how many operations (within the rollout phase) are needed to perform to obtain the given rollout values (40 and 20).
• iii) Compare Alpha-Beta pruning and MCTS algorithm's applicability considering the nature of heuristic functions and randomness.

---

Question 3

3 a) "The early Perceptron Learning Rule is typically associated with threshold activation functions, leading to binary outputs. In contrast, the Delta Rule can be used with neurons that have continuous and differentiable activation functions." In this context, compare them in terms of error propagation, problem suitability, and applicability in dealing with non-linear separability. [3+6]

Consider a neural network that generates logits [5.5, 2.9, 3.2, 0.8] for classes A, B, C, and D, respectively. First, apply the softmax activation function to these logits. Then, determine with reasoning which encoding scheme is appropriate for this scenario, given that there is no inherent superiority or inferiority among the classes. Given that the true class label is B, use the multiclass cross-entropy function to calculate the loss. Finally, analyze and comment on the model's performance based on the computed loss.

b) i) "Backpropagation is a general optimization algorithm used to minimize the loss function similar to what you have used in the previous question." Is this statement correct? Defend your stance. In any case, what information is obtained from backpropagation? Mention in words and mathematically how gradient descent utilizes this information. [3]

• ii) In the context of neural networks, an iteration refers to a single update of the model's parameters using a subset of the training data known as a batch. An epoch is one complete pass through the entire training dataset, during which the model's parameters are updated multiple times (once for each batch) to learn from all training examples. [2]
  In which of the three types of Gradient Descent algorithms are an iteration and an epoch the same? Explain why this is the case for the algorithm you choose, and why it is not the case for the other two algorithms.

---

Question 4

4 a) Discuss the notion of expressiveness within the context of propositional, First Order Predicate Logic (FOPL), and Higher Order Predicate Logic. Use the rules of chess to clarify your point. [2+6]

b) Consider the following statements:

• Everyone who loves all animals is loved by someone.
• Anyone who kills an animal is loved by no one.
• Jack loves all animals.
• Either Jack or Curiosity killed the cat, who is named Tuna.

Now, you need to use all the steps of the resolution inference process to prove whether the following statement is true or not: "Jack killed the cat". To make it easier for you, we express the original sentences, some background knowledge and the negated goal G in the first-order predicate logic. You have to explicitly show the CNF version of the problem, and then show the resolution graph.

A. $\forall x [\forall y \text{ Animal}(y) \implies \text{Loves}(x, y)] \implies [\exists y \text{ Loves}(y, x)]$
B. $\forall x [\exists z \text{ Animal}(z) \land \text{Kills}(x, z)] \implies [\forall y \neg\text{Loves}(y, x)]$
C. $\forall x \text{ Animal}(x) \implies \text{Loves}(\text{Jack}, x)$
D. $\text{Kills}(\text{Jack}, \text{Tuna}) \lor \text{Kills}(\text{Curiosity}, \text{Tuna})$
E. $\text{Cat}(\text{Tuna})$
F. $\forall x \text{ Cat}(x) \implies \text{Animal}(x)$
G. $\neg\text{Kills}(\text{Jack}, \text{Tuna})$

c) (Mislabeled as b in the exam paper) $\text{Figure: Question 4(c)}$

Assume that the driving speed is the combination of the output of the following rules:

• If it's Sunny and Warm, drive Fast
  $\text{Sunny (Cover)} \land \text{Warm (Temp)} \implies \text{Fast (Speed)}$
• If it's Cloudy and Cool, drive Slow
  $\text{Cloudy (Cover)} \land \text{Cool (Temp)} \implies \text{Slow (Speed)}$

The above three figures can be used to determine the degree of membership for the respective fuzzy set. Use the fuzzy inference process to determine the precise driving speed if the temperature is $60\text{ F}^\circ$ and $30\%$ cloud cover. You must show all the steps in so doing. [6]

---

Question 5

5 a) Discuss how the Markov Property simplifies the computational complexity of solving a Markov Decision Process (MDP). Start by mathematically defining the Markov Property within the context of the transition function. Then, compare this with a scenario where the Markov Property does not hold. [4]

b) Consider a hypothetical scenario with four states and three actions per state, where State 4 serves as the goal state. Below is a sample reward table, $R(s,a)$, for each state and action. [4+2+4]

The following table shows the updated Q-values for each state-action pair after a certain number of iterations:

• i) What would the updated Q-values be if actions A, B and C are selected from states 1, 2, and 3, respectively, with a learning rate $\alpha = 0.1$ and a discount factor $\gamma = 0.9$? You need to provide detailed calculations for each update.
• ii) If we stop iterating at this stage, what policy would the Q-learning algorithm select based on the Q-values?
• iii) What is the impact of $\epsilon$-greedy policy on the overall process of Q-learning? In Question 5b(i), which part of the calculations would be affected if the $\epsilon$-value were significantly different?

---

Question 6

Assume we are trying to learn a decision tree. Our input data consists of N samples, each with k attributes ($N \gg k$). We define the depth of a tree as the maximum number of nodes between the root and any of the leaf nodes (including the leaf, not the root).

a) If all attributes are binary, what is the maximal number of leaf (decision) nodes that we can have in a decision tree for this data? What is the maximum possible depth of a decision tree for this data? [4]

b) If all attributes are continuous, what is the maximum number of leaf nodes that we can have in a decision tree for this data? What is the maximum possible depth for a decision tree for this data? [5]

c) When using a single link what is the maximal possible depth of a hierarchical clustering tree for binary data? What is the maximum possible depth of such a hierarchical clustering tree for continuous data? [5]

---

Question 7

7 a) Explain the terms subjective probability and conditional independence. When is Bayesian learning appropriate? Elaborate. [4]

b) A doctor knows that the disease meningitis causes the patient to have a stiff neck, say $50\%$ of the time. The doctor also knows some unconditional facts: the prior probability that a patient has meningitis is $1/50000$ and the prior probability that any patient has a stiff neck is $1/20$. Find the probability of a patient with a stiff neck to have meningitis. [6]

c) Consider the following joint probability distribution: [4]

Calculate the following:

• i) $P(\text{Toothache})$
• ii) $P(\text{Cavity})$
• iii) $P(\text{Toothache} \mid \text{cavity})$
• iv) $P(\text{cavity} \mid \text{toothache} \lor \text{catch})$