Answers · How models work

Why does a tree that gets every training example right do worse on new data?

In shortA tree that fits every training row has memorised individual cases rather than learned a pattern, so its accuracy on new rows falls.

A tree grown until every leaf is pure gets every training row right by storing those rows, not by learning a relationship that carries to new rows. A new row is answered by whichever training row sits in the same leaf, so accuracy on data it has never seen falls. The drop is not a bug in the tree. It is the expected cost of giving the tree enough freedom to make a separate leaf for almost every case.

What the perfect score is

The natural guess is that a model fitting every training row has learned the relationship better than a smaller tree. It has not. The training score is perfect by construction: splitting can continue until each leaf is pure, and on data with no exactly duplicated rows most leaves end up holding one row. A perfect score on the rows used to grow the tree is therefore not a measurement of quality. It is a property of the procedure. The tree has not learned a bad relationship; it has learned no relationship.

FIG 1

leaves	correct on training rows	correct on held-back rows
2	74	72
8	86	84
41	97	79
312	100	71

Read the last two rows against each other. The unlimited tree has 312 leaves for 400 rows, which is $400/312 = 1.28$ rows per leaf on average, so most leaves are records of a single case. It gets every training row right and 71 percent of held-back rows, a gap of $100 - 71 = 29$ points. The depth-one tree has 2 leaves, gets 74 percent of training rows and 72 percent of held-back rows: two points lower on training, one point higher on held back. The depth-six tree shows the same separation: 97 percent on training, 79 percent on held back, a gap of $97 - 79 = 18$ points. The perfect training score has bought nothing on new data.

Each leaf is a record of one observation, and a new case is answered by whichever training row happens to be nearest in the particular sequence of questions the tree asked. That is a lookup table with extra steps. Two rows that differ by a hair can land in different leaves and receive different predictions, so the model is unstable precisely where it looks most confident on training data. More freedom lets the tree follow accidental quirks of the training rows as well as real structure.

What limits are doing

A limit on growth is a limit on how many separate cases the tree is allowed to remember. A maximum depth caps the number of questions in a row. A minimum number of rows in a leaf says that a prediction must rest on at least that many observations. A minimum improvement refuses a split that barely cleans anything up. The minimum-rows rule is the most directly meaningful, because it is a statement about evidence rather than about the shape of the tree.

Cutting back, not stopping early

The better procedure grows the tree fully, or nearly so, and then cuts back. The reason is specific. A split can be almost worthless on its own and still be the only route to strong splits below it. An outcome that depends on a pair of inputs agreeing is the standard case: neither input alone divides the data, and splitting on either one makes the other decisive. A rule that refuses small improvements never makes the first split, so it never discovers the good ones underneath.

C_{\alpha}(T) = E(T) + \alpha |T|

Here $E(T)$ is the error on the rows the tree was grown on and $|T|$ is the number of leaves. The second term charges a price $\alpha$ per leaf, so raising $\alpha$ makes large trees cost more. Each subtree is compared with a single leaf using everything beneath it, and the least valuable subtrees are collapsed first. The order matters: children are pruned before the parent is judged, so a parent is compared against the subtree that survived, not the one it started with.

The price $\alpha$ cannot be read off the training error, because that error only rises as the tree is cut back. It is chosen on rows the tree was not grown on: try a range of prices, score each resulting tree on held-back rows, and keep the price with the best score. With a small data set the usual arrangement is to rotate the data into several parts, average the scores for each price, and then grow the final tree on all the data at the chosen price.

Where this changes

This is the behaviour of a single tree. Inside a committee of hundreds, a tree that is limited hard can be worse, because the committee averages away the instability that the limit was controlling. The other assumption is that held-back rows are like the rows the tree will meet. If they are not, pruning cannot fix the mismatch.

Worth keeping

A perfect score on training rows is a property of an unlimited tree, not evidence that it has learned a relationship.
The gap between training and held-back accuracy is the amount of memorisation.
Cutting a tree back after growing it fully can keep a weak split that is the only route to strong splits below it.

Where this goes next

This question is one step of Trees, and Committees of Them, a course that works through its subject from the beginning. The page that teaches this part of it is Knowing When to Stop Growing, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course