What if cross-validation fails to prevent overfitting

Question

I'm training a random forest model with AUC as performance metric. I've splitted my data to train set (70%) and test set (30%) and performed cross-validation on train set to tune the hyperparameters. As for now, I've ended up with a model that has ~0.95 AUC on the training data, ~0.85 AUC in cross-validation process and ~0.84 AUC on the test data. It seems to me that cross-validation failed in that case and although it estimate test error pretty nice, my model is overfitting. I know that one way to prevent overfitting is to get more data, but it's usually not possible (as in this case). In case of linear or logistic regression I could remove some features as well, but I think random forests naturally ignores features that are irrelevant. Why, despite using cross-validation, my model overfits? What can be done to resolve that issue?

Answer 1

1. your performanc numbers are meaningless without knowing the uncertainty these estimates have.
   The main factor influencing them here is the absolute number of cases tested. In other words, unless you have a huge data set (which seems unlikely as you say more data is out of question - that's typically an indicator of small sample sizes), a 0.01 difference in observed AUC is unlikely to be significant.

2. Cross validation in itself is not supposed to do anything about overfitting. It is a verification procedure that helps estimating a particular type of generalization error. It is up to you to prevent overfitting.

3. Cross validation can only correctly estimate generalization error if the splitting procedure actually achieves statistical independence between the splits.
   So the most frequent answer to "why did cross validaton not prevent me from overfitting?" is that the splitting was not done correctly.
   Still, I don't see indication of overfitting in your case so far.

4. Random forests are set up in a way that the individual trees are assumed to overfit. In terms of predictive power there cannot be too many trees. You can have too few trees, causing the random forest's predictions to be unstable. You may consider this overfitting - but we don't have any evidence here that this actually the case.

5. There are dedicated ways to measure model instability - which is more closely related to overfitting than observing differences between training and generalization error.
   For example, you can measure instability in prediction via iterated/repeated cross validation by comparing predictions for the same case. More details in our paper Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008).
   DOI: 10.1007/s00216-007-1818-6

   Overfitting means that the model is too complex, i.e. it fits some noise in the training data. If you consider model space, in a situation of overfitting, classifiers trained on (even slightly) different training points will have different class boundaries.

   Note that if we're talking prediction, we can distinguish between differences in the model that don't hurt prediction (e.g. if the random forest switches back and forth which of a bunch of collinear predictors it actually uses) and differences that cause changes in prediction.

   Two rather direct ways of checking instability caused by overfitting are a) checking the actual model (difficult for random forest, but easy e.g. for linear models) and checking where the class boundaries (or the regression function) lies in sample space and whether that changes between our different models. The latter doesn't care about instability inside the model that doesn't affect prediction.

   One way of doing the latter is having a number of such models predict the same test cases and then looking at the variation we observe. This can be done e.g. using the surrogate models of a k-fold cross validation, but also by calculating surrogates from the internals of an out-of-bag calculation.
   The indication we get this way is more sensitive to instability in the predictions than looking at the overall error as the effect on overall error can be small if the difference in predictions leads just to other (but not necessarily more) cases being misclassified.