Trees, Forests, and Boosting: Axis-Aligned Everything

A tree is a partition, and that is the whole story

Strip away the flowchart drawing and a decision tree is a rule for cutting feature space into rectangular boxes. Each internal node asks one question of the form “is feature \(j\) less than or equal to \(t\)?” — a single axis-aligned cut. Follow the questions down and every leaf owns one box. Inside that box the model predicts one number: the mean of the training targets that landed there for regression, the majority class (or the class proportions) for classification.

Three consequences are worth spelling out.

No feature scaling is needed. The split \(x_j \le t\) only cares which side of \(t\) a point falls on. Multiply \(x_j\) by a thousand, take its logarithm, or replace it by its rank, and every threshold moves with it while the induced partition stays identical. Trees are invariant to any monotone transformation of a single feature — a rare property, since linear models, k-nearest neighbours and neural networks all care about units.

Interactions come free. Nesting a split on \(x_2\) underneath a split on \(x_1\) means “the effect of \(x_2\) depends on \(x_1\)”, which is exactly an interaction term. A linear model needs you to write \(x_1 x_2\) by hand; a tree discovers it by splitting.

Diagonals are expensive. A boundary such as \(x_1 + x_2 = 7\) is not expressible by any finite set of axis-aligned cuts. A tree approximates it with a staircase, and each extra step costs another split on half as much data. This is the structural weakness of the whole family; ensembling smooths the steps but never removes them.

Choosing a split

We need a score that says how mixed a set of labels is, and we pick the split that reduces it most. For classification, with \(p_k\) the proportion of class \(k\) in a node:

Gini impurity \(G\) is the probability of misclassifying a randomly drawn member of the node if you guessed by drawing a label at random from the node’s own distribution. Entropy \(H\) is the average number of bits needed to encode a label. Both are zero for a pure node and maximal for a uniform mix (for two classes: \(0.5\) and \(1\) bit). They rank splits almost identically in practice; Gini is the usual default because it avoids a logarithm.

For regression, the same idea with variance in place of impurity:

In every case, the quantity being maximised is the drop from the parent to the size-weighted average of the two children:

The weighting matters: a split that carves off one clean outlier gains almost nothing, because the pure child is tiny and the messy child still holds nearly everything.

One split, computed

Eight points, two features, labels generated by \(x_1 + x_2 > 7\) — a deliberately diagonal truth.

The root has four of each class, so \(G = 1 - 0.5^2 - 0.5^2 = 0.5\) and \(H = 1\) bit. Candidate thresholds are the midpoints between adjacent observed values of each feature — ten of them here. The four best, by Gini gain:

The winner is \(x_1 \le 3.5\). Working it through: the left child holds A, B, C, D, H, one positive out of five, so \(G_L = 1 - 0.2^2 - 0.8^2 = 0.32\); the right child holds E, F, G and is pure, \(G_R = 0\). The weighted impurity is \(\tfrac{5}{8}(0.32) + \tfrac{3}{8}(0) = 0.2\), a gain of \(0.3\). Entropy picks the same split, gaining \(0.5488\) bits. Recursing on the impure left child, the best second split is \(x_2 \le 5.0\), which isolates H and makes both children pure — three leaves, zero training error.

Two cuts and a perfect fit. That is the seduction, and the warning: the truth is a straight diagonal, and what we learned is a two-step staircase that happens to separate these eight points. Ask the same tree about \((3.4,\,4.0)\) — true label 1, since the sum is \(7.4\) — and it answers 0, because that point sits left of \(3.5\) and below \(5.0\).

Why one tree overfits

Grown without constraint, a tree keeps splitting until every leaf is pure — in the limit, one training point per leaf and zero training error. The bias is essentially nil and the variance is enormous: move one point, and a split near the root can flip to a different feature, redrawing every box underneath it. Two trees grown on two samples from the same distribution can look nothing alike.

The controls are all ways of saying “stop earlier” or “cut it back”:

• Maximum depth caps the number of nested questions, hence the number of leaves at \(2^{\text{depth}}\).
• Minimum samples per leaf / per split stops the tree from carving boxes so small that the constant inside them is estimated from three points.
• Minimum impurity decrease refuses splits whose \(\Delta\) is below a threshold.
• Cost-complexity pruning grows the tree fully and then removes subtrees, minimising \(R(T) + \alpha\lvert T \rvert\) where \(R\) is training error and \(\lvert T \rvert\) the number of leaves. Pruning generally beats early stopping, because a weak split can be the necessary prelude to a strong one — early stopping never gets to find out.

Random forests: bagging is only half of it

Bagging trains \(B\) trees on \(B\) bootstrap resamples and averages their predictions. Averaging \(B\) independent variables of variance \(\sigma^2\) gives variance \(\sigma^2/B\), which would suggest that enough trees drive the variance to nothing. They do not, because bootstrap resamples of the same dataset are not independent — the trees see largely the same data, latch onto the same one or two dominant features at the root, and end up correlated. For an average of \(B\) identically distributed variables with pairwise correlation \(\rho\):

