Cross-Validation

Cross-validation estimates how well a learning procedure generalizes by reusing one labelled dataset for both training and evaluation. In its standard form, k-fold cross-validation (also called rotation estimation; Kohavi, 1995), the images are divided into $K$ disjoint parts called folds; a model is trained on $K-1$ folds and scored on the remaining one, the held-out fold is rotated until every image has been scored once, and the scores are combined. It is used when a single held-out validation or test set would be too small to give a trustworthy number, and for choosing hyperparameters on small datasets. The roles of the training, validation and test sets, and the ways a split leaks, are covered in Training, Validation, and Test Sets; this article covers the k-fold family: how the estimate is formed, what it measures, how noisy it is, the variants for grouped and time-ordered images, and nested cross-validation for selecting and assessing a model with the same data.

Purpose

A single holdout split spends data twice over. The images in the held-out set do not train the model, and with a few hundred images the held-out set is small enough that its score depends heavily on which images happened to land in it. Goodfellow, Bengio and Courville (2016, §5.3.1) put the problem this way: a small test set leaves statistical uncertainty around the estimated error, which makes it hard to claim that one algorithm beats another; with hundreds of thousands of examples this is not a serious issue, and for smaller datasets procedures that repeat training and testing on different splits use every example in the estimate, at the price of more computation.

Hastie, Tibshirani and Friedman (2009, §7.10; ESL below) call cross-validation probably the simplest and most widely used method for estimating prediction error. It serves the two goals that the split article separates:

• Model selection. For a family of models indexed by a hyperparameter $\alpha$ (a blur width, the $k$ of a nearest-neighbour classifier, a weight-decay strength), the cross-validation error as a function of $\alpha$ estimates the test-error curve; one picks the minimizing $\hat{\alpha}$ and refits the chosen model on all the data (ESL, eq. 7.49).
• Model assessment. The cross-validation error of a fixed procedure estimates its error on new data.

Doing both with the same folds is where cross-validation most often goes wrong; nested cross-validation, below, keeps them apart.

When to Use It

Cross-validation is worth its cost when labelled images are scarce and training is cheap relative to labelling. Typical cases:

• Small medical and scientific datasets, where the number of patients rather than images limits the data. nnU-Net (see U-Net) trains each of its candidate U-Net configurations in a five-fold cross-validation on the training cases, chooses the configuration or ensemble and the post-processing from the pooled cross-validation results, and predicts the test cases with the ensemble of the five fold models (Isensee et al., arXiv v2). For datasets with several images per patient the authors adjusted the splits by hand so that no patient appears in two folds.
• Small benchmarks with official folds. UCF101 and HMDB51 come with three official train/test splits, and papers report accuracy averaged over them (action recognition). UCF101’s three test sets are disjoint blocks of groups (1–7, 8–14, 15–21), while groups 22–25 are always in training, so in our reading the protocol is three folds of a grouped cross-validation rather than a full partition; its technical report had recommended 25-fold leave-one-group-out cross-validation instead.
• Small classification benchmarks with random splits. Caltech-101 results were reported over repeated random draws: Lazebnik, Schmid and Ponce (2006) trained on 30 images per class, tested on up to 50 of the rest, repeated every experiment ten times with different random training and test images, and reported the mean and standard deviation of the per-class recognition rates.

It is rarely used to train large networks on large benchmarks. Training a network $K$ times multiplies the cost by $K$, and the benchmarks that deep vision models are compared on, ImageNet or COCO, have fixed splits and often hidden test labels, so results are comparable only on those splits. There a single validation split carved from the training data does the selecting, as in the training workflow. Few-shot learning resembles cross-validation but is a different procedure: classes are split once into training, validation and test classes, and a trained model is scored on many test episodes sampled at random from the test classes, for example with accuracy averaged over 600 miniImageNet test episodes and a 95% confidence interval (Snell et al., 2017). The resampling there is of test tasks; the model is not retrained.

