Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture III of IV

Lecture III · Machine Learning

Decision trees, and a model with no gradient

Lectures I and II look like two different subjects and are not. Linear regression and a neural network differ in capacity, not in kind: both hold a vector of parameters, both define a differentiable loss, and both improve by computing which way is downhill and moving that way. Both draw smooth boundaries, because a smooth function of the inputs is the only thing either one can draw. It is easy to spend a whole semester inside that family and come away believing that “learning” means following a gradient.

This lecture is the counterexample, and it is deliberately placed third rather than saved for later. A decision tree has no gradient, no learning rate, no loss to differentiate, and no notion of a small step. It is a greedy search over the data itself, and everything interesting about it follows from one question: which questions is it allowed to ask?

What the model actually is

A tree is built by recursion. At a node you hold some subset of the training points. You look at every threshold on every feature, score each candidate cut by how much purer it makes the two halves, take the best one, and recurse on each half. You stop when the node is pure, or too small, or too deep.

The model at the end is not a function you would write down as a formula. It is a partition of the feature space into boxes, one box per leaf, with a constant prediction inside each. The boundaries are always parallel to the axes, because a test of the form xj≤tx_j \le t is the only question the tree ever asks.

That is worth stating twice, because it is the whole lecture. Every node of a tree is a rectangle. The tree drawing and the partition drawing are the same object seen from two sides: descending to a node means intersecting the boxes of every ancestor, and the leaves tile the plane exactly.

Axis-alignment is not a limitation to apologise for. It is the tree’s inductive bias, the thing the model assumes about the world before it sees a single data point, and it is a different assumption from the one every model so far in this series has made. Linear regression assumed the answer was a plane. The network assumed it was smooth. The tree assumes it is piecewise constant on boxes. None of these assumptions is neutral, and no model has none.

Scoring a cut

The tree needs a number to be greedy about, and it will not be a loss in the sense of Lecture I, because there is nothing to differentiate. It is an impurity: a measurement of how mixed a set of labels is, zero when they all agree and largest when they are evenly split.

Two are standard. With two classes in proportions pp and 1−p1 - p,

G(p)=1−p2−(1−p)2=2p(1−p),H(p)=−plog⁡2p−(1−p)log⁡2(1−p).G(p) = 1 - p^2 - (1-p)^2 = 2p(1-p), \qquad H(p) = -p\log_2 p - (1-p)\log_2(1-p).

GG is Gini impurity, which reads as the probability that two points drawn from the node disagree. HH is Shannon entropy in bits, the average number of yes-or-no questions needed to pin down a label drawn from the node. Both vanish at p=0p = 0 and p=1p = 1. Both peak at p=12p = \tfrac12, where G=12G = \tfrac12 and H=1H = 1. They are different functions on different scales, which is exactly why comparing them is interesting rather than pedantic.

A candidate split sends nLn_L points left and nRn_R points right out of nn, and its score is the weighted impurity of what it produced:

Isplit=nLnI(L)+nRnI(R),gain=I(parent)−Isplit.I_{\text{split}} = \frac{n_L}{n} I(L) + \frac{n_R}{n} I(R), \qquad \text{gain} = I(\text{parent}) - I_{\text{split}}.

The gain is never negative, and the reason is worth one line of proof because it is the only theorem in this lecture. Both GG and HH are concave functions of pp. The parent’s proportion is the weighted average of the two children’s proportions, p=nLnpL+nRnpRp = \frac{n_L}{n}p_L + \frac{n_R}{n}p_R. Jensen’s inequality for a concave function says the function of the average is at least the average of the function, so

I(parent)=I ⁣(nLnpL+nRnpR)  ≥  nLnI(pL)+nRnI(pR)=Isplit.I(\text{parent}) = I\!\left(\tfrac{n_L}{n}p_L + \tfrac{n_R}{n}p_R\right) \;\ge\; \tfrac{n_L}{n}I(p_L) + \tfrac{n_R}{n}I(p_R) = I_{\text{split}} .

So splitting never makes things worse by this measurement. Notice what that does and does not promise. It says the training impurity falls monotonically, which is precisely why an unconstrained tree can drive training error to zero and why “the impurity went down” is not evidence of anything. The stopping rules are not an optimisation detail bolted on afterwards; they are the only thing standing between the algorithm and memorising the training set.

Two cuts on one node, carried to the end

The formula is short enough to look like nothing happens inside it, and the place where the two criteria come apart is not visible in decimals rounded to three places. So here is a single node with both criteria taken all the way down, in exact arithmetic.

The node holds eighty points, forty of class A and forty of class B. Its proportion is p=12p = \tfrac12, which is the worst it can be, so the parent impurities sit at their maxima: G=12G = \tfrac12 and H=1H = 1 bit. Two thresholds are on the table.

Cut P, the balanced one. Forty points go left (32 A, 8 B) and forty go right (8 A, 32 B), so both children land at p=45p = \tfrac45.

IPG=4080⋅2⋅45⋅15+4080⋅2⋅45⋅15=825,gainG=12−825=950=0.18.I_P^{G} = \tfrac{40}{80}\cdot 2\cdot\tfrac45\cdot\tfrac15 + \tfrac{40}{80}\cdot 2\cdot\tfrac45\cdot\tfrac15 = \tfrac{8}{25}, \qquad \text{gain}_G = \tfrac12 - \tfrac{8}{25} = \tfrac{9}{50} = 0.18 .

