@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",
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",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="zmigrod-etal-2022-exact">
<titleInfo>
<title>Exact Paired-Permutation Testing for Structured Test Statistics</title>
</titleInfo>
<name type="personal">
<namePart type="given">Ran</namePart>
<namePart type="family">Zmigrod</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Tim</namePart>
<namePart type="family">Vieira</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ryan</namePart>
<namePart type="family">Cotterell</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2022-07</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Marine</namePart>
<namePart type="family">Carpuat</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Marie-Catherine</namePart>
<namePart type="family">de Marneffe</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ivan</namePart>
<namePart type="given">Vladimir</namePart>
<namePart type="family">Meza Ruiz</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Seattle, United States</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<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 \mathcalO(G N (łog GN )(łog 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</abstract>
<identifier type="citekey">zmigrod-etal-2022-exact</identifier>
<identifier type="doi">10.18653/v1/2022.naacl-main.360</identifier>
<location>
<url>https://aclanthology.org/2022.naacl-main.360</url>
</location>
<part>
<date>2022-07</date>
<extent unit="page">
<start>4894</start>
<end>4902</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Exact Paired-Permutation Testing for Structured Test Statistics
%A Zmigrod, Ran
%A Vieira, Tim
%A Cotterell, Ryan
%Y Carpuat, Marine
%Y de Marneffe, Marie-Catherine
%Y Meza Ruiz, Ivan Vladimir
%S Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
%D 2022
%8 July
%I Association for Computational Linguistics
%C Seattle, United States
%F zmigrod-etal-2022-exact
%X 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 \mathcalO(G N (łog GN )(łog 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
%R 10.18653/v1/2022.naacl-main.360
%U https://aclanthology.org/2022.naacl-main.360
%U https://doi.org/10.18653/v1/2022.naacl-main.360
%P 4894-4902
Markdown (Informal)
[Exact Paired-Permutation Testing for Structured Test Statistics](https://aclanthology.org/2022.naacl-main.360) (Zmigrod et al., NAACL 2022)
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.