AdaBoost: Learning from Mistakes

Bagging trains its members independently and hopes their errors cancel. Boosting is more deliberate: train models one after another, and make each new model focus on exactly the samples the previous ones got wrong. AdaBoost (Adaptive Boosting, 1997) was the first practical algorithm to pull this off, and its central idea — re-weighting mistakes — is the cleanest way to understand everything that came after it, up to and including XGBoost.

Boosting: a sequence, not a committee

A random forest is a room full of experts voting at the same time. AdaBoost is a relay: the first model does its best, then hands the second model a note saying "I keep getting these samples wrong — you focus on them." The second model hands a similar note to the third, and so on. The final prediction is a weighted vote of the whole sequence, where models that performed well get a louder voice.

Two things had to be invented to make this work:

1. Sample weights — a number per training sample saying how much the next learner should care about it. Mistakes get their weight increased.
2. Learner weights (α) — how much each learner's vote counts in the final ensemble, based on how accurate it was on the weights it faced.

Re-weighting, round by round

Start with all n samples weighted equally at 1/n. Each round then does:

1. Train a weak learner on the current weights.
2. Compute its weighted error ε (the total weight of the samples it got wrong).
3. Give it a vote weight α = ½ · ln((1 − ε) / ε) — near-perfect learners get big α, coin-flip learners get α ≈ 0.
4. Multiply misclassified samples' weights up and correct ones down, then renormalize so the weights sum to 1.

Let's watch the numbers move for two rounds on ten samples:

Python — runs in your browser

Run

import numpy as np np.set_printoptions(precision=3, suppress=True) n = 10 w = np.full(n, 1 / n) print("round 0 weights:", w) # --- Round 1: stump misclassifies samples 3, 7, 8 --- miss = np.zeros(n, dtype=bool); miss[[3, 7, 8]] = True eps = w[miss].sum() alpha = 0.5 * np.log((1 - eps) / eps) print(f"\nround 1: weighted error = {eps:.3f}, learner weight alpha = {alpha:.3f}") w = w * np.exp(alpha * np.where(miss, 1, -1)) # up-weight misses, down-weight hits w = w / w.sum() print("weights after round 1:", w) print("-> samples 3, 7, 8 now carry", f"{w[3]:.3f}", "each vs", f"{w[0]:.3f}", "for the rest") # --- Round 2: new stump fixes 7 and 8 but misses samples 1, 3 --- miss = np.zeros(n, dtype=bool); miss[[1, 3]] = True eps = w[miss].sum() alpha = 0.5 * np.log((1 - eps) / eps) print(f"\nround 2: weighted error = {eps:.3f}, alpha = {alpha:.3f}") w = w * np.exp(alpha * np.where(miss, 1, -1)) w = w / w.sum() print("weights after round 2:", w) print("-> sample 3, wrong twice in a row, now dominates:", f"{w[3]:.3f}")

Follow sample 3 through the printout: wrong in round 1, its weight jumps from 0.10 to 0.17; wrong again in round 2, it climbs to the heaviest sample in the set. By round 3 any learner that wants a low weighted error basically must classify sample 3 correctly. That's the "adaptive" in Adaptive Boosting — the training distribution itself shifts toward the hard cases.

Weak learners and decision stumps

Boosting's base models are deliberately feeble. The classic choice is a decision stump: a depth-1 tree that asks a single question. On its own a stump barely beats a coin flip — but that's all boosting needs. Each round only has to contribute a small correction, and the weighted sum of hundreds of tiny corrections can trace an intricate boundary.

Weak learners aren't just sufficient — they're safer. A deep tree can fit the re-weighted samples (including noisy ones) almost perfectly in a round or two, which makes the ensemble jump straight to overfitting. Stumps force the progress to be gradual.

AdaBoost in scikit-learn

AdaBoostClassifier uses stumps by default. Its staged_predict method lets us score the ensemble after every round in one pass — perfect for seeing how accuracy builds up:

Python — runs in your browser

Run

