AdaBoost

Freund and Schapire showed how to combine classifiers barely better than chance into one strong classifier, raising the weight of mistakes at each step.

Why it matters

The theoretical question of whether a weak learner can be made strong got a practical answer, which the authors at once tried on digit recognition.

Each successive classifier trains on a reweighted sample where examples the earlier ones got wrong count for more. Training error falls exponentially with the number of steps. In the authors' first experiments the method seemed not to overfit: test error kept dropping after hundreds of rounds, and an explanation through margins came later. In 2001 Viola and Jones built a face detector on AdaBoost that ran at 15 frames per second on a 700 MHz Pentium III.

Event record

Event date

March 1995

Timeline date

Event date

Verification

Sources gathered automatically · September 17, 2026

Lines

Learning theory

ID

evt-0174

Presented at the second European Conference on Computational Learning Theory in March 1995; the journal version appeared in 1997.

Sources

primary A decision-theoretic generalization of on-line learning and an application to boosting
EuroCOLT 1995 · Published March 1995
primary Rapid Object Detection using a Boosted Cascade of Simple Features
CVPR 2001 · Published December 2001
archive A decision-theoretic generalization of on-line learning and an application to boosting (Yoav Freund, Robert E. Schapire), manuscript of 19 December 1996
AT&T Labs (author's archive, Robert Schapire) · Published December 1996

Related events

Earlier

Related Induction of Decision Trees 1986
In practice the method was most often applied to decision trees.
Builds on A Theory of the Learnable 1984
It answers the question posed in learnability theory: whether a weak learner can be made strong.
- A decision-theoretic generalization of on-line learning and an application to boosting · EuroCOLT 1995

Later

Related Conditional random fields 2001links to this record
Section 6 of the paper: a CRF can be trained with the same exponential loss that AdaBoost uses.
- Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data · University of Pennsylvania, ScholarlyCommons (Departmental Papers, CIS)
Contrasts Random forests 2001links to this record
The abstract: random feature selection at each node gives error rates that compare favourably with AdaBoost but are more robust to noise.
- Random Forests · Machine Learning (Kluwer, now Springer)
Builds on Gradient boosting 2001links to this record
The abstract discusses directly how the approach connects to the boosting of Freund and Schapire: AdaBoost becomes a special case of gradient descent in function space.
- Greedy function approximation: A gradient boosting machine. · The Annals of Statistics, Institute of Mathematical Statistics (Project Euclid)
Builds on Viola-Jones face detection 2001links to this record
The cascade of classifiers is trained by boosting itself.
- Rapid Object Detection using a Boosted Cascade of Simple Features · CVPR 2001