Trees and Ensembles of Them

Every form in the previous unit fixed a shape and estimated coefficients. A tree does neither. It asks a sequence of yes-or-no questions about the predictors and answers with the average of whatever training observations survive the questions.

That supplies two things. There is no functional form to get wrong, so no assumption about curvature or multiplicative growth has to be checked. And the result can be drawn and read aloud, which is why trees appear wherever a prediction has to be explained to someone who will act on it.

It costs two things. The fitted function is a staircase, constant within each region and jumping at the boundaries, so a smooth relationship is approximated by steps. And the structure is unstable: because each split is chosen by a comparison that a handful of different observations can reverse, and because every later split sits beneath an earlier one, a small change in the sample can rebuild the whole tree.

That instability is variance in the sense the evaluation unit defined, and it is what the second half of this unit is about. Averaging many trees reduces it, but not without limit. The trees are built from the same data and tend to make the same choices, and the part of the variance they share is the part averaging cannot remove.

The canonical statements above give the splitting rule and the variance identity. What follows is what each leaves out.

The criterion is evaluated on the node's own observations only. Scoring a candidate split at one node takes no account of what could be achieved beneath it. A split that scores second-best now might permit two excellent splits afterwards and is nonetheless discarded. This is what greedy means, and it is why a tree is not the best tree of its size, finding that is computationally infeasible, and the greedy construction is the price of building one at all.

Candidate cut points are boundaries between observed values. There are at most $n-1$ of them per predictor, since any two cut points with the same observations on each side produce identical groups and identical scores. Convention places the cut midway between adjacent values, which matters only for how the tree is reported, not for the fit.

A leaf's prediction is the mean, because the criterion is squared error. Minimising $\sum (y_i-c{)}^2$ over a constant $c$ gives $c=\overline{y}$. A criterion of absolute error would put the median there instead. The prediction rule is a consequence of the loss, not a separate choice.

The variance identity assumes exchangeable trees. Writing the variance of the average as $\rho {\sigma }^2+(1-\rho ){\sigma }^2/B$ takes every tree to have the same variance ${\sigma }^2$ and every pair the same correlation $\rho$. Real ensembles satisfy neither exactly. The identity describes the shape of the relationship, a term that falls with $B$ and a term that does not, rather than predicting a number.

Bagging changes variance and not bias. Each tree is fitted to a resample of the same data by the same procedure, so they share whatever systematic error the procedure makes. Averaging removes disagreement, and there is no disagreement about a region where every tree is wrong in the same direction.

Out-of-bag observations come free. A bootstrap resample of size $n$ drawn with replacement omits each observation with probability $(1-1/n{)}^n$, which approaches $e^{-1}\approx 0.368$. Those omitted observations were not used to fit that tree, so averaging each observation's predictions over the trees that omitted it gives an error estimate without a separate held-out set. The estimate describes an ensemble of about $0.368B$ trees rather than the final one, so it is mildly pessimistic.

A tree drawn on a page invites a particular reading: this predictor matters most, because it is at the root; that one matters next. The reading is often unreliable, and the reason is worth understanding because it is the whole argument for ensembles.

Near-ties at the root. The first split is chosen by comparing scores across candidates. When two candidates score $12.40$ and $12.47$, the first wins and is reported as the split, but the gap is smaller than the variation a different sample would produce. Redraw the sample and the second candidate may win instead. Nothing in the printed tree records that the contest was close.

The consequence propagates downward. Every subsequent split is chosen within the groups the first split created. Change the root and the two groups change, so different candidates are evaluated against different observations, and the entire subtree is rebuilt. One reversed comparison at the top can produce a tree that shares no split with the original.

Predictions move less than structure. Two trees that look nothing alike can predict nearly the same values, because both are approximating the same underlying relationship and the regions they carve, though differently shaped, cover similar ground. This is why the instability is easy to miss: the model keeps working while the explanation it offers changes completely.

What averaging can and cannot fix. If the $B$ trees disagreed independently, their average would have variance ${\sigma }^2/B$ and enough trees would eliminate it. They do not disagree independently. Each is built from a resample of one dataset, so a predictor that is genuinely strong is chosen first by nearly all of them, and they agree in the same places for the same reasons. That shared component is $\rho$, and it survives averaging untouched.

