How to build a decision tree regressor from scratch

In the previous article we built a classifier using the decision tree to predict whether a patient has heart disease. Decision trees can also be used for regression tasks to predict a number instead of a category — a salary, a temperature, the price of a house. In this article, we will take the Hitters dataset and build a decision tree to predict a player’s salary from seasons played and hits in the previous season.

The key mechanisms that chose every split there were Gini impurity and information gain. For regression, we replace Gini impurity with variance. Instead of asking how mixed the labels are, we ask how spread out the target values are. A good split is one that reduces that spread, measured here as the reduction in total squared error.

classifierregressor
the target columna category — disease or no diseasea number — salary in thousands of dollars
measuring a pileGini impurityvariance
scoring a splitinformation gainreduction in total squared error
what a leaf storesa tally of the labels that reached itthe mean of the rows that reached it
what the tree answersa class, with probabilitiesa single number

The split criterion and the value stored in each leaf are two sides of the same decision. A node’s impurity is the training error of the answer its leaf will give. Gini measures the cost of predicting class proportions for a pile of labels; variance measures the cost of predicting the mean for a pile of salaries. Change the leaf prediction and the appropriate error measure changes with it.

Candidate generation, recursive splitting, and the stopping rule remain unchanged. Only the impurity calculation and leaf prediction need to change.

What this article will also show is a limitation that appears only once the target is a number. Every answer a regression tree gives is an average of salaries it was trained on, so no matter how many seasons or hits you show it, it can never predict a salary above the highest one in its training data. The classifier could not run into this: its answers were the labels themselves, and there is nothing beyond a label. A number has a beyond, and the tree cannot reach it.

The same machinery

The algorithm is still CART, still growing a binary tree in which every node asks one yes-or-no question and has exactly two children. Laid out step by step, almost all of it runs unmodified. While building the tree, we generate the candidate questions, ask each candidate of every row to split them into two piles, one that answered True and one that answered False, score the candidate by how much impurity that split removes, keep the best of them, and recurse on each side until no question removes any more.

The candidates are generated exactly as before — every feature paired with every value that feature takes in the rows at hand, one pair per question, with a numeric column asking >= and a categorical column asking == — only the target column changed type, and the predictors can still be of either kind. Nothing about that generator knows or cares what the target column contains: five rows with two columns of four distinct values each produce eight candidates whether you are predicting a disease or a salary.

What we need to change is the measure of a pile — how much the rows in it differ from one another. In the classifier that was gini, how mixed the labels in the pile are; with a numeric target it becomes variance, how far the salaries in the pile sit from their own average.

What is interesting is that the information gain formula we used to score questions does not need to change with it. This is how we scored a split in the classifier:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)

And this is the regressor’s, the same function with one name changed:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

The subtraction is the one the classifier article worked out in full — the pile we started with, minus each child weighted by the share of rows that landed in it. What matters here is that it never asks what is in the target column; it asks only how much the rows in each pile differ. Feed it gini and the difference is information gain; feed it variance and the same difference is the drop in squared error, in squared dollars rather than in impurity.

What the criterion means once the target is a number has a simpler statement than this formula, and we get to it after building the impurity up.

The five players

The dataset is five players from the Hitters study — two numeric predictors, one numeric target:

#playeryearshitssalary
1BillyJo Robidoux24167.5
2Jack Howell24195.0
3Alvin Davis3130480.0
4Mike Marshall677670.0
5Lloyd Moseby7149787.5

years is seasons played in the major leagues, hits is hits in the previous season, salary is his salary for the 1987 season, in thousands of dollars. These are real rows from the real study, checked against the full file.

Measuring the spread of a dataset

We build the list of candidate questions exactly as before, so the next thing to understand is how to score them and decide which one becomes the node’s question. For that we will use a measure of how spread out a pile of numbers is, which is called variance, and the building block it is made of, the sum of squared errors (SSE). That role was played in the classifier article by Gini impurity, which measured how mixed a pile of labels was.

And just as before, we score a question by how much of that scatter it removes, so that after splitting on the question the two piles come out less scattered than the pile they came from. That score is the reduction in total squared error, the counterpart of information gain, and the question with the most of it wins.

