Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm

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

156 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Economics and Econometrics, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

Citations in the corpus

Performance Analysis of IoT-Based Sensor, Big Data Processing, and Machine Learning Model for Real-Time Monitoring System in Automotive Manufacturing (2018, methodology): “The Random Forest algorithm is constructed by combining multiple decision trees for more accurate and stable prediction [77].”
User-friendly introduction to PAC-Bayes bounds (2021, unknown): “A similar idea was rediscovered later in classification to upper bound R(Eθ∼ρ[fθ])−Eθ∼ρ[R(fθ)] by a variance term in [81, 132].”
PAC-Bayesian Bounds based on the Rényi Divergence (2016, background): “, Herbrich and Graepel, 2000], tighter bounds are obtained by specializing to linear classifiers [Langford and Shawe-Taylor, 2002], or by exploiting the “voters’ disagreement” [Germain et al., 2015].”