Entropy on the same child has a closed form worth knowing, because it turns a transcendental-looking quantity into one logarithm: H(45)=log⁡25−85H(\tfrac45) = \log_2 5 - \tfrac85. Both children are identical, so the weighted score is that same number and

gainH=1−(log⁡25−85)=135−log⁡25=0.278072…\text{gain}_H = 1 - \left(\log_2 5 - \tfrac85\right) = \tfrac{13}{5} - \log_2 5 = 0.278072\ldots

Cut Q, the sliver. It peels off twenty points that are all class B and leaves sixty behind (40 A, 20 B), sitting at p=23p = \tfrac23. The pure child contributes nothing under either criterion, which is the entire mechanism.

IQG=2080⋅0+6080⋅2⋅23⋅13=34⋅49=13,gainG=12−13=16=0.16‾.I_Q^{G} = \tfrac{20}{80}\cdot 0 + \tfrac{60}{80}\cdot 2\cdot\tfrac23\cdot\tfrac13 = \tfrac34\cdot\tfrac49 = \tfrac13, \qquad \text{gain}_G = \tfrac12 - \tfrac13 = \tfrac16 = 0.1\overline{6} . H(23)=log⁡23−23,gainH=1−34 ⁣(log⁡23−23)=32−34log⁡23=0.311278…H(\tfrac23) = \log_2 3 - \tfrac23, \qquad \text{gain}_H = 1 - \tfrac34\!\left(\log_2 3 - \tfrac23\right) = \tfrac32 - \tfrac34\log_2 3 = 0.311278\ldots

Now read the four numbers off. Gini prefers P, and you can settle 950>16\tfrac{9}{50} > \tfrac16 by cross-multiplying, 54>5054 > 50, with no calculator in the room. Entropy prefers Q, 0.3113>0.27810.3113 > 0.2781. The same node, the same two candidate thresholds, and the two criteria rank them in opposite orders. Any sentence of the form “Gini and entropy give the same tree” has just been falsified by eighty points and two fractions.

The checks · run against your code

# Gini's gain on cut P is exactly 9/50
assert abs(gain(gini, PARENT, P[0], P[1]) - 9.0 / 50.0) < 1e-12
# Gini's gain on cut Q is exactly 1/6
assert abs(gain(gini, PARENT, Q[0], Q[1]) - 1.0 / 6.0) < 1e-12
# entropy's gain on cut P is 13/5 - log2(5)
assert abs(gain(entropy, PARENT, P[0], P[1]) - (13.0 / 5.0 - log2(5.0))) < 1e-12
# entropy's gain on cut Q is 3/2 - (3/4) log2(3)
assert abs(gain(entropy, PARENT, Q[0], Q[1]) - (1.5 - 0.75 * log2(3.0))) < 1e-12
# Gini prefers the balanced cut P
assert gain(gini, PARENT, P[0], P[1]) > gain(gini, PARENT, Q[0], Q[1])
# entropy prefers the sliver cut Q, which is the disagreement
assert gain(entropy, PARENT, Q[0], Q[1]) > gain(entropy, PARENT, P[0], P[1])
# a pure child is worth zero under both, and neither of them raises
assert gini(0, 20) == 0.0 and entropy(0, 20) == 0.0
python runs in your browser · first run downloads ~240 kb
Plate I The two cuts, scored under both criteria and checked against their closed forms. The checks under the editor are the contract: Gini's gains are exactly 9/50 and 1/6, entropy's are exactly 13/5 minus log two of five and 3/2 minus three quarters of log two of three, and the last two assertions are the disagreement itself, stated as an inequality in each direction. The final check is the one that would fail first if the entropy guard were removed, because a pure child is where the logarithm goes to negative infinity.
Hint one

For the closed form, do not touch the definition. Rewrite the two logarithms of the fractions first: log⁡245=log⁡24−log⁡25=2−log⁡25\log_2\tfrac45 = \log_2 4 - \log_2 5 = 2 - \log_2 5, and log⁡215=−log⁡25\log_2\tfrac15 = -\log_2 5.

Hint two

Substitute both into H(p)=−plog⁡2p−(1−p)log⁡2(1−p)H(p) = -p\log_2 p - (1-p)\log_2(1-p) with p=45p = \tfrac45, then collect the two log⁡25\log_2 5 terms. Their coefficients are 45\tfrac45 and 15\tfrac15, which is the whole trick: they add to 1.

The solution

Substituting and collecting:

H(45)=−45(2−log⁡25)−15(−log⁡25)=−85+45log⁡25+15log⁡25=log⁡25−85H(\tfrac45) = -\tfrac45(2 - \log_2 5) - \tfrac15(-\log_2 5) = -\tfrac85 + \tfrac45\log_2 5 + \tfrac15\log_2 5 = \log_2 5 - \tfrac85.

Numerically 2.321928−1.6=0.7219282.321928 - 1.6 = 0.721928, which is what the workbench prints. The same move works whenever the proportion is 1/k1/k or (k−1)/k(k-1)/k: the two coefficients always sum to 1, so exactly one log⁡2k\log_2 k survives and everything else is rational. That is where H(23)=log⁡23−23H(\tfrac23) = \log_2 3 - \tfrac23 comes from, and it is why the four numbers in this section are exact rather than measured. It is also a useful sanity check on any entropy calculation you do by hand: if the answer is not a rational number plus a rational multiple of one logarithm, you have made an arithmetic slip.

