Complexities of convex combinations and bounding the generalization error in classification
Authors:
Open Access
- 1 August 2005
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Statistics
- Vol. 33 (4) , 1455-1496
Abstract
We introduce and study several measures of complexity of functions from the convex hull of a given base class. These complexity measures take into account the sparsity of the weights of a convex combination as well as certain clustering properties of the base functions involved in it. We prove new upper confidence bounds on the generalization error of ensemble (voting) classification algorithms that utilize the new complexity measures along with the empirical distributions of classification margins, providing a better explanation of generalization performance of large margin classification methods.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Convexity, Classification, and Risk BoundsJournal of the American Statistical Association, 2006
- Aggregated estimators and empirical complexity for least square regressionAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques, 2004
- Complexity regularization via localized random penaltiesThe Annals of Statistics, 2004
- Process consistency for AdaBoostThe Annals of Statistics, 2004
- Bounds on margin distributions inBlearningBproblemsAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques, 2003
- Symmetrization approach to concentration inequalities for empirical processesThe Annals of Probability, 2003
- Bounding the generalization error of convex combinations of classifiers: balancing the dimensionality and the marginsThe Annals of Applied Probability, 2003
- Empirical Margin Distributions and Bounding the Generalization Error of Combined ClassifiersThe Annals of Statistics, 2002
- Some applications of concentration inequalities to statisticsAnnales de la Faculté des sciences de Toulouse : Mathématiques, 2000
- Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimensionJournal of Combinatorial Theory, Series A, 1995