# How does cross-validation overcome the overfitting problem?

Why does a cross-validation procedure overcome the problem of overfitting a model?

I can't think of a sufficiently clear explanation just at the moment, so I'll leave that to someone else; however cross-validation does not completely overcome the over-fitting problem in model selection, it just reduces it. The cross-validation error does not have a negligible variance, especially if the size of the dataset is small; in other words you get a slightly different value depending on the particular sample of data you use. This means that if you have many degrees of freedom in model selection (e.g. lots of features from which to select a small subset, many hyper-parameters to tune, many models from which to choose) you can over-fit the cross-validation criterion as the model is tuned in ways that exploit this random variation rather than in ways that really do improve performance, and you can end up with a model that performs poorly. For a discussion of this, see Cawley and Talbot "On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation", JMLR, vol. 11, pp. 2079−2107, 2010

Sadly cross-validation is most likely to let you down when you have a small dataset, which is exactly when you need cross-validation the most. Note that k-fold cross-validation is generally more reliable than leave-one-out cross-validation as it has a lower variance, but may be more expensive to compute for some models (which is why LOOCV is sometimes used for model selection, even though it has a high variance).

• One thought I've had is that cross validation is merely applying a different (implicit) model for the data. You can certainly show this with the "cousin" of CV, the non-parametric bootstrap (which is based on a Dirichlet Process model with concentration parameter of 0). – probabilityislogic Aug 5 '15 at 14:15
• Interesting idea. My view is that (for the models I am interested) the separation into parameters and hyper-parameters is computational rather than logical; the hyper-parameters are still parameters that need to be fitted to the data, and that doing this indirectly using cross-validation doesn't really change that. In may last paper, I investigated tuning what are normally hyper-parameters of a kernel model using the training criterion and adding an additional regularisation term to avoid overfitting the model selection criterion (LOOCV) and it worked quite well. – Dikran Marsupial Aug 7 '15 at 6:57
• Why is k-fold CV is more expensive than leave-one-out? My experience (and my intuition) says otherwise. Since in k-fold CV we are doing k tests, wherever in L1O, we are doing N (>>k) tests, and usually the training part takes longer due to some matrix inversion, so isn't L1O the expensive option? – jeff Dec 10 '15 at 17:30
• Leave one out can be performed (or approximated) as a by-product of fitting the model to the whole dataset, at very little additional cost, for a wide range of models (e.g. linear regression). I'll edit the answer to make this more clear. – Dikran Marsupial Dec 10 '15 at 17:33
• My understanding of leave-one-out is that it is k-fold CV -- the best but most computationally expensive form of k-fold CV, where k = dataset size. – Daniel Winterstein Dec 24 '16 at 12:11

My answer is more intuitive than rigorous, but maybe it will help...

As I understand it, overfitting is the result of model selection based on training and testing using the same data, where you have a flexible fitting mechanism: you fit your sample of data so closely that you're fitting the noise, outliers, and all the other variance.

Splitting the data into a training and testing set keeps you from doing this. But a static split is not using your data efficiently and your split itself could be an issue. Cross-validation keeps the don't-reward-an-exact-fit-to-training-data advantage of the training-testing split, while also using the data that you have as efficiently as possible (i.e. all of your data is used as training and testing data, just not in the same run).

If you have a flexible fitting mechanism, you need to constrain your model selection so that it doesn't favor "perfect" but complex fits somehow. You can do it with AIC, BIC, or some other penalization method that penalizes fit complexity directly, or you can do it with CV. (Or you can do it by using a fitting method that is not very flexible, which is one reason linear models are nice.)

Another way of looking at it is that learning is about generalizing, and a fit that's too tight is in some sense not generalizing. By varying what you learn on and what you're tested on, you generalize better than if you only learned the answers to a specific set of questions.

From a Bayesian perspective, I'm not so sure that cross validation does anything that a "proper" Bayesian analysis doesn't do for comparing models. But I am not 100% certain that it does.

