10
$\begingroup$

This question already has an answer here:

In leave-one-out cross-validation (LOOCV), each of the training sets looks very similar to the others, differing in only one observation. When you want to estimate the test error, you take the average of the errors over the folds. That average has a high variance.

Is there a mathematical formula, visual, or intuitive way to understand why that average has a higher variance compared with the $k$-fold cross validation?

$\endgroup$

marked as duplicate by amoeba, whuber Oct 19 '15 at 23:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

14
$\begingroup$

The original version of this answer was missing the point (that's when the answer got a couple of downvotes). The answer was fixed in October 2015.

This is a somewhat controversial topic.

It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is so because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance. See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

What value should we choose for $K$? With $K = N$, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the $N$ "training sets" are so similar to one another.

See also a similar quote in the answer by @BrashEquilibrium (+1). The accepted and the most upvoted answers in Variance and bias in cross-validation: why does leave-one-out CV have higher variance? give the same reasoning.

HOWEVER, note that Hastie et al. do not give any citations, and while this reasoning does sound plausible, I would like to see some direct evidence that this is indeed the case. One reference that is sometimes cited is Kohavi 1995 but I don't find it very convincing in this particular claim.

MOREOVER, here are two simulations that show that LOOCV either has the same or even a bit lower variance than 10-fold CV:

$\endgroup$
  • 2
    $\begingroup$ could you give the intuition for regression too? $\endgroup$ – xyzzy Mar 21 '14 at 18:06
  • 2
    $\begingroup$ But the average over all $k$ and $n$ folds, respectively averages the same number of cases... $\endgroup$ – cbeleites Mar 22 '14 at 4:27
  • 2
    $\begingroup$ @cbeleites: Yes, certainly. I understood the question as asking about the variance over folds, not over repetitions. Maybe OP could clarify what he or she meant. $\endgroup$ – amoeba Mar 22 '14 at 12:59
  • 3
    $\begingroup$ This answer shows that the variance of a single estimate is higher for LOO than for k-fold. But if I'm not mistaken, in practice the final estimate is taken to be the average of the estimates across all k folds (with k=n in the case of LOO). So the relevant variance is the variance of the mean of the k estimates, right? In which case, for your example of LOO vs. 10-fold, both variance expressions reduce to $p(1-p)/N$ and thus are equal. This would also agree with Corollary 2 here: ai.stanford.edu/~ronnyk/accEst.pdf . Care to comment on this? Have I misunderstood something? $\endgroup$ – Jake Westfall Jul 20 '15 at 20:44
  • 3
    $\begingroup$ @amoeba I've been looking into this and have found many conflicting statements from various sources about whether it's true. Most sources just have a stock statement about the estimates being correlated and then maybe cite ESL. At least one says it doesn't matter (see previous cite). Other sources explicitly say the opposite (e.g., p. 60 here: projecteuclid.org/euclid.ssu/1268143839). I ran a little simulation comparing number of folds $k$ = 2, 5, 10, $n$ which suggests that, at least for multiple regression, variance is smallest for $k=n$. Considering writing an answer with my findings $\endgroup$ – Jake Westfall Jul 21 '15 at 16:31
7
$\begingroup$

From An Introduction to Statistical Learning

When we perform LOOCV, we are in effect averaging the outputs of $n$ fitted models, each of which is trained on an almost identical set of observations; therefore, these ouputs are highly (positively) correlated with each other. In contrast, when we perform $k$-fold CV with $k<n$, we are averaging the outputs of $k$ fitted models that are somewhat less correlated with each other, since the overlap between the training sets in each model is smaller. Since the mean of many highly correlated quantities has higher variance than does the mean of many quantities that are not as highly correlated, the test error estimate resulting from LOOCV tends to have higher variance than does the test error estimate resulting from $k$-fold CV.

To summarize, there is a bias-variance trade-off associated with the choice of $k$ in $k$-fold cross-validation. Typically, given these considerations, one performs $k$-fold cross-validation with $k=5$ or $k=10$, as these values have been shown empirically to yield test error rate estimates that suffer neither from excessively high bias nor from very high variance.

$\endgroup$
2
$\begingroup$
  • In simple cases I think the answer is: the grand mean (over all test cases and all folds) has the same variance for $k$-fold and LOO validation.

  • Simple means here: models are stable, so each of the $k$ or $n$ surrogate models yields the same predicion for the same sample (thought experiment: test surrogate models with large independent test set).

  • If the models are not stable, the situation gets more complex: each of the surrogate models has its own performance, so you have additional variance. In that case, all bets are open whether LOO or $k$-fold has more additional variance*. But you can iterate the $k$-fold CV and taking the grand mean over all test cases and all $i \times k$ surrogate models can mitigate that additional variance. There is no such possibility for LOO: the $n$ surrogate models are all possible surrogate models.

  • The large variance is usually due to two factors:

    • small sample size (if you weren't in a small sample size situation, you'd not be worried about variance ;-) ).
    • High-variance type of error measure. All proportion-of-test-cases-type of classification errors are subject to high variance. This is a basic property of estimating fractions by counting cases. Regression-type errors like MSE have a much more benign behaviour in this respect.

For classification errors, there's a number of papers that looks at the properties of different resampling validation schemes in which you also see variances, e.g.:

(I guess similar papers may exist for regression errors as well, but I'm not aware of them)

* one may expect LOO to have less variance because the surrogate models are trained with more cases, but at least for certain types of classification models, LOO doesn't behave very well.

$\endgroup$
-2
$\begingroup$

It's like taking a test with just one question - it's a lot more hit-and-miss.

This is an intuitive explanation of the standard deviation of an instance versus that of a mean - the score on a batch of instances has less variance.

Here are some more details.

$\endgroup$
  • $\begingroup$ And why is that? Can you expand a little more on this? Right now this is more of a comment than an answer. $\endgroup$ – Andy Jun 19 '15 at 11:08
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. $\endgroup$ – Christoph Hanck Jun 19 '15 at 11:16
  • $\begingroup$ When you take a test with more questions, the score is averaged. And the variance of a mean is less than the variance on a single question, see more details here: Standard deviation of the mean. $\endgroup$ – danuker Jun 19 '15 at 12:06
  • $\begingroup$ @ChristophHanck It's an intuitive explanation, though it's not a complete answer. $\endgroup$ – danuker Jun 19 '15 at 12:07
  • $\begingroup$ That's why I suggested to post it as a comment instead. $\endgroup$ – Christoph Hanck Jun 19 '15 at 12:09
-2
$\begingroup$

There are no folds in LOOCV like k-Fold Cross validation(actually they can be name as folds but meaningless). in LOOCV what it does is leave one Instance from the whole dataset for test data and use all other instances for training. So in each iteration it will leave one instance from the dataset to test.So in a particular iteration of evaluation there is only one instance in the test data and rest are in training data.that is why you saw all the training data sets equal all the time.

In K-fold Cross validation by using Stratification(an advanced method use to balance the data set ensuring that each class represents approximately in equal proportion in all the samples) we can reduce the variance of the estimates.

as LOOCV is using only one instance for testing, it cannot apply Stratification.So LOOCV has a higher variance in error estimates than k-fold cross validation.

$\endgroup$
  • $\begingroup$ -1. I don't see how stratification is relevant here. Do you have any references that support your point of view? $\endgroup$ – amoeba Jul 17 '18 at 21:04

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