Trees and Ensembles of Them

How a regression tree chooses its splits by exhaustive search, why the resulting fit is piecewise constant and unstable under resampling, and what averaging many trees changes about that instability, including the correlation floor that limits what more trees can achieve and the restriction random forests use to reduce it.

Definition

A regression tree partitions the predictor space into rectangular regions and predicts, within each, the mean of the training responses that fall in it. The fitted function is therefore piecewise constant.

Recursive binary splitting builds it. At each node, consider every predictor $j$ and every candidate cut point $s$ , and score the split by the total residual sum of squares of the two groups it creates:

RSS (j, s) = \sum_{i : x_{i j} < s} (y_{i} - {\bar{y}}_{L})^{2} + \sum_{i : x_{i j} \geq s} (y_{i} - {\bar{y}}_{R})^{2},

where ${\bar{y}}_{L}$ and ${\bar{y}}_{R}$ are the group means. Take the minimising $(j, s)$ , then repeat within each group. The procedure is greedy: each split is chosen without regard to splits that might follow it.

Bagging fits $B$ trees, each on a bootstrap resample of the training data drawn with replacement, and averages their predictions. For $B$ predictions each of variance $σ^{2}$ and with pairwise correlation $ρ$ , the variance of the average is

ρ σ^{2} + \frac{1 - ρ}{B} σ^{2} .

Only the second term falls with $B$ . As $B$ grows the variance approaches $ρ σ^{2}$ , a floor set by how alike the trees are.

A random forest is bagging plus one change: at each split, only a randomly chosen subset of the predictors is considered as candidates. The intent is to reduce $ρ$ by preventing every tree from opening with the same dominant predictor, which lowers the floor. Whether it does so, and by how much, depends on the data: the restriction is a design choice aimed at decorrelation, not a guarantee of it.

Assumptions and scope

The split criterion above is for a continuous response. Classification trees use an impurity measure such as the Gini index or cross-entropy instead, and the greedy structure and instability carry over unchanged.
The variance formula $ρ σ^{2} + (1 - ρ) σ^{2} / B$ assumes every tree has the same variance and every pair the same correlation. Real ensembles violate both mildly, so it describes the shape of the relationship rather than an exact value.
Bagging is primarily a variance-reduction device for unstable learners. Averaging changes the fitted function, so it does not leave bias exactly unchanged in general; the bias of the average is close to that of a single tree when the trees are similar, which is the case the argument assumes. A region where a single tree is systematically wrong stays wrong under averaging, since every tree makes the same error there.
Averaging a piecewise-constant fit produces a smoother fit, which helps where the truth is smooth and can hurt near a genuine discontinuity, where averaging across trees that place the boundary differently blurs it.
Bootstrap resamples omit about 37% of the observations each time. Those out-of-bag observations give an error estimate without a separate held-out set, but the estimate is of a bagged predictor built from fewer trees than the final one.

Worked material

Example

Relationships a tree handles well, and badly

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 = 2 x$ 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.

Contrast

Changes that look similar and do different work

More trees against less correlated trees.

	raise $B$	lower $ρ$
affects	$(1 - ρ) σ^{2} / B$	$ρ σ^{2}$ , the floor
at $ρ = 0.2$ , $B = 100$	variance $0.208 σ^{2}$	—
at $ρ = 0.2$ , $B \to \infty$	variance $0.200 σ^{2}$	—
at $ρ = 0.05$ , $B = 100$	—	variance $0.060 σ^{2}$

Going from a hundred trees to infinitely many recovers $0.008 σ^{2}$ . Cutting the correlation from $0.2$ to $0.05$ at a hundred trees recovers $0.148 σ^{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.

	out-of-bag	$k$ -fold
extra fits required	none	$k$
estimates the error of	an ensemble of about $0.368 B$ trees	an ensemble of $B$ trees on $n (k - 1) / k$ observations
bias	mildly pessimistic	mildly pessimistic

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.

Common errors

Common misconception

That growing more trees in an ensemble drives its variance toward zero, so a forest of 5000 trees is meaningfully better than one of 500. The variance of an average of $B$ predictions with pairwise correlation $ρ$ and individual variance $σ^{2}$ is $ρ σ^{2} + (1 - ρ) σ^{2} / B$ . Only the second term falls with $B$ ; the first does not move. At $ρ = 0.2$ the variance is $0.208 σ^{2}$ at $B = 100$ and approaches $0.200 σ^{2}$ however many trees are added, so almost all the available reduction has already happened. Lowering $ρ$ , which is what restricting the split candidates in a random forest does, moves the floor itself and is the reason that restriction exists.

Common misconception

That a regression tree's split point is chosen by eye from where the data appear to separate, or at a round value such as the median or the midpoint of the range. The split is selected by exhaustive search: every candidate boundary between adjacent observed values is scored by the total residual sum of squares of the two groups it creates, and the minimising candidate is taken. The chosen point often coincides with where a reader would have drawn it, which is what makes the misconception durable, but the coincidence is a consequence of the criterion rather than the method. Where several candidates score closely the choice is decided by small differences that a different sample would reverse, and that instability is the variance an ensemble exists to average away.

Trees and Ensembles of Them

Assumptions and scope

Worked material

Relationships a tree handles well, and badly

Changes that look similar and do different work

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history