AdaBoost AlgorithmOpen in Colab

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

  1. Initialize equal weights: wi=1/nw_i = 1/n for all nn samples
  2. Train weak learner hbh_b on the weighted dataset
  3. Compute the weighted error: ϵb=∑i: hb(xi)≠yiwi∑iwi\epsilon_b = \dfrac{\sum_{i:\,h_b(\mathbf{x}_i) \neq y_i} w_i}{\sum_i w_i}
  4. Compute the model weight: αb=12ln⁡ ⁣(1−ϵbϵb)\alpha_b = \dfrac{1}{2}\ln\!\left(\dfrac{1-\epsilon_b}{\epsilon_b}\right)
  5. Update sample weights: wi←wi⋅exp⁡ ⁣(−αb yi hb(xi))w_i \leftarrow w_i \cdot \exp\!\left(-\alpha_b\,y_i\,h_b(\mathbf{x}_i)\right)
  6. Normalize weights: wi←wi/∑jwjw_i \leftarrow w_i / \sum_j w_j — then repeat from step 2

Final prediction:

f^(x)=sign ⁣(∑b=1Bαb hb(x))\hat{f}(\mathbf{x}) = \mathrm{sign}\!\left(\sum_{b=1}^{B} \alpha_b\,h_b(\mathbf{x})\right)

Labels must be ±1

AdaBoost requires yi∈{−1,+1}y_i \in \{-1, +1\}, not {0,1}\{0, 1\}. The sign in the update rule exp⁡(−αbyihb(xi))\exp(-\alpha_b y_i h_b(\mathbf{x}_i)) flips between shrinking (correct: yihb=+1y_i h_b = +1) and growing (wrong: yihb=−1y_i h_b = -1) the weight.

Watch it run

Three rounds on ten points whose labels no single stump can capture — the first round reproduces the ϵ=0.2\epsilon = 0.2, α=0.693\alpha = 0.693 worked by hand below:

AdaBoost — re-weight, refit, and vote

1/11

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.

python
1def adaboost(X, y, rounds):
2 w = [1 / n] * n
3 model = []
4 for _ in range(rounds):
5 h = best_stump(X, y, w) # weighted fit
6 err = sum(w[i] for i in range(n)
7 if h(X[i]) != y[i])
8 alpha = 0.5 * log((1 - err) / err)
9 # wrong -> weight grows, right -> shrinks
10 w = [w[i] * exp(-alpha * y[i] * h(X[i]))
11 for i in range(n)]
12 w = [wi / sum(w) for wi in w]
13 model.append((alpha, h))
14 return model
15
16def predict(model, x):
17 return sign(sum(a * h(x) for a, h in model))
state
the dataset
0111.6-1.60.100.100.100.100.100.100.100.100.100.10x (dot size not shown — weight is in the bars below)
sample weights
x=1 (y=+)
0.100
x=2 (y=+)
0.100
x=3 (y=+)
0.100
x=4 (y=+)
0.100
x=5 (y=+)
0.100
x=6 (y=−)
0.100
x=7 (y=−)
0.100
x=8 (y=−)
0.100
x=9 (y=+)
0.100
x=10 (y=+)
0.100

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 α\alpha 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 α

αb\alpha_b is not arbitrary. It is the exact minimizer of the exponential loss after the current stump is fixed. The objective at round bb is:

min⁡α∑i=1nwiexp⁡ ⁣(−α yi hb(xi))\min_\alpha \sum_{i=1}^n w_i \exp\!\bigl(-\alpha\,y_i\,h_b(\mathbf{x}_i)\bigr)

Split the sum into correctly classified (yihb=+1y_i h_b = +1) and misclassified (yihb=−1y_i h_b = -1) examples. Their total weights are (1−ϵb)(1-\epsilon_b) and ϵb\epsilon_b:

Loss=(1−ϵb) e−α+ϵb e+α\text{Loss} = (1-\epsilon_b)\,e^{-\alpha} + \epsilon_b\,e^{+\alpha}

Differentiate with respect to α\alpha and set to zero:

d Lossdα=−(1−ϵb) e−α+ϵb e+α=0\frac{d\,\text{Loss}}{d\alpha} = -(1-\epsilon_b)\,e^{-\alpha} + \epsilon_b\,e^{+\alpha} = 0 e2α=1−ϵbϵb  ⟹    αb=12ln⁡1−ϵbϵb  e^{2\alpha} = \frac{1-\epsilon_b}{\epsilon_b} \;\Longrightarrow\; \boxed{\;\alpha_b = \frac{1}{2}\ln\frac{1-\epsilon_b}{\epsilon_b}\;}

Interpretation of αb\alpha_b as a function of ϵb\epsilon_b:

Weighted error ϵb\epsilon_bModel weight αb\alpha_bBehavior
→0\to 0 (near-perfect)→+∞\to +\inftyDominates the ensemble
=0.5= 0.5 (random)=0= 0Ignored entirely
>0.5> 0.5 (worse than random)<0< 0Inverted vote

One complete round worked by hand

Setup: 10 points, uniform weights wi=0.1w_i = 0.1. A stump misclassifies exactly 2 of them.

Step 1 — weighted error:

ϵ1=2×0.110×0.1=0.21.0=0.2\epsilon_1 = \frac{2 \times 0.1}{10 \times 0.1} = \frac{0.2}{1.0} = 0.2

Step 2 — model weight:

α1=12ln⁡0.80.2=12ln⁡4=0.693\alpha_1 = \tfrac{1}{2}\ln\frac{0.8}{0.2} = \tfrac{1}{2}\ln 4 = 0.693

Step 3: reweight. Correct points multiply by e−0.693=0.5e^{-0.693} = 0.5; wrong points multiply by e+0.693=2.0e^{+0.693} = 2.0:

Example typeCountOld weightMultiplierNew weight
Correct80.10e−0.693=0.5e^{-0.693} = 0.50.050
Wrong20.10e+0.693=2.0e^{+0.693} = 2.00.200

Step 4: normalize. Sum =8(0.05)+2(0.20)=0.40+0.40=0.80= 8(0.05) + 2(0.20) = 0.40 + 0.40 = 0.80. Divide all weights by 0.80:

Example typeNormalized weight
Correct (8)0.050/0.80=0.06250.050/0.80 = 0.0625
Wrong (2)0.200/0.80=0.25000.200/0.80 = 0.2500

Verification: 8(0.0625)+2(0.25)=0.50+0.50=1.08(0.0625) + 2(0.25) = 0.50 + 0.50 = 1.0 ✓

Key identity: After normalization, the just-trained stump has exactly 0.5 weighted error on the new distribution — the two wrong points hold 2(0.25)=0.502(0.25) = 0.50 of the total weight. This is always true: AdaBoost's αb\alpha_b is chosen so each completed stump is exactly at chance on the updated weights, forcing the next stump to look elsewhere.

Python
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:

Python
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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
AdaBoost AlgorithmDecision Tree: Informatio…BoostingBagging & Random Forests