nips nips2003 nips2003-143 nips2003-143-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire
Abstract: 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 AdaBoost’s output. By considering AdaBoost as a dynamical system, we are able to prove R¨ tsch and Warmuth’s conjecture that AdaBoost may fail a 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 arc-gv. 1
[1] Robert E. Schapire. A brief introduction to boosting. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999.
[2] Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651–1686, October 1998.
[3] Gunnar R¨ atsch and Manfred Warmuth. Maximizing the margin with boosting. In Proceedings of the 15th Annual Conference on Computational Learning Theory, pages 334–350, 2002.
[4] Gunnar R¨ atsch and Manfred Warmuth. Efficient margin maximizing with boosting. Journal of Machine Learning Research, submitted 2002.
[5] Leo Breiman. Prediction games and arcing classifiers. Neural Computation, 11(7):1493–1517, 1999.
[6] Michael Collins, Robert E. Schapire, and Yoram Singer. Logistic regression, AdaBoost and Bregman distances. Machine Learning, 48(1/2/3), 2002.
[7] Saharon Rosset, Ji Zhu, and Trevor Hastie. Boosting as a regularized path to a maximum margin classifier. Technical report, Department of Statistics, Stanford University, 2003.