ML5.4 · LESSON 4 OF 6

Bagging

Choose a split by impurity reduction and distinguish bagging, random forests and boosting.

THE IDEA

Unstable models, steady averages

A deep tree is unstable: change a few training points and the cuts move, so the whole function changes. Its errors come partly from the particular sample it saw. If you could train many trees on different samples of the world, their individual quirks would point in different directions, and the average would cancel much of it. That is variance reduction.

You only have one training set, so bagging (bootstrap aggregating) manufactures many: draw n examples with replacement from your n, train a model on that resample, repeat, then average (regression) or vote (classification). A given example misses a resample with chance (1 − 1/n)ⁿ, which tends to 1/e ≈ 0.368, so each resample contains about 63.2% of the distinct examples. The remaining ones are out of bag for that model.

Training set size n:

Each box is one training example. The number shows how many times the latest draw picked it. Grey boxes are out of bag.

11210010100310132120

draw 1: 13 distinct of 20 = 65% in the bag, 7 out of bagaverage over 1 draws: 65%theory 1 - (1 - 1/20)^20 = 64.2%limit 1 - 1/e = 63.2%

Draw bootstrap samples and watch the share of distinct examples settle near 63.2%. The draws are seeded, so you see the same numbers every time.

Averaging many trees

Below, each thin blue line is a tree grown on a different bootstrap resample of the same 40 noisy points. Individually they wobble around the dashed true curve. The green average is smoother and closer. Move the sliders.

Orange dots: the 40 noisy training points. Dashed grey: the true curve (known, because we made the data). Thin blue: individual trees (first 15 shown). Green: the average of all of them.

Tree depth 4 Trees 1 bootstrap resample for every tree

average error of one tree vs the truth: 0.236 error of the averaged ensemble: 0.236 reduction: 0%

Error is the mean squared gap to the true curve on 101 evenly spaced inputs.

Try depth 1, then depth 4. Then switch resampling off.

With depth-4 trees and 50 resamples the typical single tree is off the true curve by 0.296 (mean squared), while the average is off by 0.137: a reduction of 53.7%. With stumps (one cut) the average still has error 0.575. A stump is badly biased: it can only draw one step, and averaging many steps does not turn them into a wave. Bagging cuts variance, not bias.

Predict first. You train 50 trees on the same data, with the same settings and no resampling, and average them. What do you get?

The common mistake

Bagging needs diversity. Averaging only removes errors that differ between models. It does not fix a model that is wrong in the same direction everywhere, and it does not help a model that is already stable. Bagging and boosting are also not two names for averaging: bagging trains models independently on resamples, while boosting (lesson 6) trains them one after another.

Chapter context

A decision tree recursively asks questions that partition data. An ensemble combines many models to improve behavior, but the way those models are trained determines what kind of errors the combination can reduce.

TRY IT YOURSELF

Part 1. Do it by hand

Tune depth, number of trees and resampling to hit each target. Errors are measured against the true curve, so the numbers are exact.

Orange dots: the 40 noisy training points. Dashed grey: the true curve (known, because we made the data). Thin blue: individual trees (first 15 shown). Green: the average of all of them.

Tree depth 4 Trees 1 bootstrap resample for every tree

average error of one tree vs the truth: 0.236 error of the averaged ensemble: 0.236 reduction: 0%

Error is the mean squared gap to the true curve on 101 evenly spaced inputs.

To do: Bag at least 20 trees and cut the error against the true curve to less than half of what a single tree gets (reduction of 50% or more)
To do: Show what bagging cannot fix: with stumps (depth 1) and at least 20 trees, the averaged curve is still far from the truth (error above 0.4)
To do: Turn resampling off with deep trees (depth 4 or more) and at least 20 trees. The ensemble gains nothing (reduction 0)

Part 2. Do it in code

bootstrap_indices(n, rng) draws n row numbers with replacement: rng.integers(0, n, size=n). The rng argument is a numpy Generator.
oob_indices(idx, n) returns the sorted row numbers that were never drawn (the out-of-bag rows).
unique_fraction(idx) is the share of distinct rows in the draw. Over many draws of a large n it approaches 1 - 1/e, about 0.632.
bag_average(preds) averages a (trees x rows) array over the trees. bag_vote(preds) takes a majority vote per row, ties going to the smaller label.

import numpy as np

def bootstrap_indices(n, rng):
    pass

def oob_indices(idx, n):
    pass

def unique_fraction(idx):
    pass

def bag_average(preds):
    # preds has shape (n_trees, n_rows)
    pass

def bag_vote(preds):
    # preds holds integer labels, shape (n_trees, n_rows)
    pass

rng = np.random.default_rng(0)
idx = bootstrap_indices(10, rng)
print(idx, unique_fraction(idx), oob_indices(idx, 10))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does averaging identical model predictions create diversity?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

G(p)=1-\sum_kp_k^2,\quad \Delta G=G_{parent}-\frac{n_L}{n}G_L-\frac{n_R}{n}G_R.

A boosted additive model has the form $F_{t+1}(x)=F_t(x)+\eta h_t(x)$ . The stage target depends on the loss and boosting method.

Worked example

A parent contains three red examples and one blue example. Its Gini is 1−0.75²−0.25²=0.375. Split into a left child with two red examples and a right child with one red and one blue. Weighted child Gini is 2/4×0 + 2/4×0.5 = 0.25, giving gain 0.125.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
gini = lambda counts: 1-sum((n/sum(counts))**2 for n in counts)
parent = gini([3,1])
children = .5*gini([2,0]) + .5*gini([1,1])
assert isclose(parent, .375)
assert isclose(children, .25)
assert isclose(parent-children, .125)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Feature importance is not causal influence. A pure training leaf need not generalize. Bagging and boosting are different training strategies, not interchangeable names for averaging.