Bias and variance in leave-one-out vs K-fold cross validation

Question

How do different cross-validation methods compare in terms of model variance and bias?

My question is partly motivated by this thread: Optimal number of folds in $K$-fold cross-validation: is leave-one-out CV always the best choice?. The answer there suggests that models learned with leave-one-out cross-validation have higher variance than those learned with regular $K$-fold cross-validation, making leave-one-out CV a worse choice.

However, my intuition tells me that in leave-one-out CV one should see relatively lower variance between models than in the $K$-fold CV, since we are only shifting one data point across folds and therefore the training sets between folds overlap substantially.

Or going in the other direction, if $K$ is low in the $K$-fold CV, the training sets would be quite different across folds, and the resulting models are more likely to be different (hence higher variance).

If the above argument is right, why would models learned with leave-one-out CV have higher variance?

Answer 1

why would models learned with leave-one-out CV have higher variance?

[TL:DR] A summary of recent posts and debates (July 2018)

This topic has been widely discussed both on this site, and in the scientific literature, with conflicting views, intuitions and conclusions. Back in 2013 when this question was first asked, the dominant view was that LOOCV leads to larger variance of the expected generalization error of a training algorithm producing models out of samples of size $n(K−1)/K$.

This view, however, appears to be an incorrect generalization of a special case and I would argue that the correct answer is: "it depends..."

Paraphrasing Yves Grandvalet the author of a 2004 paper on the topic I would summarize the intuitive argument as follows:

1. If cross-validation were averaging independent estimates: then leave-one-out CV one should see relatively lower variance between models since we are only shifting one data point across folds and therefore the training sets between folds overlap substantially.
2. This is not true when training sets are highly correlated: Correlation may increase with K and this increase is responsible for the overall increase of variance in the second scenario. Intuitively, in that situation, leave-one-out CV may be blind to instabilities that exist, but may not be triggered by changing a single point in the training data, which makes it highly variable to the realization of the training set.

Experimental simulations from myself and others on this site, as well as those of researchers in the papers linked below will show you that there is no universal truth on the topic. Most experiments have monotonically decreasing or constant variance with $K$, but some special cases show increasing variance with $K$.

The rest of this answer proposes a simulation on a toy example and an informal literature review.

[Update] You can find here an alternative simulation for an unstable model in the presence of outliers.

Simulations from a toy example showing decreasing / constant variance

Consider the following toy example where we are fitting a degree 4 polynomial to a noisy sine curve. We expect this model to fare poorly for small datasets due to overfitting, as shown by the learning curve.

Note that we plot 1 - MSE here to reproduce the illustration from ESLII page 243

 Methodology

You can find the code for this simulation here. The approach was the following:

1. Generate 10,000 points from the distribution $sin(x) + \epsilon$ where the true variance of $\epsilon$ is known
2. Iterate $i$ times (e.g. 100 or 200 times). At each iteration, change the dataset by resampling $N$ points from the original distribution
3. For each data set $i$:
   • Perform K-fold cross validation for one value of $K$
   • Store the average Mean Square Error (MSE) across the K-folds
4. Once the loop over $i$ is complete, calculate the mean and standard deviation of the MSE across the $i$ datasets for the same value of $K$
5. Repeat the above steps for all $K$ in range $\{ 5,...,N\}$ all the way to Leave One Out CV (LOOCV)

Impact of $K$ on the Bias and Variance of the MSE across $i$ datasets.

Left Hand Side: Kfolds for 200 data points, Right Hand Side: Kfolds for 40 data points

Standard Deviation of MSE (across data sets i) vs Kfolds

From this simulation, it seems that:

• For small number $N = 40$ of datapoints, increasing $K$ until $K=10$ or so significantly improves both the bias and the variance. For larger $K$ there is no effect on either bias or variance.
• The intuition is that for too small effective training size, the polynomial model is very unstable, especially for $K \leq 5$
• For larger $N = 200$ - increasing $K$ has no particular impact on both the bias and variance.

---

An informal literature review

The following three papers investigate the bias and variance of cross validation

• Ron Kohavi (1995)
• Yves Grandvalet and Yoshua Bengio (2004)
• Zhang and Yang (2015)

Kohavi 1995

This paper is often refered to as the source for the argument that LOOC has higher variance. In section 1:

“For example, leave-oneout is almost unbiased, but it has high variance, leading to unreliable estimates (Efron 1983)"

