Boosting as a Regularized Path to a Maximum Margin Classifier

摘要

In this paper we study boosting methods from a new perspective. Webuild on recent work by Efron et al. to show that boostingapproximately (and in some cases exactly) minimizes its losscriterion with an l₁ constraint on the coefficient vector. Thishelps understand the success of boosting with early stopping asregularized fitting of the loss criterion. For the two mostcommonly used criteria (exponential and binomial log-likelihood),we further show that as the constraint is relaxed---orequivalently as the boosting iterations proceed---the solutionconverges (in the separable case) to an "l₁-optimal"separating hyper-plane. We prove that this l₁-optimalseparating hyper-plane has the property of maximizing the minimall₁-margin of the training data, as defined in the boostingliterature. An interesting fundamental similarity between boostingand kernel support vector machines emerges, as both can bedescribed as methods for regularized optimization inhigh-dimensional predictor space, using a computational trick tomake the calculation practical, and converging tomargin-maximizing solutions. While this statement describes SVMsexactly, it applies to boosting only approximately. color="gray">