Improved Margin Generalization Bounds for Voting Classifiers
In this paper we establish a new margin-based generalization bound for voting classifiers, refining existing results and yielding tighter generalization guarantees for widely used boosting algorithms such as AdaBoost (Freund and Schapire, 1997). Furthermore, the new margin-based generalization bound enables the derivation of an optimal weak-to-strong learner: a Majority-of-3 large-margin classifiers with an expected error matching the theoretical lower bound. This result provides a more natural alternative to the Majority-of-5 algorithm by (H{\o}gsgaard et al., 2024), and matches the Majority-of-3 result by (Aden-Ali et al., 2024) for the realizable prediction model.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsSimilar Papers 제목 키워드 기반
Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets
We prove the first margin-based generalization bound for voting classifiers, that is asymptotically tight in the tradeoff between the size of the hypothesis set, the margin, the fraction of training points with the given…
On Margins and Generalisation for Voting Classifiers
We study the generalisation properties of majority voting on finite ensembles of classifiers, proving margin-based generalisation bounds via the PAC-Bayes theory. These provide state-of-the-art guarantees on a number of …
On the Insufficiency of the Large Margins Theory in Explaining the Performance of Ensemble Methods
Boosting and other ensemble methods combine a large number of weak classifiers through weighted voting to produce stronger predictive models. To explain the successful performance of boosting algorithms, Schapire et al. …
Margin-Based Generalization Lower Bounds for Boosted Classifiers
Boosting is one of the most successful ideas in machine learning. The most well-accepted explanations for the low generalization error of boosting algorithms such as AdaBoost stem from margin theory. The study of margins…
Generalization BoundsOn the Current State of Research in Explaining Ensemble Performance Using Margins
Empirical evidence shows that ensembles, such as bagging, boosting, random and rotation forests, generally perform better in terms of their generalization error than individual classifiers. To explain this performance, S…