Return to Answer

Now either I am overlooking a completely stupid mistake (which is absolutely possible!), or we have a big problem with all the reasoning from Confidence interval for cross-validated classification accuracy, because the binomial intervals don't make any sense. For example, if I spoil my ideal class separation by relabeling 80 points from class A to B and vice versa, then my actual number of decoded samples becomes 240. The stability over iterations of CV is perfect. The binomial confidence interval binofit(240,400) is [0.55, 0.65] which excludes 0.5 so we would conclude that the decoding is significant. But the variance of shuffled correct decoders is still on average around 500-600, so standard deviation is around let's say 22, so 95% interval for the null hypothesis of random decoding is around 200$\pm$45, which includes 240, which means not significant.

Now either I am overlooking a completely stupid mistake (which is absolutely possible!), or we have a big problem with all the reasoning from Confidence interval for cross-validated classification accuracy, because the binomial intervals don't make any sense. For example, if I spoil my ideal class separation by relabeling 80 points from class A to B and vice versa, then my actual number of decoded samples becomes 240. The stability over iterations of CV is perfect. The binomial confidence interval binofit(240,400) is [0.55, 0.65] which excludes 0.5 so we would conclude that the decoding is significant. But the variance of shuffled correct decoders is still on average around 500-600, so standard deviation is around let's say 22, so 95% interval for the null hypothesis of random decoding is around 200$\pm$45, which includes 240, which means not significant.

In comments above @julieth quoted a paper by Jiang et al. Calculating Confidence Intervals for Prediction Error in Microarray Classification Using Resampling: "... the test set on which prediction of the $i$-th case has $n-2$ specimens in common with the training set on which prediction of the $j$-th is based, hence, the number of prediction errors is not binomial". In other words, they claim that the reason for non-binomiality is that training sets are not mutually exclusive. Turns out, Nadeau and Bengio have a mammoth 49-page long paper about it called Inference for the Generalization Error where they discuss exactly this issue in great detail.

In comments above @julieth quoted a paper by Jiang et al. Calculating Confidence Intervals for Prediction Error in Microarray Classification Using Resampling: "... the test [I think they mean "training" -- amoeba] set on which prediction of the $i$-th case has $n-2$ specimens in common with the training set on which prediction of the $j$-th is based, hence, the number of prediction errors is not binomial". In other words, they claim that the reason for non-binomiality is that training sets are not mutually exclusive. Turns out, Nadeau and Bengio have a mammoth 49-page long paper about it called Inference for the Generalization Error where they discuss exactly this issue in great detail.

Update:

In comments above @julieth quoted a paper by Jiang et al. Calculating Confidence Intervals for Prediction Error in Microarray Classification Using Resampling: "... the test set on which prediction of the $i$-th case has $n-2$ specimens in common with the training set on which prediction of the $j$-th is based, hence, the number of prediction errors is not binomial". In other words, they claim that the reason for non-binomiality is that training sets are not mutually exclusive. Turns out, Nadeau and Bengio have a mammoth 49-page long paper about it called Inference for the Generalization Error where they discuss exactly this issue in great detail.

I did not believe it at first, so I used the simulation above to check this claim. If I increase the total number of samples to 4000, I can use the Monte Carlo CV procedure with 100 folds (each time classifying 4 test cases) to get 400 predictions. On the shuffled data (I increased the number of shuffles to 1000) the mean number of correct classification is 199 and the variance is 346: still a whole lot more than 100 even though the sample size is now as large as 4000.

But now I can also do the following: split my 4000 samples in 100 stratified parts of 40, and in each part use 36 samples to predict 4. I will also get 400 predictions, but this time all training sets are mutually exclusive. The outcome (also after 1000 shuffles): mean 199, variance 98.

Wow! Nadeau, Bengio, and @julieth seem to be right. And binomial assumption seems to be dead wrong. I wonder how many papers there are out there using binomial confidence intervals and tests...