Cross-validation also needs the images to be exchangeable, or the folds to respect whatever structure they have: frames of one video, scans of one patient or images in time order call for the grouped and time-ordered variants below.

How It Works

The estimate

Let the dataset have $n$ labelled images $(\mathbf{x}_i, y_i)$, let $\kappa(i) \in \{1, \dots, K\}$ be the fold that image $i$ is assigned to at random, and let $\hat{f}^{-k}$ be the model trained with fold $k$ removed. The cross-validation estimate of prediction error is (ESL, eq. 7.48)

$$\mathrm{CV}(\hat{f}) = \frac{1}{n} \sum_{i=1}^{n} L\big(y_i, \hat{f}^{-\kappa(i)}(\mathbf{x}_i)\big),$$

where $L$ is the loss; with the 0–1 loss, $1 - \mathrm{CV}$ is the cross-validated accuracy. $K = n$ is leave-one-out cross-validation. ESL names 5 and 10 as typical choices of $K$.

Every step that looks at the data is part of $\hat{f}$ and has to be redone inside each fold: normalization statistics, feature selection, the choice of the stopping epoch and any hyperparameter search. ESL (§7.10.3) shows that this is also what makes cross-validation work: for a classifier that picks the best of 500 predictors unrelated to the labels, five-fold cross-validation averaged about the true 50% error over 50 simulated datasets, because the predictor was re-chosen within each fold.

What it estimates

The $K$ models are trained on $n(K-1)/K$ images, not $n$, so cross-validation estimates the error of a procedure trained on slightly less data. ESL (§7.10.1) illustrates the consequence with a hypothetical learning curve: with 200 images, five-fold training sets of 160 behave almost like the full set, but with 50 images, training sets of 40 sit on the steep part of the curve and five-fold cross-validation overestimates the error. Leave-one-out trains on $n-1$ images and has little of this bias.

A subtler point is which error is being estimated. One would like the error $\mathrm{Err}_{\mathcal{T}}$ of the model trained on this particular training set $\mathcal{T}$; what cross-validation estimates well is the expected error $\mathrm{Err}$, averaged over training sets of that size drawn from the same distribution. In ESL’s simulation (§7.12), both 10-fold and leave-one-out estimates were approximately unbiased for $\mathrm{Err}$ but correlated only weakly, and mostly negatively, with $\mathrm{Err}_{\mathcal{T}}$ across 100 training sets; the authors conclude that estimating the error of the model trained on one particular training set is not easy given only that training set. Bengio and Grandvalet (2004) take the same view: the average over folds estimates the expected error of the algorithm trained on $n - n/K$ examples.

The choice of K and the variance of the estimate

Larger $K$ means less pessimistic bias and more computation. ESL describes leave-one-out as approximately unbiased but possibly high in variance, because its $n$ training sets are almost identical, and recommends five- or ten-fold as a compromise, citing Breiman and Spector (1992) and Kohavi (1995). Kohavi adds a useful idealization: if the learning algorithm is stable, so that deleting a fold does not change its predictions, every image is effectively scored by one classifier, the number correct is binomial, and the variance of the cross-validated accuracy $a$ is about $a(1-a)/n$, whatever $K$ is. Real algorithms are only approximately stable, which is why the variance does depend on $K$ in practice.

The errors that go into the average are not independent: two images in the same fold were scored by the same model, and two images in different folds by models that share most of their training data. Bengio and Grandvalet (2004) show that, by symmetry, the covariance matrix of the $n$ errors has only three distinct values, the variance $\sigma^2$ of one error, the covariance $\omega$ between errors in the same fold, and the covariance $\gamma$ between errors in different folds, so that with $m = n/K$ images per fold

$$\mathrm{Var}[\mathrm{CV}] = \frac{1}{n}\sigma^2 + \frac{m-1}{n}\,\omega + \frac{n-m}{n}\,\gamma .$$

