The tree that predicts
How can a tree help you guess how many ice creams you'll sell, given the weather?
Many everyday decisions depend on something we can't know yet: how many people will turn up, how much a house will sell for, and whether an email is spam or not.
Computers can help us by looking at what happened before and making an educated guess about what comes next. A decision tree is one of the simplest ways to do that: it asks a few yes-or-no questions, one after the other, like a game of twenty questions, and the answers lead to a guess. Decision trees are indeed used quite often for both forecasting and classification problems, so what about opening them apart to understand how they work?
On this page we will build one ourselves, one question at a time, to guess how many ice creams a small stand will sell on a given day just from how warm it is. Nothing you'll see is invented: behind the scenes runs a faithful copy of LightGBM, a free library data scientists use every day to make predictions, and it will be with us at every step of the journey.
The ice cream stand
Picture a little ice cream stand that has kept a logbook for most of the year. Each row is one day: a temperature reading and how many cones it sold. There are 300 of these days in all. How do I know, given the temperature of a given day, how many cones I will sell?
As we want to know whether our tree is good at telling us that, common practice asks us to split data into two sets. Let's say 210 are used as a training set to teach the tree what the relationship between temperature and the cones sold is. The other 90 are used as a test set so we can check whether the tree can make good predictions comparable to real data that it has never seen.
Now, imagine drawing a plot in which, for each day, we put the temperature of the day on the horizontal axis and the number of cones sold that day on the vertical axis. Sales stay low on the cool days, rise fast once the temperature climbs into the low twenties, then keep climbing to well over 200 cones on the hottest days.
There's clearly a correlation among the two, but how can we guess how many cones we will sell by knowing only the temperature of that day? If we must pick only a single guess for all the days by ignoring their temperature, that would be the average of the cones sold each day, let's say around 95 cones. Let's draw that as one flat line across that picture.
That flat guess is wrong on almost every day: too high when it's cold, too low when it's hot. The gap between a guess and what a day actually sold is the miss. A trick is to square each day's miss so that a big miss counts far more than a small one, and misses in the opposite direction don't cancel out. Do this for the results for all 210 train days, and you get one number for how bad the mean guess is overall. This is the Mean Squared Error, or MSE for short:
Here it comes to a little under 3,800 cones². It is quite high, so let's try to bring that number down.
One question
The obvious next move is to stop ignoring temperature. What if the guess were allowed to depend on it through one yes-or-no question: "Is today above some threshold temperature?"
Answering it sorts the 210 train days into two groups, a split on the threshold, and each group is now its own leaf with its own average as its guess. Two leaves make two flat lines instead of one: a staircase with two steps. How far the MSE drops is the improvement of picking a threshold. The improvement of a threshold is how far the miss drops, counted once for every train day:
We add it up instead of averaging because we will soon compare questions asked in groups of very different sizes, and a question that helps 150 days should count far more than one that helps 5.
The figure below lets you place this threshold yourself and watch the two averages, the miss, and the improvement respond.
Drag the threshold past 26 °C and watch the two averages.
Press "let the machine find it" and watch the curve fill in.
Reshuffle, find the best threshold again, and read the improvement readout: it is the drop in error, counted once for every train day.
The best question is found by trying every candidate threshold, left to right.
The prediction is now a two-step staircase.
What we called improvement is commonly referred to as the gain of a split.
Keep asking
Nothing stops each leaf from asking its own question in turn.
Split the left leaf again, split the right leaf again, and the flat staircase grows another step each time: one more question, one more leaf, one more chance to fit the curve a little better. Keep going and the questions chain together into a tree: a sequence of yes-or-no splits ending in a leaf, with every train day assigned to exactly one of them.
At every step the tree is greedy: it looks at every leaf, tries every candidate question in it, and takes whichever single question improves the guess the most right now; never checking whether a different, less impressive question might have opened the door to a better pair of questions later. That's simpler to compute than looking ahead, and it's exactly what the figure below does, leaf by leaf.
Each new question can only make the guess fit the train days better, so the train error never goes up. But that says nothing about days the tree hasn't seen, which are the only days we actually care about. This is why we kept the 90 test days aside: we ask the same tree to guess them, and compute their MSE in exactly the same way. This is the test error, and it is the honest score. As the tree grows, the figure tracks both.
Press "split the best leaf" a few times and watch which leaf lights up each time.
Drag the leaves slider up past 30 and watch the train and test error curves below.
Reshuffle a few times and check whether the test-error curve still turns upward.
The tree always splits the leaf with the largest “+” number: the improvement its best candidate question would bring.
Train error only ever falls as leaves are added; it never goes back up.
Test error falls, bottoms out, then rises; the tree has stopped explaining the stand and started memorizing individual days.
The tree we just grew learned two things at once. Its first few questions captured how the stand really works: cool days sell little, hot days sell a lot. Every question after that only carved out a smaller group of train days, until a leaf held just a handful of them and its average simply repeated what they sold. The train error kept falling, but the test error turned back up: the tree had stopped learning about the stand and started memorizing its logbook.
A useful tree has to know when to stop asking, and that is where the next part begins, with four rules that tell it when and a look at the order in which it asks its questions.