AdaBoost: Algorithm Intuition

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.

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

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.

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?