# AdaBoost

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

Source: https://www.mlfoundry.in/learn/adaboost  
Section: ML Algorithms › Supervised · Classification  
Level: core · 17 min read · updated 2026-10-07

**AdaBoost:** (*Adaptive Boosting*, Freund & Schapire, 1997) trains a sequence of weak classifiers $h_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)=\operatorname{sign}\big(\sum_t \alpha_t h_t(x)\big)$, where a learner with weighted error $\varepsilon_t$ gets the vote $\alpha_t=\tfrac12\ln\tfrac{1-\varepsilon_t}{\varepsilon_t}$.

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

## The problem

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

## The math

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

$$
H(x)=\operatorname{sign}\big(F_T(x)\big),\qquad F_T(x)=\sum_{t=1}^{T}\alpha_t\,h_t(x)
$$

- $h_t$: weak learner fitted in round $t$, output $\pm1$
- $\alpha_t$: its vote (learner weight), ≥ 0 for a useful learner
- $F_T$: the ensemble score after $T$ rounds

$$
\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
$$

- $w_i^{(t)}$: weight of training point $i$ at round $t$ (start: $1/n$)
- $\mathbb 1[\cdot]$: 1 if the condition holds, else 0

$$
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^{-\alpha_t y_ih_t(x_i)}$: $e^{+\alpha_t}$ for a miss (weight grows), $e^{-\alpha_t}$ for a hit (weight shrinks)
- $Z_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 $F_{t-1}$ and want to add one term $\alpha h$:

$$
\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^{-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 $h$; normalized, it **is** the AdaBoost weight $w_i^{(t)}$ (unrolling the update gives $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:

$$
\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. **Choose $h$.** For any fixed $\alpha>0$ the expression $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. **Choose $\alpha$.** Differentiate: $-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. **The loss shrinks by $Z_t$.** Plugging $\alpha$ back in: $Z_t=e^{-\alpha}(1-\varepsilon)+e^{\alpha}\varepsilon=2\sqrt{\varepsilon_t(1-\varepsilon_t)}$, which is $<1$ whenever $\varepsilon_t\ne\tfrac12$.
4. **Mistakes end up holding half the weight.** After the update the misses weigh $\varepsilon e^{\alpha}/Z=\sqrt{\varepsilon(1-\varepsilon)}/Z=\tfrac12$. On $D_{t+1}$ the learner $h_t$ has error exactly $\tfrac12$ — useless — so round $t+1$ must pick something else.

Since $\mathbb 1[H(x_i)\ne y_i]\le e^{-y_iF(x_i)}$ (a misclassified point has $y_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:

$$
\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}
$$

- $\gamma_t=\tfrac12-\varepsilon_t$: the *edge* of learner $t$ over a coin flip
- $\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\gamma^2T}$ — **exponentially in the number of rounds**, however weak the learners. With $\gamma=0.1$ (55%-accurate stumps), $T=116$ rounds push the bound below $1/n$ for $n=10$; once it is below $1/n$ the training error must be exactly 0.

> **What the score F estimates:** The population minimizer of $\mathbb E\,e^{-yF(x)}$ is $F^*(x)=\tfrac12\ln\frac{P(y=1\mid x)}{P(y=-1\mid x)}$ — **half the log-odds**. So AdaBoost's score can be turned into a probability with $p(x)=1/(1+e^{-2F(x)})$. In practice these probabilities are poorly calibrated (the exponential loss rewards pushing $|F|$ large), so calibrate them on held-out data before thresholding. If you need probabilities first, boosting the log-loss instead — **Gradient Boosting** — is the better tool.

**Each hyperparameter, mathematically**

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

## Worked example: three stumps on ten points

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

Training data. Every point starts with weight wᵢ = 1/10 = 0.1.

| # | 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**

1. **Round 1** (all $w_i=0.1$). Among all 36 stumps (2 features × 9 midpoints × 2 polarities) the best is $h_1$: *$x_2>3.5\Rightarrow+1$*. It misses only #2 and #3 (negatives above the line): $\varepsilon_1=0.2$, so $\alpha_1=\tfrac12\ln\tfrac{0.8}{0.2}=\tfrac12\ln4=0.6931$.
2. **Update.** Misses × $e^{0.6931}=2$ → 0.2; hits × $e^{-0.6931}=0.5$ → 0.05. Sum $Z_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. **Round 2.** The best stump on the new weights is $h_2$: *$x_1>6.5\Rightarrow+1$*. It gets #2 and #3 right (they have $x_1\le6.5$) and misses #4, #5, #8, each of weight 0.0625: $\varepsilon_2=0.1875$, $\alpha_2=\tfrac12\ln\tfrac{0.8125}{0.1875}=0.7332$. Note it is *not* the stump that would win with uniform weights.
4. **Update.** Misses × $e^{0.7332}=2.0817$, hits × $0.4804$; $Z_2=0.7806$. New weights: #4, #5, #8 → $\tfrac16=0.1667$; #2, #3 → $\tfrac4{26}=0.1538$; the other five → $\tfrac1{26}=0.0385$.
5. **Ensemble after 2 rounds.** $F_2=0.6931h_1+0.7332h_2$. Where the two stumps disagree, $h_2$ wins by $0.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\to0.8\times0.7806=0.6245$.
6. **Round 3.** $h_3$: *$x_1>4.5\Rightarrow-1$* (i.e. $x_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 $\tfrac1{26}$: $\varepsilon_3=\tfrac5{26}=0.1923$, $\alpha_3=\tfrac12\ln\tfrac{21}{5}=0.7175$, $Z_3=0.7882$.
7. **Final model.** $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 $=Z_1Z_2Z_3=0.4922$; the looser bound $e^{-2\sum\gamma_t^2}=0.5686$.
8. **Predict $(6,4)$.** $h_1$: $x_2=4>3.5\Rightarrow+1$; $h_2$: $x_1=6\le6.5\Rightarrow-1$; $h_3$: $x_1=6>4.5\Rightarrow-1$. $F_3=0.6931-0.7332-0.7175=-0.7576<0$ → class $\mathbf{-1}$. As a (rough) probability, $p(+1)=1/(1+e^{1.5152})=0.18$.

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.

| # | 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 $|F_3|$ between 0.68 and 0.76, so the smallest normalized margin $y_iF_3(x_i)/\sum_t\alpha_t$ is $0.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.

> Figure: 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. **Initialize** $w_i=1/n$ for every training point; $F\equiv0$.
2. **Fit** the weak learner $h_t$ to the weighted data (minimize $\sum_iw_i\mathbb 1[h_t(x_i)\ne y_i]$; for a tree, use weighted impurity, or resample the data with probabilities $w_i$).
3. **Score** it: $\varepsilon_t$ = weighted error. If $\varepsilon_t\ge\tfrac12$ stop; if $\varepsilon_t=0$ return $h_t$ alone.
4. **Vote**: $\alpha_t=\nu\cdot\tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}$ (ν = 1 is the original algorithm).
5. **Reweight**: $w_i\leftarrow w_ie^{-\alpha_ty_ih_t(x_i)}$, then divide by the sum $Z_t$.
6. **Add** $\alpha_th_t$ to $F$ and repeat for $t=1,\dots,T$.
7. **Predict** $\operatorname{sign}F(x)$; $|F(x)|$ is the confidence.

**Cost**

- **One round (stumps):** $O(d\,n\log n)$ to sort and scan each feature — $O(d\,n)$ if the sort order is computed once and reused, since only the weights change between rounds
- **Training:** $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)$ comparisons per point for stumps; $O(T\cdot\text{depth})$ for deeper trees
- **Memory:** $O(n)$ weights during training; the model is $T$ (feature, threshold, polarity, α) tuples

## Variants and tuning

The AdaBoost family. scikit-learn's AdaBoostClassifier implements SAMME (SAMME.R was removed in version 1.6).

| 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** |

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.

| 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 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
import numpy as np

def fit_stump(X, y, w):
    """Best decision stump under weights w: returns (error, feature, threshold, polarity)."""
    best = (np.inf, None, None, None)
    for j in range(X.shape[1]):
        v = np.unique(X[:, j])
        for t in (v[:-1] + v[1:]) / 2:                  # midpoints between sorted values
            for s in (+1, -1):                           # s=+1: predict +1 when x_j > t
                pred = np.where(X[:, j] > t, s, -s)
                err = w[pred != y].sum()
                if err < best[0]:
                    best = (err, j, t, s)
    return best

def stump_predict(X, j, t, s):
    return np.where(X[:, j] > t, s, -s)

