Exact Paired-Permutation Testing for Structured Test Statistics (2022)

Abstract: Significance testing—especially the paired-permutation test—has played a vital role in developing NLP systems to provide confidence that the difference in performance between two systems (i.e., the test statistic) is not due to luck. However, practitioners rely on Monte Carlo approximation to perform this test due to a lack of a suitable exact algorithm. In this paper, we provide an efficient exact algorithm for the paired-permutation test for a family of structured test statistics. Our algorithm runs in \mathcal{O}(G N (\log GN )(\log N)) time where N is the dataset size and G is the range of the test statistic. We found that our exact algorithm was 10x faster than the Monte Carlo approximation with 20000 samples on a common dataset

## introduction how confident can we be that system u is more accurate than system v ? questions of this form are widespread in natural language processing @xcite @xcite @xcite and statistical hypothesis testing provides answers @xcite . in this paper, we study the pairedpermutation test @xcite -a commonly used hypothesis test in nlp because it makes no assumptions on the distribution of the data or the evaluation metric used to compare the two systems @xcite @xcite . the paired-permutation test checks whether a test statistic is significant by evaluating the probability that a value at least as large as the observed statistic would occur if system outputs were randomly swapped. thus, an exact algorithm for evaluating the paired-permutation test involves a summation over all 2 n possible swaps. without any assumptions on the test statistic, we can only exactly compute this sum in o(2 n ) time. thus, practitioners often resort to running a monte carlo (mc) approximation which replaces the summation with k ≪ 2 n randomly sampled swaps. although the mc approximation is often practical, it unfortunately,introduces additional error when determining the significance of a test @xcite . this paper proposes a family of additively structured, integer-valued test statistics. test statistics of this form admit an efficient exact algorithm that leverages the fast fourier transform @xcite to run in o(gn (log gn )(log n )) time where n is the size of the dataset and g is the range of the test statistic. we compare the efficiency of our exact method to the mc approximation for comparing part-of-speech taggers on the universal dependency dataset @xcite . surprisingly, our exact algorithm is faster than mc approximation: given 10000 sentences, our algorithm is 10x faster than mc with 20000 samples and 3x faster than mc with 5000 samples, taking ≈ 0.1 seconds. ## paired-permutation testing the paired-permutation test @xcite , the focus of this work, is a common null hypothesis significance test that has a natural application to many problems in nlp @xcite . the test attempts to reject the null hypothesis, described below, at significance level α; typically α = 0.05. preliminaries. suppose we want to compare the performances of two systems u and v where each system was evaluated on a dataset of the same n entries. we place the entries of u and v into a pair of arrays of length n denoted u and v. ## structured test statistics we now discuss a common special case of the paired-permutation test where the test statistic has a particular structure. in §4, we show how to exploit this structure to develop an efficient algorithm to exactly compute the test. the specific assumption we make is that the test statistic is an integer-valued additively decomposable function. formally, this assumption means that we can rewrite t as follows the domain of each pmf, dom(f n ), contains at most two elements. let s @xmath0. clearly, |s| = o(gn ) as we have a sum over n rvs z n each with domain size o(g). the following theorem shows that we can evaluate p[t(u ∅ , v ∅ )] from the distribution of s, which we we will show in the next section is efficient to compute. theorem 1. for any test statistic t that factorizes as in (3) with h and g, the distribution of the test statistic under the null distribution decomposes as algorithm 1: monte carlo approximation algorithm for the paired-permutation test. example. a common test statistic is the difference in accuracy, in which each entry u @xmath1, ..., c} g where c is the number of classes and in this case, g is the maximum length of an entry sequence (or one if each entry has a binary accuracy value). then g(u n , v n ) ∈ {-g, ..., g} is the difference in the number of correct predictions between individual entries u n and v n . we can additionally define the function h as either h(x) = x or h(x) = |x| depending on whether we want a one-tailed or two-tailed significance test. ## an exact paired-permutation test in this section, we describe two exact, efficient algorithms for computing the p-value under the pairedpermutation test for any structured test statistic (see (3)). 1 our algorithms hinge on an important theorem in probability: the pmf of the sum of independent events is the convolution of their individual pmfs @xcite . let f s denote the pmf 1: def exact_perm_test(u, v, g, h) : 2: algorithm 2: compute the exact p value for the pairedpermutation test for structured test statistics. pseudocode for this algorithm is given as exact_perm_test in alg 2. we omit the details of evaluating the convolution in exact_perm_test and discuss methods for efficient convolution in the remainder of this section. theorem 2. for any two entries, u and v, and test statistic t that factorizes as in (3) with h and g, for @xmath2: 5: ## experiments we demonstrate the efficiency of our exact algorithms by simulating paired-permutation tests between the accuracy of two systems. in order to have some control over the p-value, n , and g (maximum length of a sentence), we randomly generate our two system outputs from a measured distribution. specifically, we will use the stanza foot_2 @xcite part-of-speech tag accuracy statistics when evaluating on the english universal dependencies (ud) test set @xcite . we sample our outputs from the normal distribution where the mean and standard deviation match the rates @xcite on the english ud test dataset @xcite . ## conclusion we presented an algorithm to compute the exact p-value of a paired-permutation test for the case of a family of structured test statistics, including the difference in accuracy. our algorithm runs in o(gn (log gn )(log n )) time and requires o(gn ) space. we empirically show that our exact algorithm is faster than monte carlo approximation techniques. the theory of our work is extensible to a more general class of test statistics which we discuss in app. b. we hope that this work encourages the use of exact paired-permutation tests in future nlp research.