Let’s look at variance first, which is the measurement of how spread out a collection of numbers is — one number saying whether they all sit close together or run from one extreme to another.

Suppose you need to say which of two payrolls is the more scattered one:

squadsalaries
A400, 410, 420, 430, 440
B67.5, 95.0, 480.0, 670.0, 787.5

Squad B comes from our real dataset — the salaries of the five players above; squad A is a hypothetical club where everyone earns about the same.

One way to do it is to put both on a graph:

Which payroll is more scattered?
mean 420.0squad A400440squad B67.5787.50200400600800

One look is enough to tell that the second squad is more spread out. But the split search needs a number it can compute. The mean is the first thing to try, and it is already in the figure as the dashed line — falling in exactly the same place for both squads.

That tells us the mean cannot measure how scattered a pile is — it reports 420 either way. Instead, we can measure how far each salary sits from the mean:

squaddeviations from 420sum
A−20, −10, 0, +10, +200
B−352.5, −325.0, +60.0, +250.0, +367.50

We cannot use the deviations as they stand, because both sets sum to zero — a property of the mean: it is the balance point of the set, so whatever sits above it exactly cancels whatever sits below.

So we need the magnitudes, discarding the signs. Two ways to do that: take absolute values, or square. We focus on squaring first, which is the conventional choice, for two reasons — it is smooth and differentiable everywhere, where the absolute value has a corner at zero, and it punishes one large miss far more than several small ones. Absolute values are a real alternative, though, and later we will see how choosing them changes the model.

Square the deviations and add them up, and you end up with the SSE; divide that by how many there are, and you have the variance:

squadsquared deviationstotal (SSE)countvariance
A400, 100, 0, 100, 4001,0005200.00
B124,256.25, 105,625, 3,600, 62,500, 135,056.25431,037.5586,207.50

SSE is the total spread of a pile; variance is the average, that same total divided by how many rows it came from — both in squared units, which is why the numbers run so large. Add more players and the SSE keeps growing, while the variance stays where it is. Both say the same thing about these two squads — 200.00 for squad A, 86,207.50 for squad B, the wider payroll getting the bigger number, 431 times over.

When we put that arithmetic down as a formula, variance is:

Var=1ni=1n(yiyˉ)2\text{Var} = \frac{1}{n}\sum_{i=1}^{n} (y_i - \bar{y})^2

where nn is how many rows the pile holds, yiy_i the salary of one of them, and yˉ\bar{y} their mean — so yiyˉy_i - \bar{y} is one row’s deviation, the column we tabulated above.

Drop the 1n\frac{1}{n} and what is left, i=1n(yiyˉ)2\sum_{i=1}^{n}(y_i - \bar{y})^2, is the SSE.

The formula we just built is known as the population variance, and looking it up you will find it beside a second version, the sample variance, differing only in the denominator:

σ2=1Ni=1N(yiμ)2s2=1n1i=1n(yiyˉ)2\sigma^2 = \frac{1}{N}\sum_{i=1}^{N} (y_i - \mu)^2 \qquad\qquad s^2 = \frac{1}{n - 1}\sum_{i=1}^{n} (y_i - \bar{y})^2

Wherever a tree divides, it divides by nn — the population form, σ2\sigma^2, with nn the number of rows in the pile. (Often it does not divide at all, working in totals — that comes later.) Sample variance uses n1n - 1 instead, because it estimates the spread of a larger population from a handful of rows drawn out of it. The leaf will answer with the mean of exactly these rows, so the impurity has to be the cost of exactly that answer. The n1n - 1 — Bessel’s correction — is there to remove the bias in that estimate, and a node has no population to estimate.

Why this is the right impurity

Let us now understand why this particular measure is the right one to score a node with. Once the tree is built, each leaf holds the mean of its pile, and at prediction time that mean is the salary it predicts for every new player who reaches it — one number for all of them. A pile with a wide spread makes that one number badly wrong for much of what it holds, which is why the split search wants piles with as little spread as possible.

Suppose the tree never split at all — one leaf holding a whole squad, predicting the mean salary, 420.0, for every player in it.

For squad A that is a good answer: nobody there earns more than 20 away from it, so the worst the leaf can be is 20 out. For squad B it is a bad one: Robidoux earns 67.5 and Moseby 787.5, and both are told 420.0, missing by 352.5 and 367.5. Square those misses and average them and you are back at the two numbers from the table, 200.00 and 86,207.50 — the same variances, now read as the error each leaf would make. So the spread inside a node is the error that node’s answer would make — and that is the number the tree compares when it decides which question to ask, preferring the one whose two piles leave the least of it.

All of that is already in the formula, 1ni=1n(yiyˉ)2\frac{1}{n}\sum_{i=1}^{n}(y_i - \bar{y})^2. Here yˉ\bar{y} is the 420.0 the leaf predicts for everyone who reaches it. Each (yiyˉ)(y_i - \bar{y}) is the error for one player: 352.5-352.5 for Robidoux, +367.5+367.5 for Moseby, and never worse than ±20\pm 20 for anyone in squad A. Squaring and averaging those errors gives us 86,207.50 and 200.00. Variance is therefore the mean squared training error of a leaf that predicts the average — the error the best possible constant leaf would still make.

The same loss as linear regression, on a different family of functions

Squared error is what ordinary least squares (OLS) minimises too, and the tree is not doing anything different with it. Both measure the same way, against the true value: yiy_i minus what the model predicts for that row. What differs is what the model is allowed to predict — linear regression gives every row its own number, read off a line at that row’s xx, while a tree gives every row in a leaf the same number.

The tidiest way to see the connection is that a leaf is an intercept-only regression. Fit OLS with no predictors at all and the estimate is yˉ\bar{y} — the same constant the leaf stores, minimising the same sum of squares. A tree is a collection of those, one per region, with the split search doing the work of choosing the regions. It is also why the variance of a pile is its training error here: variance is the average squared distance from the mean, and the mean is exactly what the leaf predicts.

The difference that matters for the algorithm is where the freedom sits. Linear regression has continuous knobs — the coefficients — and you turn them until the error stops falling. A tree has no continuous knobs at all. Once a region is fixed its best constant is forced, because the mean is what minimises squared error there, so the only thing left to choose is the regions themselves. Regions can only be chosen by choosing questions, which is why the whole minimisation reduces to enumerating candidate feature-and-threshold pairs and keeping the one that drops the error most. There is nothing to differentiate; the free choices are discrete. The second discrete choice is when to stop, and that one the criterion cannot make at all.

Classification and regression use the same structure. The leaf stores the best constant prediction, while the impurity measures the error of that prediction. For classification those are class proportions and Gini impurity; for regression they are the mean and variance. The impurity is evaluated for every candidate at every node, so changing it can move every split in the tree. The leaf statistic is not consulted when choosing splits: it determines what the finished tree predicts, not how it is shaped.

Mean or median: choosing the criterion

We chose squared error a few paragraphs ago, when the deviations needed their signs discarded and we squared them rather than taking absolute values. It is what the libraries default to, e.g. scikit-learn uses criterion="squared_error" unless you say otherwise. It is not the only option, though, and the choice reaches further than it looks: the loss we score splits with while building also defines what a leaf must store for prediction, because both are answers to the same question — which single constant minimises this loss.

  • Minimise squared error → the leaf holds the mean.
  • Minimise absolute error → the leaf holds the median.

Take a leaf holding [10, 12, 14, 16, 200], where the 200 is an outlier or a data-entry mistake:

leaf predictstotal squared errortotal absolute error
mean = 50.4027,995.2299.2
median = 14.0034,620.0194.0

Each constant wins under its own loss, exactly as it should. But look at what the mean is: 50.40, a number larger than four of the five values in the leaf. One outlier has dragged the prediction away from every point it is supposed to serve. The median ignores it completely.

So the impurity we pick decides the constant a leaf holds, which is why the two functions below are written as a pair.

def mean(rows):
    return sum(row[-1] for row in rows) / float(len(rows))

