Why one split is not enough
Theory
Suppose we have \(n\) data points and a family of models indexed by flexibility. Polynomials of degree \(d = 1, \dots, 10\), for example. We want the \(d\) that predicts best on new data.
The obvious approach is the validation set approach. We hold out half the data, fit on the other half, and pick the \(d\) with the lowest error on the held-out half.
This works. It is also noisier than most people expect. The noise does not go away when we collect more data. It only stops being obvious.
An illustration
The figure below is built from 300 repetitions of the whole procedure, at each training set size, for each resampling strategy. The dashed line is the true expected test error, computed on a large independent test set. The blue line and the bands are what the resampling strategy reports.
Three things in this figure are worth noting.
The band is wide, and it is widest where it matters. Near the optimum the true error curve is almost flat. A small amount of noise in the estimate therefore moves the winning degree a lot. With a single split we get within one degree of the right answer less than half the time at \(n = 320\).
More data does not fix the single split. Move the slider for \(n\) to the right. The bands get narrower, so the estimate of the error does get more precise. But the fraction of runs that pick a good degree gets worse, because the true curve flattens faster than the noise shrinks.
The estimate is biased upwards. Fitting on half the data gives a worse model than fitting on all of it. So the validation error overstates the error of the model we will actually use.
What \(K\)-fold changes
We split the data into \(K\) parts. For each part in turn we fit on the other \(K-1\) parts and predict the held-out part. Every point is predicted exactly once, by a model that did not see it.
\[ \mathrm{CV}_K = \frac{1}{n} \sum_{i=1}^{n} L\bigl(y_i,\ \hat f^{(-\kappa(i))}(x_i)\bigr) \]
Here \(\kappa(i)\) is the fold that contains point \(i\), and \(\hat f^{(-\kappa)}\) is the model fitted without fold \(\kappa\). Two things improve at the same time. Each fit uses more data, and we average over \(K\) splits instead of trusting one.
If we take \(K = n\), every fit uses all but one point. This is leave-one-out cross-validation. For models that are linear in their parameters we get it almost for free,
\[ \mathrm{CV}_n = \frac{1}{n}\sum_{i=1}^n \left(\frac{y_i - \hat y_i}{1 - h_{ii}}\right)^2 \]
where \(h_{ii}\) is the \(i\)-th diagonal entry of the hat matrix \(H = X(X^\top X)^{-1}X^\top\). One fit instead of \(n\) fits. This is also why the LOOCV curve in the figure above was cheap enough to simulate 300 times at every \(n\).
Should we always use LOOCV
No, and the figure shows why if we look at the bands instead of the headline number.
LOOCV has the smallest bias, because every fit uses \(n-1\) points. But its \(n\) fits are trained on almost identical data sets. Their errors are therefore strongly correlated, and averaging them removes less variance than we would like.
Five or ten folds usually sit at a better point on this tradeoff, and they cost \(K\) fits instead of \(n\) fits.
Note that this is a bias-variance tradeoff in the estimator of the error, not in the model. These are two different tradeoffs and it is worth keeping them apart.
What this page does not cover
Everything above is about estimating the error of one model. As soon as we use these estimates to choose between models, the winner’s score is no longer an unbiased estimate of anything.
We picked the smallest of ten noisy numbers. The smallest of ten noisy numbers lies below the true smallest value on average. This is a property of minima, not a property of our data.
The fix is not a correction factor. It is a second split. See nested cross-validation, after we have written out the fold loop.