Gradient Boosting Machines

A random forest tops out at 0.902 AUC on your leaderboard, and the model that beats it uses the same trees — just shallow ones, added one after another, each trained on the mistakes of everything before it. That is gradient boosting, and the question an interviewer will actually ask is: what exactly is each new tree fitting? The answer: the negative gradient of the loss with respect to the current ensemble's prediction. In plain regression with squared error, that gradient is just the residual.

Start with the simplest case. For squared-error regression, the constant that minimizes the loss is the mean, so the initial model is:

F₀(x) = mean(y)

Then repeat for m = 1..M: compute what the ensemble currently gets wrong, fit a shallow tree to it, and add a shrunken correction:

import numpy as np
from sklearn.tree import DecisionTreeRegressor

F = np.full(len(y), y.mean())          # F0
lr = 0.1                                # shrinkage — chapter 2 owns this knob
for m in range(300):
    residual = y - F                    # pseudo-residual: what to fix
    h = DecisionTreeRegressor(max_depth=3, random_state=0)
    h.fit(X, residual)                  # the tree learns the ERROR, not the label
    F += lr * h.predict(X)              # F_m = F_{m-1} + lr * h(x)

Look at the second line inside the loop: h.fit(X, residual). The labels each new tree sees are the ensemble's own mistakes, which is why the trees can be shallow — a depth-3 tree only has to approximate a locally smooth error surface, not carve up the full label structure.

The general rule unifies every loss under one mechanism. At round m, the pseudo-residual for row i is:

gᵢ = −∂L(yᵢ, F) / ∂F  evaluated at F = F_{m−1}

Gradient boosting is gradient descent in function space: instead of nudging weights, each round adds an entire basis function (a tree) stepped in the steepest-descent direction of the loss. If you have ever asked why the same trick does not work for arbitrary black-box losses, that is the answer — you only need a differentiable loss to compute gᵢ.

Why not let each tree take a full step? Because the tree's fit to g is a greedy approximation with real error, and chasing that error fully overfits quickly — this is where the learning rate comes in, and where boosting diverges sharply from the ensemble you just built in Random Forests. Forests fit the labels directly with deep, independent trees and average them to cut variance; boosting fits residuals with shallow, dependent trees and adds them to cut bias. The dependency has a cost: rounds cannot be parallelized the way bagging can (libraries parallelize the histogram search inside one tree, not across rounds), and the order of rounds now matters.

Two practical consequences appear immediately. Training loss decreases monotonically — every round descends the training loss — so a falling training curve tells you nothing about generalization. And because each correction is small and local, boosted ensembles can extrapolate in ways forests cannot: with a linear trend, a boosted model keeps climbing because accumulated shallow corrections sum to a slope, while a forest's leaf averages flatten out.

The learning rate η (sklearn: learning_rate, XGBoost: eta) multiplies every tree's contribution: F_m = F_{m−1} + η·h_m. This single dial, together with n_estimators, is the hyperparameter pair that decides whether your GBM wins or embarrasses you, and they must be tuned together — never one alone.

The intuition for shrinkage comes from what the pseudo-residual actually is. The tree's fit to the residuals is an imperfect, slightly overfit approximation of the true gradient direction. Taking a full step (η = 1) along an approximate gradient chases noise: a depth-3 tree fitted to residuals will happily "correct" error that is really label noise, and the next round has to undo it. Taking a smaller step says: take the honest part of this direction and leave the rest. The cost is obvious — halving η roughly doubles the rounds you need — and that trade is almost always worth it, because many small steps trace a better path through the loss surface than few large ones.

import numpy as np
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import train_test_split

X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=0)

for lr in [0.3, 0.1, 0.03]:
    m = GradientBoostingRegressor(
        n_estimators=5000, learning_rate=lr, max_depth=3,
        subsample=0.8, n_iter_no_change=50, tol=1e-4, random_state=0,
    ).fit(X_tr, y_tr)
    print(f"lr={lr:>4}  rounds used={m.n_estimators_:>4}  test R2={m.score(X_te, y_te):.4f}")

Typical output tells the story: lr=0.3 stops early with decent score, lr=0.03 uses far more rounds and edges it out, and dropping to lr=0.001 will burn thousands of rounds for nothing. The empirical law is more trees at a smaller learning rate beats fewer trees at a larger one, provided you can afford the rounds and you stop before validation turns.

That "stop before" is early stopping, and it is how real GBMs are trained. You hold out a validation set, evaluate the ensemble after every round, and stop when the validation metric has not improved for patience rounds:

# xgboost: model.fit(X_tr, y_tr, eval_set=[(X_val, y_val)],
#                    early_stopping_rounds=50, verbose=False)
# best number of trees = model.best_iteration + 1
#
# lightgbm: callbacks=[lgb.early_stopping(50, first_metric_only=True)]

