PaperlayerView exact revision on arXiv

Source-linked AI summary

Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm

Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, Jean-Francis Roy

arXiv:1503.08329v2stat.MLcs.LG

TL;DR

The paper addresses the difficulty of tightly bounding majority-vote risk when weak voters compensate for one another. It develops a PAC-Bayesian C-bound based on margin moments and disagreement, extends the analysis to KL-free and sample-compressed settings, and derives MinCq. The resulting algorithm is reported to perform very well and competitively with AdaBoost and SVM on natural data.

  • Problem

    Existing Gibbs-risk bounds can be loose for majority votes because they do not capture compensation among individually weak voters.

  • Method

    The paper develops PAC-Bayesian C-bounds from margin moments, extends them to KL-free and sample-compressed settings, and uses them to formulate MinCq as a quadratic program.

  • Results

    The C-bound can be arbitrarily close to zero even when Gibbs risk is close to 1/2, and MinCq is reported as highly competitive with AdaBoost and the Support Vector Machine.

  • Takeaways & Limitations

    The analysis provides a theoretically grounded way to account for voter disagreement and supports majority-vote learning with classifier and kernel voters.

  • Takeaways & Limitations

    The KL-removal analysis requires aligned posteriors, and sample-compressed voters require distinguishing the full sample size from the compressed size.

Abstract

from arXiv · show

We propose an extensive analysis of the behavior of majority votes in binary classification. In particular, we introduce a risk bound for majority votes, called the C-bound, that takes into account the average quality of the voters and their average disagreement. We also propose an extensive PAC-Bayesian analysis that shows how the C-bound can be estimated from various observations contained in the training data. The analysis intends to be self-contained and can be used as introductory material to PAC-Bayesian statistical learning theory. It starts from a general PAC-Bayesian perspective and ends with uncommon PAC-Bayesian bounds. Some of these bounds contain no Kullback-Leibler divergence and others allow kernel functions to be used as voters (via the sample compression setting). Finally, out of the analysis, we propose the MinCq learning algorithm that basically minimizes the C-bound. MinCq reduces to a simple quadratic program. Aside from being theoretically grounded, MinCq achieves state-of-the-art performance, as shown in our extensive empirical comparison with both AdaBoost and the Support Vector Machine.

1. Previous Work and Implementation

The paper unifies and extends earlier work on majority votes and PAC-Bayesian analysis, while providing implementation resources for its bounds and MinCq algorithm.

  • The paper extends and unifies prior work by revising the mathematical approach, adding new results, and expanding empirical experiments.
  • Source code is available for computing the PAC-Bayesian bounds and implementing MinCq.

2. Introduction

The introduction motivates tighter analysis of majority votes because Gibbs-risk bounds can miss error compensation among weak voters. It presents the C-bound, PAC-Bayesian extensions, and MinCq as the resulting theoretical and algorithmic framework.

  • 2. Introduction: Gibbs-risk bounds can be loose because voter communities may compensate for individual errors, making majority-vote risk much lower than Gibbs risk.
  • 2. Introduction: The C-bound uses the first two moments of the majority-vote margin to obtain a tighter risk bound via Chebyshev’s inequality.The first moment relates to Gibbs risk, while the second relates to expected voter disagreement.
  • 2. Introduction: The C-bound can be smaller than Gibbs risk and arbitrarily close to zero even when Gibbs risk is close to 1/2.
  • 2. Introduction: The paper develops PAC-Bayesian guarantees for the C-bound, including bounds without KL divergence and extensions to training-data-dependent kernel voters.
  • 2. Introduction: MinCq selects a posterior over classifiers or kernel voters by minimizing the C-bound while accounting for voter quality and disagreement.
  • 2. Introduction: MinCq reduces to a quadratic program and is reported as competitive with AdaBoost and the Support Vector Machine.

3. Basic Definitions

