论文标题
结构化测试统计的确切配对透明测试
Exact Paired-Permutation Testing for Structured Test Statistics
论文作者
论文摘要
显着性测试 - 尤其是配对的渗透测试 - 在开发NLP系统中发挥了至关重要的作用，以提供信心，即两个系统之间的性能差异（即测试统计量）并不是由于运气。但是，由于缺乏合适的精确算法，从业者依靠蒙特卡洛近似来执行此测试。在本文中，我们为结构化测试统计的家族提供了有效的精确算法，用于配对的渗透测试。我们的算法以$ \ MATHCAL {O}（gn（\ log gn）（\ log n））$ n $是$ n $是数据集尺寸，而$ g $是测试统计范围的范围。我们发现，我们的确切算法比蒙特卡洛近似值$ 10 $ x的速度$ 10 $ x，该算法在公共数据集中带有$ 20000 $的样本。
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}(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 $10$x faster than the Monte Carlo approximation with $20000$ samples on a common dataset.
