Cross-Validation

Estimating prediction error by rotating which part of the data is held out. K-fold and leave-one-out cross-validation defined, the leverage shortcut that gives leave-one-out for least squares from a single fit derived step by step and checked on the diabetes data, a seeded simulation measuring the bias and variance of the estimates for different numbers of folds, what cross-validation does and does not estimate, why its usual standard error is too small, tuning with cross-validation and nested cross-validation, and the variants in scikit-learn.

A single split of 442 diabetes patients into training and test sets gives an estimate of prediction error that depends heavily on which patients landed where. In Training, Validation, and Test Sets, the test MSE of the same linear regression ranged from about 2,300 to 3,800 across random splits with 44 test patients. And the data spent on testing are data not spent on fitting.

Cross-validation addresses both problems by taking turns. The data are divided into parts; each part is held out once while the model is fitted to the rest; and the errors on the held-out parts are combined. Every observation is used for testing exactly once and for fitting $K - 1$ times. The idea goes back at least to the 1970s, when Stone (1974) used it both to choose among predictors and to assess the chosen one, and it is now the standard way to estimate prediction error and to tune models when data are limited (Hastie, Tibshirani and Friedman, 2009, §7.10).

K-fold cross-validation

Divide the $n$ observations at random into $K$ groups of roughly equal size, the folds. For $k = 1, \dots, K$, fit the model to all the data except fold $k$, and compute its loss on the observations in fold $k$.

Five-fold cross-validation. In each round one fold is held out for validation and the model is fitted to the other four; after five rounds every observation has been predicted once by a model that did not see it.
Five-fold cross-validation. In each round one fold is held out for validation and the model is fitted to the other four; after five rounds every observation has been predicted once by a model that did not see it.

To write the estimate, let $\kappa(i)$ be the fold that contains observation $i$, and let $\hat{f}^{-k}$ be the model fitted with fold $k$ removed. The cross-validation estimate of prediction error is the average loss of each observation's held-out prediction (Hastie et al., 2009, eq. 7.48):

$$\mathrm{CV}(\hat{f}) = \frac{1}{n} \sum_{i=1}^{n} L\bigl(y_i, \hat{f}^{-\kappa(i)}(x_i)\bigr).$$

For squared error, $L(y, \hat{y}) = (y - \hat{y})^2$, this is the mean squared error of the $n$ held-out predictions. A common variant averages the $K$ per-fold MSEs instead; the two agree exactly when the folds have equal sizes and nearly otherwise. Typical choices are $K = 5$ or $K = 10$.

The diabetes data in ten folds

The ten-input linear regression from Multiple Linear Regression, with the same ten folds (two of 45 patients and eight of 44):

Fold 1 2 3 4 5 6 7 8 9 10
MSE 3,112.0 3,766.9 2,346.3 3,501.1 2,651.4 3,359.2 2,644.8 3,098.3 2,254.6 3,117.8

The average of the ten fold MSEs is 2,985.2; the MSE pooled over all 442 held-out predictions is 2,987.3. The training MSE of the same model fitted to all 442 patients is 2,859.7, so the training error understates the cross-validated error by about 4%, a modest gap for a model with eleven coefficients and 442 observations. The fold MSEs range from 2,255 to 3,767, with a standard deviation of 498.1. Each is a holdout estimate from about 44 patients and is as noisy as the single splits above. Their average is much steadier.

What to do with the K models

Cross-validation fits $K$ models, but none of them is the final model. They exist only to estimate how well the procedure (fit a linear regression on these ten inputs) predicts. The model to use is then fitted to all $n$ observations (Hastie et al., 2009, §7.10.1). Its error is estimated by the cross-validation figure, which describes models fitted to $n(K - 1)/K$ observations, slightly fewer than the final model gets. The consequences of that difference are taken up below.

If a test set has been kept back, as the previous article recommends, cross-validation runs on the remaining data only. It replaces the validation set, not the test set.

Leave-one-out cross-validation