The search, and what it costs

“Every threshold on every feature” sounds expensive and is not. Sort the node’s points by one feature, sweep left to right maintaining running class counts on each side, and every candidate cut is an update of two integers and one score. Thresholds only matter between consecutive distinct values, so there are at most m−1m - 1 of them per feature at a node of mm points, and the midpoint is the conventional choice.

That is O(dmlog⁡m)O(dm\log m) per node for the sorts and O(dm)O(dm) for the sweeps. Summed over a balanced tree it is O(dnlog⁡2n)O(dn\log^2 n), which is why trees were practical decades before anything else in this series was.

Dataset
Impurity
Grow
The plane, partitioned
x₁x₂

Class A Class B In a rectangle that predicts the other class

The tree
x₁ ≤ 0.31x₂ ≤ 0.56n 130G 0.393n 41G 0.497n 89G 0.295n 22G 0.000n 19G 0.000

Hover or tab to a node: it and the rectangle it owns light up together. Every node is a box.

splits 2 · leaves 3 · depth 2 · training errors 16 / 130 · single-point leaves 0 Of the 2 cuts made so far, entropy would have chosen the same one 2 times.

Class B occupies two opposite corner blocks, class A the rest. The boundary is built out of axis-aligned pieces, which is exactly what a tree draws, so five cuts reach zero training error and no further growth is possible.

Next split · node 2 · 89 samples (73 class A, 16 class B)

CriterionAt this nodeBest cutWeighted childrenDropA·B split
Gini in useG = 0.295x₂ ≤ 0.390.1650.13011·15 | 62·1
EntropyH = 0.680x₂ ≤ 0.390.3700.30911·15 | 62·1

Both criteria rank the same cut first. The numbers differ (entropy is measured in bits, Gini is not) but the ordering does not, which is what usually happens.

Plate II Growing a decision tree, one split at a time. The left panel is the plane the tree is carving; the right panel is the tree doing the carving, and the two are linked, because every node of a tree IS a rectangle: hover or tab to any node and its box lights up. Cuts thin out with depth, so the order of the recursion reads off the drawing. Below, the split the grower is about to make, scored under both impurity criteria at once, with the numbers: Gini and entropy almost always rank the same cut first, and the Criteria differ dataset is a specimen, found by search, on which they do not. Raise Max depth on the Overlap dataset to watch training error reach zero the dishonest way, by drawing rectangles around single points.

Gini against entropy, with numbers instead of an opinion

The worked pair above shows the criteria can disagree. The grower in Plate II answers the question that actually matters, which is how often they do: at every node it scores the best available split under both criteria and shows both numbers, and the tally under the panels counts how many of the cuts already taken the other criterion would have chosen too.

The answer is almost all of them. The readings differ, because they are on different scales, but the ranking usually does not, and constructing a disagreement on real data took a deliberate search over seeds. The reason it is hard is visible in the derivatives. Near a pure node, G′(p)=2−4pG'(p) = 2 - 4p approaches a finite 22, while

H′(p)=log⁡21−pp⟶∞as p→0.H'(p) = \log_2\frac{1-p}{p} \longrightarrow \infty \quad \text{as } p \to 0 .

Entropy’s slope blows up as a node approaches purity, so entropy pays more than Gini ever will for a child that is almost all one class. That is the mechanism cut Q exploited, and the Criteria differ dataset is built to exploit it in two dimensions: two overlapping clouds with a thin, nearly pure band laid along the top. Gini takes the balanced vertical cut, which buys more total impurity reduction; entropy peels off the band.

The practical summary is the one the numbers support: the choice of criterion is close to irrelevant, and the choice of stopping rule is not.

Why greedy, and not the best tree

Both criteria are answering a question nobody asked. The grower minimises impurity, one node at a time; what you wanted was the fewest errors from the finished tree. Those are different objectives, and there is no reason in principle for the first move of the second to be the winner of the first.

The reason nobody fixes this is a complexity result. Hyafil and Rivest proved in 1976 that constructing an optimal binary decision tree is NP-complete, so short of P equalling NP there is no algorithm that finds the best tree in polynomial time. Greed is not a shortcut somebody took because they were in a hurry. It is the thing you do instead.

The plate below runs both. You choose the root cut; it then finishes the tree optimally underneath you by enumerating every cut in each child, and scores the result in training errors against two reference points: the root the greedy rule takes, and the root that is actually best.

Specimen
Jump to
Your root, finished optimally
x₁x₂

Class A Class B In a rectangle that predicts the other class

The tree
x₁ ≤ 0.13x₂ ≤ 0.50x₂ ≤ 0.50n 64G 0.500n 8G 0.500n 56G 0.500n 4G 0.000n 4G 0.000n 28G 0.490n 28G 0.490

Hover or tab to a node: it and the rectangle it owns light up together.

RootThe cutThen, optimallyErrors
Yoursx₁ ≤ 0.13x₂ ≤ 0.50 · x₂ ≤ 0.5024 / 6424 more errors than the optimum
Greedyno cut, one leafnothing below it32 / 64greed costs 32 errors
Best possiblex₁ ≤ 0.50x₂ ≤ 0.50 · x₂ ≤ 0.500 / 64exhaustive over every depth-2 tree