The arithmetic makes the limit concrete. With $\rho =0.2$, the variance of the average is $0.208{\sigma }^2$ at $B=100$ and $0.200{\sigma }^2$ in the limit. Going from a hundred trees to ten thousand recovers $0.008{\sigma }^2$: essentially nothing.

Which is why the random forest handicaps its trees. Forbidding most predictors at each split forces different trees to open differently, lowering $\rho$. Each tree fits worse in isolation. The quantity that matters is the variance of the average, and that is governed by $\rho$ once $B$ is moderately large, so a collection of worse, more varied trees beats a collection of better, near-identical ones.

A tree's fitted function is piecewise constant. That single property decides which relationships it represents cheaply and which it represents only by spending many splits.

A step. Cheap. A response that is one value below a threshold and another above it is exactly what a single split expresses. One comparison, two leaves, and the fit is essentially exact. No form had to be guessed, and no transformation applied.

A straight line. Expensive. A tree approximates $y=2x$ by a staircase. Each split adds one riser, so representing a line across a range to any accuracy costs splits without limit, and the fit remains visibly wrong between them. A linear model with two coefficients does better than a tree with thirty leaves, which is the clearest case of a fixed form earning its assumption.

An interaction. Cheap, and automatic. Suppose the effect of dose reverses above a certain age. A linear model represents this only if somebody writes down an age-by-dose product term. A tree splits on age and then chooses different dose splits in each branch, so the interaction is discovered rather than specified. This is the main reason trees are used on data whose structure is unknown.

A relationship depending on a sum of predictors. Expensive. If the response depends on $x_1+x_2$, the boundary is a diagonal line in the predictor space. A tree can only cut along the axes, so it approximates the diagonal by a staircase of rectangles and needs many splits to do it badly.

A smooth curve. Middling, and improved by averaging. A single tree gives a coarse staircase. Averaging many trees whose steps fall in different places produces a fit with many small steps rather than a few large ones, which is closer to smooth. This is a case where the ensemble changes the shape of the fit and not merely its stability.

---

Trees are cheap where the truth has boundaries aligned with individual predictors, and expensive where it is smooth or depends on predictors in combination. Neither is a defect: it is what choosing a partition instead of a formula gains and costs. The complementary observation is that a linear model's costs are the mirror image, which is why the two appear together in practice and why comparing them on held-out error is the routine move.

To grow a regression tree.

1. Start with every observation at the root.
2. At the current node, enumerate candidates. For each predictor, take the boundaries between adjacent distinct observed values, at most $n-1$ per predictor.
3. Score each candidate by the total residual sum of squares of the two groups it creates, using each group's own mean.
4. Take the minimising candidate and split. Record the runner-up's score: a near-tie is a warning that the split is not determined by the data as firmly as the drawn tree suggests.
5. Repeat within each group until a stopping condition is met. A minimum node size, a maximum depth, or no split that improves the score.
6. Predict at a leaf with the mean of its training responses.

To choose the depth. Depth is a flexibility parameter, so it is selected by held-out error rather than by the training criterion, which falls with every split by construction. The usual practice is to grow deliberately too far and then prune back, since a split that looks worthless can enable a valuable one beneath it and stopping early never discovers that.

To bag.

1. Draw $B$ bootstrap resamples, each of size $n$, with replacement.
2. Fit a tree on each, grown deep and left unpruned. The variance that depth introduces is what the averaging is there to remove.
3. Average the $B$ predictions for a new input.
4. Estimate error out-of-bag: for each observation, average the predictions of only those trees whose resample omitted it, then compare with the observed value.

To grow a random forest. Follow the bagging procedure with one change at step 2: at every split, draw a random subset of $m$ predictors and consider only those as candidates. A common starting point is $m\approx \sqrt{p}$ for classification and $m\approx p/3$ for regression, tuned by held-out error.

Choosing $B$. Increase it until the out-of-bag error stops falling. Because the variance of the average is $\rho {\sigma }^2+(1-\rho ){\sigma }^2/B$, the returns diminish quickly: most of the available reduction has occurred by a few hundred trees, and further trees cost computation while moving the floor not at all. More trees never hurt accuracy, which is why the parameter is safe to set generously and not worth tuning carefully.

Checks.

Compare the ensemble's out-of-bag error against a single tree's held-out error. If averaging has not improved matters, the trees are probably too shallow to have had much variance to remove.

