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?
 A: 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.
A: 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.
A: Old question, new answers...
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:


*

* Bengio, Y. & Grandvalet, Y. No Unbiased Estimator of the Variance of K-Fold Cross-Validation, Journal of Machine Learning Research, 5, 1089-1105 (2004). 

*Here's one of my papers, where you can see the three different views on the variance compared in fig. 3 and 4 (read the small print: the variation including the test set size is already averaging the $k$ folds):  Beleites, C.; Neugebauer, U.; Bocklitz, T.; Krafft, C. & Popp, J. Sample size planning for classification models., Anal Chim Acta, 760, 25-33 (2013). DOI: 10.1016/j.aca.2012.11.007

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.
