ML5.5 · LESSON 5 OF 6

Random forests

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

THE IDEA

Bagging is not enough when the trees look alike

Averaging T models with variance σ² and pairwise correlation ρ leaves a variance of about ρσ² + (1 − ρ)σ²/T. Adding trees shrinks only the second term. If the trees are strongly correlated, the first term stays. Bagged trees are correlated because one or two strong features dominate every tree's first cuts, whatever the resample.

A random forest adds one more source of randomness: at every split, the tree may look at only a random subset of the features. Strong features are sometimes unavailable, so other features get used, the trees become different, and averaging has more to cancel.

Watch it decorrelate

This data has six features. f0 and f1 are near-copies of the strongest signal, f2 is a second signal, f3 to f5 are pure noise. 150 training rows, 400 held-out rows, trees of depth up to 6. Features per split = 6 is plain bagging. Look at the bar chart of root features and at the correlation.

Features per split 6 Trees 1

OOB error 39% (on 59 of 150 points)held-out error 34.3%mean tree correlation needs 2 trees

Which feature each tree puts at its root (first 1 trees). f0 and f1 are near-copies of the strongest signal; f2 is a second signal; f3 to f5 are noise.

Slide features-per-split from 6 down to 1. The purple curve is the out-of-bag error: each training row is scored only by trees whose bootstrap sample missed it, so it needs no separate test set.

With all six features, 80 of 100 trees start with f1 and 17 with f0: nearly every tree makes the same first cut, and the mean correlation between trees is 0.392. With one feature per split it falls to 0.298, and the held-out error is 24.5% against 27.5% for plain bagging. These are numbers for this one dataset: the best setting depends on the data.

Predict first. You keep adding trees to a forest, from 10 to 100 to 1000. What do you expect from the error?

The common mistake

Two beliefs to avoid. More trees fix everything: they do not remove the correlated part of the error. Fewer features per split is always better: with too few, each tree is weak because it is forced to split on noise. The number of features per split is a setting you tune, and the out-of-bag error is a cheap way to do it.

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

Move the two sliders. The first run of a new features-per-split value takes a moment because 100 trees are grown.

Features per split 6 Trees 1

OOB error 39% (on 59 of 150 points)held-out error 34.3%mean tree correlation needs 2 trees

Which feature each tree puts at its root (first 1 trees). f0 and f1 are near-copies of the strongest signal; f2 is a second signal; f3 to f5 are noise.

To do: Grow at least 60 trees and get the out-of-bag error to 32% or lower
To do: Find a features-per-split value that drives the average correlation between trees below 0.34 (use at least 30 trees)
To do: With at least 60 trees, find a setting that beats plain bagging (all 6 features at every split) on held-out error

Part 2. Do it in code

gini, best_split (from ML5.3) and majority are given. Write grow(X, y, max_depth, max_features=None, rng=None, depth=0) that returns a nested-dict tree in the ML5.1 format.
Make a leaf {"value": majority label} when depth == max_depth, the node is pure, it has fewer than 2 rows, or none of the considered features has a split with gain above 0.
At each split consider all features, or if max_features is set, a random subset of that size drawn without replacement with rng.choice. Take the largest gain; ties go to the lowest feature index. Left is X[:, j] <= threshold.
Write predict_tree(tree, x) and forest_predict(trees, X), a majority vote over the trees (ties to the smaller label).

import numpy as np

def gini(y):
    y = np.asarray(y)
    if y.size == 0:
        return 0.0
    _, c = np.unique(y, return_counts=True)
    return float(1.0 - np.sum((c / y.size) ** 2))

def best_split(x, y):
    x = np.asarray(x, dtype=float); y = np.asarray(y)
    order = np.argsort(x, kind="stable"); xs, ys = x[order], y[order]
    best_t, best_g = None, 1e-12
    for i in range(len(xs) - 1):
        if xs[i] == xs[i + 1]:
            continue
        w = (i + 1) / len(ys) * gini(ys[: i + 1]) + (len(ys) - i - 1) / len(ys) * gini(ys[i + 1 :])
        g = gini(ys) - w
        if g > best_g + 1e-12 or (best_t is None and g > best_g):
            best_t, best_g = float((xs[i] + xs[i + 1]) / 2), g
    return (best_t, best_g) if best_t is not None else (None, 0.0)

def majority(y):
    labels, counts = np.unique(y, return_counts=True)
    return labels[int(np.argmax(counts))]

def grow(X, y, max_depth, max_features=None, rng=None, depth=0):
    # return {"value": ...} or {"feature": j, "threshold": t, "left": ..., "right": ...}
    pass

def predict_tree(tree, x):
    pass

def forest_predict(trees, X):
    # majority vote of every tree, one label per row
    pass

X = np.array([[1.0, 5.0], [2.0, 4.0], [3.0, 6.0], [4.0, 5.0]])
y = np.array([0, 0, 1, 1])
print(grow(X, y, 2))

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Why consider a subset of features at a split?

AIt makes the trees differ, because they cannot all pick the same dominant feature, so their errors are less correlated and averaging removes more of them.BIt speeds up training only; the trees stay just as correlated as before.CIt removes the noise features so each tree sees only the useful inputs.

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.