AdaBoost

Reweight misclassified points after each weak learner and combine the learners by votes αₜ = ½ ln((1 − εₜ)/εₜ).

17 min read1457 wordscore11 viewsupdated 2026-10-07

Definition

AdaBoost (Adaptive Boosting, Freund & Schapire, 1997) trains a sequence of weak classifiers h1,…,hTh_1,\dots,h_T — 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 H(x)=sign⁡(∑tαtht(x))H(x)=\operatorname{sign}\big(\sum_t \alpha_t h_t(x)\big), where a learner with weighted error εt\varepsilon_t gets the vote αt=12ln⁡1−εtεt\alpha_t=\tfrac12\ln\tfrac{1-\varepsilon_t}{\varepsilon_t}.

At a glance

Task
Classification (binary y∈{−1,+1}y\in\{-1,+1\}; SAMME extends it to KK classes)
Input → output
feature vector xx → class sign⁡F(x)\operatorname{sign}F(x), plus a real score F(x)=∑tαtht(x)F(x)=\sum_t\alpha_t h_t(x)
Learns
TT weak learners (each a feature + threshold + polarity for a stump) and one vote αt\alpha_t per learner
Loss it minimizes
the exponential loss ∑ie−yiF(xi)\sum_i e^{-y_iF(x_i)}, greedily, one learner at a time
Training
TT rounds, each one weighted fit of the base learner: about O(T d nlog⁡n)O(T\,d\,n\log n) with stumps; strictly sequential
Prediction
O(T)O(T) stump evaluations
Hyperparameters
n_estimators (T), learning_rate (ν), base-learner depth
Assumes
the base learner is weak — weighted error εt<12\varepsilon_t<\tfrac12 on every reweighting — and that labels are mostly clean

The problem

A decision stump — one question, is xj>tx_j>t? — 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: ε<12\varepsilon<\tfrac12. Usually a stump or a depth-2/3 tree.
Decision stump
a depth-1 tree: h(x)=sh(x)=s if xj>tx_j>t, else −s-s, with feature jj, threshold tt and polarity s∈{±1}s\in\{\pm1\}
Sample weights $w_i$
a probability distribution DtD_t over the training points at round tt; they sum to 1
Weighted error $ arepsilon_t$
the total weight of the points hth_t misclassifies
Vote $alpha_t$
how much hth_t counts in the final sum; large when εt\varepsilon_t is small, 0 when εt=12\varepsilon_t=\tfrac12
Normalizer $Z_t$
the sum of the weights after the multiplicative update; dividing by it keeps Dt+1D_{t+1} a distribution
Score $F(x)$
the un-thresholded vote ∑tαtht(x)\sum_t\alpha_t h_t(x); its sign is the class, its size the confidence
Margin
yiF(xi)y_iF(x_i): positive iff point ii is classified correctly; normalized margin divides by ∑tαt\sum_t\alpha_t so it lies in [−1,1][-1,1]

The math

Labels are coded yi∈{−1,+1}y_i\in\{-1,+1\} and every weak learner outputs ht(x)∈{−1,+1}h_t(x)\in\{-1,+1\}, so yiht(xi)=+1y_ih_t(x_i)=+1 for a hit and −1-1 for a miss. The final classifier is a weighted vote:

H(x)=sign⁡(FT(x)),FT(x)=∑t=1Tαt ht(x)H(x)=\operatorname{sign}\big(F_T(x)\big),\qquad F_T(x)=\sum_{t=1}^{T}\alpha_t\,h_t(x)
hth_t
weak learner fitted in round tt, output ±1\pm1
αt\alpha_t
its vote (learner weight), ≥ 0 for a useful learner
FTF_T
the ensemble score after TT rounds
εt=∑i=1nwi(t) 1 ⁣[ht(xi)≠yi],∑iwi(t)=1\varepsilon_t=\sum_{i=1}^{n} w_i^{(t)}\,\mathbb 1\!\left[h_t(x_i)\ne y_i\right],\qquad \sum_i w_i^{(t)}=1
wi(t)w_i^{(t)}
weight of training point ii at round tt (start: 1/n1/n)
1[⋅]\mathbb 1[\cdot]
1 if the condition holds, else 0
wi(t+1)=wi(t) e−αtyiht(xi)Zt,Zt=∑iwi(t)e−αtyiht(xi)w_i^{(t+1)}=\frac{w_i^{(t)}\,e^{-\alpha_t y_i h_t(x_i)}}{Z_t},\qquad Z_t=\sum_{i} w_i^{(t)}e^{-\alpha_t y_i h_t(x_i)}
e−αtyiht(xi)e^{-\alpha_t y_ih_t(x_i)}
e+αte^{+\alpha_t} for a miss (weight grows), e−αte^{-\alpha_t} for a hit (weight shrinks)
ZtZ_t
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 Ft−1F_{t-1} and want to add one term αh\alpha h:

min⁡α,h ∑i=1ne−yi(Ft−1(xi)+αh(xi))=∑i=1ne−yiFt−1(xi)⏟∝ wi(t) e−αyih(xi)\min_{\alpha,h}\ \sum_{i=1}^n e^{-y_i\left(F_{t-1}(x_i)+\alpha h(x_i)\right)}=\sum_{i=1}^n \underbrace{e^{-y_iF_{t-1}(x_i)}}_{\propto\ w_i^{(t)}}\,e^{-\alpha y_ih(x_i)}
e−yiFt−1(xi)e^{-y_iF_{t-1}(x_i)}
the loss each point already carries — large for points the ensemble gets wrong

The first factor does not depend on α\alpha or hh; normalized, it is the AdaBoost weight wi(t)w_i^{(t)} (unrolling the update gives wi(t)=e−yiFt−1(xi)/(n∏s<tZs)w_i^{(t)}=e^{-y_iF_{t-1}(x_i)}/\big(n\prod_{s<t}Z_s\big)). Split the sum into hits and misses:

∑iwie−αyih(xi)=e−α∑hitswi+eα∑misseswi=e−α(1−ε)+eαε\sum_i w_i e^{-\alpha y_ih(x_i)}=e^{-\alpha}\sum_{\text{hits}}w_i+e^{\alpha}\sum_{\text{misses}}w_i=e^{-\alpha}(1-\varepsilon)+e^{\alpha}\varepsilon

Minimizing it

  1. 1Choose hh. For any fixed α>0\alpha>0 the expression e−α+(eα−e−α)εe^{-\alpha}+(e^{\alpha}-e^{-\alpha})\varepsilon increases with ε\varepsilon, so the best weak learner is the one with the smallest weighted error — exactly what we ask the stump-fitter to do.
  2. 2Choose α\alpha. Differentiate: −e−α(1−ε)+eαε=0  ⇒  e2α=1−εε  ⇒  α=12ln⁡1−εε.-e^{-\alpha}(1-\varepsilon)+e^{\alpha}\varepsilon=0\;\Rightarrow\;e^{2\alpha}=\tfrac{1-\varepsilon}{\varepsilon}\;\Rightarrow\;\alpha=\tfrac12\ln\tfrac{1-\varepsilon}{\varepsilon}. The second derivative is positive, so this is the minimum.
  3. 3The loss shrinks by ZtZ_t. Plugging α\alpha back in: Zt=e−α(1−ε)+eαε=2εt(1−εt)Z_t=e^{-\alpha}(1-\varepsilon)+e^{\alpha}\varepsilon=2\sqrt{\varepsilon_t(1-\varepsilon_t)}, which is <1<1 whenever εt≠12\varepsilon_t\ne\tfrac12.
  4. 4Mistakes end up holding half the weight. After the update the misses weigh εeα/Z=ε(1−ε)/Z=12\varepsilon e^{\alpha}/Z=\sqrt{\varepsilon(1-\varepsilon)}/Z=\tfrac12. On Dt+1D_{t+1} the learner hth_t has error exactly 12\tfrac12 — useless — so round t+1t+1 must pick something else.

