Teaching a tree to stop asking
A decision tree that never stops asking questions ends up memorizing its data. How do we tell it when to stop?
In the previous article in this journey, we grew a decision tree that guesses how many cones an ice cream stand sells from nothing but the day's temperature. Here is what we built along the way:
We measure how wrong a guess is with the mean squared error (MSE): the average of every day's miss, squared.
A yes-or-no question about temperature splits the days into two leaves, each guessing its own average. Its improvement, commonly called gain, is how far the total squared miss drops: , with the days in the group being split.
The tree is greedy: at every step it takes the single question with the largest improvement, in whichever leaf it is.
It learns from 210 train days and is judged on 90 test days it never sees. As it grows, train error only falls, while test error falls, bottoms out, then rises again.
The problem of the last curve rising again is what we're solving today, as a tree, when left alone, asks too many questions. Let's see how to make it stop.
Four ways to say stop
Left alone, a greedy tree will keep asking questions until every leaf holds a single day: a perfect memory of the train days and a description of nothing else. This is called overfitting. There is more than one honest way to stop this process.
Give it a budget of leaves and it stops once it has spent them, wherever they did the most good;
Refuse to let it split off a leaf with too few days in it: a question answered by three or four days isn't trustworthy, however much it seems to help;
Refuse it questions that lead to long, tangled chains: how many questions deep a leaf sits below the very first one is that leaf's depth. A tree kept shallow enough can't wander far chasing a handful of odd days;
Or refuse a question outright when the improvement it buys, added up over every day it touches, is too small to bother with.
If you notice, these four different rules are actually backed by the same suspicion: a handful of points is not enough to trust.
At the defaults, read the leaves' "days per leaf" label, then bring the "days per leaf ≥" slider down to 1. The labels are replaced by "no question left": every day in them shares the same temperature, so there is nothing left to ask.
Pull "depth ≤" down to 3 and watch the labels beside the leaves switch to "depth". Push depth back up and raise "improvement ≥" instead and watch them switch, a few at a time, to "improvement".
Slide "leaves ≤" down to 8 and up to 40 while "days per leaf ≥" stays at 30 or higher, and check the tree and the readouts don't change.
Try to land the test error near its lowest by adjusting only one control at a time: first "leaves ≤" alone, then "improvement ≥" alone, then "days per leaf ≥" alone down to 11, the one that actually gets there.
Three of the four controls (days per leaf, depth, improvement) can each be the rule named beside a leaf, depending on which you tighten; "leaves ≤" is never named beside a leaf: it just stops the tree while leaves that could still split are left unused.
At the starting shuffle, with the other three left at their defaults, only "days per leaf ≥" can improve the test error by itself.
"leaves ≤ 8" and "leaves ≤ 40" grow the same tree once "days per leaf ≥" reaches 30, because 210 train days allow only a handful of leaves that large.
Which leaf next?
Once several leaves could each be split next, which one goes first?
Every tree on this page so far has picked the leaf whose next question improves the guess the most, wherever it sits in the tree. Call that going leaf-first. An equally honest alternative is to go level-first instead: give every leaf at the current depth its question before going deeper on any of them, so the tree grows out evenly on all sides before it grows down. Which of these two orders a tree follows, given the very same budget of leaves, is its growth order, and neither one is the only reasonable answer.
Drag step back to 0, then step through both trees one split at a time and notice they agree at every step — at 8 leaves there is nothing to disagree about yet.
Drag leaves up to 16 and compare the two trees' shapes, even though both now hold 16 leaves.
At 16 leaves, compare each side's depth readout: leaf-first usually runs a question or two deeper than level-first (occasionally they tie).
Reshuffle a few times at 16 leaves and watch which side has the lower test error — it doesn't always stay the same side.
Same leaf count, different shapes: leaf-first and level-first can disagree once there are enough leaves to choose between.
Leaf-first is lopsided: it keeps digging wherever a few stray days still promise the biggest single gain, so some branches end two or three questions deeper than others.
Level-first is balanced: every branch grows to nearly the same depth before the next.
Neither order is always better on this data; whichever wins on test days changes as the stand reshuffles.
What a tree is, and isn't
Strip away our widgets and a tree is nothing more than a chain of yes-or-no questions about temperature, ending in a single number. It can only ever draw staircases, flat segments joined at the thresholds it chose, and never a smooth curve. Its guess is exactly constant across every day that lands in the same leaf, no matter how differently those days might otherwise have turned out.
A deep enough tree can memorize the train days perfectly and still be nearly useless on the test days, exactly what we watched happen in the first part.
What we have been growing across these two parts, one question at a time, is what LightGBM calls a regression tree: a tree whose leaves hold numbers, not yes/no answers or categories. On its own, a single tree is a blunt tool, but there are two honest ways to put many of them to work together. Grow many small trees, one after another, each one fixing what the last one got wrong. Or grow many big trees independently, each on its own view of the days, and average their guesses. Now, the road splits.