The second term vanishes as \(B\) grows; the first does not. With \(\rho = 0.5\) and \(\sigma^2 = 1\), ten trees give \(0.55\) and a thousand trees give \(0.5005\) — the floor is \(\rho\), and buying more trees past a point buys nothing. This single equation is the entire argument for random forests: to get below the floor you must lower \(\rho\) itself.

The mechanism is feature subsampling at each split, not once per tree. At every node, the tree may only consider a random subset of \(m\) of the \(p\) features (commonly \(m \approx \sqrt{p}\) for classification, \(p/3\) for regression). A tree that is forbidden from using the dominant feature at the root is forced to find a different — and therefore differently wrong — structure. Individual trees get slightly worse, \(\sigma^2\) rises a little, but \(\rho\) falls a lot, and the product improves.

Two practical consequences. Forests want deep, unpruned trees: the averaging is there to kill variance, so each member should contribute low bias and let the ensemble handle the rest. And roughly \(1 - e^{-1} \approx 63.2\%\) of the data appears in any given bootstrap sample, so the held-out 36.8% gives an out-of-bag error estimate almost for free, without a separate validation split.

Gradient boosting: the other direction

Boosting starts from the opposite diagnosis. Instead of many low-bias models averaged to cut variance, it builds many high-bias models added to cut bias. Trees are fitted sequentially, each one to what the current ensemble is still getting wrong:

The target for tree \(m\) is the negative gradient of the loss with respect to the current prediction — a step of gradient descent, but taken in function space rather than parameter space. For squared error \(L = \tfrac{1}{2}(y - F)^2\) the negative gradient is \(y - F\), the plain residual, which is why boosting is so often introduced as “fit the next tree to the residuals”. That is the special case, not the definition: with log-loss the target is \(y - p\), with absolute error it is \(\operatorname{sign}(y - F)\), and the same machinery accommodates any differentiable loss.

Because each tree is a correction rather than a candidate answer, boosting inverts every setting a forest wants:

The learning rate \(\nu\) shrinks each correction so that no single tree dominates; smaller \(\nu\) needs proportionally more trees and generally generalises better. And since more rounds monotonically reduce training loss, the number of rounds is itself the main regularisation parameter — chosen by early stopping on a validation set, not by running until convergence. A forest cannot overfit by adding trees; a boosted model very much can.

What this does not buy you

No extrapolation. A leaf predicts the mean of the training targets that reached it. Every point beyond the training range falls into the outermost leaf, so the prediction beyond that range is a constant — flat, forever. Fit a tree to \(y = 2x\) on \(x \in [0, 10]\) and ask it about \(x = 50\): it returns roughly the mean of the largest training \(y\) values, not \(100\). This surprises people who have internalised that trees are the strong tabular default, and it rules them out for trending time series unless you difference or detrend first.

No smoothness. The fitted function is piecewise constant. Ensembling averages many step functions into something finer-grained, but it is still steps, and a genuinely smooth low-dimensional response is modelled more efficiently by something that knows about smoothness.

No notion of distance. Trees compare a feature to a threshold; they never compute a similarity between two examples. That is fine for tabular columns with independent meanings and hopeless for raw pixels or characters, where the informative structure is precisely that nearby coordinates relate to one another. Handing a tree 50,000 raw one-hot text columns or a flattened image gives it a vast set of individually near-useless splits. Impurity-based splitting also has a documented bias towards high-cardinality features, which have more candidate thresholds and so more chances to look good by luck — one reason permutation importance is a safer diagnostic than the built-in feature importances.

No causal claim, no free interpretability. A single shallow tree is genuinely readable. Five hundred of them are not, and the fact that a split on a feature helps prediction says nothing about what happens if you intervene on it.

Where they sit

On small and medium tabular problems — tens of thousands of rows, dozens to hundreds of heterogeneous columns, missing values, mixed types — gradient-boosted trees are routinely the strongest thing on the table, and often beat carefully tuned deep networks. The reason is not mysterious: the inductive bias fits the data. Tabular columns are not smooth functions of one another, they are not translation-invariant, and their units are arbitrary. A model built from axis-aligned thresholds on individual columns assumes exactly that, needs no scaling, and handles interactions without being told which ones to look for. Neural networks must learn all of that structure from data they usually do not have enough of.

That is a statement about a matching between model and data, not a ranking of methods. Change the data to pixels, waveforms, or text and the ordering reverses completely, for the same reason: the assumptions no longer match. This is why the book’s overview insists the arrow through these chapters is chronological, not a ladder from worse to better. The correct question is never “which model is best” but “which set of assumptions is true here”.