Can test set performance be too poor? I've trained a binary classifier (PCA-LDA) on some clinical data for which I have 18 patients, each with ~250 observations. I am performing leave-one-patient-out cross-validation, each left out patient's ~250 observations all from the same class.
The training set accuracy is ~55%, which is poor but I was expecting as much.
However, the test set accuracy is ~20%.
I'd expect a terrible classifier to give 50% accuracy. With 20% I need only to switch the labels and suddenly I've got 80% accuracy, which would be ridiculously good in this application.
Are my expectations reasonable and am I right to be suspicious? Any clues as to why this might be happening?
I tried leave-two-patients-out CV, ensuring those two patients were different classes, which gave far more reasonable results (test accuracy ~50%), but I can't fathom why this should be so.
Thanks for any input.
 A: I think your expectations are reasonable in principle and you're right to be suspicious. Chances are something went wrong at some point (coding error, wrong data accessed etc.). You need to go into what you were doing and check whether every single thing does what it should do and every object (data, data subsets etc.) is what it's supposed to be.
However, note that 18 is a really small sample size, so there may be quite some random variation in your results. I ran a binomial test to see whether 4 out of 18 (20%) is still compatible with a true probability for correctness of 50%, and the p-value is 0.031. This is significant at 5% but not the kind of p-value that would seem outright impossible, meaning that with some bad luck (3 in 100 times) you may just get something like this even if your classifier in fact doesn't do worse than random guessing. Note that the test is not quite appropriate as it doesn't take into account that there is some kind of dependence between the different cross-validation runs, however I think it is OK as an orientation. Surely if your training set accuracy is only 55% there is hardly any hope to get a CV result that can tell you that you're significantly better than random guessing (using the somewhat inappropriate test that I did, you'd need some 80% or more correctness on the test data for this). The message then is probably that with the given sample size and hardness of the problem basically you can't have evidence that the classifier is doing anything reasonable. (This doesn't necessarily apply to all classifiers though.)
PS: I have seen classifiers doing significantly "worse than useless" in certain situations, so this is not impossible either, but it requires a particularly bad interaction between classifier choice and data structure. However, with 250 variables (I guess you call "observations" what I'd call "variables") and $n=18$ many strange things can happen.
A: Some classifiers, including LDA default (hyper)parameters in some implementations, use the relative frequency of the classes. When doing leave-one-out with such a classifier, you'll systematically test with a class that is underrepresented in the training set (compared to the whole data set). Particularly with small sample sizes, this can lead to surprisingly large pessimistic bias.
The huge difference you observe with stratified testing points into this direction.
This has been described in the literature, e.g. in
R. Kohavi: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection. In: Artificial Intelligence Proceedings 14 t h International Joint Conference, 20 – 25. August 1995, Montréal, Québec, Canada. Hrsg. von C. S. Mellish. Morgan Kaufmann, USA, 1995, S. 1137–1145.
I've seen this happen with vibrational spectra and PLS-DA, see e.g. Beleites, C.; Baumgartner, R.; Bowman, C.; Somorjai, R.; Steiner, G.; Salzer, R. & Sowa, M. G. Variance reduction in estimating classification error using sparse datasets, Chemom Intell Lab Syst, 79, 91 - 100 (2005). 
