---
title: Learning from Examples
module: Learning
moduleNumber: 5
lessonNumber: 1
order: 501
summary: >
  An agent that improves with experience does not need its designer to anticipate
  every situation. Inductive learning takes that ambition and narrows it to one
  tractable problem: from labelled input-output pairs, recover a function that
  predicts the output for inputs never seen. This first part builds the foundation
  around a single organizing question — generalization — through decision trees and
  information gain, and the training/validation/test discipline for evaluating and
  choosing hypotheses. A second part takes up the theory of learning and the main
  model families.
topics: [Learning]
sources:
  - book: AIMA
    ref: "Ch. 18 — Learning from Examples; §18.1 Forms of Learning; §18.2 Supervised Learning"
  - book: AIMA
    ref: "§18.3 Learning Decision Trees; §18.4 Evaluating and Choosing the Best Hypothesis"
---


Every agent we have built so far came with its competence fully assembled. The
[search agent](/artificial-intelligence/search/informed-search) was handed a
successor function and a heuristic; the
[logical agent](/artificial-intelligence/logic-and-planning/propositional-logic)
was handed a knowledge base; the
[decision-theoretic agent](/artificial-intelligence/uncertainty/making-decisions)
was handed a transition model and a utility. In each case a human sat down in
advance and wrote the machinery down. An agent **learns** when it improves its
performance on future tasks after making observations about the world, and there
are three reasons a designer would want that.[^aima-forms] The designer cannot
anticipate every situation the agent will face; the world changes, so a fixed
program goes stale; and for some tasks — recognizing a face, driving a car — no
human knows how to write the rules in the first place, so the only route is to
let the agent find them from data.

This chapter narrows learning to one class of problem, restrictive-looking but
very general: **from a collection of input-output pairs, learn
a function that predicts the output for new inputs**. That is _inductive_ learning
— inferring a general rule from specific examples — and its central difficulty is
not fitting the examples you have but predicting the ones you do not. Everything
below is machinery for that one problem, and the recurring word is
**generalization**.

## Supervised learning as function approximation

Learning divides by the kind of feedback the data carries.[^aima-feedback] In
**unsupervised learning** the agent sees inputs with no labels and must find
structure on its own (the canonical task is _clustering_). In **reinforcement
learning** the agent acts and receives a scalar reward, and must decide which of
its past actions earned it — the subject of
[reinforcement learning](/artificial-intelligence/learning/reinforcement-learning).
The setting of this lesson is **supervised learning**, where the data supplies the
correct output for each input.

> **Definition (Supervised learning).** Given a **training set** of $N$
> input-output pairs $(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)$, where each
> $y_j$ was generated by an unknown function $y = f(x)$, discover a function $h$
> that approximates the true $f$. The function $h$ is a **hypothesis**; learning
> is a search through the space of possible hypotheses for one that predicts well
> on inputs beyond the training set.

