How boosting the margin can also boost classifier complexity

Lev Reyzin, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

64 Scopus citations

Abstract

Boosting methods are known not to usually overfit training data even as the size of the generated classifiers becomes large. Schapire et al. attempted to explain this phenomenon in terms of the margins the classifier achieves on training examples. Later, however, Breiman cast serious doubt on this explanation by introducing a boosting algorithm, arc-gv, that can generate a higher margins distribution than AdaBoost and yet performs worse. In this paper, we take a close look at Breiman's compelling but puzzling results. Although we can reproduce his main finding, we find that the poorer performance of arc-gv can be explained by the increased complexity of the base classifiers it uses, an explanation supported by our experiments and entirely consistent with the margins theory. Thus, we find maximizing the margins is desirable, but not necessarily at the expense of other factors, especially base-classifier complexity.

Original languageEnglish (US)
Title of host publicationACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006
Pages753-760
Number of pages8
DOIs
StatePublished - Dec 1 2006
Event23rd International Conference on Machine Learning, ICML 2006 - Pittsburgh, PA, United States
Duration: Jun 25 2006Jun 29 2006

Publication series

NameACM International Conference Proceeding Series
Volume148

Other

Other23rd International Conference on Machine Learning, ICML 2006
CountryUnited States
CityPittsburgh, PA
Period6/25/066/29/06

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'How boosting the margin can also boost classifier complexity'. Together they form a unique fingerprint.

  • Cite this

    Reyzin, L., & Schapire, R. E. (2006). How boosting the margin can also boost classifier complexity. In ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006 (pp. 753-760). (ACM International Conference Proceeding Series; Vol. 148). https://doi.org/10.1145/1143844.1143939