AdaBoost (Adaptive Boosting) trains a sequence of weak learners, giving progressively more weight to the training points previous learners got wrong — literally "adapting" its focus round by round.
The Algorithm, As Explicit Steps
| Step | What Happens |
|---|---|
| 1 | Initialize equal weights for every training point: \(w_i = 1/n\) |
| 2 | Train a weak learner using the current weights |
| 3 | Compute the weak learner's weighted error rate \(\varepsilon\) |
| 4 | Compute its voting weight: \(\alpha = \frac{1}{2}\ln\left(\frac{1-\varepsilon}{\varepsilon}\right)\) |
| 5 | Update point weights: increase weight for misclassified points, decrease for correctly classified ones |
| 6 | Normalize weights to sum to 1, repeat from step 2 |
| 7 | Final prediction: weighted vote across all rounds, using each round's \(\alpha\) |
Worked Example — One Full Round
4 training points, initial weights \(w=[0.25, 0.25, 0.25, 0.25]\). A weak learner misclassifies exactly 1 of the 4 points.
Update weights: misclassified point's weight is multiplied by \(e^{\alpha}\approx 1.732\); correctly classified points' weights are multiplied by \(e^{-\alpha}\approx 0.577\).
| Point | Before | Update | After (unnormalized) | After (normalized) |
|---|---|---|---|---|
| Misclassified | 0.25 | × 1.732 | 0.433 | 0.500 |
| Correct #1 | 0.25 | × 0.577 | 0.144 | 0.167 |
| Correct #2 | 0.25 | × 0.577 | 0.144 | 0.167 |
| Correct #3 | 0.25 | × 0.577 | 0.144 | 0.167 |
The misclassified point's weight doubles (from 0.25 to 0.50) — the next weak learner will now weight that point twice as heavily, directly forcing more focus on the mistake.
import numpy as np
weights = np.array([0.25, 0.25, 0.25, 0.25])
misclassified = np.array([True, False, False, False])
epsilon = weights[misclassified].sum()
alpha = 0.5 * np.log((1 - epsilon) / epsilon)
weights = np.where(misclassified, weights * np.exp(alpha), weights * np.exp(-alpha))
weights = weights / weights.sum() # normalize
print(alpha, weights) # 0.5493 [0.5, 0.1667, 0.1667, 0.1667]Python Implementation
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
model = AdaBoostClassifier(
estimator=DecisionTreeClassifier(max_depth=1), # a decision stump -- the classic weak learner
n_estimators=100,
learning_rate=1.0,
random_state=42,
)
model.fit(X_train, y_train)
print(model.score(X_test, y_test))What the Alpha Formula Actually Encodes
A weak learner that's only slightly better than random guessing (\(\varepsilon\) close to 0.5) gets a small \(\alpha\) — it barely counts in the final weighted vote. A weak learner that's very accurate (\(\varepsilon\) close to 0) gets a large \(\alpha\) — it dominates the final vote. This is why AdaBoost's final prediction is a weighted combination, not a plain average — better-performing rounds earn more say.
Practical Use Cases
- Binary classification problems with moderate-sized tabular data, where boosting's accuracy gains are valuable
- Historically one of the first practically successful boosting algorithms, still used and taught as the clearest introduction to the boosting idea
Common Mistakes
- Using AdaBoost on data with significant label noise — mislabeled points keep getting more weight round after round, since the algorithm has no way to distinguish "genuinely hard" from "actually mislabeled."
- Setting
n_estimatorsvery high without monitoring validation performance, risking overfitting in later rounds.
Interview Relevance
Q: "Why is AdaBoost particularly sensitive to noisy or mislabeled data?" Misclassified points get exponentially increasing weight each round — a genuinely mislabeled point can never be "correctly" classified, so its weight keeps growing round after round, eventually forcing later weak learners to distort their fit trying to accommodate what is actually bad data.
Practice Question
A weak learner achieves a weighted error of \(\varepsilon=0.1\) (very accurate). Compute its \(\alpha\), and compare it to the \(\alpha=0.549\) computed above for \(\varepsilon=0.25\).
