PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier

Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, Nicolas UsunierNeurIPS 2006 · OpenReview

This paper, a classic in PAC-Bayesian theory, tackles a long-standing gap between theoretical guarantees and the empirical success of ensemble methods like Boosting and Bagging.

TL;DR

The authors propose new PAC-Bayes bounds for majority vote classifiers that incorporate the variance of the errors, not just the mean. This allows the theory to prove that a "committee" of classifiers can be highly accurate even if individual members are mediocre, provided their errors are sufficiently uncorrelated.

What Problem Does This Paper Address?

In machine learning, a "Majority Vote" (or Bayes classifier) takes a collection of hypotheses and predicts the class chosen by the majority. Standard PAC-Bayes theory usually bounds the risk of this majority vote by looking at the "Gibbs classifier"—a stochastic model that picks one hypothesis at random.

The traditional bound states that the risk of the Majority Vote is at most twice the risk of the Gibbs classifier ($R(B_Q) \le 2R(G_Q)$). However, in practice, we often see the majority vote performing much better than this. The "wisdom of the crowd" allows classifiers to compensate for each other's mistakes. The problem was that existing PAC-Bayes frameworks couldn't mathematically capture this "compensation effect," leading to bounds that were far too pessimistic to be useful for practitioners.

Methods

The authors bridge this gap by shifting the focus from the average error to the distribution of errors.

  1. The Chebyshev Connection: They use the one-sided Chebyshev (Cantelli) inequality to derive a new bound ($C_Q$) for the majority vote. This bound depends on two things: the mean error of the classifiers and the variance of those errors (which relates to the pairwise covariance of errors between different classifiers).
  2. New PAC-Bayes Theorems: To make this practical, they needed to estimate this variance from training data. They developed generalized PAC-Bayes theorems that provide uniform bounds on:
  3. Joint Error ($e_Q$): How often two randomly picked classifiers both fail.
  4. Joint Success ($s_Q$): How often they both succeed.
  5. Disagreement ($d_Q$): How often they predict different labels.
  6. Semi-Supervised Extension: They realized that "disagreement" doesn't require labels to calculate. They introduced a semi-supervised bound that uses a large sample of unlabeled data to get a much tighter estimate of the disagreement term, significantly improving the final risk bound.

Key Insights and Ideas

  • Correlation is the Enemy: The "aha moment" is that the majority vote's success depends heavily on the classifiers being "uncorrelated." If classifiers make different mistakes on different examples, the majority will still be right.
  • The $C_Q$ Metric: The authors define a value $C_Q$ which is essentially the variance of the margin divided by its second moment. They show empirically that $C_Q$ has an almost linear correlation with the actual test risk, making it a much better predictor of performance than previous metrics.
Correlation of metrics with test risk
  • Uniformity: The bounds hold "uniformly" for all possible posterior distributions $Q$. This means you can use the bound to guide the learning process itself (e.g., as a regularization term) without "breaking" the statistical guarantee.

Key Results

  • Tightness: The proposed "PAC-Bound 2" (supervised) and "PAC-Bound 3" (semi-supervised) are significantly tighter than previous PAC-Bayes bounds.
  • Gibbs vs. Vote: The paper proves that the majority vote can have a risk arbitrarily close to zero even if the Gibbs classifier (the average individual performance) is as high as 0.5, provided the variance is low enough.
Comparison of PAC-Bounds over iterations
  • Empirical Validation: Evaluated using AdaBoost on 11 UCI datasets, the authors demonstrated that their variance-based bounds correctly track the actual error rate of AdaBoost as it iterates, whereas older bounds were often uninformative.

Limitations and Future Work

  • The "Disagreement" Bottleneck: The bounds tend to degrade (become loose) when the expected disagreement $d_Q$ approaches 0.5. This is a common issue in boosting algorithms, where the denominator of their $C_Q$ bound approaches zero.
  • Higher Moments: The authors acknowledge that mean and variance (first and second moments) might not be enough. They suggest that future work should look into higher-order moments to provide even tighter bounds in cases where classifiers are highly diverse.
  • Complexity: Calculating these joint error and disagreement terms is computationally more intensive than simply calculating the average error, which might limit their use in very large-scale real-time learning.

Summary updated

Abstract

We propose new PAC-Bayes bounds for the risk of the weighted majority vote that depend on the mean and variance of the error of its associated Gibbs classifier. We show that these bounds can be smaller than the risk of the Gibbs classifier and can be arbitrarily close to zero even if the risk of the Gibbs classifier is close to 1/2. Moreover, we show that these bounds can be uniformly estimated on the training data for all possible posteriors Q. Moreover, they can be improved by using a large sample of unlabelled data.
BibTeX
@inproceedings{lacasse2006pac,
  author = {Alexandre Lacasse and François Laviolette and Mario Marchand and Pascal Germain and Nicolas Usunier},
  title = {{PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=SkWSxYbd-H},
}
Figure