Bias in classifier model selection

Question

Say I have a set of classifier models, each generated using feature selection inside a repeated k-fold cross-validation. Each classifier model is generated using a different set of regularization parameters or hyperparameters.

I understand that choosing the 'best' model of this set, i.e. one that yields best k-fold cross validation classication estimate could produce an optimistically biased estimate of generalized performance. However is bias avoided if the final performance estimate, is based on a separate repeated k-fold cross validation using the features and hyperparameters selected above?

I have found this procedure (10 folds, 10 repetitions) works well in practice (model appears stable on genuinely unseen data) on a data set with Cases > Features however I wonder if any remaining bias could be considered unacceptable? I suspect this procedure is less acceptable in the case where Features >> Cases

My question is related to Training with the full dataset after cross-validation?

Apologies if this question appears ignorant or repeats material discussed elsewhere.

Answer 1

The key question is "have the test examples in the final cross-validation been involved in selecting any aspect of the model"; if the answer is "yes" then the performance estimate is likely to be biased. If the answer is "no" then it is probably unbiased.

For example nested cross-validation is fine (as all model choices are determined using only the examples in the "training" partition of the outer cross-validation. If you use repeated cross-validation to set the hyper-parameters or select features and then use repeated cross-validation (using a different set of random partitionings) then that will give a biased performance estimate, as all of the data have influenced a choice about the model evaluated by the second cross-validation.

Answer 2

There is a difference between repeated cross-validation and nested-cross validation. The latter is useful for determining hyper-parameters and selecting features.

I've seen a couple of recent papers about the bias-variance implications of repeated cross-validation. Rodriguez and Lozano (IEEE T.PAMI 2010) test on artificial datasets (based on parameterisations of a single mixture model) and conclude that repeated cross-validation is useful and reduces variance, while the inner k-fold cross-validation gives a tradeoff between bias and variance (with k = 5 or 10 recommended for comparing algorithms as a reasonable tradeoff) - they used 10 repetitions, but anything from 2 or 3 to 20 or 30 is reasonable in my experience. The exact tradeoff and relation to the "true" accuracy depends on the dataset.

Vanwinckelen and Blockeel (2012) explore with 9 of the larger UCI datasets, with subsets of 200 and 1000 used for cross-validation, and the full dataset used to approximate the full population. For 10-CV typically all but a couple of "true" accuracies are within the confidence interval determined by the 10-CV, but for 10x10-CV and 30x10-CV all but a couple are outside the confidence interval. Also for all but a couple, the difference between the estimated and true accuracy is better for the 1000 than the 200 samples. These datasets vary in size (and we may already use 30% of the data) so their representativeness of the population is an unwarranted assumption, and this usage is thus in fact also artificial. But the contradictory results of the two papers nonetheless do seem valid for their data, however, I think the truth, and the ideal approach, lies somewhere between.

For CxK-CV increase C by a factor of four halves the size of the confidence interval. But you are still using the same data different ways, and this apparent reduction of variance will in the end become increasingly spurious (because the independence assumption is violated). For the artificial data with the simple mixture model of the first study, 10x10-CV seems to remain within the useful range, but for most of the real datasets, the 10 repetitions seems already to be too much.

I tend to use 2x5-CV (not 5x2-CV as recommended by Dietterich) if I am not too tight on data. Where we are really scrabbling for enough data (in very large very hard signal processing problems) but can't afford to do LOO, we use Cx20-CV with C up to 10, but using an early-stopping significance-estimating technique to stop when no significant improvement can be expected, typically avoiding half the runs, suggesting that C of 5 suffices. See: David M W Powers and Adham Atyabi, “The Problem of Cross-Validation: Averaging and Bias, Reptition and Significance”, Spring World Congress on Engineering and Technology, Xian China, May 2012, IEEE USA, V2:93-97

What is lacking at the moment is good ways of seeing how many repetitions are useful, and when the reduction in variance increasing CxK-CV purports to achieve actually ceases to be real. The repetition count C of 5 is a compromise between the for and against recommendations of the two papers I cited earlier, and using the original variance for the confidence interval, and the repetition just to improve the estimate, is a suggestion of the agin paper. But really we need a method of assessing when this is, an early stopping technique like in our paper that avoids being led astray by underestimation - though we saw no sign of this in our studies on real data we really have no way of knowing as we used all the data we available for the CxK-CV.