AdaBoost

What is AdaBoost?

Adaptive Boosting (AdaBoost - Yoav Freund & Robert Schapire, 1997 - Gödel Prize) was the first practical boosting algorithm.

Instead of building complex deep trees, AdaBoost builds a sequence of very simple weak learners called Decision Stumps (a decision tree with a depth of 1, making a single binary split).

A single decision stump performs only slightly better than random guessing (e.g. 55% accuracy).

AdaBoost combines hundreds of decision stumps into a strong ensemble classifier by sequentially re-weighting misclassified data samples.

  Sample Weights Initialized Equal (1 / N)
        │
        ▼
  [ Train Decision Stump 1 ] ──► Compute Error rate err_1 ──► Compute Voting Weight alpha_1
        │
        ▼
  INCREASE sample weights for MISCLASSIFIED instances!
        │
        ▼
  [ Train Decision Stump 2 ] ──► Focuses heavily on reweighted hard samples!
        │
        ▼
  Repeat for M steps ──► Final Output = sign( sum( alpha_m * h_m(x) ) )

Step-by-Step Algorithm Walkthrough

For binary classification targets $y_i \in {-1, +1}$ on $N$ samples:

Step 1: Initialize Sample Weights

Set equal starting weight for every sample:

$$w_i = \frac{1}{N}, \quad i = 1, \dots, N$$

Step 2: Sequential Training Loop (for $m = 1 \dots M$)

1. Fit a Decision Stump $h_m(x)$ using current sample weights $w_i$.
2. Calculate weighted classification error:

$$\text{err}m = \frac{\sum{i=1}^N w_i \cdot \mathbb{I}(y_i \neq h_m(x_i))}{\sum_{i=1}^N w_i}$$

3. Calculate voting weight $\alpha_m$ for Stump $m$:

$$\alpha_m = \frac{1}{2} \ln\left( \frac{1 - \text{err}_m}{\text{err}_m} \right)$$

• If error rate is low $\implies \alpha_m$ is large (high voting power!).
• If error rate is near 0.5 $\implies \alpha_m \approx 0$ (zero voting power).

4. Update sample weights for the next round:

$$w_i \leftarrow w_i \cdot \exp\left( -\alpha_m \cdot y_i \cdot h_m(x_i) \right)$$

• If sample $i$ was misclassified ($y_i \neq h_m(x_i)$) $\implies w_i$ is multiplied by $e^{\alpha_m}$ (Weight increases!).
• If sample $i$ was correctly classified $\implies w_i$ is multiplied by $e^{-\alpha_m}$ (Weight decreases!).

5. Normalize weights so $\sum w_i = 1.0$.

Step 3: Final Ensemble Prediction

$$H(x) = \text{sign}\left( \sum_{m=1}^M \alpha_m h_m(x) \right)$$

Sensitivity to Outliers

Because AdaBoost increases sample weights exponentially for misclassified samples at every step, noisy outliers get massive weight multipliers.

Subsequent stumps become obsessed with fitting 1 or 2 corrupt outlier data points, leading to severe overfitting.

Modern systems use Gradient Boosting (XGBoost) instead, which uses smooth loss gradients rather than exponential weight multipliers.

Say this out loud

AdaBoost fits a sequence of weak decision stumps, increasing sample weights for misclassified instances at each step so subsequent stumps focus on hard errors. Final predictions are computed using a weighted majority vote where accurate stumps receive higher voting weights alpha. AdaBoost is sensitive to noisy outliers due to exponential sample reweighting.

Followups to expect

1. Why is AdaBoost called Adaptive? Because subsequent weak learners adapt their training focus dynamically based on sample misclassification errors from previous rounds.
2. Can AdaBoost handle multi class classification? Yes, SAMME (Stagewise Additive Modeling using a Multi-class Exponential loss function) extends AdaBoost to $C > 2$ classes by adjusting voting weight $\alpha_m = \ln((1 - \text{err}) / \text{err}) + \ln(C - 1)$.