Refit the single tree on a resample and compare the two structures. Splits that survive are the ones worth describing to anyone; splits that move were never as determined as the picture implied.

Ten observations, $x=1,\dots ,10$:

Step 1: the score before splitting. The mean of all ten is $5.11$, and

This is what any split must improve on.

Step 2: enumerate the candidates. Boundaries between adjacent observed values, conventionally at the midpoints: $1.5,2.5,\dots ,9.5$. Nine candidates.

Step 3: score each. For a candidate, split the observations, take each group's own mean, and add the two sums of squared deviations.

Step 4: take the minimum. The split at scores $0.6600$, reducing the total by $82.3690$, which is $99.2\mathrm{\%}$ of the unsplit sum of squares. Its leaves predict

The score falls to the winner and rises symmetrically away from it, because every other candidate leaves some low observations grouped with high ones. The nearest competitors, $24.6183$ and $26.3808$, are worse by a factor of about 37. This split is not a near-tie: it is determined by the data, and a resample would choose it again. Compare a case where the two best candidates scored $12.40$ and $12.47$, where the winner records which narrowly led rather than a finding.

It says the boundary lies between $x=5$ and $x=6$. It does not locate it at $5.5$. There are no observations in between, so every threshold in that interval produces identical groups and an identical score; $5.5$ is the midpoint convention, not an estimate. Reporting the threshold as $5.5$ claims a precision the data do not carry.

Step 5: what a second split would buy. Within the left leaf the values are $2.1,1.9,2.4,2.2,2.6$, whose sum of squared deviations is $0.3320$. The best split of that group removes part of $0.3320$, against $82.3690$ removed by the first. Continuing to split fits the noise, which is what makes depth a flexibility parameter to be chosen on held-out error rather than on this criterion, since this criterion falls with every split by construction.

The averaging arithmetic, on the same footing. If $B$ trees each have prediction variance ${\sigma }^2$ and pairwise correlation $\rho$, the average has variance $\rho {\sigma }^2+(1-\rho ){\sigma }^2/B$:

At $\rho =0.2$, every tree beyond the hundredth can recover at most $0.008{\sigma }^2$. Halving the correlation to $0.05$ recovers $0.1485{\sigma }^2$ at the same $B$. The second lever is roughly eighteen times the first, which is the entire argument for restricting the split candidates.

More trees against less correlated trees.

Going from a hundred trees to infinitely many recovers $0.008{\sigma }^2$. Cutting the correlation from $0.2$ to $0.05$ at a hundred trees recovers $0.148{\sigma }^2$, roughly eighteen times as much. This is why a random forest restricts the split candidates rather than simply growing more trees.

Bagging against pruning.

Both address a deep tree's poor test error and they work in opposite directions. Pruning removes splits, lowering variance and raising bias, and leaves one readable tree. Bagging keeps every tree deep and averages, lowering variance while leaving bias alone, and leaves no single tree to read. Choose pruning when the explanation is the deliverable; choose bagging when the prediction is.

Out-of-bag error against cross-validated error.

Both are honest held-out estimates and neither is free of bias; out-of-bag is far cheaper and estimates a slightly smaller ensemble than the one being shipped.

A tree's variance against a tree's bias.

A deep tree has low bias and high variance: it can represent almost any partition, and which partition it chooses depends heavily on the sample. A stump has the reverse. Bagging addresses only the first, so bagging stumps accomplishes very little. There is little disagreement to average away. Recognising which term dominates decides whether an ensemble is the right instrument at all.

A split's score against a split's stability.

The reported tree shows which candidate won. It does not show by how much. A split winning by $0.07$ out of $12.40$ and one winning by $6.00$ look identical on the page, and only the second is a finding about the data. Checking the runner-up's score costs one line of output and is the difference between a structure worth describing and one that happens to have won a coin toss.

A fitted tree is unusually legible, and that legibility invites three claims it does not license.

The threshold is not estimated to the precision it is printed with. A split reported at was chosen from candidates at the midpoints between observed values. If no machine ran between 40 and 50 hours, every threshold in that interval produces identical groups and an identical score. The $45$ is a drawing convention. Quoting it as the point where behaviour changes states a precision that came from the midpoint rule rather than from the data.