This section defines voters, losses, majority votes, Gibbs classifiers, risks, and disagreement for binary and real-valued settings. It establishes the standard factor-two link between majority-vote and Gibbs risks while highlighting why that link can be misleading.

  • 3. Basic Definitions: A Q-weighted majority vote aggregates voter outputs, with ties treated as abstentions and assigned zero-one loss 1.
  • 3. Basic Definitions: The framework includes zero-one and linear losses for real-valued voters, with the losses coinciding for binary outputs.
  • 3. Basic Definitions: The Gibbs classifier randomly selects a voter from Q, while its generalized risk is defined using expected linear loss.
  • 3. Basic Definitions: The majority-vote risk is bounded by twice the Gibbs risk: R_D′(B_Q) ≤ 2 R_D′(G_Q).
  • 3. Basic Definitions: The factor-two bound can be misleading because a majority vote may be perfect even when the Gibbs risk is nearly 1/2.
  • 3. Basic Definitions: Expected disagreement measures pairwise voter differences and can be estimated from unlabeled data because it does not depend on example labels.

4. Bounds on the Risk of the Majority Vote

The C-bound upper-bounds majority-vote risk using the first two moments of the margin, linking Gibbs risk with voter disagreement. It can be much smaller than the Gibbs-risk bound and empirically predicts vote risk and supports Boosting stopping decisions.

  • The C-bound upper-bounds majority-vote risk from the first and second moments of its margin distribution.It is obtained by extending the first-moment Markov analysis to the second-moment Chebyshev analysis.
  • The bound decreases when Gibbs risk decreases or voter disagreement increases, requiring a trade-off between voter quality and disagreement.This captures information absent from bounds that focus only on Gibbs risk.
  • The C-bound is optimal when its value is below twice the Gibbs risk, the classical majority-vote risk bound.Under this condition, a margin distribution with the same first two moments can attain the C-bound.
  • 4.5.1 The C-bound as a Predictor of the Risk of the Majority Vote: Experiments show that the C-bound strongly correlates with majority-vote risk, whereas Gibbs risk and margin variance alone do not.On AdaBoost runs over UCI binary datasets, C-bound values were almost linearly related to test-set majority-vote risk.
  • 4.5.2 The C-bound as a Stopping Criterion for Boosting: The empirical C-bound is a good Boosting stopping criterion, outperforming empirical Bayes-risk selection and validation while matching cross-validation accuracy with less running time.The comparison notes overfitting for empirical Bayes-risk selection and reduced training data for validation-based selection.

5. A PAC-Bayesian Story: From Zero to a PAC-Bayesian C-bound

The section develops a self-contained PAC-Bayesian framework that estimates the C-bound from empirical observations and connects general risk bounds to majority-vote guarantees.

  • The analysis estimates the C-bound from its empirical counterpart and derives majority-vote risk bounds from those observations.
  • Classical PAC-Bayesian bounds use empirical Gibbs risk and KL(Q∥P), where the posterior is compared with a prior chosen before observing data.
  • The change-of-measure inequality is a key proof step, relying on the KL divergence definition and Jensen’s inequality.
  • A general PAC-Bayesian theorem for real-valued losses serves as the basis for several specialized bounds.
  • Choosing m′ different from the training-set size changes the relative weighting of KL(Q∥P) and logarithmic terms and can tighten the bound.

5.2 PAC-Bayesian Theory for the Gibbs Classifier

This section develops classical PAC-Bayesian bounds for the Gibbs classifier and converts a Gibbs-risk bound into a majority-vote bound through a factor of two.

  • Corollaries 21 and 22 provide classical PAC-Bayesian bounds on Gibbs risk, with Corollary 21 related to Langford–Seeger and Corollary 22 to McAllester.
  • The empirical bound is computed by finding the largest value in a confidence interval for true Gibbs risk.
  • PAC-Bound 0 upper-bounds majority-vote risk by first bounding Gibbs risk and then multiplying the result by 2.
  • If the Gibbs-risk condition is not useful, the majority-vote bound becomes the trivial upper bound 1.
  • PAC-Bound 0 has no closed-form expression and is therefore computed using a root-finding method.

