Skip to main content

Weak learners that take turns

A weak learner is only a little better than guessing. Boosting trains a sequence of them, each on a reweighted copy of the data that stresses the last one’s mistakes. Learn the decision stump, weighted error and weighted Gini, and fit the best stump on the twelve points by hand.
ML02.3.1L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: ML02.1 Decision trees ML02.2 Bagging and random forests ML01.8.2 Bias and variance

What you will be able to do
  • Define a weak learner and a decision stump, and explain why a learner with error above one half can be flipped into one below it.
  • Compute the weighted error and the weighted Gini impurity of a stump for given example weights.
  • Fit the best weighted stump on a small data set by hand and in NumPy, and check it against scikit-learn.
  • Contrast boosting with bagging: members built in turn on reweighted data to cut bias, against members built independently to cut variance.

The question

A single question such as “is \(x_1\) at most 3.5?” gets ten of the twelve points right. A fully grown tree gets all twelve right and, as ML02.1.4 showed, overfits. Is there a middle road: can a crowd of rules that are each barely better than guessing be combined into one that is as accurate as we like?

Intuition

The answer is yes, and the trick is to let the rules take turns. Fit one simple rule. Look at the points it gets wrong. Make those points count for more, and fit the next rule to the reweighted data, so that it is pushed to get them right. Repeat, then let all the rules vote.

Two panels of the twelve points: blue circles for class minus 1 and sky-blue squares for class plus 1. Left panel, titled Round 1: equal weights, has every point the same size, a vermillion vertical line at x1 equals 3.5 with predict minus 1 on its left and predict plus 1 on its shaded right, and purple rings around the two points it gets wrong, the circle at (5, 5) and the square at (2, 5). Right panel, titled Before round 2: new weights, draws each point with area proportional to its weight: the two missed points are large and labelled 1/4, and the other ten are small, labelled 1/20 each.
ML02.3.1-F1

Round 1 treats every point alike, and the stump \({x_1 \le 3.5}\) misses two of them. Before round 2 those two misses are made heavier, so that together they weigh as much as the other ten.

This is boosting. Its members are weak learners: rules that only need to beat a coin flip on whatever weighting they are handed. The standard weak learner is the decision stump, a tree with a single split. The picture shows the whole rhythm of the method: a stump, its mistakes, and a new weighting that makes those mistakes impossible to ignore.

Build it up

Step 1. A stump is one question. A decision stump picks one feature \(x_j\), one threshold \(t\) and a direction \(s\), which is \({+1}\) or \({-1}\). It predicts \(s\) when \({x_j > t}\) and \({-s}\) otherwise. On the twelve points there are five thresholds for \(x_1\) (the midpoints 1.5, 2.5, 3.5, 4.5, 5.5) and four for \(x_2\), and each comes in two directions: 18 stumps in all.

Step 2. Weak means “better than a coin”. With two classes, guessing at random is wrong half the time. A weak learner is any method that, for every weighting of the training points, can return a rule whose weighted error is below one half, even if only just.

Step 3. Labels become \({-1}\) and \({+1}\). Trees used labels 0 and 1. Boosting writes them \({y_i \in \{-1, +1\}}\): class 0 of the twelve points becomes \({-1}\) and class 1 becomes \({+1}\). Then a prediction \(h(x_i)\) is right exactly when \({{y_i\, h(x_i)} = +1}\) and wrong when it is \({-1}\), and a weighted vote is just a weighted sum whose sign is the answer.

Step 4. Members built in turn. Bagging (ML02.2) grows its trees side by side, each on its own bootstrap sample, and none knows about the others. Boosting builds its members one after another, and each member is trained on weights set by the ones before it.

A flow diagram in two columns. Left, titled Bagging: side by side: a blue box training data branches into three blue boxes sample 1, sample 2, sample 3, each leading to a vermillion box tree 1, tree 2, tree 3, and all three feed a box plain vote. Underneath: members ignore each other; averaging cuts variance. Right, titled Boosting: in turn: an orange box weights leads to stump 1, a purple arrow labelled raise misses leads to the next weights box, then stump 2, then raise misses, weights, stump 3. A rail on the right collects all three stumps into a box vote weighted by alpha m. Underneath: each member fixes the last; the sum cuts bias.
ML02.3.1-F2

