Inner loop overfitting in nested cross-validation

Question

I have implemented nested cross validation in Matlab for a classification problem. I have 56 features and 408 cases. I am performing feature and model selection in the inner cross-validation loop, using 10 fold CV for both inner and outer loops.

In the inner CV loop I employ a sequential forward feature selection procedure, nested inside a grid search to determine the optimum regularization parameters for a given regularized discriminant classifier model and selected feature set. I am finding very poor performance on the outer loop CV (when compared to a standard quadratic discriminant classifier, obtained with single loop CV), leading me to conclude I am overfitting in the inner CV loop.

I have read papers by Cawley and Talbot that show that biased model selection protocols favour worse models, and furthermore, that the inner loop procedure alone produces a biased performance estimate.

Does this explain the overfitting observed for the inner loop in nested CV?

Are there any practical strategies to avoid this overfitting?

Answer 1

Overfitting in model selection problems for classification is usually due to including too many parameters. Cross-validation or bootstrap error rate estimation should avoid this problem because it avoids the optimism of an estimate like resubstitution which tests the classifier on the same data used in the fit. If you minimize the cross-validated estimate of error rate in your inner loop as the criterion for variable selection you should not have this problem. Am I correct in assuming that your selection procedure does not do this? If so you are probably using a procedure that is biased toward models with many parameters that may be poor models for prediction.

Answer 2

I know it's an old thread, but anyway...

When I've designed algorithms to perform feature selection within a nested cross-validation, I've found that you can decrease overfitting to the inner segments by performing recursive elimination and making sure that you'll resample the inner segments for each iteration of the recursive feature elimination rather than performing full ranking/selection for each inner segment.

Answer 3

To answer my own question (I realize this material is probably actually stated elsewhere on this site):

I have found that when using complex classifier models (such as an SVM with an RBF kernel or an regularized discriminant classifier) there can be extremely large variance between folds in cross validation, if a large proportion of the data is withheld for testing within each fold.

I have found a practical strategy for nested cross-validation is to use leave one out cross validation for the outer loop and k-fold cross validation (in my case k=10) for the inner loop.

While this approach does mean that the final performance estimate has a larger variance, I have found it results in a 'better' model; as a larger proportion of data are used to find the optimal model in the inner CV loop.

Answer 4

This is an old question, but I want to leave an answer in case anyone stumbles on this thread and happens to have made the same novice mistake as me.

I consistently found my errors on the outer CV loop were higher than the inner loops, even with very careful cross-validation in both loops (stratified, repeated in the inner loop).

My mistake was actually that I was re-scaling the outer CV test data in the wrong way: I was using the mean and s.d. of the test data, rather than using the same scaler as was used for the training data (see for example here). Doing it the right way resolved the problem.