On the equivalence of weak learnability and linear separability: New relaxations and efficient boosting algorithms

Shai Shalev-Shwartz, Yoram Singer

Research output: Contribution to conferencePaper

14 Scopus citations

Abstract

Boosting algorithms build highly accurate prediction mechanisms from a collection of low-accuracy predictors. To do so, they employ the notion of weak-learnability. The starting point of this paper is a proof which shows that weak learn-ability is equivalent to linear separability with l1 margin. While this equivalence is a direct consequence of von Neumann's minimax theorem, we derive the equivalence directly using Fenchel duality. We then use our derivation to describe a family of relaxations to the weak-learnability assumption that readily translates to a family of relaxations of linear separability with margin. This alternative perspective sheds new light on known soft-margin boosting algorithms and also enables us to derive several new relaxations of the notion of linear separability. Last, we describe and analyze an efficient boosting framework that can be used for minimizing the loss functions derived from our family of relaxations. In particular, we obtain efficient boosting algorithms for maximizing hard and soft versions of the l1 margin.

Original languageEnglish (US)
Pages311-321
Number of pages11
StatePublished - Dec 1 2008
Externally publishedYes
Event21st Annual Conference on Learning Theory, COLT 2008 - Helsinki, Finland
Duration: Jul 9 2008Jul 12 2008

Other

Other21st Annual Conference on Learning Theory, COLT 2008
CountryFinland
CityHelsinki
Period7/9/087/12/08

All Science Journal Classification (ASJC) codes

  • Education

Fingerprint Dive into the research topics of 'On the equivalence of weak learnability and linear separability: New relaxations and efficient boosting algorithms'. Together they form a unique fingerprint.

  • Cite this

    Shalev-Shwartz, S., & Singer, Y. (2008). On the equivalence of weak learnability and linear separability: New relaxations and efficient boosting algorithms. 311-321. Paper presented at 21st Annual Conference on Learning Theory, COLT 2008, Helsinki, Finland.