The order of the splits is not a ranking of importance. The root is whichever candidate scored best, by whatever margin. A win by $0.07$ out of $12.40$ and a win by $6.00$ are drawn identically, and only the second is a finding. Before describing the root predictor as the most important, check what the runner-up scored; it costs one line of output.

A split absent from the tree is not a predictor shown to be irrelevant. Greedy construction commits to the best split now, and a predictor useful only in combination with another may never be chosen. Its absence records that it never won a comparison, not that it carries no information.

---

Two failure modes on the ensemble side.

More trees is the lever people reach for and the one that moves least. The variance of the average is $\rho {\sigma }^2+(1-\rho ){\sigma }^2/B$, and only the second term responds to $B$. At $\rho =0.2$ the variance is $0.2080{\sigma }^2$ at a hundred trees against a floor of $0.2000{\sigma }^2$: going to ten thousand recovers less than $0.01{\sigma }^2$. If an ensemble is underperforming, the correlation between its trees is where to look.

Bagging does not repair a biased procedure. Averaging removes disagreement. Where every tree is wrong in the same direction, extrapolating past the data, or approximating a smooth trend by steps, they agree, and the average is wrong in exactly that direction. Adding trees to fix a systematic error is work that cannot succeed.

And where there is no disagreement, averaging can make matters worse. A simulation over 300 datasets, bagging 50 replicates of a depth-1 tree fitted to a clean step at $x=5.5$, gives the spread of predictions as a ratio of bagged to single:

Away from the step the ratio is essentially 1: a stump on a clean step is already near-optimal and has almost no variance to remove. Adjacent to the step the ratio rises above 2, and the bagged prediction is also displaced, at $x=5$ it averages $3.753$ against a true value of $2.2$, and at $x=6$ it gives $7.504$ against $8.0$. Bootstrap resamples place the split on either side of the discontinuity, and averaging across those placements blurs the step into a ramp.

The same simulation on the case bagging is actually for, a depth-3 tree on a smooth function, reduces the spread at every query point, with ratios $0.90$, $0.49$, $0.86$, $0.65$ and $0.90$, averaging $0.759$. Note how far that is from the $1/\sqrt{B}\approx 0.14$ that independent trees would give: the gap is the correlation floor, measured rather than asserted.

---

What a tree does outside the observed range. It predicts the nearest leaf's mean, forever. A model fitted to machines run up to 80 hours predicts the 80-hour leaf's value at 500 hours, with no indication that the input is far outside anything seen. A linear extrapolation at least fails visibly; a tree fails flat, and a flat prediction reads as a considered answer.

Clinical triage rules. A protocol that decides which head-injury patients need imaging is a short sequence of yes-or-no questions, because it has to be applied at a bedside by someone who cannot run a model. The tree structure is the deliverable, and the shallow depth is chosen for usability rather than accuracy. Such rules are validated on separate cohorts precisely because a tree fitted once is unstable, and a rule that changed with the sample could not be published as a protocol.

Credit decisions under an explanation requirement. Where a declined applicant is entitled to the reasons, a model whose prediction cannot be stated as a path through conditions is difficult to deploy. A single tree gives that path directly. A random forest does not, which is why lenders using ensembles report feature attributions computed after the fact rather than the model's own structure.

Tabular prediction where accuracy is the only requirement. For customer churn, demand forecasting, fraud scoring and similar problems on mixed-type tabular data, ensembles of trees remain the routine first choice. They need no transformation of the predictors, discover interactions without being told, and tolerate irrelevant columns. No explanation is being sold, so nothing is lost by giving up the readable structure.

Genomics and other wide data. With thousands of predictors and few observations, a single tree's first split is chosen from an enormous pool and is close to arbitrary. The random-forest restriction matters most here: without it, the handful of predictors that happen to correlate with the response in this sample would open nearly every tree, and the correlation floor would be high.

Where a tree is the wrong instrument. Smooth physical relationships, extrapolation beyond the observed range, a tree predicts the nearest leaf's mean forever, so it is flat outside the data rather than wrong in an interesting direction, and any problem where the response depends on a sum or ratio of predictors rather than on each separately.

---

The recurring decision. Each case turns on whether the structure or the prediction is the product. When the structure is the product, a single tree is grown shallow, validated on fresh data, and its instability treated as the central risk. When the prediction is the product, the trees are grown deep, decorrelated, averaged, and no one reads them.