Since 1[H(xi)≠yi]≤e−yiF(xi)\mathbb 1[H(x_i)\ne y_i]\le e^{-y_iF(x_i)} (a misclassified point has yiF≤0y_iF\le0, so the exponential is at least 1), the training error is bounded by the exponential loss, which telescopes into the product of the normalizers:

1n∑i1[H(xi)≠yi]  ≤  1n∑ie−yiFT(xi)  =  ∏t=1TZt  =  ∏t=1T1−4γt2  ≤  e−2∑tγt2\frac1n\sum_i\mathbb 1[H(x_i)\ne y_i]\;\le\;\frac1n\sum_i e^{-y_iF_T(x_i)}\;=\;\prod_{t=1}^{T}Z_t\;=\;\prod_{t=1}^T\sqrt{1-4\gamma_t^2}\;\le\;e^{-2\sum_t\gamma_t^2}
γt=12−εt\gamma_t=\tfrac12-\varepsilon_t
the edge of learner tt over a coin flip
∏tZt\prod_t Z_t
exactly the average exponential loss of the ensemble

If every learner has edge at least γ\gamma, training error falls like e−2γ2Te^{-2\gamma^2T} — exponentially in the number of rounds, however weak the learners. With γ=0.1\gamma=0.1 (55%-accurate stumps), T=116T=116 rounds push the bound below 1/n1/n for n=10n=10; once it is below 1/n1/n the training error must be exactly 0.

Each hyperparameter, mathematically

T (n_estimators)
number of terms in FTF_T. The bound ∏Zt\prod Z_t keeps falling with TT; test error usually keeps falling long after training error hits 0, but on noisy labels it eventually rises.
ν (learning_rate)
shrinks every vote: F←F+ναthtF\leftarrow F+\nu\alpha_th_t, and the weight update uses ναt\nu\alpha_t too. Then misses hold less than half the weight, each step is a partial line-search, and you need roughly 1/ν1/\nu times more rounds. Smaller ν regularizes, as in gradient boosting.
Base-learner depth
depth 1 makes FF an additive model ∑jfj(xj)\sum_j f_j(x_j) — no interactions; depth kk allows kk-way interactions. Deeper learners have smaller εt\varepsilon_t (bigger α, faster training-error drop) but each one overfits more.
When ε ≥ ½
αt≤0\alpha_t\le0: the learner is no better than chance on the current weights. Discrete AdaBoost stops (scikit-learn stops early); if εt=0\varepsilon_t=0, αt=∞\alpha_t=\infty and the one perfect learner is returned.

Worked example: three stumps on ten points