def variance(rows):
    targets = [row[-1] for row in rows]
    m = sum(targets) / len(targets)
    return sum((t - m) ** 2 for t in targets) / len(targets)

variance is what we compute to score a node; mean is what a leaf will store. That is the pair squared error asks for. Absolute error would have asked for the other one: a sum of absolute deviations, and a median in the leaf. What we have now is a number for a single node, the regression counterpart of Gini. Turning it into a score for a split is the next step, and the counterpart of information gain.

Scoring a split

So now we know how to measure how scattered a single pile is, and we can look at how to use that measurement to score a question. Our goal is to find out how much squared error is left once the question has split the rows, or equivalently how much of it the question removed. To do that we can take either of two approaches, working in totals or in averages:

totalsaverages
error in one pileSSEvariance, the SSE divided by nn — also called the MSE
error left after a splitSSEL+SSER\text{SSE}_L + \text{SSE}_Rthe two variances, weighted by pile size
error removed by a splitSSEP(SSEL+SSER)\text{SSE}_P - (\text{SSE}_L + \text{SSE}_R)the same subtraction, weighted

They rank the candidate questions identically, so nothing hangs on the choice. Totals are the simpler arithmetic, so we start there; the averaged form is what the code computes, and we come back to it once the criterion is in place.

A question splits the node into two piles, and each of them answers with its own mean — yˉL\bar{y}_L on one side, yˉR\bar{y}_R on the other. So we can apply the SSE formula to each pile separately, against its own mean. When we add those two SSEs together, we end up with the residual sum of squares (RSS) — the error the split leaves behind:

RSS=i=1nL(yiyˉL)2SSE of the left child  +  i=1nR(yiyˉR)2SSE of the right child\text{RSS} = \underbrace{\sum_{i=1}^{n_L} (y_i - \bar{y}_L)^2}_{\text{SSE of the left child}} \;+\; \underbrace{\sum_{i=1}^{n_R} (y_i - \bar{y}_R)^2}_{\text{SSE of the right child}}

So to pick the best question out of the candidates, we compute this for each of them and take the one with the smallest RSS — and that is already enough to build a regression tree: score every candidate, keep the lowest, recurse on the two piles it made.

Looking at that formula, one might wonder whether the criterion is trying to keep the tree small, or to cluster the rows into tidy groups. It does neither: it greedily looks for feature-defined divisions that make the targets in each child easier to predict with a single leaf value — less class heterogeneity in classification, less squared variation around the mean in regression. It scores the two piles at one node, takes the winner, and recurses; what the finished tree costs as a whole is never on the table.

Scoring by what a split removes

There is a different way to use the SSE to score a question. Run the same formula on the parent pile — the rows before the split, subscript PP — against its own mean yˉP\bar{y}_P, and you get SSEP=i=1nP(yiyˉP)2\text{SSE}_P = \sum_{i=1}^{n_P}(y_i - \bar{y}_P)^2 — the error that pile makes as it stands, answering every row with that one number. So instead of asking how much error a split leaves, we can ask how much it removed — that parent error minus what the two children still carry:

GainSSE=SSEP(SSEL+SSER)\text{Gain}_{\text{SSE}} = \text{SSE}_P - (\text{SSE}_L + \text{SSE}_R)

That is information gain’s shape, written in totals rather than in weighted averages.

And it is the same choice as before, because SSEP\text{SSE}_P is fixed while we compare candidates at one node: subtracting the same constant from every score shifts them all equally and reorders nothing. Say the parent’s error is 100, and two candidates leave 60 and 25:

candidateerror lefterror removed
A60100 − 60 = 40
B25100 − 25 = 75

The candidate that leaves the least has removed the most. Minimising the RSS and maximising the gain are doing the same job from opposite ends.

The gain can never be negative. Each child could have kept the parent’s mean, and instead it uses its own — which by definition is the constant minimising its own squared error. So splitting is always weakly better on the training rows, which is why gain == 0 means “no question helps at all” rather than “some questions hurt”. It is also the reason training error can never tell a tree when to stop: left alone the recursion runs until almost every row has a leaf of its own, so the stopping rule has to come from outside the criterion — a depth cap, a minimum number of rows per leaf, or pruning after the fact.