Their main theorem is that no estimator of this variance is unbiased under all distributions: although the correlations have this simple structure, their values cannot be estimated without bias from the errors of one run. A naive estimate that treats the $n$ errors as independent ignores the covariance terms, and in their experiments on very simple problems its bias was of the order of the variance itself. In our reading, a standard error computed from the $K$ fold scores as if they were independent measurements has the same flaw and claims more precision than cross-validation delivers; comparing two models fairly calls for the methods of statistical significance testing.

How to Apply It

1. Decide the unit of independence. If several images share a patient, video, scene or photographer, assign folds by that unit (grouped cross-validation); the split article explains why.
2. Balance the folds. For classification, stratify so that each fold has the class frequencies of the whole set.
3. Put the whole pipeline inside the loop. Fit normalization constants, feature selection and any tuning on the training folds only. In scikit-learn a Pipeline passed to cross_val_score refits its preprocessing in every fold. Data augmentation is applied to the training folds; the held-out fold is evaluated as test images would be.
4. Combine the scores consistently. ESL’s estimate pools all held-out predictions; cross_val_score returns one score per fold, which are usually averaged. For accuracy with equal-sized folds the two agree; for metrics that are not averages over images, such as the area under a ROC curve or average precision, pooled and per-fold values differ, and the choice should be reported (our reasoning).
5. Select, then refit. For model selection, choose the hyperparameter with the best cross-validation score and train the final model on all the data. ESL (§7.10.1) mentions the one-standard-error rule as a common refinement: take the simplest model whose error is within one standard error of the best.
6. Nest if the tuned procedure’s score will be reported. The winner’s cross-validation score is not an estimate of its performance; see nested cross-validation below.

Example

The script builds small synthetic image datasets and evaluates a $k$-nearest-neighbour classifier on Gaussian-blurred pixels. Each 16×16 grayscale image shows one of four shapes (disc, square, cross, triangle) at a random shift of up to two pixels, with contrast drawn from 0.5 to 1.0 on a zero background and additive Gaussian noise of standard deviation 0.6 (floating-point intensities). A dataset has 80 images, 20 per class; for each of 40 datasets the script also draws 4,000 fresh images that stand in for the population and are never used for any choice.

Part 1 fixes the classifier (blur $\sigma = 1$ pixel, $k = 5$) and compares four estimates of the accuracy of the model trained on all 80 images: one stratified 80/20 holdout split, 5-fold, 10-fold and leave-one-out cross-validation. For the first dataset it also repeats the holdout split and 5-fold cross-validation over 20 random partitions. Part 2 selects $\sigma$ and $k$ from 42 combinations by 5-fold cross-validation and compares the winner’s cross-validation score, a nested estimate (5 outer folds, with the whole selection repeated by 5-fold cross-validation inside each outer training set) and the chosen model’s true accuracy. A last block checks the fold construction and the score against scikit-learn 1.7.2. It runs in about 20 seconds with NumPy 2.3.5 and SciPy 1.16.3.

import numpy as np
from scipy.ndimage import gaussian_filter

K, S = 4, 16                                   # classes, image size (pixels)
yy, xx = np.mgrid[:S, :S] - (S - 1) / 2
SHAPES = np.stack([(xx**2 + yy**2 < 20).astype(float),               # disc
                   ((abs(xx) < 4) & (abs(yy) < 4)).astype(float),    # square
                   ((abs(xx) < 1.5) | (abs(yy) < 1.5)).astype(float),  # cross
                   ((yy > -4) & (yy < 5) & (abs(xx) < (yy + 4) / 2)).astype(float)])  # triangle

def make_images(n_per_class, rng):
    """Grayscale 16x16 shape images, intensities around 0: random 2-pixel shift,
    contrast 0.5-1.0, additive Gaussian noise with standard deviation 0.6."""
    X, y = [], []
    for c in range(K):
        for _ in range(n_per_class):
            img = np.roll(SHAPES[c], tuple(rng.integers(-2, 3, size=2)), axis=(0, 1))
            X.append(rng.uniform(0.5, 1.0) * img + rng.normal(scale=0.6, size=(S, S)))
            y.append(c)
    return np.array(X), np.array(y)

