25
$\begingroup$

In his paper Linear Model Selection by Cross-Validation, Jun Shao shows that for the problem of variable selection in multivariate linear regression, the method of leave-one-out cross validation (LOOCV) is 'asymptotically inconsistent'. In plain English, it tends to select models with too many variables. In a simulation study, Shao shows that even for as few as 40 observations, LOOCV can underperform other cross-validation techniques.

This paper is somewhat controversial, and somewhat ignored (10 years after its publication, my chemometrics colleagues had never heard of it and were happily using LOOCV for variable selection...). There is also a belief (I am guilty of this), that its results extend somewhat beyond the original limited scope.

The question, then: how far do these results extend? Are they applicable to the following problems?

  1. Variable selection for logistic regression/GLM?
  2. Variable selection for Fisher LDA classification?
  3. Variable selection using SVM with finite (or infinite) kernel space?
  4. Comparison of models in classification, say SVM using different kernels?
  5. Comparison of models in linear regression, say comparing MLR to Ridge Regression?
  6. etc.
$\endgroup$
1
  • $\begingroup$ There must be something in chemometrics books; the only man I know that uses LOO is also doing it. $\endgroup$
    – user88
    Sep 3, 2010 at 17:51

5 Answers 5

18
$\begingroup$

You need to specify the purpose of the model before you can say whether Shao's results are applicable. For example, if the purpose is prediction, then LOOCV makes good sense and the inconsistency of variable selection is not a problem. On the other hand, if the purpose is to identify the important variables and explain how they affect the response variable, then Shao's results are obviously important and LOOCV is not appropriate.

The AIC is asymptotically LOOCV and BIC is asymptotically equivalent to a leave-$v$-out CV where $v=n[1-1/(\log(n)-1)]$ --- the BIC result for linear models only. So the BIC gives consistent model selection. Therefore a short-hand summary of Shao's result is that AIC is useful for prediction but BIC is useful for explanation.

$\endgroup$
11
  • 1
    $\begingroup$ I believe Shao showed that k-fold CV is inconsistent if $k$ is fixed while $n$ grows. $\endgroup$
    – shabbychef
    Sep 4, 2010 at 5:18
  • 1
    $\begingroup$ The BIC has k growing with n. $\endgroup$ Sep 4, 2010 at 5:56
  • 1
    $\begingroup$ I will just silently remind that *IC <--> *CV correspondence from Shao paper works only for linear models, and BIC is equivalent only to k-fold CV with certain k. $\endgroup$
    – user88
    Sep 4, 2010 at 17:26
  • 1
    $\begingroup$ I probably shouldn't have said k-fold. The BIC is equivalent to leave-v-out CV where v=n[1-1/(log(n)-1)] and so it satisfies the Shao consistency criterion. I've updated my answer accordingly. $\endgroup$ Sep 8, 2010 at 11:23
  • 3
    $\begingroup$ @mbq: No -- the AIC/LOO proof by Stone 1977 does not assume linear models. For this reason, unlike Shao's result, it's widely quoted; see for example the model selection chapters in either EOSL or the Handbook of Computational Statistics, or really any good chapter/paper on model selection. It's only a bit more than a page long and worth reading because it's somewhat neat for the way he avoids having to compute the Fisher information/Score to derive the result. $\endgroup$
    – ars
    Sep 12, 2010 at 2:45
7
$\begingroup$

This paper is somewhat controversial, and somewhat ignored

Not really, it's well regarded where the theory of model selection is concerned, though it's certainly misinterpreted. The real issue is how relevant it is to the practice of modeling in the wild. Suppose you perform the simulations for the cases you propose to investigate and determine that LOOCV is indeed inconsistent. The only reason you'd get that is because you already knew the "true" model and could hence determine that the probability of recovering the "true" model does not converge to 1. For modeling in the wild, how often is this true (that the phenomena are described by linear models and the "true" model is a subset of those in consideration)?

Shao's paper is certainly interesting for advancing the theoretical framework. It even provides some clarity: if the "true" model is indeed under consideration, then we have the consistency results to hang our hats on. But I'm not sure how interesting actual simulations for the cases you describe would be. This is largely why most books like EOSL don't focus as much on Shao's result, but instead on prediction/generalization error as a criterion for model selection.

EDIT: The very short answer to your question is: Shao's results are applicable when you're performing least squares estimation, quadratic loss function. Not any wider. (I think there was an interesting paper by Yang (2005?) which investigated whether you could have consistency and efficiency, with a negative answer.)

$\endgroup$
6
  • $\begingroup$ I don't think it is relevant whether I know the true model in the wild. If there is a 'true' model, I would prefer a method which is more likely to find it. $\endgroup$
    – shabbychef
    Sep 12, 2010 at 3:49
  • 2
    $\begingroup$ @shabbychef: I don't disagree. But note: "If there is a 'true' model" and it's under consideration .. how would you know this a priori? $\endgroup$
    – ars
    Sep 12, 2010 at 4:08
  • 1
    $\begingroup$ Note also that my second paragraph actually makes the point in your comment. This is a nice property, but it's not all clear how applicable it is in the wild; even though it's comforting in some sense, it may be misguided. $\endgroup$
    – ars
    Sep 12, 2010 at 4:13
  • 2
    $\begingroup$ @ars - note that the "linearity" of the 'true' model is not the only way to recover the 'true' model from a linear model. If the non-linear component of the 'true' model can be well modelled by the noise term (e.g. non-linear effects tend to cancel each other out) then we could reasonably call the linear model 'true' I think. This is similar to assuming the remainder in a linear taylor series is negligible. $\endgroup$ Dec 13, 2011 at 15:03
  • 2
    $\begingroup$ So you can re-state the results as: if there exists a reasonable linear approximation to reality, then BIC / leave-$v$-out will consistently find that approximation. AIC / leave-one-out will not consistently find it. $\endgroup$ Dec 13, 2011 at 15:04