The same criterion in variance notation

The gain is stated in totals, while info_gain — the classifier article’s function, with variance where it called gini — is stated in averages, weighting each child by its share of the rows:

def info_gain(left, right, current_uncertainty):
    p = float(len(left)) / (len(left) + len(right))
    return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

p is the fraction of the parent’s rows that ended up in the left pile — three of five rows makes p = 0.6, leaving 1 - p = 0.4 for the right pile — and it is there because we are working in averages. A variance says nothing about how many rows produced it, so a child of one row and a child of a hundred would count equally — and if we want to keep using variances, we have to put the sizes back by hand, which is exactly what p and 1 - p do.

Written in totals no weights are needed at all:

def gain_sse(rows, left, right):
    return sse(rows) - (sse(left) + sse(right))

Both score the same candidates in the same order, and the averaged form is simply what the classifier already had, Gini being an average too. The two convert into each other with one identity, since variance is SSE per row:

Var=SSEnSSE=nVar\text{Var} = \frac{\text{SSE}}{n} \qquad\Longrightarrow\qquad \text{SSE} = n \cdot \text{Var}

Substitute that for all three piles, and the gain becomes

GainSSE=nPVarPnLVarLnRVarR\text{Gain}_{\text{SSE}} = n_P \text{Var}_P - n_L \text{Var}_L - n_R \text{Var}_R

and dividing through by nPn_P — again a constant at this node, so again harmless — gives the form the classification article used, and the one info_gain computes:

Gain=VarPnLnPVarLnRnPVarR\text{Gain} = \text{Var}_P - \frac{n_L}{n_P}\text{Var}_L - \frac{n_R}{n_P}\text{Var}_R

The weights that look like a design decision in the averaged form are just the row counts that were already inside the totals. So you can pick whichever of the three forms you like: the numbers they report differ, but they rank the candidates identically, and the same question wins. The gain form keeps the classifier’s code identical; the RSS form is what you will usually find in the textbooks and the libraries — scikit-learn calls the criterion squared_error for exactly this reason. This article uses gain when quoting the code and RSS when explaining what it is doing.

Scoring the root’s candidates

Let us now run that criterion on the first node of a real tree — the root, which holds all five players, before any question has been asked. Its mean is 2100/5=420.02100/5 = 420.0 and its variance is 86,207.50, so by SSE=nVar\text{SSE} = n \cdot \text{Var} the squared error we are trying to reduce is SSEP=5×86,207.50=431,037.5\text{SSE}_P = 5 \times 86{,}207.50 = 431{,}037.5. Every candidate below is scored against that number in the averaged form — the gain our code prints, VarP\text{Var}_P minus the two size-weighted child variances — and we read the winner back as an RSS afterwards.

Candidate questions are generated exactly as before — every feature paired with every value it takes. Two columns with four distinct values each gives eight candidates, two of which fail to divide the rows at all. They are laid out best-first here, though the code never sorts them; it just keeps a running winner:

candidategainleft / right
Is years >= 3?76501.04173 / 2
Is hits >= 77?76501.04173 / 2
Is years >= 6?63551.04172 / 3
Is years >= 7?33764.06251 / 4
Is hits >= 149?33764.06251 / 4
Is hits >= 130?30459.37502 / 3
Is years >= 2?does not divide5 / 0
Is hits >= 41?does not divide5 / 0

The two skipped candidates are the smallest value in each column — years runs 2, 2, 3, 6, 7 and hits runs 41, 41, 77, 130, 149 — so every row answers yes to them. Everything goes to the True side and nothing to the False side, hence the 5 / 0: there is no split to score, and they are dropped.

The gain column is what the code reports, since info_gain is the function doing the scoring. Read the winner as total squared error instead and the criterion is easier to see. Is hits >= 77? sends Davis, Marshall and Moseby one way and the two collided players the other:

