Editing Cross-validation (statistics) (section)

==Types==
Two types of cross-validation can be distinguished: exhaustive and non-exhaustive cross-validation.

===Exhaustive cross-validation ===
Exhaustive cross-validation methods are cross-validation methods which learn and test on all possible ways to divide the original sample into a training and a validation set.

====Leave-p-out cross-validation====
Leave-''p''-out cross-validation ('''LpO CV''') involves using ''p'' observations as the validation set and the remaining observations as the training set. This is repeated on all ways to cut the original sample on a validation set of ''p'' observations and a training set.<ref>{{cite journal |last1=Celisse |first1=Alain |title=Optimal cross-validation in density estimation with the L<sup>2</sup>-loss |journal=The Annals of Statistics |date=October 2014 |volume=42 |issue=5 |doi=10.1214/14-AOS1240 |arxiv=0811.0802 }}</ref>

LpO cross-validation require training and validating the model <math>C^n_p</math> times, where ''n'' is the number of observations in the original sample, and where <math>C^n_p</math> is the [[binomial coefficient]].  For ''p'' > 1 and for even moderately large ''n'', LpO CV can become computationally infeasible.  For example, with ''n'' = 100 and ''p'' = 30, <math>C^{100}_{30} \approx 3\times 10^{25}.</math>

A variant of LpO cross-validation with p=2 known as leave-pair-out cross-validation has been recommended as a nearly unbiased method for estimating the area under [[ROC curve]] of binary classifiers.<ref>{{cite journal |last1=Airola |first1=Antti |last2=Pahikkala |first2=Tapio |last3=Waegeman |first3=Willem |last4=De Baets |first4=Bernard |last5=Salakoski |first5=Tapio |title=An experimental comparison of cross-validation techniques for estimating the area under the ROC curve |journal=Computational Statistics & Data Analysis |date=April 2011 |volume=55 |issue=4 |pages=1828–1844 |doi=10.1016/j.csda.2010.11.018 }}</ref>

====Leave-one-out cross-validation====<!-- This section is linked from [[Data mining]] -->
[[File:LOOCV.gif|right|thumb|300x300px|Illustration of leave-one-out cross-validation (LOOCV) when n = 8 observations. A total of 8 models will be trained and tested.|alt=]]
Leave-''one''-out cross-validation ('''LOOCV''') is a particular case of leave-''p''-out cross-validation with ''p''&nbsp;=&nbsp;1. The process looks similar to [[Jackknife resampling|jackknife]]; however, with cross-validation one computes a statistic on the left-out sample(s), while with jackknifing one computes a statistic from the kept samples only.

LOO cross-validation requires less computation time than LpO cross-validation because there are only <math>C^n_1=n</math> passes rather than <math>C^n_p</math>. However, <math>n</math> passes may still require quite a large computation time, in which case other approaches such as k-fold cross validation may be more appropriate.<ref>{{cite journal |last1=Molinaro |first1=Annette M. |last2=Simon |first2=Richard |last3=Pfeiffer |first3=Ruth M. |title=Prediction error estimation: a comparison of resampling methods |journal=Bioinformatics |date=August 2005 |volume=21 |issue=15 |pages=3301–3307 |doi=10.1093/bioinformatics/bti499 |pmid=15905277 |doi-access=free }}</ref>

'''Pseudo-code algorithm:'''

'''Input:'''

<code>x</code>, {vector of length <code>N</code> with x-values of incoming points}

<code>y</code>, {vector of length <code>N</code> with y-values of the expected result}

<code>interpolate( x_in, y_in, x_out )</code>, { returns the estimation for point <code>x_out</code> after the model is trained with <code>x_in</code>-<code>y_in</code> pairs}

'''Output:'''

<code>err</code>, {estimate for the prediction error}