Bagging averages members that are built independently; boosting chains them, so that each one works on what the team so far gets wrong.

The two designs attack different parts of the error of ML01.8.2. Bagging averages deep trees, which have low bias and high variance, and the averaging removes much of the variance. Boosting starts from stumps, which have low variance and high bias, and adds them up into a far more flexible rule, which removes bias. A single stump can only cut the plane once; a weighted sum of many stumps can carve it into a staircase of pieces.

The formal statement

Take training points \((x_1, y_1), \dots, (x_n, y_n)\) with \({y_i \in \{-1, +1\}}\), and example weights \({\cparam{w_i} \ge 0}\) that sum to 1. A weight says how much a point counts; equal weights \({w_i = 1/n}\) give ordinary counting.

NoteDefinition: weighted error

The weighted error of a classifier \(h\) is the total weight of the points it gets wrong:

\[ \closs{\epsilon(h)} = \sum_{i=1}^{n} \cparam{w_i}\, I[h(x_i) \neq y_i]. \]

Here \(I[\,\cdot\,]\) is 1 when the statement inside is true and 0 otherwise.

With equal weights, \(\epsilon(h)\) is the plain error rate. With unequal weights, a heavy point that is missed costs more than a light one.

Flipping a stump. Reverse the direction \(s\) of a stump and every prediction changes sign, so each point it got right is now wrong and each point it got wrong is now right. The new error is the weight of the old right answers:

\[ \epsilon(-h) = 1 - \epsilon(h). \]

So a stump with error 0.7 is not useless: its flip has error 0.3. Because the stump family contains both directions of every split, its best member always has error at most \(\tfrac12\). The weak learning condition asks a little more: an edge \({\gamma > 0}\) such that every round’s learner has \({\epsilon \le \tfrac12 - \gamma}\).

A number line for the weighted error from 0 to 1, with the stretch from 0 to one half shaded green and labelled better than a coin, and the stretch from one half to 1 labelled worse than a coin. Eighteen purple dots stand above the line, one per stump of the twelve points with equal weights, stacked where errors are equal, and they lie in mirror-image pairs about one half. A green curved arrow runs from the dot at 10/12 to the dot at 2/12, labelled flip the sign: e goes to 1 minus e.
ML02.3.1-F5

The 18 stumps of the twelve points come in pairs whose errors add to 1. Flipping the worse member of a pair gives the better one, so the best stump never does worse than a coin.

Weighted Gini. A tree grower (ML02.1.2) scores a split by impurity, and the same score works with weights: measure every count by weight instead. In a node with total weight \(W\), the share of class \({+1}\) is the weight of its \({+1}\) points divided by \(W\), and the Gini impurity is \({G = 1 - p_{-}^2 - p_{+}^2}\) with these shares. A split into nodes of weight \(W_L\) and \(W_R\) is scored by the size-weighted average

\[ G_{\text{split}} = \frac{W_L\, G_L + W_R\, G_R}{W_L + W_R}. \]

With equal weights this is exactly the weighted Gini of ML02.1.2. The two scores usually pick the same stump, but not always. Weighted error asks the question boosting cares about; scikit-learn’s stumps use weighted Gini, and ML02.3.2 meets a round where the two part ways.

Worked example

Find the best stump on the twelve points with equal weights, \({w_i = 1/12}\).

Take \({x_1 \le 3.5}\) first. The six points with \({x_1 \le 3.5}\) are \((1,1)\), \((2,1)\), \((1,2)\), \((2,3)\), \((3,2)\), which are \({-1}\), and \((2,5)\), which is \({+1}\). The six with \({x_1 > 3.5}\) are five \({+1}\) points and \((5,5)\), a \({-1}\). Predicting \({-1}\) on the left and \({+1}\) on the right gets \((2,5)\) and \((5,5)\) wrong, so

\[ \epsilon = \tfrac{1}{12} + \tfrac{1}{12} = \tfrac{2}{12} = \tfrac16 . \]

Now \({x_1 \le 2.5}\). Its left side holds \((1,1)\), \((2,1)\), \((1,2)\), \((2,3)\) and \((2,5)\); predicting \({-1}\) there misses \((2,5)\). Its right side holds \((3,2)\) and \((5,5)\), both \({-1}\), and the five other \({+1}\) points; predicting \({+1}\) there misses two. The error is \(3/12\).