The output type names the problem. When $y$ ranges over a finite set of values
(_sunny_, _cloudy_, _rainy_) the problem is **classification** — Boolean or binary
if there are only two values. When $y$ is a number (tomorrow's temperature) the
problem is **regression**. We measure a hypothesis not on the data it was trained
on but on a separate **test set** of examples it has never seen; a hypothesis
**generalizes** well if it predicts $y$ accurately for those novel inputs.

$$
% caption: Supervised learning as function approximation: a training set sampled
% from an unknown $f$ is fed to a learner, which returns a hypothesis $h$; the
% test set, drawn from the same distribution, measures how well $h$ generalizes.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=11mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (train) at (0,0)   {training set\\(x, y) pairs};
  \node[box, draw=acc, text=acc, thick] (learn) at (3.9,0) {learner};
  \node[box] (hyp)   at (7.8,0)  {hypothesis h};
  \node[box] (test)  at (7.8,-2.1) {test set\\(new x)};
  \node[box] (err)   at (3.9,-2.1) {test error};
  \draw[->, acc, thick] (train) -- (learn);
  \draw[->, acc, thick] (learn) -- (hyp);
  \draw[->, thick] (hyp) -- (test) node[midway, right, font=\scriptsize] {predict};
  \draw[->, thick] (test) -- (err) node[midway, above, font=\scriptsize, xshift=-5mm] {compare to true y};
\end{tikzpicture}
$$

### The hypothesis space and the generalization problem

We never search all functions; we fix a **hypothesis space** $\mathcal{H}$ and
search within it. For fitting a curve to points in the plane, $\mathcal{H}$ might
be the polynomials up to some degree. A hypothesis is **consistent** if it agrees
with all the training data. The trouble is that consistency is cheap and
misleading: given $N$ points, a polynomial of degree $N-1$ passes through every
one of them exactly, yet wiggles wildly between them and predicts nonsense off the
data. A straight line may miss every point slightly and still predict far better.

$$
% caption: The bias-variance tension. Left, a straight line underfits — too rigid
% to follow the trend. Center, a moderate curve fits the signal and generalizes.
% Right, a high-degree polynomial overfits — it threads every point but swings
% wildly between them.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- panel 1: underfit ---
  \begin{scope}
    \draw[->, black] (-0.2,0) -- (3.3,0) node[right, font=\scriptsize, black] {x};
    \draw[->, black] (0,-0.2) -- (0,2.6) node[above, font=\scriptsize, black] {y};
    \foreach \p in {(0.4,0.5),(0.8,1.3),(1.2,0.9),(1.6,1.8),(2.0,1.4),(2.4,2.2),(2.8,1.9)}
      \fill[black] \p circle (1.6pt);
    \draw[acc, very thick] (0.2,0.7) -- (3.0,2.0);
    \node[font=\scriptsize, anchor=north] at (1.5,-0.35) {too simple};
  \end{scope}
  % --- panel 2: good fit ---
  \begin{scope}[xshift=4.6cm]
    \draw[->, black] (-0.2,0) -- (3.3,0) node[right, font=\scriptsize, black] {x};
    \draw[->, black] (0,-0.2) -- (0,2.6) node[above, font=\scriptsize, black] {y};
    \foreach \p in {(0.4,0.5),(0.8,1.3),(1.2,0.9),(1.6,1.8),(2.0,1.4),(2.4,2.2),(2.8,1.9)}
      \fill[black] \p circle (1.6pt);
    \draw[acc, very thick] (0.2,0.6) .. controls (1.0,1.6) and (1.8,1.2) .. (3.0,2.1);
    \node[font=\scriptsize, anchor=north] at (1.5,-0.35) {just right};
  \end{scope}
  % --- panel 3: overfit ---
  \begin{scope}[xshift=9.2cm]
    \draw[->, black] (-0.2,0) -- (3.3,0) node[right, font=\scriptsize, black] {x};
    \draw[->, black] (0,-0.2) -- (0,2.6) node[above, font=\scriptsize, black] {y};
    \foreach \p in {(0.4,0.5),(0.8,1.3),(1.2,0.9),(1.6,1.8),(2.0,1.4),(2.4,2.2),(2.8,1.9)}
      \fill[black] \p circle (1.6pt);
    \draw[red, very thick] (0.4,0.5) .. controls (0.6,2.3) and (0.7,-0.2) ..
      (0.8,1.3) .. controls (1.0,2.4) and (1.1,0.2) ..
      (1.2,0.9) .. controls (1.4,2.2) and (1.5,0.4) ..
      (1.6,1.8) .. controls (1.8,0.4) and (1.9,2.5) ..
      (2.0,1.4) .. controls (2.2,2.6) and (2.3,0.6) ..
      (2.4,2.2) .. controls (2.6,0.5) and (2.7,2.6) .. (2.8,1.9);
    \node[font=\scriptsize, anchor=north] at (1.5,-0.35) {too complex};
  \end{scope}
\end{tikzpicture}
$$

A hypothesis space too simple to
capture the signal **underfits**; one flexible enough to chase the noise
**overfits**. Between them sits the fit that captures the trend and ignores the
noise, and choosing it is the problem of the rest of the lesson. This tradeoff —
complex hypotheses that fit the training data versus simpler ones that generalize
better — recurs below, along with a classical answer, Ockham's razor.

> **Definition (Overfitting).** A hypothesis overfits when it fits the training
> examples, including their noise and accidents, so closely that its test error is
> worse than a simpler hypothesis would achieve. Overfitting grows more likely as
> the hypothesis space and the number of input attributes grow, and less likely as
> the training set grows.[^aima-overfit]

## Decision trees

A **decision tree** is one of the simplest and most successful hypothesis spaces.
It represents a function that takes a vector of attribute values and returns a
single output by running a sequence of tests. Each internal node tests one
attribute $A_i$; each branch out of that node is labelled with a value of $A_i$;
each leaf specifies the output to return.[^aima-dt-rep] The representation is
natural for humans — many "How To" manuals are one long decision tree — and, for
Boolean classification, a tree is logically equivalent to the assertion that the
goal is true exactly when the input satisfies one of the paths leading to a
_true_ leaf.

The running example is deciding whether to wait for a table at a restaurant. The
goal predicate $WillWait$ is a Boolean function of ten attributes, among them
$Patrons$ (how full the restaurant is: _None_, _Some_, _Full_), $Hungry$,
$Type$ (French, Italian, Thai, or burger), $Price$, and $WaitEstimate$.

$$
% caption: A decision tree for the restaurant problem. Interior nodes test one
% attribute; branches are attribute values; leaves are the WillWait verdict. An
% example with Patrons = Full and WaitEstimate = 0-10 is classified Yes.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  test/.style={draw, minimum height=7mm, inner sep=3pt},
  leaf/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[test, draw=acc, text=acc] (pat) at (5,4.4) {Patrons?};
  \node[leaf] (no1)  at (2.2,3.2) {No};
  \node[leaf] (yes1) at (4.0,3.2) {Yes};
  \node[test] (wait) at (7.4,3.2) {WaitEstimate?};
  \node[leaf] (no2)  at (4.2,1.9) {No};
  \node[test] (alt)  at (6.1,1.9) {Alternate?};
  \node[test] (hun)  at (8.7,1.9) {Hungry?};
  \node[leaf] (yes2) at (10.6,1.9) {Yes};
  \node[leaf] (no3)  at (5.4,0.6) {No};
  \node[leaf] (yes3) at (6.8,0.6) {Yes};
  \node[leaf] (yes4) at (8.1,0.6) {Yes};
  \node[leaf] (no4)  at (9.4,0.6) {No};
  \draw[->] (pat) -- (no1)  node[midway, above left, font=\scriptsize, inner sep=1pt] {None};
  \draw[->] (pat) -- (yes1) node[midway, left, font=\scriptsize, inner sep=1pt] {Some};
  \draw[->] (pat) -- (wait) node[midway, above right, font=\scriptsize, inner sep=1pt] {Full};
  \draw[->] (wait) -- (no2)  node[midway, above left, font=\scriptsize, inner sep=1pt] {$>$60};
  \draw[->] (wait) -- (alt)  node[midway, left, font=\scriptsize, inner sep=1pt] {30-60};
  \draw[->] (wait) -- (hun)  node[midway, right, font=\scriptsize, inner sep=1pt] {10-30};
  \draw[->] (wait) -- (yes2) node[midway, above right, font=\scriptsize, inner sep=1pt] {0-10};
  \draw[->] (alt) -- (no3)  node[midway, left, font=\scriptsize, inner sep=1pt] {No};
  \draw[->] (alt) -- (yes3) node[midway, right, font=\scriptsize, inner sep=1pt] {Yes};
  \draw[->] (hun) -- (yes4) node[midway, left, font=\scriptsize, inner sep=1pt] {No};
  \draw[->] (hun) -- (no4)  node[midway, right, font=\scriptsize, inner sep=1pt] {Yes};
\end{tikzpicture}
$$

Decision trees can represent any Boolean function — but not always concisely. The
majority function, true when more than half its inputs are, needs an exponentially
large tree. And the space is enormous: there are $2^{2^n}$ Boolean functions of
$n$ attributes, so with the ten attributes of the restaurant problem we are
choosing among roughly $10^{308}$ functions.[^aima-dt-expr] Finding a good tree in
that space requires a heuristic.

### Learning a tree by information gain

We want a tree that is consistent with the examples and as small as possible —
small trees are shallow, which means few tests and better generalization. Finding
the _smallest_ consistent tree is intractable, but a greedy heuristic finds a
small one: **always test the most important attribute first**, where "most
important" means the one that makes the most difference to the classification. A
good split leaves subsets that are as close to all-positive or all-negative as
possible; a useless split leaves subsets with the same mix as the parent.

$$
% caption: Splitting the 12 restaurant examples. Testing Type (left) leaves four
% subsets each still evenly split between positive and negative — no progress.
% Testing Patrons (right) isolates a pure-negative subset (None) and a
% pure-positive subset (Some), a far better split.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  pool/.style={draw, minimum width=13mm, minimum height=6mm, align=center, font=\scriptsize},
  leaf/.style={draw, minimum width=8mm, minimum height=5mm, inner sep=2pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % --- left: Type ---
  \node[pool] (typ) at (0,3.0) {Type?};
  \node[pool] (t1) at (-2.4,1.4) {1 pos\\1 neg};
  \node[pool] (t2) at (-0.8,1.4) {1 pos\\1 neg};
  \node[pool] (t3) at (0.8,1.4)  {2 pos\\2 neg};
  \node[pool] (t4) at (2.4,1.4)  {2 pos\\2 neg};
  \draw[->] (typ) -- (t1) node[midway, above left, font=\tiny, inner sep=0.5pt] {French};
  \draw[->] (typ) -- (t2) node[pos=0.35, left, font=\tiny, inner sep=0.5pt] {Italian};
  \draw[->] (typ) -- (t3) node[pos=0.35, right, font=\tiny, inner sep=0.5pt] {Thai};
  \draw[->] (typ) -- (t4) node[midway, above right, font=\tiny, inner sep=0.5pt] {Burger};
  \node[font=\scriptsize, text=black] at (0,0.5) {gain = 0 bits};
  % --- right: Patrons ---
  \begin{scope}[xshift=7.2cm]
    \node[pool, draw=acc, text=acc] (pat) at (0,3.0) {Patrons?};
    \node[leaf] (p1) at (-2.0,1.4) {No};
    \node[leaf] (p2) at (0,1.4)    {Yes};
    \node[pool] (p3) at (2.1,1.4)  {2 pos\\4 neg};
    \draw[->] (pat) -- (p1) node[midway, above left, font=\tiny, inner sep=0.5pt] {None};
    \draw[->] (pat) -- (p2) node[pos=0.4, left, font=\tiny, inner sep=0.5pt] {Some};
    \draw[->] (pat) -- (p3) node[midway, above right, font=\tiny, inner sep=0.5pt] {Full};
    \node[font=\scriptsize, text=acc] at (0,0.5) {gain = 0.541 bits};
  \end{scope}
\end{tikzpicture}
$$

To make "most important" precise we borrow **entropy** from information
theory.[^aima-entropy] Entropy measures the uncertainty of a random variable;
acquiring information reduces it. A variable with one certain value has entropy
zero; a fair coin has entropy $1$ bit. For a variable $V$ with values $v_k$
occurring with probability $P(v_k)$,

$$
H(V) \;=\; \sum_k P(v_k) \log_2 \frac{1}{P(v_k)} \;=\; -\sum_k P(v_k)\log_2 P(v_k).
$$

For a Boolean variable that is true with probability $q$, write
$B(q) = -\bigl(q\log_2 q + (1-q)\log_2(1-q)\bigr)$. A training set with $p$
positive and $n$ negative examples has goal entropy $B\bigl(\tfrac{p}{p+n}\bigr)$.
An attribute $A$ with $d$ values splits the set into subsets $E_1, \ldots, E_d$,
where subset $E_k$ has $p_k$ positive and $n_k$ negative examples. The expected
entropy remaining after testing $A$ is a weighted average over the branches,

$$
\mathit{Remainder}(A) \;=\; \sum_{k=1}^{d} \frac{p_k + n_k}{p+n}\, B\!\left(\frac{p_k}{p_k+n_k}\right),
$$

and the **information gain** from testing $A$ is the expected reduction in entropy:

$$
\mathit{Gain}(A) \;=\; B\!\left(\frac{p}{p+n}\right) - \mathit{Remainder}(A).
$$

> **Definition (Information gain).** The expected reduction in goal entropy that
> results from testing an attribute. The greedy tree learner splits, at each node,
> on the attribute of maximum information gain — the attribute that most reduces
> the uncertainty about the classification.

The restaurant set has $p = n = 6$, so the goal entropy is $B(0.5) = 1$ bit.
Working out the two splits above confirms the intuition. $Patrons$ carves off a
pure-_No_ subset (_None_) and a pure-_Yes_ subset (_Some_), leaving only _Full_
mixed, and gains most of that bit:

$$
\mathit{Gain}(Patrons) = 1 - \left[\tfrac{2}{12}B(\tfrac{0}{2}) + \tfrac{4}{12}B(\tfrac{4}{4}) + \tfrac{6}{12}B(\tfrac{2}{6})\right] \approx 0.541 \text{ bits.}
$$

$Type$, by contrast, leaves four subsets each evenly split, and gains nothing:

$$
\mathit{Gain}(Type) = 1 - \left[\tfrac{2}{12}B(\tfrac{1}{2}) + \tfrac{2}{12}B(\tfrac{1}{2}) + \tfrac{4}{12}B(\tfrac{2}{4}) + \tfrac{4}{12}B(\tfrac{2}{4})\right] = 0 \text{ bits.}
$$

#### Carrying the $Patrons$ computation all the way through

Deriving the $0.541$ in full shows how the entropy formula is used. The twelve
restaurant examples split under $Patrons$ into three branches:

- **None** (2 examples): both are _No_, so $0$ positive, $2$ negative. Its Boolean
  entropy is $B(0/2) = B(0) = 0$ — a pure subset carries no uncertainty.
- **Some** (4 examples): all four are _Yes_, so $4$ positive, $0$ negative.
  $B(4/4) = B(1) = 0$ — pure again.
- **Full** (6 examples): $2$ positive, $4$ negative. Here
  $B(2/6) = B(1/3) = -\big(\tfrac13\log_2\tfrac13 + \tfrac23\log_2\tfrac23\big)$.

Evaluate that last term. $\log_2\tfrac13 = -\log_2 3 = -1.585$ and
$\log_2\tfrac23 = 1 - \log_2 3 = -0.585$, so

$$
B(\tfrac13) = -\big(\tfrac13(-1.585) + \tfrac23(-0.585)\big) = 0.528 + 0.390 = 0.918 \text{ bits.}
$$

Now weight each branch by its share of the twelve examples. _None_ and _Some_
contribute nothing because their entropies are zero; only _Full_ survives, with
weight $6/12 = \tfrac12$:

$$
\mathit{Remainder}(Patrons) = \tfrac{2}{12}(0) + \tfrac{4}{12}(0) + \tfrac{6}{12}(0.918) = 0.459 \text{ bits.}
$$

The goal entropy before the split was $B(6/12) = B(0.5) = 1$ bit, so

$$
\mathit{Gain}(Patrons) = 1 - 0.459 = 0.541 \text{ bits.}
$$

Compare this against a middling attribute to see the ranking the learner uses.
$Hungry$ splits the twelve into _Yes_ (5 pos, 2 neg) and _No_ (1 pos, 4 neg):

$$
\mathit{Remainder}(Hungry) = \tfrac{7}{12}B(\tfrac57) + \tfrac{5}{12}B(\tfrac15)
= \tfrac{7}{12}(0.863) + \tfrac{5}{12}(0.722) = 0.804 \text{ bits,}
$$

for a gain of $1 - 0.804 = 0.196$ bits — real, but less than half of $Patrons$'s.
The greedy learner therefore ranks the candidate root attributes
$Patrons\;(0.541) > Hungry\;(0.196) > \cdots > Type\;(0)$ and tests $Patrons$ first.

$$
% caption: Information gain of four candidate root attributes on the 12 restaurant
% examples. Patrons (0.541 bits) wins because it isolates two pure subsets; Type
% (0 bits) loses because every branch keeps the parent's even split. The greedy
% learner tests the highest bar first.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (0,3.4) node[above, black, font=\scriptsize] {gain (bits)};
  \draw[black] (0,0) -- (7.2,0);
  % gridline at 0.541
  \node[anchor=east, black, font=\scriptsize] at (-0.08,3.0) {0.541};
  \draw[black, dashed] (0,3.0) -- (7.2,3.0);
  % bars: scale 0.541 -> 3.0, so factor 5.545
  \fill[acc!20, draw=acc] (0.6,0) rectangle (1.8,3.0);
  \node[acc, anchor=south, font=\scriptsize] at (1.2,3.05) {Patrons};
  \node[anchor=north, font=\scriptsize] at (1.2,-0.05) {0.541};
  \fill[black, draw=black] (2.4,0) rectangle (3.6,1.09);
  \node[anchor=south, font=\scriptsize, text=black] at (3.0,1.1) {Hungry};
  \node[anchor=north, font=\scriptsize] at (3.0,-0.05) {0.196};
  \fill[black, draw=black] (4.2,0) rectangle (5.4,0.42);
  \node[anchor=south, font=\scriptsize, text=black] at (4.8,0.45) {Rain};
  \node[anchor=north, font=\scriptsize] at (4.8,-0.05) {0.076};
  \fill[red!14, draw=red] (6.0,0) rectangle (7.2,0.06);
  \node[red, anchor=south, font=\scriptsize] at (6.6,0.1) {Type};
  \node[anchor=north, font=\scriptsize] at (6.6,-0.05) {0};
\end{tikzpicture}
$$

So $Patrons$ has the maximum gain and is chosen as the root. After splitting, each
non-pure branch becomes a smaller decision-tree problem with one fewer attribute,
solved recursively. The full algorithm handles four cases: a pure subset returns
its class; a mixed subset splits on the best remaining attribute; an empty subset
returns the plurality vote of the parent's examples; and a subset with no
attributes left but mixed labels (noise, or an unobservable distinction) returns
its own plurality vote.[^aima-dt-induce]

```algorithm
caption: $\textsc{Decision-Tree-Learning}(examples, attributes, parent)$ — greedy induction
if $examples$ is empty then
  return $\textsc{Plurality-Value}(parent)$
else if all $examples$ have the same classification then
  return that classification
else if $attributes$ is empty then
  return $\textsc{Plurality-Value}(examples)$
else
  $A \gets \arg\max_{a \in attributes} \textsc{Importance}(a, examples)$
  $tree \gets$ a new decision tree with root test $A$
  for each value $v_k$ of $A$ do
    $exs \gets \{e \in examples : e.A = v_k\}$
    $subtree \gets \textsc{Decision-Tree-Learning}(exs, attributes - A, examples)$
    add a branch to $tree$ with label $(A = v_k)$ and subtree $subtree$
  return $tree$
```

Here $\textsc{Importance}$ is information gain and $\textsc{Plurality-Value}$
returns the most common output, breaking ties at random. Run on the 12-example
training set, the algorithm produces a tree that is consistent with the data and
_simpler_ than the tree a human wrote — it never tests $Price$ or $Type$ at all,
because it can classify every example without them. That is the algorithm working
as intended: it fits the examples, not the "true" function, and among consistent
trees it prefers the small one.

### Overfitting and pruning

Left unchecked, the greedy learner grows a large tree whenever it finds any
pattern in the input, even when there is no pattern to find. Give it dice rolls
labelled by the die's color, weight, and the time of the roll, and if two fair
rolls happen to come up six, it will build a path predicting six from those
irrelevant attributes. To address this, **decision tree pruning** grows the full
tree, then eliminates nodes that are not clearly relevant.[^aima-prune]

Pruning works from the bottom. Consider a test node all of whose descendants are
leaves. If the attribute it tests appears to be irrelevant — detecting only noise
— replace the whole node with a single leaf. How do we tell? An irrelevant
attribute splits a set of $p$ positive and $n$ negative examples into subsets
whose positive fractions are all close to the parent's $p/(p+n)$, so its
information gain is close to zero. A **significance test** makes "close to zero"
precise: assume the null hypothesis that the attribute is irrelevant, compute how
far the observed split deviates from the even split that null predicts, and prune
unless the deviation is statistically unlikely (the standard $\chi^2$ test at the
5% level). This is **$\chi^2$ pruning**, and pruned trees are both more accurate
in the presence of noise and smaller, hence easier for a person to read.

Growing then pruning beats **early stopping** — halting growth when no attribute
looks good enough. Early stopping is fooled by attributes that are useless alone
but informative in combination, like the two inputs of an XOR: neither has any
gain at the root, so early stopping quits, but splitting on either one exposes an
informative split at the next level. Grow-then-prune sees the whole tree first and
keeps such structure.

## Evaluating a hypothesis

To choose among hypotheses we need to measure how well each will predict the
_future_. The **stationarity assumption** makes "future" meaningful: examples are
drawn independently from a probability distribution that does not change over time
— the examples are **independent and identically distributed (i.i.d.)**. Without
some such link between past and future, no prediction is justified.[^aima-eval]

The **error rate** of a hypothesis is the proportion of examples it misclassifies,
$h(x) \neq y$. A low error rate on the training set proves nothing — a professor
knows an exam will not measure students who have already seen the questions. To
estimate how $h$ generalizes we test it on held-out examples. The simplest
protocol splits the data into a **training set**, which the learner sees, and a
**test set**, which measures the final hypothesis. But a single split wastes data:
reserve half for testing and you train on half as much; reserve only a tenth and a
statistical accident in that tenth can give a bad estimate.

**$k$-fold cross-validation** squeezes more from the same data by letting every
example serve as both training and test data. Split the data into $k$ equal folds;
run $k$ rounds, each holding out one fold as the test set and training on the other
$k-1$; average the $k$ scores. Popular values are $k = 5$ or $10$; the extreme
$k = N$ is **leave-one-out cross-validation**.

$$
% caption: Five-fold cross-validation. In each round a different fold (dark) is
% the held-out test set and the rest (light) is training data; the five test
% scores are averaged so every example is tested exactly once.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \foreach \r in {0,1,2,3,4} {
    \pgfmathsetmacro\yy{-\r*0.85}
    \foreach \c in {0,1,2,3,4} {
      \ifnum\c=\r
        \fill[red!25] (\c*1.15, \yy) rectangle ++(1.05,0.6);
        \draw[red, thick] (\c*1.15, \yy) rectangle ++(1.05,0.6);
      \else
        \fill[acc!12] (\c*1.15, \yy) rectangle ++(1.05,0.6);
        \draw[acc] (\c*1.15, \yy) rectangle ++(1.05,0.6);
      \fi
    }
    \node[anchor=east, font=\scriptsize] at (-0.25, \yy+0.3) {round \the\numexpr\r+1\relax};
  }
  \node[font=\scriptsize, text=red, anchor=west] at (6.1,-1.4) {test fold};
  \node[font=\scriptsize, text=acc, anchor=west] at (6.1,-1.9) {training folds};
\end{tikzpicture}
$$

One discipline matters above all: never let the test set influence the choice of
hypothesis. **Peeking** ruins the estimate — if you try many settings of a
learner's knobs, measure each on the test set, and report the best, then the test
set has leaked into learning and the reported accuracy is a fiction. To avoid this,
hold the test set out until every choice is made; to compare models along the way,
carve a third **validation set** out of the training data.

### The learning curve

Plotting a learner's test accuracy against training-set size gives a **learning
curve**. Accuracy rises as the training set grows — more examples make the right
pattern easier to distinguish from noise — which is why learning curves are also
called "happy graphs." The shape says something practical: a curve still climbing
at the largest available size means more data would help; a curve that has
flattened means the hypothesis space, not the data, is now the limit.

$$
% caption: A learning curve. Test accuracy rises with training-set size and then
% flattens as the hypothesis space, rather than the amount of data, becomes the
% binding constraint.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, black] (0,0) -- (6.4,0) node[right, font=\scriptsize, black] {training set size};
  \draw[->, black] (0,0) -- (0,3.4) node[above, font=\scriptsize, black] {test accuracy};
  \node[font=\scriptsize, anchor=east] at (-0.05,3.0) {1.0};
  \node[font=\scriptsize, anchor=east] at (-0.05,1.5) {0.5};
  \draw[acc, very thick] (0.2,1.2)
    .. controls (0.9,2.6) and (1.6,2.75) .. (2.6,2.85)
    .. controls (3.8,2.95) and (5.0,2.98) .. (6.0,3.0);
  \node[acc, anchor=south west, font=\scriptsize] at (4.0,2.55) {plateau};
\end{tikzpicture}
$$

### Model selection and Occam's razor

Two questions remain: which hypothesis space, and how complex a
hypothesis within it? Choosing the polynomial degree, or the number of nodes in a
tree, is **model selection**, and it splits the job of finding the best hypothesis
into two parts — _model selection_ fixes the hypothesis space, then _optimization_
finds the best hypothesis in it.[^aima-modelsel] A cross-validation wrapper solves
model selection directly: enumerate models from simplest to most complex, and for
each, use cross-validation to estimate its error. As complexity grows the training
error falls monotonically, but the validation error falls and then _rises_ — the
U-shaped signature of underfitting giving way to overfitting. Pick the model at the
bottom of the U.

$$
% caption: Model selection by validation error. Training error falls monotonically
% with complexity; validation error is U-shaped, and its minimum marks the model
% that best balances underfitting against overfitting.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.4,0) node[right, font=\scriptsize, black] {model complexity};
  \draw[->, black] (0,0) -- (0,3.6) node[above, font=\scriptsize, black] {error};
  % training error: monotonically decreasing
  \draw[acc, very thick] (0.3,3.1) .. controls (1.6,1.4) and (3.0,0.7) .. (6.0,0.35);
  \node[acc, anchor=west, font=\scriptsize] at (6.05,0.35) {training};
  % validation error: U-shaped
  \draw[red, very thick] (0.3,3.3) .. controls (1.8,1.5) and (2.6,1.1) .. (3.4,1.05)
    .. controls (4.4,1.0) and (5.2,2.0) .. (6.0,2.9);
  \node[red, anchor=west, font=\scriptsize] at (6.05,2.9) {validation};
  \draw[dashed, black] (3.4,0) -- (3.4,1.05);
  \fill[red] (3.4,1.05) circle (2pt);
  \node[font=\scriptsize, anchor=north] at (3.4,-0.1) {best};
