Artificial Intelligence

Ask ten people what artificial intelligence is and you will get ten answers, most of them about robots or consciousness. Ask a researcher and you will get something much duller and far more useful: a specification of what the system should do, a description of the world it operates in, and a number that says how well it is doing. This lesson replaces the folk question with the working one, because the working question is the only one you can build against.

The big picture

Artificial intelligence is the effort to build machines that take sensible actions to reach goals. Think of it the way you would judge a good taxi driver: not by what is going on inside their head, but by whether they get you there safely and quickly. That shift, from asking "does the machine really think?" to asking "does it act well?", is the single idea that organizes this entire course.

Why it matters: once you measure a machine by the quality of its actions, you can use mathematics to design and compare systems. Every method you will study, whether search, logic, probability, or learning, is a different tool for choosing better actions.

Four ways people have defined AI

The standard textbook by Russell and Norvig sorts historical definitions along two questions. Question one: are we copying a human, or aiming at an ideal standard of correctness? Question two: are we judging thought, or behavior? Crossing those two questions gives four boxes.

	Human-like	Rational (ideal standard)
Thinking	Think like a person (model the mind)	Think correctly (logic, the "laws of thought")
Acting	Act like a person (the Turing Test)	Act to get the best expected result (rational agents)

Modern AI mostly lives in the bottom-right box: build things that act to get the best expected outcome. That is the most useful target because it is precise and does not require the machine to resemble a human.

Key idea: AI is judged by whether a system acts to achieve its goals, not by whether it copies a human mind.

The Turing Test

In 1950 Alan Turing replaced the fuzzy question "can machines think?" with a concrete game he called the imitation game. Picture a judge sitting at a keyboard, chatting by text with two hidden partners: one is a person, one is a program. The judge asks anything and tries to tell which is which. If the judge cannot reliably pick out the machine, the machine is said to be showing intelligent behavior.

The test is clever because it grades behavior you can observe and skips arguments about consciousness. Its most famous objection is John Searle's Chinese Room. Imagine a person locked in a room who does not speak Chinese but has a giant rulebook. Chinese sentences slide under the door, the person looks up matching rules and slides back correct Chinese replies. To someone outside, the room "speaks Chinese." Searle's point: shuffling symbols by a rulebook is not the same as understanding them, so passing the test would not prove real comprehension.

Key idea: the Turing Test measures convincing behavior, which is not the same thing as genuine understanding.

What Turing actually predicted, and why nobody uses the test

Turing's paper is more specific than the popular retelling. He predicted that by roughly the year 2000, a machine with about 10⁹ bits of storage could be programmed so that an average interrogator, after five minutes of questioning, would have no more than a 70 percent chance of correctly identifying it. That is a modest bar - a 30 percent deception rate over five minutes, not sustained indistinguishability from an expert.

The test has essentially vanished from serious research evaluation, for three reasons worth understanding because they generalize to every benchmark you will meet.

• It rewards deception rather than competence. The winning strategy is often to feign typing errors, plead ignorance, or adopt a persona that excuses odd answers - none of which is progress on any capability anyone wants.
• It is unreliable as a measurement. The result depends heavily on the judge's expertise, the time allowed, and the topic. A metric that moves that much with the measurement conditions cannot track a property of the system.
• It is a single pass or fail. Research needs graded measurements that show partial progress, which is why the field now uses task suites with numerical scores instead.

Modern systems produce fluent conversational text that would plausibly fool many judges in a short exchange, and this is genuinely a milestone in text generation. It is not evidence about reasoning, reliability, or understanding, precisely because the test was never designed to isolate those things. Treat "passes for human in conversation" as a claim about one narrow behaviour, not a summary of a system's abilities.

Weak vs. strong, narrow vs. general

Two different splits often get confused, so keep them separate.

• Weak AI means a machine can behave as if intelligent. Strong AI is the stronger claim that the machine literally has a mind and understanding. This is a philosophical distinction about inner states.
• Narrow AI is a system that does one job, like recognizing faces or translating text. Artificial general intelligence (AGI) would flexibly handle almost any task a person can. This is an engineering distinction about breadth.

Every system deployed today, however impressive, is narrow. A model that writes essays cannot also drive your car unless it was separately built to. AGI remains a research goal, not a shipped product.

Key idea: today's AI is narrow (one task at a time), and "acting smart" (weak AI) is a separate claim from "having a mind" (strong AI).

Rationality: the organizing idea

This course adopts the rational agent view from the bottom-right box. A rational agent picks the action expected to score best on a performance measure (a yardstick you define, such as "arrive safely and on time"), given what it currently perceives and knows.

One warning that trips up beginners: rationality is not the same as being right or all-knowing. A rational agent does the best it can with the information it has. If the world hides something from its sensors, a perfectly rational agent can still end up with a bad outcome, and it was not irrational to make the choice it made.

Key idea: a rational agent maximizes expected performance given limited information, so a bad result does not by itself prove the agent was irrational.

Making it concrete: the performance measure does the real work

"Build a rational agent" is not yet a task. Somebody has to write down what counts as doing well, and that specification carries almost all of the difficulty. Take a spam filter, about as unglamorous an agent as exists.

A first attempt at its performance measure might be "maximise the fraction of messages classified correctly." Run the arithmetic on that. If 2 percent of a user's mail is spam, an agent that labels everything as legitimate scores 98 percent accuracy while providing no filtering whatsoever. The measure is satisfied and the product is useless.

Fix it by naming the two error types separately. A false positive sends a real message - a job offer, a medical result - to the spam folder, where it may never be seen. A false negative lets one unwanted advert through, costing the user two seconds. These errors are not remotely equal, and a serious measure must weight them accordingly, perhaps counting one false positive as costing as much as a hundred false negatives. That weight is a value judgement wearing an engineering costume, and no amount of technical skill determines it.

Two more features of the environment shape the design before any algorithm is chosen. Senders adapt to whatever the filter blocks, which makes the world adversarial and means yesterday's accuracy is not evidence about tomorrow's. And the agent's own actions change what it later observes, since messages it silently discards never generate feedback. Both are ordinary properties of deployed systems and both break the comfortable assumption that the world stands still while you evaluate.

This is the general pattern, and it recurs at every scale. An agent scored on watch time will learn to serve whatever holds attention, including material nobody would endorse on reflection - behaving perfectly rationally with respect to the measure it was given. The measure was the mistake. Getting this right is a recurring theme through to Lesson 15, where it reappears under the name alignment.

Key idea: write down the performance measure before choosing an algorithm, and expect it to be the hardest and most consequential part of the design.

Perfect rationality is unattainable, and that is the interesting part

The definition above says "the action expected to score best," which quietly assumes you can compute that action. Usually you cannot. Chess has roughly 10⁴⁰ reachable positions and no machine will ever enumerate them; a driving agent has milliseconds to decide. Real agents must therefore settle for bounded rationality: the best decision reachable with the time, memory, and information actually available.

This reframes the whole field. Almost every technique in this course is a way of getting good-enough decisions under a computational budget - heuristics that avoid exploring the whole search space (Lesson 5), pruning that skips provably irrelevant branches (Lesson 6), independence assumptions that shrink a probability table from exponential to manageable (Lesson 11). None of these would be needed by an agent with unlimited computation. AI is, to a first approximation, the study of what to do when you cannot afford the right answer.

What today's systems actually are

Be precise here, because the surrounding discourse rarely is. Current large models are statistical systems trained to predict continuations of text, then adapted by further training stages. They are extremely capable at producing fluent, contextually appropriate output across an enormous range of topics, and that capability is real and hard-won. They are not databases of verified facts, they have no built-in mechanism that distinguishes true statements from plausible ones, and their performance on a task can change substantially with how a request is phrased.

Two claims are well supported by evidence: these systems perform strongly on many benchmark tasks, and they also produce confident, well-formed statements that are unsupported by any source, a failure mode extensively catalogued in the research literature. Two claims are genuinely contested among serious researchers, and you should treat them as open: whether scaling current architectures leads to general intelligence, and whether these systems perform anything that deserves the word "reasoning" as opposed to sophisticated pattern completion. Reasonable, well-informed people disagree on both, and anyone who tells you either is settled is overstating the evidence.

Key idea: distinguish what these systems demonstrably do, what they demonstrably fail at, and what remains genuinely open - and keep the three categories separate.

Where people get stuck

• "AI means the machine thinks like a human." Modern AI targets good action, not human-like thought. Aeroplanes do not flap, and the analogy is exact: the engineering goal is the capability, not the mechanism.
• "Passing the Turing Test proves understanding." The Chinese Room argues it proves only convincing behaviour. Note the argument's limit too: it targets the inference from behaviour to understanding, not the claim that machines can act intelligently, which Searle does not dispute.
• "We already have general AI." Every deployed system is narrow. Breadth of topics a text model can discuss is not breadth of tasks an agent can perform in the world, and conflating the two is the most common error in public discussion.
• "Rational means never wrong." Rational means the best expected choice given available information, which can still fail when the world hides something. Judge the decision procedure, not the outcome.
• "Rational means optimal." Perfect rationality is usually uncomputable. Real agents are boundedly rational, and the whole toolkit of this course exists to make that bound bite less.
• Skipping the performance measure. An agent with no stated objective cannot be evaluated, and an agent with a badly stated one will optimise exactly the wrong thing while appearing to work.
• Treating benchmark scores as capability claims. A score is evidence about performance on that distribution of inputs. Whether it transfers to your deployment is a separate empirical question, and usually the one that matters.

Recap

• AI builds machines that act to reach goals; we judge them by their actions.
• Russell and Norvig's four definitions split on human-like vs. rational and thinking vs. acting.
• The Turing Test grades behavior; the Chinese Room questions whether behavior implies understanding.
• Narrow vs. general is about breadth; weak vs. strong is about whether there is a real mind.
• Rationality, maximizing expected performance with limited information, is the course's organizing goal.
• Specify PEAS - performance measure, environment, actuators, sensors - before choosing any algorithm; the performance measure is where most real failures originate.
• Perfect rationality is generally uncomputable, so real agents are boundedly rational, and most AI techniques are ways of buying good decisions within a budget.
• Today's large models are strong text predictors that also produce confident unsupported statements; whether they "reason" and whether scaling reaches generality are open, contested questions.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59(236), 433-460. courses.cs.umbc.edu
3. Searle, J. R. (1980). Minds, brains, and programs. Behavioral and Brain Sciences, 3(3), 417-424. doi.org/10.1017/S0140525X00005756
4. Cole, D. (2024). The Chinese Room argument. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
5. Oppy, G., & Dowe, D. (2021). The Turing Test. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
6. Bringsjord, S., & Govindarajulu, N. S. (2018). Artificial intelligence. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
7. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io

In 1965 Herbert Simon, later a Nobel laureate, wrote that machines would within twenty years be capable of any work a human could do. In 1970 Marvin Minsky told a magazine that a machine with general human intelligence was three to eight years away. Both were serious scientists reasoning from real results. Both were badly wrong, and understanding exactly how they went wrong is more useful than any list of dates.

The big picture

Artificial intelligence did not advance in a straight line. It moved in waves: a burst of excitement, a crash when reality fell short, then a comeback built on new ideas or new hardware. Knowing this rhythm is practical, not just historical. It teaches you to read today's headlines with a cool head, because every era believed it was on the verge of solving intelligence.

Why it matters: the same pattern of hype and correction is still with us. Understanding what caused past booms and busts helps you judge which of today's claims are solid and which are getting ahead of the evidence.

A timeline at a glance

Era	What happened
1943 to 1955	Groundwork: model neuron, Turing's paper
1956	Field named at the Dartmouth workshop
1956 to 1969	Early optimism and bold predictions
1970s	First AI winter (methods do not scale)
1980s	Expert systems boom
late 1980s to early 1990s	Second AI winter (brittle systems)
1990s to 2000s	Statistical and machine-learning turn
2012 to present	Deep learning revolution

Key idea: AI's history is a repeating cycle of optimism, disappointment, and renewal, not steady progress.

Founding and early optimism (1943 to 1969)

The groundwork came first. In 1943 McCulloch and Pitts described a simple mathematical model of a neuron, showing brain-like units could compute logic. In 1950 Turing framed how we might test machine intelligence. The field itself got its name at the 1956 Dartmouth workshop, a summer meeting organized by John McCarthy where the phrase "artificial intelligence" was coined.

The early years were giddy. Programs proved geometry theorems, played checkers, and solved algebra word problems, and researchers made confident predictions that human-level AI was just years away. Frank Rosenblatt's perceptron (1958), an early learning machine, could adjust itself from examples to classify simple patterns.

Key idea: the 1956 Dartmouth workshop named the field and launched a wave of optimism fueled by early toy-problem successes.

The first winter (1970s)

Then reality intruded. Techniques that shone on tidy toy problems collapsed on realistic ones, largely because the number of possibilities exploded as problems grew (a "combinatorial explosion," like a chess tree branching out of control). In 1969 Minsky and Papert proved that a single-layer perceptron could not even represent the exclusive-or (XOR) function, a basic logical pattern. That result cooled neural-network research for years. Funding dried up in the first AI winter, a stretch of reduced money and interest.

Key idea: the first winter came when methods failed to scale and the perceptron's limits chilled neural research.

The XOR result, proved

The perceptron limitation is often quoted and rarely demonstrated, so here it is in full. A single-layer perceptron computes a linear threshold function: it outputs 1 exactly when w1*x1 + w2*x2 + b > 0, and 0 otherwise. XOR demands these four input-output pairs:

x1	x2	XOR	Required condition
0	0	0	b <= 0
0	1	1	w2 + b > 0
1	0	1	w1 + b > 0
1	1	0	w1 + w2 + b <= 0

1. From row 2, w2 > -b. From row 3, w1 > -b. From row 1, -b >= 0.
2. Add rows 2 and 3: w1 + w2 + 2b > 0, so w1 + w2 + b > -b.
3. Since -b >= 0, this gives w1 + w2 + b > 0.
4. But row 4 demands w1 + w2 + b <= 0. Contradiction.

No weights exist, for any values whatsoever. Geometrically, the perceptron draws a single straight line and XOR's two positive points sit on a diagonal with the two negatives on the other diagonal - no line separates them.

Now correct the folklore. Minsky and Papert did not claim neural networks were useless; they proved a precise limit on single-layer networks and observed that multilayer networks were more expressive but that no one knew how to train them. That second half was the real obstacle, and it was removed when backpropagation was popularised in 1986, supplying exactly the missing training algorithm. The lesson is not that a book killed a field. It is that a capability gap and a training-algorithm gap are different problems, and confusing them wastes a decade.

What actually ended the funding

Winters were not caused by mood. Three specific evaluations withdrew specific money.

• The ALPAC report (1966) assessed a decade of US machine-translation funding and concluded that fully automatic high-quality translation was not near, and that the output required so much human post-editing that it saved nothing. Machine-translation funding largely stopped.
• The Lighthill report (1973), commissioned by the UK Science Research Council, argued that AI results on toy problems had not transferred to realistic scale, singling out combinatorial explosion as the reason. UK academic AI funding was cut to a few sites.
• US agency cuts in the mid-1970s followed the same reasoning: demonstrations had been impressive, deliverables had not.

The common thread is worth naming, because it recurs: each was a judgement that demonstrated performance on curated problems had failed to transfer to deployment conditions. That is a measurement question, not a hype question, and it is exactly the question to ask of any capability claim you meet today.

Expert systems and the second winter (1980s to early 1990s)

The 1980s brought a commercial comeback in the form of expert systems: programs that captured a human specialist's knowledge as a large set of if-then rules. MYCIN advised on infections, and XCON configured computer orders for a manufacturer. Companies invested heavily. But these systems were brittle: they broke on anything outside their rules, were painful to keep updated, and could not learn from experience. When they underdelivered, a second AI winter set in.

Key idea: expert systems encoded expert knowledge as rules, but their brittleness and inability to learn triggered a second winter.

The statistical and learning turn (1990s to 2000s)

AI regrouped around probability and learning from data instead of hand-written rules. Support vector machines, Bayesian networks, and ensemble methods produced dependable results across many tasks. A landmark moment came in 1997 when IBM's Deep Blue defeated world chess champion Garry Kasparov, mostly through enormous, fast search rather than human-like insight.

Key idea: the field recovered by shifting from hand-coded rules to methods that learn patterns from data.

The deep learning revolution (2012 to present)

Three forces finally lined up at once:

1. Data: huge labeled datasets became available.
2. Compute: graphics processors (GPUs) made training big networks fast.
3. Algorithms: refined training methods let deep networks actually converge.

In 2012 a deep network called AlexNet won the ImageNet image-recognition contest by a wide margin, and the modern era began. The 2017 Transformer architecture then made large language models possible. Progress since has been fast, yet the 1950s questions, what intelligence really is and how to build it safely, are still open.

Key idea: deep learning took off in 2012 because data, GPU compute, and better algorithms converged at the same time.

Three game-playing systems, three different lessons

Comparing the headline game victories shows what actually changed technically, which the dates alone conceal.

• Deep Blue (1997, chess). Alpha-beta search over an enormous number of positions per second, with an evaluation function hand-tuned by human grandmasters. The intelligence about chess lived in the evaluation function, and humans put it there. This is Lesson 6's machinery, scaled up with custom hardware.
• AlphaGo (2016, Go). Go's branching factor makes exhaustive search hopeless, so the evaluation function was learned rather than written - a neural network trained first on human games and then by self-play, guiding a Monte Carlo tree search. The knowledge came from data, not from experts.
• AlphaZero (2017). The same idea with the human games removed entirely: self-play from random initialisation, reaching superhuman play in chess, shogi, and Go with one architecture. The knowledge came from the rules plus computation alone.

The trajectory is the story of the field in miniature: knowledge moves from hand-written rules, to learned-from-human-data, to learned-from-self-generated-data. Each step removed a human bottleneck and increased the compute required. Note what did not change: all three are narrow systems for games with known rules, perfect information, and a clear win condition. Nothing about AlphaZero transfers to a problem where you cannot simulate the environment.

Reading the current moment carefully

Since 2020 the dominant story has been scale. Models grew from hundreds of millions to hundreds of billions of parameters, trained on correspondingly larger text corpora, and capabilities improved substantially on a wide range of benchmarks. That much is well documented in the annual AI Index reports and is not seriously disputed.

What is disputed, and what you should hold as open, is the interpretation. One camp reads the benchmark trend as evidence that continued scaling of current architectures leads toward general capability. Another argues that benchmark gains overstate real progress, pointing to test-set contamination from web-scale training data, to benchmarks saturating without corresponding gains in reliability, and to persistent failures on tasks that require multi-step reasoning outside the training distribution. Both camps include serious researchers with real evidence, and the disagreement is not resolvable from the sidelines.

The historically informed position is neither dismissal nor credulity. Past winters followed periods when demonstrated performance failed to transfer to deployment, and the honest question about any current system is the same one ALPAC and Lighthill asked: does the measured capability hold up under the conditions where it will actually be used? That question is answerable, and it is the one worth asking.

Key idea: each era's collapse was triggered by a transfer failure from curated evaluation to real deployment, which makes "how was this measured?" the most valuable question you can ask about any claim.

Where people get stuck

• "AI has improved steadily since 1956." It advanced in booms and busts, including two funded winters triggered by specific negative evaluations.
• "Neural networks are brand new." The neuron model dates to 1943 and the perceptron to 1958. What is new is the scale of data and compute, not the core idea.
• "Minsky and Papert proved neural networks cannot work." They proved a limit on single-layer perceptrons and noted that multilayer networks lacked a training algorithm. Backpropagation supplied it in 1986.
• "Deep Blue understood chess like a grandmaster." It searched vast numbers of positions using an evaluation function written by humans. AlphaGo learned its evaluation; that is the actual difference.
• "Deep learning succeeded because of one clever idea." It took large labelled datasets, GPU compute, and training refinements together. Remove any one and 2012 does not happen.
• "The winters prove today's progress is also hype." That is the opposite error. The winters show that transfer to deployment is the thing to check - not that every claim is false.
• Reading a benchmark score as a capability. ALPAC's finding was precisely that impressive demonstrations did not survive contact with real use. Ask how the system was evaluated and whether the test data could have leaked into training.

Recap

• Foundations (1943 to 1955) led to the field being named at Dartmouth in 1956.
• Early optimism gave way to the first winter (1970s) when methods failed to scale.
• Expert systems boomed in the 1980s, then a second winter followed their brittleness.
• A statistical, data-driven turn revived the field, capped by Deep Blue in 1997.
• Deep learning took off in 2012 (AlexNet) once data, GPUs, and algorithms aligned.
• XOR is provably beyond a single-layer perceptron, but the real barrier was the missing training algorithm for multilayer networks, supplied by backpropagation in 1986.
• The ALPAC and Lighthill reports ended funding for the same stated reason: performance on curated problems had not transferred to real use.
• Deep Blue used a human-written evaluation, AlphaGo learned one from human games, AlphaZero learned one from self-play alone - all three still narrow systems for simulable games.
• Whether current scaling trends lead to general capability is genuinely contested; the historically grounded question is how a claimed capability was measured.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. McCulloch, W. S., & Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5(4), 115-133. doi.org/10.1007/BF02478259
3. Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386-408. doi.org/10.1037/h0042519
4. Lighthill, J. (1973). Artificial intelligence: A general survey. UK Science Research Council. chilton-computing.org.uk
5. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533-536. doi.org/10.1038/323533a0
6. Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). ImageNet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems, 25. papers.nips.cc
7. Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., ... Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484-489. doi.org/10.1038/nature16961

The big picture

An agent is anything that senses its surroundings and acts on them to pursue a goal. A thermostat, a chess program, a self-driving car, even a person, all fit. This lesson gives you a single vocabulary for describing any such system, so that later tools (search, logic, learning) all have a common frame to plug into.

Why it matters: before you can build something intelligent, you have to state clearly what job it is doing and in what kind of world. The agent framework is that checklist. Get it right and the rest of the course clicks into place.

Sensors, actuators, and the agent function

Every agent runs a simple loop: sense, then act. It takes in information through sensors (a camera, a microphone, a keyboard) and affects the world through actuators (wheels, a speaker, text on a screen). A single reading is a percept; the whole running record is the percept history.

Abstractly, an agent is described by its agent function: a rule that maps any percept history to an action. Think of it as a giant lookup table, "if you have seen this, do that." That table is only a concept; the real thing running on hardware is the agent program. The function says what to do; the program is how it is computed.

