ML from Scratch · Lecture 1 of 5

Decision Trees (CART) and Random Forests

Recursive yes/no questions, the impurity measures that choose them, why a single deep tree overfits, and how averaging many randomised trees fixes it.

A tree is a sequence of questions

A decision tree splits the feature space with axis-aligned questions ("is income ≤ 40k?") until each region is pure enough, then predicts the majority class (classification) or the mean (regression) in that region. CART, Classification And Regression Trees (Breiman et al., 1984), grows the tree greedily, one best split at a time.

Choosing a split: impurity

For a node with class proportions $p_k$, common impurity measures are

A split sends $n_L$ points left and $n_R$ right. CART picks the feature $j$ and threshold $t$ that maximise the impurity decrease:

For each feature, sort its values and try every midpoint between consecutive distinct values. With running counts this is $O(n\log n)$ per feature per node.

From scratch in Python

def gini(y):
    p = np.bincount(y, minlength=2) / len(y)
    return 1 - (p ** 2).sum()

def best_split(X, y):
    best = (None, None, gini(y))           # feature, threshold, impurity
    for j in range(X.shape[1]):
        order = np.argsort(X[:, j]); xs, ys = X[order, j], y[order]
        for i in range(1, len(ys)):
            if xs[i] == xs[i - 1]: continue
            imp = (i * gini(ys[:i]) + (len(ys) - i) * gini(ys[i:])) / len(ys)
            if imp < best[2]: best = (j, (xs[i] + xs[i - 1]) / 2, imp)
    return best

def grow(X, y, depth):
    j, t, _ = best_split(X, y)
    if depth == 0 or j is None: return {"leaf": y.mean()}
    m = X[:, j] <= t
    return {"j": j, "t": t, "l": grow(X[m], y[m], depth - 1), "r": grow(X[~m], y[~m], depth - 1)}

Increase the depth. Training accuracy climbs towards 100% as the tree builds tiny boxes around individual noisy points, but test accuracy peaks and then falls. A single deep tree has low bias and high variance: a slightly different training set gives a very different tree.

Controlling a single tree

• Pre-pruning: max depth, minimum samples per leaf, minimum impurity decrease.
• Cost-complexity pruning: grow fully, then minimise $\text{error}+\alpha\cdot|\text{leaves}|$, choosing α by cross-validation.

Trees are interpretable, need no feature scaling, and handle mixed types and interactions naturally. But they're unstable, and their decision boundaries are staircases.

Random forests: averaging away variance

If $B$ predictors each have variance $\sigma^2$ and pairwise correlation $\rho$, their average has variance

Averaging kills the second term. To shrink the first term we must decorrelate the trees. A random forest does both:

1. Bootstrap: each tree is trained on $n$ points drawn with replacement (bagging). About 63% of points appear in each sample.
2. Feature subsampling: at each split only a random subset of $m$ features is considered (typically $\sqrt p$ for classification, $p/3$ for regression). Strong features can't dominate every tree, so the trees disagree in useful ways.
3. Average the predictions (or majority vote).

With one tree the boundary is blocky and overfit. Add trees and it becomes a smooth, round boundary, and test accuracy improves without any pruning.

Free extras

• Out-of-bag (OOB) error: each point is left out by about 37% of the trees. Predict it with only those trees to get a built-in validation estimate.
• Feature importance: total impurity decrease per feature, or (better) permutation importance, the drop in OOB accuracy when a feature is shuffled.