ML5.3 · LESSON 3 OF 6

Split gain

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

THE IDEA

A split is judged by what it removes

The gain of a split is how much impurity it removes: the parent's impurity minus the size-weighted average of its children's impurities. A positive gain means the children are, on average, purer than the parent. A tree is grown greedily: at each node try every feature and every threshold, keep the one with the biggest gain, then repeat inside each child.

Step 1 of 4

The parent. 3 red, 1 blue. Gini = 1 - 0.75² - 0.25² = 0.375

Scanning every threshold

For one numeric feature, only the order of the values matters, so the candidate cuts are the midpoints between neighbouring distinct values in sorted order. Cutting exactly on an existing value changes nothing that a midpoint does not, and cutting outside the data would leave one side empty. The picture below scans all 41 candidates for feature x of the 60 training points. Click bars to inspect them.

Feature Criterion unweighted average (the mistake)

41 candidates

Click a bar, or use Next threshold, to see the arithmetic for one candidate.

best: x ≤ 4.75, gain 0.1225

Top: the points along the chosen feature. Bars: the gain of cutting at that threshold. The green bar is the best one.

On x the best cut is x ≤ 4.75 with gain 0.1225; on y the best is y ≤ 3.65 with gain 0.1134. So the tree would cut x first. Notice how many cuts have almost the same gain: with noisy labels the best split is often only slightly better than its neighbours.

Predict first. The best cut on x sends 20 points left and 40 right. Its left child holds 17 blue and 3 orange. Which child has the higher Gini?

The common mistake: forgetting the weights

Averaging the two child impurities without weights treats a child with 6 examples the same as a child with 54. Tick the unweighted box above: the winner jumps to x ≤ 1.6, which isolates just 6 points. Its "gain" looks like 0.2531, but the honest weighted gain is only 0.0556, far below the real best of 0.1225. Weighting makes each child count in proportion to how many examples it receives.

Weight each child by n_child / n_parent.

Don't

Average the child impurities as if the children were the same size.

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

The best bar is not marked until you have picked it. Click bars or use the next and previous buttons, and read the arithmetic panel to compare candidates.

Feature Criterion unweighted average (the mistake)

41 candidates

Click a bar, or use Next threshold, to see the arithmetic for one candidate.

To do: On feature x with Gini, select the threshold with the largest weighted gain
To do: Do the same on feature y. Which feature has the better best split?
To do: Switch the criterion to entropy and select its best threshold on x
To do: Turn on the unweighted average and select the threshold that wins under that mistaken rule. It is not the real winner

Part 2. Do it in code

gini(y) is given. Write split_gain(y, y_left, y_right) = gini(parent) minus the size-weighted average of the two children's gini. An empty child contributes nothing.
Write best_split(x, y): try the midpoint between every pair of neighbouring distinct sorted values of x as a threshold (left is x <= t). Return (threshold, gain) for the largest gain.
Ties go to the smallest threshold. If no threshold has a gain above 1e-12 (constant feature, pure node), return (None, 0.0).

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)
    p = c / y.size
    return float(1.0 - np.sum(p ** 2))

def split_gain(y, y_left, y_right):
    # parent impurity minus the weighted child impurities
    pass

def best_split(x, y):
    # scan every midpoint threshold, return (threshold, gain) or (None, 0.0)
    pass

x = [1, 2, 3, 4, 5, 6]
y = [0, 0, 0, 1, 1, 1]
print(best_split(x, y))

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Why weight child scores by sample count?

ASo the parent impurity cancels exactly and only the child terms remain.BSo each child counts in proportion to how many examples it receives, which stops a tiny pure child from looking like a great split.CBecause larger children always have lower impurity, so weighting corrects for that bias.

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.