Capacity, Overfitting and Underfitting

Generalization

A student who memorizes last year’s exam scores perfectly on it and may still fail this year’s. A model has the same problem. What counts is performance on new inputs, a property called generalization.

Training minimizes the training error, the easy half. The generalization error, also called the test error, is the expected error on a new input. We estimate it on a test set collected apart from the training set. For linear regression the training error is

Here counts training examples, stacks their inputs in rows, holds their targets and the weights. The test error is the same formula on the test set, . We see the first number when we fit, but we care about the second.

The demo runs 200 experiments. Each draws a fresh training set and test set from the same smooth curve plus noise. The left bars use parameters fixed in advance. The right bars use parameters fitted on each training set.

The fixed pair agrees. The fitted pair does not: tuning to the training sample makes the training error optimistic. Raise the degree or lower the number of examples and the gap widens. Two factors decide performance: a small training error, and a small gap.

The i.i.d. assumptions

Learning theory says something useful about the second number when the data are collected sensibly. The standard i.i.d. assumptions say the examples are independent of each other, and the training and test sets are identically distributed, drawn from one data generating distribution .

These are the two central challenges. Underfitting means the training error is too high. Overfitting means the gap is too large. Section 2 shows how to steer between them.

Capacity and polynomial models

Capacity is a model’s ability to fit a wide variety of functions. One way to change it is the hypothesis space, the set of functions the algorithm may choose from. A polynomial of degree one is the familiar line,

Here is the prediction, the input, the intercept and the slope. Adding gives a curve,

The curve is quadratic in , but still linear in the weights, so the normal equations train it. Powers up to degree 9 follow the same pattern,

Every weight multiplies one power of . The model is linear in its parameters and nonlinear in its input. Degree 9 has nine weights plus the intercept, so it has ten parameters in total.

Check the guess with Figure 5.2 of the book, rebuilt here. The true function is quadratic. Drag a training point, then press Degree 9.

The straight line cannot follow the curvature, so its training error stays high: underfitting. The degree-2 fit matches the true structure and generalizes. Degree 9 with ten points threads every point and swings between them: overfitting, with near-zero training error and a large test error. The noise variance is the floor.

Representational and effective capacity

Changing the number of features is one way to change capacity. The model family fixes which functions the algorithm may reach, and that is the representational capacity. Finding the best function in the family is often hard, and the algorithm in practice finds only one that reduces the training error significantly. Limits such as an imperfect optimizer make the effective capacity smaller than the representational capacity. Section 3 shows this with gradient descent.

Underfitting, overfitting and the U-curve

Training error falls as capacity grows, until it levels off at the smallest value the error measure allows. Generalization error usually traces a U-shaped curve against capacity. On the left, the model is too small and both errors are high. That is the underfitting regime. As capacity grows, the training error drops, but the gap to the test error widens. Past the optimal capacity the gap costs more than the training error gains, and the model is in the overfitting regime.

Press the buttons to check the guess. The curves average 30 random training sets, so the optimum is steady rather than a lucky draw. The dashed line is the noise variance, the floor under every curve.

At low degree both errors are high. The training error keeps falling as the degree rises, while the test error reaches its minimum at the optimum and then climbs. The horizontal distance between the curves is the generalization gap. The vertical axis is logarithmic. More examples move the optimum right, and more noise moves it left.

Two observations from the book. A simpler function is more likely to generalize, but it must still reach a low training error. And the training curve always lies below the test curve, because the expected training error of a fitted model is never above its expected test error.

Hypotheses, Occam and the VC dimension

Occam’s razor

Ideas about generalization go back at least to Ptolemy. Many early scholars invoked a principle of parsimony, now known as Occam’s razor (c. 1287–1347): among hypotheses that explain the observations equally well, prefer the simplest. To see why it is needed, count how many hypotheses explain a small training set perfectly.

The violet curves all pass through the five points with zero training error, yet they differ everywhere else, so training error cannot choose among them. The teal quadratic is the simplest, and here it recovers the true function. Occam’s razor is a preference for simple hypotheses, not a theorem.

The VC dimension

The best known is the Vapnik-Chervonenkis dimension, or VC dimension, for binary classifiers. It is the largest for which some different points can be labeled in every possible way, and then they are shattered. The demo uses a straight line in the plane.

