Why does a cross-validation procedure overcome the problem of overfitting a model?
2
-
4$\begingroup$ Look at the works of Alain Celisse. His work as far as I read (too little alas) is about merits of cross-validation. $\endgroup$– mpiktasCommented Apr 1, 2011 at 17:10
-
$\begingroup$ @mpiktas Indeed, and one of his paper was already proposed for the CVJC, mendeley.com/groups/999241/crossvalidated-journal-club/papers. $\endgroup$– chlCommented Apr 1, 2011 at 19:57
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
15
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).
answered Apr 1, 2011 at 16:51
-
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$ Commented Aug 5, 2015 at 14:15
-
4$\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$– jeffCommented Dec 10, 2015 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$ Commented Dec 10, 2015 at 17:33
-
2$\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$ Commented Dec 24, 2016 at 12:11
-
3$\begingroup$ @dikran-marsupial Just realized that my question already was discussed in a number of threads. Here is a specific answer that summarizes different results: stats.stackexchange.com/a/357749/244807. The cited simulation studies indicate that in most cases leave-one-out has lower variance than 10-fold CV and for linear regression this is even known for some time (Burman 1989). There is, however, another argument for LOO not yet mentioned anywhere: the result of LOO is reproducible, i.e, two different researchers obtain the same results on the same data. $\endgroup$– cdalitzCommented Jul 7, 2021 at 9:00
$\begingroup$
$\endgroup$
1
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.
-
12$\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$ Commented Feb 2, 2016 at 16:52
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.
answered Feb 2, 2016 at 20:57
-
5$\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 ABCommented Feb 3, 2016 at 1:49
-
2$\begingroup$ "Here are two concrete situations when cross-validation has flaws" -> "Here are two concrete situations where the DATA has flaws" $\endgroup$– MrRCommented Aug 3, 2021 at 12:55
$\begingroup$
$\endgroup$
24
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.
answered Apr 2, 2011 at 17:40
-
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$ Commented Apr 2, 2011 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$ Commented Apr 3, 2011 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$ Commented Apr 3, 2011 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$ Commented Apr 3, 2011 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$– JMSCommented Apr 4, 2011 at 0:34
$\begingroup$
$\endgroup$
1
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)
-
$\begingroup$ sadly the videos are now all private :-( $\endgroup$ Commented May 11, 2022 at 9:43