'''Steps:'''

  err ← 0
  for i ← 1, ..., N do
    // define the cross-validation subsets
    x_in ← (x[1], ..., x[i − 1], x[i + 1], ..., x[N])
    y_in ← (y[1], ..., y[i − 1], y[i + 1], ..., y[N])
    x_out ← x[i]
    y_out ← interpolate(x_in, y_in, x_out)
    err ← err + (y[i] − y_out)^2
  end for
  err ← err/N

=== Non-exhaustive cross-validation ===
Non-exhaustive cross validation methods do not compute all ways of splitting the original sample. These methods are approximations of leave-''p''-out cross-validation.

====''k''-fold cross-validation====
[[File:KfoldCV.gif|right|thumb|350x350px|Illustration of k-fold cross-validation when n = 12 observations and k = 3. After data is shuffled, a total of 3 models will be trained and tested.]] 
In ''k''-fold cross-validation, the original sample is randomly partitioned into ''k'' equal sized subsamples, often referred to as "folds". Of the ''k'' subsamples, a single subsample is retained as the validation data for testing the model, and the remaining ''k''&nbsp;−&nbsp;1 subsamples are used as training data. The cross-validation process is then repeated ''k'' times, with each of the ''k'' subsamples used exactly once as the validation data.  The ''k'' results can then be averaged to produce a single estimation. The advantage of this method over repeated random sub-sampling  (see below) is that all observations are used for both training and validation, and each observation is used for validation exactly once. 10-fold cross-validation is commonly used,<ref name="McLachlan">{{cite book |doi=10.1002/047172842X |title=Analyzing Microarray Gene Expression Data |series=Wiley Series in Probability and Statistics |date=2004 |publisher=Wiley |isbn=978-0-471-22616-1 }}{{pn|date=November 2024}}</ref> but in general ''k'' remains an unfixed parameter.

For example, setting ''k''&nbsp;=&nbsp;''2'' results in 2-fold cross-validation. In 2-fold cross-validation, we randomly shuffle the dataset into two sets ''d''<sub>0</sub> and ''d''<sub>1</sub>, so that both sets are equal size (this is usually implemented by shuffling the data array and then splitting it in two). We then train on ''d''<sub>0</sub> and validate on ''d''<sub>1</sub>, followed by training on ''d''<sub>1</sub> and validating on&nbsp;''d''<sub>0</sub>.

When ''k''&nbsp;=&nbsp;''n'' (the number of observations), ''k''-fold cross-validation is equivalent to leave-one-out cross-validation.<ref>{{cite book |doi=10.1007/978-0-387-84858-7 |title=The Elements of Statistical Learning |series=Springer Series in Statistics |date=2009 |isbn=978-0-387-84857-0 }}{{pn|date=November 2024}}</ref>

In ''stratified'' ''k''-fold cross-validation, the partitions are selected so that the mean response value is approximately equal in all the partitions.  In the case of binary classification, this means that each partition contains roughly the same proportions of the two types of class labels.

