34
$\begingroup$

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

$\endgroup$
24
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – probabilityislogic Aug 5 '15 at 14:15
  • $\begingroup$ 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. $\endgroup$ – Dikran Marsupial Aug 7 '15 at 6:57
  • 2
    $\begingroup$ 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? $\endgroup$ – jeff Dec 10 '15 at 17:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Dikran Marsupial Dec 10 '15 at 17:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Winterstein Dec 24 '16 at 12:11
20
$\begingroup$

Not at all. However, cross validation helps you to assess by how much your method overfits.

For instance, if your training data R-squared of a regression is 0.50 and the crossvalidated R-squared is 0.48, you hardly have any overfitting and you feel good. On the other hand, if the crossvalidated R-squared is only 0.3 here, then a considerable part of your model performance comes due to overfitting and not from true relationships. In such a case you can either accept a lower performance or try different modelling strategies with less overfitting.

| cite | improve this answer | |
$\endgroup$
  • 9
    $\begingroup$ I think this answer is correct in spirit, but I disagree with the characterization of over fitting in the second paragraph. I don't believe that over fitting occurs when train error - test error > some bound, instead, I would characterize over fitting as a situation where increasing the complexity of the model slightly tends to increase the hold out error. Requiring that your train and test errors are comparable will often result in very underfit models. $\endgroup$ – Matthew Drury Feb 2 '16 at 16:52
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

Cross-Validation is a good, but not perfect, technique to minimize over-fitting.

Cross-Validation will not perform well to outside data if the data you do have is not representative of the data you'll be trying to predict!

Here are two concrete situations when cross-validation has flaws:

  • You are using the past to predict the future: it is often a big assumption to assume that past observations will come from the same population with the same distribution as future observations. Cross-validating on a data set drawn from the past won't protect against this.
  • There is a bias in the data you collect: the data you observe is systematically different from the data you don't observed. For example, we know about respondent bias in those who chose to take a survey.
| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Having your dataset not being a poor representation of the true population is generally considered a separate issue of over fitting. Of course, it is correct that cross-validation does not address them. $\endgroup$ – Cliff AB Feb 3 '16 at 1:49
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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) $\endgroup$ – Dikran Marsupial Apr 2 '11 at 17:54
  • 2
    $\begingroup$ @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. $\endgroup$ – probabilityislogic Apr 3 '11 at 0:16
  • $\begingroup$ @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. $\endgroup$ – Dikran Marsupial Apr 3 '11 at 14:06
  • $\begingroup$ @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. $\endgroup$ – Dikran Marsupial Apr 3 '11 at 14:08
  • $\begingroup$ 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. $\endgroup$ – JMS Apr 4 '11 at 0:34
2
$\begingroup$

Also I can recomend these videos from the Stanford course in Statistical learning. These videos goes in quite depth regarding how to use cross-valudation effectively.

Cross-Validation and the Bootstrap (14:01)

K-fold Cross-Validation (13:33)

Cross-Validation: The Right and Wrong Ways (10:07)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.