5.3 Joint Error, Joint Success, and Paired-voters

The section introduces joint error, joint success, and paired-voters to express disagreement-related quantities needed for PAC-Bayesian C-bound analysis.

  • Expected joint error and expected joint success are defined as pairwise quantities for a voter distribution.
  • The first two moments of the majority-vote margin connect Gibbs risk and expected disagreement to the C-bound.
  • Losses on paired-voters allow expected joint quantities to be recovered and used to bound the C-bound.
  • Paired-voters combine two voters into a tuple, with the paired-voter distribution assigning product weights Q(fi)·Q(fj).

5.4 PAC-Bayesian Theory For Losses of Paired-voters

The section derives PAC-Bayesian bounds on the C-bound by combining Gibbs-risk bounds with bounds on voter disagreement, including a semi-supervised variant.

  • PAC-Bound 1 bounds majority-vote risk through the C-bound using an upper bound on Gibbs risk and a lower bound on expected disagreement.
  • The paired-voter theorem supplies PAC-Bayesian bounds for expected disagreement, joint success, or joint error.
  • PAC-Bound 1′ uses unlabeled data to obtain a tighter disagreement bound in the semi-supervised setting.
  • The bound can degrade rapidly when its numerator and denominator are bounded loosely, while abundant unlabeled data can improve disagreement estimation.
  • Computing PAC-Bound 1 requires solving for Gibbs-risk and disagreement quantities, after which the C-bound expression gives the majority-vote bound.

5.5 PAC-Bayesian Theory to Directly Bound the C-bound

The section develops PAC-Bayesian bounds that directly constrain the C-bound by jointly controlling paired-voter losses, culminating in PAC-Bounds 2 and 2’.

  • A PAC-Bayesian Theorem for Any Pair Among eD: Theorem 28 replaces the usual Bernoulli divergence with a KL divergence between trivalent random variables to obtain these paired-loss guarantees.The proof uses a trinomial representation of paired-voter outcomes and a corresponding concentration lemma.
  • A PAC-Bayesian Theorem for Any Pair Among eD: Theorem 28 directly bounds the C-bound by simultaneously controlling any pair among the error, success, and disagreement expectations using trivalent random variables.Its trivalent PAC-Bayesian theorem is tighter for the three-outcome case than more general k-valent results.
  • Another Bound for the Risk of the Majority Vote: The achievable region may contain disagreement and joint-error pairs that no data-generating distribution can realize, limiting the sharpness of the resulting bound.The analysis notes that such points are mathematically admissible but impossible in practice.
  • Another Bound for the Risk of the Majority Vote: PAC-Bound 2 directly bounds the C-bound from an empirically constrained achievable region of disagreement and joint error values.The region is optimized numerically, with the resulting supremum providing an upper bound on the majority-vote risk.

5.6 Empirical Comparison Between PAC-Bounds on the Bayes Risk RD(BQ)

The empirical comparison evaluates PAC-Bounds during AdaBoost and finds that bounds using more information are generally tighter, while all bounds eventually degrade during boosting.

  • Empirical comparison: PAC-Bound 1 is generally tighter than PAC-Bound 0, PAC-Bound 2 gives a substantial further improvement, and PAC-Bound 2’ adds almost no improvement in this experiment.The comparison uses AdaBoost with decision stumps on the Mushroom data set across boosting rounds.
  • Empirical comparison: Using unlabeled data to estimate disagreement makes PAC-Bound 1’ the tightest bound in the comparison.The estimate uses the empirical disagreement computed on the testing set.
  • Empirical comparison: After 8 boosting rounds, all bounds degrade even though the empirical C-bound continues to decrease.The degradation is attributed to the denominator of the C-bound tending toward zero, making slack in the first-margin-moment bound multiplicative.
  • Empirical comparison: Figure 7 compares the bounds on RD(BQ) over 60 rounds of boosting.The experiment computes PAC-Bound 0 and the paper’s other PAC-Bayesian variants for each round.

