84
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Hi Amelio. Please note that simulations provided in the new answer by Xavier and in this older Q by Jake Westfall stats.stackexchange.com/questions/280665, both demonstrate that the variance decreases with $K$. This directly contradicts the currently accepted answer, and also the most upvoted answer (that was previously accepted). I haven't seen any simulation anywhere that would support the claim that the variance increases with $K$ and is highest for LOOCV. $\endgroup$ – amoeba says Reinstate Monica Jul 18 '18 at 11:41
  • 2
    $\begingroup$ Thanks @amoeba I am watching progress on both answers. I will definitely do my best to make sure the accepted answer points to the most useful and correct one. $\endgroup$ – Amelio Vazquez-Reina Jul 18 '18 at 12:08
  • 1
    $\begingroup$ @amoeba see researchgate.net/profile/Francisco_Martinez-Murcia/publication/… whhich shows increase in variance with k $\endgroup$ – Hanan Shteingart Nov 3 '18 at 21:24
  • $\begingroup$ it would be interesting to see where he gets that graph from, at a first look at the thesis it looks like its been made up to fit his explanations in the introduction sections. Perhaps its an actual simulation but its not explained, and it is certainly not a result from his actual experiments which are lower... $\endgroup$ – Xavier Bourret Sicotte Nov 8 '18 at 21:21
53
+100
$\begingroup$

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.

enter image description here

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

enter image description here

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

enter image description here

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

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

enter image description here

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.

enter image description here

enter image description here

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

$\endgroup$
  • 11
    $\begingroup$ +11! Finally an answer with an explicit simulation! And it goes directly against the conclusion of the currently accepted and of the most upvoted answers. Regarding your conclusion: if indeed "the model stability is a key factor", then one should be able to set up a simulation where the variance would increase with $K$. I've seen two simulations: yours here, and this one and both show that the variance either decreases or stays constant with $K$. Until I see a simulation with increasing variance, I'll remain very skeptical that it ever does. $\endgroup$ – amoeba says Reinstate Monica Jul 18 '18 at 12:06
  • 4
    $\begingroup$ @amoeba here's a case where LOOCV fails: consider n data points and an interpolating polynomial of degree n. Now double the number of data points by adding a duplicate right on each existing point. LOOCV says the error is zero. You need to lower the folds to get any useful info. $\endgroup$ – Paul Jul 18 '18 at 14:15
  • 2
    $\begingroup$ For thos interested in this discussion - lets continue in chat: chat.stackexchange.com/rooms/80281/… $\endgroup$ – Xavier Bourret Sicotte Jul 20 '18 at 7:46
  • 1
    $\begingroup$ Have you considered the fact that $k-fold$ with e.g. $k=10$ allows repetition? This is not an option with LOOCV, and thus should be taken into account. $\endgroup$ – D1X Jul 20 '18 at 9:40
  • 1
    $\begingroup$ @amoeba: re Kohavi/ LOO and variance. I found that LOO for some classification models can be quite (surprisingly) unstable. This is particularly pronounced in small sample size, and I think it is related to the test case always belonging to the class that is underrepresented wrt. the whole sample: in binary classification stratified leave-2-out does not seem to have this problem (but I did not test extensively). This instability would add to the observed variance, making LOO stick out of the other choices of k. IIRC, this is consistent with Kohavi's findings. $\endgroup$ – cbeleites supports Monica Jul 23 '18 at 17:27
45
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ +1 (long time ago), but re-reading your answer now, I am confused by the following bit. You say that 2-fold CV "often also has large variance because the training sets are only half the size". I understand that having a training set two times smaller is a problem, but why does it give "large variance"? Shouldn't it be "large bias" instead? Then the whole issue of choosing the number of folds becomes a bias-variance trade-off, which is how it is often presented. $\endgroup$ – amoeba says Reinstate Monica May 8 '16 at 0:40
  • 1
    $\begingroup$ @Sebastian I think "variance" in this context refers to the variance of the "accumulated" model performance (sum over all $k$ folds) and not to the variance of the folds themselves, as you imply in the last two sentences. $\endgroup$ – amoeba says Reinstate Monica Sep 5 '16 at 1:02
  • 3
    $\begingroup$ Was just looking into some literature. Interestingly, In Introduction to Statistical Learning James, Witten, Hastie & Tibshirani say LOOCV "is highly variable, since it is based upon a single observation (x1,y1)." and in Elements of Statistical Learning Hastie & Tibshirani & Friedman say that LOOCV "can have high variance because the N training sets are so similar to one another." $\endgroup$ – user39663 Sep 5 '16 at 5:44
  • 2
    $\begingroup$ this is incorrect. The variance should be $var[\Sigma x_i / n]$=$\Sigma\Sigma cov(x_i, x_j) / n^2$. You are right that the enumerator is larger, but the denominator gets larger as well. $\endgroup$ – denizen of the north Jan 26 '18 at 3:07
  • 3
    $\begingroup$ No, that's not really the "whole point". People use k-fold CV to get a single global estimate all the time. You can certainly try to use the multiple fold estimates in other ways, but putting them together is one of the most common ways to estimate holdout performance of a modeling technique. And that is precisely what Eq 7.48 of ESL is doing. $\endgroup$ – Paul Jul 23 '18 at 19:03