\end{tikzpicture}
$$

Why prefer the simpler model at all? Because of **Ockham's razor**: among
hypotheses consistent with the data, prefer the simplest.[^aima-occam] A
degree-1 polynomial is simpler than a degree-7 one, and simplicity is a bet on
generalization — a simple hypothesis has fewer ways to have latched onto noise. An
equivalent, weight-based route to the same preference is **regularization**:
instead of enumerating model sizes, minimize a total cost that adds a complexity
penalty to the empirical loss,

$$
\mathit{Cost}(h) = \mathit{EmpLoss}(h) + \lambda\, \mathit{Complexity}(h),
$$

where $\lambda$ trades loss against complexity. The name is apt — it searches for a
hypothesis that is more _regular_, less wiggly. There is also a tradeoff between
the _expressiveness_ of a hypothesis space and the _complexity of finding_ a good
hypothesis within it: a richer language may let a simple hypothesis fit the data,
but searching it can be intractable, which is why most learning sticks to simple
representations.

This is the foundation: a hypothesis space, a search for a hypothesis that
generalizes, and a discipline for measuring whether it does. What we have not yet
done is _prove_ that generalization is possible, or survey the model families
beyond the decision tree. That is the work of the second part,
[The Theory of Learning and Model Families](/artificial-intelligence/learning/theory-and-model-families),
which opens with the question these measurements leave unanswered: how can we be
sure a hypothesis will predict well on inputs it has never seen?

