Cross-validation

Section of Estimating error rates, part of Statistical learning

Cross-validation

Type Section
Taught in Estimating error rates
Part Statistical learning
Questions using it 11

A single holdout spends some cases on testing and never uses them for training, and it spends the rest on training and never uses them for testing. When the labelled sample is small, that unused half is the difficulty. Cross-validation still partitions the data into a training piece and a test piece and counts errors. It then repeats the partition so that every case is held out once. The rule scored in each repetition is the rule trained without that case.

Leave-one-out

Main article: Leave-one-out cross-validation

The smallest holdout that still keeps the test case out of the fit leaves out one observation and trains on the other n-1. Repeating this once for each observation uses every case as a test case and almost every case, each time, as a training case.

Definition 1 (Leave-one-out cross-validation) \widehat{\mathrm{Err}}_{\mathrm{LOOCV}} =\frac1n\sum_{i=1}^n Q\bigl(y_i,\eta_{(X_{-i},y_{-i})}(x_i)\bigr),

where -i means that observation i is left out of the fit that is then scored on x_i. The class-specific estimator restricts the average to class g,

\widehat{\mathrm{Err}}_{\mathrm{LOOCV},g} =\frac{\sum_{i=1}^n Q\bigl(y_i,\eta_{(X_{-i},y_{-i})}(x_i)\bigr)\,I(y_i,g)} {\sum_{l=1}^n I(y_l,g)}.

Article: Leave-one-out cross-validation →

Leave-one-out trains on almost as many observations as the final fit. That reduces the difference in training size. It does not make the error indicators independent. Two training sets share n-2 observations, and both depend on the same original sample. A binomial standard error applied to the n leave-one-out errors would ignore this dependence.

A useful check is to ask what changes between repetitions. In leave-one-out, the held-out case changes, and almost the entire training sample stays the same. Repeating the same leave-one-out calculation cannot reveal the variability between genuinely new datasets. More fitting is not automatically more independent evidence.

K-fold cross-validation

Main article: -fold cross-validation

Leave-one-out refits the model n times, and its training sets are almost copies of one another. Geisser’s K-fold cross-validation spends more cases on each test and refits only K times. About n/K observations, a fold, are held out at each iteration. The folds do not overlap, and after K iterations every observation has been tested once.

Definition 2 (K-fold cross-validation) \widehat{\mathrm{Err}}_{\mathrm{KCV}} =\frac1n\sum_{k=1}^{K}\sum_{i=1}^{n_k} Q\bigl(y_i^{(k)},\eta_{(X^{(-k)},y^{(-k)})}(x_i^{(k)})\bigr).

Here n_k is the size of fold k, and (-k) denotes the fit that excludes that fold. Pooling individual errors gives each observation equal weight even if the fold sizes differ.

Article: -fold cross-validation →

In five-fold cross-validation the five blocks rotate through validation:

round block 1 block 2 block 3 block 4 block 5
1 validate fit fit fit fit
2 fit validate fit fit fit
3 fit fit validate fit fit
4 fit fit fit validate fit
5 fit fit fit fit validate

Every observation is used once for validation and four times for fitting. Preprocessing belongs inside each fit, so a held-out block does not help to set a mean, a standard deviation, or a tuning constant.

Increasing K enlarges each training set and increases computation. Its effect on variance is problem-dependent. Overlap of the training sets does not, by itself, prove a universal ordering of cross-validation variances. Five or ten folds are a usual compromise between training size and fitting cost. Repeating the random partition can show sensitivity to the split and can reduce that component of variation. It does not create new observations. Once the data are fixed, leave-one-out has no partition randomness to average away.

Stratification keeps class proportions approximately balanced across folds when the counts permit it. This can prevent a rare class from disappearing from a training set. One observation in a class cannot appear in every training set while also being held out. Check the actual fold counts rather than assuming that the name of a resampling method has solved the problem.

Repeated K-fold validation and repeated random holdout reuse observations in different ways. Their relative performance depends on the estimator and on the data-generating setting. No repeated scheme is uniformly better. Choose the design for the assessment target and for the computation that is available.

Nested cross-validation

Main article: Nested cross-validation

Cross-validation as written above estimates the error of a rule whose form is already fixed. Choosing a tuning constant \lambda by the same errors, and then reporting the smallest of those errors as the error of the chosen rule, uses each case twice: once to pick \lambda, and again to advertise the pick. The advertised number is optimistically biased.

As a numerical sketch, the test errors across \lambda=1,\ldots,10 may have a best value of 0.18. That 0.18 was the criterion that selected \lambda, so among noisy estimates it is the one that fell furthest below the truth. A validation set may choose \lambda. A test set that did not enter the choice estimates the error. The optimism is a tendency over repeated samples, not an inequality that every split obeys: one test score can still come out smaller than the selected validation score. Nested cross-validation is this separation when the sample is too small for three permanent blocks.

Nested cross-validation places the complete selection procedure inside an outer assessment loop. This is the separation studied by Cawley and Talbot (2010). The inner winner can differ between outer folds. In the construction below, the remaining m-1 outer folds also serve as inner folds.

  1. Split the data into m folds. Of those, m-2 are for training, one is for validation, and one is for testing.
  2. Using the training and validation data, perform (m-1)-fold cross-validation for each candidate k=1,\ldots,K. Estimate the overall error for each k from the cross-validation results, and choose the k that gives the lowest error rate.
  3. With this k=k_1^*, train the classifier on the training and validation data and test it on the test fold.
  4. Repeat for the other choices of test fold, m times in all, getting possibly different values k_2^*,\ldots,k_m^* each time. Average the results to estimate the error rate of the procedure on future observations.
  5. For the final classifier, choose a new k=k_{\mathrm{final}}^* by a similar procedure that uses only training and validation, with no test fold held out of the selection.
  6. Train the final classifier on all the data using k=k_{\mathrm{final}}^*.

The cases that select k are not the cases that assess the selected model. If one cross-validation error both picks the best of many candidates and is then reported as that candidate’s accuracy, the report is optimistic, because the minimum of many noisy estimates is systematically one of the estimates that happened to be low. Step 5 rebuilds the choice of k without a test fold, and step 6 trains the final classifier on every observation at that chosen k. The nested average estimates the error of this whole procedure, including the selection, not the error of whichever k looked best inside one split.

The same pattern appears when k for nearest neighbours is chosen on one sample and then scored on another. Training error falls toward zero as k falls to 1. A ten-fold cross-validation curve, and the error on a large independent draw, stay above that training curve and prefer a larger neighbourhood. The laboratory at the end of this page is that separation on a small scale.

Used in

See also

-fold cross-validation · Leave-one-out cross-validation · Nested cross-validation · Cross-validation of the likelihood · Bootstrap error and the correction · Cost-complexity pruning · Fixed-rule error · Confusion matrix

Glossary and index