# Is cross-validation still valid when the sample size is small?

I have what seems to be a very basic confusion about cross-validation.

Let us say I am building a linear binary classifier, and I want to use cross-validation to estimate the classification accuracy. Imagine now that my sample size $N$ is small, but the number $k$ of features is large. Even when features and classes are randomly generated (i.e. "actual" classification accuracy should be 50%), it can so happen that one of the features will perfectly predict the binary class. If $N$ is small and $k >> N$, such a situation is not unlikely. In this scenario I will get 100% classification accuracy with any amount of cross-validation folds, which obviously does not represent the actual power of my classifier, in a sense that probability to classify a new sample correctly is still only 50%. [Update: this is wrong. See my answer below for the demonstration of why it is wrong.]

Are there any common methods of dealing with such a situation?

For example, if I want to assess statistical difference between my two classes, I could run MANOVA which in case of two groups reduces to computing Hotelling's T. Even if some of the features yield significant univariate differences ("false positives"), I should get an overall non-significant multivariate difference. However, I do not see anything in the cross-validation procedure that would account for such false positives ("false discriminants"?). What am I missing?

One thing that I can think of myself, would be to cross-validate over features, e.g. to select random subset of features (in addition to randomly selecting a test set) on each cross-validation fold. But I do not think such an approach is often (ever?) used.

Update: Section 7.10.3 of "The Elements of Statistical Learning" entitled "Does Cross-Validation Really Work?" asks exactly the same question and claims that such a situation can never arise (cross-validation accuracy will be 50%, not 100%). So far I am not convinced, I will run some simulations myself. [Update: they are right; see below.]

