In 1988 Michael Kearns asked a theoretical question: if we can learn classifiers that are only slightly better than random guessing — weak learners — can we combine them into an arbitrarily accurate strong learner? Robert Schapire proved the answer is yes, and in 1995 Yoav Freund and Schapire created AdaBoost (Adaptive Boosting), a practical algorithm that won them the Gödel Prize. AdaBoost with decision stumps powered the Viola–Jones face detector that ran in early digital cameras.
Boosting versus bagging#
- Bagging trains models independently in parallel on resampled data and averages them — reducing variance.
- Boosting trains models sequentially, each focusing on the mistakes of the ensemble so far — reducing bias (and often variance too).
The AdaBoost algorithm#
Binary labels $y_i \in \{-1, +1\}$. Start with uniform example weights $w_i = 1/n$. For $t = 1, \dots, T$:
- Train a weak learner $h_t$ on the weighted data (typically a decision stump — a one-split tree).
- Compute its weighted error:
- Compute its vote weight:
- Update and renormalise example weights:
Final classifier:
Reading the update: misclassified examples ($y_ih_t(\mathbf{x}_i) = -1$) are multiplied by $e^{\alpha_t} > 1$ — they become more important; correctly classified examples are down-weighted. The next weak learner is forced to concentrate on the hard cases. Learners with low error receive large votes $\alpha_t$; a learner at chance ($\epsilon_t = 0.5$) receives $\alpha_t = 0$.
Training error falls exponentially#
If each weak learner has edge $\gamma_t = 0.5 - \epsilon_t > 0$, the training error of $H$ is bounded by
Even a small consistent edge drives training error to zero exponentially fast. This is the theoretical heart of boosting.
AdaBoost as exponential-loss minimisation#
Friedman, Hastie and Tibshirani (2000) showed that AdaBoost performs forward stagewise additive modelling with the exponential loss:
At each step it greedily adds the term $\alpha_th_t$ that most reduces this loss; the formula for $\alpha_t$ is exactly the optimal step size. This statistical view opened the door to gradient boosting, which works with any differentiable loss (next lecture).
The quantity $yF(\mathbf{x})$ is the margin. The exponential loss keeps pushing margins larger even after all training points are correctly classified — which helps explain AdaBoost's often surprising resistance to overfitting as $T$ grows.
Implementation from scratch#
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
X, y01 = make_classification(n_samples=1500, n_features=10, n_informative=5, random_state=1)
y = 2 * y01 - 1 # labels in {-1, +1}
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)
def adaboost(X, y, T=200):
n = len(y); w = np.full(n, 1 / n)
learners, alphas = [], []
for t in range(T):
stump = DecisionTreeClassifier(max_depth=1).fit(X, y, sample_weight=w)
pred = stump.predict(X)
eps = np.clip(w[pred != y].sum(), 1e-10, 1 - 1e-10)
alpha = 0.5 * np.log((1 - eps) / eps)
w *= np.exp(-alpha * y * pred); w /= w.sum()
learners.append(stump); alphas.append(alpha)
return learners, np.array(alphas)
def predict(learners, alphas, X, upto=None):
F = sum(a * h.predict(X) for h, a in zip(learners[:upto], alphas[:upto]))
return np.sign(F)
L, A = adaboost(X_tr, y_tr)
for T in [1, 10, 50, 200]:
print(f"T={T:>3}: train acc {np.mean(predict(L, A, X_tr, T) == y_tr):.3f} "
f"test acc {np.mean(predict(L, A, X_te, T) == y_te):.3f}")A single stump is weak; two hundred of them form a strong classifier.
Weaknesses#
- Sequential training cannot be parallelised across rounds.
- Performance depends on weak learners being better than chance but not too complex.
Variants#
- SAMME — multiclass AdaBoost (used by scikit-learn).
- Real AdaBoost — uses class probability estimates.
- LogitBoost — minimises logistic loss; more robust to noise.
- Gradient boosting — the general framework (next lecture).