Author: Shalev-Shwartz Shai
Publisher: Springer Publishing Company
ISSN: 0885-6125
Source: Machine Learning, Vol.80, Iss.2-3, 2010-09, pp. : 141-163
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
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 learnability is equivalent to linear separability with l 1 margin. The equivalence is a direct consequence of von Neumann’s minimax theorem. Nonetheless, 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 l 1 margin.
Related content
On the Existence of Linear Weak Learners and Applications to Boosting
By Mannor S.
Machine Learning, Vol. 48, Iss. 1-3, 2002-07 ,pp. :
The Strength of Weak Learnability
Machine Learning, Vol. 05, Iss. 2, 1990-06 ,pp. :