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

Abstract

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.

Published in JMLR http://jmlr.org/papers/v16/germain15a.html

References in corpus (3)

• A Note on the PAC Bayesian Theorem
• Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms
• Proof of a Combinatorial Conjecture Coming from the PAC-Bayesian Machine Learning Theory

Cited by in corpus (24)

• Learn on Source, Refine on Target:A Model Transfer Learning Framework with Random Forests
• Tighter risk certificates for neural networks
• A New PAC-Bayesian Perspective on Domain Adaptation
• Subgroup Generalization and Fairness of Graph Neural Networks
• A survey on domain adaptation theory: learning bounds and theoretical guarantees
• A Strongly Quasiconvex PAC-Bayesian Bound
• PAC-Bayes and Domain Adaptation
• PAC-Bayesian Theory Meets Bayesian Inference
• Second Order PAC-Bayesian Bounds for the Weighted Majority Vote
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• PAC-Bayes Analysis Beyond the Usual Bounds
• Diversity and Generalization in Neural Network Ensembles
• A PAC-Bayes Analysis of Adversarial Robustness
• Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
• How Tight Can PAC-Bayes be in the Small Data Regime?
• On the Current State of Research in Explaining Ensemble Performance Using Margins
• Ensemble Pruning via Margin Maximization
• Machine Truth Serum
• There is no Double-Descent in Random Forests
• FWDA: a Fast Wishart Discriminant Analysis with its Application to Electronic Health Records Data Classification
• Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Bound
• Multi-class Probabilistic Bounds for Self-learning
• A combinatorial conjecture from PAC-Bayesian machine learning
• Distribution-Dependent Analysis of Gibbs-ERM Principle