Artificial Intelligence
The field in its full breadth: agents that perceive, reason, and act. Search, knowledge, planning, and learning, and the question of what counts as intelligent behaviour.
Learning paths (11)
AI Search and Game Theory
Deciding what to do when another agent is deciding too: optimal play against an adversary, pruning the search, and equilibrium when interests only partly conflict.
Reinforcement Learning
Acting well when outcomes are uncertain: the Bellman equation and how to solve it, then what changes when the environment is unknown and the agent has to learn from experience alone.
Logic and Knowledge Representation
The other tradition in artificial intelligence: representing what a system knows as sentences that are true or false, and deriving what must follow - with guarantees a learned model cannot offer.
Search and Heuristics
The oldest working idea in artificial intelligence: describe a problem as states and actions, then let a systematic exploration find the path. Which strategy you pick decides whether the answer is optimal, and whether you run out of memory before you find it.
Probabilistic Reasoning with Bayesian Networks
Represent a joint distribution over many variables with a graph and a handful of small tables, then answer queries against it exactly when the structure allows and by sampling when it does not.
Probabilistic Reasoning over Time
Track a world that changes while you watch it through a noisy sensor: the two assumptions that make it tractable, the forward and backward recursions that answer every query about the past and present, and the separate algorithm needed for the most likely history.
Constraint Satisfaction
Describe a problem as variables, domains and constraints, and a general solver can attack it without knowing what it is about - provided you let it reason about the constraints instead of only guessing values.
Making Decisions under Uncertainty
Combine what you believe with what you want: expected utility as the criterion, the curve that explains why sensible people refuse favourable bets, and a price for information that is zero unless it changes your mind.
Classical Planning
Describe actions by what they change and a solver can read the description itself: the same schemas that define the problem also generate the heuristics that solve it, which is something no black-box search can offer.
Learning Probabilistic Models
When the data are complete, learning a probability model is counting - the derivative of the log likelihood does the rest. When variables are hidden there is nothing to count, and the repair is to guess the counts, refit, and repeat until the likelihood stops rising.
Decisions Under Partial Observability
An agent that cannot see which state it is in has to act on a distribution instead. That distribution is itself always observable, which turns the problem back into an MDP - over a continuous space, on which the exact algorithms do not close.
Encyclopedia (21)
Bayesian Network
A directed acyclic graph whose nodes are random variables and whose edges express direct influence, with a conditional probability table at each node, that together define a full joint distribution as a product of local factors.
Decision Tree
A model that predicts by applying a sequence of threshold tests on individual features, splitting the data into increasingly homogeneous groups.
Hidden Markov Model
A temporal model in which a single discrete state variable evolves as a Markov chain and emits one observation per time step, so the state must be inferred from a noisy proxy rather than seen directly.
Expectation–Maximization
An iterative method for maximum-likelihood estimation when some variables are unobserved: it computes the posterior distribution over the hidden variables under the current parameters, then refits the parameters as though those expected counts had been observed.
Belief State
The probability distribution an agent holds over the states it might be in, given everything it has done and perceived - the thing it can act on when the state itself is hidden.
Partially Observable MDP
A Markov decision process in which the agent cannot observe its state directly, only noisy percepts of it - solved in principle by treating the distribution over states as the state of an ordinary, fully observable MDP.
Neural Network
A model composed of layers of simple units, each computing a weighted sum followed by a non-linear function, fitted by gradient descent using backpropagation.
Constraint Satisfaction Problem
A problem stated as a set of variables, a domain of permitted values for each, and constraints restricting which combinations of values may be taken simultaneously, so that a general solver can reason about its structure without any domain knowledge.
Markov Decision Process
A formal model of sequential decision-making in which outcomes are partly random, defined by states, actions, transition probabilities, and rewards.
A* Search
A best-first graph search that expands the node minimizing the sum of the cost already incurred and an estimate of the cost remaining.
Expected Utility
The probability-weighted average utility of an action’s possible outcomes, and the quantity a rational agent maximises when choosing what to do under uncertainty.
Automated Planning
Finding a sequence of actions that achieves a goal, where states are sets of ground fluents and actions are schemas describing only what they change.
Planning Graph
A layered structure alternating literal levels and action levels, annotated with mutual-exclusion links, that bounds in polynomial time what a planning problem can achieve by a given step.
First-Order Logic
A formal language for representing knowledge in terms of objects, their properties and relations, and quantification over them.
Minimax
A decision rule for two-player zero-sum games in which each player chooses the move maximizing their own worst-case outcome against optimal opposition.
Kalman Filter
The exact filtering algorithm for a continuous state that moves linearly with Gaussian noise and is measured linearly with Gaussian noise, carrying the whole belief as a mean and a variance.
Viterbi Algorithm
A dynamic programming algorithm that finds the single most likely sequence of hidden states given a sequence of observations, by carrying forward the best path to each state rather than the total probability of reaching it.
Softmax
A function that turns a vector of real scores into a probability distribution by exponentiating each score and dividing by the total, preserving their order while making them positive and summing to one.
Perplexity
The exponential of a model’s average cross entropy, read as the number of equally likely options it is effectively choosing between at each step.
Bellman Equation
The self-consistency condition that the utility of a state equals its immediate reward plus the discounted value of the best action available from it, averaged over the outcomes that action cannot control.
Arc Consistency
A property of a constraint problem in which every value in every variable’s domain has at least one supporting value in each neighbouring domain, and the algorithm that enforces it by deleting the values that do not.
Articles (20)
The Week That Cannot Have Happened
Take the most likely state on each day and write them down in order, and you have a report the model assigns probability exactly zero: on a four-day machine-monitoring example the day-by-day answer is healthy, healthy, failed, failed, and healthy to failed is a transition that cannot occur. What the two questions actually are, why smoothing and Viterbi answer different ones, and what the 0.411 posterior on the best path means for anyone who has to act on it.
The Parameter Nobody Chooses
The living reward in a grid world is written down once and never discussed, and the optimal policy is a step function of it: eight thresholds between -3 and 0, each flipping exactly one square. The textbook value of -0.04 sits 0.0048 away from the one that decides whether the agent takes the shortcut past the pit, and above -0.0221, when steps are nearly free, the optimal move in one corner is to walk into a wall on purpose.
The Fix That Changed the Success Rate Far More Than the Cost
Allowing sideways moves takes hill climbing on 8 queens from 14.75% of runs solved to 94.55%, which reads like a six-fold improvement and is not one: with random restarts the expected cost of a solution goes from 21.9 steps to 23.1, and counted in moves evaluated it falls by 16%, from 1,547 to 1,298. Simulated annealing solves 98.8% and costs 1,622 evaluations. What changed was mostly the statistic, not the work.
A Million Clauses, or Sixty-One
Converting one short formula to conjunctive normal form by distributing gives 1,048,576 clauses and 20,971,520 literals; naming the subformulas gives 61 clauses and 160 literals, a factor of 131,072 in literals, and loses nothing at all - the two have the same number of models, checked exhaustively. The encoding is where a satisfiability problem is won or lost, not the solver.
A Hundred Thousand Samples, Four Hundred of Them Real
On the burglary network with both neighbours calling, rejection sampling keeps 183 of 100,000 draws and likelihood weighting keeps all of them at an effective sample size of 396. Both estimates are about 10% off a posterior of 0.284172, and the reason is exactly computable: 252 samples carry 76% of the weight and 99.975% of the squared weight.
Learning the Numbers in a Probability Model
Where the numbers in a Bayesian network or a Gaussian actually come from: the three-step maximum-likelihood recipe worked through on discrete and continuous parameters, the Beta prior that repairs what it does to an unseen event, naive Bayes and the single zero count that destroys it, and the EM algorithm for the case where the counts cannot be taken at all - with every figure computed rather than asserted.
Acting When You Cannot See the State
What changes when an agent gets noisy percepts instead of its state: the belief state that replaces it and the filtering update that maintains it, the exact reduction of a POMDP to an MDP over beliefs, the piecewise-linear convex value function that makes the reduction computable in principle, and the measured reasons it is not computable in practice - with the fixed point of belief, the alpha vectors and the value function all computed rather than asserted.
Decisions under Uncertainty: Utility and Information
Why a bet with positive expected monetary value can be rational to refuse, what the curvature of a utility function measures, and how to price an observation before buying it - including the common case where the honest price is zero.
Constraint Satisfaction and Propagation
What changes when you describe a problem as variables, domains and constraints instead of as a black box: commutativity that shrinks the tree for free, propagation that proves branches hopeless before searching them, and a measurement showing the most famous ordering heuristic does nothing on its own.
Classical Planning: Schemas, Relaxations and Graphs
Why planning gets its own representation rather than being a footnote to search, how deleting parts of an action description produces a heuristic for free, and what a planning graph notices that per-goal heuristics systematically miss.
Reasoning About a Changing World
How two Markov assumptions turn an unbounded history into two small tables, the forward and backward recursions that answer every question about the present and the past, why the most likely sequence needs an algorithm of its own, and what changes when the state is a real number rather than a list.
Bayesian Networks and Probabilistic Inference
How a graph and a few small tables stand in for a joint distribution with thousands of entries, how to answer a query against it exactly by enumeration and variable elimination, and what to do when exact inference is out of reach: rejection sampling, likelihood weighting, and Gibbs sampling, each worked through on the same two networks.
Classical Search: From Breadth-First to A*
Turning a problem into a state space and letting an algorithm walk it: what completeness and optimality actually cost, why memory rather than time defeats breadth-first search, and the two conditions on a heuristic that make A* provably optimal.
Probability from Zero: The Language of Uncertainty
Build probability from the ground up: possible worlds, the sample space, the two basic axioms, and the addition and multiplication rules, each derived rather than asserted, with worked numeric examples.
Logic and Knowledge Representation
Reasoning about what must be true: models and entailment worked by exhaustive enumeration, soundness and completeness, why propositional logic runs out of expressive power, and where first-order logic picks up.
Bayes' Theorem and Belief Updating
Derive Bayes' theorem from the definition of conditional probability, then work the base-rate example that fools almost everyone, twice: once with the formula and once by pure counting.
Reinforcement Learning and Q-Learning
Learning to act well without a model of the world: temporal-difference updates, the Q-learning rule, exploration versus exploitation, and a run that recovers the planned optimum from experience alone.
Markov Decision Processes
How to plan when actions do not reliably do what you intend: states, transition models, rewards and discounting, the Bellman equation, and value iteration worked numerically to its fixed point.
Adversarial Search and Minimax
How a program plays a game against an opponent who is trying to beat it: the minimax value, why alpha-beta pruning reaches the same answer while examining fewer nodes, and a game tree pruned move by move.
Game Theory and Nash Equilibrium
Strategic reasoning when players are not strictly opposed: dominant strategies, the prisoner's dilemma worked from its payoff matrix, Nash equilibrium, Pareto optimality, and why equilibrium and efficiency can conflict.
Tools (1)
Research (5)
On Computable Numbers, with an Application to the Entscheidungsproblem
Introduces an abstract machine that reads and writes symbols on a tape according to a finite table of rules, and uses it to show that no general procedure can decide whether an arbitrary program halts.
Programming a Computer for Playing Chess
Lays out how a machine might play chess: represent positions, generate legal moves, search the game tree with minimax, and evaluate non-terminal positions with a heuristic scoring function.
Computing Machinery and Intelligence
Proposes replacing the question "can machines think?" with a behavioural test, in which an interrogator tries to distinguish a machine from a human through written conversation.
The Perceptron: A Perceiving and Recognizing Automaton
Introduces the perceptron, a trainable unit that computes a weighted sum of its inputs and fires if the sum exceeds a threshold, with a rule for adjusting weights from labelled examples.
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Introduces the A* algorithm, which orders search by the sum of the cost already incurred and a heuristic estimate of the cost remaining, and proves it optimal when the heuristic never overestimates.
Projects (2)
Game-Playing Agent
Minimax with alpha-beta pruning over a real game tree, plus an equilibrium solver for small normal-form games - optimal play against an adversary, and against a rational one.
Gridworld RL Lab
Value iteration, policy iteration, and Q-learning on the same gridworld, so a planner that knows the model can be compared directly against a learner that does not.