• If you edit your question again, you should fix the typo in your title when you do it. Feb 12, 2014 at 3:45
• @Glen_b: somebody else has already done it. But let me ask: is it in any way frowned upon here, when the question is edited several times (perhaps "too often") after posting? I realize that it bumps it to the top of the active list every time, so I was wondering if it is considered importunate (and I think I can detect it in the tone of your remark). Feb 12, 2014 at 10:23
• Don't read too much into my comment (tone is difficult to discern!) -- I simply didn't consider the spelling mistake urgent enough that it couldn't wait for another edit. If you make five edits in ten minutes, or over a longer period during a quiet time, you probably won't impact anything (bumping to the top what's already at or almost at the top). If you make nine edits over four days, that would be a case where you might worry about bumping it too much and see if you could consolidate your edits more. I haven't seen anything that suggests you should worry. Feb 12, 2014 at 10:35

I don't think there is much confusion in your thoughts, you're putting your finger on one very important problem of classifier validation: not only classifier training but also classifier validation has certain sample size needs.

Well, seeing the edit: there may be some confusion after all... What the "Elements" tell you is that in practice the most likely cause of such an observation is that there is a leak between training and testing, e.g. because the "test" data was used to optimze the model (which is a training task)

The section of the Elements is concerned with an optimistic bias caused by this. But there is also variance uncertainty, and, even doing all splitting correctly you can observe extreme outcomes.

IIRC the variance problematic is not discussed in great detail in the Elements (there's more to that than what the Elements discuss in section 7.10.1), so I'll give you a start here:

Yes, it can and does happen that you either accidentally have a predictor that predicts this particular small data set perfectly (train & test set). You may even just get a splitting that does accidentally lead to seemingly perfect results while the resubstitution error would be > 0.

This can happen also with correct (and thus unbiased) cross validation because the results are also subject to variance.

IMHO it is a problem that people do not take this variance uncertainty into account (on contrast, bias is often discussed in great length; I've hardy seen any paper discussing the variance uncertainty of their results although in my field with usually < 100, frequently even < 20 patients in one study it is the predominant source of uncertainty). It is not that difficult to get a few basic sanity checks that would avoid most of these issues.

There are two points here:

• With too few training cases (trainig samples ./. model complexity and no. of variates), models get unstable. Their predictive power can be all over the place. On average, it isn't that great, but it can accidentally be truly good.
You can measure the influence of model instability on the predictions in a very easy way using the results of an iterated/repeated $k$-fold cross-validation: in each iteration, each case is predicted exactly once. As the case stays the same, any variation in these predictions is caused by instability of the surrogate models, i.e. the reaction of the model to exchanging a few training cases.
See e.g. Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008).
DOI: 10.1007/s00216-007-1818-6

IMHO checking whether the surrogate models are stable is a sanity check that should always be done in small sample situations. Particularly as it comes at nearly zero cost: it just needs a slightly different aggregation of the cross validation results (and $k$-fold cross-validation should be iterated anyways unless it is shown that the models are stable).

• Like you say: With too few test cases, your observed sucesses and failure may be all over the place. If you calculate proportions like error rate or hit rate, etc. they will also be all over the place. This is known as these proportions being subject to high variance.
E.g. if the model truly has 50% hit rate, the probability to observe 3 correct out of 3 predictions is $0.5^3 = 12.5 \%$ (binomial distribution). However, it is possible to calculate confidence intervals for proportions, and these take into account how many cases were tested. There is a whole lot of literature about how to calculate them, and what approximations work well or not at all in what situations. For the extremely small sample size of 3 test cases in my example:

binom.confint (x=3, n=3, prior.shape1=1, prior.shape2=1)
#           method x n mean     lower     upper
# 1  agresti-coull 3 3  1.0 0.3825284 1.0559745
# 2     asymptotic 3 3  1.0 1.0000000 1.0000000
# 3          bayes 3 3  0.8 0.4728708 1.0000000
# 4        cloglog 3 3  1.0 0.2924018 1.0000000
# 5          exact 3 3  1.0 0.2924018 1.0000000
# 6          logit 3 3  1.0 0.2924018 1.0000000
# 7         probit 3 3  1.0 0.2924018 1.0000000
# 8        profile 3 3  1.0 0.4043869 1.0000000 # generates warnings
# 9            lrt 3 3  1.0 0.5271642 1.0000000
# 10     prop.test 3 3  1.0 0.3099881 0.9682443
# 11        wilson 3 3  1.0 0.4385030 1.0000000


You'll notice that there is quite some variation particularly in the lower bound. This alone is an indicator that the test sample size is so small that hardy anything can be concluded from the test results.
However, in practice it hardly matters whether the confidence interval spans the range from "guessing" to "perfect" or from "worse than guessing" to "perfect"

• conclusion 1: think beforehand how precise the performance results need to be in order to allow a useful interpretation. From that, you can roughly calculate the needed (test) sample size.

• conclusion 2: calculate confidence intervals for your performance estimates

• For model comparisons on the basis of correct/wrong predictions, don't even think of doing that with less than several hundred test cases for each classifier.
Have a look at McNemar's test (for paired situations, i.e. you can test the same cases with both classifiers). If you cannot do the comparison paired, look for "comparison of proportions", you'll need even more cases, see the paper I link below for examples.

• You may be interested in our paper about these problems:
Beleites, C. et al.: Sample size planning for classification models., Anal Chim Acta, 760, 25-33 (2013). DOI: 10.1016/j.aca.2012.11.007; arXiv: 1211.1323

second update about randomly selecting features: the bagging done for random forests regularly uses this strategy. Outside that context I think it is seldom, but it is a valid possibility.

• Thank you very much! I am going to study your reply, check the references, and get back to you. However, about the update to my question: I am afraid we are talking about different sections of The Elements; you seem to refer to 7.10.2 ("The Wrong and Right Way to Do Cross-validation"), whereas I was referring to 7.10.3 ("Does Cross-Validation Really Work?"). Do you maybe want to revise the part of your answer about it? As I read that section, Hastie et al. claim it is not a problem. Feb 11, 2014 at 23:51
• @amoeba: They are right that it is not a problem if the cross validation is done correctly. The important sentence for the bias is "The preceding argument [that the cross validated result will have an optimistic bias] has ignored the fact that in cross-validation, the model must be completely retrained for each fold". If you don't do the complete retraining, you will get an optimistic bias. Subtle versions of this (e.g. doing a PCA projection first and then some classification in PC score space, but not retraining the PCA in the cross validation) are a mistake I see rather frequently. Feb 12, 2014 at 0:10
• (I've updated that part of the answer: the problem I refer to is already the variance. The Elements give a short discussion, but not about the finite test-sample-size for classification.) The Elements say in 7.10.3 that if you do the CV correctly, it is unbiased or slightly pessimistically biased: i.e. on average you are OK. They just mention the variance in one sentence. But that variance is exactly what you need to look at for your question: that variance means that indeed by chance you can observe high accuracy even if generalization power is low and you estimate is unbiased. Feb 12, 2014 at 0:37
• @cbeleites +1, I just read your 2008 paper. Would you expect a 'final' model trained on all available data to perform worse than a model aggregated/average from k submodels generated through k-fold cross-validation? Feb 13, 2014 at 10:08
• @BGreene: as always, the answer is: it depends. Aggregating doesn't improve anything if there was no problem with instability in the first place. But if the surrogate models are unstable, the 'final' model is likely to be unstable as well. Then I'd expect aggregation to help. If you'd like to have more in-depth discussion or other opinions, you could ask this as a question. Feb 13, 2014 at 11:24

I figured out what is going on: Hastie et al. were (of course) right, and my intuition was wrong. Here is the demonstration of my logic flaw.

Let's say we have 10 samples, first five are class 1 and last five are class 2. Let's generate 200 random features. Several of them are likely to predict the class perfectly, I made them bold on the following plot:

If we do the t-tests between classes using each of these three features, we get three significant p-values: 0.0047, 0.011, and 0.0039. These, of course, are false positives due to cherry-picking. If we do a Hotelling's test using all 200 features, we get a non-significant p=0.61, as expected.

Now let's try to cross-validate. I do 5-fold stratified cross-validation, holding out 1 sample from each class to classify. The classifier will be LDA on all 200 features. I repeat this procedure 100 times with different random features, and the mean number of correctly decoded classes I get is 4.9, i.e. chance level!

Well, LDA with 10 classes and 200 features overfits badly. Let's select only the features with perfect class separation on the training test in each cross-validation fold. The resulting mean accuracy is 5.1, still chance level. Why? Because it turns out that the number of features I am using on each fold is larger than the number of "perfect" features on the whole dataset. There are features that look perfect on the training set, but have zero predictive power on the test set. And they screw up the classification.

This is exactly the point that I did not appreciate before.

Finally, one can only use the features with perfect class separation on the whole dataset. Then the mean accuracy is 9.3, but this is cheating! Of course we are not allowed to use any knowledge about the whole dataset when doing cross-validation.