Math @ Duke

Publications [#287109] of Ingrid Daubechies
Papers Published
 Rudin, C; Daubechies, I; Schapire, RE, The dynamics of AdaBoost: Cyclic behavior and convergence of margins,
Journal of Machine Learning Research, vol. 5
(December, 2004),
pp. 15571595
(last updated on 2019/08/21)
Abstract: © 2004 Cynthia Rudin, Ingrid Daubechies and Robert E. Schapire. In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach allows us to understand AdaBoost's convergence properties completely in certain cases; for these cases we find stable cycles, allowing us to explicitly solve for AdaBoost's output. Using this unusual technique, we are able to show that AdaBoost does not always converge to a maximum margin combined classifier, answering an open question. In addition, we show that "nonoptimal" AdaBoost (where the weak learning algorithm does not necessarily choose the best weak classifier at each iteration) may fail to converge to a maximum margin classifier, even if "optimal" AdaBoost produces a maximum margin. Also, we show that if AdaBoost cycles, it cycles among "support vectors", i.e., examples that achieve the same smallest margin.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

