AdaBoost

The Algorithm

AdaBoost usually uses stumps: trees with a single question. Each stump on its own is barely better than guessing.

1. Give every training row the same weight, $\frac{1}{n}$.
2. Train a stump using these weights.
3. Compute its weighted error $\epsilon$: the total weight of the rows it got wrong.
4. Give the stump an amount of say:

5. Update the weights: multiply misclassified rows by $e^{\alpha }$ and correct rows by $e^{-\alpha }$, then rescale so they add up to 1.
6. Repeat from step 2.

Prediction: every stump votes, and each vote counts $\alpha$ times. The class with the larger total wins.

The Amount of Say

One Round by Hand

Ten rows, each starting with weight 0.1. The first stump gets 3 rows wrong, so $\epsilon =0.3$.

New weights before rescaling:

• Each wrong row: $0.1\times e^{0.424}=0.1\times 1.528=0.1528$. Three of them: 0.458.
• Each right row: $0.1\times e^{-0.424}=0.1\times 0.654=0.0654$. Seven of them: 0.458.

Rescale so the total is 1 (divide by 0.916):

• Each wrong row: 0.167. Each right row: 0.071.

Each misclassified row now weighs more than twice as much as a correct one. In fact, the three hard rows now hold exactly half of the total weight, so the next stump can't ignore them.

import numpy as np

w = np.full(10, 0.1)
wrong = np.array([1, 1, 1, 0, 0, 0, 0, 0, 0, 0], dtype=bool)

eps = w[wrong].sum()
alpha = 0.5 * np.log((1 - eps) / eps)
w = w * np.where(wrong, np.exp(alpha), np.exp(-alpha))
w = w / w.sum()

print(f"alpha = {alpha:.3f}")
print("new weights:", w.round(3))
print("weight on the wrong rows:", round(w[wrong].sum(), 3))

alpha = 0.424
new weights: [0.167 0.167 0.167 0.071 0.071 0.071 0.071 0.071 0.071 0.071]
weight on the wrong rows: 0.5

In scikit-learn

from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import AdaBoostClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)

stump = DecisionTreeClassifier(max_depth=1).fit(X_train, y_train)
print(f"one stump         : test accuracy {stump.score(X_test, y_test):.3f}")

for n in [10, 50, 200]:
    ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=n, learning_rate=0.5, random_state=0)
    ada.fit(X_train, y_train)
    print(f"AdaBoost {n:>3} stumps: test accuracy {ada.score(X_test, y_test):.3f}")

one stump         : test accuracy 0.889
AdaBoost  10 stumps: test accuracy 0.942
AdaBoost  50 stumps: test accuracy 0.930
AdaBoost 200 stumps: test accuracy 0.947

One question gets about nine in ten tumours right; a few dozen weighted stumps do much better.

Summary

• AdaBoost chains stumps; each round re-weights rows towards the mistakes.
• Amount of say $\alpha =\frac{1}{2}\ln \frac{1-\epsilon }{\epsilon }$; wrong rows × $e^{\alpha }$, right rows × $e^{-\alpha }$.
• The final prediction is a weighted vote.
• Sensitive to outliers and label noise.
• Next: a more general form of boosting that fits the errors directly, gradient boosting.