Decision Trees and Ensembles

Every model so far fits one global formula over the whole predictor space. Decision trees do the opposite: they partition the space into rectangular regions and predict a constant in each. This handles interactions and non-linearities without anyone specifying them, and produces a model you can read aloud - at the cost of being, on its own, distinctly unreliable.

That last weakness turns out to be fixable in a way that makes trees the backbone of some of the strongest general-purpose methods available.

A. How a tree makes predictions

A tree asks a sequence of yes/no questions about the predictors. Each internal node tests one predictor against one threshold; each leaf carries a prediction - the mean of the training responses in that region for regression, the majority class for classification.

Predicting means walking from the root to a leaf. Nothing is computed; you just follow the branches. This is why trees are held up as interpretable: the path is the explanation.

B. Growing the tree

Finding the optimal partition is computationally infeasible, so trees are grown with a greedy procedure called recursive binary splitting.

At each step, consider every predictor $X_j$ and every possible cutpoint $s$, splitting the current region into $\{X_j < s\}$ and $\{X_j \ge s\}$. Choose the pair $(j, s)$ that most improves the criterion, make the split, then repeat independently within each new region.

It is greedy because it takes the best split available now, without checking whether a worse split now would enable a much better one later. It is top-down because it starts at the root and never revisits a decision.

For regression the criterion is RSS, summed over the two child regions:

$$\sum_{i \in R_1}(y_i - \hat y_{R_1})^2 + \sum_{i \in R_2}(y_i - \hat y_{R_2})^2 .$$

C. Splitting criteria for classification

The obvious criterion is the misclassification rate. It turns out to be a poor choice, and seeing why is worth the detour.

The two standard alternatives, for a region with class proportions $\hat p_{mk}$:

$$G = \sum_{k=1}^{K}\hat p_{mk}\big(1 - \hat p_{mk}\big) \qquad\text{(Gini index)},$$ $$D = -\sum_{k=1}^{K}\hat p_{mk}\log \hat p_{mk} \qquad\text{(cross-entropy)} .$$

Both measure node purity: they are near zero when one class dominates and maximal when classes are evenly mixed. Both are also sensitive to changes in the proportions everywhere, whereas the misclassification rate only notices when the majority class flips. A split that redistributes observations without flipping either region's majority leaves the misclassification rate of the majority-vote prediction unchanged, but Gini and cross-entropy both register the real improvement - so they produce better trees.

The figure uses twenty observations, ten per class, a different sample from the ten-point split worked below. Drag the Split threshold: misclassification stays at 0.2000 across the five middle thresholds while the Gini index moves.

D. Working one split by hand

Ten observations, five in each class. A candidate split sends 6 observations left (4 of class 1, 2 of class 0) and 4 right (1 of class 1, 3 of class 0).

For two classes, $G = 2p(1-p)$ where $p$ is the proportion of class 1.

The parent node. $p = 5/10 = 0.5$, so

$$G_{\text{parent}} = 2(0.5)(0.5) = 0.5 ,$$

the maximum possible for two classes - a perfectly mixed node.

Left child. $p = 4/6 = 0.6667$:

$$G_L = 2\left(\tfrac{4}{6}\right)\left(\tfrac{2}{6}\right) = 2 \times \tfrac{8}{36} = 0.4444 .$$

Right child. $p = 1/4 = 0.25$:

$$G_R = 2(0.25)(0.75) = 0.375 .$$

Weighted by region size, since a split's value depends on how many observations it affects:

$$G_{\text{split}} = \frac{6}{10}(0.4444) + \frac{4}{10}(0.375) = 0.2667 + 0.15 = 0.4167 .$$

The improvement:

$$\Delta G = 0.5 - 0.4167 = 0.0833 .$$

The tree-growing algorithm computes exactly this for every $(j, s)$ pair and takes the largest $\Delta G$.

E. Why a single tree is unreliable

Grown far enough, a tree can isolate every training observation in its own leaf and achieve zero training error. That is pure overfitting. But even a well-pruned tree has a deeper problem: high variance.

Because splitting is greedy and hierarchical, a small change in the data can change the root split - and every split beneath it is then chosen on differently partitioned data. Two random halves of the same dataset can produce trees that look nothing alike. In the language of The Bias-Variance Tradeoff, trees sit at the low-bias, high-variance extreme.

F. Bagging: averaging the variance away

If a method has high variance, average many instances of it. For $B$ independent fits each with variance $\sigma^2$, the mean has variance $\sigma^2/B$.

We only have one dataset, so bagging (bootstrap aggregation) manufactures many: draw $B$ bootstrap samples - sampling $n$ observations with replacement - grow a deep, unpruned tree on each, and average the predictions (or take a majority vote).

Deep trees are exactly right here. Each has low bias and high variance, and averaging attacks the variance while leaving the low bias intact.

Bagging also comes with a free validation set. Each bootstrap sample omits about a third of the observations - the probability a given observation is missed is $(1 - 1/n)^n \to e^{-1} \approx 0.368$. Predicting each observation using only the trees that did not see it gives the out-of-bag error estimate, at no extra computational cost.

G. Random forests: decorrelating the trees

Bagging has a limit. If one predictor is strongly dominant, it will be the root split in nearly every bootstrap sample, so the trees are highly correlated - and averaging correlated quantities reduces variance far less than averaging independent ones. (The same fact explained why LOOCV is noisier than 10-fold in Cross-Validation and Resampling.)

Random forests add one deliberate handicap: at each split, only a random subset of $m$ predictors is even considered, typically $m \approx \sqrt{p}$ for classification. Most splits cannot use the dominant predictor at all, so other predictors get their turn, the trees become genuinely different, and the average is far more effective.

It is a striking idea: each individual tree is made worse on purpose, and the ensemble is better for it.

H. What you trade away

The interpretability that motivated trees is gone the moment you average hundreds of them. Variable-importance measures - how much each predictor reduced Gini across the forest - recover a summary, but not the readable if-then path.

Importance scores are not causal. A predictor can rank highly because it is correlated with the true driver, and impurity-based importance is biased towards high-cardinality predictors. Treat them as a description of what the model used, not of what matters in the world.

Key takeaways

• Trees partition the predictor space and predict a constant per region, grown by greedy recursive binary splitting.
• Gini and cross-entropy beat misclassification rate as splitting criteria because they respond to purity changes that do not flip the majority.
• Our worked split: parent Gini $0.5$, children $0.4444$ and $0.375$, weighted $0.4167$, gain $0.0833$.
• Single trees are low-bias, high-variance - unstable under small data changes.
• Bagging averages deep trees over bootstrap samples, with out-of-bag error free; random forests additionally restrict each split to $m \approx \sqrt p$ predictors to decorrelate the trees.
• The ensemble buys accuracy with interpretability.

What's next

Trees carve the input space with axis-aligned cuts. A different family builds flexible functions by composing simple non-linear transformations, and learns them by following the gradient of the error. That is Backpropagation and Gradient Descent.