Doing this for every threshold gives the trace below. The best stump is \({x_1 \le 3.5}\) with error \(2/12\), which is well below a coin’s \(6/12\).

Two bar charts side by side of weighted error, from 0 to one half, with a dashed line at one half labelled coin flip. Left, thresholds on x1: 1.5 has 4/12, 2.5 has 3/12, 3.5 has 2/12 drawn as a yellow bar outlined in vermillion and labelled best: x1 at most 3.5, 4.5 has 4/12 and 5.5 has 5/12. Right, thresholds on x2: 1.5 has 5/12, 2.5 has 4/12, 3.5 has 4/12 and 4.5 has 5/12.
ML02.3.1-F3

The weighted error of the better direction of every stump, with equal weights. The split \({x_1 \le 3.5}\) wins with two mistakes out of twelve.

The weighted Gini agrees. Each side of \({x_1 \le 3.5}\) has shares \(5/6\) and \(1/6\), so

\[ \begin{aligned} G_L = G_R &= 1 - \left(\tfrac56\right)^2 - \left(\tfrac16\right)^2 \\ &= \tfrac{10}{36} = \tfrac{5}{18}, \end{aligned} \]

and the split scores \(5/18\), the value ML02.1.2 found.

Now change the weights. Suppose the two missed points weigh \(1/4\) each and the other ten weigh \(1/20\) each (lesson ML02.3.2 shows these are exactly AdaBoost’s weights after one round). The same stump \({x_1 \le 3.5}\) still misses only two points, but they now hold

\[ \epsilon = \tfrac14 + \tfrac14 = \tfrac12 , \]

no better than a coin. Its weighted Gini is also \(1/2\), the same as the root, so it separates nothing. The stump \({x_1 \le 1.5}\) with \({+1}\) on the right misses four points, \((2,1)\), \((2,3)\), \((3,2)\) and \((5,5)\), yet its weighted error is only \({3 \times \tfrac{1}{20} + \tfrac14 = \tfrac{2}{5}}\). Under the new weights it is the better stump.

Code

A weighted stump from scratch. The search runs over features, then thresholds, then the two directions, and keeps the first stump found when two tie.

import numpy as np

X = np.array([(1, 1), (2, 1), (1, 2), (2, 3), (3, 2), (5, 5),
              (4, 1), (5, 2), (5, 3), (4, 4), (2, 5), (6, 5)], dtype=float)
y = np.array([-1] * 6 + [1] * 6)

def stump_predict(X, j, t, s):
    """Predict s where feature j is above t, and -s elsewhere."""
    return np.where(X[:, j] > t, s, -s)

def fit_stump(X, y, w):
    """The stump with the smallest weighted error; the first found wins a tie."""
    best, best_err, count = None, np.inf, 0
    for j in range(X.shape[1]):
        values = np.unique(X[:, j])
        for t in (values[:-1] + values[1:]) / 2:
            for s in (1, -1):
                count += 1
                err = w[stump_predict(X, j, t, s) != y].sum() / w.sum()
                if err < best_err - 1e-12:
                    best, best_err = (j, float(t), s), err
    return best, best_err, count

equal = np.full(12, 1 / 12)
stump, err, count = fit_stump(X, y, equal)
print("stumps tried:", count, " best:", stump, " weighted error:", round(err, 4))

later = np.full(12, 1 / 20)
later[[5, 10]] = 1 / 4                      # the two misses made heavy
print("x1 <= 3.5 under the new weights:",
      later[stump_predict(X, 0, 3.5, 1) != y].sum())
print("best under the new weights:", fit_stump(X, y, later)[:2])
stumps tried: 18  best: (0, 3.5, 1)  weighted error: 0.1667
x1 <= 3.5 under the new weights: 0.5
best under the new weights: ((0, 1.5, 1), np.float64(0.3999999999999999))

The weighted Gini of a split, and scikit-learn’s stump, which takes the weights through sample_weight and chooses its split by weighted Gini.

from sklearn.tree import DecisionTreeClassifier

def weighted_gini(X, y, w, j, t):
    total = 0.0
    for side in (X[:, j] <= t, X[:, j] > t):
        W = w[side].sum()
        p = w[side & (y == 1)].sum() / W
        total += W * (1 - p**2 - (1 - p)**2)
    return total / w.sum()