This is because if you are comparing models in a Bayesian way, then you are essentially already doing cross validation. This is because the posterior odds of model A $M_A$ against model B $M_B$, with data $D$ and prior information $I$ has the following form:

$$\frac{P(M_A|D,I)}{P(M_B|D,I)}=\frac{P(M_A|I)}{P(M_B|I)}\times\frac{P(D|M_A,I)}{P(D|M_B,I)}$$

And $P(D|M_A,I)$ is given by:

$$P(D|M_A,I)=\int P(D,\theta_A|M_A,I)d\theta_A=\int P(\theta_A|M_A,I)P(D|M_A,\theta_A,I)d\theta_A$$

Which is called the prior predictive distribution. It basically says how well the model predicted the data that was actually observed, which is exactly what cross validation does, with the "prior" being replaced by the "training" model fitted, and the "data" being replace by the "testing" data. So if model B predicted the data better than model A, its posterior probability increases relative to model A. It seems from this that Bayes theorem will actually do cross validation using all the data, rather than a subset. However, I am not fully convinced of this - seems like we get something for nothing.

Another neat feature of this method is that it has an in built "occam's razor", given by the ratio of normalisation constants of the prior distributions for each model.

However cross validation seems valuable for the dreaded old "something else" or what is sometimes called "model mispecification". I am constantly torn by whether this "something else" matters or not, for it seems like it should matter - but it leaves you paralyzed with no solution at all when it apparently matters. Just something to give you a headache, but nothing you can do about it - except for thinking of what that "something else" might be, and trying it out in your model (so that it is no longer part of "something else").

And further, cross validation is a way to actually do a Bayesian analysis when the integrals above are ridiculously hard. And cross validation "makes sense" to just about anyone - it is "mechanical" rather than "mathematical". So it is easy to understand what is going on. And it also seems to get your head to focus on the important part of models - making good predictions.

• The model mispecification issue is the key. Bayesian methods (especially the "poor-mans" Bayes of evidence maximisation) can perform very poorly under model misspecification, whereas cross-validation seems to work pretty well almost all the time. The gain when the assumptions (priors) are "right" is generally much smaller than the penalty when they are "wrong", so cross-validation wins on average (as it makes almost no assumptions). It isn't nearly as intellectually satisfying though! ;o) – Dikran Marsupial Apr 2 '11 at 17:54
• @dikran - interesting. I'm not so sure I agree with what you say though. So you say if the model is mispecified, then cross validation with that same model is better than using Bayes theorem? I would like to see an example of this. – probabilityislogic Apr 3 '11 at 0:16
• @probabiltyislogic I don't think it is a particularly new observation, Rasmussen and Williams mention it on page 118 of their excellent Gaussian Process book (although it is essentially a reference to a similar comment in Grace Wahba's monograph on splines). Essentially the marginal likelihood is the probability of the data given the assumptions of the model, whereas the XVAL likelihood is an estimate of the probability of the data, regardless of the model assumptions, hence more reliable when the assumptions are not valid. A proper empirical study would be useful. – Dikran Marsupial Apr 3 '11 at 14:06
• @probabilityislogic I should add that I like the Bayesian approach to model selection, but I almost always used cross-validation in practice simply because it generally gives results that are (statistically) as good as, or better than Bayesian approaches. – Dikran Marsupial Apr 3 '11 at 14:08
• Cross validation selects models based solely on predictive performance; marginal likelihoods don't - they "account" for every dimension. In very high dimensional settings this matters - sometimes a lot. Say you've got a big predictor vector $X_i$ and a 1 dimensional response $y_i$. You need a model for $X_i$ to do dimension reduction in a fully Bayesian way. So you specify a joint model as $p(y_i|X_i, \theta_y)p(X_i|\theta_X)$. The second term has a much bigger contribution to the likelihood, so if a model does well there and bites it on the prediction the marginal likelihood won't care. – JMS Apr 4 '11 at 0:34