The extreme case $K = n$ holds out one observation at a time: fit to the other $n - 1$, predict the one left out, and repeat for every observation. This is leave-one-out cross-validation (LOOCV). It has no randomness, since there is only one way to leave out each observation, and each fit uses almost all the data. In general it costs $n$ fits. For least-squares regression it costs one.

The leverage shortcut

Write the linear model in matrix form as in Multiple Linear Regression: $A$ is the $n \times p$ matrix of inputs with a column of ones, $x_i^{\mathsf{T}}$ is its $i$th row, $M = A^{\mathsf{T}} A$, the coefficients are $b = M^{-1} A^{\mathsf{T}} y$, and the fitted values are $\hat{y} = A b = H y$ with the hat matrix $H = A M^{-1} A^{\mathsf{T}}$. The diagonal entry

$$h_i = x_i^{\mathsf{T}} M^{-1} x_i$$

is the leverage of observation $i$: how much its own outcome contributes to its own fitted value, $\partial \hat{y}_i / \partial y_i = h_i$. Linear Regression Assumptions gives its form for a single input. Leverages lie between $1/n$ and 1 and add up to $p$, the number of coefficients.

Remove observation $i$. The fit without it uses $M - x_i x_i^{\mathsf{T}}$ in place of $M$ and $A^{\mathsf{T}} y - x_i y_i$ in place of $A^{\mathsf{T}} y$. The inverse of a matrix changed by one outer product has a closed form, the Sherman-Morrison formula:

$$\bigl(M - x_i x_i^{\mathsf{T}}\bigr)^{-1} = M^{-1} + \frac{M^{-1} x_i \, x_i^{\mathsf{T}} M^{-1}}{1 - h_i}.$$

Multiplying on the left by $x_i^{\mathsf{T}}$ and using $x_i^{\mathsf{T}} M^{-1} x_i = h_i$,

$$x_i^{\mathsf{T}} \bigl(M - x_i x_i^{\mathsf{T}}\bigr)^{-1} = x_i^{\mathsf{T}} M^{-1} \Bigl(1 + \frac{h_i}{1 - h_i}\Bigr) = \frac{x_i^{\mathsf{T}} M^{-1}}{1 - h_i}.$$

The prediction for $y_i$ from the fit without it is therefore

$$\hat{y}_{(-i)} = \frac{x_i^{\mathsf{T}} M^{-1}\bigl(A^{\mathsf{T}} y - x_i y_i\bigr)}{1 - h_i} = \frac{\hat{y}_i - h_i y_i}{1 - h_i},$$

and its error, after putting $y_i$ over the same denominator,

$$y_i - \hat{y}_{(-i)} = \frac{y_i (1 - h_i) - \hat{y}_i + h_i y_i}{1 - h_i} = \frac{y_i - \hat{y}_i}{1 - h_i}.$$

The deleted residual is the ordinary residual divided by $1 - h_i$. Leave-one-out cross-validation for least squares is then (James, Witten, Hastie and Tibshirani, 2021, eq. 5.2; Hastie et al., 2009, eq. 7.51)

$$\mathrm{CV}_{(n)} = \frac{1}{n} \sum_{i=1}^{n} \Bigl(\frac{y_i - \hat{y}_i}{1 - h_i}\Bigr)^2,$$

computed from one fit to all the data. The sum of the squared deleted residuals is known as the PRESS (prediction sum of squares) statistic; Allen (1974) is, with Stone (1974), one of the key early references for cross-validation that Hastie et al. (2009, ch. 7 bibliographic notes) single out. The formula also explains why the training error is optimistic: each residual is shrunk by the factor $1 - h_i$, because each observation pulls the fit toward itself, and points of high leverage pull hardest.

A version of the shortcut, with the diagonal of $S$ in place of the leverages, holds for many linear fitting methods $\hat{y} = S y$ (Hastie et al., 2009, eq. 7.51), such as ridge regression and smoothing splines. For logistic regression, trees and most other methods there is no such formula, and the model is refitted $n$ times.

Checking it on the diabetes data

