New framework turns random ensemble votes into reliable single votes
On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm
Machine Learning
Summary
In machine learning, combining many small models by taking a weighted majority vote helps improve predictions. Usually, it’s easier to analyze the performance of a random choice among these models rather than the final combined vote, leading to less direct guarantees for the majority vote itself. The authors build on recent mathematical advances to transform these random-vote guarantees into strong assurances for a single, fixed majority vote. This approach also leads to a way of training ensembles that directly optimize the final combined vote’s reliability.
What this means in practice
- •For machine learning engineers: Develop ensemble classifiers with tighter guarantees on their deterministic combined output's accuracy, improving reliability in automated decision systems.
- •For data science teams: Use the new learning algorithm to optimize majority vote models directly for better predictive performance on given datasets.
A theory result. No direct application yet.
Authors
Julien Bastian, Benjamin Leblanc, Pascal Germain, Amaury Habrard, Guillaume Metzler, Emilie Morvant, Paul Viallard
Abstract
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 analyzing the risk of deterministic majority votes relies on surrogate bounds. To avoid these surrogates, Zantedeschi et al. ( 2021) introduced guarantees for stochastic majority votes, but the resulting models remain randomized. In this paper, we propose a derandomization framework for stochastic majority votes. To do so, we apply recent advances in disintegrated PAC-Bayesian theory directly to the space of majority vote weight vectors, transforming stochastic guarantees into certificates for a single deterministic majority vote. We derive two families of high-probability generalization bounds, covering both data-independent and data-dependent constructions of the ensemble, which naturally lead to a self-bounding learning algorithm optimizing deterministic majority vote guarantees.