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
BibTeX
@inproceedings{zmigrod-etal-2022-exact,
title = "Exact Paired-Permutation Testing for Structured Test Statistics",
author = "Zmigrod, Ran and
Vieira, Tim and
Cotterell, Ryan",
editor = "Carpuat, Marine and
de Marneffe, Marie-Catherine and
Meza Ruiz, Ivan Vladimir",
booktitle = "Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies",
month = jul,
year = "2022",
address = "Seattle, United States",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2022.naacl-main.360/",
doi = "10.18653/v1/2022.naacl-main.360",
pages = "4894--4902"
}