def features(X, sigma):                         # blur each image, then flatten
    return np.array([gaussian_filter(x, sigma) if sigma else x for x in X]).reshape(len(X), -1)

def sqdist(A, B):
    return (A**2).sum(1)[:, None] - 2 * A @ B.T + (B**2).sum(1)[None]

def knn(D, ytr, k):                             # D: test-by-train squared distances
    votes = ytr[np.argsort(D, axis=1)[:, :k]]
    return np.array([np.bincount(v, minlength=K).argmax() for v in votes])  # ties -> lowest label

def stratified_folds(y, n_folds, rng):
    """Shuffle each class, then deal its images round-robin to the folds."""
    fold = np.empty(len(y), int)
    for c in np.unique(y):
        idx = rng.permutation(np.flatnonzero(y == c))
        fold[idx] = (np.arange(len(idx)) + rng.integers(n_folds)) % n_folds
    return [np.flatnonzero(fold == f) for f in range(n_folds)]

def cv_accuracy(D, y, k, folds):                # D: all-by-all distances of the dataset
    """Correct predictions over all held-out images / number of held-out images."""
    hits = 0
    for te in folds:
        tr = np.setdiff1d(np.arange(len(y)), te)
        hits += np.sum(knn(D[np.ix_(te, tr)], y[tr], k) == y[te])
    return hits / sum(len(te) for te in folds)

SIGMAS, KS = (0, 0.5, 1, 1.5, 2, 3), (1, 3, 5, 7, 9, 11, 15)

def select(D_by_sigma, y, idx, n_folds, rng):   # choose (sigma, k) by k-fold CV on images idx
    folds = stratified_folds(y[idx], n_folds, rng)
    scores = {(s, k): cv_accuracy(D_by_sigma[s][np.ix_(idx, idx)], y[idx], k, folds)
              for s in SIGMAS for k in KS}
    best = max(scores, key=scores.get)
    return best, scores[best]

rows = {m: [] for m in ("holdout 20%", "5-fold", "10-fold", "leave-one-out")}
rep = {m: [] for m in ("holdout 20%", "5-fold")}
nest, trues = [], []
for seed in range(40):
    rng = np.random.default_rng(seed)
    X, y = make_images(20, rng)                 # 80 labelled images: all the data we have
    Xf, yf = make_images(1000, rng)             # 4,000 fresh images, never used for any choice
    n = len(y)
    F = {s: features(X, s) for s in SIGMAS}
    Ff = {s: features(Xf, s) for s in SIGMAS}
    D = {s: sqdist(F[s], F[s]) for s in SIGMAS}
    Dfresh = {s: sqdist(Ff[s], F[s]) for s in SIGMAS}

    # Part 1: one fixed classifier (sigma = 1, k = 5). Its true accuracy when trained on all 80.
    s0, k0 = 1, 5
    true = np.mean(knn(Dfresh[s0], y, k0) == yf)
    est = {"holdout 20%": cv_accuracy(D[s0], y, k0, stratified_folds(y, 5, rng)[:1]),  # one fold only
           "5-fold": cv_accuracy(D[s0], y, k0, stratified_folds(y, 5, rng)),
           "10-fold": cv_accuracy(D[s0], y, k0, stratified_folds(y, 10, rng)),
           "leave-one-out": cv_accuracy(D[s0], y, k0, [np.array([i]) for i in range(n)])}
    for m in rows:
        rows[m].append(est[m] - true)
    trues.append(true)
    if seed == 0:                               # same 80 images, 20 different random partitions
        for r in range(20):
            rep["holdout 20%"].append(cv_accuracy(D[s0], y, k0, stratified_folds(y, 5, rng)[:1]))
            rep["5-fold"].append(cv_accuracy(D[s0], y, k0, stratified_folds(y, 5, rng)))

    # Part 2: choose (sigma, k) from 42 settings. Non-nested: report the winner's CV score.
    all_idx = np.arange(n)
    (s_best, k_best), cv_best = select(D, y, all_idx, 5, rng)
    true_sel = np.mean(knn(Dfresh[s_best], y, k_best) == yf)
    # Nested: the selection is repeated inside each outer training set.
    hits = 0
    for te in stratified_folds(y, 5, rng):
        tr = np.setdiff1d(all_idx, te)
        (s, k), _ = select(D, y, tr, 5, rng)
        hits += np.sum(knn(D[s][np.ix_(te, tr)], y[tr], k) == y[te])
    nest.append((cv_best, hits / n, true_sel))

