Exact Paired-Permutation Testing for Structured Test Statistics

Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4894 - 4902 July 10-15, 2022 ©2022 Association for Computational Linguistics Exact Paired-Permutation Testing for Structured Test Statistics Ran Zmigrod Tim Vieira Ryan Cotterell University of Cambridge Johns Hopkins University ETH Zürich rz279@cam.ac.uk tim.f.vieira@gmail.com ryan.cotterell@inf.ethz.ch 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 O(GN(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. https://github.com/rycolab/ paired-perm-test 1 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 (Di- etterich, 1998; Koehn, 2004; Ojala and Garriga, 2010; Clark et al., 2011; Berg-Kirkpatrick et al., 2012; Dror et al., 2018) and statistical hypothe- sis testing provides answers (Lehmann and Ro- mano, 2005). In this paper, we study the paired- permutation test (Good, 2000)—a commonly used hypothesis test in NLP because it makes no as- sumptions on the distribution of the data or the evaluation metric used to compare the two sys- tems (Yeh, 2000; Dror et al., 2018, 2020; Deutsch et al., 2021). 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 2N possible swaps. Without 2000 4000 6000 8000 10000 Number of Sentences (N) 0 1 2 3 4 5 6 Runtime (seconds) exact perm test+ convolve DP exact perm test+ convolve FFT monte carlo (K = 40000) monte carlo (K = 20000) monte carlo (K = 10000) monte carlo (K = 5000) Figure 1: Runtime comparison of exact_perm_test using convolve_DP and convolve_FFT, and monte_carlo as a function of the number of en- tries in the dataset. See for §5 for experimental details. any assumptions on the test statistic, we can only exactly compute this sum in O(2N) time. Thus, practitioners often resort to running a Monte Carlo (MC) approximation which replaces the summa- tion with K ≪ 2N randomly sampled swaps. Al- though the MC approximation is often practical, it unfortunately,introduces additional error when determining the significance of a test (Serlin, 2000; Koehler et al., 2009). This paper proposes a family of additively struc- tured, integer-valued test statistics. Test statistics of this form admit an efficient …

Content truncated to 500 words