Watch the two curves while training: training loss falls monotonically forever (boosting descends the training loss every round), while validation loss follows a U-shape — down as the ensemble fits real structure, then up as rounds start memorizing noise. n_estimators in a GBM is therefore not the "more is safer" knob it is in a random forest; it is a budget you fill until the validation curve says stop.

Practical guidance from running that loop: patience of 30–100 rounds, a learning-rate grid of {0.01, 0.03, 0.1}, and one arithmetic fact to keep straight — halving η needs roughly double the rounds to trace the same fit, so shrinking the learning rate without enlarging the round budget just under-trains the model. To see the curve itself without custom loops, sklearn's model.staged_predict(X_val) yields the ensemble's prediction after each added round — the cheapest way to plot the U-shape you are making decisions from.

One more regularization lever worth knowing: subsample < 1.0 trains each round on a random fraction of rows (stochastic gradient boosting). It injects a little bagging-flavored noise between rounds, usually improves generalization slightly, and speeds training — sklearn uses subsample, XGBoost uses subsample, LightGBM uses bagging_fraction/bagging_freq.

The defaults you just saw — max_depth 3–6, learning_rate 0.01–0.1, n_estimators up to early stopping — are the common baseline. The industrial libraries add a second-order layer of controls over exactly this process, and knowing which knob maps to which part of the objective is where interviews separate users from people who understand it.

XGBoost does not merely fit pseudo-residuals; it optimizes a regularized objective with a second-order Taylor expansion, and every hyperparameter you tune maps to a term in it:

L = Σᵢ l(yᵢ, ŷᵢ) + Σₖ Ω(fₖ),   Ω(f) = γ·T + ½·λ·Σⱼ wⱼ²

The first sum is the differentiable loss (squared error, logistic, etc.). The second penalizes each tree: T is its leaf count (penalized by gamma) and Σw² the squared leaf weights (penalized by lambda, the L2 term; alpha is the L1 analogue). Because the algorithm expands l to second order, each round works with per-row gradients gᵢ and Hessians hᵢ, the optimal weight of leaf j is wⱼ* = −Gⱼ/(Hⱼ + λ), and a split is accepted only if its gain exceeds gamma. That machinery explains three things interviewers love: leaves are shrunk by λ in the denominator (heavy L2 → timid corrections), a leaf needs enough summed Hessian min_child_weight to be trustworthy, and splits are explicitly costed before being taken.

The knobs you actually sweep, grouped by what they control:

LightGBM's structural difference deserves its own warning: it grows leaf-wise — it keeps splitting whichever existing leaf reduces loss the most — instead of growing all branches level by level. On sufficient data that reaches lower loss faster and trains quicker (histogram binning plus Gradient-based One-Side Sampling and Exclusive Feature Bundling make it the fastest of the three). But leaf-wise growth can drill a long, thin branch deep into a small region and overfit, so cap it with num_leaves (≤ 2^max_depth) and a healthy min_data_in_leaf, or grow depth-wise for small datasets. CatBoost, the third standard library, attacks a different problem: ordered boosting and ordered target statistics prevent the target leakage that plagues categorical features, so it is usually the best choice when you have high-cardinality categoricals and want minimal preprocessing.

import lightgbm as lgb

params = dict(
    objective="binary", metric="auc",
    learning_rate=0.05, num_boost_round=4000,
    max_depth=6, num_leaves=31, min_data_in_leaf=50,
    feature_fraction=0.8, bagging_fraction=0.8, bagging_freq=1,
    lambda_l2=1.0, verbose=-1,
)
model = lgb.train(params, dtrain, valid_sets=[dval],
                  callbacks=[lgb.early_stopping(50, first_metric_only=True)])
print("best iteration:", model.best_iteration)

Two disciplines matter as much as the parameters. Validate with a split that matches deployment — time-based for temporal data, grouped for repeated entities — because a random split that leaks future rows inflates every metric you tune against. And expect diminishing returns: below ~0.9 AUC, gains come from validation design and features, not from another 0.01 of eta.

Choosing a library when you get one slot in the pipeline: LightGBM for large datasets (roughly >100k rows) where histogram binning and leaf-wise growth pay off in wall-clock time; XGBoost when you want depth-wise control, the widest ecosystem (GPU, distributed training, sklearn-compatible API), and battle-tested defaults; CatBoost when raw categorical columns dominate and your preprocessing budget is near zero. All three converge on the same discipline — the objective machinery above only delivers its gains when best_iteration is selected on a split that resembles deployment, not a convenient random one.

Once the model is trained, it hands you a ranking of features by accumulated split gain — a number that looks authoritative and is quietly biased. Interpreting (and distrusting) that ranking is Tree-Based Feature Importance.