Abstract
We propose a new method for comparing learning algorithms on multiple tasks which is based on a novel non-parametric test that we call the Poisson binomial test. The key aspect of this work is that it treats the "win" probability of an algorithm as a random variable and accounts for dependencies between classifiers, providing a more reliable and statistically powerful way to declare a "winner" than traditional frequentist tests.
Introduction
In machine learning research, the standard approach to proving that one algorithm is superior to another involves comparing error rates across a suite of datasets. However, traditional statistical tools like the sign test or the Wilcoxon signed-rank (WSR) test often fail to account for the complexities of these comparisons. Specifically, they struggle with incommensurability (averaging error rates across tasks of varying difficulty), dependency (non-independent errors on the same test set), and low statistical power.
The Poisson Binomial Framework
To address these issues, we introduce a hierarchical Bayesian approach. For a single task, we model the joint error of two classifiers using a multinomial distribution, capturing outcomes where both are correct, both are wrong, or one outperforms the other.
When extending this to $N$ datasets, the probability of one algorithm winning varies across tasks. This leads to the Poisson binomial test. Unlike a standard binomial distribution, which assumes a constant success probability, the Poisson binomial distribution accounts for varying win probabilities across different contexts.
To make this computationally feasible, we employ a dynamic programming algorithm with $O(N^2)$ complexity, avoiding the combinatorial explosion typically associated with such distributions.
Experimental Evaluation
We evaluated the proposed method using both synthetic simulations and real-world benchmarks. Synthetic contexts allowed us to measure how often each test correctly identified a known "ground truth" winner.
As shown in the evaluation above, the Poisson binomial test consistently achieves a higher Area Under the ROC Curve (AUC) compared to the sign test and WSR test, particularly as the number of datasets $N$ increases. This indicates a superior ability to distinguish true performance improvements from random noise.
In real-world tests across 22 datasets (including UCI repositories and MNIST variants), we compared SVMs, Parzen Windows, AdaBoost, and ANNs. The Poisson binomial test provided more confident assertions of superiority in cases where traditional tests remained ambiguous.
Key Insights
A critical finding is the failure of the Wilcoxon Signed Rank test in asymmetric distributions. In ML, one algorithm may be slightly better on many tasks but significantly worse on a few; the WSR test's symmetry assumption can lead it to perform worse than a random guess in such scenarios. Additionally, we highlight the non-transitivity of algorithm rankings across multiple datasets, a phenomenon akin to the Condorcet paradox, which complicates simple rankings.
Conclusion and Future Work
The Poisson binomial test offers a robust, Bayesian alternative for algorithm comparison. While currently focused on pairwise classification tasks, future work will extend this framework to handle multiple comparisons (controlling family-wise error rates) and regression tasks involving continuous loss functions.
Summary updated