This statement is source of much confusion, because it seems to be from Efron in 1983, not Kohavi. Both Kohavi's theoretical argumentations and experimental results go against this statement:

Corollary 2 ( Variance in CV)

Given a dataset and an inducer. If the inducer is stable under the perturbations caused by deleting the test instances for the folds in k-fold CV for various values of $k$, then the variance of the estimate will be the same

Experiment In his experiment, Kohavi compares two algorithms: a C4.5 decision tree and a Naive Bayes classifier across multiple datasets from the UC Irvine repository. His results are below: LHS is accuracy vs folds (i.e. bias) and RHS is standard deviation vs folds

In fact, only the decision tree on three data sets clearly has higher variance for increasing K. Other results show decreasing or constant variance.

Finally, although the conclusion could be worded more strongly, there is no argument for LOO having higher variance, quite the opposite. From section 6. Summary

"k-fold cross validation with moderate k values (10-20) reduces the variance... As k-decreases (2-5) and the samples get smaller, there is variance due to instability of the training sets themselves.

Zhang and Yang

The authors take a strong view on this topic and clearly state in Section 7.1

In fact, in least squares linear regression, Burman (1989) shows that among the k-fold CVs, in estimating the prediction error, LOO (i.e., n-fold CV) has the smallest asymptotic bias and variance. ...

... Then a theoretical calculation (Lu, 2007) shows that LOO has the smallest bias and variance at the same time among all delete-n CVs with all possible n_v deletions considered

Experimental results Similarly, Zhang's experiments point in the direction of decreasing variance with K, as shown below for the True model and the wrong model for Figure 3 and Figure 5.

The only experiment for which variance increases with $K$ is for the Lasso and SCAD models. This is explained as follows on page 31:

However, if model selection is involved, the performance of LOO worsens in variability as the model selection uncertainty gets higher due to large model space, small penalty coefficients and/or the use of data-driven penalty coefficients

Answer 2

In $k$-fold cross-validation we partition a dataset into $k$ equally sized non-overlapping subsets $S$. For each fold $S_i$, a model is trained on $S \setminus S_i$, which is then evaluated on $S_i$. The cross-validation estimator of, for example the prediction error, is defined as the average of the prediction errors obtained on each fold.

While there is no overlap between the test sets on which the models are evaluated, there is overlap between the training sets for all $k>2$. The overlap is largest for leave-one-out cross-validation. This means that the learned models are correlated, i.e. dependent, and the variance of the sum of correlated variables increases with the amount of covariance (see wikipedia):

\begin{equation} \operatorname{Var}\left(\sum_{i=1}^NX_i\right)=\sum_{i=1}^N \sum_{j=1}^N \operatorname{Cov}\left(X_i,X_j\right) \end{equation}

Therefore, leave-one-out cross-validation has large variance in comparison to CV with smaller $k$.

However, note that while two-fold cross validation doesn't have the problem of overlapping training sets, it often also has large variance because the training sets are only half the size of the original sample. A good compromise is ten-fold cross-validation.

Some interesting papers that touch upon this subject (out of many more):

• A study of cross-validation and bootstrap for accuracy estimation and model selection by Ron Kohavi
• No unbiased estimator of the variance of k-fold cross-validation by Yoshua Bengio and Yves Grandvalet

Answer 3

[...] my intuition tells me that in leave-one-out CV one should see relatively lower variance between models than in the $K$-fold CV, since we are only shifting one data point across folds and therefore the training sets between folds overlap substantially.

I think your intuition is sensible if you are thinking about the predictions made by the models on each leave-one-out fold. They are based on correlated/very similar data (the full dataset minus one data point) and will therefore make similar predictions - i.e., low variability.

The source of confusion though is that when people talk about LOOCV leading to high variability, they aren't talking about the predictions made by the many models built during that loop of cross-validation on the holdout sets. Instead, they are talking about how much variability your final chosen model (the one chosen via LOOCV) would have if you train that exact model/parameters on new training sets - training sets your model haven't seen before. In this case, variability would be high.

