Overfitting and model choice: cross-validation

Fit curves of rising degree to eight points. Watch the error on those points fall to zero while the error on new points climbs.

A curve that fits too well

Polynomials of degree 1 to 7 fitted to eight noisy points from a parabola (seed 9300); errors averaged over 200 such datasets.

Eight points from a smooth parabola plus noise. Fit polynomials of rising degree; below, the errors on the eight points and on 200 new ones, averaged over 200 such datasets.

degree

–

average error, eight points

–

average error, new points

–

Predict first. As the degree rises from 1 to 7, what will the two errors do?

Describe this picture

Two panels. The first holds eight training points at $x=0,0.5,\dots,3.5$ , drawn from the parabola $y=0.5+2x-0.6x^2$ , shown dashed, plus noise of standard deviation 0.5 (seed 9300), and a fitted polynomial curve. The second draws two error curves against the degree: the mean squared error on the eight training points, and on 200 fresh points from the same source, each averaged over 200 datasets built the same way (seeds 9300 to 9499), with a dashed line at the noise level, 0.25. Before the clip a question asks what the two errors will do as the degree rises from 1 to 7: both fall; the training error falls while the error on new points falls, then rises; or both rise. A tap picks one and starts the clip. In the clip, over 10 seconds, the degree steps from 1 to 7, each step a short morph, and both error curves grow by one point per step. The curve bends towards each point, and at degree 7 it passes through all eight with large swings between them. The average training error falls to 0; the average error on new points falls from 0.6361 to its lowest, 0.3299 at degree 2, then climbs to 0.7846 at degree 7. Readouts give the degree and both average errors. After the clip a slider sets the degree; it starts at 7.

Training error and error on new points

Before the clip you guessed. The training error only falls as the degree rises, down to 0 at degree 7, where eight coefficients can pass a curve through eight points exactly. Averaged over 200 datasets like the one in the picture, the error on new points falls from 0.6361 at degree 1 to its lowest, 0.3299, at degree 2, the true shape, and then rises, to 0.7846 at degree 7. One dataset alone can mislead: the one drawn here happens to fit best at degree 5, because its first point landed almost three noise standard deviations low.

A degree-7 curve does not learn the parabola. It learns the parabola plus the noise in these eight points, and the noise will not be there next time. Fitting the noise along with the signal is overfitting.

Watch out

The model with the lowest error on its own data is not the best model. A flexible enough model can always reach zero error there. What matters is the error on data it has not seen.

Training error against test error

A polynomial of degree $d$ has $d+1$ coefficients, and fitting it is a least-squares problem with $d+1$ columns, as in Least squares. Each extra column can only lower the training error; with $d+1$ equal to the number of points it reaches 0.

How much does the training error flatter the model? Suppose the model’s form contains the truth, the $x$ values are fixed, and the noise has variance $\sigma^2$ . Then on average, per point,

\begin{aligned} \text{training error}&=\sigma^2\Big(1-\frac{d+1}{n}\Big),\\ \text{error on new }y\text{ at the same }x&=\sigma^2\Big(1+\frac{d+1}{n}\Big). \end{aligned}

The gap between them, $2\sigma^2(d+1)/n$ , is the optimism of the training error. It grows with every coefficient.

Holding points back: cross-validation

The honest check is to test a model on points it was not fitted to. With few data, take turns: leave one point out, fit to the rest, and see how badly the fit misses the point left out. Do this for every point and average the squared misses:

\mathrm{CV}=\frac1n\sum_{k=1}^{n}\big(y_k-\hat y_{(-k)}\big)^2,

where $\hat y_{(-k)}$ is the prediction at $x_k$ of the model fitted without point $k$ . This is leave-one-out cross-validation.

Leave one out

Four points; each held out in turn, a line and then a parabola fitted to the other three.

Four points. Hold one out, fit to the other three, and see how far the fit misses the one it never saw.

line, held-out squares

–

parabola, held-out squares

–

Describe this picture

Four points at $t=-1,0,1,2$ with $y=2,1,2,6$ , the data of the least-squares page of the linear algebra course. In the clip each point is held out in turn and ringed: a line, then a parabola, is fitted to the other three and drawn across the panel, and the miss at the held-out point is drawn as a square. Readouts add up the squares as they come: 41.25 for the line and 2.22 for the parabola. The panel has a play button and no other control.

Fitted to all four points, the parabola misses by less than the line, but any curve with more coefficients would too. Held out, the comparison is fair: the parabola’s squares add to 2.22 and the line’s to 41.25. The parabola predicts points it has not seen far better.

A price for complexity: AIC

Cross-validation refits the model many times. A cheaper rule adds a fixed price for each coefficient to the training fit. For bell-shaped noise, with constants dropped,

\mathrm{AIC}=n\ln\frac{\mathrm{SS}_\text{res}}{n}+2(d+1),