import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_moons from sklearn.model_selection import train_test_split from sklearn.ensemble import AdaBoostClassifier from sklearn.metrics import accuracy_score X, y = make_moons(n_samples=500, noise=0.25, random_state=42) X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.3, stratify=y, random_state=42) ada = AdaBoostClassifier(n_estimators=200, learning_rate=0.5, random_state=42) ada.fit(X_train, y_train) train_curve = [accuracy_score(y_train, p) for p in ada.staged_predict(X_train)] test_curve = [accuracy_score(y_test, p) for p in ada.staged_predict(X_test)] plt.plot(train_curve, label="train") plt.plot(test_curve, label="test") plt.xlabel("number of stumps"); plt.ylabel("accuracy"); plt.legend() plt.show() print(f"1 stump : test acc = {test_curve[0]:.3f}") print(f"200 stumps: test acc = {test_curve[-1]:.3f}")

One stump manages a crude single cut; by a few dozen rounds the ensemble has bent itself around both moons. Notice the shape of the curves: fast gains early, then a long plateau — and if you push far enough on noisy data, the test curve can start drifting back down while train keeps climbing. Unlike a random forest, more boosting rounds is an overfitting axis, so n_estimators needs validation.

The learning rate

learning_rate scales every learner's contribution before it's added to the ensemble. It trades off against n_estimators:

• Small learning rate (0.1–0.5): each round corrects gently, so you need more rounds — but the ensemble is smoother and usually generalizes better.
• Learning rate near 1: aggressive corrections. Fewer rounds needed, but each round can over-commit to the current mistakes, and later rounds spend their effort fighting earlier over-corrections.

The standard recipe is shrink the learning rate, grow the round count, and pick the pair by validation.

Where AdaBoost sits in history

Freund and Schapire's AdaBoost (1997) was the proof that boosting worked outside of theory, and it earned them the Gödel Prize. A few years later, statisticians showed AdaBoost is a special case of a much more general recipe — gradient boosting, which reframes "focus on the mistakes" as gradient descent on any differentiable loss (AdaBoost corresponds to the exponential loss). That generalization, hardware-optimized as XGBoost and LightGBM, is what actually ships in production today. AdaBoost remains the best place to learn boosting, because you can see the mechanism — the weights — with your own eyes.

Check your understanding

5 questions · free

1. Q1.What is the key difference between how bagging and boosting train their members?

   ABagging uses trees; boosting uses linear modelsBBagging trains members independently in parallel; boosting trains them sequentially, each focusing on the previous members' errorsCBoosting requires more training dataDBagging uses sample weights; boosting uses bootstrap samples

2. Q2.After a round of AdaBoost, what happens to the weight of a sample the learner misclassified?

   AIt is removed from the training setBIt stays the sameCIt is increased, so the next learner pays more attention to itDIt is set to zero

3. Q3.Why are decision stumps (depth-1 trees) a good base learner for AdaBoost?

   AThey are more accurate than deep treesBEach round should add only a small correction; a strong learner would fit the re-weighted noise immediately and overfitCStumps do not require labelsDAdaBoost only supports depth-1 trees

4. Q4.A weak learner has weighted error ε = 0.5 (a coin flip). What vote weight α does AdaBoost give it?

   AA large positive weightBApproximately zero — ln(0.5/0.5) = ln(1) = 0CA weight of exactly 1DA negative infinite weight

5. Q5.Why is AdaBoost particularly sensitive to mislabeled samples?

   AIt cannot compute gini impurity on themBEvery learner misclassifies them, so their weights grow round after round until the ensemble distorts itself to fit themCMislabeled samples break the bootstrapDIt ignores them completely, wasting data

Exercise: Stumps vs deeper base learners

On make_moons with noise=0.3, train two AdaBoost models with 150 rounds: one with the default stumps (max_depth=1) and one whose base learner is a DecisionTreeClassifier with max_depth=4. Plot both test-accuracy curves (via staged_predict) on the same axes. Which base learner peaks higher, and which one's test accuracy decays as rounds accumulate?

Next up: gradient boosting — the reframing of AdaBoost's idea as gradient descent on residuals, and its industrial-strength descendant, XGBoost.