Skip to content
Last Dictionary
Plane
Machine LearningHistory & Landmarks

AdaBoost

proper noun/AD-uh-boost/Also: Adaptive Boosting, AdaBoost.M1, discrete AdaBoost, SAMME

In plain wordsOne of the first practical boosting methods: it trains simple models in turn, giving extra weight to examples the earlier models got wrong, then lets all the models vote, weighted by accuracy.

  1. A boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made. algorithm for binary classificationbinary classification, n.: Sorting things into exactly two groups, such as spam versus not spam or sick versus healthy. Most yes-or-no decisions made by AI systems are of this kind. that keeps a weight on every training example, starting uniform. In each round it trains a weak learner — classically a decision stump, a one-split decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer. — on the weighted data, computes the learner's weighted error ε, gives it a vote α = ½ ln((1 − ε)/ε), and increases the weights of misclassified examples so they count more in the next round. The final classifier is the sign of the α-weighted sum of the weak learners' outputs. Training error falls exponentially as long as each learner beats chance, and marginmargin, n.: How far, and on which side, an example lies from a classifier's dividing line. A wide gap between the line and the nearest examples suggests the classifier will handle new data well. theory helps explain why test error often keeps improving after training error reaches zero. AdaBoost is equivalent to stagewise minimization of the exponential loss, which makes it sensitive to label noise and outliers. Multiclass variants include AdaBoost.M1, AdaBoost.M2 and SAMME.

    AdaBoost with 200 stumps picked out the handful of pixel features that mattered.

F(x)=sign⁡(∑t=1Tαtht(x)),αt=12ln⁡1−εtεtF(\mathbf{x}) = \operatorname{sign}\Big(\sum_{t=1}^{T} \alpha_t h_t(\mathbf{x})\Big), \qquad \alpha_t = \frac{1}{2}\ln\frac{1-\varepsilon_t}{\varepsilon_t}

Origin

Introduced by Yoav Freund and Robert Schapire at the EuroCOLT conference in 1995 and in 'A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting' (Journal of Computer and System Sciences, 1997); the name abbreviates 'adaptive boosting'. The paper won the 2003 Gödel Prize. Paul Viola and Michael Jones's real-time face detector (2001) made it famous in computer vision.

Usage note

Largely superseded by gradient boostinggradient boosting, n.: A method that builds a strong predictor by adding small decision trees one at a time, each trained to correct the errors that remain after all the trees before it. for general use, but still a standard teaching example and a component of classic face detectionface detection, n.: Finding where the faces are in a photo or video, without working out whose faces they are: the step that lets a camera focus on people or blur them out. pipelines.

Related

See also
  • boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made.
  • gradient boostinggradient boosting, n.: A method that builds a strong predictor by adding small decision trees one at a time, each trained to correct the errors that remain after all the trees before it.
  • decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer.
  • ensemble learningensemble learning, n.: Combining the predictions of several models — by voting or averaging — so their individual mistakes partly cancel out, giving more accurate and stable results than any one model.
  • marginmargin, n.: How far, and on which side, an example lies from a classifier's dividing line. A wide gap between the line and the nearest examples suggests the classifier will handle new data well.
  • face detectionface detection, n.: Finding where the faces are in a photo or video, without working out whose faces they are: the step that lets a camera focus on people or blur them out.

Sources

  1. Freund, Y. & Schapire, R. E. (1997). A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), 119–139.

Mentioned in

boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made., face detectionface detection, n.: Finding where the faces are in a photo or video, without working out whose faces they are: the step that lets a camera focus on people or blur them out., marginmargin, n.: How far, and on which side, an example lies from a classifier's dividing line. A wide gap between the line and the nearest examples suggests the classifier will handle new data well.