42  Trees & Ensembles

← Back to: Classical ML Overview

TipTL;DR

A decision tree splits the feature space with axis-aligned rules; it is interpretable but high-variance. Random forests (Breiman, 2001) average many decorrelated trees to cut variance, and gradient boosting (Friedman, 2001) fits trees sequentially to the residual error. Boosted-tree libraries (XGBoost (Chen & Guestrin, 2016)) remain the state of the art on tabular data in 2026 — the clearest place neural nets did not win.

42.1 Decision trees

A tree recursively partitions the data, choosing at each node the split that most reduces impurity — Gini or entropy for classification, variance for regression:

\[ \text{Gini}(S) = 1 - \sum_c p_c^2. \]

Trees are interpretable (a path is a rule list), handle mixed feature types natively, and need no scaling. Their weakness is variance: a deep tree memorizes the training set and a small data change reshapes it entirely. The two ensemble families below both exist to tame that variance.

42.2 Random forests: bagging decorrelated trees

Train many trees, each on a bootstrap sample of the rows and a random subset of features at each split, then average their predictions:

\[ \hat y = \frac{1}{T}\sum_{t=1}^{T} f_t(x). \]

Bootstrapping + feature subsampling decorrelates the trees, so averaging collapses variance without inflating bias. Robust, hard to overfit, and almost parameter-free — a strong default.

42.3 Gradient boosting: sequential residual fitting

Boosting builds the ensemble additively: each new tree fits the gradient of the loss left over by the current model:

\[ F_m(x) = F_{m-1}(x) + \nu\, h_m(x), \qquad h_m \approx -\nabla_F \mathcal{L}\big(y, F_{m-1}(x)\big), \]

with learning rate \(\nu\). This is gradient descent in function space — the same optimization logic as neural training, but the “step” is a small tree rather than a parameter update. XGBoost/LightGBM add regularization, second-order information, and engineering that make them the production tabular workhorse.

tree 1 + tree 2 + tree 3 → … each tree fits the previous model's residual error

42.4 Timeline context

This is the honest counterweight to the deep-learning narrative: on tabular, heterogeneous, structured data — most of enterprise ML — gradient-boosted trees still beat neural nets in accuracy, training cost, and ease of tuning. Deep learning won perception and language; trees still own the spreadsheet.

NoteKey takeaway

Trees split, ensembles average or boost away their variance. Random forests decorrelate-and-average; gradient boosting does gradient descent in function space one tree at a time. Their continued dominance on tabular data is the sharpest reminder that “deep learning won everything” is a perception/language story, not a universal one.

← Back to: Classical ML Overview