AdaBoost with stumps

Each round adds a one-question tree (a stump) trained on weighted points, then raises the weight of the points it got wrong. Marker size shows weight.

Class A
Class B
Newest stump

Newest stump: up ≤ −0.41 votes class B, otherwise class A. Shading shows the weighted vote of all stumps so far: strong color where it is decisive, gray where it is close.

Newest stump's weighted error0.273

Its say in the vote (alpha)0.489

Its error on the new weights0.500

Training accuracy72.7%

Test accuracy64%

Challenges

0 of 3 complete

On Circle with no noise, add stumps until every training point is right. (not yet)
On XOR, run at least 100 rounds and see whether test accuracy ever passes 60%. (not yet)
On Moons with 10% noise, find a round where the flipped points hold more than 40% of all the weight. (not yet)

Try this

Press Next round a few times and watch which points grow.
Check Its error on the new weights after any round: it is always 0.500.
Play to 200 rounds on Moons with 20% noise and compare the training and test lines.
Try XOR and see the vote fail to find the checkerboard.

AdaBoost with stumpsPython with NumPy

import numpy as np

# Points on a line with labels +1 and -1. No single threshold separates them.
x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
y = np.array([1, 1, -1, -1, 1, 1, 1, -1, -1, -1])

def best_stump(w):
    # Try every threshold and both directions; keep the lowest weighted error.
    best = (np.inf, None, None)
    for t in (x[:-1] + x[1:]) / 2:
        for sign in (1, -1):
            pred = np.where(x <= t, sign, -sign)
            err = w[pred != y].sum()
            if err < best[0]:
                best = (err, t, sign)
    return best

w = np.full(len(x), 1 / len(x))  # start with equal weights
score = np.zeros(len(x))
for t in range(1, 6):
    err, thr, sign = best_stump(w)
    alpha = 0.5 * np.log((1 - err) / err)  # the stump's say in the vote
    pred = np.where(x <= thr, sign, -sign)
    w = w * np.exp(-alpha * y * pred)      # raise weights of mistakes
    w = w / w.sum()
    score += alpha * pred
    right = np.mean(np.sign(score) == y)
    print(f"round {t}: x <= {thr} -> {sign:+d}, error {err:.3f}, "
          f"alpha {alpha:.3f}, combined accuracy {right:.0%}")

round 1: x <= 7.5 -> +1, error 0.200, alpha 0.693, combined accuracy 80%
round 2: x <= 2.5 -> +1, error 0.188, alpha 0.733, combined accuracy 70%
round 3: x <= 4.5 -> -1, error 0.192, alpha 0.718, combined accuracy 100%
round 4: x <= 7.5 -> +1, error 0.190, alpha 0.723, combined accuracy 100%
round 5: x <= 2.5 -> +1, error 0.191, alpha 0.721, combined accuracy 100%