[^aima-forms]: **Russell & Norvig**, _AIMA_ (3rd ed.), Ch. 18 opening and §18.1 — Forms of Learning: an agent learns if it improves on future tasks after observing the world; the three reasons a designer wants learning (unanticipated situations, changing environments, tasks no one can program by hand).
[^aima-feedback]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.1 — the three types of feedback: unsupervised (patterns with no labels, e.g. clustering), reinforcement (a reward signal), and supervised (correct outputs supplied).
[^aima-overfit]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.2 and §18.3.5 — Fig. 18.1's underfit/consistent/overfit polynomial fits; overfitting grows more likely as the hypothesis space and attribute count grow, less likely as training data grows.
[^aima-dt-rep]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.3.1–18.3.2 — the decision-tree representation (interior tests, branch values, leaf outputs), the $WillWait$ example and its attributes, and equivalence to a DNF assertion over root-to-leaf paths.
[^aima-dt-expr]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.3.2 — decision trees express any Boolean function but not always concisely (the majority function); there are $2^{2^n}$ Boolean functions of $n$ attributes.
[^aima-dt-induce]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.3.3 and Fig. 18.5 — the greedy divide-and-conquer $\textsc{Decision-Tree-Learning}$ algorithm and its four recursive cases; the induced tree is consistent with and simpler than the hand-built one.
[^aima-entropy]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.3.4 — entropy $H(V)$, the Boolean-entropy shorthand $B(q)$, $\mathit{Remainder}(A)$, and the information-gain heuristic $\mathit{Gain}(A)$; the worked $\mathit{Gain}(Patrons) \approx 0.541$ vs. $\mathit{Gain}(Type) = 0$.
[^aima-prune]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.3.5 — generalization and overfitting; decision-tree pruning via a $\chi^2$ significance test on the null hypothesis of an irrelevant attribute, and why grow-then-prune beats early stopping (the XOR case).
[^aima-eval]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.4 — the stationarity/i.i.d. assumption, error rate, holdout vs. $k$-fold and leave-one-out cross-validation, peeking, and the training/validation/test discipline; the learning curve of §18.3 (Fig. 18.7).
[^aima-modelsel]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.4.1 and §18.4.3 — model selection as a wrapper over a size parameter, the U-shaped validation curve (Fig. 18.9), and regularization as minimizing $\mathit{EmpLoss} + \lambda\,\mathit{Complexity}$.
[^aima-occam]: **Russell & Norvig**, _AIMA_ (3rd ed.), §18.2 and §18.3 — Ockham's razor (prefer the simplest consistent hypothesis) and the expressiveness-versus-search tradeoff in choosing a hypothesis space.