10-fold CV performance test: need to use same folds for both evaluated algorithms? I want to compare the performance of 2 algorithms with 10-fold cross validation.
What is the correct procedure and why?


*

*Procedure A: 

*

*generate the 10 folds

*test algo1 with these 10 folds and register results

*generate 10 new folds

*test algo2 with these 10 new folds and register results

*compare performance


*Procedure B:

*

*generate 10 folds

*test algo1 on these 10 folds and register results

*test algo2 on these 10 folds and register results

*compare performance



Does the fact that in procedure A both algorithms are tested with different folds have an impact on our ability to compare results?
 A: For smaller sample sizes, to compare like with like it is probably fairer to choose option B. In theory you should get approximately the same result. Any differences would be due to random variations in the sample. 
Repeating the cross-validation N times (e.g. N=10) will reduce the variance of the performance estimate. Using this method differences between scenario A and B would be reduced.
A: The correct procedure depends on the properties of the distribution of folds with respect to difficulty. 
For example, suppose that you are using two classifiers which are linear (i.e. they cannot match non-linear classification boundaries). If your dataset contains some subset of points which are not linearly separable, then some folds (those with many of these points) will be harder than other folds. Imagine that you use procedure A. Algo1 gets only folds that are (more or less) linearly separable. Algo2 gets one really pathological fold where it's no better than guessing. If the effect is large enough, Algo2 will appear to be worse than Algo1, but really it's just an aberration produced by the sampling of folds. 
If you incorporate the sample size (10 folds) into your comparison (i.e. do a two sample t-test or similar on the individual results of both algorithms on their folds, instead of just comparing the average scores directly), then probably it is fine to use procedure A. The test will be wrong some of the time because of the sampling errors, but this is incorporated into the p-value. This means the p-value will generally be higher than if you had used procedure B as described below.
If you opt for procedure B however, you can use a paired difference test instead (e.g. a paired t-test). This is a more powerful test, so you might be able to find statistically significant differences between the classifiers using fewer folds. If runtimes are an issue, and small differences matter, use procedure B and analyze results with a paired difference test. If getting the same folds is hard, use procedure A, and use more folds if you care about detecting small differences in performance (e.g. use 50 folds). 
