Random forests and gradient boosting

1. Intuition

A single deep tree has low bias but high variance: retrain on slightly different data and it changes a lot.

Bagging (bootstrap aggregating): train many deep trees, each on a random sample of the rows drawn with replacement (a bootstrap sample). Average their predictions (or vote). Individual trees' errors are partly independent, so averaging cancels much of the variance. Random forests add a twist: at each split a tree may consider only a random subset of features, which makes trees more different from each other and the average even more stable.

Boosting: start with a simple prediction (the mean). Fit a small tree to the current errors (residuals). Add a fraction of it (the learning rate) to the ensemble. Repeat hundreds of times. Each tree is weak, but the sum becomes strong. Boosting mainly reduces bias, and it can overfit if you keep adding trees, so you stop early using a validation set.

2. Visualization

Try it (predict first, then check):

1. At round 0 the prediction is a flat line. Predict where the first stump will split, then step to round 1.
2. Set the learning rate to 1.0, then to 0.05. Which reaches its best test error in fewer rounds, and which has the lower best error?
3. At the default settings, push rounds to 200. Predict whether test error turns back up. (Barely: with clean data, stumps overfit slowly.) Now press Too many rounds (noisy data), which raises label noise to σ = 0.6 and η to 1. Find the round where test error was lowest: that's what early stopping picks. What made the difference?

3. The math

Symbols

Bagging

If each tree has variance $\sigma^2$ and pairwise correlation $\rho$, the average has variance $\rho\sigma^2 + \frac{1-\rho}{B}\sigma^2$. More trees shrink the second term; random feature selection lowers $\rho$, shrinking the first.

Gradient boosting

For squared error the residual is exactly the negative gradient of the loss with respect to the prediction, so boosting is gradient descent in function space. Other losses (log loss for classification) replace $r_i$ with their negative gradient. XGBoost and LightGBM also use second derivatives and add regularization on leaf values.

Worked example: three boosting rounds

Data $x = [1, 2, 3, 4]$, $y = [2, 4, 7, 9]$; stumps (depth-1 trees); $\eta = 0.5$.

Round 0. $F_0 = \bar{y} = 5.5$ for every point. MSE $= \frac{3.5^2 + 1.5^2 + 1.5^2 + 3.5^2}{4} = \frac{29}{4} = 7.25$.

Round 1. Residuals $r = y - F_0 = [-3.5, -1.5, 1.5, 3.5]$. The best stump splits at $x \le 2.5$: left mean $-2.5$, right mean $2.5$. $F_1 = 5.5 + 0.5 \times [-2.5, -2.5, 2.5, 2.5] = [4.25, 4.25, 6.75, 6.75]$. MSE $= \frac{2.25^2 + 0.25^2 + 0.25^2 + 2.25^2}{4} = 2.5625$.

Round 2. Residuals $[-2.25, -0.25, 0.25, 2.25]$. Best stump splits at $x \le 1.5$: left $-2.25$, right mean $(-0.25 + 0.25 + 2.25)/3 = 0.75$. $F_2 = [4.25 - 1.125,\; 4.25 + 0.375,\; 6.75 + 0.375,\; 6.75 + 0.375] = [3.125, 4.625, 7.125, 7.125]$. MSE $= 1.2969$.

Round 3. Residuals $[-1.125, -0.625, -0.125, 1.875]$. Split at $x \le 3.5$: left mean $-0.625$, right $1.875$. $F_3 = [2.8125, 4.3125, 6.8125, 8.0625]$. MSE $= 0.4180$.

Each round fixes part of what remains, and the learning rate keeps every correction partial.

4. Implementation

Build it from scratch

Both ensembles reuse the scratch tree from Decision trees (gini, best_split, grow, predict in tree_scratch.py). A forest tree differs in one way. At each split it may only look at max_features randomly chosen columns. That is the decorrelation trick that lowers $\rho$ in the variance formula.

def grow_random(X, y, rng, max_features):
    """A forest tree: like grow(), but each split may only look at max_features random columns."""
    leaf = {"value": int(np.bincount(y, minlength=2).argmax())}
    if gini(y) == 0:
        return leaf
    cols = rng.choice(X.shape[1], max_features, replace=False)
    j, t, _ = best_split(X[:, cols], y)
    if j is None:
        return leaf
    j = cols[j]                                   # map back to the real column
    mask = X[:, j] <= t
    return {"feature": j, "threshold": t,
            "left": grow_random(X[mask], y[mask], rng, max_features),
            "right": grow_random(X[~mask], y[~mask], rng, max_features)}

Predict: if max_features equals the number of columns, how does this differ from plain bagging?

Bagging is the outer loop. Each tree trains on a bootstrap sample: $n$ row indices drawn with replacement. The forest predicts by majority vote.

def random_forest(X, y, n_trees, max_features, rng):
    """Bagging: each tree sees a bootstrap sample (n rows drawn with replacement)."""
    trees = []
    for _ in range(n_trees):
        rows = rng.integers(0, len(y), len(y))
        trees.append(grow_random(X[rows], y[rows], rng, max_features))
    return trees

def forest_predict(trees, X):
    votes = np.array([predict(t, X) for t in trees])   # [n_trees, n_samples]
    return (votes.mean(axis=0) > 0.5).astype(int)      # majority vote for labels 0/1

Predict: about what fraction of the original rows does one bootstrap sample miss? (Each row is missed with probability $(1 - 1/n)^n \approx e^{-1}$.) Those missed rows are the "out-of-bag" set.

Boosting needs a regression stump. It tries each threshold, predicts the mean residual on each side, and keeps the threshold with the smallest squared error.

