Exact Paired-Permutation Testing for Structured Test Statistics

Ran Zmigrod, Tim Vieira, Ryan Cotterell


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 𝒪(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
Anthology ID:
2022.naacl-main.360
Volume:
Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
Month:
July
Year:
2022
Address:
Seattle, United States
Venue:
NAACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
4894–4902
Language:
URL:
https://aclanthology.org/2022.naacl-main.360
DOI:
10.18653/v1/2022.naacl-main.360
Bibkey:
Cite (ACL):
Ran Zmigrod, Tim Vieira, and Ryan Cotterell. 2022. Exact Paired-Permutation Testing for Structured Test Statistics. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4894–4902, Seattle, United States. Association for Computational Linguistics.
Cite (Informal):
Exact Paired-Permutation Testing for Structured Test Statistics (Zmigrod et al., NAACL 2022)
Copy Citation:
PDF:
https://aclanthology.org/2022.naacl-main.360.pdf
Code
 rycolab/paired-perm-test