Permutation testing for machine learning: permute entire set or only training set? Ojala and Garriga (2010) [Journal of Machine Learning Research 11 (2010) 1833-1863] mention two permutation tests for machine learning: test one for assessing whether a classifier has learned anything better than random guessing. As far as I understand, the idea is to permute class labels and perform machine learning k number of times and compare with original model performance to derive a p value.
The question is a simple one: if I am using cross-validation, should I permute the entire data set before diving into training/test (per fold) OR should I permute the cross-validation training data only (within each fold) and leave the test data untouched. (As far as I understand, one would permute the class labels for the entire data and then perform cross-validation).
 A: There are few things to unpack here. The goal of permutation testing is to get a null distribution for your test statistic by permuting labels and repeating your procedure many times.
Your test statistic is e.g., average accuracy, and your procedure is CV. So you should permute the labels (all labels, because all labels go into the procedure) and then split the data into folds and run CV.
If you permute only the training set, then you are not getting valid null, because you don't have randomness in your outcome labels. If you permute data only in the test set, this will not be valid because it would not take into account the dependence between CV folds, which is the whole reason for doing permutation testing and not just some binomial test.
There are few caveats.
If you perform CV split randomly, then you can also simply permute the data first and then continue CV.
If your CV split is done so that each fold has the same proportion of labels from each class or that the folds are balanced based on the same other variables, then you have to permute so that this is also the case in your permutations. Usually, an easy way to do it is to permute first and then create your balanced splits.
If you don't have random folds, but they are already given, e.g., each fold is data from different cities, or different hospitals, or different measuring devices, then you have to permute within these folds so that labels from the same hospital will not get permuted with labels from a different hospital.
You might have other so-called "exchangeability blocks" that are not based on folds, e.g., you have different hospitals, but you don't split your data by hospital, then you should permute your data within these blocks, but not necessarily within folds.
A: At prediction time, you have the $(y_i, \hat y_i)$ pairs of the actual labels and the predictions. Notice that the result would be the same if you permuted the actual labels $y_i$'s and if you permuted the predictions $\hat y_i$'s, since permuting them breaks the pairing. So such a permutation test would create the null distribution in the scenario where the predictions were made at random but the distribution of the predictions is fixed.
But notice what does the paper say:

A significant classifier for Test 1 rejects the null hypothesis that
the features and the labels are independent, i.e., that there is no
difference between the classes. If the original data contains
dependency between data points and labels, then: (1) a significant
classifier $f$ will use such information to achieve a good
classification accuracy, resulting into a small $p$-value; (2) if the
classifier $f$ is not significant with Test 1, $f$ was not able to use
the existing dependency between data and labels in the original data.
Finally, if the original data did not contain any real dependency
between data points and labels, then all classifiers would have a high
$p$-value and the null hypothesis would never be rejected.
Applying randomizations on the original data is therefore a powerful
way to understand how the different classifiers use the structure
implicit in the data, if such structure exists. [...]

It mentions "different classifiers" using the structure of the data. If you permuted whole data it is a different question that is answered. A model trained on data with permuted labels learns to find spurious correlations. Having a small train error in such a case tells you how much is it prone to overfit. There is another difference when permuting only the labels and comparing them to predictions. In the first case, you are looking at the distribution of predictions from a single model. In the second case, you look at the distribution of predictions from different "null" models. Only the second case tells you how does the classifier learns the structure of the data.
Finally, correct me if I'm wrong, but the paper does not seem to say anything about the train and test data. They seem to be describing training the classifier on a dataset $D$ and comparing the performance to the permuted datasets $D'$, but those are the training errors.
