Artifical Intelligence

Module 1: Search Problems and Uninformed (Blind) Search

A search problem is formally defined by five components: a complete set of possible world states $S$, a successor function $Succ(s)$ yielding possible actions and resulting states, an initial starting state, a goal test, and action costs. The objective is to find an optimal solution, which is a sequence of actions from the initial state to a goal state that minimises the total cost.

Breadth-First Search (BFS):
BFS expands nodes level by level using a First-In-First-Out (FIFO) queue. It is complete and optimal only if action costs are constant. The total number of nodes generated in the worst case is given by the formula:

$$N = 1 + b + b^2 + ... + b^d + (b^{d+1} - b) = O(b^{d+1})$$

where $b$ is the branching factor and $d$ is the depth of the shallowest goal node. Consequently, its space complexity is also $O(b^{d+1})$.

Uniform Cost Search (UCS):
UCS expands the node with the lowest path cost $g(n)$ using a priority queue. It is complete if all step costs are strictly greater than $0$, and it is always optimal. If $C^*$ is the cost of the optimal solution and $\epsilon$ is the minimum action cost, the worst-case time and space complexity is:

$$O(b^{\lceil C^*/\epsilon \rceil})$$

which can be significantly greater than $b^d$.

Depth-First Search (DFS) & Iterative Deepening (IDS):
DFS always expands the deepest node in the current fringe using a Last-In-First-Out (LIFO) stack. It is not complete and not optimal, possessing a time complexity of $O(b^m)$ and a space complexity of $O(bm)$, where $m$ is the maximum path length. Iterative Deepening Search (IDS) mitigates the lack of completeness by repeatedly applying Depth-Limited Search with increasing depth limits. Despite regenerating upper levels multiple times, its asymptotic time complexity remains $O(b^d)$, calculated as:

$$N = (d)b + (d - 1)b^2 + ... + (1)b^d = O(b^d)$$

IDS achieves $O(bd)$ space complexity while ensuring completeness and optimality (for uniform step costs).

Module 2: Informed (Heuristic) Search

Informed search leverages problem-specific knowledge encapsulated in an evaluation function $f(n)$ to estimate a node's promise. A crucial component is the heuristic function $h(n)$, which estimates the cost of the cheapest path from node $n$ to a goal node.

Greedy Best-First Search:
This strategy directly relies on the heuristic function, selecting the node that appears closest to the goal. The evaluation function is:

$$f(n) = h(n)$$

Greedy search is neither complete nor optimal and has a worst-case complexity of $O(b^m)$.

A Search:*
A* search aims to minimise the total estimated solution cost by combining the path cost $g(n)$ and the heuristic $h(n)$. Its evaluation function is:

$$f(n) = g(n) + h(n)$$

A heuristic function is termed admissible if it never overestimates the true cost $h^*(n)$ to the goal:

$$h(n) \le h^*(n)$$

If $h(n)$ is admissible, A* search is guaranteed to be complete and optimal.

Heuristic Dominance & Effective Branching Factor:
If two admissible heuristics $h_1$ and $h_2$ exist, and $h_2(n) \ge h_1(n)$ for all nodes $n$, then $h_2$ strictly dominates $h_1$ and will never expand more nodes than $h_1$. Furthermore, an elegant way of combining heuristics is to take their maximum:

$$h(n) = \max(h_1(n), h_2(n))$$

The performance of a heuristic is measured using the Effective Branching Factor $b^*$, defined by the total number of generated nodes $N$ at solution depth $d$:

$$N + 1 = 1 + b^* + (b^*)^2 + ... + (b^*)^d$$

Module 3: Adversarial Search and Games

In two-player, perfect information, zero-sum games, an agent aims to find an optimal strategy against an infallible opponent.

Minimax and Alpha-Beta Pruning:
The Minimax algorithm computes the best move by assuming the opponent (MIN) will play optimally to minimise the utility of the agent (MAX). Alpha-beta ( $\alpha$ - $\beta$ ) pruning improves the efficiency of Minimax by maintaining two parameters during tree traversal:

• $\alpha$: the best (highest) value found so far for MAX along the path.
• $\beta$: the best (lowest) value found so far for MIN along the path.
  If a minimax value below a MIN node falls below $\alpha$, or a value below a MAX node rises above $\beta$, the remaining subtrees are ignored (pruned).

Monte Carlo Tree Search (MCTS):
MCTS explores the search space without a heuristic function by running random simulations from nodes. It balances the exploitation of promising moves and the exploration of unvisited moves using the UCT (Upper Confidence Bound applied to Trees) formula:

$$UCT(N_i) = \frac{w_i}{n_i} + c \cdot \sqrt{\frac{\ln N}{n_i}}$$

where $w_i$ is the number of wins from node $N_i$, $n_i$ is the number of simulations from $N_i$, $N$ is the total number of simulations from the parent node, and $c$ is the exploration parameter.

Module 4: Reinforcement Learning

Reinforcement Learning (RL) involves an agent learning optimal actions by interacting with an environment, observing states $s_t$, executing actions $a_t$, and receiving immediate rewards $r_t$. A central challenge is the Temporal Credit Assignment Problem due to delayed rewards.

Q-Learning & Temporal Difference (TD):
Q-learning estimates training values $\hat{v}$ through iterative approximations of the $Q(s, a)$ function. The incremental Temporal Difference (TD) update adjusts the current Q-value closer to the newly backed-up target:

$$Q[s, a] \leftarrow Q[s, a] + \alpha \left( r + \gamma \cdot \max_{a' \in \mathcal{A}} Q[s', a'] - Q[s, a] \right)$$

where $\alpha$ is the learning rate, $\gamma$ is the discount factor, and $r + \gamma \cdot \max_{a' \in \mathcal{A}} Q[s', a']$ represents the new experience observation.

Module 5: Propositional Logic and Inference

Propositional logic relies on elementary truth values and proposition symbols connected by logical operators. Logical inference determines whether a sentence $\beta$ is entailed by a knowledge base $\alpha$, denoted as $\alpha \models \beta$.

Standard Inference Rules:

• Modus Ponens: $$\frac{\alpha \Rightarrow \beta, \alpha}{\beta}$$
• AND-Elimination: $$\frac{\alpha \wedge \beta}{\alpha}$$

Logical Equivalences:

• Commutativity: $(\alpha \wedge \beta) \equiv (\beta \wedge \alpha)$
• Double-negation elimination: $\neg(\neg \alpha) \equiv \alpha$
• Contraposition: $(\alpha \Rightarrow \beta) \equiv (\neg \beta \Rightarrow \neg \alpha)$
• Implication elimination: $(\alpha \Rightarrow \beta) \equiv (\neg \alpha \vee \beta)$
• Biconditional elimination: $(\alpha \Leftrightarrow \beta) \equiv ((\alpha \Rightarrow \beta) \wedge (\beta \Rightarrow \alpha))$
• DeMorgan's Laws: $\neg(\alpha \wedge \beta) \equiv (\neg \alpha \vee \neg \beta)$ and $\neg(\alpha \vee \beta) \equiv (\neg \alpha \wedge \neg \beta)$
• Distributivity: $(\alpha \wedge (\beta \vee \gamma)) \equiv ((\alpha \wedge \beta) \vee (\alpha \wedge \gamma))$

Resolution Rule:
A complete inference rule applied to clauses (disjunctions of literals). The Unit Resolution Rule is defined as:

$$\frac{l_1 \vee ... \vee l_i \vee ... \vee l_k, m}{l_1 \vee ... \vee l_{i-1} \vee l_{i+1} \vee ... \vee l_k}$$

where $l_i = \neg m$ or $\neg l_i = m$.
The General Resolution Rule takes two clauses and produces a new resolvent:

$$\frac{l_1 \vee ... \vee l_i \vee ... \vee l_k, m_1 \vee ... \vee m_j \vee ... \vee m_n}{l_1 \vee ... \vee l_{i-1} \vee l_{i+1} \vee ... \vee l_k \vee m_1 \vee ... \vee m_{j-1} \vee m_{j+1} \vee ... \vee m_n}$$

Module 6: Neural Networks and Deep Learning

Modern neural networks utilise gradient descent to optimise parameters by minimising a loss function $E(\theta^{(i)}; \mathcal{D})$ over training data $\mathcal{D}$.

Softmax Normalisation & Categorical Cross-Entropy:
To generalise logistic regression to multiple classes, network outputs must form a valid probability distribution using softmax normalisation:

$$y_i = \sigma(z_i) = \frac{e^{z_i}}{\sum_j e^{z_j}}$$

The corresponding loss function for $k$ classes is Categorical Cross-Entropy, which evaluates the one-hot encoded true classes $y_i$ against the predicted distributions $\hat{y}_i$:

$$E(\theta; \mathcal{D}) = - \sum_{i=1}^N \sum_{j=1}^k y_{ij} \log(\hat{y}_{ij}) = - \sum_{i=1}^N \log(\hat{y}_{i, \text{true}j})$$