Key idea: an agent senses and acts in a loop, and its behavior is captured by an agent function mapping percept histories to actions.

Why the lookup table is only a thought experiment

The agent function as a table is a clarifying fiction, and it is worth seeing exactly how fictional. Take the most impoverished agent imaginable: one binary sensor, sampled once per second, for one hour.

1. The percept history is a string of 3600 bits.
2. The number of distinct such histories is 23600.
3. Convert to base 10: 23600 = 103600 * log10(2) = 103600 * 0.30103, which is about 101084.
4. The observable universe contains on the order of 1080 atoms.

The table for a one-bit sensor over one hour needs roughly 101004 times more entries than there are atoms to build it from. A camera-equipped taxi is unimaginably worse. So the agent function is a specification of what behaviour we want, and the agent program is a compact procedure that produces that behaviour without storing it. Every algorithm in this course is such a compression, and the entire discipline exists because the table does not.

Defining the task: PEAS

To pin down what an agent should do, specify its PEAS: Performance measure, Environment, Actuators, Sensors. Here it is for a self-driving taxi.

Letter	Meaning	Taxi example
P	Performance measure	Safety, speed, legality, passenger comfort
E	Environment	Roads, traffic, pedestrians, weather
A	Actuators	Steering, accelerator, brake, signals
S	Sensors	Cameras, radar, GPS, speedometer

Key idea: PEAS is the four-part specification (Performance, Environment, Actuators, Sensors) that defines an agent's task.

Classifying the environment

How hard the agent's job is depends on the world it lives in. Six standard dimensions describe any environment:

• Fully vs. partially observable: can the sensors see the whole state, or only part of it?
• Deterministic vs. stochastic: does an action always lead to the same next state, or is there randomness?
• Episodic vs. sequential: are decisions independent one-shots, or does now affect later?
• Static vs. dynamic: does the world hold still while the agent thinks, or keep changing?
• Discrete vs. continuous: are states, time, and actions countable, or real-valued?
• Single vs. multi-agent: is the agent alone, or must it reckon with other agents?

Compare two worlds:

Dimension	Chess	Driving a taxi
Observable	Fully	Partially
Deterministic?	Deterministic	Stochastic
Episodic?	Sequential	Sequential
Static?	Static (with a clock, semi-dynamic)	Dynamic
Discrete?	Discrete	Continuous
Agents	Multi-agent	Multi-agent

Driving is harder on almost every axis, which is exactly why it is a far tougher engineering problem than chess.

Push the comparison to both extremes and the framework becomes predictive rather than descriptive. Consider an image classifier at one end and an automated trading agent at the other.

Dimension	Image classifier	Automated trader
Observable	Fully (the image is the entire state)	Partially (other traders' intentions are hidden)
Deterministic?	Deterministic	Stochastic
Episodic?	Episodic (each image independent)	Sequential (positions accumulate)
Static?	Static	Dynamic (prices move while you compute)
Discrete?	Effectively discrete	Continuous (prices, time, quantities)
Agents	Single	Multi-agent and adversarial

The classifier sits in the easy cell of every single dimension, and the trader in the hard cell of every one. That is not a coincidence and it is not hindsight: it predicts, correctly, that supervised image classification would be solved to superhuman accuracy years before reliable autonomous trading or driving. When you meet a new problem, running these six checks tells you roughly how much trouble you are in before you have written a line of code.

One caution about the dimensions: they describe the task as you have modelled it, not the world itself. Chess is fully observable only because we agreed the board is the state; if you also want to model your opponent's fatigue, it becomes partially observable. Choosing where to draw that line is a modelling decision, and drawing it too generously is a common way to build a system that works in simulation and fails in the field.

Key idea: the six environment dimensions predict difficulty, and driving is hard because it is partially observable, stochastic, dynamic, and continuous.

A ladder of agent designs

Agent programs get more capable in five steps:

1. Simple reflex agents react to the current percept with condition-action rules ("if a car brakes ahead, brake"). They fail when the right move depends on history they cannot currently see.
2. Model-based reflex agents keep an internal state, a running estimate of the parts of the world they cannot directly see, updated with a model of how things change.
3. Goal-based agents think ahead: they pick actions that move toward an explicit goal. This is where search and planning enter.
4. Utility-based agents go further with a utility function (a numeric score for how good each outcome is), letting them trade off competing goals and handle uncertainty by choosing the highest expected score.
5. Learning agents improve with experience: a learning element tunes the acting part based on feedback, so performance rises over time.

function SIMPLE-REFLEX-AGENT(percept):
    state = INTERPRET-INPUT(percept)
    rule  = RULE-MATCH(state, rules)     # first matching condition-action rule
    return rule.action

This ladder previews the whole course: search and logic build goal-based agents, probability and decision theory build utility-based agents, and the machine-learning modules build learning agents.

Why memory matters: a reflex agent that cannot stop

The classic demonstration uses a two-square vacuum world. Squares A and B are each Clean or Dirty; the agent perceives its own location and that square's status; actions are Suck, MoveLeft, MoveRight, NoOp. Score it as +1 for each clean square at each time step, -1 for each move.

Consider the simple reflex rule: if the current square is Dirty then Suck, otherwise move to the other square.

1. Start with both squares dirty, agent in A. It sucks A clean, moves to B, sucks B clean. Good so far.
2. Now both squares are clean. The agent perceives "B, Clean" and its rule says move. It goes to A, perceives "A, Clean", and moves back to B. Forever.
3. Score the steady state: two clean squares earn +2 per step, but each move costs -1, so the net is +1 per step.

Now give the agent one bit of memory - a model-based reflex agent that records whether it has seen the other square clean. When both are known clean it chooses NoOp, earning +2 per step with no movement penalty. Over 100 steps the difference is 100 points, and it came entirely from remembering something the sensors could not currently see.

That is the general principle. A reflex agent is optimal exactly when the current percept determines the best action. The moment the right choice depends on anything the sensors cannot see right now - a partially observable environment - internal state is not an optimisation but a requirement.

Why goals are not enough: utilities carry the trade-offs

A goal is a binary test: reached or not. That is fine when there is one way to succeed, and useless when there are several, because a goal cannot rank them. Suppose you must reach the airport and have two routes:

• Route A: 20 minutes, but a 10 percent chance of traffic that makes you miss the flight.
• Route B: 35 minutes, with a 1 percent chance of missing the flight.

A goal-based agent whose goal is "be at the airport" is indifferent: both routes achieve it. A utility-based agent must be given numbers. Say each minute costs 1 unit and missing the flight costs 100 units. Then the expected cost of each route is:

• Route A: 20 + 0.10 * 100 = 20 + 10 = 30
• Route B: 35 + 0.01 * 100 = 35 + 1 = 36

Route A wins. But now change one number - suppose missing the flight costs 500 because it is the last one before a wedding:

• Route A: 20 + 0.10 * 500 = 20 + 50 = 70
• Route B: 35 + 0.01 * 500 = 35 + 5 = 40

Now route B wins decisively. Nothing about the world changed; only the utility numbers did. This is the whole argument for utility-based agents: when outcomes are uncertain and objectives conflict, the ranking has to live in explicit numbers, and pretending otherwise just hides the trade-off somewhere less visible.

Key idea: agent designs climb from simple reflex to learning agents, and each rung matches a later part of this course.

Where people get stuck

• "The agent function is the actual program." The function is an abstract mapping and is astronomically large; the program is a compact procedure that produces the same behaviour. One binary sensor for an hour already needs about 101084 table entries.
• "A rational agent needs to see everything." Most interesting environments are partially observable. Rationality is about the best use of available information, not about having all of it.
• "Deterministic means predictable to the agent." An environment can be deterministic yet appear uncertain, because the agent cannot observe the parts of the state that determine the outcome. Determinism is a property of the world; uncertainty is a property of the agent's knowledge.
• "Utility and goals are the same." A goal is pass or fail; utility is a graded score that supports trade-offs. The airport example flips its answer purely by changing one utility number, which a goal cannot express at all.
• Classifying the world rather than the model. The six dimensions describe the task as modelled. Chess is fully observable because we declared the board to be the state. Over-generous modelling is a standard route to a system that works in simulation and fails in the field.
• Reaching for a learning agent first. The ladder is ordered by capability, not by preference. If the current percept determines the right action, a reflex agent is correct, cheaper, and easier to verify.
• Forgetting that the agent changes its own environment. A filter that silently discards messages never learns whether it was right, and a trader's orders move the prices it is predicting. Feedback loops through the environment are the rule in deployment, not an exotic case.

Recap

• An agent senses via sensors and acts via actuators, described by an agent function; the program is a tractable compression of an intractable table.
• PEAS specifies the task: Performance measure, Environment, Actuators, Sensors.
• Six dimensions classify environments and predict how hard the job is. Image classification sits in the easy cell of every one and automated trading in the hard cell of every one, which is why they were solved decades apart.
• Agent designs form a ladder: simple reflex, model-based, goal-based, utility-based, learning. Internal state is required, not optional, once the environment is partially observable - the vacuum world costs a reflex agent 1 point per step forever.
• Utilities are required once outcomes are uncertain and objectives conflict; the same two routes to an airport reverse their ranking when the cost of missing the flight changes from 100 to 500.
• Each design level maps to later course topics (search, decision theory, learning).

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Wooldridge, M. (2009). An introduction to multiagent systems (2nd ed.). Wiley. find source ↗
3. Russell, S. J., & Norvig, P. (n.d.). Artificial intelligence: A modern approach [Companion site]. University of California, Berkeley. aima.cs.berkeley.edu
4. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
5. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu
6. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press. incompleteideas.net
7. Bringsjord, S., & Govindarajulu, N. S. (2018). Artificial intelligence. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu

A puzzle, a route, a robot's next ten moves, a proof: these look like different problems, and to a search algorithm they are the same problem wearing different clothes. Learning to see that shape - and to recognise which of a handful of exploration strategies fits it - is the first genuinely general skill in AI, and it is the substrate for everything in the next two lessons.

The big picture

Many AI problems boil down to the same shape: you are in some situation, you can take actions that move you to new situations, and you want to reach a goal. Finding a route on a map, solving a puzzle, or planning a sequence of moves are all this. Search is the systematic way of exploring the possibilities until you find a path to the goal.

Why it matters: search is the first general problem-solving method in AI, and it is the foundation the next two lessons build on. Master how a problem is framed and how the two basic strategies explore, and the smarter methods will make immediate sense.

Framing a search problem

Any search problem is defined by five parts:

1. State: a snapshot of the situation (for a map, the city you are in).
2. Initial state: where you start.
3. Actions: what you can do from a state (roads leaving a city).
4. Goal test: a check for whether a state is a goal.
5. Path cost: a number totaling the cost of the steps taken (miles driven).

Searching builds a search tree: the start is the root, and each action expands a node into its children (the states you can reach next). The frontier is the set of nodes discovered but not yet expanded, the "to-do list." The strategy is simply the rule for which frontier node to expand next.

Key idea: a search problem is states, actions, a goal test, and path cost, and a strategy is just the rule for which frontier node to expand next.

Breadth-first search (BFS)

BFS expands the shallowest unexpanded node first. It uses a queue (first in, first out), so it explores the tree level by level, like ripples spreading out from a stone dropped in a pond. It finds all nodes at depth 1, then all at depth 2, and so on.

Worked expansion. Suppose the start A has children B and C; B has children D and E; C has children F and G; and the goal is G.

Frontier starts: [A]
Expand A  -> add B, C     frontier: [B, C]
Expand B  -> add D, E     frontier: [C, D, E]
Expand C  -> add F, G     frontier: [D, E, F, G]
Expand D  -> (no goal)    frontier: [E, F, G]
Expand E  -> (no goal)    frontier: [F, G]
Expand F  -> (no goal)    frontier: [G]
Expand G  -> GOAL found

BFS reached G after fully clearing the shallower levels, which is exactly the level-by-level behavior.

Properties (with branching factor b and shallowest goal at depth d):

• Complete: yes, it will find a solution if one exists.
• Optimal: yes when every step costs the same, because the first goal found is the shallowest.
• Time: about b^d nodes.
• Space: about b^d nodes, because the whole frontier must be stored. This memory cost is BFS's main weakness.

Key idea: BFS explores level by level, is complete and optimal for equal step costs, but can use enormous memory.

Depth-first search (DFS)

DFS expands the deepest unexpanded node first. It uses a stack (last in, first out), so it plunges down one branch to the bottom before backing up. Picture exploring a maze by always taking the next corridor and only backtracking at dead ends.

Worked expansion on the same tree (children pushed so the left one is explored first):

Frontier starts: [A]
Expand A  -> push B, C    frontier(top=B): [C, B]
Expand B  -> push D, E    frontier(top=D): [C, E, D]
Expand D  -> (leaf)       frontier(top=E): [C, E]
Expand E  -> (leaf)       frontier(top=C): [C]
Expand C  -> push F, G    frontier(top=F): [G, F]
Expand F  -> (leaf)       frontier(top=G): [G]
Expand G  -> GOAL found

DFS dove all the way into B's branch (D, E) before touching C.

Properties (tree of maximum depth m):

• Complete: not in general. On an infinite or looping path it can wander forever; it is complete only in finite spaces with cycle checking.
• Optimal: no. It returns the first goal it stumbles on, which may be a long, expensive path.
• Time: about b^m in the worst case.
• Space: only about b times m, because it stores just the current path plus siblings. This small memory footprint is DFS's big advantage.

Key idea: DFS uses little memory but is neither complete nor optimal in general.

BFS vs. DFS at a glance

Property	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO)
Complete?	Yes	Not in general
Optimal?	Yes (equal step costs)	No
Time	bd	bm
Space	bd (large)	b times m (small)

When you need uniform-cost search

BFS is only optimal when every step costs the same. If steps differ (some roads are longer), the shallowest path is not always the cheapest. Uniform-cost search (UCS) fixes this by expanding the frontier node with the lowest total path cost so far, using a priority queue ordered by cumulative cost. UCS is complete and optimal for any non-negative step costs. In fact, when all step costs are equal, UCS behaves just like BFS. UCS is the direct ancestor of A*, which the next lesson adds a heuristic to.

Worked example: BFS returning a bad answer, and UCS fixing it

Claims about optimality deserve a counterexample, so here is the smallest one that works. Five cities, with road costs:

S --1--> A --1--> C --1--> G
S --5--> B --1--> G

There are exactly two routes from S to G:

• S -> A -> C -> G, three steps, total cost 1 + 1 + 1 = 3.
• S -> B -> G, two steps, total cost 5 + 1 = 6.

BFS. It explores by depth. Depth 1 holds A and B; depth 2 holds C (reached via A) and G (reached via B). BFS therefore finds the goal at depth 2 and returns S -> B -> G at cost 6. That is the shallowest path and it is twice as expensive as the best one. BFS did not malfunction; it optimised the wrong quantity, because "fewest steps" and "cheapest" are different objectives whenever step costs differ.

UCS. Now order the frontier by cumulative cost g, always expanding the cheapest node.

Frontier              Expand   Result
[(S,0)]               S        add (A,1), (B,5)
[(A,1), (B,5)]        A        add (C,2)
[(C,2), (B,5)]        C        add (G,3)
[(G,3), (B,5)]        G        GOAL, cost 3

UCS returns S -> A -> C -> G at cost 3, the true optimum. Notice that B was placed on the frontier and never expanded: its cost of 5 already exceeded the goal's cost of 3, so UCS correctly ignored it. Notice also the goal test happens when a node is expanded, not when it is generated. If UCS declared victory the moment G first appeared on the frontier, it could return a suboptimal path; only expansion guarantees nothing cheaper remains.

Key idea: use uniform-cost search when step costs differ; it expands the cheapest-so-far node and is optimal for non-negative costs.

Iterative deepening: BFS guarantees at DFS memory cost

BFS is optimal but memory-hungry; DFS is memory-frugal but neither complete nor optimal. Iterative deepening search (IDS) gets most of both: run a depth-limited DFS with limit 0, then limit 1, then limit 2, and so on until a goal is found.

The obvious objection is that this re-explores the shallow levels over and over. Cost it out. With branching factor b = 10 and a goal at depth d = 5, the nodes at depth 1 are generated 5 times, those at depth 2 four times, and so on down to depth 5 once:

• IDS: 5(10) + 4(100) + 3(1000) + 2(10000) + 1(100000) = 50 + 400 + 3000 + 20000 + 100000 = 123450
• BFS: 10 + 100 + 1000 + 10000 + 100000 = 111110

IDS generates about 11 percent more nodes. In exchange, its memory is O(bd) rather than O(bd) - here on the order of 50 nodes instead of 100,000. The repeated work is cheap because a tree's nodes are overwhelmingly concentrated in its deepest level, so redoing everything above it costs almost nothing. IDS is the standard choice for large search spaces with unknown depth and uniform costs.

Repeated states: why you need a visited set

Everything above assumed a tree. Real state spaces are graphs, where different action sequences reach the same state, and ignoring that is catastrophic.

Picture a robot on a grid moving in four directions. From any square there are up to four moves, so the number of distinct paths of length n grows roughly like 3n (three, since you would not immediately reverse). But the number of distinct squares within n steps is only about 2n2. At n = 20 that is on the order of 109 paths over roughly 800 squares. Tree search explores the paths; graph search explores the squares.

The fix is one line: keep an explored set of states already expanded, and discard any newly generated node whose state is already in it. This turns an exponential blow-up into something polynomial, and it also makes DFS complete in finite spaces by preventing infinite loops around cycles. The price is memory proportional to the number of distinct states, which is exactly the trade DFS was trying to avoid - so the choice between tree search and graph search is itself a time-versus-memory decision.

What these complexity numbers mean in practice

Asymptotic notation hides how quickly this bites. Take b = 10 and d = 12, a machine generating a million nodes per second, and a kilobyte of storage per node.

• Nodes: bd = 1012.
• Time: 1012/106 = 106 seconds, about 11.6 days. Slow, but conceivable.
• Memory for BFS: 1012 kilobytes, which is 109 megabytes - one petabyte. Not conceivable.

Memory is the binding constraint, and by a wide margin. That single observation explains why iterative deepening exists at all, and why the next lesson's heuristics matter so much: cutting the effective branching factor from 10 to 3 turns 1012 nodes into 312, about half a million - a problem that finishes in under a second on a laptop.

Where people get stuck

• "BFS is always optimal." Only when every step costs the same. The five-city example returns cost 6 when the optimum is 3, because BFS minimises the number of steps and the question asked about cost.
• "DFS always finds the shortest path." DFS returns the first goal it reaches. On a tree where the shallow branch is a dead end and the deep one succeeds, it can return an arbitrarily long path.
• "DFS uses more memory because it goes deep." The opposite. DFS stores the current path and its siblings, O(bm); BFS stores an entire level, O(bd). Depth is cheap; breadth is expensive.
• Testing for the goal on generation rather than expansion. In UCS this silently breaks optimality: a goal node can appear on the frontier with a high cost while a cheaper route to it is still being discovered. Test when you expand.
• Omitting the explored set. On any graph with cycles this makes DFS non-terminating and BFS exponentially wasteful. On a grid, tree search explores 3n paths where graph search explores O(n2) squares.
• Assuming time is the binding constraint. At b = 10, d = 12, BFS needs about 11 days of compute and a petabyte of memory. You will hit the memory wall first, every time.
• Expecting search to know where the goal is. All of these are uninformed: they use no domain knowledge about goal location. The next lesson adds exactly that, and the payoff is a smaller effective branching factor.
• Treating iterative deepening's repeated work as wasteful. The overhead is about 11 percent at b = 10, because nearly all nodes live in the deepest level. The memory saving is a factor of thousands.

Recap

• A search problem is states, initial state, actions, goal test, and path cost.
• BFS expands shallowest first with a queue; complete and optimal for equal costs, but memory-hungry.
• DFS expands deepest first with a stack; memory-light, but not complete or optimal in general.
• Time is b^d for BFS and b^m for DFS; space is b^d vs. b times m.
• Uniform-cost search handles unequal step costs optimally and leads into A*. On the five-city example it returns cost 3 where BFS returns 6, and it never expands the expensive branch at all.
• Iterative deepening buys BFS's completeness and optimality at DFS's memory cost, for about 11 percent extra node generation when b = 10.
• Graph search with an explored set is necessary whenever states can be reached by more than one path, which is almost always.
• Memory, not time, is what stops uninformed search: b = 10 and d = 12 needs roughly 11 days of compute but a petabyte of storage.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press. find source ↗
3. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. doi.org/10.1007/BF01386390
4. Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109. doi.org/10.1016/0004-3702(85)90084-0
5. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
6. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu
7. Russell, S. J., & Norvig, P. (n.d.). Artificial intelligence: A modern approach [Companion site]. University of California, Berkeley. aima.cs.berkeley.edu

The big picture

Uninformed search explores blindly, with no sense of which direction the goal lies. Informed search adds a hint: an estimate of how far each state is from the goal, so the search can head toward it instead of wandering. The star of this lesson, the A* algorithm, combines that hint with the cost already paid to find the cheapest path efficiently.

Why it matters: A* is one of the most widely used algorithms in all of computing, powering game pathfinding, route planners, and robotics. Understanding why it is both fast and provably optimal is a milestone in AI.

Heuristics: an educated guess

A heuristic function h(n) estimates the cost from node n to the nearest goal. Think of it as a hunch, cheap to compute and usually pretty good, though not exact. On a map, a natural heuristic is the straight-line (as-the-crow-flies) distance to the destination: you cannot drive through buildings, but the crow-flies distance is a sensible lower bound on how far you still have to go.

Two properties of heuristics matter enormously:

• Admissible: h never overestimates the true remaining cost. It is optimistic, promising a cost no larger than reality. Straight-line distance is admissible because the real road can only be longer.
• Consistent (monotone): for every step from n to a neighbor n', h(n) is at most the step cost plus h(n'). Consistency is a slightly stronger condition, and every consistent heuristic is also admissible.

Write h*(n) for the true cheapest cost from n to a goal. Then the two properties are:

• Admissible: h(n) <= h*(n) for every node n.
• Consistent: h(n) <= c(n, n') + h(n') for every edge from n to a neighbour n', where c is the step cost, and h(goal) = 0.

Consistency is a triangle inequality: going straight from n cannot be estimated as costing more than detouring through n'. Every consistent heuristic is admissible, and the converse fails, which matters for graph search below.

Key idea: a heuristic estimates the remaining cost to the goal, and an admissible heuristic never overestimates it.

