# 10-fold cross validation

(5 points) Assume that we are interested in generating a model (e.g., a decision tree) from a sample of examples of a specific size drawn from some distribution. Assume further that we would like to investigate how sensitive the resulting model is to the actual choice of training examples (i.e., how the performance varies over different sets of training examples of the specific size). Assume that we have access to 100 training examples drawn from the underlying distribution. If we are interested in investigating how the performance varies for models generated from 90 examples, would we obtain a reliable estimate of the variance of the model performance by performing a 10-fold cross-validation? Motivate your answer. Is the 10-fold cross validation reliable for estimating the variance of model performance?

• Please, don't just post your homework as is. Tell us what you have done or where you are having difficulties. Homework questions receive a special treatment on this site.
– chl
Sep 30 '12 at 17:12
• It's not an homework. It's an old exam that I am trying to solve before my exam tomorrow. Plus I tried to write my own question regarding this question but it kept seeing it's not enough so I just copied the original question. Sep 30 '12 at 18:26

10 fold cross-validation is known to be a good way to get unbiased or nearly unbiased estimates of the error rates for classification / prediction based on a training set of a given size. If that is what you mean then the answer to your first question is yes.

If you mean by variance how the decision trees, which are different because the training samples differ, performance varies from one training sample of size 90 to another I am not sure. But I do think you could assess that by bootstrap.

• I know that 10 fold cross-validation it gives a good estimate of accuracy but the question is does it give reliable estimate of variance in different models or does it underestimate variance? Sep 30 '12 at 18:28

Cross-validation is not always the magic wand. I've seen some examples in geostatistics, where it may produce biased results.

In particular, for the regression/classification trees, I believe that the resulting variance may be underestimated, because you're sampling from a finite set, not an infinite population. This should depend on the training set size, the bias getting smaller as the set is larger.

• Cross validation still needs the user to take care that the splits are done independently. My guess is that this is a problem in geostatistics (even more than for time series). If that is not the case, then the resulting optimistic bias will also influence the observed variance. May 19 '14 at 18:58

The short answer is: no (but in practice, I think there are two types of situations, where one can still draw conclusions, see below).

Here's some reasoning:

The observed variance has (at least) 3 different contributions.

• a variance due to the finite number of tested cases, which even after pooling the results of the 10 folds cannot exceed the 100 cases that were available in the first place
• we may also say that the true performance of each of the 10 surrogate models varies somewhat. I'll call this the (in)tability with respect to exchanging a few training cases.
Doing iterated $k$-fold cross validation I think we can derive a reasonable guess on the order of magnitude for this variance contribution. From just one run of the cross validation, we cannot derive information about this.
• But the question asks about drawing more samples of 90 cases each from the underlying distribution. We do not know how much larger this instability is compared to the second type. And we cannot measure it as we do not have enough samples to draw disjoint sets of 90 cases.

Literature:

In practice, there are 2 situations where looking at the stability measurements of iterated $k$-fold cross validation nevertheless allows some conclusions.

• If the observed instability due to exchanging a few cases is so large that the model cannot be used for the application. This can be detected.
• There is a huge difference depending on whether the task is to build a model for the (one) given data set (in which case checking the stability against small changes does make sense; this is not so seldom for application-oriented tasks - but the achievable performance for other data sets of the same problem and of the same size may be without any interest as no such data set is available), or whether a statement is needed that in general for a training sample size of $n$, $p \pm sp$ performance will be achieved by algorithm $A$ for the given problem and data type.

• There's a third loosely related situation: calculating the variance due to the finite number of test cases, we may find that the uncertainty on the testing results is too high to allow any kind of conclusions, i.e. that instability doesn't matter because we anyways cannot give any results of the testing that are useful information in practice (if the confidence interval for the true performance ranges from 40 - 100 % correct because the effective sample size was only 3, there are other issues to deal with, and model stability should not be the top priority...)
With "in practice", I mean compared to how precisely the testing result needs to be in order to allow distinction between "good" and "useless" models.