def adaboost(X, y, T=3):
    n = len(y)
    w = np.full(n, 1 / n)                                # D_1: uniform weights
    model = []
    for _ in range(T):
        err, j, t, s = fit_stump(X, y, w)
        err = np.clip(err, 1e-12, 1 - 1e-12)
        alpha = 0.5 * np.log((1 - err) / err)            # vote of this learner
        h = stump_predict(X, j, t, s)
        w = w * np.exp(-alpha * y * h)                   # up-weight mistakes, down-weight hits
        w = w / w.sum()                                  # normalize (divide by Z_t)
        model.append((alpha, j, t, s))
        print(f"x{j+1} > {t:.1f} -> {s:+d}  eps={err:.4f}  alpha={alpha:.4f}  w={np.round(w, 4)}")
    return model

def decision_function(model, X):
    return sum(a * stump_predict(X, j, t, s) for a, j, t, s in model)

X = np.array([[3, 2], [6, 10], [5, 6], [10, 1], [4, 4], [1, 3], [8, 7], [2, 9], [9, 5], [7, 8]], float)
y = np.array([-1, -1, -1, -1, 1, -1, 1, 1, 1, 1])
model = adaboost(X, y, T=3)
F = decision_function(model, X)
print("F(x_i) =", np.round(F, 4), " training errors:", int((np.sign(F) != y).sum()))
q = np.array([[6, 4]], float)
print("F(6,4) =", round(float(decision_function(model, q)[0]), 4), "->", int(np.sign(decision_function(model, q)[0])))

# x2 > 3.5 -> +1  eps=0.2000  alpha=0.6931  w=[0.0625 0.25 0.25 0.0625 ...]
# x1 > 6.5 -> +1  eps=0.1875  alpha=0.7332  w=[0.0385 0.1538 0.1538 0.1667 0.1667 ...]
# x1 > 4.5 -> -1  eps=0.1923  alpha=0.7175  w=[0.1 0.0952 0.0952 0.1032 0.1032 ...]
# 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
# 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
import numpy as np
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

X = np.array([[3, 2], [6, 10], [5, 6], [10, 1], [4, 4], [1, 3], [8, 7], [2, 9], [9, 5], [7, 8]], float)
y = np.array([-1, -1, -1, -1, 1, -1, 1, 1, 1, 1])

ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=3,
                         learning_rate=1.0, random_state=0).fit(X, y)
for est, err, wt in zip(ada.estimators_, ada.estimator_errors_, ada.estimator_weights_):
    t = est.tree_
    print(f"split x{t.feature[0] + 1} <= {t.threshold[0]:.1f}  error={err:.4f}  weight={wt:.4f}  (= 2*alpha)")
print("train accuracy:", ada.score(X, y))
q = np.array([[6, 4]])
print("decision_function(6,4):", ada.decision_function(q).round(4), "predict:", ada.predict(q))
print("staged train acc:", [round(s, 2) for s in ada.staged_score(X, y)])

# split x2 <= 3.5  error=0.2000  weight=1.3863  (= 2*alpha)
# split x1 <= 6.5  error=0.1875  weight=1.4663  (= 2*alpha)
# split x1 <= 4.5  error=0.1923  weight=1.4351  (= 2*alpha)
# train accuracy: 1.0
# decision_function(6,4): [-0.7067] predict: [-1]
# 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.

> **Reading scikit-learn's numbers:** For two classes, `decision_function` returns $2F(x)/\sum_t\alpha_t$: here $2(-0.7576)/2.1438=-0.7067$. Same sign as $F$, but bounded in $[-2,2]$ — do not plug it into $1/(1+e^{-2F})$ without undoing the scaling.

> **Why test error keeps falling after training error hits 0:** Running AdaBoost with depth-4 trees on the Hastie data, training error reaches 0 at round 112 (test error 0.102) — yet test error keeps dropping to 0.094 by round 1000. The exponential loss is still positive, so AdaBoost keeps **enlarging the margins**: the smallest normalized margin on the training set grows from 0.003 to 0.086. Schapire et al. (1998) bound test error by the fraction of training points with small margin, independent of $T$ — which is why AdaBoost resists overfitting far better than its number of parameters suggests.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **Label noise is AdaBoost's weak spot:** A mislabelled point is misclassified round after round, so its weight is multiplied by $e^{\alpha_t}$ again and again. On the Hastie data with 15.45% of training labels (309 of 2,000) flipped, after 400 stump rounds those flipped points held 25% of the total weight; test error rose from 0.116 (clean labels) to 0.146, while gradient boosting with log-loss on the same noisy labels kept 0.116. Clean labels, limit T, use $\nu<1$, or prefer a log-loss booster when labels are unreliable.

