ML5.1 · LESSON 1 OF 6

Partitions and leaves

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

THE IDEA

A tree is a list of yes/no questions

Imagine sorting 60 emails into spam and not spam using only questions of the form "is this number above that line?" Each question sends an example down one of two doors. Ask a few of them in sequence and you have a decision tree. Every example ends up in exactly one leaf, and the leaf holds the answer.

Geometrically each question is an axis-aligned cut: "x ≤ 4.75" draws a vertical line through the feature space, "y ≤ 3.65" a horizontal one. A tree therefore chops the plane into rectangles (a partition), and the tree and the rectangles are two views of one object. A leaf predicts from the training examples that landed in it: the most common class for classification, the mean target for regression. A tree with no cuts at all is a single leaf, which predicts one constant for every input.

Click cuts along:

Leaf at

1 leavesdepth 0train accuracy 50%test accuracy 62.5% (400 held-out points)

Each leaf box shows its predicted class and the training counts as blue | orange. The tree is the picture on the left written as questions.

The 60 training points (blue and orange, 30 each). Click inside the plot to cut the region you click in. Watch the tree on the right and the accuracy numbers change.

Where the predictions come from

With one leaf the best constant guess is the majority class, and since the classes are 30 and 30 that is a coin flip: 50% training accuracy. One cut on x already gets 73.3%. A second round of cuts (4 leaves) reaches 90% on the training points and 83% on 400 fresh points the tree never saw. Those fresh points are the honest number.

Predict first. You keep cutting until every leaf holds only one class. What happens to the training accuracy, and to the accuracy on fresh points?

The common mistake: reading a pure leaf as proof

A leaf that holds one class looks like certainty, but a leaf with a single example is just that example repeated. Training accuracy only measures how well the tree remembers; it cannot tell remembering from understanding. Depth is the knob that controls how fine the rectangles get, so a tree's depth (or minimum leaf size) is something you choose by looking at held-out data.

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

Choose an axis, then click in the plot to cut. Tasks tick from the real tree and stay ticked once earned. You can undo a cut. The test accuracy comes from 400 held-out points that are not drawn.

Click cuts along:

Leaf at

1 leavesdepth 0train accuracy 50%test accuracy 62.5% (400 held-out points)

Each leaf box shows its predicted class and the training counts as blue | orange. The tree is the picture on the left written as questions.

To do: Make the first cut: two or more leaves, and training accuracy above the 50% a single leaf gets
To do: Reach 90% training accuracy using at most 4 leaves
To do: Keep it small and honest: at most 4 leaves and at least 80% accuracy on the held-out test points
To do: Now memorise: keep cutting until every leaf is pure (100% training accuracy)
To do: Check the cost: a pure tree whose held-out accuracy is below 80%

Part 2. Do it in code

A tree is a nested dict. A leaf is {"value": v}. A split is {"feature": j, "threshold": t, "left": ..., "right": ...}. A row goes left when x[j] <= t, otherwise right.
Write leaf_value(y, kind): for kind "class" return the most common label (ties go to the smaller label), for kind "mean" return the mean of y.
Write predict_one(tree, x) that walks the tree to a leaf, then predict(tree, X) that returns a numpy array with one prediction per row.
Write count_leaves(tree) and depth(tree). A lone leaf has 1 leaf and depth 0.

import numpy as np

def leaf_value(y, kind):
    # "class": most common label, ties to the smaller label. "mean": the average.
    pass

def predict_one(tree, x):
    # follow left / right until you reach a leaf, then return its value
    pass

def predict(tree, X):
    # one prediction per row of X, as a numpy array
    pass

def count_leaves(tree):
    pass

def depth(tree):
    pass

tree = {"feature": 0, "threshold": 5.0,
        "left": {"value": 0},
        "right": {"feature": 1, "threshold": 3.0, "left": {"value": 0}, "right": {"value": 1}}}
print(predict(tree, np.array([[2.0, 9.0], [7.0, 1.0], [7.0, 8.0]])))

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

What does a one-leaf regression tree predict?

AA single constant for every input, the mean target of its training examples, because the mean minimises squared error for a constant.BThe most common feature value among its training examples, because a leaf stores a class.CNothing: a leaf with no split has no prediction until the tree is grown deeper.

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.