Crossvalidation (statistics)
Crossvalidation, sometimes called rotation estimation,[1][2][3] is a model validation technique for assessing how the results of a statistical analysis will generalize to an independent data set. It is mainly used in settings where the goal is prediction, and one wants to estimate how accurately a predictive model will perform in practice. 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 (testing dataset).[4] The goal of cross validation is to define a dataset to "test" the model in the training phase (i.e., the validation dataset), in order to limit problems like overfitting, give an insight on how the model will generalize to an independent dataset (i.e., an unknown dataset, for instance from a real problem), etc.
One round of crossvalidation involves partitioning a sample of data into 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 variability, multiple rounds of crossvalidation are performed using different partitions, and the validation results are averaged over the rounds.
Crossvalidation is important in guarding against testing hypotheses suggested by the data (called "Type III errors"[5]), especially where further samples are hazardous, costly or impossible to collect.
Purpose of crossvalidation
Suppose we have a 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 optimizes the model parameters to make the model fit the training data as well as possible. If we then take an independent sample of validation data from the same 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. This is called overfitting, and is particularly likely to happen when the size of the training data set is small, or when the number of parameters in the model is large. Crossvalidation is a way to predict the fit of a model to a hypothetical validation set when an explicit validation set is not available.
Linear regression provides a simple illustration of overfitting. In linear regression we have real response values y1, ..., yn, and n pdimensional vector covariates x1, ..., xn. The components of the vectors xi are denoted x_{i1}, ..., x_{ip}. If we use least squares to fit a function in the form of a hyperplane y = a + βTx to the data (xi, yi)1≤i≤n, we could then assess the fit using the mean squared error (MSE). The MSE for a given value of the parameters a and β on the training set (xi, yi)1≤i≤n is
It can be shown under mild assumptions that the expected value of the MSE for the training set is (n − p − 1)/(n + p + 1) < 1 times the expected value of the MSE for the validation set[citation needed] (the expected value is taken over the distribution of training sets). Thus if we fit the model and compute the MSE on the training set, we will get an optimistically biased assessment of how well the model will fit an independent data set. This biased estimate is called the insample estimate of the fit, whereas the crossvalidation estimate is an outofsample estimate.
Since in linear regression it is possible to directly compute the factor (n − p − 1)/(n + p + 1) by which the training MSE underestimates the validation MSE, crossvalidation is not practically useful in that setting (however, crossvalidation remains useful in the context of linear regression in that it can be used to select an optimally regularized cost function). In most other regression procedures (e.g. logistic regression), there is no simple formula to make such an adjustment. Crossvalidation is, thus, a generally applicable way to predict the performance of a model on a validation set using computation in place of mathematical analysis.
Common types of crossvalidation
Two types of crossvalidation can be distinguished, exhaustive and nonexhaustive crossvalidation.
Exhaustive crossvalidation
Exhaustive crossvalidation methods are crossvalidation methods which learn and test on all possible ways to divide the original sample into a training and a validation set.
Leavepout crossvalidation
Leavepout crossvalidation (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.
LpO crossvalidation requires to learn and validate
times (where n is the number of observations in the original sample). So as soon as n is quite big it becomes impossible to calculate.
Leaveoneout crossvalidation
Leaveoneout crossvalidation (LOOCV) is a particular case of leavepout crossvalidation with p = 1.
LOO crossvalidation doesn't have the calculation problem of general LpO crossvalidation because
Nonexhaustive crossvalidation
Nonexhaustive cross validation methods do not compute all ways of splitting the original sample. Those methods are approximations of leavepout crossvalidation.
kfold crossvalidation
In kfold crossvalidation, the original sample is randomly partitioned into k equal sized subsamples. Of the k subsamples, a single subsample is retained as the validation data for testing the model, and the remaining k − 1 subsamples are used as training data. The crossvalidation process is then repeated k times (the folds), with each of the k subsamples used exactly once as the validation data. The k results from the folds can then be averaged (or otherwise combined) to produce a single estimation. The advantage of this method over repeated random subsampling (see below) is that all observations are used for both training and validation, and each observation is used for validation exactly once. 10fold crossvalidation is commonly used,[6] but in general k remains an unfixed parameter.
When k=n (the number of observations), the kfold crossvalidation is exactly the leaveoneout crossvalidation.
In stratified kfold crossvalidation, the folds are selected so that the mean response value is approximately equal in all the folds. In the case of a dichotomous classification, this means that each fold contains roughly the same proportions of the two types of class labels.
2fold crossvalidation
This is the simplest variation of kfold crossvalidation. Also called holdout method.[7] For each fold, we randomly assign data points to two sets d0 and d1, 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 d0 and test on d1, followed by training on d1 and testing on d0.
This has the advantage that our training and test sets are both large, and each data point is used for both training and validation on each fold.
Repeated random subsampling validation
This method randomly splits the dataset into training and validation data. 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 kfold cross validation) is that the proportion of the training/validation split is not dependent on the number of iterations (folds). 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 variation, meaning that the results will vary if the analysis is repeated with different random splits.
When the number of random splits goes to infinity, the Repeated random subsampling validation become arbitrary close to the leavepout crossvalidation.
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.
Measures of fit
The goal of crossvalidation 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 like positive predictive value 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.
Applications
Crossvalidation 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 support vector machines (SVM) or k nearest neighbors (KNN) to predict the true character from an image of a handwritten character. Using crossvalidation, we could objectively compare these two methods in terms of their respective fractions of misclassified characters. If we simply compared the methods based on their insample error rates, the KNN method would likely appear to perform better, since it is more flexible and hence more prone to overfitting compared to the SVM method.
Crossvalidation can also be used in variable selection.[8] Suppose we are using the 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 insample error rates, the best performance will occur when all 20 features are used. However under crossvalidation, the model with the best fit will generally include only a subset of the features that are deemed truly informative.
Statistical properties
Suppose we choose a measure of fit F, and use crossvalidation to produce an estimate F* 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* will vary. The statistical properties of F* result from this variation.
The crossvalidation estimator F* is very nearly unbiased for EF. The reason that it is slightly biased is that the training set in crossvalidation is slightly smaller than the actual data set (e.g. for LOOCV the training set size is n − 1 when there are n observed cases). In nearly all situations, the effect of this bias will be conservative in that the estimated fit will be slightly biased in the direction suggesting a poorer fit. In practice, this bias is rarely a concern.
The variance of F* can be large.[9][10] For this reason, if two statistical procedures are compared based on the results of crossvalidation, it is important to note that 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 intervals around crossvalidation estimates,[9] but this is considered a difficult problem.
Computational issues
Most forms of crossvalidation are straightforward to implement as long as an implementation of the prediction method being studied is available. In particular, the prediction method need only be available as a "black box" – there is no need to have access to the internals of its implementation. If the prediction method is expensive to train, crossvalidation can be very slow since the training must be carried out repeatedly. In some cases such as least squares and kernel regression, crossvalidation can be sped up significantly by precomputing 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 crossvalidation occurs in linear regression, where the results of crossvalidation have a closedform expression known as the prediction residual error sum of squares
Relationship to other forms of validation
In "true validation," or "holdout validation," a subset of observations is chosen randomly from the initial sample to form a validation or testing set, and the remaining observations are retained as the training data. Normally, less than a third of the initial sample is used for validation data.[11]
References

