classifier performing well in leave-one-out cross-validation but not k-fold

Question

I am building a classifier and have over 1 million features to choose from. I implemented penalized regression, aka, lasso regression, followed by recursive feature selection in order to select features in each fold of my cross-validation. I only have 58 samples total.

When I run leave-one-out (LOO) cross-validation (cv), I get ROC AUCs around 0.9, but there is some variance each time I run it. When I ran 16x16-fold cv 100 times, the median AUC was only 0.6. The reason for choosing 16-fold is because that is the number of processors I have available to parallelize the code.

The lasso regression will only pick a total of n-1 features, where n is the number of samples in my training set. This means that for 16-fold cv, there are slightly fewer features that can be selected by lasso regression, so that is one possible explanation for the difference, but I am skeptical that is the reason for the 0.3 drop in AUC.

Any ideas on why it would perform so differently in 16-fold cv versus LOO cv? It should really only come down to a difference of training on 54 or 55 samples and predicting two or three vs. training on 57 and predicting 1 in each fold. Also, what does it mean that I am getting slightly different AUCs each time I run LOO cv?

Answer 1

Pooling LOO-CV estimates to compute an AUC can lead to very biased estimates of performance if you don't adjust the class proportions on each fold. Why?

Suppose I construct the one of the simplest classifiers I can possibly think of, which just predicts the proportion of positive outcomes in the training set every time. This classifier should give me an AUC of 0.5 because it doesn't even bother to discriminate between positive and negative cases; the ability to make this distinction is what the AUC is measuring.

However, if I just remove a data point and 'train' this model on the remaining data, my prediction is relatively small when I remove a positive case and relatively large when I remove a negative case; this gets me a perfectly bad classifier -- I always predict a higher probability for a held-out negative case than I do for a held-out positive case, leaving me with an AUC of 0, not 0.5. Note, some routines that compute the AUC will actually report an AUC of 1 in such cases because you just need to reverse the class labels to get a perfectly good classifier; so depending on whether your particular implementation does that, you can end up with pessimistic/optimistic estimates.

Of course, in most cases you have a more sophisticated classifier than the one I've described, but you're more often than not making adjustments to a 'baseline' prediction of the class probabilities and the bias is still there.

You can remedy this by randomly removing an observation with the opposite class label in each fold, then things should be more realistic.