Learning from Examples

Every agent we have built so far came with its competence fully assembled. The search agent was handed a successor function and a heuristic; the logical agent was handed a knowledge base; the decision-theoretic agent 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.¹ 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.² 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. The setting of this lesson is supervised learning, where the data supplies the correct output for each input.

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.

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.

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.

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.⁴ 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$.

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.⁵ 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.

To make most important precise we borrow entropy from information theory.⁶ 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)$,

For a Boolean variable that is true with probability $q$, write $B(q)=-(q{\log }_{2}q+(1-q){\log }_2(1-q))$. A training set with $p$ positive and $n$ negative examples has goal entropy $B\left(\frac{p}{p+n}\right)$. An attribute $A$ with $d$ values splits the set into subsets $E_1,\dots ,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,

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

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:

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

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)=-(\frac{1}{3}{\log }_2\frac{1}{3}+\frac{2}{3}{\log }_2\frac{2}{3})$.

Evaluate that last term. ${\log }_2\frac{1}{3}=-{\log }_{2}3=-1.585$ and ${\log }_2\frac{2}{3}=1-{\log }_{2}3=-0.585$, so

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=\frac{1}{2}$:

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

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):

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.

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.⁷

Here $\text{Importance}$ is information gain and $\text{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.⁸

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.⁹

The error rate of a hypothesis is the proportion of examples it misclassifies, $h(x)\ne 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.

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.

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.¹⁰ 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.

Why prefer the simpler model at all? Because of Ockham's razor: among hypotheses consistent with the data, prefer the simplest.¹¹ 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,

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, 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?