Rob Schapire and Yoav Freund receive Goedel Prize for AdaBoost algorithm

[Manfred Warmuth]

The Goedel Prize is one of most prestigious
prizes in Theoretical Computer Science
(jointly sponsored by EATCS and SIGACT).

This is the first time that a paper in
Machine Learning received this award

See http://sigact.acm.org/prizes/godel
for some background information on the Goedel Prize
and a list of past recipients

Rob Schapire and Yoav Freund received the 2003 prize
for their famed AdaBoost paper. For an announcement
see http://sigact.acm.org/prizes/godel/2003.html

Background:

Michael Kearns and Les Valiant first defined
weak and strong learning and posed the open
problem whether weak learning and strong learning
are the same. In short weak learners must have
accuracy only slightly better than 50% and strong
learners must be able to achieve high accuracy

In his 1991 Ph.D. thesis from MIT Rob gave the first
recursive construction for combining many weak learners
to form a strong learner

This was followed by Yoav Freund's Ph.D. thesis in 1993,
where he gave a simple flat scheme
of combining weak learner by a majority vote

After graduating from Santa Cruz, Yoav accepted a job at
AT&T Bell labs in what was one of the strongest machine
learning research groups in the country.
Rob was part of that group as well

They combined ideas and came up with an
``adaptive'' Boosting algorithm
(called AdaBoost - just 10 lines of code)
which received a lot of attention in the Machine Learning
and Statistics communities

Prize winning paper that introduced AdaBoost:
"A Decision Theoretic Generalization of On-Line
Learning and an Application to Boosting,"
Journal of Computer and System Sciences 55 (1997),
pp. 119-139.

Congrats to them !


_____________________________

Manfred K. Warmuth
Prof. in Computer Science
Univ. of Calif. at Santa Cruz

manfred at cse.ucsc.edu
http://www.cse.ucsc.edu/~manfred/