In ''repeated'' cross-validation the data is randomly split into ''k'' partitions several times. The performance of the model can thereby be averaged over several runs, but this is rarely desirable in practice.<ref>{{cite book |last1=Vanwinckelen |first1=Gitte |last2=Blockeel |first2=Hendrik |chapter=On Estimating Model Accuracy with Repeated Cross-Validation |pages=39–44 |chapter-url=https://lirias.kuleuven.be/retrieve/186558 |date=2012 |title=BeneLearn 2012: Proceedings of the 21st Belgian-Dutch Conference on Machine Learning |isbn=978-94-6197-044-2 }}</ref>

When many different statistical or [[Machine learning#Models|machine learning models]] are being considered, ''greedy'' ''k''-fold cross-validation can be used to quickly identify the most promising candidate models.<ref name="soper">{{cite journal |last1=Soper |first1=Daniel S. |title=Greed Is Good: Rapid Hyperparameter Optimization and Model Selection Using Greedy k-Fold Cross Validation |journal=Electronics |date=16 August 2021 |volume=10 |issue=16 |pages=1973 |doi=10.3390/electronics10161973 |doi-access=free }}</ref>

====Holdout method====

In the holdout method, we randomly assign data points to two sets ''d''<sub>0</sub> and ''d''<sub>1</sub>, usually called the training set and the test set, respectively. The size of each of the sets is arbitrary although typically the test set is smaller than the training set. We then train (build a model) on ''d''<sub>0</sub> and test (evaluate its performance) on ''d''<sub>1</sub>.

In typical cross-validation, results of multiple runs of model-testing are averaged together; in contrast, the holdout method, in isolation, involves a single run. It should be used with caution because without such averaging of multiple runs, one may achieve highly misleading results. One's indicator of predictive accuracy ([[#Statistical properties|''F''<sup>*</sup>]]) will tend to be unstable since it will not be smoothed out by multiple iterations (see below).  Similarly, indicators of the specific role played by various predictor variables (e.g., values of regression coefficients) will tend to be unstable.

While the holdout method can be framed as "the simplest kind of cross-validation",<ref>{{cite web|title=Cross Validation|url=https://www.cs.cmu.edu/~schneide/tut5/node42.html|access-date=11 November 2012}}{{self-published inline|date=November 2024}}</ref> many sources instead classify holdout as a type of simple validation, rather than a simple or degenerate form of cross-validation.<ref name="Kohavi95" /><ref>{{cite journal |last1=Arlot |first1=Sylvain |first2=Alain |last2=Celisse |title=A survey of cross-validation procedures for model selection |journal=Statistics Surveys |volume=4 |year=2010 |pages=40–79 |quote=In brief, CV consists in averaging several hold-out estimators of the risk corresponding to different data splits. |doi=10.1214/09-SS054 |arxiv=0907.4728 }}</ref>

====Repeated random sub-sampling validation====

This method, also known as [[Monte Carlo method|Monte Carlo]] cross-validation,<ref>{{cite journal |last1=Xu |first1=Qing-Song |last2=Liang |first2=Yi-Zeng |title=Monte Carlo cross validation |journal=Chemometrics and Intelligent Laboratory Systems |date=April 2001 |volume=56 |issue=1 |pages=1–11 |doi=10.1016/S0169-7439(00)00122-2 }}</ref><ref name="mccv">{{cite book |doi=10.1007/978-0-387-47509-7_8 |chapter=Resampling Strategies for Model Assessment and Selection |title=Fundamentals of Data Mining in Genomics and Proteomics |date=2007 |last1=Simon |first1=Richard |pages=173–186 |isbn=978-0-387-47508-0 }}</ref> creates multiple random splits of the dataset into training and validation data.<ref>{{cite book |doi=10.1007/978-1-4614-6849-3 |title=Applied Predictive Modeling |date=2013 |last1=Kuhn |first1=Max |last2=Johnson |first2=Kjell |isbn=978-1-4614-6848-6 }}{{pn|date=November 2024}}</ref> For each such split, the model is fit to the training data, and predictive accuracy is assessed using the validation data. The results are then averaged over the splits. The advantage of this method (over ''k''-fold cross validation) is that the proportion of the training/validation split is not dependent on the number of iterations (i.e., the number of partitions). The disadvantage of this method is that some observations may never be selected in the validation subsample, whereas others may be selected more than once. In other words, validation subsets may overlap. This method also exhibits [[Monte Carlo method|Monte Carlo]] variation, meaning that the results will vary if the analysis is repeated with different random splits.

As the number of random splits approaches infinity, the result of repeated random sub-sampling validation tends towards that of leave-p-out cross-validation.

In a stratified variant of this approach, the random samples are generated in such a way that the mean response value (i.e. the dependent variable in the regression) is equal in the training and testing sets. This is particularly useful if the responses are [[dichotomous]] with an unbalanced representation of the two response values in the data.

A method that applies repeated random sub-sampling is [[RANSAC]].<ref>{{cite report |last1=Cantzler |first1=H |title=Random Sample Consensus (RANSAC) |url=https://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/CANTZLER2/ransac.pdf }}{{self-published inline|date=November 2024}}</ref>