Cross-validation (statistics)

Assume 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 an independent sample of validation data is taken 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. 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.

In linear regression, there exist real response values y₁, ..., y_n, and n p-dimensional vector covariates x₁, ..., x_n. The components of the vector x_i are denoted x_i1, ..., x_ip. If least squares is used to fit a function in the form of a hyperplane ŷ = a + β^Tx to the data (x_i, y_i) _{1 ≤ i ≤ n}, 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_i, y_i) _{1 ≤ i ≤ n} is defined as:

${\displaystyle {\begin{aligned}{\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 _{1}x_{i1}-\dots -\beta _{p}x_{ip})^{2}\end{aligned}}}$

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 − p − 1)/(n + p + 1) < 1 times the expected value of the MSE for the validation set[12] (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 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.

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 under the assumption that the model specification is valid, cross-validation can be used for checking whether the model has been 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 regularized cost function.) 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.

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

Leave-one-out cross-validation

Illustration of leave-one-out cross-validation (LOOCV) when n = 8 observations. A total of 8 models will be trained and tested.

Leave-one-out cross-validation (LOOCV) is a particular case of leave-p-out cross-validation with p = 1.The process looks similar to 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 ${\displaystyle C_{1}^{n}=n}$ passes rather than ${\displaystyle C_{p}^{n}}$. However, ${\displaystyle n}$ passes may still require quite a large computation time, in which case other approaches such as k-fold cross validation may be more appropriate.[15]

Pseudo-code algorithm:

Input:

x, {vector of length N with x-values of incoming points}

y, {vector of length N with y-values of the expected result}

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

Output:

err, {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

k-fold cross-validation

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. 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 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,[16] but in general k remains an unfixed parameter.

For example, setting k = 2 results in 2-fold cross-validation. In 2-fold cross-validation, we randomly shuffle the dataset into two sets d₀ and d₁, 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₀ and validate on d₁, followed by training on d₁ and validating on d₀.

When k = n (the number of observations), k-fold cross-validation is equivalent to leave-one-out cross-validation.[17]

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.[18]

When cross-validation is used simultaneously for selection of the best set of 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:

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

When users apply cross-validation to select a good configuration ${\displaystyle \lambda }$, 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.[24] 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.[24] Hoornweg (2018) shows how a tuning parameter ${\displaystyle \gamma }$ 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 ${\displaystyle \lambda _{R}}$ that is defined by the user.

If ${\displaystyle \lambda _{i}}$ denotes the ${\displaystyle i^{th}}$ candidate configuration that might be selected, then the loss function that is to be minimized can be defined as

${\displaystyle L_{\lambda _{i}}=(1-\gamma ){\mbox{ Relative Accuracy}}_{i}+\gamma {\mbox{ Relative Simplicity}}_{i}.}$

Relative accuracy can be quantified as ${\displaystyle {\mbox{MSE}}(\lambda _{i})/{\mbox{MSE}}(\lambda _{R})}$, so that the mean squared error of a candidate ${\displaystyle \lambda _{i}}$ is made relative to that of a user-specified ${\displaystyle \lambda _{R}}$. The relative simplicity term measures the amount that ${\displaystyle \lambda _{i}}$ deviates from ${\displaystyle \lambda _{R}}$ relative to the maximum amount of deviation from ${\displaystyle \lambda _{R}}$. Accordingly, relative simplicity can be specified as ${\displaystyle {\frac {(\lambda _{i}-\lambda _{R})^{2}}{(\lambda _{\max }-\lambda _{R})^{2}}}}$, where ${\displaystyle \lambda _{\max }}$ corresponds to the ${\displaystyle \lambda }$ value with the highest permissible deviation from ${\displaystyle \lambda _{R}}$. With ${\displaystyle \gamma \in [0,1]}$, 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 ${\displaystyle c=1,2,...,C}$ by specifying the loss function as

${\displaystyle L_{\lambda _{i}}={\mbox{ Relative Accuracy}}_{i}+\sum _{c=1}^{C}{\frac {\gamma _{c}}{1-\gamma _{c}}}{\mbox{ Relative Simplicity}}_{i,c}.}$

Hoornweg (2018) shows that a loss function with such an accuracy-simplicity tradeoff can also be used to intuitively define shrinkage estimators like the (adaptive) lasso and Bayesian / ridge regression.[24] Click on the lasso for an example.

Suppose we choose a measure of fit F, and use cross-validation 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 cross-validation estimator F^* is very nearly unbiased for EF.[25] The reason that it is slightly biased is that the training set in cross-validation 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.[26][27] 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 intervals around cross-validation estimates,[26] but this is considered a difficult problem.

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).

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 predicting stock values 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 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.[28] 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 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.[29] 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.[30]
• 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. 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.

Since the order of the data is important, cross-validation might be problematic for time-series models. A more appropriate approach might be to use rolling cross-validation.[31]

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[32] 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.

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 (KNN) to predict the true character from an image of a handwritten character. Using cross-validation, 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 in-sample error rates, one method would likely appear to perform better, since it is more flexible and hence more prone to overfitting compared to the other method.

Cross-validation can also be used in variable selection.[33] 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 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.[34] It has also been used in a more conventional sense in meta-analysis to estimate the likely prediction error of meta-analysis results.[35]