RSS=48,154.17{480,670,787.5}+378.13{67.5,95}=48,532.29\text{RSS} = \underbrace{48{,}154.17}_{\{480,\,670,\,787.5\}} + \underbrace{378.13}_{\{67.5,\,95\}} = 48{,}532.29

against the root’s 431,037.50431{,}037.50. One question disposes of 89% of the squared error in the dataset, and no other question on offer leaves less behind. (The gain column is the same fact per-observation: 76,501.0417×5=382,505.2176{,}501.0417 \times 5 = 382{,}505.21 removed, and 431,037.5382,505.21=48,532.29431{,}037.5 - 382{,}505.21 = 48{,}532.29.)

Two candidates tie exactly at the top — Is years >= 3? and Is hits >= 77?, both 76501.0416666667, because they cut the five players into the same two groups. The >= in find_best_split hands the win to whichever column is scanned last, exactly as it did in the classification article.

The finished tree, and what its leaves hold

Run the recursion to completion and it stops when no pile can be divided any further:

flowchart TD n0{"Is hits >= 77?"} n1{"Is years >= 6?"} n2{"Is hits >= 149?"} n3["787.5"] n4["670.0"] n5["480.0"] n6["mean(67.5, 95.0) = 81.25"] n0 -->|True| n1 n0 -->|False| n6 n1 -->|True| n2 n1 -->|False| n5 n2 -->|True| n3 n2 -->|False| n4 classDef pure fill:#dcf5e3,stroke:#3ba55c,color:#1c1c22; classDef mixed fill:#fdf0d0,stroke:#d9a514,color:#1c1c22; class n3,n4,n5 pure; class n6 mixed;

Three leaves hold exactly one player each and reproduce their salary perfectly. The fourth holds the collided pair and answers 81.25, the mean of 67.5 and 95.0.

Run the five players back down the finished tree — the same walk a new player would take, each one following the questions to a leaf and taking the number it holds — and this is what comes back:

BillyJo Robidoux     actual    67.5   predicted   81.25
Jack Howell          actual    95.0   predicted   81.25
Alvin Davis          actual   480.0   predicted  480.00
Mike Marshall        actual   670.0   predicted  670.00
Lloyd Moseby         actual   787.5   predicted  787.50

That is textbook memorisation — the tree kept splitting until almost every row had a leaf to itself, exactly as the classifier did, and for the same reason: gain == 0 is the only thing that stops it.

That 81.25 clearly demonstrates why we keep the mean in a leaf rather than anything else — the smaller of the two salaries, say, or the larger. The leaf must emit one number, call it cc, and the loss we are minimising is squared error, so the question is which cc makes i(yic)2\sum_i (y_i - c)^2 as small as possible. That is a smooth function of cc, so the minimum is where its derivative vanishes:

ddci(yic)2=2i(yic)=0iyi=ncc=yˉ\frac{d}{dc}\sum_i (y_i - c)^2 = -2\sum_i (y_i - c) = 0 \qquad\Longrightarrow\qquad \sum_i y_i = n c \qquad\Longrightarrow\qquad c = \bar{y}

So the mean is not one reasonable choice among several, and not a convention either: it is the only constant that satisfies this, and it is the solution to the same minimisation the split criterion is running. Impurity and leaf value come from one loss function.

That leaf is also where the tree stops improving. Robidoux and Howell have identical years and hits, so no question can ever separate them: they share a leaf at any depth, and whatever number that leaf answers, it is wrong for at least one of them. Answering 81.25 leaves (67.581.25)2+(9581.25)2=378.125(67.5 - 81.25)^2 + (95 - 81.25)^2 = 378.125 of squared error, and no tree reading only these two columns can drive it lower — a floor under the training error that growing deeper cannot get past.

And this is not an artefact of five convenient rows: nine such pairs occur among the 263 players, the worst of them disagreeing by $310,000 — so on these two columns even a perfect model would be wrong by an average of $155,000 on that pair. The full file has seventeen more predictors that would pull them apart; the point is that with any fixed set of features there is a floor, and the leaf mean is how a tree finds it.

Inside the data: a staircase

