Does the standard deviation of the folds of LOO cross-validation have any practical meaning in comparison/evaluation of classifiers?

Question

There are dozens of questions regarding LOO and variance. Most of the answers are purely theoretical or too general. I have also read many papers like this paper.

Specifically: I have two not too stable classifiers/learning algorithms (suppose C4.5 and RIPPER for simplicity), the dataset is small, thus LOO is desirable. I need to compare the accuracy of models generated from both algorithms (it is not about model selection nor accurate absolute estimates of the prediction error nor how to setup experiments).

Is there any value calculating, e.g. the standard deviation in this case? ps. it is a single run, the the standard deviation is over the hits obtained by the models during LOO

It seems to me that LOO's accuracy estimate and LOO's StDev are function of each other, almost redundant information. If you take from one, immediately you have given to the other.

---

Another way to think about this is to realize that the "internal" variance of LOO is due to scarce testing data and not due to lack of accuracy of the model. However, this brings another question, which is how much the scarceness of testing data affects the the "internal" variance of other CVs besides LOO.

Answer 1

Is there any value calculating, e.g. the standard deviation [of LOO]?

No.
You are right: for (hard) classification and LOO, this is redundant information. You already "know" the variance/standard deviation once you have the average (e.g. hit rate) and the number of cases.

But: that's a particular drawback of LOO, because LOO is complete (all possible training/test splits have been evaluated). Other resampling estimation methods do not suffer from this, and there you can gain new information by looking at the variance.

My practical recommendations thus would be:

• The most important practical recommendation: do not try to attempt comparing classifiers with a sample size that is so small that you think the only option for validation is LOO. If you write a paper about the performance of the classifiers in general (for the particular type of application and data you are looking at, but independent of the concrete data set; I assume that is the case but your question is still somewhat unclear to me in that point), may I ask you to explicitly remind the reader that this is basically impossible if the aim is building a classifier for a given data set (= for application papers)?
  You may get around this by doing lots of the small sample size experiments. In that case, you need to be aware though that the variance you can get from the resampling validation does not include the variance due to the drawing of a small data set. More theory about this in
  Bengio, Y. & Grandvalet, Y. No Unbiased Estimator of the Variance of K-Fold Cross-Validation, Journal of Machine Learning Research, 5, 1089-1105 (2004).

• Switch from LOO to $k$-fold/leave-$n$-out cross validation (or out-of-bootstrap).

• The advantage with these is that iterations (multiple runs, repetitions) are possible: do iterate.
• After $i$ iterations, you have $i$ predictions for each test case (by different surrogate models). Looking at the variance between these predictions gives you a direct measure of the stability. This is important information, as you say that your classifier is not too stable.
• In addition, taking the average over all cases and iterations somewhat lowers the variance uncertainty: variance caused by the instability is reduced.
  However this doesn't to miracles, the variance due to the finite and small number of test cases stays untouched.