cross-validation and over-fitting

I am performing model evaluation (via maximum likelihood) on several datasets with a number of different classes of models.

I have reasons to suspect that a specific class of models is (much) more flexible than the others, and therefore measures such as AIC might favour this more flexible class due to the risk of over-fitting. One of the reasons is that, for example, when I switch to BIC results change dramatically (although it is fair to say that BIC might be over-penalizing model complexity).

Therefore, I performed a 10-fold cross validation on stratified data ($9/10$-th training, $1/10$-th test), and evaluated the models using the sum (or average) log likelihood on the hold out test data, as an estimate of model out-of-sample performance.

To my surprise, the model class that I thought was more flexible(*) won the model comparison under 10-fold CV.

• Should I conclude that there is no over-fitting going on, notwithstanding the mixed evidence from other metrics (e.g., BIC) and prior information?
• Are there other tests you would perform to verify that this model class is (not) winning out of additional flexibility?

(*) Edit: not just more flexible, but excessively more flexible.

• You appear to expect minimizing AIC to lead to overfitting. What leads you to that expectation? Mar 14 '16 at 4:11
• Among other things, the posterior landscape for this class of models is very complex -- I doubt that a point estimate can capture what's going on -- it might be unrepresentative. By the way, I am re-checking the results of the CV and I find a strange thing: the summed log likelihood evaluated on test folds is often hugely better than the log-like at the MLE for the full datasets. I would have expected the log-like summed over test folds to be less than (or at best about the same as) the log-like obtained on the full data -- since in the latter case train and test sets coincide. Uhm... Mar 14 '16 at 6:09

I have reasons to suspect that a specific class of models is more flexible than the others, and therefore measures such as AIC might favour this more flexible class due to over-fitting.

A few points of clarification

• The fact that a more flexible model fits better is a very natural thing and by no means indicates overfitting. A model can be either not flexible enough (underfitting), and too flexible (overfitting).
• The most common methods to find the right degree of flexibility include AIC, BIC and CV, where AIC and CV are closely related, see 1). The fact that AIC and BIC differ for large datasets is well-known.
• Which of them is best has been subject to extended debates, with no clear answer. In any case, both AIC and CV are means to avoid overfitting (with AIC having a bit of reputation for favoring too complex models).

To summarize, I don't see a general problem with choosing the model that is favored by your 10-fold CV.

1) Stone, M. (1977) An Asymptotic Equivalence of Choice of Model by Cross-Validation and Akaike's Criterion. Journal of the Royal Statistical Society. Series B (Methodological), 39, 44-47.

• If I recall correctly from a previous discussion on this site, aic is asymptotically LOOCV and BIC is K-fold CV for (asymptotically) equivalent to for a large K that is a complicated function of the sample size.
– meh
Mar 13 '16 at 17:41
• (+1) Thanks. I am aware of all these basic points in model comparison, the differences between metrics (AIC, BIC, DIC, WAIC, LOO-CV, etc.) and their asymptotic properties. My point is that I have a strong prior from other lines of reasoning that this class of models might be winning for the wrong reason (e.g., excess flexibility). I understand that the 10-fold CV is a pretty strong result, so perhaps I have to look elsewhere to find a problem with the model (if any). Mar 13 '16 at 22:14
• (I would probably be happier if I could compute the full marginal likelihoods of the models and be fully Bayesian about it, but it's intractable. Even MCMC is really hard to perform on this model space, that's why I am sticking to point estimates.) Mar 13 '16 at 22:23

There is another simple answer: a bug in the code. Whops. After a long debugging session, I found a subtle indexing mistake in the script that was reading the results of the 10-fold CV.

I am writing this as a separate answer because I feel it might be instructive...

What pointed me to the existence of a bug, expectations aside, was that the predictions of the CV on test folds would often beat the predictions based on MLE results obtained by training on the full dataset. This should not happen, or at least be extremely unlikely, and it is a clear signal that there is a mistake somewhere.

Now the results that I get are better aligned with previous information. The model that I believed to be "exceedingly flexible" is not consistently best any more. As expected, the result of the 10-fold CV across models happens to be somewhat in-between what AIC and BIC predict.

• By the way, I was tempted to delete this question, but I am leaving it since there is another valuable answer on this thread, which still holds beyond my specific resolution. Also, the way in which I found my mistake, albeit very simple, may be useful to someone. Mar 14 '16 at 17:46