Intro to Artificial Intelligence

Module 1: History and Philosophical Foundations

The concept of artificial intelligence dates back to antiquity, such as the mythical bronze automaton Talos built by Hephaistos. The modern computational foundation was shaped by Kurt Gödel's 1931 proof that a sufficiently complex formalization of arithmetic cannot be both complete and consistent, and Alan Turing's 1936 paper showing that some problems are not decidable in finite time. The field of Artificial Intelligence was officially born at the 1956 Dartmouth Conference organized by John McCarthy, Marvin Minsky, Allen Newell, and Herbert Simon.

Philosophically, the debate divides into "Weak AI," which builds agents acting rationally to solve specific tasks without universal intelligence, and "Strong AI," which aims to build universally intelligent agents that can think. A well-known philosophical challenge to Strong AI is John Searle's Chinese Room argument, which counters the Physical Symbol Systems Hypothesis by questioning whether symbol manipulation equates to true understanding.

Module 2: Search and Constraint Satisfaction Problems (CSP)

Search problems require a state description, a state space, and a goal function.

• Simple Exhaustive Search: Generates all possible states sequentially without utilizing heuristics.
• Hill-Climbing (Greedy Local Search): Only keeps a single current state and modifies it via local actions to maximize a heuristic evaluation, suffering from the problem of becoming stuck in local optima.
• Beam Search: Maintains a beam size $k$ representing the number of states tracked, selecting the $k$ best successors at each iteration.

For Constraint Satisfaction Problems (CSPs), efficiency is gained via general-purpose heuristics:

• Minimum Remaining Values Heuristic: Select the variable with the fewest consistent values.
• Degree Heuristic: Select the variable that imposes the most constraints on the remaining unassigned variables.
• Least Constraining Value Heuristic: Select the value that rules out the fewest values in the remaining variables.
• Min-Conflicts Heuristic: Randomly select a conflicted variable and reassign the value that violates the fewest constraints.

Module 3: Game Playing and Adversarial Search

Games represent competitive multi-agent environments necessitating adversarial search. Ernst Zermelo (1912) provided the first formalization of game playing, proving that in deterministic, 2-person, perfect information games, either one player can force a win or both can force a draw.

In zero-sum games, the Minimax principle assumes both players optimize their result; Player 1 maximizes the score while Player 2 minimizes it. Because exhaustive search is intractable for complex games (like Chess with $\approx 10^{123}$ nodes), search is cut off and a heuristic evaluation function estimates the utility of the position.

The linear evaluation function is defined as:

$$EVAL(s) = \sum_{i=1}^n w_i \cdot f_i(s)$$

where $f_i(s)$ is a feature of state $s$ and $w_i$ is its weight.

Module 4: Machine Learning Foundations

Machine learning aims to construct or modify representations of experiences to improve performance on a task $T$ with respect to a measure $P$. Inductive learning attempts to learn an unknown target function $f$ from examples $(x, f(x))$ by finding a hypothesis $h$ such that $h \approx f$.

Artificial Neural Networks:
Networks calculate errors to adjust weights. The squared error $E(\mathbf{x})$ for an output $h(\mathbf{x})$ and target $f(\mathbf{x})$ is defined as:

$$E(\mathbf{x}) = \frac{1}{2} Err^2 = \frac{1}{2} (f(\mathbf{x}) - h(\mathbf{x}))^2 = \frac{1}{2} \left(f(\mathbf{x}) - g\left(\sum_{j=0}^n W_j \cdot x_j\right)\right)^2$$

where $g$ is the activation function and $W_j$ are the weights.

Error minimization utilizes gradient descent to move weights in the direction of the steepest descent:

$$\frac{\partial E}{\partial W_j} = -Err \cdot g'(in) \cdot x_j$$
The perceptron weight update rule with learning rate $\alpha$ is:

$$W_j \leftarrow W_j + \alpha \cdot Err \cdot g'(in) \cdot x_j$$

This requires a continuous, differentiable activation function like the sigmoid function, as the regular threshold function has a derivative of $0$, resulting in no weight changes.

Module 5: Reinforcement Learning and MCTS

Reinforcement learning relies on delayed rewards from the environment, leading to the credit assignment problem. Temporal Difference Learning allows generalization via neural networks, leading to human-level systems like TD-Gammon.

In chance games or extremely complex trees, Monte-Carlo Tree Search (MCTS) incrementally builds a search tree using roll-outs to evaluate leaves. The Upper Confidence bounds applied to Trees (UCT) formula balances exploitation and exploration:

$$s_{max} = \arg\max_{s \in Successors(n)} value(s) + C \cdot \sqrt{\frac{\ln \#visits(n)}{\#visits(s)}}$$

where $C$ is the trade-off parameter.

Module 6: Planning

Planning utilizes explicit representations of states, actions, and goals using logical calculus. The STRIPS (STanford Research Institute Problem Solver) language decomposes states into conjunctions of positive grounded, function-free literals. STRIPS actions define preconditions, an add list, and a delete list.

• Progression Algorithm: Forward state-space search starting from the initial state.
• Regression Algorithm: Backward state-space search starting from the goal state, heavily reducing the branching factor by only considering relevant actions.
• Sussman Anomaly: Demonstrates that subgoals are not strictly independent. Achieving one subgoal (e.g., $on(b,c)$ ) may necessitate undoing it to achieve a second subgoal ( $on(a,b)$ ).
• Partial-Order Planning (POP): Delays sequencing actions unless necessary (least commitment strategy), utilizing causal links and ordering constraints to resolve conflicts.

Module 7: Natural Language Processing

NLP requires overcoming ambiguities across word, syntax, and semantic levels. The Bag of Words model assumes a document is generated by repeatedly drawing words independently. The Simple Naïve Bayes Classifier assigns the most probable class $c$ to document $d$:

$$c = \arg\max_c \prod_{i=1}^{|d|} p(t_i|c) \cdot p(c)$$

where $p(t_i|c)$ is the probability of term $t_i$ occurring in class $c$.