For the ten-input regression, 442 separate refits and the shortcut give the same LOOCV estimate, 3,001.753, and the 442 deleted residuals agree to within $2 \times 10^{-11}$. The leverages run from 0.0072 to 0.1276 and sum to 11, the number of coefficients. The patient with the highest leverage has an ordinary residual of $-37.31$; divided by $1 - 0.1276$, it becomes $-42.77$ when that patient is left out. With BMI as the only input, the leverages are all below 0.032 and LOOCV (3,923.0) is barely above the training MSE (3,890.5).

Replacing each $h_i$ by their average $p/n$ gives generalized cross-validation,

$$\mathrm{GCV} = \frac{1}{n} \sum_{i=1}^{n} \Bigl(\frac{y_i - \hat{y}_i}{1 - p/n}\Bigr)^2 = \frac{\text{training MSE}}{(1 - p/n)^2},$$

which needs only the trace of $H$ (Hastie et al., 2009, eq. 7.52). For the ten-input model it is 3,007.5, close to the exact LOOCV value of 3,001.8. Since $1/(1 - x)^2 \approx 1 + 2x$ for small $x$, GCV is approximately the training MSE times $1 + 2p/n$, the same correction for optimism that underlies Mallows' $C_p$ and AIC in Model Selection.

How good are the estimates?

Cross-validation is an estimator, with a bias and a variance of its own. The number of folds trades one against the other, and the usual account (James et al., 2021, §5.1.4) runs as follows. Each training part has $n(K - 1)/K$ observations. With few folds, the models are fitted to noticeably less data than the final model, so they are worse and the estimate is biased upward. With $K = n$, the training sets are almost the full data and the bias almost disappears, but the $n$ fitted models are nearly identical, so their errors are highly correlated, and the average of highly correlated quantities has a high variance.

The first half of that account is certain; the second is a tendency, not a law. Both can be measured in a simulation where the true error is known.

A simulation

Training sets of $n = 40$ points are drawn with $x$ uniform on $[0, 1]$ and $y = \sin(5x) + \varepsilon$, $\varepsilon \sim N(0, 0.3^2)$, the setting of The Bias-Variance Tradeoff with random rather than fixed inputs. Two methods are fitted: a cubic polynomial by least squares, which is stable, and 1-nearest-neighbor regression, which predicts each new point by the outcome of its single closest training point and is very unstable. For each of 2,000 training sets (seed 742), the script computes the conditional error $\mathrm{Err}_{\mathcal{T}}$, the expected squared error of that particular fitted model on a new point,

$$\mathrm{Err}_{\mathcal{T}} = \sigma^2 + \int_0^1 \bigl(\hat{f}(x) - f(x)\bigr)^2 \, dx,$$

and its cross-validation estimates for several $K$. The expected error $\mathrm{Err}$ is the average of $\mathrm{Err}_{\mathcal{T}}$ over training sets: 0.1050 for the cubic and 0.1840 for 1-nearest neighbor.

Cubic 2-fold 5-fold 10-fold 20-fold LOOCV 10-fold × 10
Mean estimate 0.1279 0.1083 0.1057 0.1050 0.1046 0.1059
Bias +0.0229 +0.0033 +0.0007 +0.0000 −0.0004 +0.0009
Standard deviation 0.0858 0.0292 0.0267 0.0258 0.0255 0.0260
1-nearest neighbor 2-fold 5-fold 10-fold 20-fold LOOCV 10-fold × 10
Mean estimate 0.1946 0.1871 0.1850 0.1845 0.1840 0.1848
Bias +0.0106 +0.0031 +0.0010 +0.0005 +0.0000 +0.0008
Standard deviation 0.0627 0.0567 0.0554 0.0556 0.0551 0.0534
Left: the expected error of a cubic fitted to n points (the learning curve), marked at the training sizes that 2-, 5- and 10-fold and leave-one-out cross-validation use with 40 points. Right: their estimates over 2,000 training sets. Two-fold is biased upward by exactly the learning curve's rise from 40 to 20 points; the others are nearly unbiased and about equally variable.
Left: the expected error of a cubic fitted to n points (the learning curve), marked at the training sizes that 2-, 5- and 10-fold and leave-one-out cross-validation use with 40 points. Right: their estimates over 2,000 training sets. Two-fold is biased upward by exactly the learning curve's rise from 40 to 20 points; the others are nearly unbiased and about equally variable.

