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 margin, the number of training samples and the failure probability.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 (Fr…
Generalization BoundsOn 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 BoundsTight Generalization Bound for AdaBoost
In this paper we show that the generalization error of AdaBoost is $Θ\big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big)$, where $γ$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the …
On 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…