Second Order PAC-Bayesian Bounds for the Weighted Majority Vote
We present a novel analysis of the expected risk of weighted majority vote in multiclass classification. The analysis takes correlation of predictions by ensemble members into account and provides a bound that is amenable to efficient minimization, which yields improved weighting for the majority vote. We also provide a specialized version of our bound for binary classification, which allows to exploit additional unlabeled data for tighter risk estimation. In experiments, we apply the bound to improve weighting of trees in random forests and show that, in contrast to the commonly used first order bound, minimization of the new bound typically does not lead to degradation of the test error of the ensemble.
Code (1)
Tasks
Binary ClassificationClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
We present a new second-order oracle bound for the expected risk of a weighted majority vote. The bound is based on a novel parametric form of the Chebyshev- Cantelli inequality (a.k.a. one-sided Chebyshev's), which is a…
FormMulti-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds
The PAC-Bayesian framework has significantly advanced the understanding of statistical learning, particularly for majority voting methods. Despite its successes, its application to multi-view learning -- a setting with m…
Generalization BoundsMULTI-VIEW LEARNINGOn the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm
Weighted majority votes are central to many successful ensemble methods. PAC-Bayesian theory provides tight generalization guarantees for such models by analyzing the expected risk of stochastic classifiers, while analyz…
Consistency of weighted majority votes
We revisit the classical decision-theoretic problem of weighted expert voting from a statistical learning perspective. In particular, we examine the consistency (both asymptotic and finitary) of the optimal Nitzan-Parous…
Error Rate Bounds and Iterative Weighted Majority Voting for Crowdsourcing
Crowdsourcing has become an effective and popular tool for human-powered computation to label large datasets. Since the workers can be unreliable, it is common in crowdsourcing to assign multiple workers to one task, and…