Greedy best-first search (and its flaw)

Greedy best-first search expands whichever frontier node looks closest to the goal, that is, the one with the smallest h(n). It is often fast, but it ignores the cost already spent, so it can charge toward the goal down a path that turns out to be long and expensive. It is not optimal, and it can even get stuck. Greedy search looks only ahead; it forgets where it has been.

Key idea: greedy best-first search follows the heuristic alone, so it is fast but not optimal.

A* search: the best of both

A* fixes greedy search by scoring each node with the sum of two quantities:

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

• g(n): the actual cost of the path from the start to n (where you have been).
• h(n): the estimated cost from n to the goal (where you still must go).
• f(n): the estimated total cost of the cheapest path through n.

A* always expands the frontier node with the smallest f. It balances the two concerns: g keeps it honest about cost paid, and h steers it toward the goal.

Worked example. Start S, goal G. Two routes:

Node	g (cost so far)	h (estimate to G)	f = g + h
A (via top road)	2	6	8
B (via bottom road)	5	2	7

Greedy search ranks by h alone and picks the smallest h, which is B (h = 2). A* instead compares f: f(A) = 8 versus f(B) = 7, so A* also expands B first, but for the right reason, its estimated total cost is lower.

If B truly leads to a cheaper complete path, A* confirms it; if not, A* comes back and tries A. Here both agree on B, but consider a case where the bottom road is a dead-end detour with g(B) = 9 and h(B) = 2: then f(B) = 11 while f(A) = 8, so A* would correctly prefer A even though B still looks closer to greedy search. The f-score, not h alone, guides the choice.

Key idea: A* ranks nodes by f = g + h, combining cost already paid with estimated cost remaining.

A full A* trace on a labelled graph

Here is a complete run, with every frontier entry and its g, h, and f values. The graph has six nodes; all edges are usable in either direction.

Edges and step costs:
  S - A : 1        A - C : 2        C - G : 3
  S - B : 4        A - D : 5        D - G : 2
                   B - D : 1

Heuristic h(n), an estimate of the remaining cost to G:
  h(S)=5   h(A)=4   h(B)=2   h(C)=3   h(D)=2   h(G)=0

Before running anything, note the three complete routes and their true costs, so we know what the right answer is:

• S -> A -> C -> G: 1 + 2 + 3 = 6  (the optimum)
• S -> B -> D -> G: 4 + 1 + 2 = 7
• S -> A -> D -> G: 1 + 5 + 2 = 8

Checking admissibility. Compare each h with the true remaining cost h*:

Node	h(n)	h*(n), true cost to G	h <= h*?
S	5	6	yes
A	4	5, via C	yes
B	2	3, via D	yes
C	3	3	yes, with equality
D	2	2	yes, with equality
G	0	0	yes

Checking consistency. Test h(n) <= c(n,n') + h(n') on every edge:

• S to A: 5 <= 1 + 4 = 5. Holds, tightly.
• S to B: 5 <= 4 + 2 = 6. Holds.
• A to C: 4 <= 2 + 3 = 5. Holds.
• A to D: 4 <= 5 + 2 = 7. Holds.
• B to D: 2 <= 1 + 2 = 3. Holds.
• C to G: 3 <= 3 + 0 = 3. Holds, tightly.
• D to G: 2 <= 2 + 0 = 2. Holds, tightly.

Every edge passes, so h is consistent, hence also admissible, and A* graph search is guaranteed optimal here.

The run. At each step the frontier is listed as node(g, h, f), and A* expands the smallest f.

Init      frontier: S(0, 5, 5)

Step 1    expand S  (f=5)
          generate  A: g = 0+1 = 1, h = 4, f = 5
                    B: g = 0+4 = 4, h = 2, f = 6
          frontier: A(1, 4, 5), B(4, 2, 6)

Step 2    expand A  (f=5, the smallest)
          generate  C: g = 1+2 = 3, h = 3, f = 6
                    D: g = 1+5 = 6, h = 2, f = 8
          frontier: B(4, 2, 6), C(3, 3, 6), D(6, 2, 8)

Step 3    expand B  (f=6; ties with C, broken alphabetically)
          generate  D via B: g = 4+1 = 5, h = 2, f = 7
                    this beats the old D(g=6), so replace it
          frontier: C(3, 3, 6), D(5, 2, 7)

Step 4    expand C  (f=6)
          generate  G: g = 3+3 = 6, h = 0, f = 6
          frontier: G(6, 0, 6), D(5, 2, 7)

Step 5    expand G  (f=6)  -- goal test succeeds on expansion
          return    S -> A -> C -> G  at cost 6

Three things in that trace are worth pausing on. First, D was never expanded: its f of 7 exceeded the goal's f of 6, so A* proved it irrelevant without exploring it. Second, D's g was corrected in step 3 from 6 to 5 when a cheaper route through B appeared; A* must always keep the best known g for each state. Third, the goal test fires on expansion, not generation. G appeared on the frontier at the end of step 4, but A* did not stop there - it stopped only when G had the smallest f, which is exactly what proves no cheaper path remains.

What goes wrong with an inadmissible heuristic

Change a single number. Set h(C) = 6 instead of 3, which overestimates C's true remaining cost of 3. Leave everything else identical. Now rerun:

Init      frontier: S(0, 5, 5)

Step 1    expand S   -> A(1, 4, 5), B(4, 2, 6)

Step 2    expand A   -> C: g=3, h=6, f=9      (was f=6)
                        D: g=6, h=2, f=8
          frontier: B(4, 2, 6), D(6, 2, 8), C(3, 6, 9)

Step 3    expand B   -> D via B: g=5, h=2, f=7   (replaces D)
          frontier: D(5, 2, 7), C(3, 6, 9)

Step 4    expand D   -> G: g = 5+2 = 7, h=0, f=7
          frontier: G(7, 0, 7), C(3, 6, 9)

Step 5    expand G   (f=7)
          return    S -> B -> D -> G  at cost 7

A* returns a path costing 7 when a path costing 6 exists. The mechanism is precise: inflating h(C) pushed C's f-score to 9, so the cheap route through C sat unexplored at the back of the queue while A* found the goal by a more expensive route and stopped. The algorithm did not malfunction. Its optimality proof requires h <= h*, that hypothesis was violated, and the guarantee evaporated with it.

This failure mode is quiet, which is what makes it dangerous. A* still returns a path, it still runs fast - often faster, since overestimates prune aggressively - and nothing in the output signals that the answer is not optimal. If you invent a heuristic, prove h <= h* before trusting the result, or accept that you are running a fast approximation rather than an exact algorithm. Inflating a heuristic deliberately, called weighted A*, is a legitimate technique precisely because it trades optimality for speed - but it must be a choice, not an accident.

Why consistency matters separately

Admissibility alone guarantees optimality for tree search. Graph search, which discards a state once it has been expanded, needs the stronger condition. The reason is straightforward: with an admissible-but-inconsistent heuristic, a state can first be reached along an expensive path, be expanded and closed, and only later be reachable more cheaply - at which point the closed set blocks the improvement.

