Adaboost
AdaBoost (Adaptive Boosting) is the original boosting algorithm that combines many "weak learners" (typically decision stumps — single-split trees) into a powerful ensemble — by iteratively reweighting training examples so that misclassified examples receive higher weights in each round, forcing subsequent weak learners to focus on the hard cases, and combining their predictions with weights proportional to each learner's accuracy, proving for the first time that many weak models can be systematically combined into a strong one.
What Is AdaBoost?
- Definition: A boosting algorithm that trains a sequence of weak classifiers (usually decision stumps), where each classifier receives higher-weighted examples that previous classifiers got wrong, and the final prediction is a weighted vote where more accurate classifiers get more influence.
- Historical Significance: AdaBoost (Freund & Schapire, 1997) was the first practical boosting algorithm, proving the theoretical result that weak learners can be boosted into strong learners, and winning the Gödel Prize in 2003 for its theoretical foundations.
- The Key Idea: "Focus where you fail" — after each round, increase the importance of misclassified examples so the next classifier is forced to get them right.
How AdaBoost Works
| Step | Process | Effect |
|---|---|---|
| 1. Initialize weights | All examples get equal weight: $w_i = 1/N$ | Every example equally important |
| 2. Train weak learner $h_1$ | Decision stump on weighted data | Gets ~60% right, ~40% wrong |
| 3. Compute learner weight $\alpha_1$ | $\alpha = \frac{1}{2}lnfrac{1-\varepsilon}{\varepsilon}$ (ε = error rate) | Better learners get higher α |
| 4. Update example weights | Misclassified examples: weight ↑ | Hard examples become more important |
| Correctly classified: weight ↓ | Easy examples become less important | |
| 5. Train weak learner $h_2$ | On reweighted data | Focuses on previously hard examples |
| 6. Repeat T rounds | Build ensemble of T weak learners | Progressive improvement |
| 7. Final prediction | $H(x) = \text{sign}left(\sum_{t=1}^{T} \alpha_t h_t(x)\right)$ | Weighted vote of all learners |
Example: Three Rounds
| Round | What Weak Learner Focuses On | Error Rate | Learner Weight (α) |
|---|---|---|---|
| 1 | All examples equally | 0.30 | 0.42 |
| 2 | The 30% that Round 1 got wrong | 0.25 | 0.55 |
| 3 | The remaining hard cases | 0.20 | 0.69 |
AdaBoost vs Gradient Boosting
| Feature | AdaBoost | Gradient Boosting (GBM/XGBoost) |
|---|---|---|
| Error correction | Reweight misclassified examples | Fit to residual errors (gradients) |
| Loss function | Exponential loss | Any differentiable loss |
| Weak learner | Decision stumps | Shallow decision trees (depth 3-8) |
| Outlier sensitivity | High ⚠️ (exponential loss amplifies outlier weights) | Lower (can use robust loss functions) |
| Modern usage | Limited (mostly educational/simple tasks) | Dominant (XGBoost, LightGBM, CatBoost) |
| Regularization | Limited | L1/L2, subsampling, learning rate |
Python Implementation
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
ada = AdaBoostClassifier(
estimator=DecisionTreeClassifier(max_depth=1), # Stumps
n_estimators=50,
learning_rate=1.0,
random_state=42
)
ada.fit(X_train, y_train)AdaBoost is the pioneering boosting algorithm that proved weak learners can be combined into strong learners — introducing the principle of adaptive reweighting that forces sequential classifiers to focus on hard examples, laying the theoretical and practical foundation for the modern gradient boosting family (XGBoost, LightGBM, CatBoost) that now dominates structured data tasks in both competitions and production.