AdaBoost: Algorithm Intuition

Your loan default model uses a single decision stump — one rule like "income ≤ 55k → default." Accuracy: 88%, barely better than guessing. The boss asks for 95%. One stump can't do it, but you build 500 of them, each focused on the mistakes of the previous ones, and combine their votes. The final model hits 98%.

That's AdaBoost — turning a sequence of weak learners into a strong one by making each new model fix the errors of its predecessors.

What Is AdaBoost?

AdaBoost (Adaptive Boosting) builds a strong classifier from many weak ones — each a decision stump (depth-1 tree). The key: after each round, samples that were misclassified receive higher weight, forcing the next stump to focus on them. The final prediction is a weighted vote of all stumps.

Anchor dataset: 8-sample loan default (y = ±1 for AdaBoost).

import numpy as np

# 8 samples: [income_$k, credit_score]
X = np.array([[25,580],[32,610],[45,650],[60,680],
              [70,710],[80,730],[90,750],[110,780]])
y = np.array([-1,-1,-1,-1,1,1,1,1])  # −1=default, +1=no_default

Setup

• Base learner: decision stump (max_depth=1, one feature, one threshold)
• Rounds: T (typically 50–500)
• Initial weights: all equal, $w_i=1/n=1/8=0.125$
• Final predictor: $F(x)=\text{sign}\left({\sum }_{t=1}^T{\alpha }_t{h}_t(x)\right)$

The sign of the weighted sum is the prediction; the magnitude is the confidence.

The Plan — 3 Rounds of Boosting

1. Round 1: Find the best stump, compute its weight ${\alpha }_1$, upweight the misclassified sample
2. Round 2: New stump focuses on the upweighted sample, gets its own ${\alpha }_2$
3. Round 3: Balance the two hard cases from Rounds 1 and 2
4. Final Prediction: Weighted vote of all 3 stumps on $x_{\text{new}}$

Round 1

Step 1a: Find Best Weighted Stump

For each threshold, compute weighted classification error:

$\epsilon ={\sum }_i{w}_i\cdot 1[h_t(x_i)\ne y_i]$

Test stump: income ≤ 55k → predict −1, income > 55k → predict +1.

${\epsilon }_1=0.125\text{(only sample 4 is wrong)}$

Step 1b: Compute Learner Weight

${\alpha }_1=\frac{1}{2}\ln \left(\frac{1-{\epsilon }_1}{{\epsilon }_1}\right)=\frac{1}{2}\ln \left(\frac{0.875}{0.125}\right)=\frac{1}{2}\ln (7)=\frac{1}{2}\times 1.946=0.973$

High ${\alpha }_1$ because this stump was nearly perfect (only 1 of 8 wrong).

Step 1c: Update Sample Weights

$w_i^{\text{new}}=w_i\cdot \exp \left(-{\alpha }_1\cdot y_i\cdot h_1(x_i)\right)$

When the stump is correct: $y_i{h}_1(x_i)=+1$ → multiply by $e^{-{\alpha }_1}$ (downweight).
When the stump is wrong: $y_i{h}_1(x_i)=-1$ → multiply by $e^{+{\alpha }_1}$ (upweight).

• Correct samples (1,2,3,5,6,7,8): $0.125\times e^{-0.973}=0.125\times 0.378=0.0473$
• Wrong sample 4: $0.125\times e^{+0.973}=0.125\times 2.645=0.3306$

Normalize (sum = $7\times 0.0473+0.3306=0.662$):

$w_{\text{correct}}=0.0473/0.662=0.0714,w_4=0.3306/0.662=0.4993$

Updated weights: $[0.0714,0.0714,0.0714,0.4993,0.0714,0.0714,0.0714,0.0714]$

Sample 4 now holds 50% of the total weight. Any stump that misclassifies it incurs a weighted error ≥ 0.5 — worse than random guessing.

✓ Round 1 complete. Stump 1 (income ≤ 55k) gets α=0.973. Sample 4 misclassified → weight jumps from 0.125 to 0.499.

Round 2

Step 2a: Best Stump with New Weights

Sample 4 (income=60, credit=680, y=−1) dominates. The algorithm searches for a stump that classifies it correctly.

Candidate: credit_score ≤ 695 → predict −1, credit_score > 695 → predict +1.

All samples classified correctly! $\epsilon =0$ → ${\alpha }_2=\infty$ — the stump is perfect. In practice, a perfect stump terminates AdaBoost early (training complete). To illustrate Round 3, use a harder boundary:

Stump 2: credit_score ≤ 720 → predict −1, credit_score > 720 → predict +1.
Sample 6 (credit=730, y=+1): predict −1 → wrong.

${\epsilon }_2=w_6=0.0714$

${\alpha }_2=\frac{1}{2}\ln \left(\frac{1-0.0714}{0.0714}\right)=\frac{1}{2}\ln (13)=\frac{1}{2}\times 2.565=1.282$

After weight update: sample 6 is upweighted significantly (weight ≈ 0.30 after normalization), at the expense of the other correctly classified samples.

✓ Round 2 complete. Stump 2 (credit ≤ 720) gets α=1.282. Sample 6 misclassified → upweighted.

Round 3

After Round 2, the hard samples are 4 (high weight from Round 1) and 6 (high weight from Round 2). Stump 3 must handle them simultaneously.

Candidate: income ≤ 75k → predict −1, income > 75k → predict +1.
Sample 5 (income=70, y=+1): predict −1 → wrong.

With current weights (sample 4 partially normalized, sample 6 upweighted), say ${\epsilon }_3\approx 0.12$:

