adaboost

AdaBoost (Adaptive Boosting, Freund and Schapire) is a way to build one strong classifier out of many weak ones — classifiers each only slightly better than a coin flip — by training them in sequence and forcing each new one to focus on the mistakes of those before it. The intuition is a study group: the first student takes the test and gets some questions wrong; you then highlight exactly those hard questions for the next student so they specialize in them; you keep adding students, each covering the previous ones' blind spots; and the final answer is a weighted vote where students who proved more accurate get a louder say.

Made precise, AdaBoost maintains a weight on every training example, all equal at the start. In each round it trains a weak learner to minimize the weighted error, computes that learner's overall accuracy, and gives it a vote weight (alpha) that grows as its error shrinks. Then it reweights the data: examples the new learner got wrong have their weights increased, correctly classified ones decreased, so the next round concentrates on the still-hard cases. The strong classifier is the sign of the weighted sum of all weak learners' votes. There is deep theory behind this — AdaBoost provably drives training error down exponentially and can be understood as greedy stagewise minimization of an exponential loss — and it tends to keep improving generalization even after training error hits zero, by enlarging the margin.

In vision, AdaBoost's killer application is feature selection for detection. In the Viola–Jones face detector each weak learner is a decision stump on a single Haar feature — essentially is this one rectangular contrast above some threshold? There are tens of thousands of candidate Haar features, and AdaBoost, by picking the best feature in each round, simultaneously builds the classifier and selects the few hundred features that actually matter, discarding the rest. The same rounds are then sliced into the stages of the attentional cascade. AdaBoost is sensitive to label noise and heavy outliers (it keeps up-weighting examples it cannot get right, which can be mislabeled ones), and in many tabular settings gradient boosting (XGBoost, LightGBM) has supplanted it; but as the engine of classical real-time detection and as the textbook introduction to boosting and ensemble methods, it is foundational.