Definition
AdaBoost (Adaptive Boosting, Freund & Schapire, 1997) trains a sequence of weak classifiers — usually one-split decision stumps — each on a reweighted copy of the training set in which the points the previous learners got wrong count more, and predicts with the weighted vote , where a learner with weighted error gets the vote .
At a glance
- Task
- Classification (binary ; SAMME extends it to classes)
- Input → output
- feature vector → class , plus a real score
- Learns
- weak learners (each a feature + threshold + polarity for a stump) and one vote per learner
- Loss it minimizes
- the exponential loss , greedily, one learner at a time
- Training
- rounds, each one weighted fit of the base learner: about with stumps; strictly sequential
- Prediction
- stump evaluations
- Hyperparameters
n_estimators(T),learning_rate(ν), base-learner depth- Assumes
- the base learner is weak — weighted error on every reweighting — and that labels are mostly clean
The problem
A decision stump — one question, is ? — is about the simplest classifier there is. It is fast, never overfits much, and is almost always weak: on the 10-feature Hastie benchmark used later in this article, the best single stump has 45.9% test error, barely better than a coin. A deeper tree does better (24.5% fully grown) but is high-variance.
Averaging many trees trained on bootstrap samples (see Random Forests) fixes variance, but averaging copies of a biased stump just gives a biased stump. In 1988 Kearns and Valiant asked a sharper question: if you can always find a rule that is slightly better than chance, can you combine such rules into one that is arbitrarily accurate? AdaBoost is the constructive yes: it forces each new weak learner to work on the examples the current ensemble still gets wrong, and it does so without any tuning of how weak the learners are — hence adaptive.
The idea
Keep a weight on every training point. Fit a stump that minimizes the weighted error. Then turn up the weight of the points it got wrong and turn down the rest, so that — exactly — the stump you just fitted would be no better than a coin flip on the new weights. The next stump is therefore forced to find a different pattern. Repeat, and let every stump vote, with confident (low-error) stumps getting louder votes.
Two things adapt: the data weights (where to look next) and the votes (how much to trust each learner). Both come from the same number, the learner's weighted error.
Vocabulary
- Weak learner
- a classifier guaranteed only to beat chance on weighted data: . Usually a stump or a depth-2/3 tree.
- Decision stump
- a depth-1 tree: if , else , with feature , threshold and polarity
- Sample weights $w_i$
- a probability distribution over the training points at round ; they sum to 1
- Weighted error $arepsilon_t$
- the total weight of the points misclassifies
- Vote $alpha_t$
- how much counts in the final sum; large when is small, 0 when
- Normalizer $Z_t$
- the sum of the weights after the multiplicative update; dividing by it keeps a distribution
- Score $F(x)$
- the un-thresholded vote ; its sign is the class, its size the confidence
- Margin
- : positive iff point is classified correctly; normalized margin divides by so it lies in
The math
Labels are coded and every weak learner outputs , so for a hit and for a miss. The final classifier is a weighted vote:
- weak learner fitted in round , output
- its vote (learner weight), ≥ 0 for a useful learner
- the ensemble score after rounds
- weight of training point at round (start: )
- 1 if the condition holds, else 0
- for a miss (weight grows), for a hit (weight shrinks)
- normalizer so the new weights sum to 1
Where α comes from: stagewise exponential loss
AdaBoost was found by intuition, but it is exactly forward stagewise additive modelling with the exponential loss (Friedman, Hastie & Tibshirani, 2000). Suppose we already have and want to add one term :
- the loss each point already carries — large for points the ensemble gets wrong
The first factor does not depend on or ; normalized, it is the AdaBoost weight (unrolling the update gives ). Split the sum into hits and misses:
Minimizing it
- 1Choose . For any fixed the expression increases with , so the best weak learner is the one with the smallest weighted error — exactly what we ask the stump-fitter to do.
- 2Choose . Differentiate: The second derivative is positive, so this is the minimum.
- 3The loss shrinks by . Plugging back in: , which is whenever .
- 4Mistakes end up holding half the weight. After the update the misses weigh . On the learner has error exactly — useless — so round must pick something else.
Since (a misclassified point has , so the exponential is at least 1), the training error is bounded by the exponential loss, which telescopes into the product of the normalizers:
- the edge of learner over a coin flip
- exactly the average exponential loss of the ensemble
If every learner has edge at least , training error falls like — exponentially in the number of rounds, however weak the learners. With (55%-accurate stumps), rounds push the bound below for ; once it is below the training error must be exactly 0.
Each hyperparameter, mathematically
- T (n_estimators)
- number of terms in . The bound keeps falling with ; test error usually keeps falling long after training error hits 0, but on noisy labels it eventually rises.
- ν (learning_rate)
- shrinks every vote: , and the weight update uses too. Then misses hold less than half the weight, each step is a partial line-search, and you need roughly times more rounds. Smaller ν regularizes, as in gradient boosting.
- Base-learner depth
- depth 1 makes an additive model — no interactions; depth allows -way interactions. Deeper learners have smaller (bigger α, faster training-error drop) but each one overfits more.
- When ε ≥ ½
- : the learner is no better than chance on the current weights. Discrete AdaBoost stops (scikit-learn stops early); if , and the one perfect learner is returned.
Worked example: three stumps on ten points
Ten points on a grid with two features, five of each class. No single stump separates them: the points sit low () and in a middle band (#2, #3), while the point #5 hides among them at .
| # | x₁ | x₂ | y |
|---|---|---|---|
| 1 | 3 | 2 | −1 |
| 2 | 6 | 10 | −1 |
| 3 | 5 | 6 | −1 |
| 4 | 10 | 1 | −1 |
| 5 | 4 | 4 | +1 |
| 6 | 1 | 3 | −1 |
| 7 | 8 | 7 | +1 |
| 8 | 2 | 9 | +1 |
| 9 | 9 | 5 | +1 |
| 10 | 7 | 8 | +1 |
Three rounds by hand
- 1Round 1 (all ). Among all 36 stumps (2 features × 9 midpoints × 2 polarities) the best is : . It misses only #2 and #3 (negatives above the line): , so .
- 2Update. Misses × → 0.2; hits × → 0.05. Sum . Normalize: #2, #3 → 0.25 each (together 0.5), the other eight → 0.0625.
- 3Round 2. The best stump on the new weights is : . It gets #2 and #3 right (they have ) and misses #4, #5, #8, each of weight 0.0625: , . Note it is not the stump that would win with uniform weights.
- 4Update. Misses × , hits × ; . New weights: #4, #5, #8 → ; #2, #3 → ; the other five → .
- 5Ensemble after 2 rounds. . Where the two stumps disagree, wins by , so #4, #5, #8 are now wrong: training errors go up, from 2 to 3. The exponential loss still falls, .
- 6Round 3. : (i.e. ). It gets the three heavy points #4, #5, #8 right and misses #1, #6, #7, #9, #10 — five light points of weight : , , .
- 7Final model. classifies all 10 points correctly (table below). Exponential loss ; the looser bound .
- 8Predict . : ; : ; : . → class . As a (rough) probability, .
| # | y | w (rd 1) | w (rd 2) | w (rd 3) | h₁ | h₂ | h₃ | F₃(x) |
|---|---|---|---|---|---|---|---|---|
| 1 | −1 | 0.1 | 0.0625 | 0.0385 | −1 | −1 | +1 ✗ | −0.7088 |
| 2 | −1 | 0.1 | 0.25 | 0.1538 | +1 ✗ | −1 | −1 | −0.7576 |
| 3 | −1 | 0.1 | 0.25 | 0.1538 | +1 ✗ | −1 | −1 | −0.7576 |
| 4 | −1 | 0.1 | 0.0625 | 0.1667 | −1 | +1 ✗ | −1 | −0.6775 |
| 5 | +1 | 0.1 | 0.0625 | 0.1667 | +1 | −1 ✗ | +1 | +0.6775 |
| 6 | −1 | 0.1 | 0.0625 | 0.0385 | −1 | −1 | +1 ✗ | −0.7088 |
| 7 | +1 | 0.1 | 0.0625 | 0.0385 | +1 | +1 | −1 ✗ | +0.7088 |
| 8 | +1 | 0.1 | 0.0625 | 0.1667 | +1 | −1 ✗ | +1 | +0.6775 |
| 9 | +1 | 0.1 | 0.0625 | 0.0385 | +1 | +1 | −1 ✗ | +0.7088 |
| 10 | +1 | 0.1 | 0.0625 | 0.0385 | +1 | +1 | −1 ✗ | +0.7088 |
Every training point ends with between 0.68 and 0.76, so the smallest normalized margin is . Notice how the hard points (#2, #3 in round 2; #4, #5, #8 in round 3) dictate which stump wins next.
- 1wᵢ ← 1/n
- 2for t = 1 … T:
- 3 hₜ ← stump minimising Σ wᵢ·[h(xᵢ) ≠ yᵢ]
- 4 εₜ ← that error; αₜ ← ½ ln((1−εₜ)/εₜ)
- 5 wᵢ ← wᵢ · exp(−αₜ yᵢ hₜ(xᵢ))
- 6 wᵢ ← wᵢ / Zₜ (Zₜ = Σ wᵢ)
- 7 F ← F + αₜ hₜ
- 8predict: sign(F(x))
Start with uniform weights: each of the 10 points has wᵢ = 1/10 = 0.1 (dot area ∝ weight).
The algorithm, step by step
Discrete AdaBoost (binary, y ∈ {−1, +1})
- 1Initialize for every training point; .
- 2Fit the weak learner to the weighted data (minimize ; for a tree, use weighted impurity, or resample the data with probabilities ).
- 3Score it: = weighted error. If stop; if return alone.
- 4Vote: (ν = 1 is the original algorithm).
- 5Reweight: , then divide by the sum .
- 6Add to and repeat for .
- 7Predict ; is the confidence.
Cost
- One round (stumps)
- to sort and scan each feature — if the sort order is computed once and reused, since only the weights change between rounds
- Training
- with pre-sorting; rounds are sequential (each needs the previous weights), so only the inner split search parallelizes
- Prediction
- comparisons per point for stumps; for deeper trees
- Memory
- weights during training; the model is (feature, threshold, polarity, α) tuples
Variants and tuning
| Variant | Weak learner outputs | Vote / update | Notes |
|---|---|---|---|
| Discrete AdaBoost | a class ±1 | α = ½ ln((1−ε)/ε) | the original (1997); what this article computes |
| SAMME | a class out of K | α = ln((1−ε)/ε) + ln(K−1) | multi-class; needs only ε < 1 − 1/K. For K = 2 it is 2× the discrete α — same predictions |
| Real AdaBoost / SAMME.R | class probabilities | h = ½ ln(p/(1−p)) per leaf | smoother, usually faster to converge; removed from scikit-learn |
| Gentle AdaBoost | real values | weighted least-squares step | Newton steps on the exp loss; more robust to outliers |
| LogitBoost | real values | Newton step on log-loss | binomial deviance instead of exp loss — the bridge to gradient boosting |
| AdaBoost.R2 | real values | weighted median of the learners | regression — see AdaBoost Regression |
| Base learner | ν | T = 10 | T = 50 | T = 100 | T = 400 |
|---|---|---|---|---|---|
| stump (depth 1) | 1.0 | 0.345 | 0.225 | 0.177 | 0.116 |
| stump (depth 1) | 0.5 | 0.401 | 0.292 | 0.237 | 0.161 |
| stump (depth 1) | 0.1 | 0.460 | 0.428 | 0.358 | 0.274 |
| depth 2 | 1.0 | 0.301 | 0.150 | 0.118 | 0.082 |
| depth 2 | 0.5 | 0.339 | 0.185 | 0.156 | 0.106 |
| depth 4 | 1.0 | 0.229 | 0.121 | 0.103 | 0.091 |
| depth 4 | 0.1 | 0.338 | 0.230 | 0.184 | 0.123 |
Practical tuning
- Start with
- depth-1 or depth-2 trees,
learning_rate=1.0, a few hundred rounds; read the curve withstaged_scoreon a validation set rather than refitting for every T - Depth
- the strongest lever. Here depth 2 beats stumps (0.082 vs 0.116 at T = 400): the target Σxⱼ² is additive, so stumps can represent it in principle, but one stump captures only one side of a parabola, while a depth-2 tree can carve both tails of a feature at once. Depth 4 fits the training data perfectly and gains less (0.091)
- ν and T together
- lowering ν needs proportionally more rounds: at T = 400, ν = 0.1 is still far behind (0.274). Shrinkage pays off only when you can afford the extra rounds
- Stopping
- on clean data AdaBoost overfits slowly; on noisy labels pick T by validation error, or switch to a log-loss booster
- Imbalance
- pass
sample_weightto start from class-balanced weights instead of 1/n
In code
1import numpy as np23def fit_stump(X, y, w):4 """Best decision stump under weights w: returns (error, feature, threshold, polarity)."""5 best = (np.inf, None, None, None)6 for j in range(X.shape[1]):7 v = np.unique(X[:, j])8 for t in (v[:-1] + v[1:]) / 2: # midpoints between sorted values9 for s in (+1, -1): # s=+1: predict +1 when x_j > t10 pred = np.where(X[:, j] > t, s, -s)11 err = w[pred != y].sum()12 if err < best[0]:13 best = (err, j, t, s)14 return best1516def stump_predict(X, j, t, s):17 return np.where(X[:, j] > t, s, -s)1819def adaboost(X, y, T=3):20 n = len(y)21 w = np.full(n, 1 / n) # D_1: uniform weights22 model = []23 for _ in range(T):24 err, j, t, s = fit_stump(X, y, w)25 err = np.clip(err, 1e-12, 1 - 1e-12)26 alpha = 0.5 * np.log((1 - err) / err) # vote of this learner27 h = stump_predict(X, j, t, s)28 w = w * np.exp(-alpha * y * h) # up-weight mistakes, down-weight hits29 w = w / w.sum() # normalize (divide by Z_t)30 model.append((alpha, j, t, s))31 print(f"x{j+1} > {t:.1f} -> {s:+d} eps={err:.4f} alpha={alpha:.4f} w={np.round(w, 4)}")32 return model3334def decision_function(model, X):35 return sum(a * stump_predict(X, j, t, s) for a, j, t, s in model)3637X = np.array([[3, 2], [6, 10], [5, 6], [10, 1], [4, 4], [1, 3], [8, 7], [2, 9], [9, 5], [7, 8]], float)38y = np.array([-1, -1, -1, -1, 1, -1, 1, 1, 1, 1])39model = adaboost(X, y, T=3)40F = decision_function(model, X)41print("F(x_i) =", np.round(F, 4), " training errors:", int((np.sign(F) != y).sum()))42q = np.array([[6, 4]], float)43print("F(6,4) =", round(float(decision_function(model, q)[0]), 4), "->", int(np.sign(decision_function(model, q)[0])))4445# x2 > 3.5 -> +1 eps=0.2000 alpha=0.6931 w=[0.0625 0.25 0.25 0.0625 ...]46# x1 > 6.5 -> +1 eps=0.1875 alpha=0.7332 w=[0.0385 0.1538 0.1538 0.1667 0.1667 ...]47# x1 > 4.5 -> -1 eps=0.1923 alpha=0.7175 w=[0.1 0.0952 0.0952 0.1032 0.1032 ...]48# F(x_i) = [-0.7088 -0.7576 -0.7576 -0.6775 0.6775 -0.7088 0.7088 0.6775 0.7088 0.7088] training errors: 049# F(6,4) = -0.7576 -> -11import numpy as np2from sklearn.ensemble import AdaBoostClassifier3from sklearn.tree import DecisionTreeClassifier45X = np.array([[3, 2], [6, 10], [5, 6], [10, 1], [4, 4], [1, 3], [8, 7], [2, 9], [9, 5], [7, 8]], float)6y = np.array([-1, -1, -1, -1, 1, -1, 1, 1, 1, 1])78ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=3,9 learning_rate=1.0, random_state=0).fit(X, y)10for est, err, wt in zip(ada.estimators_, ada.estimator_errors_, ada.estimator_weights_):11 t = est.tree_12 print(f"split x{t.feature[0] + 1} <= {t.threshold[0]:.1f} error={err:.4f} weight={wt:.4f} (= 2*alpha)")13print("train accuracy:", ada.score(X, y))14q = np.array([[6, 4]])15print("decision_function(6,4):", ada.decision_function(q).round(4), "predict:", ada.predict(q))16print("staged train acc:", [round(s, 2) for s in ada.staged_score(X, y)])1718# split x2 <= 3.5 error=0.2000 weight=1.3863 (= 2*alpha)19# split x1 <= 6.5 error=0.1875 weight=1.4663 (= 2*alpha)20# split x1 <= 4.5 error=0.1923 weight=1.4351 (= 2*alpha)21# train accuracy: 1.022# decision_function(6,4): [-0.7067] predict: [-1]23# staged train acc: [0.8, 0.7, 1.0]Use when
- +Your base learner is weak but cheap (stumps, rules, Haar-like features) and you want a strong, compact classifier from it.
- +Labels are clean and you want a strong default with almost no tuning: one main knob (T), no scaling of features.
- +You need fast prediction and a model that is easy to inspect: a short list of (feature, threshold, vote) triples.
- +You want a cascade or feature selection — each round picks one feature, so the order of rounds ranks features.
Avoid when
- −Labels are noisy or there are outliers: the exponential loss puts exponentially growing weight on points it cannot fit.
- −You need calibrated probabilities: use gradient boosting with log-loss, or calibrate.
- −Data are large and tabular and accuracy is everything: gradient-boosting libraries (XGBoost, LightGBM, CatBoost) are usually more accurate and far faster.
- −You need parallel training: rounds are inherently sequential, unlike a random forest.
Where it's used
Real-time face detection
Viola–Jones (2001) boosts thousands of one-feature Haar-like stumps and chains the boosted classifiers into a cascade — the classic camera face detector.
Feature selection
Each boosting round with stumps chooses one feature; the first rounds give a ranked, small set of informative features (used in vision and genomics).
Text and spam filtering
BoosTexter (Schapire & Singer) boosts word-presence stumps for multi-class text categorization.
Tabular baselines
A boosted-stump model is a strong, interpretable additive baseline for credit, churn and medical-risk tables before reaching for heavier gradient boosting.
Check yourself
A stump has weighted error ε = 0.25. What vote α does AdaBoost give it, and how much of the total weight do its mistakes hold after the update?
Check yourself
On some reweighting the best stump has ε = 0.6. What does discrete AdaBoost's formula give, and what does that mean?
Check yourself
In the worked example, why did round 2 choose x₁ > 6.5 → +1 rather than another stump?
Check yourself
Every weak learner has edge γ = ½ − ε ≥ 0.1. Which statement about the training error after T rounds is guaranteed?
Remember
- ✓AdaBoost fits weak learners in sequence on reweighted data: misses are multiplied by , hits by , then renormalized — after which the misses hold exactly half the weight.
- ✓The vote is the exact line-search minimizer of the exponential loss; AdaBoost is forward stagewise additive modelling with loss .
- ✓Training error ≤ exponential loss : it falls exponentially as long as each learner beats chance.
- ✓ estimates half the log-odds; is the class. Margins keep growing after training error reaches 0, which explains the slow overfitting on clean data.
- ✓Tune base-learner depth (1–3), number of rounds and learning rate on validation data; beware label noise, where the exponential loss over-weights mislabelled points.