Celebratio Mathematica

C. Rudin, I. Daubechies, and R. E. Schapire: “The dynamics of AdaBoost: Cyclic behavior and convergence of margins,” J. Mach. Learn. Res. 5 (2003–2004), pp. 1557–1595. MR 2248027 Zbl 1222.68293 article

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.

Cynthia Diane Rudin	Related
Robert Elias Schapire	Related

C. Rudin, R. E. Schapire, and I. Daubechies: “Boosting based on a smooth margin,” pp. 502–517 in Learning theory: 17th annual conference on learning theory (Banff, AB, 1–4 July 2004). Edited by J. Shawe-Taylor and Y. Singer. Lecture Notes in Computer Science 3120. Springer (Berlin), 2004. MR 2177931 Zbl 1078.68724 incollection

We study two boosting algorithms, Coordinate Ascent Boosting and Approximate Coordinate Ascent Boosting, which are explicitly designed to produce maximum margins. To derive these algorithms, we introduce a smooth approximation of the margin that one can maximize in order to produce a maximum margin classifier. Our first algorithm is simply coordinate ascent on this function, involving a line search at each step. We then make a simple approximation of this line search to reveal our second algorithm. These algorithms are proven to asymptotically achieve maximum margins, and we provide two convergence rate calculations. The second calculation yields a faster rate of convergence than the first, although the first gives a more explicit (still fast) rate. These algorithms are very similar to AdaBoost in that they are based on coordinate ascent, easy to implement, and empirically tend to converge faster than other boosting algorithms. Finally, we attempt to understand AdaBoost in terms of our smooth margin, focusing on cases where AdaBoost exhibits cyclic behavior.

Robert Elias Schapire	Related
Cynthia Diane Rudin	Related
John Stewart Shawe-Taylor	Related
Yoram Singer	Related

C. Rudin, I. Daubechies, and R. Schapire: “On the dynamics of boosting” in Advances in neural information processing systems 16: Proceedings of the 2003 conference (Vancouver and Whistler, BC, 8–13 December 2003). Edited by S. Thrun, L. K. Saul, and B. Schölkopf. MIT Press (Cambridge, MA), 2004. incollection

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 Ratsch and Warmuth’s conjecture that AdaBoost may fail 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.

Lawrence Kevin Saul	Related
Robert Elias Schapire	Related
Sebastian Thrun	Related
Bernhard Schölkopf	Related
Cynthia Diane Rudin	Related

C. Rudin, R. E. Schapire, and I. Daubechies: “Analysis of boosting algorithms using the smooth margin function,” Ann. Statist. 35 : 6 (2007), pp. 2723–2768. MR 2382664 Zbl 1132.68827 ArXiv 0803.4092 article

We introduce a useful tool for analyzing boosting algorithms called the “smooth margin function,” a differentiable approximation of the usual margin for boosting algorithms. We present two boosting algorithms based on this smooth margin, “coordinate ascent boosting” and “approximate coordinate ascent boosting,” which are similar to Freund and Schapire’s AdaBoost algorithm and Breiman’s arc-gv algorithm. We give convergence rates to the maximum margin solution for both of our algorithms and for arc-gv. We then study AdaBoost’s convergence properties using the smooth margin function. We precisely bound the margin attained by AdaBoost when the edges of the weak classifiers fall within a specified range. This shows that a previous bound proved by Rätsch and Warmuth is exactly tight. Furthermore, we use the smooth margin to capture explicit properties of AdaBoost in cases where cyclic behavior occurs.

Cynthia Diane Rudin	Related
Robert Elias Schapire	Related

C. Rudin, R. E. Schapire, and I. Daubechies: “Precise statements of convergence for AdaBoost and arc-gv,” pp. 131–145 in Prediction and discovery: AMS-IMS-SIAM joint summer research conference on machine and statistical learning (Snowbird, UT, 25–29 June 2006). Edited by J. S. Verducci, X. Shen, and J. Lafferty. Contemporary Mathematics 443. American Mathematical Society (Providence, RI), 2007. Paper dedicated to Leo Breiman. Available open access here. MR 2433289 Zbl 1141.68722 incollection

We present two main results, the first concerning Freund and Schapire’s AdaBoost algorithm, and the second concerning Breiman’s arc-gv algorithm. Our discussion of AdaBoost revolves around a circumstance called the case of “bounded edges”, in which AdaBoost’s convergence properties can be completely understood. Specifically, our first main result is that if AdaBoost’s “edge” values fall into a small interval, a corresponding interval can be found for the asymptotic margin. A special case of this result closes an open theoretical question of Rätsch and Warmuth. Our main result concerning arc-gv is a convergence rate to a maximum margin solution. Both of these results are derived from an important tool called the “smooth margin”, which is a differentiable approximation of the true margin for boosting algorithms.

Robert Elias Schapire	Related
Leo Breiman	Related
Cynthia Diane Rudin	Related
Xiaotong Shen	Related
Joseph Stephen Verducci	Related
John D. Lafferty	Related

@incollection {key2433289m,
	AUTHOR = {Rudin, Cynthia and Schapire, Robert
		 E. and Daubechies, Ingrid},
	TITLE = {Precise statements of convergence for
		 {A}da{B}oost and arc-gv},
	BOOKTITLE = {Prediction and discovery: {AMS}-{IMS}-{SIAM}
		 joint summer research conference on
		 machine and statistical learning},
	EDITOR = {Verducci, Joseph S. and Shen, Xiaotong
		 and Lafferty, John},
	SERIES = {Contemporary Mathematics},
	NUMBER = {443},
	PUBLISHER = {American Mathematical Society},
	ADDRESS = {Providence, RI},
	YEAR = {2007},
	PAGES = {131--145},
	DOI = {10.1090/conm/443/08559},
	NOTE = {(Snowbird, UT, 25--29 June 2006). Paper
		 dedicated to Leo Breiman. Available
		 open access at http://web.mit.edu/rudin/www/docs/RudinScDa07a.pdf.
		 MR:2433289. Zbl:1141.68722.},
	ISSN = {0271-4132},
	ISBN = {9780821841952},
}

year	title	people

			clear

Ingrid Daubechies

Complete Bibliography

Works connected to Robert Elias Schapire

Filter the Bibliography List