print("Part 1: fixed classifier (blur 1, k = 5), 40 datasets of 80 images")
print(f"true accuracy (4,000 fresh images): {min(trues):.3f}-{max(trues):.3f}")
print("estimator       mean(est - true)  sd(est - true)")
for m, d in rows.items():
    print(f"{m:15s}  {np.mean(d):+.3f}            {np.std(d, ddof=1):.3f}")
for m, a in rep.items():
    print(f"seed 0, 20 repartitions, {m:11s}: {min(a):.3f}-{max(a):.3f} (sd {np.std(a, ddof=1):.3f})")

nest = np.array(nest)
print("\nPart 2: selecting blur and k from 42 settings, 40 datasets")
print(f"non-nested CV score of winner  mean {nest[:, 0].mean():.3f}")
print(f"nested CV estimate             mean {nest[:, 1].mean():.3f}")
print(f"true accuracy of chosen model  mean {nest[:, 2].mean():.3f}")
print(f"optimism, non-nested - true: mean {np.mean(nest[:, 0] - nest[:, 2]):+.3f}, "
      f"positive in {np.sum(nest[:, 0] > nest[:, 2])} of 40")
print(f"error,    nested - true:     mean {np.mean(nest[:, 1] - nest[:, 2]):+.3f}, "
      f"positive in {np.sum(nest[:, 1] > nest[:, 2])} of 40")

# Cross-check the fold construction and the CV score against scikit-learn 1.7.2.
from sklearn.model_selection import KFold, StratifiedKFold, cross_val_score
from sklearn.neighbors import KNeighborsClassifier
rng = np.random.default_rng(0)
X, y = make_images(20, rng)
F1 = features(X, 1)
ours = stratified_folds(y, 5, rng)
theirs = [te for _, te in StratifiedKFold(5, shuffle=True, random_state=0).split(F1, y)]
same_counts = all((np.bincount(y[a], minlength=K) == np.bincount(y[b], minlength=K)).all()
                  for a, b in zip(ours, theirs))
blocks = all((te == b).all() for (_, te), b in zip(KFold(5).split(F1), np.array_split(np.arange(80), 5)))
sk = cross_val_score(KNeighborsClassifier(5), F1, y,
                     cv=[(np.setdiff1d(np.arange(80), te), te) for te in ours]).mean()
print(f"\nper-class counts per fold match StratifiedKFold: {same_counts}; "
      f"KFold without shuffling = consecutive blocks: {blocks}")
print(f"5-fold accuracy, ours {cv_accuracy(sqdist(F1, F1), y, 5, ours):.4f}, scikit-learn {sk:.4f}")

Output:

Part 1: fixed classifier (blur 1, k = 5), 40 datasets of 80 images
true accuracy (4,000 fresh images): 0.560-0.650
estimator       mean(est - true)  sd(est - true)
holdout 20%      -0.013            0.123
5-fold           -0.011            0.063
10-fold          +0.005            0.055
leave-one-out    -0.012            0.054
seed 0, 20 repartitions, holdout 20%: 0.438-0.938 (sd 0.112)
seed 0, 20 repartitions, 5-fold     : 0.575-0.700 (sd 0.040)

Part 2: selecting blur and k from 42 settings, 40 datasets
non-nested CV score of winner  mean 0.664
nested CV estimate             mean 0.597
true accuracy of chosen model  mean 0.595
optimism, non-nested - true: mean +0.069, positive in 35 of 40
error,    nested - true:     mean +0.001, positive in 20 of 40