Why would variability be high? Let's simplify this a bit. Imagine that instead of using LOOCV to pick a model, you just had one training set and then you tested a model built using that training data, say, 100 times on 100 single test data points (data points are not part of the training set). If you pick the model and parameter set that does the best across those 100 tests, then you'll select one that allows this particular training set to be really good at predicting the test data. You could potentially choose a model that captures 100% of the associations between that particular training dataset and the holdout data. Unfortunately, some part of those associations between the training and test data sets will be noise or spurious associations because, although the test set changes and you can identify noise on this side, the training dataset doesn't and you can't determine what explained variance is due to noise. In other words, what this means is that have overfit your predictions to this particular training dataset.

Now, if you were to re-train this model with the same parameters multiple times on new training sets, what would happen? Well, a model that is overfit to a particular set of training data will lead to variability in its prediction when the training set changes (ie. change the training set slightly and the model will change its predictions substantially).

Because all of the folds in LOOCV are highly correlated, it is similar to the case above (same training set; different test points). In other words, if that particular training set has some spurious correlation with those test points, you're model will have difficulties determining which correlations are real and which are spurious, because even though the test set changes, the training set doesn't.

In contrast, less correlated training folds means that the model will be fit to multiple unique datasets. So, in this situation, if you retrain the model on a another new data set, it'll lead to a similar prediction (i.e., small variability).

Answer 4

Although this question is rather old, I would like to add an additional answer because I think it is worth clarifying this a bit more.

My question is partly motivated by this thread: Optimal number of folds in K-fold cross-validation: is leave-one-out CV always the best choice?. The answer there suggests that models learned with leave-one-out cross-validation have higher variance than those learned with regular K-fold cross-validation, making leave-one-out CV a worse choice.

That answer does not suggest that, and it should not. Let's review the answer provided there:

Leave-one-out cross-validation does not generally lead to better performance than K-fold, and is more likely to be worse, as it has a relatively high variance (i.e. its value changes more for different samples of data than the value for k-fold cross-validation).

It is talking about performance. Here performance must be understood as the performance of the model error estimator. What you are estimating with k-fold or LOOCV is model performance, both when using these techniques for choosing the model and for providing an error estimate in itself. This is NOT the model variance, it is the variance of the estimator of the error (of the model). See the example (*) bellow.

However, my intuition tells me that in leave-one-out CV one should see relatively lower variance between models than in the K-fold CV, since we are only shifting one data point across folds and therefore the training sets between folds overlap substantially.

Indeed, there is lower variance between models, They are trained with datasets that have $n-2$ observations in common! As $n$ increases, they become virtually the same model (Assuming no stochasticity).

It is precisely this lower variance and higher correlation between models what makes the estimator I talk about above have more variance, because that estimator is the mean of these correlated quantities, and the variance of the mean of correlated data is higher than that of uncorrelated data. Here it is shown why: variance of the mean of correlated and uncorrelated data.

Or going in the other direction, if K is low in the K-fold CV, the training sets would be quite different across folds, and the resulting models are more likely to be different (hence higher variance).

Indeed.

If the above argument is right, why would models learned with leave-one-out CV have higher variance?

The above argument is right. Now, the question is wrong. The variance of the model is a whole different topic. There is a variance where there is a random variable. In machine learning you deal with lots of random variables, in particular and not restricted to: each observation is a random variable; the sample is a random variable; the model, since it is trained from a random variable, is a random variable; the estimator of the error that your model will produce when faced to the population is a random variable; and last but not least, the error of the model is a random variable, since there is likely to be noise in the population (this is called irreducible error). There can also be more randomness if there is stochasticity involved in the model learning process. It is of paramount importance to distinguish between all these variables.

---

(*) Example: Suppose you have a model with a real error $err$, where you should understand $err$ as the error that the model produces over the entire population. Since you have a sample drawn from this population, you use Cross validation techniques over that sample to compute an estimate of $E$, which we can name $\tilde{err}$. As every estimator, $\tilde{err}$ is a random variable, meaning it has its own variance, $var(\tilde{err})$, and its own bias, $E(\tilde{err}-err)$. $var(\tilde{err})$ is precisely what is higher when employing LOOCV. While LOOCV is a less biased estimator than $k-fold$ with $k < n$, it has more variance. To further understand why a compromise between bias and variance is desired, suppose $err = 10$, and that you have two estimators: $\tilde{err}_1$ and $\tilde{err}_2$. The first one is producing this output

$$\tilde{err}_1 = 0,5,10,20,15,5,20,0,10,15...$$ whereas the second one is producing $$ \tilde{err}_2 = 8.5,9.5,8.5,9.5,8.75,9.25,8.8,9.2...$$