6
$\begingroup$

I would say: everywhere, but I haven't seen a strict proof of it. The intuition behind is such that when doing CV one must hold a balance between train large enough to build sensible model and test large enough so it would be a sensible benchmark.
When dealing with thousands of pretty homogeneous objects, picking one is connected with risk that it is pretty similar to other object that was left in the set -- and then the results would be too optimistic.
On the other hand, in case of few objects there will be no vital difference between LOO and k-fold; $10/10$ is just $1$ and we can't do anything with it.

$\endgroup$
4
  • $\begingroup$ Beyond proofs, I'm wondering if there have been simulation studies of any of the five cases I list, for example. $\endgroup$
    – shabbychef
    Sep 8, 2010 at 17:27
  • $\begingroup$ Wanna make some? $\endgroup$
    – user88
    Sep 8, 2010 at 17:58
  • 2
    $\begingroup$ I do; I'm going to have to learn a lot more R, though, to share the results here, though. $\endgroup$
    – shabbychef
    Sep 9, 2010 at 21:16
  • 1
    $\begingroup$ @shabbychef: ever got to do this? And by the way, if you're still counting chemometricians who do or do not use CV for variable selection, you can count me on the side of those who refuse to do it, because a) I've not yet had any real data set with enough cases (samples) to allow even a single model comparison, and b) for my spectroscopic data, the relevant information is usually "smeared" over large parts of the spectrum, so I prefer regularizationthat does not do a hard variable selection. $\endgroup$ Nov 24, 2013 at 13:43
4
$\begingroup$

1) The answer by @ars mentions Yang (2005), "Can The Strengths of AIC and BIC Be Shared?". Loosely speaking, it seems that you can't have a model-selection criterion achieve both consistency (tend to pick the correct model, if there is indeed a correct model and it is among the models being considered) and efficiency (achieve the lowest mean squared error on average among the models you picked). If you tend to pick the right model on average, sometimes you'll get slightly-too-small models... but by often missing a real predictor, you do worse in terms of MSE than someone who always includes a few spurious predictors.

So, as said before, if you care about making-good-predictions more than getting-exactly-the-right-variables, it's fine to keep using LOOCV or AIC.

2) But I also wanted to point out two other of his papers: Yang (2006) "Comparing Learning Methods for Classification" and Yang (2007) "Consistency of Cross Validation for Comparing Regression Procedures". These papers show that you don't need the ratio of training-to-testing data to shrink towards 0 if you're comparing models which converge at slower rates than linear models do.

So, to answer your original questions 1-6 more directly: Shao's results apply when comparing linear models to each other. Whether for regression or classification, if you are comparing nonparametric models that converge at a slower rate (or even comparing one linear model to one nonparametric model), you can use most of the data for training and still have model-selection-consistent CV... but still, Yang suggests that LOOCV is too extreme.

$\endgroup$
0
$\begingroup$

I believe Shao's article applies most effectively to situations where a person is trying to eliminate predictors from a model (whether linear or non-linear, such as machine learning, etc.), and he recommends using Monte Carlo CV (MCCV) in this case.

On the other hand, if you are not worried about the size (number of factors/predictors) in your model, LOOCV might be a shorter and somewhat more intuitive method, which is probably why it is used and accepted so widely.

$\endgroup$
5
  • $\begingroup$ please add a reference for your link in case it dies in the future. Thanks! $\endgroup$
    – Antoine
    Feb 19, 2020 at 17:21
  • $\begingroup$ @Antoine here is a link to the original paper by Shao (let me know if that is not what you are after): amstat.tandfonline.com/doi/abs/10.1080/01621459.1993.10476299 $\endgroup$
    – brethvoice
    Feb 19, 2020 at 18:53
  • $\begingroup$ @Antoine the original 1993 paper is behind significant paywalls. I am also looking at this paper for alternatives which was originally published on ArXiv and is now in Biometrika: academic.oup.com/biomet/article/107/2/489/5715611 $\endgroup$
    – brethvoice
    Apr 25, 2022 at 20:55
  • 1
    $\begingroup$ I found a PDF version of the original paper by pasting its title into Google Scholar: libpls.net/publication/MCCV_Shao_1993.pdf $\endgroup$
    – Antoine
    Apr 25, 2022 at 22:50
  • $\begingroup$ @Antoine unfortunately that copy violates the terms under which it was downloaded and is technically illegal. Which is sad because the paper is, in my estimation, extremely valuable and I never would have been able to read it had someone not illegally posted it. I have access to a brick-and-mortar technical library which almost certainly will allow me to photocopy the article for professional use from its paper holdings. $\endgroup$
    – brethvoice
    Apr 27, 2022 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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