Consistency rules this out, because it forces f to be non-decreasing along any path: if h(n) <= c(n,n') + h(n'), then f(n') = g(n) + c(n,n') + h(n') >= g(n) + h(n) = f(n). Non-decreasing f means A* expands nodes in non-decreasing order of f, so the first time it expands a state it has already found the cheapest route to it. If you are stuck with an inconsistent heuristic, the standard repair is to re-open a closed node whenever a cheaper path to it is discovered.

Why A* is optimal

Here is the guarantee, stated plainly: if the heuristic h is admissible, A* returns an optimal (cheapest) solution. The intuition is that an admissible h never overstates the remaining cost, so A* will never wrongly skip past a truly cheaper path. A* will not declare a goal found until no other frontier node could possibly lead to something cheaper. (With the stronger consistency property, this holds even for graph search that discards repeated states.)

A* is also, in a precise sense, optimally efficient: no other algorithm using the same heuristic is guaranteed to expand fewer nodes. The quality of h decides its speed. A perfect h would walk straight to the goal; the constant heuristic h = 0 turns A* back into uniform-cost search.

Key idea: with an admissible heuristic, A* is guaranteed to find the cheapest path, and a better heuristic makes it faster.

Comparing the strategies

Algorithm	Ranks nodes by	Optimal?
Uniform-cost search	g(n)	Yes (non-negative costs)
Greedy best-first	h(n)	No
A*	g(n) + h(n)	Yes (admissible h)

Where heuristics come from, and how much they buy

Good heuristics are usually built by relaxing the problem: delete some constraint, and the exact cost of the easier problem is an admissible estimate for the harder one, because any real solution is also a solution to the relaxed version.

The 8-puzzle makes this concrete. The real rule is that a tile may move into the blank square if it is adjacent.

• Relax to "a tile may move anywhere in one step." The exact cost is h1, the number of misplaced tiles.
• Relax to "a tile may move to any adjacent square, blank or not." The exact cost is h2, the sum of Manhattan distances of each tile from its home.

Both are admissible by construction. Moreover h2(n) >= h1(n) for every n - a misplaced tile contributes at least 1 to the Manhattan sum - so h2 dominates h1. Dominance is exactly the right notion of "better": if two admissible heuristics satisfy h2 >= h1 everywhere, A* with h2 expands no more nodes than A* with h1, and usually far fewer.

The magnitudes are startling. In the standard comparison reported by Russell and Norvig for 8-puzzle instances at solution depth 12, iterative deepening generates on the order of 3.6 million nodes, A* with h1 about 227, and A* with h2 about 73. That is five orders of magnitude from adding domain knowledge, and a further factor of three from a better relaxation. The takeaway is blunt: effort spent designing the heuristic usually pays far more than effort spent optimising the search code.

Two boundary cases anchor the scale. With h = 0, A* degenerates to uniform-cost search - always admissible, never informative. With h = h*, A* walks straight down an optimal path expanding nothing extra. Real heuristics live between, and their quality is measured by how close they get to h* without ever exceeding it.

Where people get stuck

• "A better heuristic changes which path A* returns." With any admissible h, A* returns an optimal path. A better h changes only how many nodes are expanded - 227 versus 73, not a different answer.
• "Greedy search is just A*." Greedy ranks by h alone and discards the cost already paid, so it is not optimal. A* ranks by g + h.
• "Any heuristic guarantees optimality." Only an admissible one. Raising h(C) from 3 to 6 in the worked graph makes A* return a path of cost 7 instead of 6, silently.
• Confusing admissible with consistent. Admissibility suffices for tree search; graph search needs consistency, or else a state closed on an expensive path can block a later cheaper one. Repair by re-opening closed nodes.
• Testing the goal on generation. In the trace, G appears on the frontier at step 4 but is only accepted at step 5, when its f is smallest. Accepting on generation can return a suboptimal path.
• Failing to update g when a cheaper route appears. Step 3 replaced D's g of 6 with 5. Skipping that update leaves stale costs on the frontier and can break optimality.
• Assuming A* is always affordable. Its memory is still proportional to the number of nodes generated, which can exhaust RAM on large problems. Variants such as iterative-deepening A* trade time for memory in exactly the way IDS does.
• Inventing a heuristic without checking it. Derive one by relaxing the problem, which makes admissibility automatic, rather than guessing a formula and hoping.

Recap

• A heuristic h(n) estimates remaining cost; admissible means it never overestimates.
• Greedy best-first uses h alone: fast but not optimal.
• A* ranks nodes by f(n) = g(n) + h(n), balancing cost paid and cost remaining.
• With an admissible heuristic, A* is optimal; with a consistent one, optimal even for graph search.
• Setting h = 0 reduces A* to uniform-cost search.
• On the worked graph, A* with a consistent h returns S -> A -> C -> G at cost 6 while never expanding D; raising h(C) to an inadmissible 6 makes it return cost 7 instead, with no warning.
• Test the goal on expansion, not generation, and update a node's g whenever a cheaper route to it is found.
• Build heuristics by relaxing the problem, which makes admissibility automatic; a dominating heuristic (h2 >= h1) never expands more nodes.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. cs.auckland.ac.nz
3. Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley. find source ↗
4. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. doi.org/10.1007/BF01386390
5. Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109. doi.org/10.1016/0004-3702(85)90084-0
6. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
7. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu

The big picture

So far the search problems had no opponent: the world sat still while you planned. Games like chess or tic-tac-toe are different because a second player is actively trying to beat you. Adversarial search is how an agent plans in that setting, assuming the other side will always make its best move against you.

Why it matters: this is the reasoning behind classic game-playing programs, from checkers to Deep Blue's chess. It also teaches a broadly useful mindset, planning against a worst case rather than a friendly one.

The game setup

We focus on games that are two-player, turn-taking, zero-sum, and perfect-information. Zero-sum means one player's gain is exactly the other's loss, so there is nothing to share. The two players are named by convention:

• MAX: the player trying to maximize the score (that is us).
• MIN: the opponent trying to minimize our score.

A utility function scores final positions from MAX's point of view, for example +1 for a win, 0 for a draw, and -1 for a loss. The whole game forms a game tree: levels alternate between MAX's choices and MIN's choices, down to terminal (finished) positions at the leaves.

Key idea: in a zero-sum game, MAX tries to maximize the final score and MIN tries to minimize it, and the game tree alternates their turns.

The minimax rule

Minimax computes the best move by assuming perfect play from both sides. Working up from the leaves:

• At a MAX node, take the maximum of the children's values (MAX picks its best option).
• At a MIN node, take the minimum of the children's values (the opponent picks the worst option for us).

The value that flows up to the root is the minimax value: the best score MAX can guarantee against an optimal opponent.

Worked example. MAX moves first (root), then MIN, then leaves. The tree has a root MAX node with two children (MIN node A and MIN node B); A has leaves 3 and 5, and B has leaves 2 and 9.

Level (whose turn)	Node	Children / leaves
Root (MAX)	Root	MIN node A, MIN node B
Next (MIN)	MIN node A	leaves 3 and 5
Next (MIN)	MIN node B	leaves 2 and 9

Step 1, evaluate the MIN nodes:

• MIN node A = min(3, 5) = 3.
• MIN node B = min(2, 9) = 2.

Step 2, evaluate the root (MAX): root = max(3, 2) = 3. So MAX should move toward node A, guaranteeing a score of 3. Notice MAX does not chase the tempting 9 under B, because a rational MIN would answer with the 2.

Key idea: minimax values a MAX node as the max of its children and a MIN node as the min, giving the score MAX can guarantee.

The problem: game trees are huge

Minimax is correct but explores the entire tree. With branching factor b and depth d, that is about b^d positions. Chess has roughly 35 legal moves per turn and games run dozens of moves deep, so the full tree has more positions than there are atoms in the observable universe. Searching all of it is impossible.

Key idea: full minimax is infeasible for real games because the game tree grows like b^d.

Alpha-beta pruning

Alpha-beta pruning is a way to compute the exact same minimax answer while skipping branches that cannot change it. The insight: once you know a branch is worse than one you have already secured, you can stop examining it. It carries two bookkeeping values down the tree:

• alpha: the best (highest) score MAX can already guarantee so far.
• beta: the best (lowest) score MIN can already guarantee so far.

Whenever alpha becomes greater than or equal to beta at a node, the remaining children are pruned: exploring them cannot affect the result, so they are cut off.

Worked prune. Reuse the tree above. MAX explores node A first and learns its value is 3, so alpha = 3. Now MAX starts node B and sees its first leaf, 2. Because B is a MIN node, its value is at most 2 (MIN will never choose more than the smallest it finds). But MAX already has 3 in hand from A, and 2 is worse. So the second leaf under B (the 9) never needs to be examined; it is pruned. The answer is still 3, computed with less work.

A full alpha-beta trace, naming every pruned node

Two leaves is too small to see the machinery, so here is the standard nine-leaf tree, traced with alpha and beta at every step. The root is a MAX node with three MIN children B, C, and D, each holding three leaves.

                   ROOT (MAX)
        /              |              \
     B (MIN)        C (MIN)        D (MIN)
     / | \          / | \          / | \
    3 12  8        2  4  6       14  5  2

First, the plain minimax answer, so we know what alpha-beta must reproduce:

• B = min(3, 12, 8) = 3
• C = min(2, 4, 6) = 2
• D = min(14, 5, 2) = 2
• ROOT = max(3, 2, 2) = 3, so MAX should move to B.

Now run alpha-beta left to right. Both values start at their extremes: alpha = -infinity (MAX has guaranteed nothing yet) and beta = +infinity.

ENTER B (MIN)         alpha = -inf, beta = +inf
  leaf 3   -> B's best-so-far = 3,  beta = min(+inf, 3) = 3
             alpha(-inf) < beta(3), keep going
  leaf 12  -> B's best-so-far = min(3,12) = 3,  beta = 3
  leaf 8   -> B's best-so-far = min(3,8)  = 3
  B returns 3
ROOT: alpha = max(-inf, 3) = 3

ENTER C (MIN)         alpha = 3, beta = +inf
  leaf 2   -> C's best-so-far = 2,  beta = min(+inf, 2) = 2
             alpha(3) >= beta(2)  ==>  PRUNE
  leaves 4 and 6 are NEVER EXAMINED
  C returns 2 (only an upper bound, which is enough)
ROOT: alpha = max(3, 2) = 3

ENTER D (MIN)         alpha = 3, beta = +inf
  leaf 14  -> D's best-so-far = 14, beta = 14
             alpha(3) < beta(14), keep going
  leaf 5   -> D's best-so-far = min(14,5) = 5,  beta = 5
             alpha(3) < beta(5), keep going
  leaf 2   -> D's best-so-far = min(5,2)  = 2,  beta = 2
             alpha(3) >= beta(2), but this was the last child anyway
  D returns 2
ROOT: alpha = max(3, 2) = 3

ROOT value = 3, best move = B

Exactly two leaves were pruned: the 4 and the 6 under C. Understand precisely why. Once C's first leaf revealed a 2, C's final value could only be 2 or lower, since MIN takes the minimum. MAX already held 3 from B. So whatever C turns out to be, MAX will never choose it, and its exact value is irrelevant. The 4 and 6 could have been any numbers at all - a million, or a negative billion - and the root would still be 3.

Notice also what the trace did not prune. Nothing under B was cut, because B was explored first with no alpha in hand yet. And under D, the 14 and 5 had to be examined, because until the value dropped below 3 there was still a chance D would beat B.

One warning the trace makes visible: the value C returned is 2 as an upper bound, not necessarily C's true minimax value. Here they coincide, but in general a pruned node's reported value is only a bound. If you need exact values for every node - say, to display an evaluation for each candidate move - alpha-beta does not give them to you, and asking for them means giving up the pruning.

How much does pruning actually buy?

Pruning does not change the answer, only the effort - and the effort saved depends entirely on move ordering. If the best move is examined first at every node, alpha is large as early as possible and cuts maximally. Knuth and Moore's analysis gives the two regimes:

• Perfect ordering: alpha-beta examines about bd/2 leaves instead of bd. The effective branching factor becomes the square root of b.
• Random ordering: roughly b3d/4 - still a large saving, but far short of the ideal.
• Worst ordering: no pruning at all, and alpha-beta degenerates to plain minimax.

Put chess numbers on it. With b = 35 and d = 8, plain minimax examines about 358 = 2.3 * 1012 leaves. With perfect ordering alpha-beta examines about 354 = 1500625, roughly 1.5 million - a factor of about 1.5 million fewer. Equivalently, in a fixed time budget you can search twice as deep, and in chess two extra plies is a large difference in playing strength.

This is why real engines spend serious effort on ordering heuristics: try the move that worked at this position last time, try captures before quiet moves, try moves that caused a cutoff at the same depth elsewhere. None of these change what alpha-beta computes; they only change how fast it gets there, and that turns out to matter more than almost anything else in the program.

Key idea: alpha-beta pruning returns the exact minimax value while skipping branches that cannot change it, often letting the search go much deeper.

Getting practical: evaluation functions and depth limits

Even with pruning, agents cannot search a game like chess to the end. Real programs stop at a fixed depth and apply an evaluation function, a quick numeric estimate of how good a non-terminal position is (in chess, roughly material plus positional factors). It plays the role h(n) played in A*: a heuristic estimate that replaces exhaustive lookahead. Deeper search plus a better evaluation function equals stronger play.

Key idea: real game programs cut off search at a depth limit and score positions with a heuristic evaluation function.

The horizon effect: what a depth limit costs you

Cutting off at a fixed depth introduces a failure that has nothing to do with pruning and cannot be fixed by searching faster. Suppose a chess program searching eight plies is about to lose a queen. It discovers that a sequence of pointless checks delays the capture until move nine - just past its horizon. Every line it can see now ends with the queen still on the board, so the position scores well, and the program plays the pointless checks. It has not avoided the loss; it has pushed the loss out of view and thrown away material doing so.

This is the horizon effect, and it is a structural consequence of stopping mid-game. The standard mitigation is quiescence search: at the depth limit, do not stop if the position is volatile. Keep searching captures and checks until reaching a quiet position where the static evaluation is trustworthy. It does not eliminate the problem - there is always some horizon - but it moves the cutoff to positions where the evaluation function is least likely to be badly wrong.

The general lesson transfers well beyond games: a system evaluated at a fixed lookahead will systematically prefer actions that move bad outcomes just beyond what it measures. Any agent with a bounded planning horizon and a metric evaluated at that horizon has this failure available to it.

When there is chance in the game: expectimax

Minimax assumes both players choose deliberately. Backgammon, card games, and any environment with randomness need a third node type. Expectimax adds chance nodes, whose value is the expected value of their children, weighted by probability.

Take a chance node with two outcomes: with probability 0.5 the dice give a position worth 10, and with probability 0.5 a position worth 2. Its value is

0.5 * 10 + 0.5 * 2 = 5 + 1 = 6

Not 10 (optimism), not 2 (pessimism), but 6 - the average outcome. MAX nodes still maximise, MIN nodes still minimise, and chance nodes average. Two consequences follow immediately. First, alpha-beta pruning is much weaker here, because a chance node's value cannot be bounded from a single child unless you also know the range of the others. Second, the evaluation function's scale now matters, not just its ordering: with minimax, any monotonic rescaling of the evaluation gives the same move, but with expectations, doubling one score changes the average and can change the decision.

Where people get stuck

• "Alpha-beta finds a better move than minimax." It returns the identical move with the identical value, just faster. If your alpha-beta and minimax disagree, you have a bug, not an improvement.
• "MAX should always head for the highest leaf." In the two-node example MAX ignores the 9 because a rational MIN answers with the 2. You are choosing against the opponent's best reply, not against the best leaf.
• "Pruning risks missing the best move." It cuts only branches that provably cannot change the root value. The 4 and 6 under C could have been anything.
• Reading a pruned node's value as exact. C "returned 2", but that is an upper bound produced by a cutoff. Node values from a pruned search are bounds, not evaluations.
• Mixing up alpha and beta. Alpha is the best MAX has guaranteed anywhere so far and only ever increases; beta is the best MIN has guaranteed and only ever decreases. The cutoff test is alpha >= beta at both node types.
• Ignoring move ordering. Ordering is the difference between bd/2 and bd - at chess depth 8, between about 1.5 million leaves and 2.3 trillion. It is not a micro-optimisation.
• "Chess programs search to checkmate." They stop at a depth limit and apply an evaluation function, which is why the horizon effect exists and why quiescence search is needed.
• Using minimax where there is chance. Randomness needs expectimax with chance nodes; treating a dice roll as an adversary makes the agent needlessly pessimistic.

Recap

• Adversarial search plans against an opponent who plays to minimize your score.
• Minimax values MAX nodes as the max and MIN nodes as the min of their children; the minimax value is the score MAX can guarantee against optimal play.
• Alpha-beta pruning gives the identical answer while skipping branches that cannot matter. On the nine-leaf tree it returns 3 and prunes exactly the 4 and 6 under C.
• The saving depends on move ordering: about bd/2 leaves with perfect ordering, b3d/4 with random ordering, none with the worst ordering. At b = 35, d = 8 that is 1.5 million leaves instead of 2.3 trillion.
• A pruned node's returned value is a bound, not its true minimax value.
• Practical programs use a depth limit plus an evaluation function, which creates the horizon effect; quiescence search mitigates it.
• Games with randomness use expectimax, where chance nodes take the probability-weighted average of their children.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293-326. doi.org/10.1016/0004-3702(75)90019-3
3. Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256-275. doi.org/10.1080/14786445008521796
4. Campbell, M., Hoane, A. J., & Hsu, F.-h. (2002). Deep Blue. Artificial Intelligence, 134(1-2), 57-83. doi.org/10.1016/S0004-3702(01)00129-1
5. Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., ... Hassabis, D. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv. arxiv.org
6. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
7. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu

The big picture

Some problems are less about finding a path and more about filling in blanks so that a set of rules is satisfied. Sudoku, scheduling classes without clashes, and coloring a map so neighbors differ are all like this. A constraint satisfaction problem (CSP) is a clean framework for exactly these "assign values so all the rules hold" puzzles.

Why it matters: framing a problem as a CSP unlocks powerful general-purpose solvers. Instead of writing custom code for each puzzle, you describe the variables and rules, and a standard algorithm does the searching, often far faster than blind search.

The three ingredients

Every CSP has exactly three parts:

1. Variables: the blanks to fill (each region on a map, each empty Sudoku cell).
2. Domains: the allowed values for each variable (the set of colors, the digits 1 through 9).
3. Constraints: rules restricting which combinations are legal (adjacent regions must differ; a Sudoku row cannot repeat a digit).

A solution is a complete assignment (every variable given a value) that violates no constraint. Because a CSP exposes this structure, solvers can be smarter than treating it as a generic search over states.

Key idea: a CSP is defined by variables, their domains, and constraints, and a solution assigns every variable a value that breaks no constraint.

Running example: map coloring

Color three mutually bordering regions R1, R2, R3 using {red, green, blue} so that no two touching regions share a color.

• Variables: R1, R2, R3.
• Domains: each is {red, green, blue}.
• Constraints: R1 != R2, R2 != R3, R1 != R3 (they all border each other).

One solution: R1 = red, R2 = green, R3 = blue. Because all three border one another, they must all differ, so we need at least three colors, and three suffice.

Key idea: map coloring encodes "neighbors must differ" as not-equal constraints between adjacent variables.

Backtracking search

Backtracking search is depth-first search specialized for CSPs. It assigns one variable at a time, and the moment an assignment breaks a constraint, it stops and backs up rather than continuing down a doomed path. Assign, check, and if stuck, undo the last choice and try the next value.

function BACKTRACK(assignment, csp):
    if assignment is complete: return assignment
    var = SELECT-UNASSIGNED-VARIABLE(csp)
    for each value in ORDER-DOMAIN-VALUES(var, csp):
        if value is consistent with assignment:
            add {var = value} to assignment
            result = BACKTRACK(assignment, csp)
            if result is not failure: return result
            remove {var = value}      # undo and try next
    return failure

Checking constraints early is what makes backtracking beat blind search: it prunes whole subtrees the instant they become illegal.

A trace that actually backtracks

The three-region example never fails, so it hides the algorithm's real behaviour. Here is a four-region map that does. Regions A, B, C, D with these borders:

A - B      A - C      B - C      B - D      C - D

Domains:  A, B, C in {Red, Green, Blue}
          D in {Green, Blue}     (D borders water and cannot be Red)

Note that B, C, and D all border one another - they form a triangle. Take variables in the fixed order A, B, C, D and try values in the order Red, Green, Blue.

A = Red
  B = Green            (Red blocked by A)
    C = Blue           (Red blocked by A, Green blocked by B)
      D: needs != B(Green) and != C(Blue)
         D's domain is {Green, Blue} -- both blocked
         FAIL, back up
    C: no values left after Blue.  FAIL, back up
  B = Blue             (next value after Green)
    C = Green          (Red blocked by A, Blue blocked by B)
      D: needs != B(Blue) and != C(Green)
         both blocked again.  FAIL, back up
    C: no values left.  FAIL, back up
  B: no values left.   FAIL, back up
A = Green              (next value after Red)
  B = Red
    C = Blue
      D: needs != B(Red) and != C(Blue), domain {Green, Blue}
         D = Green works
SOLUTION: A=Green, B=Red, C=Blue, D=Green

That run wasted six assignments and two complete restarts of the B-C subtree, all because the hard variable was left until last. D is the bottleneck - it has only two values and three constrained neighbours - and the fixed ordering discovered that fact only after committing to everything else.

The same problem with MRV and forward checking

Now let the heuristics choose. MRV picks the variable with the fewest remaining values; forward checking deletes newly illegal values from neighbours after each assignment.

Domains:  A {R,G,Bl}   B {R,G,Bl}   C {R,G,Bl}   D {G,Bl}

MRV -> D has 2 values, everything else has 3.  Choose D.
D = Green
  forward check: B loses Green -> B {R, Bl}
                 C loses Green -> C {R, Bl}
                 A unchanged   -> A {R, G, Bl}

MRV -> B and C both have 2, A has 3.  Choose B (tie broken arbitrarily).
B = Red
  forward check: A loses Red   -> A {G, Bl}
                 C loses Red   -> C {Bl}

MRV -> C has 1 value.  Choose C.
C = Blue
  forward check: A loses Blue  -> A {G}

MRV -> A has 1 value.  A = Green.
SOLUTION: D=Green, B=Red, C=Blue, A=Green -- zero backtracks

Six wasted assignments became none. The mechanism is worth stating explicitly, because it is counter-intuitive at first: MRV deliberately attacks the variable most likely to fail. Failing early is cheap, because the failure prunes a subtree you have not yet built; failing late is expensive, because you must unwind everything you assigned on the way down. This is the fail-first principle, and it is one of the most transferable ideas in the whole of search.

Least-constraining-value works in the opposite direction and is not a contradiction. Once you have committed to a variable, you want the value that keeps the most doors open for everyone else, because you are now trying to succeed rather than to prune. Fail first on variables, succeed first on values.

Key idea: backtracking search assigns variables one at a time and abandons a branch as soon as a constraint is violated.

Making it fast: heuristics and inference

Plain backtracking can still be slow. Three standard improvements help enormously.

• Minimum-remaining-values (MRV): choose the variable with the fewest legal values left. Tackle the most constrained blank first, because it is most likely to fail, and failing fast prunes more. This is the "fail-first" idea.
• Least-constraining-value: when picking a value, prefer the one that rules out the fewest options for neighboring variables, keeping the most flexibility.
• Forward checking: after assigning a variable, remove now-illegal values from its neighbors' domains. If any neighbor's domain becomes empty, you know immediately to backtrack.

Worked step (forward checking). In the map example, assign R1 = red. Forward checking deletes red from the domains of R2 and R3, leaving each as {green, blue}. Now assign R2 = green; forward checking deletes green from R3, leaving R3 = {blue}. R3 is forced to blue, and no domain went empty, so we reach a solution with almost no backtracking.

Key idea: MRV, least-constraining-value, and forward checking prune the search early and often solve CSPs with little or no backtracking.

Constraint propagation and arc consistency

Constraint propagation pushes the consequences of constraints further than forward checking does. The common form is arc consistency: a variable X is arc-consistent with Y if every value left in X's domain has at least one compatible value in Y's domain. The AC-3 algorithm enforces this across all pairs, repeatedly deleting values that have no support until nothing changes. Doing this before or during search can shrink domains so much that the answer nearly falls out. Arc consistency is why a good Sudoku solver can often finish by logic with barely any guessing.

AC-3 worked step by step

Arc consistency is easiest to see on a numeric constraint. Take two variables with

X in {1, 2, 3}, Y in {1, 2, 3}, subject to X < Y

An arc (X, Y) is consistent when every value left in X has at least one supporting value in Y. Process the arcs in both directions.

Arc (X -> Y):  does each X value have a legal partner in Y?
   X=1  needs some Y > 1   -> Y=2 or 3   SUPPORTED
   X=2  needs some Y > 2   -> Y=3        SUPPORTED
   X=3  needs some Y > 3   -> none       DELETE 3 from X
   X is now {1, 2}

Arc (Y -> X):  does each Y value have a legal partner in X?
   Y=1  needs some X < 1   -> none       DELETE 1 from Y
   Y=2  needs some X < 2   -> X=1        SUPPORTED
   Y=3  needs some X < 3   -> X=1 or 2   SUPPORTED
   Y is now {2, 3}

Re-check (X -> Y) because Y changed:
   X=1  needs Y > 1  -> Y=2 or 3   SUPPORTED
   X=2  needs Y > 2  -> Y=3        SUPPORTED
   no change, queue empties

RESULT:  X in {1, 2},  Y in {2, 3}

Both domains shrank from three values to two before any search began, cutting the assignment space from nine combinations to four. Note the crucial bookkeeping detail: whenever a domain shrinks, every arc pointing into that variable must be re-queued, because its neighbours' supports may have just disappeared. That re-queuing is what makes it propagation rather than a single pass.

What arc consistency cannot do

AC-3 is sound - it never deletes a value that appears in some solution - but it is incomplete, and the four-region map shows this crisply. Return to the moment after A = Red in the first trace:

A = {Red}      B = {Green, Blue}      C = {Green, Blue}      D = {Green, Blue}
constraints among B, C, D:  B != C,  B != D,  C != D

Check every arc. For B = Green, is there a supporting C? Yes, C = Blue. For B = Blue, C = Green works. The same holds for every pair in both directions. Every arc is consistent, and nothing is deleted.

Yet this branch has no solution at all: B, C, and D form a triangle, so they need three different colours, and only two remain. Arc consistency examines constraints two variables at a time and therefore cannot see a three-way conflict. Stronger conditions exist - path consistency, and k-consistency generally - but they cost more, and full k-consistency is as hard as solving the problem. This is the standard trade-off: propagation is cheap and partial, search is expensive and complete, and real solvers interleave the two.

Key idea: arc consistency (via AC-3) deletes unsupported values from domains, shrinking the problem before and during search, but it can leave an unsolvable branch looking perfectly consistent.

Why the CSP framing pays off

A CSP with n variables and domain size d has dn complete assignments. At n = 20 and d = 3 that is 320 = 3486784401, roughly 3.5 billion - hopeless for generic search, routine for a CSP solver, because the structure is exposed rather than hidden inside opaque states.

Two structural facts explain the gap.

• Commutativity. Assigning A then B reaches the same state as B then A, so a CSP solver considers only one variable per level instead of all of them. That alone cuts the branching factor from nd to d, turning n! dn into dn.
• Structure. If the constraint graph is a tree, the problem is solvable in O(n d2) time - polynomial, with no search at all. Real problems are rarely trees, but decomposing a graph into near-tree pieces is a standard and effective attack.

Sudoku is the everyday demonstration: 81 variables, domains of size 9, and 981 raw assignments, yet constraint propagation alone solves most published puzzles with no guessing whatsoever. The search space was never the difficulty; failing to exploit its structure was.

Where people get stuck

• "A CSP just needs any full assignment." It needs a complete assignment that satisfies every constraint. Completeness and consistency are separate requirements and both are mandatory.
• "Backtracking is unrelated to depth-first search." Backtracking is DFS, with a constraint check at every node so that doomed subtrees are never built.
• "MRV means pick the variable with the most options." The opposite: fewest remaining values, so that failures happen early and cheaply. In the worked map, MRV picked D first and eliminated all six wasted assignments.
• Applying fail-first to values as well. Variables are chosen to fail fast; values are chosen to succeed, which is why least-constraining-value picks the option that removes fewest choices from neighbours.
• "Forward checking guarantees no backtracking." It reduces backtracking substantially but does not eliminate it, because it looks only one step ahead.
• "Arc consistency finds all inconsistencies." It works pairwise and misses the three-way conflict among B, C, and D. An arc-consistent problem can still be unsolvable, so propagation never replaces search.
• Forgetting to re-queue arcs. When a domain shrinks, every arc into that variable must be reconsidered. A single forward pass over the arcs is not AC-3 and will miss deletions.
• Modelling with too few variables. Encoding a schedule as one giant variable whose domain is "all timetables" is technically a CSP and gains nothing. The power comes from many small variables with explicit constraints between them.

Recap

• A CSP has variables, domains, and constraints; a solution satisfies all constraints.
• Map coloring encodes neighbors-must-differ as not-equal constraints.
• Backtracking search is DFS that abandons a branch the moment a constraint breaks. On the four-region map a fixed ordering wasted six assignments and two subtree restarts.
• MRV, least-constraining-value, and forward checking speed the search dramatically - the same map solved with zero backtracks once MRV chose the two-value variable first.
• Fail first on variables, succeed first on values.
• Arc consistency (AC-3) propagates constraints to prune domains: on X < Y with domains {1,2,3} it reduces them to X in {1,2} and Y in {2,3}. Re-queue every arc into any variable whose domain changed.
• AC-3 is sound but incomplete: it cannot detect the three-way conflict that makes an arc-consistent branch unsolvable.
• Commutativity cuts the branching factor to d, and tree-structured constraint graphs are solvable in O(n d2) with no search.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99-118. doi.org/10.1016/0004-3702(77)90007-8
3. Dechter, R. (2003). Constraint processing. Morgan Kaufmann. find source ↗
4. Bonet, B., & Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence, 129(1-2), 5-33. doi.org/10.1016/S0004-3702(01)00108-4
5. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
6. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu
7. Russell, S. J., & Norvig, P. (n.d.). Artificial intelligence: A modern approach [Companion site]. University of California, Berkeley. aima.cs.berkeley.edu

The big picture

For an agent to reason, it needs a way to write down what it knows and rules for drawing new conclusions from it. Knowledge representation is that first half (how to store facts), and logic is the second (how to derive new facts that must follow). This lesson covers the simplest formal logic, propositional logic, the algebra of true-or-false statements.

Why it matters: logic gives us reasoning that is guaranteed correct. If the starting facts are true and the rules are valid, the conclusions cannot be wrong. That certainty is the backbone of verification, planning, and many expert systems.

Propositions and connectives

A proposition is a statement that is either true or false, nothing in between. "It is raining" is a proposition; "close the door" is not. We label propositions with symbols like P and Q and combine them with five connectives:

Connective	Read as	Meaning
NOT P	not P	True exactly when P is false
P AND Q	P and Q	True only when both are true
P OR Q	P or Q	True when at least one is true
P implies Q	if P then Q	False only when P is true and Q is false
P iff Q	P if and only if Q	True when P and Q have the same value

The one that trips people up is implication (if P then Q). It is false in only one situation: P true but Q false. In particular, if P is false, the whole statement is automatically true (a false premise promises nothing). "If it rains, the ground is wet" is not broken on a dry, rainless day.

Key idea: propositions are true-or-false statements combined by NOT, AND, OR, implication, and biconditional, and implication fails only when a true premise leads to a false conclusion.

Truth tables

A truth table lists a statement's value for every combination of its variables. With n variables there are 2ⁿ rows. Here is implication in full:

P	Q	P implies Q
true	true	true
true	false	false
false	true	true
false	false	true

Truth tables let us classify any sentence: a tautology is true in every row (for example, P OR NOT P), a contradiction is false in every row (P AND NOT P), and a contingent sentence is true in some rows and false in others.

Key idea: a truth table evaluates a sentence over all 2ⁿ assignments, revealing whether it is a tautology, a contradiction, or contingent.

Models, entailment, and validity

A model is one assignment of true or false to every proposition, one possible world. A sentence entails another, written KB entails A, when A is true in every model where the knowledge base KB is true. Entailment is the heart of logical reasoning: it means "A must be true whenever what we know is true."

Do not confuse two ideas:

• Soundness: an inference procedure is sound if it only derives things that are actually entailed. It never lies.
• Completeness: a procedure is complete if it can derive everything that is entailed. It never misses.

Key idea: KB entails A means A holds in every model where KB holds; a good inference method is both sound (only true conclusions) and complete (all true conclusions).

Inference rules and a worked proof

Rather than build giant truth tables, we can chain small inference rules. The most famous is modus ponens: from P and (P implies Q), conclude Q.

Worked example. Suppose the knowledge base says:

1. It is raining. (R)
2. If it is raining, the ground is wet. (R implies W)
3. If the ground is wet, the game is canceled. (W implies C)

Derive whether the game is canceled (C):

• From (1) R and (2) R implies W, modus ponens gives W (the ground is wet).
• From that W and (3) W implies C, modus ponens gives C (the game is canceled).

So KB entails C. We reached a guaranteed conclusion by chaining two valid steps, no truth table required.

Key idea: inference rules like modus ponens let us chain facts into new guaranteed conclusions without enumerating every model.

Reasoning by refutation

Automated provers often prove KB entails A by refutation: assume the opposite (NOT A), add it to the knowledge base, and show the result is a contradiction. If assuming A is false breaks everything, then A must be true. The resolution inference rule, applied to sentences in a standard clause form, is a single rule that is complete for propositional logic using exactly this strategy. It is the engine inside many logic-based systems.

Conjunctive normal form: getting clauses to resolve

Resolution operates on one syntactic shape only, so everything must first be converted to conjunctive normal form (CNF): an AND of clauses, where each clause is an OR of literals, and a literal is a proposition or its negation. Every propositional sentence has an equivalent CNF, reached by a fixed procedure.

Worked conversion. Put (A implies (B OR C)) AND NOT(B AND D) into CNF.

1. Eliminate biconditionals (none here). In general, P iff Q becomes (NOT P OR Q) AND (NOT Q OR P).
2. Eliminate implications using P implies Q == NOT P OR Q. The first conjunct becomes NOT A OR B OR C.
3. Push negations inward with De Morgan's laws. NOT(B AND D) becomes NOT B OR NOT D.
4. Distribute OR over AND if needed (not needed here).

The result is (NOT A OR B OR C) AND (NOT B OR NOT D), which as a clause set is

{ NOT A, B, C }        { NOT B, NOT D }

Each clause is just a set of literals, and the whole knowledge base is the conjunction of them all.

The resolution rule

Resolution takes two clauses containing exactly one complementary pair of literals and produces a new clause containing everything else:

from (alpha OR L) and (beta OR NOT L), infer (alpha OR beta)

The new clause is the resolvent. The intuition is a case split: either L is true, in which case the second clause forces beta; or L is false, in which case the first forces alpha. Either way, alpha OR beta holds.

A full resolution refutation on concrete clauses

Take a knowledge base that plain modus ponens cannot handle, because one rule has a disjunction in its conclusion.

1. If the alarm sounds, there is a fire or a drill. A implies (F OR D)
2. If there is a drill, the manager was notified. D implies M
3. The manager was not notified. NOT M
4. The alarm sounded. A

Goal: show the knowledge base entails F - there is a fire.

Step 1, convert everything to clauses and negate the goal. Refutation adds NOT F and aims for a contradiction.

C1: { NOT A, F, D }      from  A implies (F OR D)
C2: { NOT D, M }         from  D implies M
C3: { NOT M }            given
C4: { A }                given
C5: { NOT F }            NEGATED GOAL

Step 2, resolve until the empty clause appears. Each line names the two parent clauses and the literal resolved on.

C6 = resolve(C2, C3) on M
     { NOT D, M } + { NOT M }        ->  { NOT D }
     "no drill was held, since the manager was never notified"

C7 = resolve(C1, C4) on A
     { NOT A, F, D } + { A }         ->  { F, D }
     "the alarm sounded, so it is a fire or a drill"

C8 = resolve(C7, C6) on D
     { F, D } + { NOT D }            ->  { F }
     "it was not a drill, so it is a fire"

C9 = resolve(C8, C5) on F
     { F } + { NOT F }               ->  { }   EMPTY CLAUSE

The empty clause is a clause with no literals, and it can never be satisfied - there is nothing in it that could be true. Deriving it means the set KB together with NOT F is unsatisfiable, which is exactly the definition of KB entails F. The fire is proved.

Notice what made this necessary. Clause C1 encodes a rule whose conclusion is a disjunction, so modus ponens has nothing to fire on: knowing A tells you "fire or drill" and no more. Resolution handled it by using C3 and C2 to rule out the drill and letting the remaining case stand. That capacity for reasoning by elimination is precisely what resolution adds over forward chaining with modus ponens, which is complete only for Horn clauses - those with at most one positive literal.

Two cautions about the rule

First, resolve on exactly one complementary pair. It is tempting, given {P, Q} and {NOT P, NOT Q}, to cancel both pairs and declare the empty clause. That inference is unsound: set P = true and Q = false and both parent clauses are satisfied, so no contradiction exists. Resolving correctly on P alone yields {Q, NOT Q}, a tautology carrying no information - which is the honest answer.

Second, resolution is refutation-complete, not complete in the everyday sense. It will always derive the empty clause from an unsatisfiable set, which is what proving entailment requires. It will not generate every sentence entailed by a knowledge base: from {P} alone it cannot produce {P, Q}, even though that is entailed. Always run it in the refutation pattern - negate what you want to prove, then look for the empty clause.

Key idea: proof by refutation shows A is entailed by deriving a contradiction from KB together with NOT A, and resolution is a complete rule for doing so.

How hard is this? SAT and the theory-practice gap

Deciding whether a set of clauses is satisfiable is the SAT problem, and Cook proved in 1971 that it is NP-complete - the first problem shown to be so. The brute-force cost is stark: a truth table over 100 propositions has 2100 rows, about 1.3 * 1030, which no amount of hardware will ever enumerate.

And yet modern SAT solvers routinely dispatch industrial instances with millions of variables, and they are standard equipment in hardware verification, software model checking, and planning. The bridge is a family of algorithms descending from the Davis-Putnam-Logemann-Loveland procedure of 1962 - essentially backtracking search over assignments with unit propagation - extended by conflict-driven clause learning, which records why each dead end failed so the same mistake is never repeated.

The moral generalises past logic. NP-completeness is a statement about the worst case over all possible inputs. Real inputs carry structure, and algorithms that exploit structure can be fast on the instances people actually have while remaining exponential in theory. Do not read a hardness result as a verdict that a problem is hopeless in practice, and do not read practical speed as a refutation of the hardness result.

Where people get stuck

• "If P then Q is false when P is false." With a false premise the implication is true. A promise about rainy days is not broken by a dry one.
• "OR means one or the other but not both." Logical OR is inclusive and is true when both disjuncts are true. Exclusive-or is a different connective.
• "Sound and complete mean the same thing." Sound means only entailed conclusions are derived; complete means all entailed conclusions can be derived. A procedure that outputs nothing is trivially sound; one that outputs everything is trivially complete.
• "Entailment depends on one lucky world." Entailment requires A to hold in every model where KB holds. Finding one model where both are true shows satisfiability, not entailment.
• Resolving on two complementary pairs at once. From {P, Q} and {NOT P, NOT Q} this "derives" the empty clause, but P = true, Q = false satisfies both parents. Cancel one pair only.
• Expecting resolution to generate all consequences. It is refutation-complete, not generatively complete. Negate the goal and hunt for the empty clause; do not run it forward and expect the answer to appear.
• Skipping CNF conversion. Resolution applies to clauses. An unconverted implication has no complementary literal to resolve on, and the rule simply does not apply.
• Forgetting that modus ponens is not enough. It is complete only for Horn clauses. The alarm example needs resolution precisely because A implies (F OR D) has two positive literals.
• Reading NP-completeness as impossibility. SAT is NP-complete and modern solvers still handle millions of variables on structured instances. Worst-case hardness and practical performance are different claims.

Recap

• Knowledge representation stores facts; logic derives new guaranteed conclusions.
• Propositions combine with NOT, AND, OR, implication, and biconditional; implication is false only for a true premise with a false conclusion.
• Truth tables evaluate all 2ⁿ assignments and classify sentences as tautology, contradiction, or contingent.
• KB entails A means A is true in every model where KB is true; good inference is sound and complete.
• Resolution works on CNF clauses: from (alpha OR L) and (beta OR NOT L) infer (alpha OR beta), cancelling exactly one complementary pair.
• Refutation proves A by adding NOT A and deriving the empty clause. The alarm example reaches it in four resolution steps and proves F despite a disjunctive rule that modus ponens cannot use.
• SAT is NP-complete, yet DPLL with conflict-driven clause learning makes million-variable industrial instances routine.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Robinson, J. A. (1965). A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1), 23-41. doi.org/10.1145/321250.321253
3. Davis, M., Logemann, G., & Loveland, D. (1962). A machine program for theorem-proving. Communications of the ACM, 5(7), 394-397. doi.org/10.1145/368273.368557
4. Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151-158. doi.org/10.1145/800157.805047
5. Shapiro, S., & Kouri Kissel, T. (2026). Classical logic. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
6. Thomason, R. (2024). Logic-based artificial intelligence. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
7. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io

