Logistic regression, AdaBoost and Bregman distances

TY - JOUR

T1 - Logistic regression, AdaBoost and Bregman distances

AU - Collins, Michael

AU - Schapire, Robert E.

AU - Singer, Yoram

PY - 2002/7

Y1 - 2002/7

N2 - We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this framework allows us to design and analyze algorithms for both simultaneously, and to easily adapt algorithms designed for one problem to the other. For both problems, we give new algorithms and explain their potential advantages over existing methods. These algorithms are iterative and can be divided into two types based on whether the parameters are updated sequentially (one at a time) or in parallel (all at once). We also describe a parameterized family of algorithms that includes both a sequential- and a parallel-update algorithm as special cases, thus showing how the sequential and parallel approaches can themselves be unified. For all of the algorithms, we give convergence proofs using a general formalization of the auxiliary-function proof technique. As one of our sequential-update algorithms is equivalent to AdaBoost, this provides the first general proof of convergence for AdaBoost. We show that all of our algorithms generalize easily to the multiclass case, and we contrast the new algorithms with the iterative scaling algorithm. We conclude with a few experimental results with synthetic data that highlight the behavior of the old and newly proposed algorithms in different settings.

AB - We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this framework allows us to design and analyze algorithms for both simultaneously, and to easily adapt algorithms designed for one problem to the other. For both problems, we give new algorithms and explain their potential advantages over existing methods. These algorithms are iterative and can be divided into two types based on whether the parameters are updated sequentially (one at a time) or in parallel (all at once). We also describe a parameterized family of algorithms that includes both a sequential- and a parallel-update algorithm as special cases, thus showing how the sequential and parallel approaches can themselves be unified. For all of the algorithms, we give convergence proofs using a general formalization of the auxiliary-function proof technique. As one of our sequential-update algorithms is equivalent to AdaBoost, this provides the first general proof of convergence for AdaBoost. We show that all of our algorithms generalize easily to the multiclass case, and we contrast the new algorithms with the iterative scaling algorithm. We conclude with a few experimental results with synthetic data that highlight the behavior of the old and newly proposed algorithms in different settings.

KW - AdaBoost

KW - Boosting

KW - Bregman distances

KW - Convex optimization

KW - Information geometry

KW - Iterative scaling

KW - Logistic regression

KW - Maximum-entropy methods

UR - http://www.scopus.com/inward/record.url?scp=0036643072&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036643072&partnerID=8YFLogxK

U2 - https://doi.org/10.1023/A:1013912006537

DO - https://doi.org/10.1023/A:1013912006537

M3 - Article

SN - 0885-6125

VL - 48

SP - 253

EP - 285

JO - Machine Learning

JF - Machine Learning

IS - 1-3

ER -