How to run a paired permutation test for 1 classifier, with 2 sets of predictions (paired), with classification accuracies as the test statistic?

Question

CORE QUESTION: I have a single trained classifier (single participant) tested on 2 related multiclass classification tasks. As each trial of the classification tasks are related, the 2 sets of predictions constitute paired data. I would like to run a paired permutation test to find out if the difference in classification accuracy between the 2 prediction sets is significant.

So my data consists of 2 lists of predicted classes, where each prediction is related to the prediction in the other test set at the same index.

Example:

actual_classes = [1, 3, 6, 1, 22, 1, 11, 12, 9, 2]
predictions1 = [1, 3, 6, 1, 22, 1, 11, 12, 9 10] # 90% acc.
predictions2 = [1, 3, 7, 10, 22, 1, 7, 12, 2, 10] # 50% acc.

H0: There is no significant difference in classification accuracy.

ADDITIONAL INFORMATION: In my case, the classifier is a deep neural network model, trained to classify audiovisual videos (but if you're uncomfortable with that, imagine it is a single participant). The model is tested on a held-out test set of audiovisual videos, and then tested on this same video set again, but without any audio data (hence paired). I would like to know if there is a significant difference in classification accuracy.

I am not interested here in cross-validation. I am using a particular held-out test set in a different domain to the training set (and so the entire training set is used for training and the entire test set is used for testing).

I'm comfortable with running a paired permutation test with continuous data (finding the difference between each value in a pair, randomising the sign and then taking the mean). But I'm unsure of how to deal with classification data as I am unsure how to measure the single paired value.

I would really like a paired permutation test here, but failing that, upvotes for anyone providing other tests and advice. Any help appreciated!

Answer 1

I have been thinking about this and I'm going to post a proposed solution and see if someone approves or explains why I'm wrong.

actual_classes = [1, 3, 6, 1, 22, 1, 11, 12, 9, 2]
predictions1 = [1, 3, 6, 1, 22, 1, 11, 12, 9 10] # 90% acc.
predictions2 = [1, 3, 7, 10, 22, 1, 7, 12, 2, 10] # 50% acc.
paired_predictions = [[1,1], [3,3], [6,7], [1,10], [22,22], [1,1], [11,7], [12,12], [9,2], [10,10]]

actual_test_statistic = predictions1 - predictions2 # 90%-50%=40 # 0.9-0.5=0.4
all_simulations = [] # empty list
for number_of_iterations:
    shuffle(paired_predictions) # only shuffle between pairs, not within
    simulated_predictions1 = paired_predictions[first prediction of each pair]
    simulated_predictions2 = paired_predictions[second prediction of each pair]
    simulated_accuracy1 = proportion of times simulated_predictions1 equals actual_classes
    simulated_accuracy2 = proportion of times simulated_predictions2 equals actual_classes
    all_simulations.append(simulated_accuracy1 - simulated_accuracy2) # Put the simulated difference in the list

p = count(absolute(all_simulations) > absolute(actual_test_statistic ))/number_of_iterations

If you have any thoughts, let me know in the comments. Or better still, provide your own corrected version in your own answer. Thank you!