6. PAC-Bayesian Bounds without KL

The paper removes the KL-divergence term from PAC-Bayesian bounds by restricting posteriors to aligned distributions on self-complemented voter sets, producing bounds that support C-bound minimization.

  • Aligned posteriors: Aligned-posterior PAC-Bayesian bounds eliminate the KL term, provided the voter set is self-complemented and the posterior satisfies the alignment restriction.For uniform priors, aligned posteriors are called quasi-uniform and induce bounded voter weights.
  • Aligned posteriors: The alignment restriction acts as built-in regularization, while quasi-uniform distributions also make the KL term necessarily small before it is removed.The paper relates this restriction to an L∞-norm regularization of voter weights.
  • Aligned posteriors: Theorem 31 provides the PAC-Bayesian theorem for aligned posteriors, using a symmetry condition on the convex divergence and replacing the standard change-of-measure step.Its parameter m′ is later needed for sample-compressed voters, where m′ = m − λ.
  • Limitation: The aligned-posterior theorem cannot be applied straightforwardly to paired voters because the product of two aligned posteriors need not remain aligned.The paper therefore requires an additional construction to remove the KL term in the paired-voter setting.
  • PAC-Bound 3: PAC-Bound 3 bounds the C-bound, and therefore majority-vote risk, for aligned posteriors without a KL term while separately controlling Gibbs risk and expected disagreement.Its moment-based form supplies the basis for the MinCq learning algorithm.

7. PAC-Bayesian Theory for Sample-Compressed Voters

The sample-compression framework extends PAC-Bayesian C-bound guarantees to voters constructed from training examples, including kernel voters, while correcting the bias of their empirical Gibbs risk.

  • Motivation: Standard PAC-Bayesian theorems fail for kernel voters defined from training examples because their voter set depends on data that the prior must precede.The paper addresses this mismatch through sample compression rather than an RKHS or representer-theorem construction.
  • Sample-compression setting: A sample-compressed voter is represented by a compression sequence from the training data plus a message, with a reconstruction function producing the classifier.The prior and posterior are placed on compression indices and messages so the prior can be defined before observing the data.
  • Correcting empirical-risk bias: Sample compression introduces bias because a voter may avoid errors on examples in its own compression sequence, so its empirical Gibbs risk is not unbiased.The bounds replace the usual sample-size factor with one depending on the compression size, using m − λ effective examples.
  • Consequences: The sample-compression results preserve the no-KL PAC-Bayesian framework and provide the bounds used to develop MinCq.The preceding PAC-Bayesian results are generalized, with the no-KL bounds retained for the learning algorithm.
  • Kernel voters: The resulting PAC-Bound 3’ applies the aligned-posterior C-bound analysis to majority votes whose voters are kernel functions constructed from compressed training examples.The construction uses compression size at most one and yields a risk bound for aligned posteriors.

8. MinCq: Learning by Minimizing the C-bound