> **A base learner that is too strong (or too weak):** If the base learner fits the weighted data perfectly ($\varepsilon_t=0$), $\alpha_t=\infty$ and boosting stops after one round — you just trained a deep tree. If it cannot beat ½ on some reweighting ($\varepsilon_t\ge\tfrac12$), $\alpha_t\le0$ and training halts early (scikit-learn silently returns fewer estimators — check `len(model.estimators_)`). Keep the learner weak: depth 1–3.

> **Training error is not monotone:** In the worked example training errors went 2 → 3 → 0. AdaBoost minimizes the exponential loss, which does decrease every round ($\prod Z_t$); the 0–1 training error can go up temporarily. Do not stop the first time training error increases.

**Question:** 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?

- A. α = 0.25; 25%
- B. α = ½ ln 3 ≈ 0.549; 50%
- C. α = ln 3 ≈ 1.099; 75%
- D. α = ½ ln 3 ≈ 0.549; 25%

**Answer:** B. α = ½ ln 3 ≈ 0.549; 50% — $\alpha=\tfrac12\ln\tfrac{0.75}{0.25}=\tfrac12\ln3=0.549$. After the update the misses weigh $\varepsilon e^{\alpha}/Z=\tfrac12$ — always exactly half, whatever $\varepsilon$ was.

**Question:** On some reweighting the best stump has ε = 0.6. What does discrete AdaBoost's formula give, and what does that mean?

- A. α ≈ 0.203: a small positive vote
- B. α ≈ −0.203: the learner is worse than chance; flipping it would give ε = 0.4, and AdaBoost stops
- C. α = 0: it is ignored but training continues unchanged
- D. α = ∞: it is perfect

**Answer:** B. α ≈ −0.203: the learner is worse than chance; flipping it would give ε = 0.4, and AdaBoost stops — $\tfrac12\ln\tfrac{0.4}{0.6}=-0.203$. A stump that is wrong 60% of the time is a 40%-error stump with flipped polarity — the stump search should have found that one. ε ≥ ½ for the best learner means no weak learner is left, and discrete AdaBoost stops.

**Question:** In the worked example, why did round 2 choose x₁ > 6.5 → +1 rather than another stump?

- A. It has the lowest unweighted error
- B. It classifies the two heavy points #2 and #3 (weight 0.25 each) correctly and only misses three light points (0.0625 each), for ε = 0.1875
- C. AdaBoost never reuses the feature of the previous round
- D. It maximizes information gain

**Answer:** B. It classifies the two heavy points #2 and #3 (weight 0.25 each) correctly and only misses three light points (0.0625 each), for ε = 0.1875 — Half of the weight sat on #2 and #3 after round 1. Any stump that misses them pays at least 0.25; x₁ > 6.5 gets both right and misses #4, #5, #8 for 3 × 0.0625 = 0.1875 — the smallest weighted error. Features can repeat: round 3 uses x₁ again, and round 4 reuses h₁ exactly.

**Question:** Every weak learner has edge γ = ½ − ε ≥ 0.1. Which statement about the training error after T rounds is guaranteed?

- A. It is at most e^(−2·0.01·T) = e^(−0.02T)
- B. It decreases by 0.1 every round
- C. It is at most (0.9)^T
- D. Nothing can be guaranteed

**Answer:** A. It is at most e^(−2·0.01·T) = e^(−0.02T) — Training error ≤ $\prod_t\sqrt{1-4\gamma_t^2}\le e^{-2\sum_t\gamma_t^2}\le e^{-2(0.1)^2T}=e^{-0.02T}$. It falls exponentially in $T$, but not necessarily every round — in the worked example it rose from 2 to 3 errors in round 2.

**Key points**

- AdaBoost fits weak learners in sequence on reweighted data: misses are multiplied by $e^{\alpha_t}$, hits by $e^{-\alpha_t}$, then renormalized — after which the misses hold exactly half the weight.
- The vote $\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^{-yF}$.
- Training error ≤ exponential loss $=\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)$ estimates half the log-odds; $\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
