Bounding the generalization error of convex combinations of classifiers: Balancing the dimensionality and the margins

• 成果类型: Article
• 署名作者: Koltchinskii, V; Panchenko, D; Lozano, F
• 署名单位: University of New Mexico; Pontificia Universidad Javeriana
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2003
• 页码: 213-252
• 关键词: Concentration Inequalities

摘要

A problem of bounding the generalization error of a classifier f is an element of conv(H), where H is a base class of functions (classifiers), is considered. This problem frequently occurs in computer learning, where efficient algorithms that combine simple classifiers into a complex one (such as boosting and bagging) have attracted a lot of attention. Using Talagrand's concentration inequalities for empirical processes, we obtain new sharper bounds on the generalization error of combined classifiers that take into account both the empirical distribution of classification margins and an approximate dimension of the classifiers, and study the performance of these bounds in several experiments with learning algorithms.