MinCq constructs weighted majority votes by minimizing the C-bound while constraining voter distributions to control overfitting. Across three evaluation contexts, it is competitive with AdaBoost and SVM, with strongest gains on handwritten-digit recognition.

  • 8. MinCq: Learning by Minimizing the C-bound: MinCq minimizes the C-bound through quadratic programming, constructing weighted majority votes from a finite set of classifiers or kernel-based voters.The supervised version minimizes the C-bound; both supervised and transductive variants can be expressed as quadratic programs on positive semidefinite matrices.
  • 8. MinCq: Learning by Minimizing the C-bound: To reduce overfitting, MinCq uses quasi-uniform voter distributions and constrains the first margin moment to exceed a positive hyperparameter µ.The hyperparameter µ is selected by cross-validation, and PAC-Bounds 3 and 3’ provide the theoretical justification for these constraints.
  • 8. MinCq: Learning by Minimizing the C-bound: Minimizing the C-bound requires reducing margin variance while maintaining the first margin moment, favoring voters whose errors are maximally uncorrelated.This provides the stated theoretical rationale for MinCq and connects its objective to the compensation of individual voter errors.
  • 8. MinCq: Learning by Minimizing the C-bound: Restricting voters to quasi-uniform distributions loses no generality because an equivalent distribution can preserve the majority vote and C-bound.Theorem 43 states that every distribution has a quasi-uniform counterpart with the same majority vote and empirical and true C-bound values.
  • 8.3 Experiments: MinCq is highly competitive with AdaBoost and SVM, achieving a highly significant gain on handwritten-digit recognition while matching competitors on other evaluated contexts.On UCI tasks, MinCq and SVM or AdaBoost perform similarly; on Amazon reviews, LinearMinCq has an edge but no statistically significant difference.
  • 8.3.4 Experiments with Stronger Voters: For stronger voters on Mushroom, PAC-Bounds tighten as µ increases, while the empirical C-bound and testing risk rise slightly at the largest µ values.PAC-Bound 3 is looser than the other bounds but follows the same behavior, supporting its use to justify MinCq after µ is fixed.

9. Conclusion

The paper consolidates the C-bound and PAC-Bayesian extensions that support MinCq, while positioning the analysis within broader developments of PAC-Bayesian learning theory.

  • 9. Conclusion: The paper frames its contributions as a clarified and extended treatment of prior work while noting that PAC-Bayesian theory is being applied to increasingly sophisticated learning settings.
  • 9. Conclusion: The C-bound uses the first two moments of the majority vote’s margin distribution and has strong empirical predictive power for majority-vote risk.It is based on the one-sided Chebyshev inequality, which is tight under the stated mild condition.
  • 9. Conclusion: PAC-Bayesian results provide high-confidence estimates of the C-bound uniformly over all posterior distributions.
  • 9. Conclusion: The analysis extends to sample compression and kernel-defined voters, and also derives bounds without a Kullback-Leibler divergence term.
  • 9. Conclusion: These theoretical results ground MinCq, which can be formulated as a quadratic program and performs very well compared with the state-of-the-art SVM on natural data.

Appendix A. Auxiliary mathematical results

Appendix A collects foundational inequalities and convexity results used in the paper’s PAC-Bayesian analysis, including concentration, divergence, and concavity arguments.

  • Appendix A. Auxiliary mathematical results: Markov’s and one-sided Chebyshev’s inequalities relate probabilities to expectations and variance, supplying concentration tools for the analysis.
  • Appendix A. Auxiliary mathematical results: Jensen’s inequality and convexity results establish the expectation bounds needed for later PAC-Bayesian derivations.
  • Appendix A. Auxiliary mathematical results: The appendix generalizes Maurer’s lemma from scalar variables to pairs with three possible outcomes using convex combinations of extreme points.
  • Appendix A. Auxiliary mathematical results: The function FC(d, e) is shown to be concave by proving that its Hessian matrix is negative semi-definite.

Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors

Appendix B generalizes PAC-Bayesian change-of-measure arguments to tuples of voters and posterior distributions aligned with a prior.

  • Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors: The appendix develops a generalized change-of-measure inequality and PAC-Bayesian theorem for tuples of voters and aligned posteriors.
  • Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors: The appendix presents these generalizations because they require more complex notation than the simpler main-paper theorems.
  • Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors: A self-complemented voter set uses a bijection mapping each voter to its negative, while alignment requires paired posterior and prior masses to agree.
  • Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors: The construction represents tuples of votes through Cartesian products of the posterior and prior distributions and enumerates complemented vote configurations.
  • Appendix B. A General PAC-Bayesian Theorem for Tuples of Voters and Aligned Posteriors: The proof combines the generalized change-of-measure inequality with Jensen’s inequality and convexity to obtain a uniform result for all aligned posteriors.
Loading 1503.08329v2…