The big picture

Propositional logic can only talk about whole statements being true or false. It has no way to say "all humans are mortal" without listing every human by name. First-order logic (FOL) fixes this by letting us talk about objects, their properties, the relations between them, and, crucially, quantities like "all" and "some."

Why it matters: FOL is expressive enough to capture most of ordinary mathematical and commonsense knowledge, which is why it underlies formal knowledge bases, theorem provers, and the semantics of many AI systems.

What FOL adds over propositional logic

Propositional logic knows only atomic true-or-false facts. FOL breaks a fact into parts:

• Constants name specific objects (Socrates, 7, Paris).
• Variables stand for objects in general (x, y).
• Predicates express properties or relations that are true or false of objects. Human(x) says x is human; Taller(x, y) says x is taller than y.
• Functions map objects to objects. MotherOf(x) denotes x's mother, an object, not a truth value.

So "Socrates is human" becomes Human(Socrates), and "Paris is the capital of France" becomes Capital(Paris, France). The difference from propositional logic is that we can now see inside a fact and reason about the objects it mentions.

Key idea: first-order logic adds objects, predicates (properties and relations), and functions, so it can reason about the internal structure of facts.

The two quantifiers

The real power comes from quantifiers, which let one sentence range over many objects.

• Universal (for all x): the statement holds for every object. "All humans are mortal" is: for all x, Human(x) implies Mortal(x).
• Existential (there exists x): the statement holds for at least one object. "Some human is a philosopher" is: there exists x such that Human(x) AND Philosopher(x).

Two pairing rules are worth memorizing, because beginners often swap them:

• Universal naturally pairs with implication: for all x, Human(x) implies Mortal(x). Using AND here would wrongly claim everything is human.
• Existential naturally pairs with conjunction (AND): there exists x, Human(x) AND Philosopher(x). Using implication here would be satisfied too easily by any non-human.

Key idea: "for all" pairs with implication and "there exists" pairs with AND, and swapping them changes the meaning entirely.

A worked translation

Translate: "Every dog has an owner."

• Identify objects and relations: dogs, owners, and the Owns relation.
• "Every dog" is universal; "has an owner" asserts existence of an owner.
• Result: for all x, Dog(x) implies (there exists y such that Owns(y, x)).

Read it back: for every object x, if x is a dog, then there is some object y that owns x. The nesting of a "there exists" inside a "for all" is what lets each dog have a possibly different owner.

Key idea: nesting an existential inside a universal expresses "each of these has some (possibly different) that."

Quantifier order changes the claim

Swapping two adjacent quantifiers of different kinds produces a genuinely different sentence, and this is the single most common source of translation errors. Compare:

• for all x, there exists y, Loves(x, y) - everybody loves somebody, and the somebody may differ from person to person.
• there exists y, for all x, Loves(x, y) - there is one particular individual whom everybody loves.

Build a world that separates them. Take three people A, B, and C, where A loves B, B loves C, and C loves A, and nobody loves anyone else.

• First sentence: A has someone (B), B has someone (C), C has someone (A). True.
• Second sentence: is there one person everyone loves? B is loved only by A, C only by B, A only by C. False.

So the two are not equivalent. The implication runs one way only: the second sentence entails the first (if one universally beloved person exists, then certainly everyone loves someone), but not the reverse. The rule of thumb: an inner quantifier may depend on an outer one, never the other way round. Two quantifiers of the same kind commute freely - for all x, for all y means the same as for all y, for all x - so only mixed pairs need care.

The classic syllogism, now provable

FOL finally lets us formalize the oldest example in logic:

1. For all x, Human(x) implies Mortal(x). (All humans are mortal.)
2. Human(Socrates). (Socrates is human.)

To conclude Mortal(Socrates), we use universal instantiation: a "for all x" statement can be specialized to any particular object. Substituting x = Socrates into rule (1) yields Human(Socrates) implies Mortal(Socrates). Combined with fact (2) by modus ponens, we get Mortal(Socrates). The step that finds the right substitution (here x = Socrates) is called unification, and it is the core operation of automated first-order reasoning.

Key idea: universal instantiation specializes a "for all" rule to a specific object, and unification is the matching step that makes it work.

Unification, precisely

Unification takes two expressions and finds a substitution that makes them identical, or reports failure. A substitution is a list of variable-to-term bindings written like {x/Jane}.

Unify these	Result
Knows(John, x) and Knows(John, Jane)	{x/Jane}
Knows(John, x) and Knows(y, Mother(y))	{y/John, x/Mother(John)}
Knows(John, x) and Knows(x, Elizabeth)	fails as written
Knows(John, x) and Knows(z, Elizabeth)	{z/John, x/Elizabeth}

The third row fails only because the same variable name x appears in both expressions and cannot be bound to John and Elizabeth at once. The variables in different clauses are unrelated, so the fix is to standardise apart - rename variables so no two clauses share one - and then the fourth row succeeds. Every serious implementation renames before every attempt.

One further requirement, the occurs check: unifying x with f(x) must fail, because no finite term satisfies it. Skipping the check builds an infinite term and makes the prover unsound. Most Prolog systems omit it by default for speed, which is a deliberate and documented trade of correctness for performance.

From FOL sentences to clauses: Skolemisation

To run resolution on first-order sentences they must first become clauses, and quantifiers have to go. Universals are dropped and their variables left implicit. Existentials are removed by Skolemisation: replace the existentially quantified variable with a new name that records what it depends on.

• An existential not inside any universal becomes a fresh Skolem constant. there exists y, Cat(y) becomes Cat(C1) - "call that cat C1".
• An existential inside a universal becomes a Skolem function of the enclosing variables, because the witness may differ for each one.

Worked conversion. Take "Every dog has an owner": for all x, Dog(x) implies (there exists y, Owns(y, x)).

1. Eliminate the implication
   for all x, ( NOT Dog(x) OR (there exists y, Owns(y, x)) )

2. Skolemise. The y sits inside the scope of x, so the owner
   may depend on which dog we have. Replace y by f(x).
   for all x, ( NOT Dog(x) OR Owns(f(x), x) )

3. Drop the universal quantifier; free variables are read as universal.
   CLAUSE:  { NOT Dog(x), Owns(f(x), x) }

Here f is a brand-new function symbol meaning "the owner of". Using a constant instead of a function would have said all dogs share one owner - a strictly stronger and false claim. Skolemisation does not preserve logical equivalence, but it does preserve satisfiability, which is all a refutation proof needs.

Resolution in first-order logic, worked

Now put unification and clauses together. The knowledge base:

1. All humans are mortal: for all x, Human(x) implies Mortal(x)
2. All Greeks are human: for all y, Greek(y) implies Human(y)
3. Socrates is Greek: Greek(Socrates)

Goal: prove Mortal(Socrates). Convert and negate the goal:

C1: { NOT Human(x), Mortal(x) }
C2: { NOT Greek(y), Human(y) }
C3: { Greek(Socrates) }
C4: { NOT Mortal(Socrates) }          NEGATED GOAL

Each resolution step now needs a unifier as well as a complementary pair:

C5 = resolve(C3, C2)
     unify  Greek(Socrates)  with  Greek(y)     ->  { y/Socrates }
     apply to the rest of C2:  { Human(Socrates) }

C6 = resolve(C5, C1)
     unify  Human(Socrates)  with  Human(x)     ->  { x/Socrates }
     apply to the rest of C1:  { Mortal(Socrates) }

C7 = resolve(C6, C4)
     unify  Mortal(Socrates) with Mortal(Socrates)  ->  { }  (already identical)
     nothing remains:          { }   EMPTY CLAUSE

The empty clause appears, so KB together with NOT Mortal(Socrates) is unsatisfiable and the knowledge base entails Mortal(Socrates). Compare this with the propositional case in the previous lesson: the rule and the refutation strategy are identical, and the only addition is that each step must find a substitution making two literals match. That single addition is what lets one clause, {NOT Human(x), Mortal(x)}, stand in for infinitely many propositional facts.

Power and cost

FOL is far more expressive than propositional logic, but that expressiveness has a price. General first-order inference is semidecidable: if a sentence is entailed, a complete procedure will eventually confirm it, but if it is not entailed, the procedure may run forever without ever saying "no." Propositional logic, by contrast, is fully decidable. This trade-off (more expressive power, weaker guarantees of termination) is a recurring theme in knowledge representation.

Be precise about what semidecidable means, because the phrase is often used loosely. Two theorems bracket the situation. Godel's completeness theorem (1930) guarantees that every entailment in first-order logic has a finite proof, and resolution is refutation-complete, so a prover searching systematically will find it eventually. Church and Turing showed independently in 1936 that first-order validity is undecidable: no algorithm can always terminate with a correct yes-or-no answer. Put together, a prover that has been running for an hour without success leaves you unable to distinguish "no proof exists" from "the proof is longer than an hour". In practice systems impose a time or depth limit and report "unknown", which is an honest answer rather than a bug.

The contrast with propositional logic is exact. Propositional entailment is decidable - a truth table always terminates - but NP-complete, so it is hard yet answerable. First-order entailment is not merely harder; it is a different kind of problem. This is why practical knowledge representation so often uses restricted fragments: Horn clauses (the basis of Prolog and Datalog) and description logics (the basis of OWL and the semantic web) both give up expressiveness deliberately to recover decidable, and often tractable, inference.

A limit that logic exposed: the frame problem

Logic makes one difficulty unusually visible. Suppose a robot picks up a block. You must assert not only what changed but everything that did not: the colour of the block is unchanged, the position of every other block is unchanged, the time of day is unchanged, and so on for every property in the knowledge base. With n properties and m actions, a naive axiomatisation needs on the order of n * m of these "nothing else happened" axioms.

This is the frame problem, identified by McCarthy and Hayes in 1969. Technical fixes exist - successor-state axioms, which say what makes a property true rather than listing what leaves it alone - and they work well for closed, well-specified domains. The broader philosophical version, which asks how any agent decides what is relevant to consider at all, remains open and is a live topic in philosophy of mind. It is a good example of a problem that only became visible because someone tried to write the knowledge down formally.

Key idea: first-order logic buys great expressive power at the cost of only semidecidable inference, unlike decidable propositional logic.

Where people get stuck

• "Predicates and functions are the same." A predicate returns true or false; a function returns an object. Mother(x) denotes a person and cannot stand alone as a sentence; Human(x) is a sentence and cannot be an argument to another function.
• "For all should pair with AND." Writing for all x, Human(x) AND Mortal(x) claims every object in the universe is human. Use implication.
• "There exists should pair with implication." Writing there exists x, Human(x) implies Philosopher(x) is satisfied by any non-human, since a false premise makes the implication true. Use AND.
• Swapping mixed quantifiers. "Everybody loves somebody" and "somebody is loved by everybody" differ, and the three-person cycle shows the first true while the second is false.
• Skolemising an inner existential to a constant. "Every dog has an owner" needs f(x), not a constant, or you have asserted that all dogs share a single owner.
• Failing to standardise variables apart. Two clauses that both use x are unrelated, and unification will spuriously fail until the variables are renamed.
• Omitting the occurs check. Unifying x with f(x) must fail. Allowing it constructs an infinite term and makes the prover unsound.
• "FOL inference always terminates." It is semidecidable: entailments are eventually found, non-entailments may loop forever. A long-running prover is not necessarily broken.
• Assuming logic captures uncertainty. Everything here is categorical - a sentence is entailed or it is not. "Probably mortal" has no representation, which is exactly the gap the next module fills.

Recap

• FOL adds constants, variables, predicates, and functions to reason about objects and their relations.
• Universal (for all) and existential (there exists) quantifiers generalize over objects; "for all" pairs with implication and "there exists" pairs with AND.
• Mixed quantifier order is significant: an inner quantifier may depend on an outer one, never the reverse.
• Universal instantiation plus unification proves specific facts like Mortal(Socrates). Unification returns a substitution such as {y/Socrates}, requires standardising variables apart, and needs the occurs check to stay sound.
• Clause conversion drops universals and Skolemises existentials: a fresh constant when unnested, a function of the enclosing variables when nested.
• First-order resolution is propositional resolution plus unification, and it refutes the Socrates goal in three steps.
• FOL is more expressive than propositional logic but only semidecidable - proofs are always findable, non-entailment may never terminate - which is why Horn clauses and description logics trade expressiveness for decidability.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Enderton, H. B. (2001). A mathematical introduction to logic (2nd ed.). Academic Press. find source ↗
3. Robinson, J. A. (1965). A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1), 23-41. doi.org/10.1145/321250.321253
4. Shanahan, M. (2016). The frame problem. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
5. Thomason, R. (2024). Logic-based artificial intelligence. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
6. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
7. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu

The big picture

Logic assumes we know facts for certain. The real world rarely cooperates: sensors are noisy, the future is unknown, and information is incomplete. Probability is the mathematics of reasoning when you are not sure. It lets an agent hold beliefs graded by confidence and update them as evidence arrives.

Why it matters: nearly every modern AI system, from spam filters to self-driving perception to large language models, reasons probabilistically. This lesson builds the vocabulary you need before the next one on Bayesian updating.

Probability as a degree of belief

A probability is a number between 0 and 1 measuring how likely something is: 0 means impossible, 1 means certain, 0.5 means "as likely as not." We write P(A) for the probability of event A. Two anchoring rules:

• Every probability satisfies 0 <= P(A) <= 1.
• The probabilities of all mutually exclusive outcomes that cover every case sum to 1. For a fair die, P(1) + P(2) + ... + P(6) = 1, with each equal to 1/6.

The probability of an event is the sum of the probabilities of the outcomes in it. For "roll an even number" on a fair die: P(even) = P(2) + P(4) + P(6) = 1/6 + 1/6 + 1/6 = 3/6 = 1/2.

Key idea: a probability is a degree of belief between 0 and 1, and the probabilities of all outcomes sum to 1.

Joint, marginal, and conditional probability

Three flavors of probability come up constantly.

• Joint probability P(A and B): the chance that both A and B happen.
• Marginal probability P(A): the chance of A regardless of anything else, found by summing the joint over the other variable ("marginalizing").
• Conditional probability P(A given B): the chance of A once you already know B is true. This is how evidence enters.

The definition that links them is:

P(A given B) = P(A and B) / P(B), provided P(B) > 0.

In words: restrict attention to the worlds where B holds, then ask what fraction of those also have A.

Key idea: conditional probability P(A given B) equals the joint P(A and B) divided by P(B), narrowing the world to cases where B is true.

A worked example

A standard deck has 52 cards, 26 of them red, and 12 face cards (jack, queen, king in each of four suits). There are 6 red face cards. What is P(face card given red)?

1. P(red) = 26/52 = 1/2.
2. P(face and red) = 6/52.
3. P(face given red) = (6/52) / (26/52) = 6/26 = 3/13, which is about 0.231.

Check it directly: among the 26 red cards, 6 are face cards, and 6/26 = 3/13. The two methods agree.

Key idea: conditioning on "red" shrinks the sample space from 52 cards to 26, and the answer is the fraction of those that are face cards.

The full joint distribution: everything in one table