Let us now look at the shape a finished tree draws, and then at what happens past the edge of the training data. This will help us see what a regression tree can and cannot express. A regression tree is piecewise constant: its questions divide the input space into regions, and every point in a region receives the same prediction. As a function of the features, its output is a set of flat plateaus with vertical jumps at the thresholds — no slopes anywhere, at any depth. We will refer to this property as flatness below.

To demonstrate this easily we plot a synthetic dataset below rather than Hitters: 40 rows with one feature, xx, evenly spaced from 0 to 10, and a target that follows a smooth wave with a little noise on it.

x00.2560.5130.7699.74410
y45.9052.2957.3658.8679.4882.41

Two columns and a curved relationship for the tree to approximate, which is all this figure needs. It fits a full CART regressor to those rows. The dashed vertical lines are the thresholds it split on, so the plot between two neighbouring lines is one leaf, drawn flat at the mean of the points inside it. Raise the depth cap and watch the tree cut the range into more pieces:

How deep the tree may grow
no training dataxy

At depth 1 there are two plateaus and the fit is terrible. By depth 6 there are 27 and the squared error has fallen from 5,816 to 89 — that figure being the whole fit’s error, every one of the 40 points walked down the tree and scored against the mean held by the leaf it lands in, exactly the sum we have been calling the RSS, now over 27 leaves rather than two. The tree is converging on the curve, but it never bends — it approximates a smooth function by chopping it into ever-narrower constant pieces.

This is the structural difference from a linear model, and it cuts both ways. A tree needs no assumption that the relationship is linear, monotonic, or smooth, and it picks up interactions between columns for free. What it gives up is the ability to express even the simplest continuous trend compactly: representing y=2xy = 2x takes one coefficient in a linear model and an unbounded number of steps in a tree.

With two features, the staircase becomes a terrain

One feature gives a staircase because there is one axis to lay the steps along, with the prediction on the other. Add a second feature and both axes are spoken for, so the prediction has to go somewhere else: the tree cuts the plane into rectangles, and what was the height of a step becomes the height of a flat roof over each one.

The two panels below are the same model. On the left, the partition seen from above, where the prediction shows up as the shading and the number inside each rectangle — the picture the classification article drew for decision regions. On the right, the identical boxes raised to that number, so the height carries what the yy axis carried in the staircase:

How deep the tree may grow
The partition of the feature space
x₁x₂
The prediction surface

Every roof is flat and every wall is vertical, which is what piecewise constant looks like when you can see it. Raise the depth and the terrain gains blocks the way the staircase gained steps — 2 regions, then 4, 8, 16 — approaching the shape of the data in flat facets, never in slopes.

Outside the data: a ceiling

Look again at the staircase widget, at the shaded band on the right, past the last training point. The staircase does not continue there. It goes flat and stays flat, forever, at whatever value the right-most leaf holds. What that means is that every input beyond the values found in the training set is predicted to have the same target.

The mechanism behind this is not unique to regression. A classifier’s regions are just as flat, and it too answers anything beyond its training data with whatever its outermost leaf holds. For regression, the limitation is especially visible because target values have an order. If salary keeps rising outside the training range, the tree cannot follow it; it continues returning the value stored in its outermost leaf. Labels have no equivalent direction — there is no category above “disease” — so the same behaviour is less obvious in classification.

This behaviour follows directly from how prediction works: a row arriving with x=106x = 10^6 answers “yes” to every threshold question on the way down, lands in the right-most leaf, and receives the mean of the training rows that landed there. There is no mechanism by which a leaf value can depend on how far past the threshold the row is.

Here is the sharpest possible demonstration — a perfectly linear relationship with no noise at all, y=2.5x+3y = 2.5x + 3, sampled on x[0,10]x \in [0, 10], fitted by a depth-3 tree and by ordinary linear regression:

X = np.linspace(0, 10, 60).reshape(-1, 1)
y = 2.5 * X.ravel() + 3

tree = DecisionTreeRegressor(max_depth=3).fit(X, y)
linear = LinearRegression().fit(X, y)

Both models fit the same 60 rows, all of them inside x[0,10]x \in [0, 10]. Now ask each of them for values inside that range and then well outside it:

