8
$\begingroup$

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).

$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If the labels of the entire data set is permuted, followed by cross-validation, then would it be correct to say that the hypothesis being tested is whether the non-permuted classifier performance is any better than chance? On the other hand, if only the training data is permuted during cross-validation, then the hypothesis being tested is whether the classifier can learn an association between features and class labels just by chance? $\endgroup$
    – stuckstat
    Aug 5, 2021 at 6:48
  • $\begingroup$ From your answer (and thanks for it!), I understand that the correct thing to do is to permute the entire data and perform CV afterwards. However, see Tim's response which seems to say otherwise $\endgroup$
    – stuckstat
    Aug 5, 2021 at 6:49
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer and clarification! The paper does not say anything about train and test data. They briefly mention the idea of cross-validation (in the context of handling instabilities) $\endgroup$
    – stuckstat
    Aug 5, 2021 at 6:50
  • $\begingroup$ If I understand your answer correctly, you are suggesting that it would be correct to compare only the training performances between permuted and non-permuted data set (and therefore, only permute the training labels)? See also rep_ho's reply above which seems to suggest otherwise. $\endgroup$
    – stuckstat
    Aug 5, 2021 at 6:52
  • $\begingroup$ @stuckstat this is not what I'm saying. I was saying that the paper did not mention the test set, it sounds like they used the permutation test on the training set alone--this can be seen as an alternative to cross-validation. You would permute the labels and re-train the model many times and then compare the performance from the model trained on non-permuted labels vs the distribution of predictions on permuted labels. $\endgroup$
    – Tim
    Aug 5, 2021 at 6:55
1
$\begingroup$

I just met that question and found that there is a simulation study (Valente et al., 2021) proved to permutation all data before CV is correct.

And, here is reason.

A theoretical insight into why the other resampling schemes result in an inflation of false positives can be gained from (Bengio and Grandvalet, 2004), where the authors describe the error covariance matrix across all samples in terms of blocks and decompose the variance of the cross-validation error (i.e. the sum of all the elements of the covariance matrix) into three components. The first component is the variance of errors for each test data point (main diagonal of the covariance matrix), the other two stem from the use of cross-validation: the first arises from the fact that all the sample in a partition are tested using the same model (that changes per test partition), while the second arises from the overlap present in the training data of different partitions (this overlap is more pronounced when more partitions are used). When conducting a permutation test, if the resampling takes place in both the training and testing datasets or only in one of them at each cross-validation iteration, the cross-validation related terms in the variance decomposition are ignored, since it is implicitly assumed that the data across different iterations are independent. In other words, these resampling schemes subsume that one or both of the cross-validation related variance components described above is zero. This underestimation results in a sharper (i.e. with lower variance) null distribution, and therefore overconfident statements and invalid tests. On the other hand, when the data/labels association is kept constant across the different cross-validation iterations, the cross-validation related variance components are kept also in the estimation under H0, resulting in a more realistic empirical null distribution.

Valente, G., Castellanos, A. L., Hausfeld, L., De Martino, F., & Formisano, E. (2021). Cross-validation and permutations in MVPA: Validity of permutation strategies and power of cross-validation schemes. NeuroImage, 238, 118145. https://doi.org/10.1016/j.neuroimage.2021.118145

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.