per-class counts per fold match StratifiedKFold: True; KFold without shuffling = consecutive blocks: True
5-fold accuracy, ours 0.7000, scikit-learn 0.7000

For a fixed classifier none of the four estimators shows a bias that 40 datasets can distinguish from zero; they differ in spread. The holdout estimate rests on 16 images, so its error varies about twice as much as that of 5-fold cross-validation, which scores all 80; more folds help only a little further. On a single dataset, re-drawing which 16 images are held out moves the holdout estimate across a range of 50 points. The partition-to-partition spread of 5-fold is smaller than its error across datasets: repeating cross-validation with new partitions removes the first kind of noise but not the second, which comes from the 80 images themselves.

Selecting among 42 settings changes the picture. The winner’s cross-validation score overstates the chosen model’s accuracy on almost every dataset, because the maximum of 42 noisy estimates is biased upward. The nested estimate, which repeats the selection inside each outer fold, shows no such bias: it is as often too high as too low. The scikit-learn check agrees on fold composition and score.

In scikit-learn

scikit-learn 1.7.2 provides the splitters as classes in sklearn.model_selection: KFold, StratifiedKFold, GroupKFold, StratifiedGroupKFold, LeaveOneOut, LeaveOneGroupOut, RepeatedKFold, RepeatedStratifiedKFold and TimeSeriesSplit. cross_val_score uses 5-fold cross-validation when cv is not given and, for classifiers with binary or multiclass labels, StratifiedKFold; these default splitters do not shuffle, so the folds are the same across calls. KFold and StratifiedKFold also default to shuffle=False, which assigns consecutive blocks of the data, as the check above confirms; the user guide warns that when the data are ordered, for example with images of one class stored together, shuffling first may be essential (scikit-learn 1.7.2 User Guide, §3.1.3).

Variants

• Leave-one-out ($K = n$) trains $n$ models on $n-1$ images each. It has the smallest pessimistic bias and no randomness in the partition, but its variance can be high and it can fail outright: Kohavi (1995) notes that a majority-class predictor on the Iris dataset (50 instances in each of three classes) scores 0% under leave-one-out, since deleting an instance always makes its class the minority, and every fold reports the same 0%, which suggests a stable estimate.
• Repeated k-fold. A single $K$-fold run is one random partition. Kohavi (1995) describes repeating it with different partitions as a better Monte Carlo estimate of complete cross-validation, the average over all possible partitions; the example shows that repetition reduces only the partition part of the variance.
• Stratified k-fold assigns folds within each class so that every fold has approximately the class proportions of the whole set (Kohavi, 1995; scikit-learn’s StratifiedKFold).
• Grouped k-fold and leave-one-group-out. Each group (video, patient, scene, photographer, object instance) goes into exactly one fold, so no group appears on both sides of a split; scikit-learn’s GroupKFold and LeaveOneGroupOut take the group of each image as an argument, and StratifiedGroupKFold also tries to balance the classes. On the UCF50 action dataset, whose clips come in 25 groups, improved dense trajectories were evaluated by leave-one-group-out cross-validation, and the UCF101 article shows how much video-wise rather than group-wise folds inflated a published UCF50 result.
• Time-ordered splits. When the deployed model will see images captured after its training images, the folds must respect time. scikit-learn’s TimeSeriesSplit trains on the first $k$ blocks and tests on block $k+1$, so successive training sets grow, and its gap parameter drops samples between the training and test blocks. For video from a fixed camera, a gap guards against near-identical neighbouring frames on both sides of the boundary (our reasoning).
• Repeated random subsampling (Monte Carlo cross-validation) draws independent random training/test splits rather than a partition, as in the Caltech-101 protocol above; Kohavi (1995) calls it random subsampling and notes a weakness it shares with any single split: because each split divides one dataset, a class over-represented in the training set is under-represented in the test set.
• Nested cross-validation wraps the whole selection procedure, including its own inner cross-validation, inside an outer cross-validation loop that only assesses it. The outer estimate then measures the procedure that will actually be used, selection included. Cawley and Talbot (2010) recommend it under the names nested cross-validation and Stone’s (1974) “double cross”. Nested cross-validation costs roughly the product of the inner and outer numbers of folds times the number of candidate settings, which is why it is mostly seen with cheap models or small grids.

