TY - GEN

T1 - On the dynamics of boosting

AU - Rudin, Cynthia

AU - Daubechies, Ingrid

AU - Schapire, Robert E.

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 2004

Y1 - 2004

N2 - In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for Ada- Boost's output. By considering AdaBoost as a dynamical system, we are able to prove R̈atsch and Warmuth's conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a 'nonoptimal' weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to maximize the margin (such as AdaBoost and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maximum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arcgv.

AB - In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for Ada- Boost's output. By considering AdaBoost as a dynamical system, we are able to prove R̈atsch and Warmuth's conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a 'nonoptimal' weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to maximize the margin (such as AdaBoost and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maximum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arcgv.

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

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

M3 - Conference contribution

AN - SCOPUS:9444247113

SN - 0262201526

SN - 9780262201520

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems 16 - Proceedings of the 2003 Conference, NIPS 2003

PB - Neural information processing systems foundation

T2 - 17th Annual Conference on Neural Information Processing Systems, NIPS 2003

Y2 - 8 December 2003 through 13 December 2003

ER -