The last one, although it has more bias, should be preferred, as it has a lot less variance and a acceptable bias, i.e. a compromise (bias-variance trade-off). Please do note that you neither want very low variance if that entails a high bias!

---

Additional note: In this answer I try to clarify (what I think are) the misconceptions that surround this topic and, in particular, tries to answer point by point and precisely the doubts the asker has. In particular, I try to make clear which variance we are talking about, which is what it is essentially asked here. I.e. I explain the answer which is linked by the OP.

That being said, while I provide the theoretical reasoning behind the claim, we have not found, yet, conclusive empirical evidence that supports it. So please be very careful.

Ideally, you should read this post first and then refer to the answer by Xavier Bourret Sicotte, which provides an insightful discussion about the empirical aspects.

Last but not least, something else must be taken into account: Even if variance as you increase $k$ remains flat (as we haven't empirically proved otherwise), $k-fold$ with $k$ small enough allows for repetition (repeated k-fold), which definitely should be done, e.g. $10 \ \times \ 10-fold$. This effectively reduces variance, and is not an option when performing LOOCV.

Answer 5

The issues are indeed subtle. But it is definitely not true that LOOCV has larger variance in general. A recent paper discusses some key aspects and addresses several seemingly widespread misconceptions on cross-validation.

Yongli Zhang and Yuhong Yang (2015). Cross-validation for selecting a model selection procedure. Journal of Econometrics, vol. 187, 95-112.

The following misconceptions are frequently seen in the literature, even up to now:

"Leave-one-out (LOO) CV has smaller bias but larger variance than leave- more-out CV"

This view is quite popular. For instance, Kohavi (1995, Section 1) states: "For example, leave-one-out is almost unbiased, but it has high variance, leading to unreliable estimates". The statement, however, is not generally true.

In more detail:

In the literature, even including recent publications, there are overly taken recommendations. The general suggestion of Kohavi (1995) to use 10-fold CV has been widely accepted. For instance, Krstajic et al (2014, page 11) state: “Kohavi [6] and Hastie et al [4] empirically show that V-fold cross-validation compared to leave-one-out cross-validation has lower variance”. They consequently take the recommendation of 10-fold CV (with repetition) for all their numerical investigations. In our view, such a practice may be misleading. First, there should not be any general recommendation that does not take into account of the goal of the use of CV. In particular, examination of bias and variance of CV accuracy estimation of a candidate model/modeling procedure can be a very different matter from optimal model selection (with either of the two goals of model selection stated earlier). Second, even limited to the accuracy estimation context, the statement is not generally correct. For models/modeling procedures with low instability, LOO often has the smallest variability. We have also demonstrated that for highly unstable procedures (e.g., LASSO with pn much larger than n), the 10-fold or 5-fold CVs, while reducing variability, can have significantly larger MSE than LOO due to even worse bias increase.

Overall, from Figures 3-4, LOO and repeated 50- and 20-fold CVs are the best here, 10-fold is significantly worse, and k ≤ 5 is clearly poor. For predictive performance estimation, we tend to believe that LOO is typically the best or among the best for a fixed model or a very stable modeling procedure (such as BIC in our context) in both bias and variance, or quite close to the best in MSE for a more unstable procedure (such as AIC or even LASSO with p ≫ n). While 10-fold CV (with repetitions) certainly can be the best sometimes, but more frequently, it is in an awkward position: it is riskier than LOO (due to the bias problem) for prediction error estimation and it is usually worse than delete-n/2 CV for identifying the best candidate.

Answer 6

Before discussing about bias and variance, the first question is:

What is estimated by cross-validation?

In our 2004 JMLR paper, we argue that, without any further assumption, $K$-fold cross-validation estimates the expected generalization error of a training algorithm producing models out of samples of size $n(K-1)/K$. Here, the expectation is with respect to training samples. With this view, changing $K$ means changing the estimated quantity: the comparison of bias and variance for different values of $K$ should then be treated with caution.

That being said, we provide experimental results that show that variance may monotonically decreases with $K$, or that it may be minimal for an intermediate value. We conjecture that the first scenario should be encountered for stable algorithms (for the current data distribution), and the second one for unstable algorithms.

my intuition tells me that in leave-one-out CV one should see relatively lower variance between models than in the $K$-fold CV, since we are only shifting one data point across folds and therefore the training sets between folds overlap substantially.

This intuition would be correct if cross-validation was averaging independent estimates, but they can be highly correlated, and this correlation may increase with $K$. This increase is responsible for the overall increase of variance in the second scenario mentioned above. Intuitively, in that situation, leave-one-out CV may be blind to instabilities that exist, but may not be triggered by changing a siongle point in the training data, which makes it highly variable to the realization of the training set.

Answer 7

I think there is a more straightforward answer. If you increase k, the test sets get smaller and smaller. Since the folds are randomly sampled, it can happen with small test sets, but not as likely with bigger ones, that they are not representative of a random shuffle. One test set could contain all the difficult to predict records and another all the easy ones. Therefore, variance is high when you predict very small test sets per fold.

Answer 8

I see in most machine learning courses, that a model is validated on smaller training sets and prediction scores are evaluated to give a measure of prediction power, these models are then discarded and the model fit to the whole dataset for the final model.

I have a couple of bug bears with terminology often used when talking about validation. For a start, each model fit on each fold of data (using k folds) or each loocv is a different model. No two will be the same (different coefficient values), therefore I think the term 'model validation ' is misleading, I prefer to say method validation in this case.

Secondly, and more directly related to this topic, if the end product is to fit to the whole dataset for the final model, the loocv will always give a more better idea of how the final model will predict, as each will likely be very similar to the final model.

Personally, I see little point in validating a model using models that are quite different from the model being validated. The more you stray from the model being validated, the less valid and relevant the validation actually is.

Unless I am missing something, which I may well be, computational expense should be the only thing that would persuade one to move toward lower k folds

Answer 9

Lets say you have data set of 100 observations. You choose 80 for training and 20 in test data. You will use dataset of 80 observations to train the model. i.e. further split it into K fold.

Method 1: LOOCV:

The holdout data contains only one data point. All the models across different holdout sets will be quite similar due to highly correlated training data. Any model you pick here will have have (poor) generalization ability because it is on just one data point in the holdout. Test set data (20 points) would be very different from the hold out data. Since model did not learn enough variation from the holdout set, it wont generalize well on test data.

Method 2: K fold (K say 5 <<N)

Here your training data sizes are smaller and k-th fold used for validation will be larger than 1 observations (as in LOOCV). If you fit number of models say, and if you decide best model using a larger hold out data set, the model will be less complex (or less likely to overfit) because otherwise it wont generalize on the hold out data set (unless holdout has same distribution than K-1 folds of training data).

Now we know that a model which does not generalize to the test data will have high variance because its typically overfitting.

Also using bias variance tradeoff principal, models based on LOOCV will have low bias (but high variance). On the other hand, models using K fold may have low variance (but higher bias).

Hope this helps.

Answer 10

I think the standard error that we are talking about here is the standard error of the $MSE$s or $Err$s generated across different cross-validation iterations. But the simulation done by Xavier Bourret Sicotte calculated the standard error of $MSE$ or $Err$ based on repeatedly drawing different sample data from the population.

If you refer to the lecture on Cross-Validation of Rob and Trevor Hastie (free online), they gave the formula for standard error of $CV_k$ as

$$ \widehat{\mathrm{SE}}\left(\mathrm{CV}_{K}\right)=\sqrt{\sum_{k=1}^{K}\left(\operatorname{Err}_{k}-\overline{\operatorname{Err}_{k}}\right)^{2} /(K-1)} $$ where $$ \mathrm{CV}_{K}=\sum_{k=1}^{K} \frac{n_{k}}{n} \operatorname{Err}_{k} $$ where $\operatorname{Err}_{k}=\sum_{i \in C_{k}} I\left(y_{i} \neq \hat{y}_{i}\right) / n_{k}$

So in my opinion the simulation was not correctly done:

Generate 10,000 points from the distribution sin(x)+ϵ where the true variance of ϵ is known
Iterate i times (e.g. 100 or 200 times). At each iteration, change the dataset by resampling N points from the original distribution
For each data set i:
Perform K-fold cross validation for one value of K
Store the average Mean Square Error (MSE) across the K-folds
Once the loop over i is complete, calculate the mean and standard deviation of the MSE across the i datasets for the same value of K <<this is where I think it is not right>>
Repeat the above steps for all K in range {5,...,N} all the way to Leave One Out CV (LOOCV)