Greed scored 14 candidate cuts to build its tree. The exhaustive search examined 1,639 trees to be sure of the answer, and that ratio is the whole argument.

Sixty-four points on an 8 by 8 lattice, labelled by quadrant parity. Every row and every column is exactly half of each class, so every candidate cut has gain exactly zero and the greedy rule declines to split at all. Two cuts, chosen together rather than one after the other, separate the classes perfectly.

All three specimens, depth two, scored in training errors

Specimen Points Greedy errors Best possible Cuts greed scored Trees enumerated
XOR lattice 64 32 0 14 1,639
Blocks 130 12 2 498 2,638,991
Overlap 140 17 14 554 3,580,919
Plate III Greed against exhaustion, scored in training errors. Nothing here can be failed: a worse root is still a measurement, and the figure exists to price the choice rather than mark it. On the XOR lattice, sixty-four points labelled by quadrant parity, every row and every column holds exactly half of each class, so all fourteen candidate cuts have gain of exactly zero, greed declines to split, and thirty-two points stay wrong; two cuts chosen together are perfect. On Blocks the failure is quieter and more typical: greed lands twelve errors where two are available. The table underneath is the whole comparison for all three specimens, and it is the figure with JavaScript off.

The XOR lattice is the pathological case and it is worth being precise about why it is pathological. It is not that the gains are small. They are exactly zero, in floating point and not merely in the limit, because every full row and every full column of the lattice holds four points of each class, so any axis-aligned cut hands both children the parent’s own proportions. A grower that requires a positive gain therefore stops at the root and predicts one class for everything, getting 32 of 64 wrong. Two cuts, chosen together rather than one after the other, get all 64 right.

Blocks is the more honest specimen because nothing about it is contrived: greed reaches 12 errors on 130 points where 2 are available at the same depth. And the price of knowing that is the last two columns of the table. Greed scored 498 candidate cuts across the three nodes it built. The exhaustive search examined 2,638,991 trees. Go one level deeper and the same enumeration over the same thresholds is 12,216,147,304,645 trees, which is the shape of the complexity result rather than a large constant.

When exhaustive search does win, and it does: when the data is small, the depth budget is tiny, and the tree has to be defended rather than merely deployed. Modern optimal-tree solvers (Bertsimas and Dunn’s mixed-integer formulation in 2017, DL8.5 in 2020, GOSDT in the same year) reach depth three to five on tens of thousands of rows by pairing branch and bound with aggressive caching of subproblems, and they are used where somebody is going to read the tree out loud: sentencing risk, clinical triage, credit adjudication. In that setting two extra points of accuracy matter less than a model whose every branch you can defend, and a certificate of optimality is worth paying for because it removes the question of whether a better tree of that size existed.

One caveat, and it is not a small one. The optimum this plate finds is optimal on the training set. Two errors instead of twelve on 130 points may be a better model or may be a better memoriser, and nothing in the search knows the difference. Everything the next two sections say about overfitting applies to the optimal tree at least as much as to the greedy one.

The checks · run against your code

# every candidate cut at the root has gain of exactly zero, not merely nearly
assert max(abs(gain(GRID, c)) for c in cuts(GRID)) == 0.0
# so a greedy grower stops at the root with half the lattice wrong
assert errors(GRID) == 32
# two cuts chosen TOGETHER separate the classes perfectly
assert best == 0
# and being sure of that meant looking at 1,639 trees
assert trees == 1639
python runs in your browser · first run downloads ~240 kb
Plate IV The lattice in code, and the enumeration that beats greed on it. The first block prints the largest gain available at the root, which is 0.0 exactly, and the count of points a non-splitting tree gets wrong. The second enumerates every depth-two tree over the same fourteen thresholds and finds a perfect one. The checks assert all four figures the prose quotes, including the exact zero, which is the assertion that would break first if the lattice were jittered.

The bias, seen where it fails

An inductive bias is invisible when it is right. Turn Plate II to the Diagonal dataset, a single straight boundary at forty-five degrees, and watch it become visible. That problem is trivial for logistic regression: two weights and a bias, one line, exact. The tree cannot draw the line at all. It approximates it with a staircase whose treads land wherever the training points happen to fall, and refining the approximation costs one more split per step.

The question worth asking is how much that costs, in numbers, and the answer is sharper than “it is worse”.

The construction. Take the boundary x2=x1x_2 = x_1 on the unit square and cut the square in half both ways. Two of the four quadrants are now pure, and the other two are half-scale copies of the original problem. Recurse. After gg generations, and therefore at depth 2g2g, there are 2g2^g unresolved cells of side 2−g2^{-g}, each of which is exactly half wrong, so the misclassified area is

ε(2g)=2g⋅(2−g)22=2−g2,leaves=3⋅2g−2.\varepsilon(2g) = 2^{g}\cdot\frac{(2^{-g})^2}{2} = \frac{2^{-g}}{2}, \qquad \text{leaves} = 3\cdot 2^{g} - 2 .

Error halves for every two levels of depth. To get below one per cent you need g=6g = 6: depth 12, 190 leaves, and 0.78 per cent of the plane still wrong. The line that does the job exactly has three numbers in it.