For a set of variables, the full joint distribution assigns a probability to every combination of values. Once you have it, every probabilistic question is answerable by adding up cells. Here is the standard dental example with three boolean variables - Cavity, Toothache, and Catch (the dentist's probe catches in the tooth).

	toothache		no toothache
	catch	no catch	catch	no catch
cavity	0.108	0.012	0.072	0.008
no cavity	0.016	0.064	0.144	0.576

All eight cells sum to 1.000, as they must. Now answer three different questions with nothing but addition and division.

Marginalising. To get P(cavity), add every cell where cavity is true:

P(cavity) = 0.108 + 0.012 + 0.072 + 0.008 = 0.200

Summing out the variables you do not care about is called marginalisation, and it is the reason single-variable probabilities are called marginals.

Conditioning. A patient walks in with a toothache. What is the chance of a cavity?

P(toothache)          = 0.108 + 0.012 + 0.016 + 0.064 = 0.200
P(cavity AND toothache) = 0.108 + 0.012                 = 0.120

P(cavity | toothache) = 0.120 / 0.200 = 0.60

The toothache raised the probability of a cavity from 0.20 to 0.60 - a threefold jump. That is evidence doing its job.

Normalisation. There is a shortcut worth learning, because it avoids computing P(toothache) separately. Collect the unnormalised numbers for both values of Cavity and rescale them to sum to 1:

unnormalised:  cavity 0.120,  no cavity 0.016 + 0.064 = 0.080
total:         0.120 + 0.080 = 0.200
normalise:     0.120/0.200 = 0.60,   0.080/0.200 = 0.40

The denominator you would have divided by is the total, so it never needs separate calculation. This trick reappears constantly in Bayesian inference, where the denominator is the awkward term.

Conditional independence, the idea that rescues everything

Two variables can be dependent overall yet independent once you know a third. Test it here. Does knowing about a toothache change the chance the probe catches, if we already know there is a cavity?

P(catch | cavity)              = (0.108 + 0.072) / 0.200 = 0.180 / 0.200 = 0.90
P(catch | cavity, toothache)   =  0.108 / 0.120                        = 0.90

P(catch | no cavity)            = (0.016 + 0.144) / 0.800 = 0.160 / 0.800 = 0.20
P(catch | no cavity, toothache) =  0.016 / 0.080                        = 0.20

Identical in both cases. So Catch is conditionally independent of Toothache given Cavity. The intuition is causal: the cavity is what produces both the ache and the catch, so once the cavity is known, the ache carries no further news about the probe. Toothache and Catch are certainly not independent unconditionally - both are symptoms of the same underlying cause - which is exactly why the qualifier "given Cavity" matters.

Why this matters: the size of the table

The full joint is universally powerful and almost never usable. With n boolean variables it has 2n cells and needs 2n - 1 independent numbers.

• n = 10: about 1000 numbers. Fine.
• n = 30: 230, roughly 1.07 billion numbers. Already hopeless to estimate from data.
• n = 100: about 1.3 * 1030. Not storable, and no dataset could ever fill it.

Conditional independence is the escape. In the dental example the full joint needs 7 independent numbers, but the factored form needs only 5: P(Cavity) is one number, P(Toothache | Cavity) is two (one per value of Cavity), and P(Catch | Cavity) is two more. With n symptoms all conditionally independent given the disease, the count drops from 2n+1 - 1 to 2n + 1 - exponential to linear.

The general tool that assembles a joint distribution out of small conditional pieces is the chain rule:

P(A, B, C) = P(A) * P(B | A) * P(C | A, B)

Every conditional independence you can justify lets you delete conditions from these factors and shrink the table. That observation, systematised, is the Bayesian network of the next lesson.

Key idea: the full joint answers everything but is exponentially large; conditional independence factors it into small pieces and is what makes probabilistic AI possible at all.

Independence

Two events are independent when knowing one tells you nothing about the other. Formally, A and B are independent if P(A and B) = P(A) times P(B), equivalently P(A given B) = P(A). Successive fair coin flips are independent: a run of heads does not change the next flip's 1/2. Independence is powerful because it lets us multiply simple probabilities instead of tracking a huge joint table.

Worked example. Two independent fair coins. P(both heads) = P(H) times P(H) = 1/2 times 1/2 = 1/4. Listing the four equally likely outcomes (HH, HT, TH, TT) confirms exactly one is HH, so 1/4.

Key idea: independent events multiply, P(A and B) = P(A) times P(B), because one carries no information about the other.

Random variables and expectation

A random variable is a quantity whose value depends on chance, such as the number rolled on a die. Its expected value (mean) is the long-run average, computed by weighting each value by its probability:

E[X] = sum over values of (value times its probability).

Worked example. For one fair die, E[X] = (1 + 2 + 3 + 4 + 5 + 6) times (1/6) = 21/6 = 3.5. You never roll a 3.5, but over many rolls the average settles near it. Expected value is exactly how a rational agent scores uncertain outcomes, which connects back to the utility-based agents from Module 1.

Key idea: the expected value of a random variable is the probability-weighted average of its outcomes, the long-run mean.

Why probability, and not something else?

Grading belief with numbers between 0 and 1 can look like an arbitrary modelling choice, and in the 1970s and 1980s it was widely treated as one. MYCIN and other expert systems used hand-designed "certainty factors" with their own combination rules, chosen for intuitive appeal rather than derived from anything. Those schemes turned out to behave badly - they could be sensitive to the order evidence arrived in, and they double-counted correlated evidence.

Two results explain why probability is not merely one option among many.

• The Dutch book argument. Treat your degrees of belief as the odds at which you would accept bets. If those degrees violate the probability axioms, someone can offer you a collection of bets you consider individually fair whose combined outcome loses you money with certainty. Coherent betting behaviour forces the axioms on you.
• Cox's theorem. Suppose you want to represent plausibility by a single real number, want consistency (two valid routes to the same conclusion must agree), and want the ordering to respect common sense. Any system meeting those conditions turns out to be probability theory in disguise, up to rescaling.

Neither result says probability is easy or that the numbers are easy to obtain. They say that if you want graded belief that cannot be exploited and does not contradict itself, you do not get to invent your own arithmetic. That is a strong reason to learn the standard machinery rather than improvise.

Where people get stuck

• "P(A given B) equals P(B given A)." These are generally very different. P(has disease | tested positive) and P(tested positive | has disease) can differ by orders of magnitude, as the next lesson demonstrates numerically. Confusing them is the single most consequential probability error in applied AI.
• "A run of heads makes tails due." Independent trials have no memory. The gambler's fallacy survives because people expect short sequences to look like long-run averages.
• Confusing independence with conditional independence. Toothache and Catch are dependent overall and independent given Cavity. Neither property implies the other in either direction.
• Forgetting that conditioning renormalises. Conditioning on B does not just filter; it rescales so the remaining probabilities sum to 1. That division by P(B) is the whole content of the definition.
• "Expected value is the most likely outcome." It is the probability-weighted average. A fair die has expectation 3.5, a value it can never produce.
• "Probabilities can exceed 1." Every probability lies in [0, 1]. A result outside that range means an arithmetic error, usually a missing normalisation.
• Assuming independence to make the maths easy. It is a substantive empirical claim, not a convenience. Wrongly assuming independent evidence sources double-counts correlated evidence and produces overconfident conclusions.
• Reaching for the full joint. It answers everything and is unusable past about twenty variables. The engineering work is finding the conditional independences that let you avoid building it.

Recap

• Probability grades belief from 0 to 1, and all outcomes sum to 1.
• Joint, marginal, and conditional probabilities describe combined, overall, and evidence-based chances.
• P(A given B) = P(A and B) / P(B) narrows the world to cases where B holds and renormalises.
• The full joint distribution answers every query by summing cells: in the dental table, P(cavity) = 0.20 rises to P(cavity | toothache) = 0.60.
• Normalising unnormalised values avoids computing the denominator separately.
• Independent events multiply: P(A and B) = P(A) * P(B). Conditional independence is different: Catch and Toothache are dependent, but independent given Cavity, both at 0.90 and 0.20.
• A joint over n booleans needs 2n - 1 numbers - about a billion at n = 30. Conditional independence factors it, turning 2n+1 - 1 into 2n + 1 for a disease with n symptoms.
• Expected value is the probability-weighted average, and the Dutch book and Cox arguments show probability is forced, not chosen.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Koller, D., & Friedman, N. (2009). Probabilistic graphical models: Principles and techniques. MIT Press. find source ↗
3. Hajek, A. (2023). Interpretations of probability. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
4. Joyce, J. (2003). Bayes' theorem. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
5. Pearl, J. (1986). Fusion, propagation, and structuring in belief networks. Artificial Intelligence, 29(3), 241-288. doi.org/10.1016/0004-3702(86)90072-X
6. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io
7. University of California, Berkeley. (n.d.). CS188: Introduction to artificial intelligence. inst.eecs.berkeley.edu

The big picture

Bayes' rule is a single formula that tells an agent how to update its beliefs when new evidence arrives. It is the mathematical answer to "I believed X; now I have observed Y, so how much should I believe X now?" This one idea powers medical diagnosis, spam filters, and countless AI systems that must revise their opinions as data comes in.

Why it matters: the most common reasoning error people make, and one machines can avoid, is ignoring how rare something is. Bayes' rule forces the base rate into the calculation, which is why a positive test for a rare disease is far less alarming than it first appears.

The formula and its four parts

Bayes' rule relates two conditional probabilities that are easy to confuse:

P(H given E) = P(E given H) times P(H) / P(E)

Read H as a hypothesis (a disease, the label "spam") and E as the evidence (a positive test, a word in an email). The pieces have names:

• Prior P(H): your belief before seeing the evidence, often the base rate.
• Likelihood P(E given H): how probable the evidence is if the hypothesis is true.
• Posterior P(H given E): your updated belief after seeing the evidence, the thing you want.
• Evidence P(E): how probable the evidence is overall, which acts as a normalizer.

The key insight is that P(H given E) and P(E given H) are not the same. Bayes' rule is exactly the bridge that converts the one you can measure into the one you want.

Key idea: Bayes' rule updates a prior into a posterior using the likelihood and the overall probability of the evidence.

Finding P(E): the law of total probability

The denominator P(E) is usually computed by adding up the ways the evidence can occur, whether or not the hypothesis holds:

P(E) = P(E given H) times P(H) + P(E given not-H) times P(not-H)

The first term is true positives; the second is false positives. For a rare disease, the false-positive term can dominate simply because so many people do not have the disease.

Key idea: the evidence probability P(E) combines true positives and false positives, and for rare hypotheses the false positives often dominate.

The classic medical-test example

A disease affects 1% of people. A test is 90% sensitive (if you have it, it flags positive 90% of the time) and has a 9% false-positive rate (if you do not have it, it still flags positive 9% of the time). You test positive. What is the chance you actually have the disease?

Let H = "has disease," E = "positive test." Given values:

• Prior P(H) = 0.01, so P(not-H) = 0.99.
• Likelihood P(E given H) = 0.90.
• False positive P(E given not-H) = 0.09.

Step 1, compute P(E):

P(E) = (0.90 times 0.01) + (0.09 times 0.99) = 0.009 + 0.0891 = 0.0981.

Step 2, apply Bayes' rule:

P(H given E) = (0.90 times 0.01) / 0.0981 = 0.009 / 0.0981, which is about 0.0917, roughly 9%.

Even after a positive test, there is only about a 9% chance you have the disease. The reason is the base rate: the disease is so rare that the many false positives from the 99% healthy majority swamp the true positives. This is the famous base-rate fallacy, ignoring the prior, and Bayes' rule is the cure.

Key idea: a positive test for a rare condition can still leave the true probability low, because the prior (base rate) heavily weights the result.

Sanity-check the arithmetic

Imagine 10,000 people. About 100 have the disease (1%), and 90 of them test positive (90%). Of the 9,900 healthy people, 9% or about 891 test positive too. Total positives: 90 + 891 = 981. Fraction truly sick among positives: 90 / 981, which is about 0.0917, the same 9%. Counting people confirms the formula.

Key idea: reasoning with actual counts of a large population reproduces the Bayesian answer and makes it intuitive.

Naive Bayes and why it matters for AI

To handle many pieces of evidence at once (say, all the words in an email), the naive Bayes classifier assumes the pieces are independent given the hypothesis. That assumption is usually not strictly true, hence "naive," yet it works remarkably well and made early spam filters both fast and accurate. It is a clean example of how a simple probabilistic model, updated by Bayes' rule, becomes a practical machine-learning tool. Belief updating like this also generalizes to Bayesian networks, graphs that track many interdependent variables.

Key idea: naive Bayes applies Bayes' rule with an independence assumption to combine many clues, powering practical classifiers like spam filters.

A Bayesian network, and a query computed by hand

A Bayesian network is a directed acyclic graph in which each node is a variable, each edge points from a cause to something it influences, and each node carries a conditional probability table (CPT) giving its distribution for every combination of its parents' values. The graph is a compact encoding of conditional independence: a node is independent of its non-descendants given its parents.

Here is a three-node network. Rain and Sprinkler both cause WetGrass, and neither influences the other.

     Rain            Sprinkler
        |             |
        +-----+ +-----+
              v v
           WetGrass

The three CPTs, which together define the whole joint distribution:

P(Rain)
rain	0.2
no rain	0.8

P(Sprinkler)
on	0.4
off	0.6

Rain	Sprinkler	P(WetGrass = wet)
rain	on	0.99
rain	off	0.80
no rain	on	0.90
no rain	off	0.00

Query: the grass is wet. How likely is it that it rained? We want P(rain | wet). The recipe is to compute the joint probability of each value of Rain together with the evidence, summing out the variables we do not observe, then normalise.

Step 1 -- P(rain AND wet), summing over Sprinkler:

  P(rain) * [ P(on)  * P(wet | rain, on)
            + P(off) * P(wet | rain, off) ]

  = 0.2 * [ 0.4 * 0.99  +  0.6 * 0.80 ]
  = 0.2 * [ 0.396       +  0.480      ]
  = 0.2 * 0.876
  = 0.1752

Step 2 -- P(no rain AND wet), summing over Sprinkler:

  P(no rain) * [ P(on)  * P(wet | no rain, on)
               + P(off) * P(wet | no rain, off) ]

  = 0.8 * [ 0.4 * 0.90  +  0.6 * 0.00 ]
  = 0.8 * [ 0.360       +  0.000      ]
  = 0.8 * 0.36
  = 0.2880

Step 3 -- normalise:

  P(wet)        = 0.1752 + 0.2880 = 0.4632
  P(rain | wet) = 0.1752 / 0.4632 = 0.3782

Wet grass raises the probability of rain from its prior of 0.20 to about 0.378 - not conclusive, because the sprinkler is a competing explanation.

Explaining away: evidence that cuts both ways

Now suppose you also notice the sprinkler is running. Recompute with both pieces of evidence, and this time no summation is needed because every variable is fixed:

P(rain, on, wet)    = 0.2 * 0.4 * 0.99 = 0.0792
P(no rain, on, wet) = 0.8 * 0.4 * 0.90 = 0.2880
                              total    = 0.3672

P(rain | wet, sprinkler on) = 0.0792 / 0.3672 = 0.2157

Belief in rain falls from 0.378 back to about 0.216. The sprinkler explains the wet grass, so rain is no longer needed to account for it. This is explaining away, and it is worth pausing on because it is a genuine surprise.

Rain and Sprinkler are marginally independent - there is no edge between them and no shared ancestor, so learning it rained tells you nothing about the sprinkler. But given that the grass is wet they become dependent, because the two compete to account for the same observation. Conditioning on a common effect creates a dependence between its causes. This pattern, a node with two parents converging on it, is called a collider, and it is the one case where conditioning on a variable adds a dependence instead of removing one. Doctors do this constantly without naming it: a second sufficient explanation for a symptom lowers the probability of the first.

Note also that 0.216 remains slightly above the prior of 0.20, because the sprinkler alone wets the grass only 90 percent of the time, so a little of the evidence is still unaccounted for.

Why networks are compact

A node with k parents needs 2k numbers in its CPT. If every node in an n-variable network has at most k parents, the whole network needs at most n * 2k numbers instead of the full joint's 2n - 1. At n = 30 with at most 3 parents each, that is 30 * 8 = 240 numbers rather than roughly 1.07 billion. The graph is not a picture drawn afterwards; it is the independence assumption, written down in a form you can check against domain knowledge.

Exact inference in general Bayesian networks is NP-hard, so large networks use approximate methods such as sampling. But the modelling gain is real regardless: it is often possible to elicit a few hundred conditional probabilities from experts, and never possible to elicit a billion.

Reasoning over time: one step of the HMM forward pass

When the world changes, the same machinery runs forward through time. A hidden Markov model has a hidden state that evolves and an observation emitted at each step. The classic example: you are underground and cannot see the weather, but you observe each day whether your colleague carries an umbrella.

Hidden state:   Rain(t) in { rain, no rain }
Observation:    Umbrella(t) in { yes, no }

Transition model    P(rain(t) | rain(t-1))     = 0.7
                    P(rain(t) | no rain(t-1))  = 0.3

Sensor model        P(umbrella | rain)         = 0.9
                    P(umbrella | no rain)      = 0.2

Prior at day 0      P(rain) = 0.5

Each forward step has two halves: predict using the transition model, then update using the observation.

DAY 1 -- you see an umbrella.

Predict (transition from the day-0 prior):
  P(rain_1)    = 0.7 * 0.5 + 0.3 * 0.5 = 0.35 + 0.15 = 0.5
  P(no rain_1) = 0.5

Update (multiply by the sensor model, then normalise):
  rain:    0.9 * 0.5 = 0.45
  no rain: 0.2 * 0.5 = 0.10
  total = 0.55
  P(rain_1 | umbrella_1) = 0.45 / 0.55 = 0.8182

DAY 2 -- you see an umbrella again.

Predict (transition from day 1's belief):
  P(rain_2)    = 0.7 * 0.8182 + 0.3 * 0.1818 = 0.5727 + 0.0545 = 0.6273
  P(no rain_2) = 0.3 * 0.8182 + 0.7 * 0.1818 = 0.2455 + 0.1273 = 0.3727

Update:
  rain:    0.9 * 0.6273 = 0.5645
  no rain: 0.2 * 0.3727 = 0.0745
  total = 0.6391
  P(rain_2 | umbrella_1, umbrella_2) = 0.5645 / 0.6391 = 0.8834

Belief in rain climbs from 0.50 to 0.818 to 0.883 as the umbrellas accumulate. Three features of this computation matter well beyond weather.

• It is recursive and constant-memory. Day 2 used only day 1's belief, not the raw observation history. The current belief state is a sufficient summary of everything seen so far, so tracking cost does not grow with time.
• Prediction always increases uncertainty; observation always reduces it. The predict step pulled 0.818 back toward 0.627 because the weather might have changed; the umbrella then pushed it up to 0.883.
• It is exactly a Kalman filter in discrete form. Swap the discrete states for Gaussians and you have the algorithm that tracks aircraft and localises robots. The predict-update loop is the same.

Key idea: filtering maintains a belief over hidden states by alternating a prediction step and an observation update, and the belief state is all you need to carry forward.

Where people get stuck

• "P(H given E) equals P(E given H)." These differ, often by an order of magnitude. In the medical example the likelihood is 0.90 and the posterior is 0.09. Bayes' rule is precisely the conversion between them, and the base rate is what separates them.
• "A 90% accurate test means a positive result is 90% likely to be right." Not for a rare condition. The 10,000-person count makes it concrete: 90 true positives against 891 false positives.
• "The prior does not matter once you have evidence." The prior multiplies the likelihood in every posterior and can dominate it completely.
• "Naive Bayes needs its independence assumption to be true." The assumption is usually false and the classifier still performs well, because ranking classes correctly is easier than estimating calibrated probabilities. Its probability outputs, however, are typically badly overconfident and should not be read as real confidences.
• Reading a network edge as proven causation. An edge encodes a conditional independence assumption. Causal reading is a modelling choice you are responsible for defending, and the same joint distribution can often be represented by networks with edges pointing the other way.
• Missing explaining away. Independent causes become dependent once a shared effect is observed. Learning the sprinkler was on drops belief in rain from 0.378 to 0.216, and no amount of thinking about the marginal independence of Rain and Sprinkler predicts that.
• Forgetting to sum out unobserved variables. In the query for P(rain | wet), Sprinkler is neither observed nor asked about, so it must be marginalised over both values. Silently fixing it to one value answers a different question.
• Skipping the normalisation. The numbers 0.1752 and 0.2880 are joint probabilities, not conditional ones. They must be divided by their total before they mean anything as a posterior.
• Storing the observation history in a filter. The whole point of the forward algorithm is that the current belief summarises the past. Keeping the full history is unnecessary and does not scale.

Recap

• Bayes' rule: P(H given E) = P(E given H) * P(H) / P(E), with prior, likelihood, posterior, and evidence as its four named parts.
• P(E) sums true positives and false positives via total probability, and normalising unnormalised values avoids computing it separately.
• For rare hypotheses a positive test can still leave the posterior low: 1 percent prevalence, 90 percent sensitivity and 9 percent false positives give a posterior near 9 percent.
• Naive Bayes combines many clues under an independence assumption and works well for classification despite poorly calibrated probabilities.
• A Bayesian network stores a CPT per node; the sprinkler network gives P(rain | wet) = 0.378 against a prior of 0.20.
• Observing a common effect makes independent causes dependent - explaining away drops P(rain) to 0.216 once the sprinkler is known to be on.
• Networks are compact: at most k parents per node means n * 2k numbers rather than 2n - 1, so 240 instead of a billion at n = 30, k = 3.
• The HMM forward pass alternates predict and update; two umbrella sightings move belief in rain from 0.50 to 0.818 to 0.883, carrying only the current belief state.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Pearl, J. (1986). Fusion, propagation, and structuring in belief networks. Artificial Intelligence, 29(3), 241-288. doi.org/10.1016/0004-3702(86)90072-X
3. Pearl, J., & Russell, S. (2000). Bayesian networks (Technical Report R-277). UCLA Cognitive Systems Laboratory. ftp.cs.ucla.edu
4. Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257-286. web.ece.ucsb.edu
5. Koller, D., & Friedman, N. (2009). Probabilistic graphical models: Principles and techniques. MIT Press. find source ↗
6. Joyce, J. (2003). Bayes' theorem. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu
7. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io

The big picture

Machine learning (ML) is how a program gets better at a task by finding patterns in examples instead of following rules a human wrote out by hand. Rather than telling a computer exactly how to spot a cat, you show it thousands of labeled pictures and let it work out the rule for itself.

Why it matters: most modern AI, from spam filters to language models, is machine learning underneath. Once you can frame a problem as "learn a rule from data that also works on data you have never seen," a huge range of tasks opens up.

Learning a function, then generalizing

Think of a learner as searching a big catalog of candidate models (possible rules) for one that both fits the examples you have and, crucially, generalizes: it keeps working on new, unseen data. Generalization is the whole game. A rule that only repeats the answers it was shown is like a student who memorized last year's exam and is lost when the questions change.

Key idea: the goal of machine learning is not to fit the training data but to generalize to data the model has never seen.

Three paradigms

Machine learning problems fall into three broad families, defined by what feedback the learner gets.

• Supervised learning: the data comes as input-output pairs (x, y), like a stack of flashcards with the answer on the back, and the goal is to learn a function from x to y. If y is a category, the task is classification (spam or not-spam, digit 0 to 9). If y is a number, it is regression (predict a house price).
• Unsupervised learning: the data has inputs x but no answer labels, so the learner hunts for structure on its own. Clustering groups similar customers together; dimensionality reduction compresses many features into a few without losing much.
• Reinforcement learning: an agent acts in an environment and gets rewards or penalties, like training a dog with treats, and learns a policy (a strategy) that maximizes long-run reward. This is how systems learn to play games and steer robots.

Key idea: supervised learning uses labeled answers, unsupervised learning finds structure in unlabeled data, and reinforcement learning learns from rewards.

Underfitting, overfitting, and the bias-variance trade-off

The central difficulty is getting generalization right, and there are two ways to fail. A model that is too simple underfits: it misses real patterns and does poorly even on the training data. We say it has high bias. A model that is too complex overfits: it memorizes the noise and quirks of the training set and then stumbles on new data. We say it has high variance.

A useful analogy: fitting a model is like tailoring a suit. Too loose (underfit) and it fits no one well; tailored to every wrinkle of one fitting session (overfit) and it fits only that exact pose. The bias-variance trade-off is the tension between these, and good learning lands in the middle with low total error.

Underfit  (high bias):     poor on training AND test data
Good fit:                   good on training AND test data
Overfit   (high variance):  great on training, poor on test data

Key idea: underfitting is too-simple (high bias), overfitting is too-complex (high variance), and the aim is the balance point with the lowest error on new data.

Splitting the data honestly

To measure generalization you must never grade the model on data it studied. So the data is split into three parts:

• Training set: used to fit the model (the homework the model studies).
• Validation set: used to tune choices such as how complex the model should be. These tuning knobs are called hyperparameters (settings you pick rather than learn). This is like a practice quiz you check your studying against.
• Test set: touched only once, at the very end, to give an honest estimate of real-world performance (the final exam you see only on exam day).

Two more tools guard against overfitting. Regularization adds a penalty for complexity, nudging the model toward simpler rules. Cross-validation rotates which slice of data is held out for checking, so the estimate does not hinge on one lucky split.

Key idea: train, validate, and test on separate data so the final score reflects true generalization, not memorization.

A tiny worked example

Suppose you fit models to 10 points that roughly follow a straight line. A straight line (2 parameters) might leave small errors everywhere: underfit if the true pattern curves, but often fine. A degree-9 polynomial (10 parameters) can pass through all 10 points exactly, driving training error to zero, yet it wiggles wildly between the points and predicts nonsense on new inputs. Zero training error but terrible test error is the classic fingerprint of overfitting, and it is why we always hold out a test set.

Key idea: zero training error is a warning sign, not a trophy, when test error is high.

Why accuracy is the wrong metric more often than not

Reporting a single accuracy number hides exactly the information that matters. Take a fraud detector evaluated on 10,000 transactions of which 100 are fraudulent - a 1 percent base rate, which is realistic.

A model that predicts "not fraud" for every transaction scores 9900 / 10000 = 99 percent accuracy and catches nothing. Any serious evaluation has to break the errors apart. Suppose a real model produces this confusion matrix:

	Predicted fraud	Predicted legitimate
Actually fraud (100)	80 (true positives)	20 (false negatives)
Actually legitimate (9900)	120 (false positives)	9780 (true negatives)

Now compute the metrics that carry real information:

Accuracy  = (80 + 9780) / 10000        = 0.986   (98.6 percent)
Precision = 80 / (80 + 120)  = 80/200  = 0.40
            "of the transactions we flagged, 40 percent really were fraud"
Recall    = 80 / (80 + 20)   = 80/100  = 0.80
            "of the actual frauds, we caught 80 percent"
F1        = 2 * (0.40 * 0.80) / (0.40 + 0.80) = 0.64 / 1.20 = 0.533

The accuracy of 98.6 percent is lower than the useless always-legitimate model's 99 percent, and yet this model is enormously more valuable. Precision and recall expose the real behaviour: it catches four fraud cases in five, at the cost of three false alarms for every two genuine catches.

Precision and recall trade against each other, and the trade is controlled by a threshold you choose. Lower the flagging threshold and recall rises while precision falls; raise it and the reverse happens. Which direction to move is a question about consequences, not about statistics: missed fraud costs money, false alarms cost blocked customers, and only someone who knows the domain can set the exchange rate. This is the performance-measure problem from Lesson 1 in its most concrete form.

How the test set gets contaminated

"Do not tune on the test set" sounds easy and is violated constantly, usually without anyone noticing. Three routine ways it happens:

• Repeated peeking. Try 50 model variants, report the best test score. That score is the maximum of 50 noisy estimates and is biased upward - you have effectively used the test set for selection, which is what the validation set exists to absorb.
• Preprocessing before splitting. Compute a mean and standard deviation for normalisation over the whole dataset, then split. Test-set statistics have leaked into training. Fit every transformation on the training split alone and apply it to the others.
• Leakage through time or grouping. Splitting medical images randomly can put two scans of the same patient on both sides of the split; splitting time series randomly lets the model see the future. Split by patient, and split time series chronologically.

A fourth form now affects the whole field: benchmark contamination in web-scale training data. When a model is trained on a large scrape of the internet, published benchmark questions and answers may well be inside the training set, which turns a supposed test of generalisation into a test of memorisation. This is a live methodological problem, not a hypothetical one, and it is a major reason to treat headline benchmark numbers with caution.

No free lunch: why there is no best algorithm

A natural question is which learning algorithm is best. The answer, made precise by the no free lunch theorems, is that averaged over all possible target functions every algorithm performs identically - including one that guesses at random. Superior performance on real problems comes entirely from assumptions that happen to match the structure of real problems.

Those assumptions are the model's inductive bias: linear regression assumes the relationship is roughly additive, decision trees assume it is a set of nested thresholds, convolutional networks assume nearby pixels matter together and that a pattern means the same thing wherever it appears. None is neutral, and none is universally right. Selecting a model is choosing which assumption to bet on, which is why domain knowledge stays valuable no matter how good the algorithms get.

Where people get stuck

• "High training accuracy means the model is good." Only if test accuracy is also high. A large gap between the two is the definition of overfitting.
• "More complex models are always better." Extra capacity raises variance. A degree-9 polynomial through 10 points has zero training error and predicts nonsense between them.
• Reporting accuracy on imbalanced data. At a 1 percent base rate, predicting the majority class scores 99 percent and is worthless. Report precision and recall, or a confusion matrix.
• Treating precision and recall as independently improvable. They trade off through a threshold. Quoting one without the other, or without saying what threshold produced it, is not a result.
• "You can tune on the test set." Every look at the test set spends some of its value. Use validation for all decisions and touch the test set once.
• Leaking through preprocessing or grouping. Normalise using training statistics only, split medical data by patient, and split time series by time.
• "Unsupervised learning has no goal." It has a clear objective - find structure such as clusters or a low-dimensional representation - just no labelled answers to check against, which makes evaluation harder rather than absent.
• Looking for the universally best algorithm. No free lunch says there is none. Performance comes from an inductive bias that matches your problem, so understanding the problem is not optional.

Recap

• Machine learning finds rules from data and aims to generalize to unseen data.
• The three paradigms are supervised (labels), unsupervised (structure), and reinforcement (rewards).
• Underfitting is high bias; overfitting is high variance; good learning balances them.
• Data is split into training, validation, and test sets to measure generalization honestly, and leakage through preprocessing, grouping, or repeated peeking silently destroys that guarantee.
• Accuracy is misleading on imbalanced data: the worked fraud example scores 98.6 percent accuracy with precision 0.40 and recall 0.80, while a useless model scores 99 percent.
• Precision and recall trade off through a decision threshold, and choosing where to sit is a question about consequences, not statistics.
• Regularization and cross-validation further protect against overfitting.
• No free lunch: averaged over all problems no algorithm beats any other, so all real performance comes from an inductive bias suited to the task.

Sources

1. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
2. Mitchell, T. M. (1997). Machine learning. McGraw-Hill. find source ↗
3. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep learning. MIT Press. deeplearningbook.org
4. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81-106. doi.org/10.1023/A:1022643204877
5. Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134-1142. doi.org/10.1145/1968.1972
6. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press. incompleteideas.net
7. Stanford University. (n.d.). CS221: Artificial intelligence - Principles and techniques. stanford-cs221.github.io

The big picture

Artificial neural networks are the models behind most of modern AI's biggest wins, from image recognition to language models. A network is built from many tiny units called neurons, wired together in layers, that together learn to turn inputs into useful outputs.

Why it matters: the same basic recipe, adjust a pile of numbers until the output is right, scales from a toy example to systems with hundreds of billions of parameters. Understanding one neuron and one training step is enough to understand the whole idea.

One artificial neuron

A single neuron acts like a weighted vote. It takes several inputs, multiplies each by a weight that says how much that input matters, adds them up together with a bias (a constant offset), and then passes the total through a nonlinear activation function.

output = activation( w1*x1 + w2*x2 + ... + wn*xn + b )

Common activations include the sigmoid, which squashes any number into the range 0 to 1 (useful as a probability), and the most widely used today, ReLU (rectified linear unit), which passes the input through if it is positive and outputs 0 otherwise. ReLU is like a one-way valve: positive signals flow, negative ones are shut off.

Worked micro-example. Take weights w1 = 0.5, w2 = -1.0, bias b = 0.2, inputs x1 = 4, x2 = 1. The weighted sum is 0.5 times 4 plus (-1.0) times 1 plus 0.2, which is 2.0 - 1.0 + 0.2 = 1.2. Since 1.2 is positive, ReLU outputs 1.2. Had the sum been -0.3, ReLU would output 0.

Key idea: a neuron is a weighted vote plus a bias, passed through a nonlinearity that decides how it fires.

Why the nonlinearity is essential

The activation function must be nonlinear, and this is not a technicality. If every layer were purely linear, stacking them would collapse into a single linear function, no matter how many layers you used, because a chain of linear steps is still just one linear step. The nonlinearity is what lets depth actually buy you richer functions.

Key idea: without nonlinear activations, any deep network reduces to one linear layer and depth gains nothing.

Layers and forward propagation

Neurons are organized into an input layer (which receives the raw data), one or more hidden layers in the middle, and an output layer (which produces the answer). Pushing data through the network from input to output, one layer at a time, is called forward propagation, and it yields the network's prediction.

Key idea: forward propagation runs data through the layers in order to compute a prediction.

Training: loss, gradient descent, and backpropagation

Learning means tuning the weights so predictions get better. First we need a way to score how wrong we are: a loss function. Think of loss as a golf score you want to minimize, lower is better. Mean squared error is a common loss for regression; cross-entropy is common for classification.

To reduce the loss we use gradient descent. The gradient is the direction in which the loss increases fastest; imagine standing on a foggy hillside and feeling which way is steepest uphill. To go down, you step in the opposite direction. The size of each step is set by the learning rate: too big and you overshoot the valley, too small and training crawls.

repeat until converged:
    prediction = forward_propagate(inputs)          # forward pass
    loss       = loss_function(prediction, target)  # how wrong we are (golf score)
    gradients  = backpropagate(loss)                # dLoss/dWeight per weight
    for each weight w:
        w = w - learning_rate * gradient_of_w       # step downhill

Tiny gradient-descent step. Suppose one weight is w = 0.80, its gradient is dLoss/dw = +2.0 (loss rises as w rises), and the learning rate is 0.10. The update is w = 0.80 - 0.10 times 2.0 = 0.80 - 0.20 = 0.60. We moved w down because increasing it would have increased the loss.

The algorithm that makes this practical is backpropagation. Using the chain rule of calculus, it computes in a single backward sweep how much each individual weight contributed to the loss. Doing this by hand for millions of weights would be hopeless; backpropagation does it efficiently.

One complete backpropagation step, by hand

Descriptions of backpropagation rarely include the arithmetic, so here is a full pass on the smallest network that has a hidden layer: one input, one hidden ReLU unit, one linear output.

x  ---w1--->  [hidden, ReLU]  ---w2--->  y_pred

Starting values:   x = 2.0     target y = 1.5
                   w1 = 0.5    b1 = 0.0
                   w2 = 0.8    b2 = 0.1
                   learning rate = 0.1
Loss:  L = 0.5 * (y_pred - y)^2

Forward pass.

h_pre  = w1 * x + b1  = 0.5 * 2.0 + 0.0 = 1.0
h      = ReLU(1.0)                      = 1.0
y_pred = w2 * h + b2  = 0.8 * 1.0 + 0.1 = 0.9
L      = 0.5 * (0.9 - 1.5)^2 = 0.5 * 0.36 = 0.18

Backward pass. Work from the loss back toward the input, multiplying local derivatives - that chain of multiplications is the chain rule, and it is all backpropagation is.

dL/dy_pred = (y_pred - y)              = 0.9 - 1.5 = -0.6

Output layer:
dL/dw2 = dL/dy_pred * h    = -0.6 * 1.0 = -0.6
dL/db2 = dL/dy_pred        =              -0.6

Pass the signal back through w2:
dL/dh  = dL/dy_pred * w2   = -0.6 * 0.8 = -0.48

Through the ReLU. Its derivative is 1 where the input was
positive and 0 where it was negative. Here h_pre = 1.0 > 0,
so the derivative is 1:
dL/dh_pre = -0.48 * 1                   = -0.48

Hidden layer:
dL/dw1 = dL/dh_pre * x     = -0.48 * 2.0 = -0.96
dL/db1 = dL/dh_pre         =               -0.48

Update. Every weight steps against its gradient, scaled by the learning rate.

w2 = 0.8 - 0.1 * (-0.60) = 0.8 + 0.060 = 0.860
b2 = 0.1 - 0.1 * (-0.60) = 0.1 + 0.060 = 0.160
w1 = 0.5 - 0.1 * (-0.96) = 0.5 + 0.096 = 0.596
b1 = 0.0 - 0.1 * (-0.48) = 0.0 + 0.048 = 0.048

Check that it worked. Rerun the forward pass with the new weights:

h_pre  = 0.596 * 2.0 + 0.048 = 1.240
h      = ReLU(1.240)         = 1.240
y_pred = 0.860 * 1.240 + 0.160 = 1.0664 + 0.160 = 1.2264
L      = 0.5 * (1.2264 - 1.5)^2 = 0.5 * 0.07486 = 0.0374

The loss fell from 0.18 to 0.0374, a reduction of about 79 percent, and the prediction moved from 0.9 toward the target of 1.5. Every gradient was negative, meaning each weight was too small, so every weight increased. That is the entire algorithm. A network with a hundred billion parameters does exactly this, on the same principle, with the bookkeeping automated.

Notice one detail that matters in practice: dL/dw1 = -0.96 was twice dL/db1 = -0.48, purely because the input x = 2.0 multiplies into that gradient. Large-magnitude inputs produce large gradients, which is precisely why input features are normalised before training - otherwise a feature measured in millimetres and one measured in kilometres receive wildly different effective learning rates.

Key idea: training minimizes a loss by gradient descent, and backpropagation computes every weight's gradient efficiently via the chain rule.

The hidden layer solves XOR

Lesson 2 proved that no single-layer perceptron can compute XOR. One hidden layer removes the obstacle, and the solution is small enough to check by hand. Use two hidden ReLU units and a linear output:

h1 = ReLU(x1 + x2 - 0.5)      fires when at least one input is 1
h2 = ReLU(x1 + x2 - 1.5)      fires only when both inputs are 1
out = h1 - 3 * h2

x1	x2	h1	h2	out = h1 - 3*h2	XOR
0	0	0.0	0.0	0.0	0
0	1	0.5	0.0	0.5	1
1	0	0.5	0.0	0.5	1
1	1	1.5	0.5	0.0	0

Threshold the output at 0.25 and it is exactly XOR. What the hidden layer bought is a change of coordinates: h1 and h2 compute a rough OR and a rough AND, and in those new coordinates the four points are linearly separable, which they were not in the original ones. That is the general story of representation learning - depth does not add magic, it adds the ability to re-describe the input in a space where the remaining problem is easy.

And this is precisely the gap that stalled the field for seventeen years. The architecture above was known to work in 1969; nobody knew how to find those weights automatically until backpropagation.

Why deep networks are hard to train

Backpropagation multiplies derivatives along the chain, and multiplying many small numbers together produces a very small number. Sigmoid's derivative peaks at 0.25, so across ten sigmoid layers the gradient reaching the first layer is scaled by at most

0.2510 = 0.00000095, roughly one part in a million

This is the vanishing gradient problem: early layers receive almost no training signal and effectively stop learning. ReLU is the standard fix, since its derivative is exactly 1 for positive inputs and multiplying by 1 repeatedly changes nothing. That single substitution, along with better initialisation schemes and normalisation layers, is much of what made networks deeper than a few layers trainable at all - and it is why the 2012 breakthrough was as much about engineering details as about the idea of depth.

Two further practicalities. Stochastic gradient descent estimates the gradient from a small batch of examples rather than the whole dataset, which is thousands of times cheaper per step and whose noise appears to help escape poor minima. And the learning rate is the most consequential hyperparameter in the whole system: too large and the loss diverges, too small and training never finishes.

What makes it "deep," and the major architectures

Deep learning simply means neural networks with many hidden layers. Depth lets the network learn a hierarchy of features: early layers pick up simple patterns such as edges, and later layers combine those into complex ones such as shapes and then whole objects, all learned automatically rather than hand-designed. A few families dominate:

• Convolutional neural networks (CNNs) exploit spatial structure and excel at images by scanning for local patterns.
• Recurrent neural networks (RNNs) process sequences by carrying a hidden state forward through time.
• Transformers, introduced in 2017, use an attention mechanism, which works like a highlighter marking the relevant words in a sentence so the model can weigh relationships across the whole sequence in parallel. They now power large language models and much of state-of-the-art AI.

Deep learning's power comes at a cost: it needs large datasets, heavy computation, and care against overfitting. But its ability to learn representations straight from raw data is what unlocked the current era.

Key idea: depth builds features from simple to complex, and CNNs, RNNs, and Transformers are the workhorse architectures.

Where people get stuck

• "Neural networks work just like the human brain." They are loosely inspired by it and mathematically very different. Real neurons spike in time, learn by mechanisms unlike backpropagation, and are not arranged in feedforward layers. The name is a historical analogy, not a claim.
• "More layers always help." Extra depth needs more data and compute, can overfit, and creates optimisation problems such as vanishing gradients. Depth is a tool, not a scale of goodness.
• "Backpropagation is the same as gradient descent." Backpropagation computes the gradients; gradient descent is the update rule that consumes them. You can pair backpropagation with many different optimisers.
• "The activation function is optional." Remove the nonlinearity and the network collapses to a single linear map regardless of depth, and the XOR construction above stops working.
• Getting the sign of the update wrong. The step is w - learning_rate * gradient. In the worked example every gradient was negative and every weight therefore increased. Adding the gradient instead climbs the loss surface and diverges.
• Forgetting to normalise inputs. The gradient for w1 was twice that for b1 only because x = 2.0 multiplied into it. Features on wildly different scales get wildly different effective learning rates.
• Ignoring the learning rate. It is the single most consequential hyperparameter. Too large diverges, too small never converges, and no architecture choice compensates for getting it wrong.
• Believing depth alone caused the 2012 breakthrough. Deep architectures were known for decades. What changed was the combination of large labelled data, GPU compute, and the engineering fixes - ReLU, better initialisation, normalisation - that made deep networks trainable.

Recap

• A neuron computes a nonlinear activation of a weighted sum of inputs plus a bias.
• Nonlinear activations (ReLU, sigmoid) are essential or depth would collapse to one linear layer.
• Forward propagation runs inputs through layers to produce a prediction.
• A loss function scores errors; gradient descent steps weights downhill; backpropagation supplies the gradients by chaining local derivatives backwards.
• One worked step on a two-weight network cut the loss from 0.18 to 0.0374 and moved the prediction from 0.9 toward the target 1.5.
• A single hidden layer computes XOR - h1 = ReLU(x1+x2-0.5), h2 = ReLU(x1+x2-1.5), out = h1 - 3*h2 - by re-describing the inputs in coordinates where they are linearly separable.
• Vanishing gradients scale the signal reaching early layers by up to 0.2510, about one in a million, across ten sigmoid layers; ReLU's derivative of 1 is the standard fix.
• Deep networks learn feature hierarchies, with CNNs, RNNs, and Transformers as the main architectures.

Sources

1. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep learning. MIT Press. deeplearningbook.org
2. Russell, S. J., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson. find source ↗
3. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533-536. doi.org/10.1038/323533a0
4. LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. Nature, 521(7553), 436-444. doi.org/10.1038/nature14539
5. Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). ImageNet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems, 25. papers.nips.cc
6. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017). Attention is all you need. Advances in Neural Information Processing Systems, 30. arxiv.org
7. Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., ... Hassabis, D. (2021). Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873), 583-589. doi.org/10.1038/s41586-021-03819-2

