# Does the cross validation implementation influence its results?

As you know, there are two popular types of cross-validation, K-fold and random subsampling (as described in Wikipedia). Nevertheless, I know that some researchers are making and publishing papers where something that is described as a K-fold CV is indeed a random subsampling one, so in practice you never know what is really in the article you're reading.
Usually of course the difference is unnoticeable, and so goes my question -- can you think of an example when the result of one type is significantly different from another?

You can certainly get different results simply because you train on different examples. I very much doubt that there's an algorithm or problem domain where the results of the two would differ in some predictable way.

• I meant significantly different results. I also think there is none, at least real-world example. Still, I think I'll wait some time more.
– user88
Commented Jul 24, 2010 at 9:04

Usually of course the difference is unnoticeable, and so goes my question -- can you think of an example when the result of one type is significantly different from another?

I am not sure at all the difference is unnoticeable, and that only in ad hoc example it will be noticeable. Both cross-validation and bootstrapping (sub-sampling) methods depend critically on their design parameters, and this understanding is not complete yet. In general, results within k-fold cross-validation depend critically on the number of folds, so you can expect always different results from what you would observe in sub-sampling.

Case in point: say that you have a true linear model with a fixed number of parameters. If you use k-fold cross-validation (with a given, fixed k), and let the number of observations go to infinity, k-fold cross validation will be asymptotically inconsistent for model selection, i.e., it will identify an incorrect model with probability greater than 0. This surprising result is due to Jun Shao, "Linear Model Selection by Cross-Validation", Journal of the American Statistical Association, 88, 486-494 (1993), but more papers can be found in this vein.

In general, respectable statistical papers specify the cross-validation protocol, exactly because results are not invariant. In the case where they choose a large number of folds for large datasets, they remark and try to correct for biases in model selection.

• No, no, no, it is about machine learning not model selection.
– user88
Commented Jul 24, 2010 at 23:09
• Interesting distinction. I thought model selection was central to machine learning, in almost all meanings of the term. Commented Jul 25, 2010 at 2:40
• All those things work for trivial (mostly linear) models when you have few parameters and you just want to fit them to data to say something about it, like you have y and x and you want to check whether y=x^2 or y=x. Here I talk about estimating error of models like SVMs or RFs which can have thousands of parameters and are still not overfitting due to complex heuristics.
– user88
Commented Jul 25, 2010 at 8:22
• These results are valid for regression of general linear models with arbitrary number of independent variables. The variables can be arbitrary learners. The crucial assumption is that as the number of observations goes to infinity the number of learners describing the true model stays finite. All of this works for regression, so for a classification task like yours I am not sure it helps. Commented Jul 25, 2010 at 20:57
• It does not; GLM is not machine learning. True machine learning methods are wise enough to hold their level of complexity independent of growing number of objects (if it is sufficient of course); even for linear models this whole theory works quite bad since the convergence is poor.
– user88
Commented Jul 29, 2010 at 7:43