28
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ I think this answer clarifies a lot more than the accepted answer and particularly explains the accepted answer. $\endgroup$ – D1X Jul 24 '17 at 17:51
  • $\begingroup$ what do you mean by >"Now, if you were to re-train this model with the same parameters multiple times on new training sets, what would happen?". Training means finding the parameters, right? did you mean to say hyperparameters? $\endgroup$ – MiloMinderbinder May 28 '18 at 20:50
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Please note that simulations provided in the new answer by Xavier and also in this older Q by Jake Westfall, both demonstrate that the variance decreases with $K$. This directly contradicts your answer. So far I haven't seen any simulation that would support the claim that the variance increases with $K$ and is highest for LOOCV. $\endgroup$ – amoeba says Reinstate Monica Jul 18 '18 at 11:43
  • 3
    $\begingroup$ They demonstrate the variance decreases as $k \to N$ up to a certain point, where it remains flat. It is theoretically shown that the mean of correlated samples has more variance, therefore showing the result theoretically. That being said, you are right, an actual experiment which shows this is missing. I will do my best to construct it. $\endgroup$ – D1X Jul 18 '18 at 12:03
  • $\begingroup$ Yes the decrease with $K$ from $K=10$ to $K=N$ was due to an error in Xavier's answer. Now it's fixed and the variance indeed stays the same in this range. Given that two independent simulations show the same effect, I continue to be skeptical that LOOCV can be expected to have higher variance. Your theoretical argument is very hand-waving. The mean of correlated samples has higher variance only when everything else is the same. It's not clear that everything else is the same for 10-fold vs N-fold CV. Looking forward to your simulation. $\endgroup$ – amoeba says Reinstate Monica Jul 18 '18 at 13:57
  • 1
    $\begingroup$ Haven't looked at those papers yet, I will have a look at them when I have time. Still, OLS linear models are very simple models, indeed subject themselves to low variance. Not only that, they have closed formulae for Cross-validation. $\endgroup$ – D1X Jul 20 '18 at 9:31
  • 1
    $\begingroup$ +1 your edits make the answer much clearer - we are aligned on the impact of correlation between training sets --> higher variance. In practice though (experimentally) it seems that the training sets are not always that correlated between each other. $\endgroup$ – Xavier Bourret Sicotte Sep 7 '18 at 8:26
12
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Is it possible to expand on this answer a little, perhaps to summarise some of the key aspects raised in the paper? $\endgroup$ – Silverfish Dec 16 '16 at 23:06
  • 3
    $\begingroup$ Very interesting paper. In reviewing Kohavi (1995) I felt that many statements were impossibly broad and largely unsubstantiated. It is a folk-wisdom paper whose critical interrogation is long overdue. $\endgroup$ – Paul Jul 16 '18 at 16:31
3
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ +1. Welcome to CrossValidated! Great to see you join the discussion. I should re-read your 2004 paper to refresh it in memory, but I'm wondering if the algorithms that people use in practice with CV are more likely to be stable or unstable? I've seen two simulations here: one using polynomial fitting and another using regression. In both cases variance was decreasing with $K$ all the way up to LOOCV. What kind of algorithm should one use to observe a different outcome? $\endgroup$ – amoeba says Reinstate Monica Jul 20 '18 at 11:59
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Interestingly this argument seems somewhat orthogonal to the one presented in the currently accepted answer, which, if I understood correctly, focuses instead on the covariance between the training folds. It would be good to see how you relate this answer to the $X_i$'s in @Gitte's answer. $\endgroup$ – Amelio Vazquez-Reina Nov 4 '16 at 2:09
  • 4
    $\begingroup$ it seems like you are talking about variability in the models predictions across the holdout sets during cross validation. I don't think this is of much interest. What is of interest is whether your final tuned model will vary much in the predictions it makes if it were to be trained on different data (i.e., your model's estimate of truth is really variable depending on the training set) $\endgroup$ – captain_ahab Nov 4 '16 at 17:48
  • $\begingroup$ And how would you estimate the expected variation on yet unseen data if not through the observed variation among consecutively predicted sets of data that were unknown at the time? I get your point though, variability that stems from the experimental setup alone is not of interest. My response: Therefore one needs to select an experimental setup that does not introduce new kinds of variability. If one does so, the two kinds of variability cannot be told apart and it becomes more difficult to estimate the extend of the one kind that is of interest. $\endgroup$ – David Ernst Nov 4 '16 at 17:50
  • 1
    $\begingroup$ you can show this with simulations (I'll look for a paper). I'm not sure if we are talking past eachother - but when hastie and people are talking about the high correlation among the training sets in LOOCV, they emphasizing that you basically keep training your model on the same training dataset. That leads to overfitting to that training dataset. change the training dataset, you models predictions for test example X will change a lot. in contrast if you training sets were less correlated, you can use a totally new training set and you'd get a similar prediction for test example X. $\endgroup$ – captain_ahab Nov 4 '16 at 17:56
  • $\begingroup$ I think there are two separate issues involved. Increasing k leads to more overlap among training sets which has the consequences that you mention. (I'm not arguing with any of that) At the same time, increasing k leads to smaller test sets per fold which means that records are more likely to be shuffled in unwanted ways in those sets. I think that for the specific question asked, this is the main reason. There might be contributions from training set overlap as well. (There is a third issue when you use repetitions because then the test sets have overlap as well.) $\endgroup$ – David Ernst Nov 4 '16 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.