Bias follows the learning curve. The expected error of a cubic fitted to 20 points is 0.1289, to 32 points 0.1094, to 36 points 0.1068 and to 39 points 0.1058; the 2-, 5-, 10-fold and leave-one-out means are within about 0.001 of these. Cross-validation estimates the error of the model fitted to the training part, so its bias is the slope of the learning curve over the data it withholds (Hastie et al., 2009, §7.10.1). With 40 observations, 2-fold cross-validation fits a cubic to 20 points, where the curve is steep, and overstates the error by 22%. By 10 folds the bias is under 1%. The 1-nearest-neighbor learning curve is flatter, so its bias is smaller at every $K$.

Variance did not rise with K. For both methods the standard deviation of the estimate fell from 2 to 5 to 10 folds and was flat or slightly lower beyond, with LOOCV the least variable estimate for the cubic and essentially tied for 1-nearest neighbor. The 2-fold estimate is the most variable, partly because some cubics fitted to 20 random points extrapolate wildly into gaps in the data. This contradicts the textbook tendency, and it is not a quirk of the simulation. Bengio and Grandvalet (2004) decompose the variance of K-fold cross-validation and conclude that there is "no general trend": the minimum variance "can be reached for $K = n$ or for an intermediate value of $K$." Hastie et al. (2009, §7.10.1) state the textbook view carefully, that leave-one-out "can have high variance", and their own simulation in §7.12 found 10-fold cross-validation less variable than leave-one-out. Which way it goes depends on the method, the loss and the data. The practical recommendation of $K = 5$ or 10 survives on other grounds: it is cheaper than leave-one-out, its bias is usually small, and repeating it with new random folds can reduce the part of its variance that comes from the fold assignment.

Repeating the split helps a little. Ten-fold cross-validation repeated with ten different random fold assignments, and averaged, lowered the standard deviation from 0.0267 to 0.0260 for the cubic and from 0.0554 to 0.0534 for 1-nearest neighbor. Repetition removes the noise of the fold assignment, not the noise of the data. On the diabetes data, 200 different assignments of the same 442 patients to ten folds gave estimates with a standard deviation of 21.4 (range 2,962 to 3,061), small next to the uncertainty that comes from having 442 patients at all.

What cross-validation estimates

A natural hope is that cross-validation estimates $\mathrm{Err}_{\mathcal{T}}$, the error of the model actually fitted to the data at hand. It does not do so well. In the simulation, the correlation across training sets between the 10-fold estimate and $\mathrm{Err}_{\mathcal{T}}$ was $-0.03$ for the cubic and $+0.47$ for 1-nearest neighbor.

Ten-fold cross-validation estimates against the true conditional error of the model fitted to each of 2,000 training sets. For the cubic the estimate carries essentially no information about which training sets produced better models; for the unstable 1-nearest-neighbor rule it carries some.
Ten-fold cross-validation estimates against the true conditional error of the model fitted to each of 2,000 training sets. For the cubic the estimate carries essentially no information about which training sets produced better models; for the unstable 1-nearest-neighbor rule it carries some.

For the cubic, the conditional error varies little between training sets (standard deviation 0.0124), much less than the estimate does (0.0267), and the variation the estimate does have is unrelated to it. Hastie et al. (2009, §7.12) report the same pattern, including correlations near zero or negative, and conclude that cross-validation "typically estimates well only the expected prediction error" $\mathrm{Err}$, the average over training sets. Bates, Hastie and Tibshirani (2024) prove this for least-squares regression: the cross-validation estimate is closer, in mean squared error, to the average error of models fitted to other training sets of the same size than to the error of the model fitted to the data at hand. The cross-validation figure for a procedure is therefore best read as a statement about the procedure: this is how well a cubic fitted to 40 points from this population predicts, on average.

The standard error is too small