The big picture

Natural language processing (NLP) is the part of AI that gets computers to understand, interpret, and generate human language. It sits behind translation, search, question answering, sentiment analysis, and conversational assistants.

Why it matters: language is how people store and share most knowledge, so a machine that handles language well can plug into an enormous range of tasks. It is also genuinely hard, which makes it a revealing test of how far AI has come.

Why language is hard

Language resists simple rules for a few stubborn reasons:

• Ambiguity: one sentence can have several meanings. "I saw the man with the telescope" could mean you used a telescope, or the man was holding one.
• Context dependence: the meaning of "it" or "there" depends on what came before, sometimes many sentences earlier.
• Idiom and creativity: "kick the bucket" has nothing to do with buckets, and people invent new phrasings constantly.

Key idea: language is ambiguous, context-dependent, and creative, so fixed rules alone cannot reliably capture meaning.

Core tasks and the classic pipeline

Traditional NLP broke a sentence down in stages, like an assembly line:

1. Tokenization: split text into words or subword pieces called tokens (the basic chunks the model reads).
2. Part-of-speech tagging: label each token as noun, verb, and so on.
3. Parsing: recover the grammatical structure that shows how words relate.
4. Named entity recognition: find the people, places, and organizations.

Early systems used hand-written grammar rules; later ones used statistics gathered over large text collections (corpora).

Key idea: classic NLP processed language in stages, moving from splitting tokens up to recovering structure and meaning.

Representing meaning as vectors

A pivotal idea is the word embedding: represent each word as a dense list of numbers (a vector) chosen so that words used in similar contexts get similar vectors. Picture placing every word as a point on a giant map where "dog" and "puppy" sit close together and "dog" and "airplane" sit far apart.

This rests on the distributional hypothesis: a word's meaning is characterized by the company it keeps. Embeddings famously capture analogies with arithmetic. The vector for "king" minus "man" plus "woman" lands near "queen," because subtracting a "male" direction and adding a "female" one leaves royalty intact. Turning words into vectors lets neural networks compute over meaning rather than bare symbols.

Key idea: word embeddings place words in a vector space so that geometric closeness reflects similarity of meaning.

Large language models

Modern NLP is dominated by large language models (LLMs) built on the Transformer architecture. They are trained by self-supervised learning: the model repeatedly tries to predict a hidden or next token and adjusts its weights whenever it guesses wrong. No human has to label the data, because the text itself supplies the answers.

Doing this across billions of sentences forces the model to soak up grammar, facts, and patterns of reasoning as a side effect of getting good at prediction. The key mechanism, attention, works like a highlighter: for each word it processes, the model marks which earlier words are most relevant, letting it capture long-range context that older methods missed.

training objective (simplified):
    for each position in a huge text corpus:
        predict the next token given all previous tokens
        increase the probability the model assigns to the correct token

Key idea: LLMs learn language by self-supervised token prediction over vast text, using attention to weigh relevant context.

Strengths and honest limits

LLMs are remarkably fluent and general, but they have real limitations you must design around:

• They can hallucinate: produce fluent statements that are simply false, because they optimize for plausible continuations, not truth.
• They lack grounded understanding and a reliable world model, and can fail at multi-step logical or arithmetic reasoning.
• They inherit biases present in their training data.
• Their knowledge is frozen at training time unless connected to external tools or retrieval.

Understanding both the power and these failure modes is essential to using language models responsibly, which leads directly into the final lesson on ethics and safety.

What a language model actually is, mechanically

Precision here prevents most confused arguments about these systems. Strip away the interface and a language model computes exactly one thing:

given a sequence of tokens, output a probability distribution over which token comes next

That is the whole operation. Text appears because the system samples a token from that distribution, appends it to the sequence, and repeats. Answering a question, writing code, and summarising a document are all the same computation applied to different starting sequences. A temperature setting controls how sharply the sampling favours high-probability tokens; at temperature zero it simply takes the most likely token every time.

Modern assistants add stages on top of that base model. Supervised fine-tuning trains on demonstrations of desired responses. Preference-based training, of which reinforcement learning from human feedback is the best known form, trains the model against a learned model of which of two responses people prefer. These stages substantially change behaviour, but they do not change the underlying computation: it is still next-token prediction, now with the distribution shaped by additional training signal.

Three things follow directly, and each rules out a common assumption.