xtrue valuetreelinear regression
28.007.458.00
515.5013.8115.50
823.0023.3423.00
1233.0026.5233.00
2053.0026.5253.00
50128.0026.52128.00
10002503.0026.522503.00

Drawn out to x=20x = 20, with the training range ending at 10:

no training data0510152002040xlinear modeltree

The linear model recovers the rule exactly and is correct at x=1000x = 1000. The tree returns 26.52 at x=12x = 12, at x=50x = 50, and at x=1000x = 1000 — one number, for every input beyond its experience, on data with no noise and a relationship a straight line captures with two parameters.

Even inside the training range the tree is never exactly right: it says 7.45 where the truth is 8.00. That is the flatness again. A straight line is being split into eight plateaus, and each one answers with its own average.

Worse than the flatness is the bound. A leaf holds the mean of the training targets that reached it, and a mean cannot lie outside the values it averages. So every prediction a regression tree can ever make is confined to the range of the training targets. It cannot forecast a record high or a record low, at any depth, on any data.

On the straight line above, the largest value the tree can emit is 26.5169 against a training maximum of 28.0 — it cannot even reach the biggest number it has seen. That last part is not universal, though, and Hitters shows why. Fit a tree to the salaries and its ceiling is 2127.3, which is the training maximum exactly, at every depth down to 2:

depth 2      highest possible prediction  2127.3   reached by 1 player
depth 3      highest possible prediction  2127.3   reached by 1 player
depth 5      highest possible prediction  2127.3   reached by 1 player
depth full   highest possible prediction  2127.3   reached by 1 player

The top earner is such an outlier that the greedy search spends a whole split isolating him into a leaf of his own — even in a four-leaf tree — because removing that much squared error is the best trade available. Where the targets are smooth, the ceiling sits strictly below the maximum; where there is a lone extreme, the tree carves it out and reaches it.

Either way the ceiling lands at or below the largest target in the training data — never above it, whatever you feed the tree. Ask that same depth-3 tree to price a player with twice the best career totals anyone in the dataset has ever posted:

depth-3 tree       predicts   1169.8
linear regression  predicts   5836.3

The tree answers with a number it has already seen — a perfectly ordinary salary, well inside the observed range — for a player twice as good as the best in history.

This matters most when extrapolation is part of the task:

  • Trends and time series. Once the time feature passes every learned threshold, a tree keeps predicting the same plateau. If the trend itself matters, detrend first and model the residuals with a tree, or use a model that can express a slope.
  • Prices and growth. A tree cannot continue a rising pattern beyond the feature values represented by its learned thresholds.
  • Ensembles. Random forests inherit the same limitation. Boosted trees can produce values outside the original target range, but their predictions still become constant once every feature has moved beyond the learned split thresholds.

The limitation comes from what sits in the leaf, not from the splitting. Some tree variants fit a linear model in each leaf instead of a constant. That allows extrapolation, although predictions far beyond the data then depend heavily on the fitted slope.

From one tree to an ensemble

Turning the classifier into a regressor required only two changes: use variance to score nodes and store the mean in each leaf. The resulting model is flexible within the training range, but its piecewise-constant predictions cannot extrapolate a trend beyond it.

Almost every practical use of a regression tree is as a component rather than a model. Average hundreds of them, each grown on a different sample, and you get a random forest — where nothing is optimised jointly, each tree minimising its own squared error on its own sample and the averaging doing the rest.

Fit them in sequence to each other’s errors instead and you get gradient boosting, where the squared error being minimised is the whole ensemble’s. Each round measures what the ensemble so far still gets wrong and fits the next tree to those residuals, so every tree runs exactly the split search from this article, only against a target made of the current mistakes rather than the raw salaries. It is also why these trees do the work even when the problem is classification: what they are fitted to is a column of real-valued gradients rather than labels.

The tree in this article is the unit those ensembles are built from — and the warning travels with it. Squared error on the training rows is what a tree drives to zero by growing and what boosting drives to zero by adding rounds, which is why both come with knobs whose only job is to stop them.