The bound. That construction is not merely one option among many. Any partition of the square into LL axis-aligned rectangles, however chosen, misclassifies at least 12L\tfrac{1}{2L} of it against this boundary, so one per cent requires at least fifty leaves no matter how cleverly they are placed. The proof is three lines and it is in the hints. The construction above reaches 0.78 per cent with 190 leaves, and the floor at that error is 64, so it is within a factor of three of optimal and the shape of the answer, leaves growing like 1/ε1/\varepsilon, is not negotiable.

And what the actual grower does, which is worse than both, because it has to find its thresholds from a finite sample rather than being handed them.

x₁x₂

Class A Class B The true boundary

angle 45° · leaves 22 · training errors 4 / 600 · area wrong 3.54%No arrangement of 22 rectangles beats 2.27% at this angle, and a straight line reaches 0.00% with three numbers.

Training error counts points and stops at zero. Area error measures the square itself, on a 160 by 160 grid, and does not. The gap between them is the wedges the staircase leaves along the boundary, where the tree is confident and wrong and no training point ever lands to say so.

Area wrong, per cent of the square · 600 points, seed 7

Depth 0°15°30°45° Leaves at 45° Floor for that many
2 0.006.7516.6314.42 4 12.50
4 0.002.484.895.63 15 3.33
6 0.001.703.303.59 26 1.92
8 0.001.703.303.62 27 1.85
10 0.001.703.303.62 27 1.85
12 0.001.703.303.62 27 1.85
A line 0.000.000.000.00 3 numbers 0.00
Plate V The price of an axis-aligned bias, measured in area rather than asserted in words. Six hundred points, seed 7, in fixed positions: moving the angle slider re-labels the same points rather than redrawing them, so everything that changes is caused by the boundary and by nothing else. Two numbers disagree on purpose. Training error counts points and can be driven to zero; area error measures the square itself, on a 160 by 160 grid, and cannot. At 0 degrees one cut is exact. At 45 degrees the training error reaches zero at depth 7 with 27 leaves while 3.62 per cent of the plane stays wrong, and the last two levels of growth make that number slightly worse rather than better. The tree is scored against the floor rather than against another tree: no arrangement of that many rectangles beats tan(angle) over twice the leaf count, which is a theorem and not a measurement. The table is the reference figure with JavaScript off, and its last row is the straight line.

Read the ladder at forty-five degrees and the two columns part company at depth five. There the tree has 22 leaves, 4 training errors left, and 3.54 per cent of the plane wrong. Grow to depth seven and the training error reaches zero at 27 leaves, while the area wrong rises to 3.62 per cent. The last four training points were bought with two extra levels and paid for in true error. Nothing after that changes anything: depth 8, 10 and 12 give the identical tree, because the grower has run out of training points to distinguish, not out of permission to split.

The last column of the table is the honest comparison, and it separates two complaints that are easy to run together. At depth five the floor for 22 rectangles is 2.27 per cent, and the tree scores 3.54, so greed and the finite sample together cost a factor of about 1.6. The remaining 2.27 per cent is not greed’s fault at all. It is the bias: no arrangement of 22 axis-aligned boxes does better, however it is found, which is why the fix for this problem is a different question and not a better search.

Zero training error and a boundary that is wrong along its whole length is the cleanest picture in this series of what a bias costs when it does not match the problem. And it generalises in the encouraging direction too. Rotate the same data by forty-five degrees and the tree solves it with a single cut, 0.00 per cent. The data did not get easier; it got aligned with the questions the model is able to ask.

Hint one

Only the rectangles the boundary actually passes through can be wrong, so let m≤Lm \le L be that number, and let eie_i be the horizontal extent of the boundary segment lying inside rectangle ii. Those extents tile the boundary’s shadow on the xx axis, so ∑iei=1\sum_i e_i = 1.

Hint two

A rectangle is a box, and it contains the whole bounding box of any segment whose endpoints it contains. For a segment at forty-five degrees of extent eie_i that bounding box is a square of side eie_i, cut into two right triangles by the boundary. So whichever single label the rectangle is given, at least one of those triangles is wrong.

Hint three

You now need a lower bound on ∑iei2\sum_i e_i^2 given ∑iei=1\sum_i e_i = 1 over mm terms. Cauchy-Schwarz does it in one step, and so does convexity of t↦t2t \mapsto t^2.

The solution

Each crossed rectangle costs at least ei2/2e_i^2/2 in area, so the total misclassified area is at least 12∑i=1mei2\tfrac12\sum_{i=1}^{m} e_i^2. By Cauchy-Schwarz, (∑iei)2≤m∑iei2\left(\sum_i e_i\right)^2 \le m \sum_i e_i^2, and the left side is 1, so ∑iei2≥1/m\sum_i e_i^2 \ge 1/m. Therefore the error is at least 12m≥12L\tfrac{1}{2m} \ge \tfrac{1}{2L}, with equality only when every crossed rectangle has the same extent, which is exactly the even staircase.

Invert it: reaching error ε\varepsilon needs L≥1/(2ε)L \ge 1/(2\varepsilon) leaves, so 1 per cent needs 50 and 0.1 per cent needs 500. Leaves grow like 1/ε1/\varepsilon and depth therefore like log⁡2(1/ε)\log_2(1/\varepsilon), which is the best case and assumes the tree is perfectly balanced. The recursive construction in the text spends 190 leaves to reach 0.78 per cent where the floor at that error is 64, so it is within a factor of three of the bound and the exponent is right. Compare the honest alternative: a linear model reaches error zero with three parameters and no dependence on ε\varepsilon at all, because it is allowed to ask a question the tree is not.

