The Dynamics of AdaBoost

author: Cynthia Rudin, Sloan School of Management, Massachusetts Institute of Technology, MIT
published: Feb. 25, 2007,   recorded: May 2005,   views: 24685


Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Delicious Bibliography


One of the most successful and popular learning algorithms is AdaBoost, which is a classification algorithm designed to construct a "strong" classifier from a "weak" learning algorithm. Just after the development of AdaBoost nine years ago, scientists derived margin- based generalization bounds to explain AdaBoost's unexpectedly good performance. Their result predicts that AdaBoost yields the best possible performance if it always achieves a "maximum margin" solution. Yet, does AdaBoost achieve a maximum margin solution? Empirical and theoretical studies conducted within this period conjecture the answer to be "yes". In order to answer this question, we look toward AdaBoost's dynamics. We simplify AdaBoost to reveal a nonlinear iterated map. We then analyze the convergence of AdaBoost for cases where cyclic behavior is found; this cyclic behavior provides the key to answering the question of whether AdaBoost always maximizes the margin. As it turns out, the answer to this question turns out to be the opposite of what was thought to be true! In this talk, I will introduce AdaBoost, describe our analysis of AdaBoost when viewed as a dynamical system, briefly mention a new boosting algorithm which always maximizes the margin with a fast convergence rate, and if time permits, I will reveal a surprising new result about AdaBoost and the problem of bipartite ranking.

See Also:

Download slides icon Download slides: Cynthia_Rudin.ppt (1.8┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Oscar, August 26, 2008 at 10:33 a.m.:

Not bad, but I recommend Robert Schapire's lecture first, or rather: instead.

Comment2 Rob, June 26, 2009 at 4:39 p.m.:

For a tutorial on the main concepts of boosting, check Robert Schapire's lecture. This lectures discusses the margin maximization issues in detail.
Slide synchronization is very bad, sometimes you miss some slides, author is talking about different slide than the one displayed on the site.
Furthermore, when the author explains the cycles, this camera is not on the slide, to the whole concept is not visible to the user. Too bad.

Spontaneous and nicely presented by the author.

Comment3 qinliu, November 4, 2011 at 11:28 a.m.:

vey good

Write your own review or comment:

make sure you have javascript enabled or clear this field: