AdaBoost Algorithm
AdaBoost trains a sequence of weak learners (typically depth-1 decision stumps) where each round re-weights the training set so the next stump focuses on the current errors. The final prediction is a weighted vote across all stumps.
The six steps of the algorithm
- Initialize equal weights: for all samples
- Train weak learner on the weighted dataset
- Compute the weighted error:
- Compute the model weight:
- Update sample weights:
- Normalize weights: — then repeat from step 2
Final prediction:
Labels must be ±1
AdaBoost requires , not . The sign in the update rule flips between shrinking (correct: ) and growing (wrong: ) the weight.
Watch it run
Three rounds on ten points whose labels no single stump can capture — the first round reproduces the , worked by hand below:
AdaBoost — re-weight, refit, and vote
Ten points on a line. The labels are +1, then −1 in the middle, then +1 again — deliberately not monotone in x, which means **no single decision stump can get them all right**. A stump is a threshold and a direction; this data needs two boundaries. All weights start equal at 1/10 = 0.1.
Three rounds of AdaBoost on ten points whose labels no single decision stump can capture. Round 1 reproduces the hand-worked ε = 0.2 and α = 0.693 above; watch the sample weights after it, where the two missed points jump to half the total mass and steer the next stump. The final step votes the three stumps together and gets every point right — none of them could alone.
What to notice as you step:
- The re-weighting is the algorithm. After round 1 the two missed points carry 50% of the total weight, and they carry exactly 50% after every round, which is not a coincidence: the that minimizes exponential loss is precisely the one that equalizes the weight on hits and misses.
- Each stump is worse than the last, by raw accuracy. Rounds 2 and 3 miss 3 and 5 points. They are not meant to be good. They are meant to be good on the part of the data the ensemble still gets wrong.
- The vote gets everything right. Three learners that individually fail, in weighted combination, classify all ten points. Their errors do not overlap, which is the whole return on re-weighting.
Deriving the model weight α
is not arbitrary. It is the exact minimizer of the exponential loss after the current stump is fixed. The objective at round is:
Split the sum into correctly classified () and misclassified () examples. Their total weights are and :
Differentiate with respect to and set to zero:
Interpretation of as a function of :
| Weighted error | Model weight | Behavior |
|---|---|---|
| (near-perfect) | Dominates the ensemble | |
| (random) | Ignored entirely | |
| (worse than random) | Inverted vote |
One complete round worked by hand
Setup: 10 points, uniform weights . A stump misclassifies exactly 2 of them.
Step 1 — weighted error:
Step 2 — model weight:
Step 3: reweight. Correct points multiply by ; wrong points multiply by :
| Example type | Count | Old weight | Multiplier | New weight |
|---|---|---|---|---|
| Correct | 8 | 0.10 | 0.050 | |
| Wrong | 2 | 0.10 | 0.200 |
Step 4: normalize. Sum . Divide all weights by 0.80:
| Example type | Normalized weight |
|---|---|
| Correct (8) | |
| Wrong (2) |
Verification: ✓
Key identity: After normalization, the just-trained stump has exactly 0.5 weighted error on the new distribution — the two wrong points hold of the total weight. This is always true: AdaBoost's is chosen so each completed stump is exactly at chance on the updated weights, forcing the next stump to look elsewhere.
import numpy as np
def adaboost_one_round(n=10, n_wrong=2):
w = np.full(n, 1/n)
# Simulated stump: first n_wrong examples are misclassified
correct = np.ones(n)
correct[:n_wrong] = -1 # -1 means y_i * h_b = -1 (wrong)
epsilon = np.sum(w[correct < 0]) # weighted error
alpha = 0.5 * np.log((1 - epsilon) / (epsilon + 1e-12))
# Update weights: multiply by exp(-alpha * y_i * h_b)
w *= np.exp(-alpha * correct)
w /= w.sum() # normalize
print(f"ε₁ = {epsilon:.3f}, α₁ = {alpha:.3f}")
print(f"Correct weight: {w[correct > 0][0]:.4f} each")
print(f"Wrong weight: {w[correct < 0][0]:.4f} each")
print(f"Wrong points total weight: {w[correct < 0].sum():.3f}") # ≈ 0.5
adaboost_one_round(n=10, n_wrong=2)
Coding the algorithm from scratch
From-scratch AdaBoost with decision stumps:
import numpy as np
class DecisionStump:
def fit(self, X, y, w):
n, d = X.shape
best = {'err': np.inf}
for j in range(d):
for thresh in np.unique(X[:, j]):
for sign in [1, -1]:
pred = np.where(X[:, j] >= thresh, sign, -sign)
err = np.dot(w, pred != y)
if err < best['err']:
best = {'err': err, 'j': j, 'thresh': thresh, 'sign': sign}
self.__dict__.update(best)
def predict(self, X):
return np.where(X[:, self.j] >= self.thresh, self.sign, -self.sign)
class AdaBoost:
def __init__(self, n_rounds=50):
self.n_rounds = n_rounds
def fit(self, X, y):
n = len(y)
w = np.full(n, 1/n)
self.stumps, self.alphas = [], []
for _ in range(self.n_rounds):
h = DecisionStump()
h.fit(X, y, w)
pred = h.predict(X)
eps = np.dot(w, pred != y) + 1e-12
alpha = 0.5 * np.log((1 - eps) / eps)
w *= np.exp(-alpha * y * pred)
w /= w.sum()
self.stumps.append(h)
self.alphas.append(alpha)
def predict(self, X):
votes = sum(a * h.predict(X) for a, h in zip(self.alphas, self.stumps))
return np.sign(votes)
Related concepts
- Boosting: gradient boosting, XGBoost, and the full ensemble lesson
- Decision Tree: Information Gain: the weak learner typically boosted
- Bagging & Random Forests: the parallel alternative