def fit_stump(x, r):
    """Depth-1 regression tree on one feature: the threshold whose two leaf means minimize squared error."""
    best = (np.inf, None, None, None)
    values = np.unique(x)
    for t in (values[:-1] + values[1:]) / 2:
        left, right = r[x <= t], r[x > t]
        sse = np.sum((left - left.mean()) ** 2) + np.sum((right - right.mean()) ** 2)
        if sse < best[0]:
            best = (sse, t, left.mean(), right.mean())
    _, t, lv, rv = best
    return lambda z: np.where(z <= t, lv, rv), t

Predict: on round 1 of the worked example the residuals are $[-3.5, -1.5, 1.5, 3.5]$. Which threshold wins, and what are the two leaf values?

The boosting loop is the update rule from section 3, line for line: start at the mean, fit the residuals, take a step of size $\eta$.

def gradient_boost(x, y, rounds, lr):
    """F_0 = mean(y); each round fits a stump to the residuals y - F and adds lr * stump."""
    F = np.full(len(y), y.mean())
    history = [F.copy()]
    for _ in range(rounds):
        stump, _ = fit_stump(x, y - F)            # residual y - F = negative gradient of (y - F)^2 / 2
        F = F + lr * stump(x)
        history.append(F.copy())
    return history

Predict: with lr=1.0 instead of 0.5, what is $F_1$? Is the round-1 MSE lower or higher than 2.5625?

Use the library

scikit-learn's RandomForestClassifier and GradientBoostingRegressor/Classifier are these loops in optimized form. XGBoost and LightGBM add second-order gradients, leaf-weight regularization, histogram-binned splits, and early stopping on a validation set.

from sklearn.ensemble import RandomForestClassifier
from xgboost import XGBClassifier           # pip install xgboost

rf = RandomForestClassifier(n_estimators=500, max_features="sqrt", n_jobs=-1, random_state=0)
rf.fit(X_train, y_train)

xgb = XGBClassifier(
    n_estimators=2000, learning_rate=0.05, max_depth=5,
    subsample=0.8, colsample_bytree=0.8,
    early_stopping_rounds=100, eval_metric="logloss",
)
xgb.fit(X_train, y_train, eval_set=[(X_val, y_val)], verbose=False)   # stops when validation loss stalls
print(xgb.best_iteration)

The runnable script checks the scratch code against scikit-learn only, so no extra install is needed.

Run it

From guide/:

uv run code/06-trees-and-ensembles/ensembles_scratch.py

Key output:

round 0: F = [5.5, 5.5, 5.5, 5.5]  MSE 7.2500
round 1: F = [4.25, 4.25, 6.75, 6.75]  MSE 2.5625
round 2: F = [3.125, 4.625, 7.125, 7.125]  MSE 1.2969
round 3: F = [2.8125, 4.3125, 6.8125, 8.0625]  MSE 0.4180
scikit-learn after 3 rounds: [2.8125, 4.3125, 6.8125, 8.0625]

One unlimited tree:       test 0.887
Scratch forest,   1 trees: test 0.873
Scratch forest,  10 trees: test 0.913
Scratch forest, 100 trees: test 0.917
scikit-learn forest, 100:  test 0.917

The boosting rounds reproduce the worked example exactly, and scikit-learn agrees to four decimals. On the synthetic two moons, one forest tree (bootstrap plus random features) is slightly worse than one full tree. Averaging 100 of them beats the single tree by 3 points. The figure and learning-rate curves come from code/06-trees-and-ensembles/trees.py.

5. Engineering

The knobs.

Lower learning rate plus more trees (with early stopping) is the usual recipe.

Random forests need little tuning: more trees never hurts accuracy (only time), and max_features is the main knob. Out-of-bag error gives a free validation estimate.

Which library? LightGBM is fast on large data; CatBoost handles categorical features natively and is robust with defaults; XGBoost is mature and widely deployed.

Interpretation. Impurity-based importances are biased toward high-cardinality features; permutation importance on validation data is more honest. SHAP values attribute each prediction to features additively and are the standard for explaining boosted trees.

An honest note on the figure's data. On the noisy moons dataset in the script, a depth-6 tree, a random forest, and gradient boosting all reach about 0.92 test accuracy. Ensembles don't always win by a large margin on a small, easy 2D problem. Their advantages show up as stability across resamples and on larger, messier, higher-dimensional tables.

Watch out

Failure modes. Boosting for too many rounds without early stopping; tuning on the test set; leakage through target-encoded categoricals; extrapolation (tree ensembles predict constants outside the training range); trusting impurity importance.

Common mistakes

• Treating n_estimators as "more is better" for boosting (it is for forests).
• Scaling features for tree models (unneeded).
• Comparing a tuned XGBoost to an untuned baseline and calling it a fair comparison.

6. Knowledge check

Practice exercise. Data $x = [1, 2]$, $y = [10, 20]$, $\eta = 0.1$, stumps. Compute $F_0$, the first residuals, the stump's predictions, and $F_1$.

Implementation challenge. Implement gradient boosting for regression from scratch using DecisionTreeRegressor(max_depth=2) as the weak learner, then compare its validation MSE curve with scikit-learn's GradientBoostingRegressor using the same settings.

Summary

• Bagging (random forests) averages many decorrelated deep trees and mainly reduces variance.
• Boosting adds small trees fitted to residuals (negative gradients), scaled by a learning rate, and mainly reduces bias.
• Low learning rate plus many trees with early stopping is the standard boosting recipe.
• Gradient-boosted trees are a top baseline for tabular data; explain them with SHAP or permutation importance.

Next: K-means clustering

Related: Decision trees · Gradient descent · Model card: gradient boosting · Model card: XGBoost

Parts of this lesson are adapted from AI Engineering from Scratch by Rohit Ghumare (MIT license, notice): Ensemble Methods.

Interview angle