print("Gini of x1 <= 3.5, equal weights:", round(weighted_gini(X, y, equal, 0, 3.5), 4))
print("Gini of x1 <= 3.5, new weights:  ", round(weighted_gini(X, y, later, 0, 3.5), 4))

for name, w in (("equal", equal), ("new", later)):
    tree = DecisionTreeClassifier(max_depth=1).fit(X, y, sample_weight=w)
    print(name, "weights: library splits on feature", tree.tree_.feature[0],
          "at", tree.tree_.threshold[0])
Gini of x1 <= 3.5, equal weights: 0.2778
Gini of x1 <= 3.5, new weights:   0.5
equal weights: library splits on feature 0 at 3.5
new weights: library splits on feature 0 at 1.5

Both weightings give the same answer from the library as from the hand search: \({x_1 \le 3.5}\) first, then \({x_1 \le 1.5}\) once the misses are heavy.

Explore

This module’s interactive, the AdaBoost stepper, lives in the next lesson. There you can press Step and watch each stump pick its split under the weights that the stumps before it set.

Pitfalls

Two panels of the twelve points, each point drawn with area proportional to its weight: the circle at (5, 5) and the square at (2, 5) are large, the rest small. Left, marked with a cross and titled Fewest mistakes: the vermillion line x1 equals 3.5, with the two large points ringed; underneath: 2 wrong, weighted error 1/2. Right, marked with a tick and titled Least weight wrong: the line x1 equals 1.5, with plus 1 predicted on its right, and four points ringed: the small ones at (2, 1), (2, 3) and (3, 2) and the large circle at (5, 5); underneath: 4 wrong, weighted error 2/5.
ML02.3.1-F4

Wrong beside right, under the weights of round 2. Counting mistakes picks the stump on the left, which is no better than a coin. Adding up the weight of the mistakes picks the one on the right.

“The best stump is the one with the fewest mistakes.”

Only when the weights are equal. Once AdaBoost reweights, a mistake on a heavy point costs more than several on light points. The figure shows it: two mistakes worth \(1/2\) lose to four mistakes worth \(2/5\).

“A weak learner is a bad model, so a team of them is a bad model too.”

Weak only means an edge over a coin on every weighting. The edge is what boosting needs: lesson ML02.3.3 proves that, as long as each round has an edge \(\gamma\), the training error of the vote falls exponentially fast in the number of rounds.

“Boosting is bagging with weights.”

Bagging’s members never see each other and can be built in parallel; averaging them cuts variance. Boosting’s members are built in order, each on weights set by the others, and adding them cuts bias. Bagged stumps each answer the same question on their own; boosted stumps form a team whose members cover each other’s mistakes.

Check yourself

Recall

1. What is a decision stump, and how many does the search try on the twelve points?

Show answer

A tree with one split: one feature, one threshold and a direction. The twelve points have five thresholds on \(x_1\) and four on \(x_2\), each in two directions, so 18 stumps.

2. Define the weighted error of a classifier.

Show answer

The total weight of the training points it gets wrong, \({\epsilon(h) = \sum_i w_i I[h(x_i) \neq y_i]}\), with weights that sum to 1.

3. Why can the best stump always reach an error of at most one half?

Show answer

Flipping a stump’s direction turns its error \(\epsilon\) into \({1 - \epsilon}\), and the family holds both directions, so one of each pair has error at most one half.

4. Which part of the error does boosting mainly reduce, and which does bagging reduce?

Show answer

Boosting adds up high-bias stumps into a flexible rule, so it mainly cuts bias. Bagging averages high-variance deep trees, so it mainly cuts variance.

5. With equal weights, what is the best stump on the twelve points and its error?

Show answer

\({x_1 \le 3.5}\), predicting \({-1}\) on the left and \({+1}\) on the right; it misses \((2,5)\) and \((5,5)\), so its error is \({2/12 = 1/6}\).

Exercises

1. ★ With equal weights, find the weighted error of the stump \({x_2 \le 2.5}\) that predicts \({+1}\) above the threshold. Then give the error of its flip.

Show solution

