Machine Learning from First Principles

Chapter 10 · Part II: Supervised Learning

Decision Trees and Ensembles

A tree asks a few yes/no questions about the features. One tree is easy to read but unstable. Hundreds of trees, averaged or added up cleverly, give random forests and gradient boosting: still the strongest methods for spreadsheet-style data.

After this chapter you will be able to

  • Describe how a tree predicts with a sequence of axis-aligned questions.
  • Compute entropy, Gini impurity, and information gain to choose splits.
  • Grow a tree greedily and control its depth to avoid overfitting.
  • Explain and derive why averaging trees (bagging, random forests) reduces variance.
  • Describe gradient boosting as gradient descent in function space.

10.1Decision Trees

Each internal node tests one feature against a threshold ("income > 52,000?"), and each leaf predicts the majority class or mean target of the training examples that reach it. Trees need no feature scaling, mix numeric and categorical features, capture interactions automatically, and are easy to explain. Geometrically, a tree cuts feature space into axis-aligned boxes and predicts a constant in each. A deep enough tree gives every training point its own box: the overfitting regime.

10.2Choosing Splits: Impurity

For class proportions $p_1, \dots, p_K$ in a node:

  • Entropy $H = -\sum_k p_k\log_2 p_k$: 0 when pure, $\log_2 K$ when evenly mixed.
  • Gini $G = 1 - \sum_k p_k^2$: the chance that two random examples from the node disagree.
  • Misclassification $1 - \max_k p_k$: intuitive, but blind to purity gains that don't change the majority, so a poor criterion.

A split's impurity decrease (information gain, for entropy) weights the children by size:

$$\Delta = I(\text{parent}) - \frac{n_L}{n}I(\text{left}) - \frac{n_R}{n}I(\text{right}). \tag{10.1}$$

Example: information gain

A node with $10^+, 10^-$ has $H = 1$ bit. Split A gives $(8^+,2^-)$ and $(2^+,8^-)$, each $H\approx 0.722$: gain 0.278. Split B gives $(10^+,6^-)$ and $(0^+,4^-)$: gain $1 - \frac{16}{20}\cdot0.954 = 0.237$. A wins.

Regression trees use the variance of the targets as impurity. To find a split, sort by each feature and sweep the midpoints between consecutive values, updating counts incrementally.

10.3Growing and Pruning

Algorithm 10.1  Growing a tree (CART-style)
  1. Grow($S$, depth): if $S$ is pure, depth = max, or $|S|$ too small, return a leaf.
  2. Pick the split $(j, t)$ with the largest $\Delta$.
  3. return node($j$, $t$, Grow($S_{x_j\le t}$), Grow($S_{x_j > t}$)).

Greedy growth is not optimal (the best tree is NP-hard to find) but works well. Control capacity with maximum depth, minimum leaf size, or minimum gain, or grow large and prune back with cost-complexity pruning tuned by cross-validation.

10.4Bagging and Random Forests

A deep tree has low bias and high variance. Averaging reduces variance, but only the part the models do not share. For $B$ predictions with variance $\sigma^2$ and pairwise correlation $\rho$:

$$\Var\Big(\frac1B\sum_{b=1}^B Z_b\Big) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2. \tag{10.2}$$
  • Bagging: train deep trees on bootstrap samples (draw $n$ examples with replacement; about 63% are distinct) and average.
  • Random forests: also consider only a random subset of $m\approx\sqrt d$ features at each split, lowering $\rho$.
  • Out-of-bag error: each example is missing from about 37% of bootstrap samples; predicting it with those trees gives a free test-error estimate.
  • Importance: impurity-based importances are quick but biased; permutation importance is more reliable.

10.5Boosting

Boosting trains shallow trees sequentially, each correcting the ensemble so far. For squared error: start from $F_0 = \bar y$; at stage $m$ fit a small tree $h_m$ to the residuals $r^{(i)} = y^{(i)} - F_{m-1}(\vx^{(i)})$ and update

$$F_m(\vx) = F_{m-1}(\vx) + \nu\,h_m(\vx), \qquad \nu\approx 0.05\text{–}0.1. \tag{10.3}$$

Why "gradient"? The residual is exactly $-\partial\ell/\partial F(\vx^{(i)})$ for $\ell = \tfrac12(y - F)^2$, so each stage is a gradient-descent step in function space. For any differentiable loss, fit each tree to the negative gradient. XGBoost, LightGBM, and CatBoost add Newton steps, leaf regularization, and missing-value handling; on tabular data they are the method to beat.

Key idea: two routes to a strong ensemble

Bagging and forests reduce variance by averaging independent deep trees. Boosting reduces bias by adding shallow trees fitted to what remains wrong. Forests need little tuning; boosting is usually more accurate but needs its learning rate, depth, and number of trees tuned with early stopping.

10.6AdaBoost

Can a weak learner that barely beats chance be boosted into an accurate classifier? AdaBoost (Freund and Schapire 1997) answered yes. Labels are $\pm1$; weak learners are usually decision stumps (one split).

Algorithm 10.2  AdaBoost
  1. Input: data $(\vx^{(i)},y^{(i)})$ with $y^{(i)}\in\{-1,+1\}$, rounds $M$
  2. $w_i\gets1/n$ for all $i$ example weights
  3. for $m=1,\dots,M$:
    1. fit $h_m$ minimizing $\varepsilon_m=\sum_iw_i\,\mathbb 1[h_m(\vx^{(i)})\ne y^{(i)}]$
    2. $\alpha_m\gets\frac12\log\frac{1-\varepsilon_m}{\varepsilon_m}$ vote of this learner
    3. $w_i\gets w_i\exp(-\alpha_m y^{(i)}h_m(\vx^{(i)}))$, then normalize
  4. return $\sign(F_M(\vx))$ with $F_M=\sum_m\alpha_mh_m$

