The dynamics of AdaBoost: Cyclic behavior and convergence of margins

Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire

Research output: Contribution to journalArticlepeer-review

71 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1557-1595
Number of pages39
JournalJournal of Machine Learning Research
Volume5
StatePublished - Dec 1 2004

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Keywords

  • AdaBoost
  • Boosting
  • Convergence
  • Dynamics
  • Margins

Fingerprint

Dive into the research topics of 'The dynamics of AdaBoost: Cyclic behavior and convergence of margins'. Together they form a unique fingerprint.

Cite this