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

Abstract

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