and the model with the smallest $\mathrm{AIC}$ wins. The first term rewards a good fit; the second charges 2 for each coefficient. The rule works when $n$ is well above the number of coefficients; it breaks down when the fit is exact, because the logarithm of 0 is not defined.

Shrinking instead: ridge

Instead of choosing a degree, keep many coefficients but pull them towards 0. Ridge regression minimises

\mathrm{SS}_\text{res}+\alpha\sum_ib_i^2,

with the intercept left out of the penalty. Here $\alpha$ is a penalty weight, not the false-alarm chance of the testing pages. With $\alpha=0$ it is ordinary least squares; as $\alpha$ grows, the curve flattens towards a horizontal line at the mean of $y$ . The penalty plays the part of the degree, and cross-validation is the usual way to set it. This is the shrinkage of Estimators: bias and variance: a little bias for much less scatter.

Worked example

1. Fitting the four points. The line leaves $\mathrm{SS}_\text{res}=6.30$ , the parabola $0.05$ , the cubic 0: a cubic passes through any four points.

2. Leave-one-out. For the line, the predictions at the held-out points are $-2$ , $2.5714$ , $4$ and $1.6667$ , missing by $4$ , $-1.5714$ , $-2$ and $4.3333$ : squares adding to 41.25, mean 10.31. For the parabola, which passes exactly through each set of three, the predictions are $3$ , $0.6667$ , $2.3333$ and $5$ , missing by $-1$ , $0.3333$ , $-0.3333$ and $1$ : squares adding to 2.222, mean 0.5556. The parabola predicts held-out points about twenty times better. The cubic cannot be cross-validated here: three points cannot fix four coefficients.

3. AIC. Line: $4\ln(6.30/4)+2\times2=1.817+4=5.82$ . Parabola: $4\ln(0.05/4)+2\times3=-17.53+6=-11.53$ . Lower wins: the parabola.

4. Optimism. With $n=8$ points, noise $\sigma=0.5$ and a parabola ( $d+1=3$ ): expected training error $0.25\times\tfrac58=0.15625$ , expected error on new $y$ at the same $x$ $0.25\times\tfrac{11}8=0.34375$ , a gap of $0.1875$ . At degree 7 the training error is 0 and the error on new $y$ at the same $x$ is $0.25\times2=0.5$ . Between the points, where the degree-7 curve swings, it is worse still.

Try it yourself. A cubic fitted to 4 points has training error 0. A very large ridge penalty flattens the fit to the mean of $y$ .

Where you’ll meet this

Choosing a model’s size. The order of an autoregressive model, the number of taps in a filter, the number of features in a predictor: each is a degree to choose, and each is chosen by held-out error or a criterion like AIC.

Machine learning. A trained model should be checked on data held out from training, because its training error is optimistic in exactly the way shown here.

Smoothing. How wide a smoothing window to use, in Smoothing and seasonality, is the same question: too narrow follows the noise, too wide loses the shape.

In signal processing · choosing a model order

Linear prediction fits an autoregressive model whose error power keeps falling as the order grows; AIC adds a price per coefficient and picks the order where the total is smallest. Linear prediction in the signal processing course makes that choice.

Where this leads · ridge and conditioning

Polynomial columns are nearly dependent, so high-degree fits are badly conditioned. Ridge regression is the damped pseudo-inverse of the linear algebra course, which shrinks each direction by $\sigma_i^2/(\sigma_i^2+\alpha)$ , with $\sigma_i$ its singular value.

Reference card

Quantity	Formula	Notes
Degree $d$	$d+1$ coefficients	training error 0 once $d+1\ge n$
Training error	$\sigma^2(1-(d+1)/n)$ per point on average	optimistic
New $y$ , same $x$	$\sigma^2(1+(d+1)/n)$	gap $2\sigma^2(d+1)/n$
Leave-one-out	$\mathrm{CV}=\frac1n\sum_{k=1}^{n}(y_k-\hat y_{(-k)})^2$	refit without each point
AIC	$n\ln(\mathrm{SS}_\text{res}/n)+2(d+1)$	smaller is better
Ridge	minimise $\mathrm{SS}_\text{res}+\alpha\sum_ib_i^2$	penalty in place of degree
Rule	judge a model on data it has not seen

Overfitting and model choice

A curve that fits too well

Training error and error on new points

Training error against test error

Holding points back: cross-validation

Leave one out

A price for complexity: AIC

Shrinking instead: ridge

Worked example

Where you’ll meet this

Reference card

Keep reading with a free account.

Are you 13 or over?

Where to go next.

Account

Subjects

Site

Look

Overfitting and model choice

First, the picture

Training error and error on new points

Training error against test error

Holding points back: cross-validation

A price for complexity: AIC

Shrinking instead: ridge

Worked example

Where you’ll meet this

Reference card