Above 2.5 lie \((2,3)\) and \((5,5)\), both \({-1}\), and \((5,3)\), \((4,4)\), \((2,5)\), \((6,5)\), all \({+1}\): two mistakes. Below lie \((1,1)\), \((2,1)\), \((1,2)\), \((3,2)\), all \({-1}\), and \((4,1)\), \((5,2)\), both \({+1}\): two more mistakes. The error is \({4/12 = 1/3}\), and its flip has error \({1 - 1/3 = 2/3}\).

2. ★★ Under the weights of the worked example (\(1/4\) on \((2,5)\) and \((5,5)\), \(1/20\) on the rest), find the weighted error of the stump \({x_2 \le 2.5}\) with \({+1}\) above, and compare it with \({x_1 \le 1.5}\).

Show solution

Its mistakes are \((2,3)\) and \((5,5)\) above the threshold and \((4,1)\) and \((5,2)\) below it. Their weight is \(\tfrac{1}{20} + \tfrac14 + \tfrac{1}{20} + \tfrac{1}{20} = \tfrac{8}{20} = \tfrac25\). That ties with \({x_1 \le 1.5}\), whose error is also \(\tfrac25\). The search order breaks the tie: features are tried in order, so \({x_1 \le 1.5}\) is found first and kept.

3. ★★★ Show that for any weights summing to 1, the weighted Gini of a split is never larger than the weighted Gini of the unsplit node. (Hint: Gini is a concave function of the share \(p\) of class \({+1}\).)

Show solution

For two classes,

\[ \begin{aligned} G(p) &= 1 - p^2 - (1-p)^2 \\ &= 2p(1-p), \end{aligned} \]

a concave function of \(p\). Let the node’s weight be split into \({W_L + W_R = 1}\), with shares \(p_L\) and \(p_R\). The parent’s share is the weighted average \({p = W_L p_L + W_R p_R}\), because both sides count the weight of class \({+1}\). Concavity says the function of an average is at least the average of the function values:

\[ \begin{aligned} G(p) &= G(W_L p_L + W_R p_R) \\ &\ge W_L\, G(p_L) + W_R\, G(p_R), \end{aligned} \]

and the right-hand side is the weighted Gini of the split. Equality holds when \({p_L = p_R}\), as for \({x_1 \le 3.5}\) under the round-2 weights, where both sides and the root have Gini \(1/2\).

Summary card

Boosting trains weak learners in turn, each on weights that stress the last one’s mistakes.

The anchor figure again: the twelve points with the stump x1 at most 3.5 and its two mistakes ringed, then the same points resized by weight, with the two misses at 1/4 each and the rest at 1/20.
ML02.3.1-F1

A stump, its misses, new weights.

  • Stump. Predict \(s\) if \({x_j > t}\), else \({-s}\).
  • Weighted error. \({\epsilon(h) = \sum_i w_i I[h(x_i) \neq y_i]}\), and \({\epsilon(-h) = 1 - \epsilon(h)}\).
  • Weak learner. Error at most \({\tfrac12 - \gamma}\) on every weighting.
  • Twelve points. Best stump \({x_1 \le 3.5}\), error \(1/6\), weighted Gini \(5/18\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Trevor Hastie, Robert Tibshirani and Jerome Friedman, The Elements of Statistical Learning, 2nd edition, corrected 12th printing, free PDF from the authors. Section 10.1 defines a weak classifier as one “only slightly better than random guessing”, describes reweighting the observations at each step, and uses a stump, “a two terminal-node classification tree”, as the weak classifier; Figure 10.1 is the schematic of classifiers trained on weighted versions of the data.
  • Robert E. Schapire, The Boosting Approach to Machine Learning: An Overview, in Nonlinear Estimation and Classification, Springer, 2003. Section 2 tells how Kearns and Valiant first asked whether a weak learner could be boosted into a strong one, and how AdaBoost was introduced by Freund and Schapire.
  • Kilian Weinberger, Cornell CS4780, lecture 19: Boosting (Fall 2018). It frames boosting as the way to combine weak learners into a learner with low bias.
  • scikit-learn 1.9 User Guide, section 1.11.7: AdaBoost. States that the weak learners are decision stumps by default, that every weight starts at \(1/N\), and that misclassified examples have their weights increased at each iteration.

Next. ML02.3.2 The AdaBoost algorithm, step by step turns this rhythm into an exact rule for the weights and the votes.

This lesson unlocks

ML02.3.2 The AdaBoost algorithm, step by step

Your progress is saved in this browser only. No account, no tracking.
Back to top