The argument survives being tilted. For a boundary at θ\theta degrees from vertical the segment inside a crossed rectangle has a bounding box of ℓisin⁡θ\ell_i\sin\theta by ℓicos⁡θ\ell_i\cos\theta, the lengths ℓi\ell_i sum to 1/cos⁡θ1/\cos\theta, and the same application of Cauchy-Schwarz gives a floor of tan⁡θ/(2L)\tan\theta / (2L). At θ=45°\theta = 45° that is the bound above; at θ=0\theta = 0 it is zero, which is right, because one cut is exact. That expression is what the last column of Plate V reports, and it is a theorem rather than a second measurement, which is the only reason it is allowed to sit beside the first one.

What entropy does at zero, and why the grower carries a tolerance

Two places in this algorithm are arithmetic rather than mathematics, and both of them are one line in src/lib/dtree.ts.

The first is p=0p = 0. The entropy of a pure node is a product of zero and negative infinity, which is not a number. The definition wants 0log⁡20=00\log_2 0 = 0, and it is entitled to it: lim⁡p→0+plog⁡2p=0\lim_{p\to 0^+} p\log_2 p = 0, so the extension is continuous and not a fudge. But the machine does not take limits. In JavaScript Math.log2(0) is -Infinity and -0 * -Infinity is NaN; in Python math.log2(0.0) does not even return, it raises ValueError: math domain error. So entropy in dtree.ts guards the endpoints explicitly and returns 0 there, and the listing further down does the same thing in a different spelling, with if p > 0.0 filtering the generator.

The consequence of getting this wrong is worse than a crash, which is why it is worth a paragraph. A NaN does not propagate loudly; it propagates as a comparison that is always false. bestSplit keeps a candidate only when gain > best.gain + 1e-12, and every comparison against NaN is false, so a poisoned candidate does not raise an error and does not win. It silently makes the search return whatever it happened to be holding, which is a wrong tree that looks exactly like a right one. A pure child is the single most common thing a grower produces. It would happen on the first dataset anybody tried.

The second is the 10−1210^{-12} in growOne. Jensen’s inequality above proves the gain is never negative, and the proof is correct, and floating point does not care. Take a node of 21 points, 6 of class A and 15 of class B, and cut it into 7 points (2 A, 5 B) and 14 points (4 A, 10 B). Both children have exactly the parent’s proportions, so the true gain is exactly zero. The computed Gini gain is

0.40816326530612246−0.4081632653061224=5.551115123125783×10−17,0.40816326530612246 - 0.4081632653061224 = 5.551115123125783\times 10^{-17},

which is one unit in the last place, and it is positive. Entropy on the same cut happens to give exactly zero, which is luck and not a property. A grower testing gain > 0 would accept that cut, spend a level of depth, and produce two children that are statistically identical to their parent and to each other. Do that a few times and you have a tree with a fringe of nodes that separate nothing, all of them justified by arithmetic dust. The tolerance is not defensive programming; it is the difference between a tree and a tree with noise in it.

Where overfitting stops being a word

The controls that matter are Max depth and Min samples to split, and the Overlap dataset is where they earn their keep. Its two classes genuinely intersect: they are drawn from two Gaussians whose clouds interpenetrate, so no partition of any kind separates them, and the best achievable error is not zero.

Push the depth limit to ten and drop the minimum samples to two, and the tree reaches zero training error anyway. It does it by drawing rectangles around individual points, and the plate counts them for you: twenty leaves for a hundred and forty points, six of them holding exactly one. Nothing in the growing procedure knows this is worthless. Every one of those splits reduced impurity, which the theorem above guarantees, and each was the best available cut, and the result is a model that has memorised noise and will pass it on as confident prediction.

That picture is the entire argument for the three standard responses.

  • Depth and size limits, which stop the recursion before it can isolate single points. Cheap and blunt.
  • Pruning, which grows the tree fully and then collapses back any subtree whose complexity is not paid for by a held-out set. Better, because the decision is made with evidence the grower did not have.
  • Ensembles, which grow many deliberately decorrelated trees and average their votes. Each tree overfits in its own direction and the errors partly cancel. That is what a random forest is, and it is the reason trees remain the default for tabular data long after neural networks took the rest of the field.

Notice that none of the three is a change to the splitting rule. The greedy search is fine. What needed fixing was knowing when to stop.

The whole learner, in code

No framework, and no calculus anywhere in it.

from math import log2

def impurity(counts, crit="gini"):
    n = counts[0] + counts[1]
    if n == 0:
        return 0.0
    ps = [c / n for c in counts]
    if crit == "gini":
        return 1.0 - sum(p * p for p in ps)
    return -sum(p * log2(p) for p in ps if p > 0.0)

