Leveraging the margin more carefully

Nir Krause, Yoram Singer

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

41 Scopus citations

Abstract

Boosting is a popular approach for building accurate classifiers. Despite the initial popular belief, boosting algorithms do exhibit overfitting and are sensitive to label noise. Part of the sensitivity of boosting algorithms to outliers and noise can be attributed to the unboundedness of the margin-based loss functions that they employ. In this paper we describe two leveraging algorithms that build on boosting techniques and employ a bounded loss function of the margin. The first algorithm interleaves the expectation maximization (EM) algorithm with boosting steps. The second algorithm decomposes a non-convex loss into a difference of two convex losses. We prove that both algorithms converge to a stationary point. We also analyze the generalization properties of the algorithms using the Rademacher complexity. We describe experiments with both synthetic data and natural data (OCR and text) that demonstrate the merits of our framework, in particular robustness to outliers.

Original languageEnglish (US)
Title of host publicationProceedings, Twenty-First International Conference on Machine Learning, ICML 2004
EditorsR. Greiner, D. Schuurmans
Pages496-503
Number of pages8
StatePublished - Dec 1 2004
Externally publishedYes
EventProceedings, Twenty-First International Conference on Machine Learning, ICML 2004 - Banff, Alta, Canada
Duration: Jul 4 2004Jul 8 2004

Publication series

NameProceedings, Twenty-First International Conference on Machine Learning, ICML 2004

Other

OtherProceedings, Twenty-First International Conference on Machine Learning, ICML 2004
CountryCanada
CityBanff, Alta
Period7/4/047/8/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Leveraging the margin more carefully'. Together they form a unique fingerprint.

  • Cite this

    Krause, N., & Singer, Y. (2004). Leveraging the margin more carefully. In R. Greiner, & D. Schuurmans (Eds.), Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004 (pp. 496-503). (Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004).