• There is no fact database inside. Information is distributed across billions of weights that also encode grammar, style, and everything else. There is no table to look up, no row to correct, and no query that returns "what do you know about X".
• There is no separate representation of certainty. A well-attested fact and a plausible-sounding invention are produced by the same mechanism from the same weights. The model has no internal flag distinguishing recall from confabulation.
• The knowledge is fixed at training time. Anything after the training cutoff is absent unless supplied in the input, which is what retrieval augmentation and tool use are for.

Why hallucination happens

Hallucination - fluent, confident output unsupported by any source - is not a bug that a patch removes. It follows from the design, and at least four distinct mechanisms contribute.

1. The objective rewards plausibility, not truth. Next-token prediction asks "what text would likely follow?" Nothing in that objective references the world. A fabricated citation in the correct format is exactly what a well-trained predictor should consider likely, because real citations look like that.
2. Rare facts get a weak training signal. Syntactic patterns appear billions of times; a specific obscure fact may appear once. The model therefore becomes far better at producing the form of an answer than at retaining its rare content, which is precisely the recipe for a confident, well-structured, wrong answer.
3. Generation commits and cannot revise. Tokens are emitted one at a time, and each becomes part of the context conditioning the next. Once the model has begun "The 1957 study by Henderson showed...", it will continue coherently whether or not that study exists. There is no backtracking step and no point at which the text is checked.
4. Preference training can reward confidence. If human raters prefer answers that are complete and assured over ones that decline or hedge, training against those preferences pushes toward confident completion even when hedging would be correct. This mechanism is argued for in the research literature and taken seriously by practitioners, though how much of observed hallucination it explains relative to the first three is an open empirical question.

The practical consequence is that hallucination rates can be reduced - by retrieval that supplies real sources, by training that rewards calibrated uncertainty, by tool use that offloads facts and arithmetic - but no current technique eliminates the failure mode. Any system design that depends on the model never being confidently wrong is unsound.

Capability is not reliability

This distinction is the most useful thing in the lesson, and it is routinely collapsed.

• A capability claim is existential: there is some prompt, some setting, some attempt at which the system does X. Demonstrations establish capability.
• A reliability claim is statistical: the system does X correctly with probability p under the conditions where it will be used. Only systematic evaluation establishes reliability.

A demonstration proves the first and says almost nothing about the second, and the gap compounds badly. Suppose a model performs some step correctly 90 percent of the time - a respectable figure. Chain five such steps into a pipeline where every step must succeed:

0.95 = 0.59

The pipeline works about 59 percent of the time. At ten steps it is 0.910 = 0.35. This arithmetic is why multi-step autonomous systems are so much harder to build than single-turn demonstrations suggest, and why "the model can do each of these steps" is not evidence that it can do the sequence.

Reliability has a second dimension too: sensitivity to phrasing. The same question reworded, or with the options reordered, can produce different answers. A system whose output depends on incidental features of the input has a reliability problem that no capability demonstration will surface, and it is the single most common reason a prototype that impressed everyone fails in deployment.

What is genuinely contested

Two questions about these systems are open, and you should treat confident answers in either direction with suspicion.

• Do they reason, or pattern-match? One position points to strong performance on tasks unlikely to appear verbatim in training, and to systematic improvements from intermediate reasoning steps, as evidence of genuine generalisation. Another points to sharp failures on lightly perturbed versions of problems the model solves, and to the difficulty of ruling out contamination from web-scale training data, as evidence for sophisticated interpolation. Serious researchers hold both views, and the disagreement partly reflects the absence of an agreed test that would settle it.
• Does scaling continue to deliver? Empirical scaling relationships have held over several orders of magnitude, which supports extrapolation. Against that, data availability, cost, and evidence of diminishing returns on some capabilities are argued to signal a plateau. Nobody knows, and past confident predictions in both directions have a poor record.

Evaluation itself is under strain, which is part of why these questions stay open. Benchmark scores are compromised by contamination when test items appear in web-scale training data; many benchmarks are near saturation, so remaining headroom measures little; and there are real questions of construct validity about whether scoring highly on a multiple-choice exam measures the capability its name implies. A benchmark number is evidence about performance on that benchmark, and inferring anything broader requires an argument you should ask to see.

Key idea: LLMs are fluent but can hallucinate, carry bias, and reason imperfectly, so their outputs need checking.

Where people get stuck

• "A fluent answer must be correct." Fluency and truth are produced by the same mechanism from the same weights. A well-formatted citation is exactly what a good text predictor produces, whether or not the paper exists.
• "Embeddings store dictionary definitions." They store positions in a vector space learned from usage. Nothing in the model corresponds to a definition you could read or edit.
• "LLMs are trained by hand-labeling meanings." The base model is self-supervised on raw text. Later stages use human demonstrations and preferences, but nobody labels meanings.
• "An LLM knows today's news." Parameters freeze at the training cutoff. Anything later must arrive through the input, which is what retrieval and tools provide.
• "Hallucination is a bug that will be patched." It follows from an objective that rewards plausible continuations, from weak signal on rare facts, and from committed left-to-right generation. Rates can be reduced; the failure mode has not been eliminated.
• Treating a demonstration as a reliability estimate. Capability is existential, reliability is statistical. A step that works 90 percent of the time succeeds through a five-step chain only 59 percent of the time.
• Ignoring sensitivity to phrasing. If rewording a question changes the answer, the system is unreliable in a way no showcase example reveals. Test with the input variation your users will actually produce.
• Reading a benchmark score as a capability. Contamination, saturation, and construct validity all weaken the inference from a number to a claim about the world.
• Taking a side on the open questions. Whether these systems reason, and whether scaling keeps paying, are genuinely unsettled among informed researchers. Confident claims in either direction outrun the evidence.

Recap

• NLP gets computers to understand and generate language, which is hard because language is ambiguous and context-dependent.
• Classic pipelines tokenize, tag, parse, and extract entities.
• Word embeddings represent words as vectors so similar words are close, capturing meaning geometrically.
• An LLM computes one thing: a probability distribution over the next token. Generation is repeated sampling; fine-tuning and preference training reshape the distribution without changing the operation.
• There is no internal fact database, no separate certainty signal, and no knowledge after the training cutoff.
• Hallucination arises from an objective that rewards plausibility, weak signal on rare facts, irreversible left-to-right generation, and possibly from preference training that rewards confidence.
• Capability is not reliability: 0.95 = 0.59 is why multi-step pipelines fail even when each step looks strong.
• Whether these systems reason and whether scaling continues to deliver are contested; benchmark contamination and saturation are part of why.

Sources

1. Jurafsky, D., & Martin, J. H. (n.d.). Speech and language processing (3rd ed. draft). Stanford University. web.stanford.edu
2. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017). Attention is all you need. Advances in Neural Information Processing Systems, 30. arxiv.org
3. Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013). Efficient estimation of word representations in vector space. arXiv. arxiv.org
4. Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. Proceedings of NAACL-HLT. arxiv.org
5. Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., ... Amodei, D. (2020). Language models are few-shot learners. Advances in Neural Information Processing Systems, 33. arxiv.org
6. Ji, Z., Lee, N., Frieske, R., Yu, T., Su, D., Xu, Y., ... Fung, P. (2023). Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12), 1-38. arxiv.org
7. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., ... Lowe, R. (2022). Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35. arxiv.org

The big picture

As AI systems increasingly make or influence consequential decisions, in hiring, lending, medicine, policing, and more, their design becomes an ethical question, not just a technical one. This lesson surveys the main concerns and the responses now taking shape.

Why it matters: a system that is accurate on average can still be unfair, opaque, or unsafe for particular people. The aim here is sober judgment, neither hype nor panic, but engineering responsibility.

Fairness and bias

Machine learning models learn from historical data, so if that data reflects past discrimination, the model can perpetuate or even amplify it, lending a false air of objectivity to unfair outcomes. Think of it as a mirror that reflects society's past decisions, including the biased ones. A hiring model trained on a company's past hires may quietly disadvantage groups who were underrepresented in that history.

Mitigations include auditing the training data, measuring outcomes across groups with explicit fairness metrics, and testing for disparate impact (when a supposedly neutral rule hits one group much harder). A hard truth from this research: several reasonable mathematical definitions of fairness can be mutually incompatible, so fairness requires human value choices, not just formulas.

Two documented cases, with numbers

Abstract warnings about bias are easy to nod along to and hard to learn from. Two published audits make the mechanisms concrete.

Gender Shades (2018). Buolamwini and Gebru evaluated three commercial gender-classification systems on a benchmark of parliamentarians assembled to span skin tones. Reported error rates:

• Lighter-skinned men: no worse than 0.8 percent error.
• Darker-skinned women: up to 34.7 percent error.

A gap of more than forty-fold, in shipped commercial products. The cause was not a malicious design decision; it was that the standard evaluation datasets were overwhelmingly composed of lighter-skinned faces, so aggregate accuracy looked excellent while an entire subgroup was served terribly. Nobody had disaggregated the metric. That is the transferable lesson: an average conceals precisely the disparity you need to see, and the fix - reporting performance broken out by subgroup - is cheap and was simply not being done.

A health-care risk algorithm (2019). Obermeyer and colleagues studied a commercial tool used to identify patients who should receive extra care, affecting millions of people. The algorithm did not use race as an input at all. It predicted future health-care costs as a stand-in for health needs.

Because less money had historically been spent on Black patients at any given level of illness, equal predicted cost corresponded to greater actual illness. Black patients at a given risk score were substantially sicker than white patients at the same score. The authors calculated that correcting the proxy would raise the proportion of Black patients flagged for additional help from 17.7 percent to 46.5 percent.

This case is the more instructive of the two, because every obvious safeguard was in place. No protected attribute was an input. The model was accurate at the task it was given - predicting costs - and the training data was not mislabelled. The harm came entirely from the choice of target variable: cost is a measurement of care received, not of care needed, and the gap between those two things is exactly where historical inequity lives. "We did not use race" is not a defence, because any variable correlated with the outcome of past discrimination will reconstruct it.

Key idea: bias enters through unrepresentative evaluation data and through proxy target variables, and neither is visible in an aggregate accuracy score.

Fairness definitions, stated precisely

"Fair" has to be made mathematical before it can be tested, and there are several incompatible ways to do it. Write Y for the true outcome, S for the model's score or decision, and A for group membership.

• Demographic parity. P(S = 1 | A = a) is the same for every group. The selection rate is equal - equal proportions hired, approved, or flagged.
• Equalised odds. P(S = 1 | Y = y, A = a) is the same for every group, for each outcome y. True positive rates match and false positive rates match: the model makes each kind of mistake equally often across groups.
• Calibration within groups (predictive parity). P(Y = 1 | S = s, A = a) is the same for every group. A score of 7 means the same thing regardless of who receives it, so the number can be read at face value.

Each is defensible. Demographic parity captures "equal outcomes". Equalised odds captures "equal error burden". Calibration captures "the score is honest". A reasonable person might want all three.

The impossibility result

You cannot have all three. Kleinberg, Mullainathan and Raghavan, and independently Chouldechova, proved that except in two degenerate cases - a perfect classifier, or groups with identical base rates - calibration and equalised odds cannot hold simultaneously.

The algebra is short enough to see why. For each group, the false positive rate, the false negative rate, the base rate p, and the positive predictive value PPV are linked by

FPR = (p / (1 - p)) * ((1 - PPV) / PPV) * (1 - FNR)

Now suppose you enforce equal PPV across two groups - that is calibration. If the base rates p differ, the leading factor p/(1-p) differs, so the equation forces FPR or FNR to differ too. Equal error rates are then impossible. The constraint is arithmetic, not a limitation of current methods, and no future algorithm will escape it.

This is what the COMPAS dispute was actually about. In 2016 ProPublica analysed a recidivism risk tool and reported that among defendants who did not go on to reoffend, Black defendants were roughly twice as likely as white defendants to have been labelled high risk - about 45 percent against 23 percent. The vendor replied that the tool was calibrated: among defendants assigned the same score, reoffence rates were similar across races.

Both claims were correct. The tool satisfied calibration and violated equalised odds, and because the base rates in the two populations differed, it could not have satisfied both. The public argument was conducted as though one side must be lying, when in fact the two sides had chosen different fairness criteria and the mathematics forbade satisfying both at once.

The consequence for practice is uncomfortable but clarifying. You must choose which fairness criterion your application requires, state the choice openly, and defend it on grounds about consequences - who is harmed by a false positive, who by a false negative, and how much. That is a normative argument that engineers cannot settle alone and must not make silently by default. It should also be said that some scholars argue the whole framing is too narrow, and that arithmetic parity between groups is a poor substitute for asking whether the system should be built at all. That objection is not answered by any of the metrics above.

Key idea: models can inherit and amplify bias from historical data, and no single formula settles what fairness means - in fact the standard formulas are provably incompatible.

Privacy, transparency, and accountability

• Privacy: models trained on personal data can leak it or enable surveillance. Techniques such as anonymization and differential privacy (adding controlled noise so no single person's data stands out) help, though imperfectly.
• Transparency and explainability: many powerful models are black boxes whose internal reasoning is opaque, like a decision handed down with no reasons attached. Explainable AI seeks methods to justify individual decisions, which matters when someone is denied a loan or parole.
• Accountability: when an autonomous system causes harm, who is responsible, the developer, the deployer, or the user? Clear lines of responsibility and human oversight are essential.

Key idea: responsible AI must protect privacy, offer explanations for high-stakes decisions, and assign clear accountability.

Accountability: why it keeps evaporating

Accountability sounds like an easy principle and dissolves on contact with a real deployment. A single harmful decision may involve a team that assembled the dataset, a team that trained the model, a vendor that packaged it, an organisation that deployed it in a context nobody anticipated, and an operator who followed its recommendation. Each participant can truthfully say their contribution was reasonable, and the harm still occurred. This diffusion - sometimes called the problem of many hands - means responsibility has to be assigned in advance rather than discovered afterwards.

Three mechanisms have gained traction, and all three are documentation-first rather than technical.

• Documentation artefacts. Datasheets record how a dataset was collected, who is represented, and what uses it is unsuitable for. Model cards record intended use, out-of-scope use, and - critically - performance broken out by subgroup. The Gender Shades disparity is exactly what a model card is designed to surface before shipping.
• Risk-tiered governance. The NIST AI Risk Management Framework organises practice around four functions - govern, map, measure, and manage - and matches the intensity of oversight to the stakes. The EU AI Act takes a similar risk-tiered approach in law. Neither prescribes algorithms; both prescribe process and evidence.
• Meaningful human oversight. A human in the loop is only a safeguard if that person has the information, authority, and time to disagree. An operator who must justify every deviation from the system's recommendation, under time pressure, is providing the appearance of oversight rather than the substance - a failure mode well documented under the name automation bias.

A related trap: the right to an explanation is easy to satisfy badly. A post-hoc feature attribution can be plausible, stable-looking, and still not describe why the model produced its output. If an explanation would not let an affected person contest a decision or change their behaviour, it is decoration.

Dual use: capability without a safety catch

A final category has nothing to do with bugs or bias. Many AI capabilities are inherently dual-use: the same system serves a beneficial and a harmful purpose, and the two cannot be separated at the level of the model.

• Molecular design models that search for therapeutic compounds explore the same chemical space whether the objective rewards low toxicity or high.
• Speech and image synthesis restores voices to people who have lost them and enables impersonation fraud, using identical machinery.
• Code models that find vulnerabilities help defenders patch them and help attackers exploit them, with no principled distinction between the two searches.
• Automated content generation supports translation and accessibility at scale, and supports influence operations at the same scale.

What makes this structurally different from bias is that there is no version of the model without the problem. You cannot remove the harmful application while keeping the beneficial one, because they are the same computation pointed at a different objective. Mitigation therefore has to move outside the model - to who can access it, what monitoring accompanies use, what norms and law apply, and in some cases whether a capability should be released at all. Those are governance questions, and they cannot be delegated to a technical fix.

Note also that dual-use concerns are frequently overstated in both directions. Claims that a model has unlocked some dangerous capability need the same scrutiny as any other capability claim from Lesson 14: what was the evaluation, was the capability reliable or a single demonstration, and what marginal uplift does it provide over resources already available? Genuine risk assessment requires that arithmetic, not vividness.

The alignment problem

A distinct, forward-looking concern is alignment: ensuring an AI system actually pursues what its designers intend. The core difficulty is value specification, because we cannot fully write down everything we care about. A system optimizing a simplified proxy can then pursue it in unintended, harmful ways.

This failure is called specification gaming or reward hacking. The classic analogy: a boat-racing agent told to maximize its game score learns to spin in circles collecting bonus points forever instead of finishing the race. It did exactly what the score rewarded, just not what the designers meant. As systems grow more capable and autonomous, keeping them controllable and aligned with human values becomes increasingly important.

Key idea: alignment is hard because we cannot fully specify our values, so systems may game a proxy objective in unintended ways.

Toward responsible AI

Practical responses are converging across research and policy:

1. Keep a human in the loop for high-stakes decisions rather than fully automating them.
2. Test rigorously for bias, robustness, and failure modes before deployment, and keep monitoring after.
3. Build in transparency, documentation, and clear accountability from the start.
4. Invest in technical AI safety research on alignment, interpretability, and robustness.
5. Support thoughtful governance and regulation, such as risk-based frameworks that match oversight to the stakes of an application.

The recurring lesson of this course is that intelligence is the ability to act well toward goals. For artificial agents, deciding whose goals, and ensuring the agent pursues them safely and fairly, is the defining challenge of the field's future.

Key idea: safer AI combines human oversight, rigorous testing, transparency, safety research, and sensible governance.

Where the field genuinely disagrees

Ethics and safety discussions are often presented as a settled consensus, and they are not. Several disagreements are real, run between serious people, and are worth holding open rather than resolving by assertion.

• Near-term harms versus long-term risk. One community argues that documented present-day harms - the two cases above, labour displacement, surveillance - deserve the attention and resources, and that speculation about future systems distracts from them. Another argues that risks from substantially more capable systems warrant preparation now, because safeguards are easier to build before deployment than after. The framing as a zero-sum contest is itself contested; many researchers work on both.
• Openness versus restriction. Releasing model weights enables independent auditing, reproducible safety research, and broad access, and it also removes the ability to withdraw or restrict a capability later. There is no consensus on where the line sits, and reasonable positions depend on the specific capability.
• How much current alignment techniques accomplish. Preference-based training measurably reduces some harmful outputs. Whether it produces a system that has internalised the intended values, or one that has learned to produce outputs human raters approve of - which are different things, and come apart under distribution shift or adversarial pressure - remains an open research question rather than a solved problem.

The honest position on all three is that the evidence is incomplete. What is not in dispute is the value of measurement: disaggregated evaluation, documented limitations, and monitoring after deployment are agreed on across otherwise opposed camps, because they are what turn any of these arguments into something testable.

Where people get stuck

• "An accurate model is automatically fair." High average accuracy can conceal severe subgroup harm. The commercial classifiers in Gender Shades had respectable aggregate numbers and a 34.7 percent error rate on darker-skinned women.
• "If we do not use race as an input, the model cannot be racially biased." The health-care algorithm used no protected attribute and reproduced a large disparity through its choice of target variable. Any correlate of a historically unequal outcome will reconstruct it.
• "There is one correct mathematical definition of fairness." Demographic parity, equalised odds, and calibration are each defensible and provably incompatible whenever base rates differ. You must choose and justify.
• Treating COMPAS as a case of one side lying. ProPublica's error-rate finding and the vendor's calibration finding were both correct. They measured different criteria that cannot both hold.
• "Debiasing the data solves it." Sometimes the data are fine and the label is the problem, as with cost standing in for need. Ask what the target variable actually measures before adjusting anything else.
• "Alignment just means preventing bugs." A bug-free system that optimises a proxy will pursue the proxy exactly as instructed. Specification gaming is correct behaviour with respect to a wrong objective.
• Treating a human in the loop as automatic accountability. Oversight is real only when the person has the information, the authority, and the time to overrule the system, and is not penalised for doing so.
• "Regulation and technical safety are opposed." Dual-use capabilities cannot be fixed inside the model, so governance and technical work address different parts of the problem and neither substitutes for the other.
• Accepting an explanation that explains nothing. If an explanation would not let an affected person contest a decision or act differently, it is not serving the purpose that motivated requiring it.

Recap

• AI that drives consequential decisions raises ethical, not merely technical, questions.
• Bias enters through unrepresentative evaluation data (Gender Shades: 0.8 percent error for lighter-skinned men against 34.7 percent for darker-skinned women) and through proxy targets (a health algorithm using cost for need, where correcting it moved Black patients flagged for extra care from 17.7 to 46.5 percent).
• Demographic parity, equalised odds, and calibration are all defensible and provably cannot hold together when base rates differ - which is precisely what the COMPAS dispute was.
• Choosing a fairness criterion is a normative decision about who bears which error, and it must be made explicitly rather than by default.
• Privacy, explainability, and accountability are core pillars of responsible deployment; documentation, risk-tiered governance, and meaningful oversight are the mechanisms that make accountability stick.
• Alignment is the difficulty of making a system pursue intended goals, with specification gaming a key failure.
• Dual-use capabilities cannot be separated from their harmful applications inside the model, so mitigation moves to access, monitoring, and governance.
• Near-term versus long-term priority, openness versus restriction, and the reach of current alignment techniques are genuinely open disputes; disaggregated measurement is the common ground.

Sources

1. Buolamwini, J., & Gebru, T. (2018). Gender shades: Intersectional accuracy disparities in commercial gender classification. Proceedings of Machine Learning Research, 81, 77-91. proceedings.mlr.press
2. Obermeyer, Z., Powers, B., Vogeli, C., & Mullainathan, S. (2019). Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464), 447-453. doi.org/10.1126/science.aax2342
3. Kleinberg, J., Mullainathan, S., & Raghavan, M. (2016). Inherent trade-offs in the fair determination of risk scores. arXiv. arxiv.org
4. Chouldechova, A. (2017). Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2), 153-163. arxiv.org
5. Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., & Mane, D. (2016). Concrete problems in AI safety. arXiv. arxiv.org
6. National Institute of Standards and Technology. (2023). Artificial intelligence risk management framework (AI RMF 1.0) (NIST AI 100-1). U.S. Department of Commerce. nist.gov
7. Muller, V. C. (2026). Ethics of artificial intelligence and robotics. In E. N. Zalta (Ed.), The Stanford encyclopedia of philosophy. Stanford University. plato.stanford.edu