${\alpha }_3=\frac{1}{2}\ln \left(\frac{0.88}{0.12}\right)=\frac{1}{2}\ln (7.33)=0.995$

✓ Round 3 complete. Stump 3 (income ≤ 75k) gets α=0.995. Sample 5 misclassified. Weighted vote ready.

Final Prediction

$F(x)={\alpha }_1{h}_1(x)+{\alpha }_2{h}_2(x)+{\alpha }_3{h}_3(x)$

For $x_{\text{new}}=[55k\text{ income},685\text{ credit}]$:

$F(x)=-0.973-1.282-0.995=-3.250$

$\hat{y}=\text{sign}(-3.250)=-1(\text{predict: default})$

All three stumps agree. $|F(x)|=3.25$ — strong confidence.

Why AdaBoost Works — The Margin View

For each sample, the margin is:

$M_i=y_i\cdot F(x_i)=y_i\cdot {\sum }_{t=1}^T{\alpha }_t{h}_t(x_i)$

• $M_i>0$: correctly classified, larger margin = higher confidence
• $M_i<0$: misclassified

Training error bound: If each weak learner achieves ${\epsilon }_t<0.5$ (better than random):

$\text{Training error}\le \exp \left(-2{\sum }_{t=1}^T{\left(\frac{1}{2}-{\epsilon }_t\right)}^2\right)$

This bound is exponentially decreasing in T. As long as each stump does better than a coin flip, AdaBoost's training error approaches zero. In practice, test error also decreases for many rounds — often continuing after training error reaches 0, due to growing margins on correctly classified samples.

Key Properties

AdaBoost reduces bias where Random Forest reduces variance. If your base model already has low bias (deep tree), use RF. If base models are shallow (stumps), use AdaBoost.

When It Works and When It Doesn't

Reach for AdaBoost when your problem is binary classification, your base learners are weak but consistent (accuracy consistently > 50%), and you need high accuracy from a small number of features. It's especially effective when training data is clean (low label noise) and the decision boundary is complex enough that a single stump can't capture it.

The limit: AdaBoost fails on noisy data. A single mislabeled sample gets exponentially upweighted and can dominate the ensemble after a few rounds. It also can't be parallelized — each stump depends on the weights from the previous round, so T rounds require T sequential fits. For problems with high-dimensional sparse features where individual features have near-zero signal, stumps may fail the "better than random" requirement and the ensemble never converges.

Trace Table: AdaBoost on 8-Sample Loan Data

Related Concepts

AdaBoost builds directly on the boosting intuition from the ensemble overview post — understanding that sequential models target the errors of previous ones is the prerequisite. It also requires knowing what a decision stump is (a depth-1 decision tree from the Decision Tree series), since stumps are the required base learner. AdaBoost's weight update and margin analysis set up Gradient Boosting (next post), which replaces sample reweighting with residual fitting — a more general framework that works with any differentiable loss.

Honest Limitations

AdaBoost is highly sensitive to mislabeled training examples: a sample with a wrong label gets upweighted every time it is misclassified, eventually dominating the weight distribution. With label noise above approximately 5%, test accuracy can fall below a single stump because later rounds memorize the noisy sample rather than learning structure. The algorithm also requires that each weak learner performs better than random chance (ε < 0.5); on very high-dimensional sparse data where individual features carry nearly no signal individually, stumps may fail this requirement and the exponential training error bound breaks down entirely. Sequential training prevents parallelism — building 500 stumps requires 500 sequential model fits, roughly 10× slower than a Random Forest with the same number of base learners.

Test Your Understanding

1. After Round 1: ${\alpha }_1=0.973$. After Round 2: ${\alpha }_2=1.282$. Round 2's stump (credit ≤ 720) has a lower weighted error (0.0714) than Round 1 (0.125), yet ${\alpha }_2>{\alpha }_1$. Confirm this by computing $\alpha$ from the formula. What is the relationship between ${\epsilon }_t$ and ${\alpha }_t$? At what ${\epsilon }_t$ is ${\alpha }_t=0$?

2. If ${\epsilon }_t=0$ (perfect stump), ${\alpha }_t=\infty$. AdaBoost immediately terminates in this case because the model is already perfect (training error = 0). What does this imply about the usefulness of AdaBoost when the base learner is already a high-capacity model (e.g., a deep decision tree with low training error)?

3. The training error bound is $\exp (-2{\sum }_t(0.5-{\epsilon }_t{)}^2)$. For T=10 rounds all with ${\epsilon }_t=0.4$: compute the bound. For T=10 rounds all with ${\epsilon }_t=0.45$: compute the bound. How much more lenient is AdaBoost when each weak learner is slightly weaker?

4. An outlier in the training set (mislabeled: income=25k, y=+1 — should be default but labeled no_default) will be misclassified by every reasonable stump. In Round 1 it gets upweighted. In Round 2, the stump focuses on it and might be right by luck, but then another stump misses it again. What happens to this sample's weight after T=10 rounds where it's misclassified 8 times and correctly classified 2 times?

5. AdaBoost minimizes exponential loss $L={\sum }_i{e}^{-y_{i}F(x_i)}$, while logistic regression minimizes log loss $L={\sum }_i\log (1+e^{-y_{i}F(x_i)})$. For a correctly classified sample with $y_{i}F(x_i)=3$: compute both losses. For a misclassified sample with $y_{i}F(x_i)=-3$: compute both. Which loss penalizes misclassification more severely? What does this explain about AdaBoost's outlier sensitivity?