Ten points on a 1…101\ldots10 grid with two features, five of each class. No single stump separates them: the −1-1 points sit low (x2≤3x_2\le3) and in a middle band (#2, #3), while the +1+1 point #5 hides among them at (4,4)(4,4).

#x₁x₂y
132−1
2610−1
356−1
4101−1
544+1
613−1
787+1
829+1
995+1
1078+1
Training data. Every point starts with weight wᵢ = 1/10 = 0.1.

Three rounds by hand

  1. 1Round 1 (all wi=0.1w_i=0.1). Among all 36 stumps (2 features × 9 midpoints × 2 polarities) the best is h1h_1: x2>3.5⇒+1x_2>3.5\Rightarrow+1. It misses only #2 and #3 (negatives above the line): ε1=0.2\varepsilon_1=0.2, so α1=12ln⁡0.80.2=12ln⁡4=0.6931\alpha_1=\tfrac12\ln\tfrac{0.8}{0.2}=\tfrac12\ln4=0.6931.
  2. 2Update. Misses × e0.6931=2e^{0.6931}=2 → 0.2; hits × e−0.6931=0.5e^{-0.6931}=0.5 → 0.05. Sum Z1=2(0.2)+8(0.05)=0.8=20.2⋅0.8Z_1=2(0.2)+8(0.05)=0.8=2\sqrt{0.2\cdot0.8}. Normalize: #2, #3 → 0.25 each (together 0.5), the other eight → 0.0625.
  3. 3Round 2. The best stump on the new weights is h2h_2: x1>6.5⇒+1x_1>6.5\Rightarrow+1. It gets #2 and #3 right (they have x1≤6.5x_1\le6.5) and misses #4, #5, #8, each of weight 0.0625: ε2=0.1875\varepsilon_2=0.1875, α2=12ln⁡0.81250.1875=0.7332\alpha_2=\tfrac12\ln\tfrac{0.8125}{0.1875}=0.7332. Note it is not the stump that would win with uniform weights.
  4. 4Update. Misses × e0.7332=2.0817e^{0.7332}=2.0817, hits × 0.48040.4804; Z2=0.7806Z_2=0.7806. New weights: #4, #5, #8 → 16=0.1667\tfrac16=0.1667; #2, #3 → 426=0.1538\tfrac4{26}=0.1538; the other five → 126=0.0385\tfrac1{26}=0.0385.
  5. 5Ensemble after 2 rounds. F2=0.6931h1+0.7332h2F_2=0.6931h_1+0.7332h_2. Where the two stumps disagree, h2h_2 wins by 0.7332−0.6931=0.040.7332-0.6931=0.04, so #4, #5, #8 are now wrong: training errors go up, from 2 to 3. The exponential loss still falls, 0.8→0.8×0.7806=0.62450.8\to0.8\times0.7806=0.6245.
  6. 6Round 3. h3h_3: x1>4.5⇒−1x_1>4.5\Rightarrow-1 (i.e. x1≤4.5⇒+1x_1\le4.5\Rightarrow+1). It gets the three heavy points #4, #5, #8 right and misses #1, #6, #7, #9, #10 — five light points of weight 126\tfrac1{26}: ε3=526=0.1923\varepsilon_3=\tfrac5{26}=0.1923, α3=12ln⁡215=0.7175\alpha_3=\tfrac12\ln\tfrac{21}{5}=0.7175, Z3=0.7882Z_3=0.7882.
  7. 7Final model. F3(x)=0.6931 h1(x)+0.7332 h2(x)+0.7175 h3(x)F_3(x)=0.6931\,h_1(x)+0.7332\,h_2(x)+0.7175\,h_3(x) classifies all 10 points correctly (table below). Exponential loss =Z1Z2Z3=0.4922=Z_1Z_2Z_3=0.4922; the looser bound e−2∑γt2=0.5686e^{-2\sum\gamma_t^2}=0.5686.
  8. 8Predict (6,4)(6,4). h1h_1: x2=4>3.5⇒+1x_2=4>3.5\Rightarrow+1; h2h_2: x1=6≤6.5⇒−1x_1=6\le6.5\Rightarrow-1; h3h_3: x1=6>4.5⇒−1x_1=6>4.5\Rightarrow-1. F3=0.6931−0.7332−0.7175=−0.7576<0F_3=0.6931-0.7332-0.7175=-0.7576<0 → class −1\mathbf{-1}. As a (rough) probability, p(+1)=1/(1+e1.5152)=0.18p(+1)=1/(1+e^{1.5152})=0.18.
#yw (rd 1)w (rd 2)w (rd 3)h₁h₂h₃F₃(x)
1−10.10.06250.0385−1−1+1 ✗−0.7088
2−10.10.250.1538+1 ✗−1−1−0.7576
3−10.10.250.1538+1 ✗−1−1−0.7576
4−10.10.06250.1667−1+1 ✗−1−0.6775
5+10.10.06250.1667+1−1 ✗+1+0.6775
6−10.10.06250.0385−1−1+1 ✗−0.7088
7+10.10.06250.0385+1+1−1 ✗+0.7088
8+10.10.06250.1667+1−1 ✗+1+0.6775
9+10.10.06250.0385+1+1−1 ✗+0.7088
10+10.10.06250.0385+1+1−1 ✗+0.7088
Weights entering each round, the three stumps' outputs and the final score. Highlighted: the points whose weight grows the most at some round. ✗ = that stump misclassifies the point.

Every training point ends with ∣F3∣|F_3| between 0.68 and 0.76, so the smallest normalized margin yiF3(xi)/∑tαty_iF_3(x_i)/\sum_t\alpha_t is 0.6775/2.1438=0.3160.6775/2.1438=0.316. Notice how the hard points (#2, #3 in round 2; #4, #5, #8 in round 3) dictate which stump wins next.

▸ adaboost · stumps on 10 pointsstep 1/25
224466881010x₁x₂12345678910weights wᵢ10.10020.10030.10040.10050.10060.10070.10080.10090.100100.100votes αₜ12345678910
round 0/10train errors –/10exp-loss 1.0000
  1. 1wᵢ ← 1/n
  2. 2for t = 1 … T:
  3. 3 hₜ ← stump minimising Σ wᵢ·[h(xᵢ) ≠ yᵢ]
  4. 4 εₜ ← that error; αₜ ← ½ ln((1−εₜ)/εₜ)
  5. 5 wᵢ ← wᵢ · exp(−αₜ yᵢ hₜ(xᵢ))
  6. 6 wᵢ ← wᵢ / Zₜ (Zₜ = Σ wᵢ)
  7. 7 F ← F + αₜ hₜ
  8. 8predict: sign(F(x))

Start with uniform weights: each of the 10 points has wᵢ = 1/10 = 0.1 (dot area ∝ weight).

fig.AdaBoost on the ten points above (dot area ∝ weight; right: the 10 weights and the votes αₜ). Each of the first three rounds is shown in four beats — pick the stump (mistakes ringed), compute ε and α, multiply the weights (they sum to Zₜ = 0.8, 0.7806, 0.7882), renormalize — then the shaded plane shows sign(Fₜ). Training errors go 2 → 3 → 0 while the exponential loss falls 0.8 → 0.6245 → 0.4922. The query (6, 4) gets F₃ = −0.7576. Rounds 4–10 cycle through the same three stumps and drive the exponential loss down to 0.0913.

The algorithm, step by step

Discrete AdaBoost (binary, y ∈ {−1, +1})

  1. 1Initialize wi=1/nw_i=1/n for every training point; F≡0F\equiv0.
  2. 2Fit the weak learner hth_t to the weighted data (minimize ∑iwi1[ht(xi)≠yi]\sum_iw_i\mathbb 1[h_t(x_i)\ne y_i]; for a tree, use weighted impurity, or resample the data with probabilities wiw_i).
  3. 3Score it: εt\varepsilon_t = weighted error. If εt≥12\varepsilon_t\ge\tfrac12 stop; if εt=0\varepsilon_t=0 return hth_t alone.
  4. 4Vote: αt=ν⋅12ln⁡1−εtεt\alpha_t=\nu\cdot\tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t} (ν = 1 is the original algorithm).
  5. 5Reweight: wi←wie−αtyiht(xi)w_i\leftarrow w_ie^{-\alpha_ty_ih_t(x_i)}, then divide by the sum ZtZ_t.
  6. 6Add αtht\alpha_th_t to FF and repeat for t=1,…,Tt=1,\dots,T.
  7. 7Predict sign⁡F(x)\operatorname{sign}F(x); ∣F(x)∣|F(x)| is the confidence.

Cost

One round (stumps)
O(d nlog⁡n)O(d\,n\log n) to sort and scan each feature — O(d n)O(d\,n) if the sort order is computed once and reused, since only the weights change between rounds
Training
O(T d n)O(T\,d\,n) with pre-sorting; rounds are sequential (each needs the previous weights), so only the inner split search parallelizes
Prediction
O(T)O(T) comparisons per point for stumps; O(T⋅depth)O(T\cdot\text{depth}) for deeper trees
Memory
O(n)O(n) weights during training; the model is TT (feature, threshold, polarity, α) tuples

Variants and tuning

VariantWeak learner outputsVote / updateNotes
Discrete AdaBoosta class ±1α = ½ ln((1−ε)/ε)the original (1997); what this article computes
SAMMEa 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.Rclass probabilitiesh = ½ ln(p/(1−p)) per leafsmoother, usually faster to converge; removed from scikit-learn
Gentle AdaBoostreal valuesweighted least-squares stepNewton steps on the exp loss; more robust to outliers
LogitBoostreal valuesNewton step on log-lossbinomial deviance instead of exp loss — the bridge to gradient boosting
AdaBoost.R2real valuesweighted median of the learnersregression — see AdaBoost Regression
The AdaBoost family. scikit-learn's AdaBoostClassifier implements SAMME (SAMME.R was removed in version 1.6).
Base learnerνT = 10T = 50T = 100T = 400
stump (depth 1)1.00.3450.2250.1770.116
stump (depth 1)0.50.4010.2920.2370.161
stump (depth 1)0.10.4600.4280.3580.274
depth 21.00.3010.1500.1180.082
depth 20.50.3390.1850.1560.106
depth 41.00.2290.1210.1030.091
depth 40.10.3380.2300.1840.123
Test error on make_hastie_10_2 (2,000 train / 10,000 test points; y = +1 iff Σxⱼ² > 9.34). Best single stump 0.459, fully grown tree 0.245. Bold: best per depth.

Practical tuning

Start with
depth-1 or depth-2 trees, learning_rate=1.0, a few hundred rounds; read the curve with staged_score on 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_weight to start from class-balanced weights instead of 1/n

In code

python
1import numpy as np
2
3def 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 values
9 for s in (+1, -1): # s=+1: predict +1 when x_j > t
10 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 best
15
16def stump_predict(X, j, t, s):
17 return np.where(X[:, j] > t, s, -s)
18
19def adaboost(X, y, T=3):
20 n = len(y)
21 w = np.full(n, 1 / n) # D_1: uniform weights
22 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 learner
27 h = stump_predict(X, j, t, s)
28 w = w * np.exp(-alpha * y * h) # up-weight mistakes, down-weight hits
29 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 model
33
34def decision_function(model, X):
35 return sum(a * stump_predict(X, j, t, s) for a, j, t, s in model)
36
37X = 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])))
44
45# 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: 0
49# F(6,4) = -0.7576 -> -1
From scratch with NumPy: exhaustive weighted stumps, the α rule and the multiplicative update. Prints the three rounds of the worked example.
python
1import numpy as np
2from sklearn.ensemble import AdaBoostClassifier
3from sklearn.tree import DecisionTreeClassifier
4
5X = 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])
7
8ada = 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)])
17
18# 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.0
22# decision_function(6,4): [-0.7067] predict: [-1]
23# staged train acc: [0.8, 0.7, 1.0]
scikit-learn on the same data. It finds the same three stumps and errors; its estimator_weights_ are 2α (SAMME) and its decision_function is rescaled, but the signs agree.

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 eαte^{\alpha_t}, hits by e−αte^{-\alpha_t}, then renormalized — after which the misses hold exactly half the weight.
  • ✓The vote αt=12ln⁡1−εtεt\alpha_t=\tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t} is the exact line-search minimizer of the exponential loss; AdaBoost is forward stagewise additive modelling with loss e−yFe^{-yF}.
  • ✓Training error ≤ exponential loss =∏tZt=∏t2εt(1−εt)≤e−2∑γt2=\prod_tZ_t=\prod_t2\sqrt{\varepsilon_t(1-\varepsilon_t)}\le e^{-2\sum\gamma_t^2}: it falls exponentially as long as each learner beats chance.
  • ✓F(x)F(x) estimates half the log-odds; sign⁡F\operatorname{sign}F 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.
← back to ML Algorithms roadmap