Editing Cross-validation (statistics)

{{short description|Statistical model validation technique}}
{{More citations needed|date=August 2017}}
[[File:Confusion matrix.png|thumb|250x250px|Comparing the cross-validation accuracy and percent of false negative (overestimation) of five classification models. Size of bubbles represent the standard deviation of cross-validation accuracy (tenfold).<ref name=":1">{{cite journal |last1=Piryonesi |first1=S. Madeh |last2=El-Diraby |first2=Tamer E. |title=Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index |journal=Journal of Infrastructure Systems |date=March 2020 |volume=26 |issue=1 |doi=10.1061/(ASCE)IS.1943-555X.0000512 }}</ref>]]
[[File:K-fold cross validation EN.svg|thumb|250px|right|Diagram of k-fold cross-validation]]

'''Cross-validation''',<ref>{{cite journal |last=Allen | first=David M |year=1974 |title=The Relationship between Variable Selection and Data Agumentation and a Method for Prediction |journal=Technometrics |volume=16 |issue=1 |pages=125–127 |doi=10.2307/1267500 |jstor=1267500 }}</ref><ref>{{cite journal |last1=Stone |first1=M. |title=Cross-Validatory Choice and Assessment of Statistical Predictions |journal=Journal of the Royal Statistical Society Series B: Statistical Methodology |date=1974 |volume=36 |issue=2 |pages=111–133 |doi=10.1111/j.2517-6161.1974.tb00994.x }}</ref><ref>{{cite journal |last=Stone | first=M |year=1977 |title=An Asymptotic Equivalence of Choice of Model by Cross-Validation and Akaike's Criterion |journal=Journal of the Royal Statistical Society, Series B (Methodological) |volume=39 |issue=1 |pages=44–47 | doi=10.1111/j.2517-6161.1977.tb01603.x | jstor=2984877 }}</ref> sometimes called '''rotation estimation'''<ref>{{cite book |last=Geisser |first=Seymour |year=1993 |title=Predictive Inference |publisher=Chapman and Hall |location=New York, NY |isbn=978-0-412-03471-8 }}{{pn|date=November 2024}}</ref><ref name="Kohavi95">{{cite book |last1=Kohavi |first1=Ron |chapter=A study of cross-validation and bootstrap for accuracy estimation and model selection |pages=1137–1143 |chapter-url=https://www.ijcai.org/Proceedings/95-2/Papers/016.pdf |title=Proceedings of the 14th international joint conference on Artificial intelligence |volume=2 |date=20 August 1995 |publisher=Morgan Kaufmann Publishers |isbn=978-1-55860-363-9 }}</ref><ref name="Devijver82">{{cite book | last1 = Devijver | first1 = Pierre A. | last2 = Kittler | first2 = Josef | title = Pattern Recognition: A Statistical Approach | publisher = Prentice-Hall | location = London, GB | date = 1982 |isbn=978-0-13-654236-0 }}{{pn|date=November 2024}}</ref> or '''out-of-sample testing''', is any of various similar [[model validation]] techniques for assessing how the results of a [[statistics|statistical]] analysis will [[Generalization error|generalize]] to an independent data set.
Cross-validation includes [[Resampling (statistics)|resampling]] and sample splitting methods that use different portions of the data to test and train a model on different iterations. It is often used in settings where the goal is prediction, and one wants to estimate how [[accuracy|accurately]] a [[predictive modelling|predictive model]] will perform in practice. It can also be used to assess the quality of a fitted model and the stability of its parameters.

In a prediction problem, a model is usually given a dataset of ''known data'' on which training is run (''training dataset''), and a dataset of ''unknown data'' (or ''first seen'' data) against which the model is tested (called the [[validation set|validation dataset]] or ''testing set'').<ref>{{cite web |title= What is the difference between test set and validation set? |url=https://stats.stackexchange.com/q/19051 |website=Cross Validated |publisher=Stack Exchange |first=Alexander |last=Galkin |date=November 28, 2011 |access-date=10 October 2018}}</ref><ref name="Newbie question: Confused about train, validation and test data!">{{cite web|url=http://www.heatonresearch.com/node/1823 |title=Newbie question: Confused about train, validation and test data! |date=December 2010 |website=Heaton Research  |access-date=2013-11-14 |url-status=dead |archive-url=https://web.archive.org/web/20150314221014/http://www.heatonresearch.com/node/1823 |archive-date=2015-03-14 }}{{self-published inline|date=November 2024}}</ref> The goal of cross-validation is to test the model's ability to predict new data that was not used in estimating it, in order to flag problems like [[overfitting]] or [[selection bias]]<ref>{{cite journal |last1=Cawley |first1=Gavin C. |last2=Talbot |first2=Nicola L. C. |title=On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation |journal=Journal of Machine Learning Research |volume=11 |date=2010 |pages=2079–2107 |url=https://www.jmlr.org/papers/volume11/cawley10a/cawley10a.pdf }}</ref> and to give an insight on how the model will generalize to an independent dataset (i.e., an unknown dataset, for instance from a real problem).

One round of cross-validation involves [[partition of a set|partitioning]] a [[statistical sample|sample]] of [[data]] into [[Complement (set theory)|complementary]] subsets, performing the analysis on one subset (called the ''training set''), and validating the analysis on the other subset (called the ''validation set'' or ''testing set''). To reduce [[variance|variability]], in most methods multiple rounds of cross-validation are performed using different partitions, and the validation results are combined (e.g. averaged) over the rounds to give an estimate of the model's predictive performance.

In summary, cross-validation combines (averages) measures of [[Goodness of fit|fitness]] in prediction to derive a more accurate estimate of model prediction performance.<ref>{{cite journal |last1=Seni |first1=Giovanni |last2=Elder |first2=John F. |title=Ensemble Methods in Data Mining: Improving Accuracy Through Combining Predictions |journal=Synthesis Lectures on Data Mining and Knowledge Discovery |date=January 2010 |volume=2 |issue=1 |pages=1–126 |doi=10.2200/S00240ED1V01Y200912DMK002 }}</ref>

==Motivation==

Assume a [[statistical model|model]] with one or more unknown [[parameters]], and a data set to which the model can be fit (the training data set). The fitting process [[optimization (mathematics)|optimizes]] the model parameters to make the model fit the training data as well as possible. If an [[independence (probability theory)|independent]] sample of validation data is taken from the same [[statistical population|population]] as the training data, it will generally turn out that the model does not fit the validation data as well as it fits the training data. The size of this difference is likely to be large especially when the size of the training data set is small, or when the number of parameters in the model is large. Cross-validation is a way to estimate the size of this effect.{{fact|date=November 2024}}

===Example: linear regression ===
In linear regression, there exist [[real number|real]] ''response values'' <math display="inline">y_1,\ldots, y_n </math>, and ''n'' ''p''-dimensional [[Euclidean vector|vector]] ''covariates'' '''''x'''''<sub>1</sub>, ..., '''''x'''''<sub>''n''</sub>.  The components of the vector '''''x'''''<sub>''i''</sub> are denoted ''x''<sub>''i''1</sub>, ..., ''x''<sub>''ip''</sub>. If [[least squares]] is used to fit a function in the form of a [[hyperplane]] '''''ŷ''''' = ''a'' + '''''β'''''<sup>T</sup>'''''x''''' to the data ('''''x'''''<sub>''i''</sub>, ''y''<sub>''i''</sub>)<sub>&nbsp;1&nbsp;≤&nbsp;''i''&nbsp;≤&nbsp;''n''</sub>, then the fit can be assessed using the [[mean squared error]] (MSE). The MSE for given estimated parameter values ''a'' and '''''β''''' on the training set ('''''x'''''<sub>''i''</sub>, ''y''<sub>''i''</sub>)<sub>&nbsp;1&nbsp;≤&nbsp;''i''&nbsp;≤&nbsp;''n''</sub> is defined as:

:<math>\begin{align}
\text{MSE} &= \frac 1 n \sum_{i=1}^n (y_i - \hat{y}_i)^2 = \frac 1 n \sum_{i=1}^n (y_i - a - \boldsymbol\beta^T \mathbf{x}_i)^2\\&= \frac{1}{n}\sum_{i=1}^n (y_i - a - \beta_1x_{i1} - \dots - \beta_px_{ip})^2
\end{align}</math>

If the model is correctly specified, it can be shown under mild assumptions that the [[expected value]] of the MSE for the training set is (''n''&nbsp;&minus;&nbsp;''p''&nbsp;&minus;&nbsp;1)/(''n''&nbsp;+&nbsp;''p''&nbsp;+&nbsp;1)&nbsp;<&nbsp;1 times the expected value of the MSE for the validation set (the expected value is taken over the distribution of training sets).  Thus, a fitted model and computed MSE on the training set will result in an optimistically [[bias (statistics)|biased]] assessment of how well the model will fit an independent data set.  This biased estimate is called the ''in-sample'' estimate of the fit, whereas the cross-validation estimate is an ''out-of-sample'' estimate.{{fact|date=November 2024}}

Since in linear regression it is possible to directly compute the factor (''n''&nbsp;&minus;&nbsp;''p''&nbsp;&minus;&nbsp;1)/(''n''&nbsp;+&nbsp;''p''&nbsp;+&nbsp;1) by which the training MSE underestimates the validation MSE under the assumption that the model specification is valid, cross-validation can be used for checking whether the model has been [[overfitting|overfitted]], in which case the MSE in the validation set will substantially exceed its anticipated value. (Cross-validation in the context of linear regression is also useful in that it can be used to select an optimally [[Regularization (mathematics)|regularized]] [[Loss function|cost function]].)

=== General case===
In most other regression procedures (e.g. [[logistic regression]]), there is no simple formula to compute the expected out-of-sample fit. Cross-validation is, thus, a generally applicable way to predict the performance of a model on unavailable data using numerical computation in place of theoretical analysis.

==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>

==Nested cross-validation==

When cross-validation is used simultaneously for selection of the best set of [[Hyperparameter (machine learning)|hyperparameters]] and for error estimation (and assessment of generalization capacity), a nested cross-validation is required. Many variants exist. At least two variants can be distinguished:

===k*l-fold cross-validation===

This is a truly nested variant which contains an outer loop of ''k'' sets and an inner loop of ''l'' sets. The total data set is split into ''k'' sets. One by one, a set is selected as the (outer) test set and the ''k''&nbsp;-&nbsp;1 other sets are combined into the corresponding outer training set. This is repeated for each of the ''k'' sets. Each outer training set is further sub-divided into ''l'' sets.  One by one, a set is selected as inner test (validation) set and the ''l''&nbsp;-&nbsp;1 other sets are combined into the corresponding inner training set. This is repeated for each of the ''l'' sets. The inner training sets are used to fit model parameters, while the outer test set is used as a validation set to provide an unbiased evaluation of the model fit. Typically, this is repeated for many different hyperparameters (or even different model types) and the validation set is used to determine the best hyperparameter set (and model type) for this inner training set. After this, a new model is fit on the entire outer training set, using the best set of hyperparameters from the inner cross-validation. The performance of this model is then evaluated using the outer test set.

===k-fold cross-validation with validation and test set===

This is a type of k*l-fold cross-validation when ''l''&nbsp;=&nbsp;''k''&nbsp;-&nbsp;1. A single k-fold cross-validation is used with both a [[Training, validation, and test sets|validation and test set]]. The total data set is split into ''k'' sets. One by one, a set is selected as test set. Then, one by one, one of the remaining sets is used as a validation set and the other ''k''&nbsp;-&nbsp;2 sets are used as training sets until all possible combinations have been evaluated. Similar to the k*l-fold cross validation, the training set is used for model fitting and the validation set is used for model evaluation for each of the hyperparameter sets. Finally, for the selected parameter set, the test set is used to evaluate the model with the best parameter set. Here, two variants are possible: either evaluating the model that was trained on the training set or evaluating a new model that was fit on the combination of the training and the validation set.

==Measures of fit==

The goal of cross-validation is to estimate the expected level of fit of a model to a data set that is independent of the data that were used to train the model.  It can be used to estimate any quantitative measure of fit that is appropriate for the data and model.  For example, for [[binary classification]] problems, each case in the validation set is either predicted correctly or incorrectly. In this situation the misclassification error rate can be used to summarize the fit, although other measures derived from information (e.g., counts, frequency) contained within a [[contingency table]] or [[confusion matrix]] could also be used.  When the value being predicted is continuously distributed, the [[mean squared error]], [[root mean squared error]] or [[median absolute deviation]] could be used to summarize the errors.

==Using prior information==
When users apply cross-validation to select a good configuration <math>\lambda</math>, then they might want to balance the cross-validated choice with their own estimate of the configuration. In this way, they can attempt to counter the volatility of cross-validation when the sample size is small and include relevant information from previous research. In a forecasting combination exercise, for instance, cross-validation can be applied to estimate the weights that are assigned to each forecast. Since a simple equal-weighted forecast is difficult to beat, a penalty can be added for deviating from equal weights.<ref name="Hoornweg2018SUS">{{cite book |last1=Hoornweg |first1=Victor |title=Science: Under Submission | date=2018 |publisher=Hoornweg Press |isbn=978-90-829188-0-9 |url=https://victorhoornweg.com/docs/Hoornweg%202018%20Science%20Under%20Submission.pdf }}{{pn|date=November 2024}}{{self-published inline|date=November 2024}}</ref>  Or, if cross-validation is applied to assign individual weights to observations, then one can penalize deviations from equal weights to avoid wasting potentially relevant information.<ref name = "Hoornweg2018SUS" />  Hoornweg (2018) shows how a tuning parameter <math>\gamma</math> can be defined so that a user can intuitively balance between the accuracy of cross-validation and the simplicity of sticking to a reference parameter <math>\lambda_R</math> that is defined by the user.

If <math>\lambda_i</math> denotes the <math>i^{th}</math> candidate configuration that might be selected, then the [[Loss function#Statistics|loss function]] that is to be minimized can be defined as
: <math>
	L_{\lambda_i} = (1-\gamma) \mbox{ Relative Accuracy}_i + \gamma \mbox{ Relative Simplicity}_i.
</math>
Relative accuracy can be quantified as <math>\mbox{MSE}(\lambda_i)/\mbox{MSE}(\lambda_R)</math>, so that the mean squared error of a candidate  <math>\lambda_i</math> is made relative to that of a user-specified <math>\lambda_R</math>. The relative simplicity term measures the amount that <math>\lambda_i</math> deviates from <math>\lambda_R</math> relative to the maximum amount of deviation from <math>\lambda_R</math>. Accordingly, relative simplicity can be specified as <math>\frac{(\lambda_i-\lambda_R)^2}{(\lambda_{\max}-\lambda_R)^2}</math>, where <math>\lambda_{\max}</math> corresponds to the <math>\lambda</math> value with the highest permissible deviation from <math>\lambda_R</math>. With <math>\gamma\in[0,1]</math>, the user determines how high the influence of the reference parameter is relative to cross-validation.

One can add relative simplicity terms for multiple configurations <math>c=1,2,...,C</math> by specifying the loss function as
: <math>
	L_{\lambda_i} = \mbox{ Relative Accuracy}_i + \sum_{c=1}^C \frac{\gamma_c}{1-\gamma_c} \mbox{ Relative Simplicity}_{i,c}.
</math>
Hoornweg (2018) shows that a loss function with such an accuracy-simplicity tradeoff can also be used to intuitively define [[shrinkage estimator]]s like the (adaptive) lasso and [[Bayesian regression|Bayesian]] / [[ridge regression]].<ref name = "Hoornweg2018SUS" /> Click on the [[Lasso (statistics)#Interpretations of lasso|lasso]] for an example.

==Statistical properties==
{{see also|bias-variance tradeoff}}
Suppose we choose a measure of fit ''F'', and use cross-validation to produce an estimate ''F<sup>*</sup>'' of the expected fit ''EF'' of a model to an independent data set drawn from the same population as the training data. If we imagine sampling multiple independent training sets following the same distribution, the resulting values for ''F<sup>*</sup>'' will vary. The statistical properties of ''F<sup>*</sup>'' result from this variation.

The variance of ''F<sup>*</sup>'' can be large.<ref name="Efron97">{{cite journal |last1=Efron |first1=Bradley |last2=Tibshirani |first2=Robert |year=1997 |title=Improvements on cross-validation: The .632 + Bootstrap Method |journal=[[Journal of the American Statistical Association]] |volume=92 |pages=548–560 |mr=1467848 |jstor=2965703 |doi=10.2307/2965703 |issue=438 }}</ref><ref name="Stone77">{{cite journal |last=Stone |first=Mervyn |year=1977 |title=Asymptotics for and against cross-validation |journal=[[Biometrika]] |volume=64 |number=1 |pages=29–35 |doi=10.1093/biomet/64.1.29 |mr=0474601 |jstor=2335766 }}</ref> For this reason, if two statistical procedures are compared based on the results of cross-validation, the procedure with the better estimated performance may not actually be the better of the two procedures (i.e. it may not have the better value of ''EF'').  Some progress has been made on constructing [[confidence interval]]s around cross-validation estimates,<ref name="Efron97" /> but this is considered a difficult problem.

==Computational issues==

Most forms of cross-validation are straightforward to implement as long as an implementation of the prediction method being studied is available.  In particular, the prediction method can be a "black box" – there is no need to have access to the internals of its implementation.  If the prediction method is expensive to train, cross-validation can be very slow since the training must be carried out repeatedly.  In some cases such as [[least squares]] and [[kernel regression]], cross-validation can be sped up significantly by pre-computing certain values that are needed repeatedly in the training, or by using fast "updating rules" such as the [[Sherman–Morrison formula]].  However one must be careful to preserve the "total blinding" of the validation set from the training procedure, otherwise bias may result.  An extreme example of accelerating cross-validation occurs in [[linear regression]], where the results of cross-validation have a [[closed-form expression]] known as the ''prediction residual error sum of squares'' ([[PRESS statistic|PRESS]]).

==Limitations and misuse==

Cross-validation only yields meaningful results if the validation set and training set are drawn from the same population and only if human biases are controlled.

In many applications of predictive modeling, the structure of the system being studied evolves over time (i.e. it is "non-stationary").  Both of these can introduce systematic differences between the training and validation sets.  For example, if a model for prediction of trend changes in financial quotations is trained on data for a certain five-year period, it is unrealistic to treat the subsequent five-year period as a draw from the same population.  As another example, suppose a model is developed to predict an individual's risk for being [[medical diagnosis|diagnosed]] with a particular disease within the next year.  If the model is trained using data from a study involving only a specific population group (e.g. young people or males), but is then applied to the general population, the cross-validation results from the training set could differ greatly from the actual predictive performance.

In many applications, models also may be incorrectly specified and vary as a function of modeler biases and/or arbitrary choices. When this occurs, there may be an illusion that the system changes in external samples, whereas the reason is that the model has missed a critical predictor and/or included a confounded predictor.   New evidence is that cross-validation by itself is not very predictive of external validity, whereas a form of experimental validation known as swap sampling that does control for human bias can be much more predictive of external validity.<ref>{{cite journal |doi=10.1038/nbt.1665 |title=The MicroArray Quality Control (MAQC)-II study of common practices for the development and validation of microarray-based predictive models |journal=Nature Biotechnology |date=2010 |volume=28 |issue=8 |pages=827–838 |pmid=20676074 |last1=Shi |first1=L. |last2=Campbell |first2=G. |last3=Jones |first3=W. D. |last4=Campagne |first4=F. |last5=Wen |first5=Z. |last6=Walker |first6=S. J. |last7=Su |first7=Z. |last8=Chu |first8=T. M. |last9=Goodsaid |first9=F. M. |last10=Pusztai |first10=L. |last11=Shaughnessy Jr |first11=J. D. |last12=Oberthuer |first12=A. |last13=Thomas |first13=R. S. |last14=Paules |first14=R. S. |last15=Fielden |first15=M. |last16=Barlogie |first16=B. |last17=Chen |first17=W. |last18=Du |first18=P. |last19=Fischer |first19=M. |last20=Furlanello |first20=C. |last21=Gallas |first21=B. D. |last22=Ge |first22=X. |last23=Megherbi |first23=D. B. |last24=Symmans |first24=W. F. |last25=Wang |first25=M. D. |last26=Zhang |first26=J. |last27=Bitter |first27=H. |last28=Brors |first28=B. |last29=Bushel |first29=P. R. |last30=Bylesjo |first30=M. |pmc=3315840 |display-authors=1 }}</ref>  As defined by this large MAQC-II study across 30,000 models, swap sampling incorporates cross-validation in the sense that predictions are tested across independent training and validation samples. Yet, models are also developed across these independent samples and by modelers who are blinded to one another.  When there is a mismatch in these models developed across these swapped training and validation samples as happens quite frequently, MAQC-II shows that this will be much more predictive of poor external predictive validity than traditional cross-validation.

The reason for the success of the swapped sampling is a built-in control for human biases in model building.  In addition to placing too much faith in predictions that may vary across modelers and lead to poor external validity due to these confounding modeler effects, these are some other ways that cross-validation can be misused:

* By performing an initial analysis to identify the most informative [[features (pattern recognition)|features]] using the entire data set – if feature selection or model tuning is required by the modeling procedure, this must be repeated on every training set. Otherwise, predictions will certainly be upwardly biased.<ref name="Bermingham-intro">{{cite journal |last1=Bermingham |first1=M. L. |last2=Pong-Wong |first2=R. |last3=Spiliopoulou |first3=A. |last4=Hayward |first4=C. |last5=Rudan |first5=I. |last6=Campbell |first6=H. |last7=Wright |first7=A. F. |last8=Wilson |first8=J. F. |last9=Agakov |first9=F. |last10=Navarro |first10=P. |last11=Haley |first11=C. S. |title=Application of high-dimensional feature selection: evaluation for genomic prediction in man |journal=Scientific Reports |date=19 May 2015 |volume=5 |issue=1 |page=10312 |doi=10.1038/srep10312 |pmid=25988841 |pmc=4437376 |bibcode=2015NatSR...510312B }}</ref>  If cross-validation is used to decide which features to use, an ''inner cross-validation'' to carry out the feature selection on every training set must be performed.<ref>{{cite journal |last1=Varma |first1=Sudhir |last2=Simon |first2=Richard |title=Bias in error estimation when using cross-validation for model selection |journal=BMC Bioinformatics |date=December 2006 |volume=7 |issue=1 |page=91 |doi=10.1186/1471-2105-7-91 |pmid=16504092 |pmc=1397873 |doi-access=free }}</ref>
* Performing mean-centering, rescaling, dimensionality reduction, outlier removal or any other data-dependent preprocessing using the entire data set. While very common in practice, this has been shown to introduce biases into the cross-validation estimates.<ref>{{cite journal |last1=Moscovich |first1=Amit |last2=Rosset |first2=Saharon |title=On the Cross-Validation Bias due to Unsupervised Preprocessing |journal=Journal of the Royal Statistical Society Series B: Statistical Methodology |date=September 2022 |volume=84 |issue=4 |pages=1474–1502 |doi=10.1111/rssb.12537 |arxiv=1901.08974 }}</ref>
* By allowing some of the training data to also be included in the test set – this can happen due to "twinning" in the data set, whereby some exactly identical or nearly identical samples are present in the data set, see [[pseudoreplication]]. To some extent twinning always takes place even in perfectly independent training and validation samples. This is because some of the training sample observations will have nearly identical values of predictors as validation sample observations. And some of these will correlate with a target at better than chance levels in the same direction in both training and validation when they are actually driven by confounded predictors with poor external validity.  If such a cross-validated model is selected from a ''k''-fold set, human [[confirmation bias]] will be at work and determine that such a model has been validated. This is why traditional cross-validation needs to be supplemented with controls for human bias and confounded model specification like swap sampling and prospective studies.

==Cross validation for time-series models==
{{See also|Blocking (statistics)}}
Due to correlations, cross-validation with random splits might be problematic for [[time-series]] models (if we are more interested in evaluating extrapolation, rather than interpolation).<ref>Cross-validation strategies for data with temporal, spatial, hierarchical, or phylogenetic structure https://nsojournals.onlinelibrary.wiley.com/doi/10.1111/ecog.02881</ref> A more appropriate approach might be to use rolling cross-validation.<ref>{{cite journal |last1=Bergmeir |first1=Christoph |last2=Benítez |first2=José M. |title=On the use of cross-validation for time series predictor evaluation |journal=Information Sciences |date=May 2012 |volume=191 |pages=192–213 |doi=10.1016/j.ins.2011.12.028 }}</ref>

However, if performance is described by a single [[summary statistic]], it is possible that the approach described by Politis and Romano as a [[stationary bootstrap]]<ref>{{cite journal |last1=Politis |first1=Dimitris N. |last2=Romano |first2=Joseph P. |title=The Stationary Bootstrap |journal=Journal of the American Statistical Association |date=December 1994 |volume=89 |issue=428 |pages=1303–1313 |doi=10.1080/01621459.1994.10476870 |hdl=10983/25607 |hdl-access=free }}</ref> will work. The statistic of the bootstrap needs to accept an interval of the time series and return the summary statistic on it. The call to the stationary bootstrap needs to specify an appropriate mean interval length.

==Applications==

Cross-validation can be used to compare the performances of different predictive modeling procedures.  For example, suppose we are interested in [[optical character recognition]], and we are considering using either a [[Support Vector Machine]] (SVM) or [[K-nearest neighbors algorithm|''k''-nearest neighbors]] (KNN) to predict the true character from an image of a handwritten character.  Using cross-validation, we can obtain empirical estimates comparing these two methods in terms of their respective fractions of misclassified characters. In contrast, the in-sample estimate will not represent the quantity of interest (i.e. the generalization error).<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>

Cross-validation can also be used in [[Feature selection|''variable selection'']].<ref name="Picard84">{{cite journal |last1=Picard |first1=Richard |last2=Cook |first2=Dennis |year=1984 |title=Cross-Validation of Regression Models |journal=Journal of the American Statistical Association |jstor=2288403 |volume=79 |pages=575–583 |doi=10.2307/2288403 |issue=387 }}</ref> Suppose we are using the [[gene expression|expression]] levels of 20 [[proteins]] to predict whether a [[cancer]] patient will respond to a [[drug]]. A practical goal would be to determine which subset of the 20 features should be used to produce the best predictive model. For most modeling procedures, if we compare feature subsets using the in-sample error rates, the best performance will occur when all 20 features are used. However under cross-validation, the model with the best fit will generally include only a subset of the features that are deemed truly informative.

A recent development in medical statistics is its use in meta-analysis. It forms the basis of the validation statistic, Vn which is used to test the statistical validity of meta-analysis summary estimates.<ref>{{cite journal |last1=Willis |first1=Brian H. |last2=Riley |first2=Richard D. |title=Measuring the statistical validity of summary meta-analysis and meta-regression results for use in clinical practice |journal=Statistics in Medicine |date=20 September 2017 |volume=36 |issue=21 |pages=3283–3301 |doi=10.1002/sim.7372 |pmid=28620945 |pmc=5575530 }}</ref>  It has also been used in a more conventional sense in meta-analysis to estimate the likely prediction error of meta-analysis results.<ref>{{cite journal |last1=Riley |first1=Richard D. |last2=Ahmed |first2=Ikhlaaq |last3=Debray |first3=Thomas P. A. |last4=Willis |first4=Brian H. |last5=Noordzij |first5=J. Pieter |last6=Higgins |first6=Julian P.T. |last7=Deeks |first7=Jonathan J. |title=Summarising and validating test accuracy results across multiple studies for use in clinical practice |journal=Statistics in Medicine |date=15 June 2015 |volume=34 |issue=13 |pages=2081–2103 |doi=10.1002/sim.6471 |pmid=25800943 |pmc=4973708 }}</ref>

==See also==
{{Commons category|Cross-validation (statistics)}}
{{Div col|colwidth=20em}}
* [[Boosting (machine learning)]]
* [[Bootstrap aggregating]] (bagging)
** [[Out-of-bag error]]
* [[Bootstrapping (statistics)]]
* [[Leakage (machine learning)]]
* [[Model selection]]
* [[Stability (learning theory)]]
* [[Validity (statistics)]]
{{Div col end}}

==Notes and references==
{{reflist|30em}}

==Further reading==
* {{cite journal |last1=Bengio |first1=Yoshua |last2=Grandvalet |first2=Yves |title=No Unbiased Estimator of the Variance of K-Fold Cross-Validation |journal=Journal of Machine Learning Research |volume=5 |date=2004 |pages=1089–1105 |url=https://www.jmlr.org/papers/volume5/grandvalet04a/grandvalet04a.pdf }}
* {{cite journal |last1=Kim |first1=Ji-Hyun |title=Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap |journal=Computational Statistics & Data Analysis |date=September 2009 |volume=53 |issue=11 |pages=3735–3745 |doi=10.1016/j.csda.2009.04.009 }}
* {{cite journal |last1=Beleites |first1=Claudia |last2=Baumgartner |first2=Richard |last3=Bowman |first3=Christopher |last4=Somorjai |first4=Ray |last5=Steiner |first5=Gerald |last6=Salzer |first6=Reiner |last7=Sowa |first7=Michael G. |title=Variance reduction in estimating classification error using sparse datasets |journal=Chemometrics and Intelligent Laboratory Systems |date=October 2005 |volume=79 |issue=1–2 |pages=91–100 |doi=10.1016/j.chemolab.2005.04.008 }}
* {{cite journal |last1=Trippa |first1=Lorenzo |last2=Waldron |first2=Levi |last3=Huttenhower |first3=Curtis |last4=Parmigiani |first4=Giovanni |title=Bayesian nonparametric cross-study validation of prediction methods |journal=The Annals of Applied Statistics |date=March 2015 |volume=9 |issue=1 |doi=10.1214/14-AOAS798 |arxiv=1506.00474 }}

{{Statistics|hide}}

{{DEFAULTSORT:Cross-Validation (Statistics)}}
[[Category:Model selection]]
[[Category:Regression variable selection]]
[[Category:Machine learning]]