Geisser, Seymour (1993). Predictive Inference. New York, NY: Chapman and Hall. ISBN 0412034719.

Kohavi, Ron (1995). "A study of crossvalidation and bootstrap for accuracy estimation and model selection". Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (San Mateo, CA: Morgan Kaufmann) 2 (12): 1137–1143. CiteSeerX: 10.1.1.48.529

Devijver, Pierre A.; Kittler, Josef (1982). Pattern Recognition: A Statistical Approach. London, GB: PrenticeHall.

"Newbie question: Confused about train, validation and test data!". Retrieved 20131114.

Mosteller, Frederick (1948). "A ksample slippage test for an extreme population". Annals of Mathematical Statistics 19 (1): 58–65. doi:10.1214/aoms/1177730290. JSTOR 2236056. MR 0024116

McLachlan, Geoffrey J.; Do, KimAnh; Ambroise, Christophe (2004). Analyzing microarray gene expression data. Wiley.

"Cross Validation". Retrieved 11 November 2012

Picard, Richard; Cook, Dennis (1984). "CrossValidation of Regression Models". Journal of the American Statistical Association 79 (387): 575–583. doi:10.2307/2288403. JSTOR 2288403
Efron, Bradley; Tibshirani, Robert (1997). "Improvements on crossvalidation: The .632 + Bootstrap Method". Journal of the American Statistical Association 92 (438): 548–560. doi:10.2307/2965703. JSTOR 2965703. MR 1467848
9. Efron, Bradley; Tibshirani, Robert (1997). "Improvements on crossvalidation: The .632 + Bootstrap Method". Journal of the American Statistical Association 92 (438): 548–560. doi:10.2307/2965703. JSTOR 2965703. MR 1467848.
10. Stone, Mervyn (1977). "Asymptotics for and against crossvalidation". Biometrika 64 (1): 29–35. doi:10.1093/biomet/64.1.29. JSTOR 2335766. MR 0474601.
11. "Tutorial 12". Decision Trees Interactive Tutorial and Resources. Archived from the original on 20060623. Retrieved 20060621.
* https://en.wikipedia.org/