The dynamics of AdaBoost: Cyclic behavior and convergence of margins

Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire

Research output: Contribution to journalArticlepeer-review

74 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
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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