23
$\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$
  • $\begingroup$ There must be something in chemometrics books; the only man I know that uses LOO is also doing it. $\endgroup$ – user88 Sep 3 '10 at 17:51
14
$\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$
  • 1
    $\begingroup$ I believe Shao showed that k-fold CV is inconsistent if $k$ is fixed while $n$ grows. $\endgroup$ – shabbychef Sep 4 '10 at 5:18
  • 1
    $\begingroup$ The BIC has k growing with n. $\endgroup$ – Rob Hyndman Sep 4 '10 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 '10 at 17:26
  • $\begingroup$ Actually, I believe Shao shows that CV is inconsistent unless $n_v/n \to 1$ as $n \to \inf$, where $n_v$ is the number of samples in the test set. Thus $k$-fold CV is always inconsistent for variable selection. Have I misunderstood? By $k$-fold CV I mean dividing the sample into $k$ groups and training on $k-1$ of them, and testing on 1 of them, then repeating $k$ times. Then $n_v/n = 1/k$ for $k$-fold CV, which never approaches 1. $\endgroup$ – shabbychef Sep 7 '10 at 16:46
  • 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 '10 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$
  • $\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 '10 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 '10 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 '10 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$ – probabilityislogic Dec 13 '11 at 15:03
  • 1
    $\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$ – probabilityislogic Dec 13 '11 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$
  • $\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 '10 at 17:27
  • $\begingroup$ Wanna make some? $\endgroup$ – user88 Sep 8 '10 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 '10 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$ – cbeleites supports Monica Nov 24 '13 at 13:43
2
$\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$

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.