Misclassified examples gain weight by $e^{\alpha_m}=\sqrt{(1-\varepsilon_m)/\varepsilon_m}$, so the next learner focuses on them; after the update the current learner has weighted error exactly $\frac12$, so the next must find something new.

Theorem 10.1 (AdaBoost's training error)

With edge $\gamma_m=\frac12-\varepsilon_m$,

$$\frac1n\sum_{i}\mathbb 1\big[\sign F_M(\vx^{(i)})\ne y^{(i)}\big]\ \le\ \prod_{m=1}^M2\sqrt{\varepsilon_m(1-\varepsilon_m)}\ \le\ \exp\Big(-2\sum_m\gamma_m^2\Big). \tag{10.4}$$

A fixed edge $\gamma$ gives training error below $e^{-2\gamma^2M}$. The proof bounds $\mathbb 1[yF<0]\le e^{-yF}$ and notes that round $m$'s weight normalizer is $2\sqrt{\varepsilon_m(1-\varepsilon_m)}$.

The statistical view. AdaBoost is forward stagewise fitting of the exponential loss $\sum_ie^{-y^{(i)}F(\vx^{(i)})}$ (Friedman, Hastie, and Tibshirani 2000): the weights are each example's current loss and $\alpha_m$ is an exact line search. So it is gradient boosting with a particular loss, whose minimizer is half the log-odds. The exponential growth for badly misclassified points makes it sensitive to label noise; gradient boosting with logistic loss is more robust. Its test error often keeps falling after training error hits zero, because later rounds keep enlarging the normalized margins $yF_M(\vx)/\sum_m\alpha_m$ (Schapire et al. 1998): the same margin idea as SVMs (Chapter 9, Chapter 11).

10.7Implementation

import numpy as np

def gini(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / len(y)
    return 1 - np.sum(p**2)

def best_split(X, y):
    best, parent = (0.0, None, None), gini(y)
    for j in range(X.shape[1]):
        values = np.unique(X[:, j])
        for t in (values[:-1] + values[1:]) / 2:
            left = X[:, j] <= t
            gain = parent - (left.sum() * gini(y[left]) + (~left).sum() * gini(y[~left])) / len(y)
            if gain > best[0]:
                best = (gain, j, t)
    return best

def grow(X, y, depth=0, max_depth=5, min_samples=2):
    gain, j, t = best_split(X, y) if len(y) >= min_samples else (0, None, None)
    if depth == max_depth or j is None:
        return np.bincount(y).argmax()
    left = X[:, j] <= t
    return (j, t, grow(X[left], y[left], depth + 1, max_depth, min_samples),
                  grow(X[~left], y[~left], depth + 1, max_depth, min_samples))

def predict_one(node, x):
    while isinstance(node, tuple):
        j, t, l, r = node
        node = l if x[j] <= t else r
    return node

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, HistGradientBoostingClassifier

X, y = load_breast_cancer(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
tree = DecisionTreeClassifier(max_depth=5, random_state=0).fit(Xtr, ytr)
forest = RandomForestClassifier(n_estimators=300, oob_score=True, random_state=0).fit(Xtr, ytr)
gbm = HistGradientBoostingClassifier(learning_rate=0.1, max_iter=500,
                                     early_stopping=True, random_state=0).fit(Xtr, ytr)
print("OOB accuracy:", round(forest.oob_score_, 3))
for name, m in [("tree", tree), ("forest", forest), ("boosting", gbm)]:
    print(f"{name:8s} test accuracy {m.score(Xte, yte):.3f}")

10.8Common Pitfalls

Pitfall: trusting impurity-based importances

They favor features with many distinct values. Use permutation importance on validation data.

Pitfall: boosting without early stopping

Every stage lowers training loss forever. Stop when validation loss stops improving.

10.9Summary

  • A tree partitions space into axis-aligned boxes with a constant prediction in each.
  • Splits greedily maximize impurity decrease (entropy, Gini, or variance).
  • Limit depth or leaf size, or prune, to avoid overfitting.
  • Averaging leaves variance $\rho\sigma^2 + (1-\rho)\sigma^2/B$; random forests lower $\rho$.
  • Gradient boosting fits shallow trees to the negative gradient; it leads on tabular data.
  • AdaBoost reweights examples toward current mistakes and combines weak learners with votes $\alpha_m=\frac12\log\frac{1-\varepsilon_m}{\varepsilon_m}$; its training error falls exponentially when each learner beats chance, and it is stagewise fitting of the exponential loss.

10.10Exercises

  1. MathFor two classes, show Gini $= 2p(1-p)$ and plot it with entropy. Find a split that improves purity without changing either child's majority.
  2. MathDerive Equation (10.2).
  3. MathShow that the chance an example is absent from a bootstrap sample is $(1-1/n)^n\to e^{-1}$.
  4. MathFor $\ell(y,F) = \log(1 + e^{-yF})$ with $y\in\{\pm1\}$, compute the negative gradient boosting fits.
  5. CodingPlot train and test accuracy against max_depth on load_breast_cancer, then add bagging with 50 trees.
  6. CodingImplement gradient boosting with depth-2 regression trees; compare $\nu = 0.1$ and $\nu = 1$ over 500 stages.
  7. MathShow that after round $m$'s update $h_m$ has weighted error exactly $\frac12$, that the normalizer equals $2\sqrt{\varepsilon_m(1-\varepsilon_m)}$, and that $\alpha_m$ minimizes it.
  8. CodingImplement AdaBoost with stumps and compare with AdaBoostClassifier(DecisionTreeClassifier(max_depth=1)) on make_hastie_10_2. Plot training error, test error, and bound (10.4) against rounds, then repeat with 10% of training labels flipped.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.