def best_split(points, crit="gini", min_leaf=1):
    # points is a list of ((x0, x1), label). One sort per feature, then a
    # left-to-right sweep that keeps the class counts on each side.
    n = len(points)
    total = [0, 0]
    for _, y in points:
        total[y] += 1
    parent = impurity(total, crit)
    best = (0.0, None, None)                    # gain, feature, threshold
    for f in range(2):
        order = sorted(points, key=lambda p: p[0][f])
        left, right = [0, 0], list(total)
        for i in range(n - 1):
            left[order[i][1]] += 1
            right[order[i][1]] -= 1
            if order[i][0][f] == order[i + 1][0][f]:
                continue                        # equal values: no cut between them
            nl, nr = left[0] + left[1], right[0] + right[1]
            if nl < min_leaf or nr < min_leaf:
                continue
            gain = parent - (nl * impurity(left, crit)
                             + nr * impurity(right, crit)) / n
            if gain > best[0]:
                thr = (order[i][0][f] + order[i + 1][0][f]) / 2.0
                best = (gain, f, thr)
    return best

def build(points, depth=0, max_depth=4, min_split=4, crit="gini"):
    counts = [0, 0]
    for _, y in points:
        counts[y] += 1
    leaf = {"leaf": True, "predict": 0 if counts[0] >= counts[1] else 1,
            "n": len(points)}
    if depth >= max_depth or len(points) < min_split or 0 in counts:
        return leaf                             # too deep, too small, or pure
    gain, f, thr = best_split(points, crit)
    if f is None or gain <= 1e-12:
        return leaf                             # see the tolerance, above
    return {"leaf": False, "feature": f, "threshold": thr, "gain": gain,
            "left": build([p for p in points if p[0][f] <= thr],
                          depth + 1, max_depth, min_split, crit),
            "right": build([p for p in points if p[0][f] > thr],
                           depth + 1, max_depth, min_split, crit)}

def predict(node, x):
    while not node["leaf"]:
        node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]
    return node["predict"]

Sixty lines, four of which are the model. Compare that with Lecture II, where the four lines that mattered were a chain rule and everything else was bookkeeping about shapes. Here there are no shapes, no learning rate, no initialisation, and no run-to-run variation at all: given the same data and the same criterion, build returns the same tree every time. That determinism is genuinely unusual in this series, and it is the reason the ensemble methods have to inject randomness deliberately in order to have anything to average.

The same object, from the other course

Look at predict again. It walks down from the root, compares one number against one threshold at each node, and goes left or right. That is the binary search tree of Data Structures Lecture XI, with thresholds where the keys would be, and prediction is a search that returns the leaf rather than a match. The cost analysis transfers whole: a query is O(depth)O(\text{depth}), and depth between log⁡2L\log_2 L and LL for LL leaves is the same spread that separates a balanced BST from a linked list.

The differences are the interesting part, and there are exactly two.

A BST’s shape is chosen for balance; a tree’s shape is chosen by the data. That is why DSA XI spends its length on rotations and AVL invariants and this lecture spends none: nobody wants a balanced decision tree. A balanced tree with LL leaves is one that split every region evenly, and if the data called for that it would be a coincidence. Depth here is a hyperparameter you tune against a held-out set, not an invariant you restore after every insertion.

And there is no rotation. A BST rotation preserves the key set and every lookup, which is precisely what makes rebalancing safe. Swapping two tests along a path in a decision tree does not preserve the partition, because the sibling subtree that hung off the upper test was fitted to a region that no longer exists. The move that looks like it should work quietly changes the function. That is why the repair kit for a decision tree is pruning and regrowing rather than rebalancing: a tree that is the wrong shape is not a tree with a broken invariant, it is a tree fitted to the wrong regions.

What comes next

Two threads leave here. The first is ensembles, where the fix for a high-variance learner is to build many of them badly on purpose and average: bagging, random feature subsets, then boosting, where each tree is fitted to the previous ensemble’s residuals and the gradient quietly comes back, this time taken with respect to the predictions rather than to any parameter.

The second is the one Lecture IV takes. Everything in this series so far, including the tree, has had an answer key: a yy to be right or wrong about. Take the labels away and “better” has to come from somewhere else, and where it comes from turns out to change the answer.

Problems