Drag the points. Each labeling colors each point violet or teal, and the slider steps through them. A dashed line appears when a line separates the two colors. The table counts how many labelings each placement can separate. A placement in a triangle realizes all of them, so three points can be shattered. A placement on one straight line cannot. Four points cannot be shattered by any placement, so the VC dimension of lines in the plane is three.

Quantifying capacity gives bounds on the gap, but they are rarely tight enough for deep learning.

Effective versus representational capacity

This last demo is an honest toy. It fits a degree-9 polynomial to ten noisy points by gradient descent and stops after a chosen number of steps, on a log scale.

Early on, gradient descent fits the easy directions of the problem and the curve stays smooth. Later it also fits the hard directions, and the curve bends towards the noisy points. A degree-9 model stopped early therefore behaves like a simpler model, with lower effective capacity than its degree suggests.

Non-parametric models and more data

Every model so far is parametric: it has a parameter vector of finite size, fixed before any data arrive. A non-parametric model has no such limit. Its complexity can grow with the training set. The standard example is nearest neighbor regression. It stores the training inputs and targets. For a new input , it returns the target of the closest stored input, with . The -nearest-neighbour rule averages the targets of the nearest points.

The prediction is a staircase that jumps to the nearest training target, so it reproduces every training target and its training error is zero. With more data the staircase hugs the true curve. The cubic has four parameters and keeps a gap that more data cannot close.

The ideal model and the Bayes error

The ideal model knows the true distribution . It still errs when the mapping from to is random, or when depends on variables missing from . That unavoidable error is the Bayes error, here the noise variance .

Training set size

Both errors depend on the training set size. Expected generalization error never increases as the training set grows. A fixed model with too little capacity levels off above the Bayes error. The right capacity may need more examples to close its gap.

The data come from a degree-5 polynomial with noise. For each size, the demo draws 15 training sets. It shows the quadratic, whose capacity is fixed, and a model whose degree is chosen for each set as the best one. That choice uses the test error and is an oracle, as in the book’s Figure 5.4. It shows what optimal capacity can achieve, and it is not a method for real data.

The quadratic’s training error rises with the training set, since larger sets are harder to fit with so little capacity. Its test error falls, then flattens above the Bayes error. For small sets the training error can sit below the Bayes error, because the algorithm can memorize. The lower panel shows the best degree climbing and then leveling off near the true degree 5.

The no free lunch theorem

Inductive reasoning, from a few examples to a general rule, is not logically valid. Machine learning escapes only partly, with rules that are probably correct. The no free lunch theorem for machine learning (Wolpert, 1996) goes further: over all possible data generating distributions, every classification algorithm has the same average error rate on previously unobserved points. The most sophisticated algorithm has the same average accuracy as one that predicts the same class for every point.

Here is the theorem in miniature. The inputs are the eight points 0 to 7 on a line. A world assigns a label of 0 or 1 to each point, and there are 2⁸ = 256 worlds. The learner sees the labels of the inputs you tick and must predict the rest. The score counts only the unseen inputs, averaged over the chosen family of worlds.

The four learners are majority (the more common training label), nearest (the label of the closest training input), always 0, and contrarian (the opposite of nearest). On all 256 worlds every learner scores exactly 50 percent. For each world a learner gets right on an unseen input, a twin world agrees on the training inputs and is wrong. Switch to smooth worlds and nearest wins; jagged worlds reorder them.

Regularization and weight decay

The no free lunch theorem means an algorithm must be designed for its task, by building in preferences. The book’s example is weight decay: linear regression minimizes the training error plus a penalty that prefers small weights,

Here is a hyperparameter chosen before training. At there is no preference, and a larger pushes the weights towards zero, trading fit for smaller slopes.

The model here has degree 9 throughout, as in the book’s Figure 5.5. The true function is quadratic. Use the slider to move from very small to very large and watch both panels.

A very large forces the weights to almost zero, which underfits. As approaches zero, the degree-9 curve overfits, as in Figure 5.2. Regularization is any change meant to reduce generalization error, not training error. Here it raises the training error.

A regularized model learns by adding a penalty to its cost. For weight decay the penalty is . Excluding a function from the hypothesis space is an infinitely strong preference against it.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 5.2 (pages 110–120), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.