Best Practices

• Use 5- or 10-fold cross-validation as a default, stratified for classification and grouped whenever images share a source.
• Write the whole pipeline as one function or Pipeline that the loop calls, so nothing is fitted outside the folds by accident.
• Repeat cross-validation with several partitions when the estimate decides between close alternatives, and report the spread as partition noise, not as a confidence interval for the error.
• Report the protocol in full (number of folds, stratification, grouping, repetitions, pooled or per-fold averaging), since results under different protocols are not comparable, as Cawley and Talbot’s median protocol shows below.

Pitfalls

• Selecting before cross-validating. Choosing features, a normalization or a hyperparameter on all the images and then cross-validating the rest leaks the held-out folds into the model; the split article gives ESL’s example.
• Reporting the winner’s cross-validation score. The selected configuration’s score is the maximum of many noisy estimates and is biased upward, by about 7 points in the example; Varma and Simon (2006) found the same in microarray data (below).
• Treating the fold scores as independent, which understates the uncertainty (see above).
• Ordered data without shuffling. With images stored class by class, unshuffled folds can hold out whole classes. With images stored in time order, shuffling has the opposite effect, putting near-identical neighbours in training and test.
• Expecting cross-validation to predict performance on new data sources. It estimates error on the distribution the dataset was drawn from. When Recht et al. (2018) collected a new CIFAR-10 test set, a VGG-style model’s accuracy fell from 93.0% on the original test set to 84.9% on the new one, yet five reshuffled cross-validation splits of the original data gave 93.5–94.0%, close to the original test set.

Evidence and Impact

Stone (1974), whose title names cross-validatory choice and assessment, is listed by ESL with Allen (1974) and Stone (1977) as the key references for cross-validation. The rule of thumb of 10 folds rests largely on empirical studies. Kohavi (1995) ran more than half a million runs of the C4.5 decision tree and naive Bayes on six UCI datasets and an artificial dataset with random labels, using the remaining instances of each dataset to estimate the true accuracies: k-fold cross-validation was pessimistically biased, especially with 2 and 5 folds, most estimates were reasonably good at 10 folds and almost unbiased at 20, and stratification gave lower bias and slightly lower variance. He recommended stratified ten-fold cross-validation for model selection, even when more folds are affordable.

The cost of non-nested selection was quantified by Varma and Simon (2006), with synthetic datasets of 40 samples (20 per class) and 6,000 features and no real difference between the two classes, so the true error was 50%. Tuning a shrunken-centroid classifier by 10-fold cross-validation and an SVM by leave-one-out, then reporting the minimum cross-validation error, gave mean estimates of 37.8% and 41.7% (their Table 1). Nesting the tuning inside a leave-one-out outer loop gave 54.2% for the shrunken centroids and 35.3% against a true 32.0% for the SVM on data with a real class difference; the authors attribute the slight pessimism to each outer model being trained on 39 rather than 40 samples.

Cawley and Talbot (2010) showed that the variance of a model-selection criterion leads to overfitting in model selection, with effects often comparable to the differences between learning algorithms. On 13 benchmark datasets they compared selecting kernel ridge regression’s hyperparameters afresh in every train/test realization with the then common protocol of taking the median of the hyperparameters chosen on the first five realizations and reusing them everywhere. The median protocol lowered the error on 11 of the 13 datasets, and with it a Wilcoxon signed-rank test declared the method significantly better than two others that were statistically indistinguishable from it under the unbiased protocol. They concluded that model selection must be treated as part of fitting the model and repeated in every trial.