At what point does cross-validation become overtraining?

Question

I've often worked on projects for which the data is plentiful enough that I can do k-fold cross validation (k=5 or k=10, typically). In my experience, I've used this as a way to compare different model development methods or as a way to test the predictions of a model by leaving 10-20% out per round and predicting those when not part of the model. Standard stuff there.

Recently, I've seen some work in which cross-validation is used to build up the model. For example, consider forward step-wise feature selection in which each co-variate entering the model is selected based upon the k-fold cross-validation performance as I described above. This seems OK but in my mind this starts to become overly optimistic and maybe bordering on over-training.

Further, I've seen this done in which multiple runs of the cross-validation are done. In this case, it would be 10 or more independent runs of k-fold cross-validation, and the results of all of those runs aggregated to select co-variates. To me, this starts to defeat the whole purpose of the cross-validation.

This multiple run approach does generate a distribution of performance values that would be useful to compare different methods, but for the purposes of building the model itself, it seems to border on overtraining.

Have there been any evaluations of the effects of this type of approach on the resulting model and its ability to generalize? I have searched and cannot find anything that address it in the way I described.

Answer 1

Over-optimism with cross validation for stepwise feature selection

As @KarlOveHufthammer already explained, using cross validation for (step-wise) feature selection means that the cross validation is part of the model training. More generally, this applies to all kinds of data-driven feature selection, model comparison or optimization procedures.

And yes, the problem of overfitting is much more pronounced for iterative training procedures such as a forward selection.

(And I think he means that step-wise feature selection usually isn't a good idea - IMHO it would be better to use a regularization that selects features, e.g. LASSO)

Iterated/Repeated $k$-fold cross validation defeating its purpose?

Iterated aka repeated cross validation covers a particular source of variance in the modeling-testing calculations: the instability of predictions due to slight changes in the composition of the training data, i.e. a particular view on model instability. This is very useful information in case you want to build a predictive model from the particular data set you have at hand (for the particular application). This variance you can measure and successfully reduce by repeated/iterated cross validation (same holds for out-of-bootstrap).

Another practically very important source of variance at least for classifier validation results is the variance due to the finite number of test cases. Repeating the cross validation does not change the actual number of independent test cases, so neither is the variance caused by this affected by the repetitions. In small sample size situations and in particular with figures of merit which are proportions of tested cases (overall accuracy, sensitivity, specificity, predictive values etc.) which suffer from high variance, this second source of variance may be the dominating factor of uncertainty.

This multiple run approach does generate a distribution of performance values that would be useful to compare different methods

Be careful here: CV does not cover the variance between training sets of size $n_{train}$ drawn freshly from the underlying population, only the variance for exchanging a few cases (slightly disturbing the training data) is covered. So you may be able to compare different methods for the data set at hand, but strictly speaking you cannot extend that conclusion to a data set of size $n$.

So there's a big difference here whether your focus is on solving the application problem (with whatever method) from the data set at hand or whether you interest are the properties of the method or the underlying population and you don't care for the particular data set as it is just an example.

This difference is the part of variance that is underestimated by cross validation from Bengio's point of view (their focus is on the methods, so they would need the variance between disjunct data sets) in
Bengio, Y. and Grandvalet, Y. No Unbiased Estimator of the Variance of K-Fold Cross-Validation Journal of Machine Learning Research, 2004, 5, 1089-1105.