Boosting II: Gradient Boosting Machines

Gradient boosting is the workhorse behind countless winning solutions on tabular data — in credit risk, click prediction, demand forecasting and data-science competitions. Jerome Friedman's 1999 insight was to view boosting as gradient descent, not in parameter space, but in function space. Once you see it that way, you can boost with any differentiable loss.

The additive model#

We build a model as a sum of $M$ simple functions (usually small regression trees):

where $\nu \in (0, 1]$ is the learning rate (shrinkage). Each new tree $h_m$ should move $F$ in the direction that decreases the loss most.

Functional gradient descent#

Our objective is $\sum_i L(y_i, F(\mathbf{x}_i))$. Treat the predictions $F(\mathbf{x}_i)$ as the variables. The steepest-descent direction for each training point is the negative gradient, called the pseudo-residual:

But a gradient defined only at training points does not generalise. So we fit a regression tree $h_m$ to the pseudo-residuals — it approximates the gradient direction as a function that can be evaluated anywhere.

The algorithm#

1. Initialise with the best constant: $F_0 = \arg\min_c\sum_iL(y_i, c)$ (the mean for squared loss; the log-odds for logistic loss).
2. For $m = 1, \dots, M$:
   1. Compute pseudo-residuals $r_{im}$.
   2. Fit a regression tree $h_m$ to $\{(\mathbf{x}_i, r_{im})\}$ with $J$ leaves.
   3. For each leaf $j$, compute the optimal output $\gamma_{jm} = \arg\min_\gamma\sum_{\mathbf{x}_i \in R_{jm}}L(y_i, F_{m-1}(\mathbf{x}_i) + \gamma)$ (a line search per leaf).
   4. Update $F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \nu\sum_j\gamma_{jm}\mathbb{1}[\mathbf{x} \in R_{jm}]$.

Pseudo-residuals for common losses#

For squared loss, gradient boosting is intuitive: each tree fits the residual errors of the current model. For other losses, "residual" generalises to "negative gradient".

From scratch (squared loss)#

import numpy as np
from sklearn.tree import DecisionTreeRegressor

class GBRegressor:
    def __init__(self, n_trees=300, lr=0.05, depth=3):
        self.n_trees, self.lr, self.depth = n_trees, lr, depth
    def fit(self, X, y):
        self.f0 = y.mean()
        F = np.full(len(y), self.f0)
        self.trees = []
        for _ in range(self.n_trees):
            residual = y - F                               # negative gradient of 0.5*(y-F)^2
            t = DecisionTreeRegressor(max_depth=self.depth).fit(X, residual)
            F += self.lr * t.predict(X)
            self.trees.append(t)
        return self
    def predict(self, X):
        return self.f0 + self.lr * sum(t.predict(X) for t in self.trees)

rng = np.random.default_rng(0)
X = rng.uniform(-3, 3, (800, 2))
y = np.sin(X[:, 0]) * np.cos(X[:, 1]) + 0.1 * rng.normal(size=800)
m = GBRegressor().fit(X[:600], y[:600])
print("test RMSE:", np.sqrt(np.mean((m.predict(X[600:]) - y[600:]) ** 2)).round(4))

Regularisation: the key to good generalisation#

Unlike random forests, gradient boosting will overfit if you keep adding trees. Controls:

1. Shrinkage ($\nu$): small learning rates (0.01–0.1) need more trees but generalise better. Friedman found shrinkage to be the single most effective regulariser.
2. Number of trees $M$: choose by early stopping on validation data.
3. Tree size: depth 3–8 (or 8–64 leaves). Depth controls the order of interactions the model can capture — depth 1 (stumps) gives an additive model.
4. Stochastic gradient boosting: fit each tree on a random subsample (e.g. 50–80%) of rows — reduces variance and speeds training.
5. Column subsampling, minimum samples per leaf, and L1/L2 penalties on leaf values (in modern libraries).

from sklearn.ensemble import HistGradientBoostingRegressor
from sklearn.model_selection import train_test_split
from sklearn.datasets import fetch_california_housing
from sklearn.metrics import mean_absolute_error

X, y = fetch_california_housing(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)
gb = HistGradientBoostingRegressor(learning_rate=0.05, max_iter=2000, max_leaf_nodes=31,
                                   early_stopping=True, validation_fraction=0.1,
                                   n_iter_no_change=50, random_state=0).fit(X_tr, y_tr)
print("trees used:", gb.n_iter_, " test MAE:", round(mean_absolute_error(y_te, gb.predict(X_te)), 3))

Why gradient boosting dominates tabular data#

• Trees handle heterogeneous features, missing values, monotonic and non-linear relationships and interactions.
• Boosting reduces bias progressively while regularisation controls variance.
• Flexible losses fit many business objectives (ranking, quantiles, Poisson counts).
• Benchmarks comparing tree ensembles and deep networks on typical medium-sized tabular datasets have repeatedly found tree-based boosting to be highly competitive or superior, especially with limited tuning time.