It is common to report the standard deviation of the $K$ fold errors divided by $\sqrt{K}$ as the standard error of the cross-validation estimate, as in the diabetes example: $498.1 / \sqrt{10} = 157.5$. The formula would be right if the fold errors were independent. They are not: each pair of training parts shares $(K - 2)/(K - 1)$ of its observations, and an observation used to test one fold was used to fit all the others. In the simulation, this naive standard error averaged 0.0228 for the cubic with 10 folds, while the estimates actually varied with a standard deviation of 0.0267; for 1-nearest neighbor the figures were 0.0369 and 0.0554. Bengio and Grandvalet (2004) prove that no estimator of the variance of K-fold cross-validation is unbiased for all distributions, and Bates et al. (2024) show that intervals built on the naive standard error can cover the true error far less often than their nominal level, proposing a nested scheme that corrects it. The naive standard error remains useful as a rough scale, which is how the one-standard-error rule uses it, but it should not be read as exact.

Tuning with cross-validation

When a model has a hyperparameter, cross-validation estimates the error for each candidate value, and the value with the smallest estimate is chosen (Hastie et al., 2009, eq. 7.49). For nearest-neighbor regression of diabetes progression on BMI and S5, with $k$ from 1 to 100 and the same ten folds, the cross-validated MSE is 5,633.2 at $k = 1$, falls to its minimum of 3,226.3 at $k = 22$, and rises slowly to 3,362.0 at $k = 100$. The final model uses $k = 22$ and all 442 patients. The pruned trees of Regression Trees were chosen the same way, and Model Selection adds the one-standard-error rule, which prefers a simpler model when the curve is flat near its minimum.

Nested cross-validation

The minimum of a cross-validation curve, 3,226.3, is not an honest estimate of the tuned model's error. It is the winner's curse again: among 100 noisy estimates, the smallest is the one most likely to be too small. To estimate the error of the whole procedure, including the tuning, the tuning has to be repeated inside each fold, so that the held-out fold plays no part in choosing $k$. This is nested cross-validation:

  1. Split the data into $K$ outer folds.
  2. For each outer fold $k$: on the other $K - 1$ folds, run an ordinary (inner) cross-validation to choose the hyperparameter; fit the model with that value to those $K - 1$ folds; predict the outer fold $k$.
  3. Average the outer-fold errors.

On the diabetes data, with ten outer folds and ten inner folds, the nested estimate is 3,301.0, against 3,226.3 for the minimum of the curve: the curve's minimum understates the tuned model's error by about 2%. The values of $k$ chosen in the ten outer training parts were 17, 19, 20, 20, 20, 21, 21, 21, 32 and 68, a reminder that the tuning itself is variable. Varma and Simon (2006) showed the effect is large when many settings are searched and the signal is weak: on simulated gene-expression data with no difference between classes, the cross-validated error of tuned classifiers was below 30% for a sizable share of datasets, while nested cross-validation gave "an almost unbiased estimate of the true error."

The same experiment can be run on data with no signal at all. Fifty cases have ten inputs and an outcome drawn independently of them from a standard normal distribution, so no prediction can beat the true mean of 0, whose expected squared error is 1. Nearest-neighbor regression with $k$ from 1 to 40 is tuned by 10-fold cross-validation, over 300 simulated datasets:

Estimate Mean over 300 datasets
Minimum of the cross-validation curve 0.985
Nested cross-validation 1.057
True error of the tuned model 1.063

The minimum of the curve claims an error below 1 in 54.7% of the datasets, better than any possible predictor; the nested estimate is within 0.006 of the truth on average.

Nested cross-validation estimates the error of the procedure; it does not choose the final hyperparameter. That is still done by an ordinary cross-validation on all the data, as above. When the data allow a separate test set, the test set does the same job as the outer loop.

