AdaBoost
Era 3 · From the expert boom to the statistical turn (1980–2011) › Statistical learning and probabilistic models
- Lineage
- Data and learning
- Kind
- Publication
Who
AT&T Bell Labs
What happened
In 1995, at the EuroCOLT conference in Barcelona, Yoav Freund and Robert Schapire of AT&T's laboratories present the AdaBoost algorithm, published in full in 1997 in the Journal of Computer and System Sciences.
Why it mattered
It combines many weak classifiers, each only slightly better than chance, into a highly accurate one. It is the most widely used boosting method and the basis of the Viola-Jones face detector.
The full story
Within the PAC learning framework, Michael Kearns and Leslie Valiant had asked a question: if you have a method that is right only a little more often than a coin toss, can it be turned into one that is right almost all the time? Schapire proved in 1990 that it can, and Freund later gave a more efficient procedure, but both methods were hard to use in practice.
AdaBoost, short for adaptive boosting, solved this with a simple idea. Train a weak classifier, such as a one-question decision tree, and see which examples it gets wrong. Give those examples more weight and train the next classifier, which then focuses on the hard cases. Repeat many times, and at the end combine all the classifiers in a vote weighted by how well each one did.
The algorithm did not need to know in advance how weak each classifier was, hence "adaptive," and it worked very well on real data. Freund and Schapire received the 2003 Gödel Prize for the 1997 paper.
In 2001 Paul Viola and Michael Jones used it to pick a few simple features out of tens of thousands, and built the first face detector able to run in real time.
Builds on
Valiant's PAC learning (November 1984)
Documented direct influence
Boosting answers a question posed within the PAC framework: whether a learner slightly better than chance can be turned into a highly accurate one
Leads to
SIFT and the Viola–Jones face detector (September 1999)
Documented direct influence
The Viola-Jones detector uses AdaBoost to choose its features, as the paper's title says
Sources
Original source
- A decision-theoretic generalization of on-line learning and an application to boosting. EuroCOLT 1995, Lecture Notes in Computer Science 904, pp. 23-37 (opens in a new tab). Yoav Freund and Robert Schapire, 1995
- A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), pp. 119-139 (opens in a new tab). Yoav Freund and Robert Schapire, 1997
Further reading
How to cite
“AdaBoost.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/adaboost
This entry was last reviewed on November 13, 2026.