Thumbnail
Access Restriction
Open

Author Panchenko, Dmitriy
Source CiteSeerX
Content type Text
Publisher Morgan Kaufmann
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword New Observation ♦ Class Classification Problem ♦ Main Technical Difficulty ♦ Abstract Uniform Entropy Condition ♦ Generalization Ability ♦ Separate Section ♦ Support Vector Machine ♦ Weak Classifier ♦ New Bound ♦ New Zero-error Bound ♦ Vc Class ♦ Zero Error Version ♦ Generalization Error ♦ Sample Size ♦ Weak Classifier Consists ♦ Vc-subgraph Class ♦ Training Set ♦ Toy Problem ♦ Voting Algorithm ♦ Several Direction ♦ Empirical Distribution
Description In this paper we prove new bounds for the generalization error of voting learning algorithms such as boosting, bagging or support vector machines in the framework of two class classification problem. This paper continues the line of research pioneered in the work of Schapire et al. who explained the generalization ability of voting classifiers via the empirical distribution of the margin and the complexity of the family of weak classifiers. In this paper we extend their result in several directions. First of all, we prove a zero error version of their bound which significantly improves the dependence of the bound on all parameters such as sample size. Secondly, we consider the case when the set of weak classifiers consists of real valued uniformly bounded functions and satis es some abstract uniform entropy condition, for example, when the set of weak classifiers is a VC-subgraph class of functions. This is the main technical difficulty of the paper, compared to an easier case of VC classes of sets that was considered in the work of Schapire et al. We consider VC classes of sets in a separate section together with some new observations about families of weak classifiers that depend on the training set. We also incorporate some measure of the sparsity of representation of a combined classifier into the bound. Finally, we experiment with two toy problems to study the performance of the bounds.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2001-01-01
Publisher Institution In Proceedings of the Thirteenth Na-tional Conference on Artificial Intelligence