Work these in order. The last one runs its own checks; make every row green.

  1. On paper, the criterion that does not work. Define the misclassification impurity M(p)=min⁡(p,1−p)M(p) = \min(p, 1-p), which looks like the honest choice because it is the thing you are actually trying to minimise. Take a node of 800 points, 400 of each class, and score two cuts: cut A sending (300 A, 100 B) left and (100 A, 300 B) right, and cut B sending (200 A, 400 B) left and (200 A, 0 B) right. Show that MM gives both cuts a gain of exactly 14\tfrac14 and so cannot choose between them, while Gini gives 18\tfrac18 and 16\tfrac16 and prefers B. Then say, in one sentence, what property of MM produces the tie, and why concavity alone was not enough to make it a usable criterion.

  2. On paper, the exact arithmetic again. Repeat the worked pair from this lecture for a node of 90 points, 45 of each class, against a cut that sends (30 A, 15 B) left and (15 A, 30 B) right, and a second cut that sends (0 A, 15 B) left and (45 A, 30 B) right. Give all four gains as exact quantities, using the log⁡2\log_2 closed forms rather than decimals, and then say which criterion prefers which cut. Finally, state what changed relative to the eighty-point example and why the answer moved.

  3. On paper, the staircase budget. Using ε(2g)=2−g/2\varepsilon(2g) = 2^{-g}/2 and L=3⋅2g−2L = 3\cdot 2^{g} - 2 from the failure section, find the smallest depth reaching 0.1 per cent area error on the forty-five degree boundary, and the leaf count it costs. Then compare that leaf count against the L≥1/(2ε)L \ge 1/(2\varepsilon) floor and report the ratio. Finally, redo both for a boundary in three dimensions, a plane at forty-five degrees to all three axes, and say what happens to the exponent.

  4. On paper, the price of certainty. Let TT be the number of candidate thresholds available at a node and suppose, generously, that every node has all TT of them. Write down the number of distinct trees of depth at most DD as a recurrence N(D)N(D), and the number of cuts a greedy grower scores to build one tree of depth DD. Evaluate both at T=249T = 249 for D=2D = 2 and D=3D = 3, and check the first against the 2,638,991 the plate reports for Blocks. Your recurrence will overshoot; say precisely which assumption causes that, and in which direction the error goes.

  5. On paper, the ties. bestSplit in dtree.ts breaks ties by taking the lower feature index and then the lower threshold, and best_split in the listing does the same by scanning in that order and requiring a strict improvement. Construct a dataset of six points on which two different features offer cuts of identical gain, and say what the tree looks like under each tie-break. Then answer the question that makes this more than bookkeeping: what would go wrong in the figure on this page if the tie-break depended on the order the points arrived in?

  6. On paper, the ensemble’s first step. A random forest grows each tree on a bootstrap resample of nn points drawn with replacement. Show that the probability a given training point is left out of a given tree’s sample tends to 1/e1/e as nn grows, and evaluate it at n=140n = 140. Then explain what the roughly 37 per cent of points left out are used for, and why that estimate needs no separate validation split.

  7. Write the split search. Implement best_split(points, crit) with one sort per feature and a single sweep, matching the slow reference exactly, including its tie-break. The reference is provided, so the checks compare your answer against a computation rather than against a stored constant: they run on separable data, on overlapping data, under both criteria, on a node whose feature values are all identical, and they confirm that the gain you report is never negative. This is the four lines the whole lecture is about.

    The checks · run against your code

    # it matches the reference on separable data, under Gini
    assert same(best_split(SEP, "gini"), reference_split(SEP, "gini"))
    # and on overlapping data, under Gini
    assert same(best_split(MIX, "gini"), reference_split(MIX, "gini"))
    # and under entropy, where the ranking need not be the same
    assert same(best_split(MIX, "entropy"), reference_split(MIX, "entropy"))
    # a node whose feature values are all identical admits no cut at all
    assert best_split(FLAT, "gini")[1] is None
    # the gain it reports is never negative, on any of the three
    assert min(best_split(d, "gini")[0] for d in (SEP, MIX, FLAT)) >= 0.0
    python runs in your browser · first run downloads ~240 kb
    Plate VI The split search, checked against a slow reference rather than against a stored answer. Both functions are in front of the reader, so a passing check means the fast version agrees with the obviously correct one on every dataset in the cell, including the degenerate one where every feature value is identical and there is no threshold to place. The reference recounts from scratch at every candidate and is quadratic; yours is one sort and one sweep, and the agreement is the point.
    Hint one

    Sort a copy of the points by the feature you are working on. Keep two count pairs, left starting at [0, 0] and right starting as a copy of the totals, and move one point across per step. The whole sweep needs no re-counting at all, which is the entire saving.

    Hint two

    The trap is duplicate values. After moving point i across, a threshold between it and point i + 1 only exists if their values on this feature differ. Skip the candidate when they are equal, but move the point across first, or your counts will be wrong for the next candidate.

    Hint three

    For the tie-break, use a strict > against the best gain so far and scan feature 0 before feature 1, in increasing threshold order. The reference uses > best[0] + 1e-12; the difference is only visible on exact ties, and same() compares with a tolerance, so either works here. Use the midpoint of the two straddling values as the threshold.

    The solution

    One sort per feature, one sweep, no recounting:

    def best_split(points, crit="gini"):
      n = len(points)
      total = [0, 0]
      for _, y in points:
          total[y] += 1
      parent = impurity(total, crit)
      best = (0.0, None, None)
      for f in (0, 1):
          order = sorted(points, key=lambda p: p[0][f])
          left, right = [0, 0], list(total)
          for i in range(n - 1):
              left[order[i][1]] += 1
              right[order[i][1]] -= 1
              a, b = order[i][0][f], order[i + 1][0][f]
              if a == b:
                  continue
              nl, nr = left[0] + left[1], right[0] + right[1]
              g = parent - (nl * impurity(left, crit)
                            + nr * impurity(right, crit)) / n
              if g > best[0] + 1e-12:
                  best = (g, f, (a + b) / 2.0)
      return best

    Fourteen lines. The reference recomputes both children’s counts at every candidate, which is O(m)O(m) per candidate and O(m2)O(m^2) per feature; this version does one sort and then pays two integer updates per candidate. On the ten-point datasets in the cell the difference is invisible, which is exactly why the check compares answers rather than timings. The continue on equal values is the line most people leave out, and leaving it out does not raise: it proposes a threshold that separates two identical points, which the partition cannot honour, so the reported gain and the tree you actually get stop agreeing. On the FLAT dataset, where every value is identical, that bug is the whole difference between returning None and confidently returning a cut that does not exist.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.