Bayesian Comparison of Machine Learning Algorithms on Single and Multiple Datasets.

Alexandre Lacoste, François Laviolette, Mario MarchandAISTATS 2012 · OpenReview

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.

Graphical model representing the hierarchical Bayesian framework for comparing algorithms across multiple tasks.

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.

Comparison of the Poisson binomial test against traditional frequentist tests in terms of AUC as the number of datasets N increases.

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

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...
BibTeX
@inproceedings{lacoste2012bayesian,
  author = {Alexandre Lacoste and François Laviolette and Mario Marchand},
  title = {{Bayesian Comparison of Machine Learning Algorithms on Single and Multiple Datasets.}},
  booktitle = {AISTATS},
  year = {2012},
  url = {https://openreview.net/forum?id=SfqJ7vT9-H_},
}
Figure