Variants

  • Stratified K-fold, for classification, makes each fold's class proportions match the whole dataset's. It removes one source of noise between folds, and matters most with rare classes. The course wiki's Evaluating Classifiers shows the fold-to-fold variation of text classification scores.
  • Repeated K-fold runs the procedure several times with different random folds and averages, reducing the variance due to the fold assignment, as measured above.
  • Monte Carlo cross-validation (repeated random subsampling) draws a fresh random training and validation split each time. Observations can be held out several times or never.
  • Leave-$p$-out holds out every possible subset of $p$ observations. With $p = 1$ it is LOOCV; with $p = 2$ it already needs $n(n - 1)/2$ fits, and it is used mainly where pairs are natural, for example to estimate the area under an ROC curve, which compares pairs of cases.
  • Grouped cross-validation keeps all records of a patient, a site or a document collection in the same fold, and time-series cross-validation always trains on the past and tests on the future. Both prevent the forms of leakage that a random assignment of correlated records would allow.

K-fold cross-validation with $K < n$ is sometimes called non-exhaustive, because it uses only one of the many ways to divide the data, and leave-one-out and leave-$p$-out exhaustive. The distinction matters less than it sounds: the variation from the choice of folds is usually small next to the variation from the data, as the 200 fold assignments of the diabetes data showed.

For classification, cross-validation works with any loss: the error rate, the log loss of Loss Functions for Classification, or a ranking measure such as AUC. The bootstrap offers another way to estimate prediction error by resampling, with its own corrections for the overlap between training and test data.

In Python

import numpy as np
from sklearn.datasets import load_diabetes
from sklearn.linear_model import LinearRegression
from sklearn.model_selection import GridSearchCV, KFold, cross_val_score
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_diabetes(return_X_y=True, scaled=False)
folds = KFold(n_splits=10, shuffle=True, random_state=0)

mse = -cross_val_score(LinearRegression(), X, y, cv=folds, scoring="neg_mean_squared_error")
print(mse.mean(), mse.std(ddof=1) / np.sqrt(10))      # 2985.2 157.5

# leave-one-out by the leverage shortcut
A = np.column_stack([np.ones(len(y)), X])
H = A @ np.linalg.solve(A.T @ A, A.T)
e = y - H @ y
print(np.mean((e / (1 - np.diag(H))) ** 2))           # 3001.8

# nested CV: k chosen by an inner 10-fold CV inside each outer training part
knn = make_pipeline(StandardScaler(), KNeighborsRegressor())
inner = GridSearchCV(knn, {"kneighborsregressor__n_neighbors": range(1, 101)},
                     cv=KFold(10, shuffle=True, random_state=1), scoring="neg_mean_squared_error")
nested = -cross_val_score(inner, X[:, [2, 8]], y, cv=folds, scoring="neg_mean_squared_error")
print(nested.mean())                                  # 3296.3

scikit-learn's scorers follow the convention that larger is better, so error measures come negated: "neg_mean_squared_error" returns $-\text{MSE}$ for each fold, and the minus sign in front of cross_val_score turns the values back into MSEs. Measures that are already larger-is-better, such as "r2", are not negated. Passing an integer as cv uses unshuffled folds (stratified for classifiers); passing a KFold object with shuffle=True and a seed gives random folds that can be reproduced. Putting the scaler inside the pipeline means it is refitted within every training part, and wrapping GridSearchCV in cross_val_score gives nested cross-validation. Its result, 3,296.3, differs slightly from the 3,301.0 above because GridSearchCV chooses $k$ by the average of the inner fold MSEs and cross_val_score averages the outer fold MSEs, where the article's script pools the squared errors. For leave-one-out with any model, cv=LeaveOneOut() refits $n$ times. The numbers in this article are computed by tools/experiments/data-science/cross-validation.py in the site's repository.

References

  • Allen, D. M. (1974). The relationship between variable selection and data agumentation and a method for prediction. Technometrics, 16(1), 125–127. record
  • Bates, S., Hastie, T., and Tibshirani, R. (2024). Cross-validation: What does it estimate and how well does it do it? Journal of the American Statistical Association, 119(546), 1434–1445. record
  • Bengio, Y., and Grandvalet, Y. (2004). No unbiased estimator of the variance of K-fold cross-validation. Journal of Machine Learning Research, 5, 1089–1105. record
  • Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
  • Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society, Series B, 36(2), 111–147. record
  • Varma, S., and Simon, R. (2006). Bias in error estimation when using cross-validation for model selection. BMC Bioinformatics, 7, 91. record