Gradient boosting

Bagging and random forests, in the previous note, average trees that were grown independently. Averaging keeps the bias of a single tree and lowers only its variance, so it needs deep, low-bias trees, and it can do nothing about a systematic error that all trees share. Boosting builds the ensemble the other way round. The trees are small and grown one after another, and each new tree is fitted to what the current ensemble still gets wrong. The sum of many weak trees then has a low bias, and the variance is controlled by keeping each step small and stopping in time. Friedman (2001) showed that this is gradient descent, carried out in a space of functions instead of a space of parameters, which makes it work for any differentiable loss. Gradient-boosted trees, in the implementations XGBoost, LightGBM and CatBoost, are the default method for tabular data.

Notation. $L(y, F)$ is a differentiable loss of a prediction $F$ (a number: a regression value, or a log-odds for classification). The model after $m$ stages is $F_m(x) = F_0 + \nu \sum_{k=1}^m b_k(x)$, where $F_0$ is the best constant, $b_k$ a regression tree (the base learner) and $\nu \in (0, 1]$ the learning rate. At stage $m$, $g_i = \partial L(y_i, F) / \partial F$ and $h_i = \partial^2 L(y_i, F) / \partial F^2$ are evaluated at $F = F_{m-1}(x_i)$. A tree with $J$ leaves has regions $R_1, \dots, R_J$ and leaf values $w_1, \dots, w_J$.

Fitting residuals#

Start with squared loss and the constant model $F_0 = \bar y$. Its errors on the training set are the residuals $r_i = y_i - F_0$. A tree $b_1$ fitted to the residuals by least squares predicts where the model is too low and where too high, so $F_1 = F_0 + \nu b_1$ is closer to the data; the new residuals $y_i - F_1(x_i)$ are fitted by $b_2$, and so on. A toy example with four points, $x = 1, 2, 3, 4$ and $y = 1, 3, 4, 8$, stumps and $\nu = 0.5$: $F_0 = 4$ and the residuals are $-3, -1, 0, 4$. The best stump splits between 3 and 4, predicting $-4/3$ on the left and $4$ on the right, so $F_1 = (3.333, 3.333, 3.333, 6)$ and the training MSE falls from $6.5$ to $2.5$. Two more stumps bring it to $1.139$ and $0.470$.

Figure

Boosting stage by stage

The figure runs the same procedure on 50 noisy points of a sine:

1. The first stump splits the residuals of the constant model into a positive and a negative half; half of it is added to the model.
2. The residuals of $F_1$ still have a clear shape, and the second stump fits it.
3. After five stages the model has six steps and the residuals are small.
4. After forty, the model follows the sine and the residuals look like noise. Continued, boosting would fit that noise too: the training error, $0.055$, is already below the noise variance $0.09$.

Each tree is weak, a single split, and the training loss of the sum falls with every stage; the bias typically falls with it, while the test error falls only until the stages start fitting noise. This is the opposite of bagging, where the trees are strong and the sum only averages them.

Gradient descent in function space#

Why residuals, and what replaces them for other losses? The training loss

$$Q(F) = \sum_{i=1}^n L\big(y_i, F(x_i)\big)$$

depends on the function $F$ only through its $n$ values $F(x_1), \dots, F(x_n)$. Treat these values as parameters. Gradient descent on them, as in the gradient descent note, moves each value against the partial derivative of $Q$:

$$F(x_i) \leftarrow F(x_i) - \eta \, g_i , \qquad g_i = \frac{\partial L(y_i, F)}{\partial F}\Big|_{F = F_{m-1}(x_i)} .$$

For squared loss $L = \frac12 (y - F)^2$, the negative gradient $-g_i = y_i - F_{m-1}(x_i)$ is exactly the residual: fitting residuals is gradient descent. But this step is defined only at the training points, and the model must predict everywhere. Friedman’s solution is to replace the vector $-g$ by the closest function in the base class, fitting a tree to the pseudo-residuals $-g_i$ by least squares (Friedman, 2001, Section 3, Eq. 11):

$$b_m = \arg\min_{b} \sum_{i=1}^n \big(-g_i - b(x_i)\big)^2 .$$

Why does this step lower the loss? By a first-order Taylor expansion, adding $\varepsilon b$ changes the loss by

$$Q(F_{m-1} + \varepsilon b) - Q(F_{m-1}) \approx \varepsilon \sum_{i=1}^n g_i \, b(x_i) ,$$

which is negative, and steepest, when the vector $(b(x_1), \dots, b(x_n))$ points along $-g$. Among the functions of the base class, the least-squares fit to $-g$ is the one most nearly parallel to it, the member “most highly correlated with $-g$” in Friedman’s words. The tree only chooses the direction; how far to go is a separate one-dimensional problem. With trees it is solved in each leaf separately, since the leaves do not overlap:

$$w_j = \arg\min_{w} \sum_{x_i \in R_j} L\big(y_i, F_{m-1}(x_i) + w\big) ,$$

and the model takes the shrunken step $F_m = F_{m-1} + \nu \sum_j w_j [x \in R_j]$. This is Friedman’s TreeBoost, Algorithm 10.3 of Hastie, Tibshirani and Friedman (2009). The structure of the tree is chosen with squared error on the pseudo-residuals, whatever the loss, and the loss enters twice: in the pseudo-residuals and in the leaf values.

Losses#

Changing the loss changes the pseudo-residuals and the leaf values, and nothing else. The best constant prediction under each loss is the summary of the conditional distribution from the conditional expectation note, and $F_0$ is that summary of all targets.

Loss $L(y, F)$	Pseudo-residual $-g$	Leaf value	Predicts
squared $\frac12 (y - F)^2$	$y - F$	mean of residuals	conditional mean
absolute $\lvert y - F \rvert$	$\operatorname{sign}(y - F)$	median of residuals	conditional median
Huber	residual, clipped at $\delta$	Huber location of residuals	robust mean
pinball at level $q$	$q$ or $q - 1$	$q$-quantile of residuals	conditional $q$-quantile
log-loss, $y \in \{0, 1\}$, $p = \sigma(F)$	$y - p$	Newton step $\frac{\sum (y_i - p_i)}{\sum p_i (1 - p_i)}$	log-odds
Poisson, $F = \log \mu$	$y - e^F$	$\log \frac{\sum y_i}{\sum e^{F_i}}$	log-mean of counts

For log-loss, $F$ is a log-odds as in logistic regression, and $L = -y \log p - (1 - y) \log(1 - p)$ with $p = 1/(1 + e^{-F})$. Its derivatives in $F$ are $g = p - y$ and $h = p(1 - p)$, so the pseudo-residual is the gap between the label and the predicted probability. The leaf value has no closed form, and one Newton step from $w = 0$, $-\sum g_i / \sum h_i$, replaces it (Friedman, 2001, Algorithm 5, written there with $y \in \{-1, 1\}$ and half the log-odds). Every pseudo-residual lies in $(-1, 1)$: a badly misclassified point pulls with weight at most one. The exponential loss $e^{-yF}$, $y \in \{-1, 1\}$, gives AdaBoost (Freund and Schapire, 1997; Friedman, Hastie and Tibshirani, 2000); its pseudo-residuals $y \, e^{-yF}$ grow without bound on misclassified points, which makes it sensitive to label noise (Hastie, Tibshirani and Friedman, 2009, Section 10.6).

Shrinkage, tree size and subsampling#

Boosting drives the training loss down fast, and with it it fits the noise. Three controls slow it down.

• Shrinkage. The learning rate $\nu$ scales each tree. Smaller $\nu$ needs more trees to reach the same training loss, and in practice usually gives lower test error, an empirical regularity rather than a theorem; the recommended strategy is a small $\nu$, $0.1$ or less, with the number of trees chosen by early stopping (Friedman, 2001, Section 5; Hastie, Tibshirani and Friedman, 2009, Section 10.12.1). On Friedman’s function in 10 dimensions with 500 training points and depth-3 trees, $\nu = 1$ reaches its best validation MSE, $5.72$, after 8 trees and is at $6.75$ after 1000; $\nu = 0.1$ reaches $2.71$ after 189 trees, with test MSE $2.66$.
• Tree size. A tree with $J$ leaves can represent interactions of at most $J - 1$ features, and so can a sum of such trees. Stumps give an additive model. Experience suggests $4 \le J \le 8$ (Hastie, Tibshirani and Friedman, 2009, Section 10.11): small trees have high bias and low variance, which is what boosting needs, the opposite of the deep trees of a forest.
• Subsampling. Stochastic gradient boosting grows each tree on a random fraction of the training points drawn without replacement, typically one half (Friedman, 2002; Hastie, Tibshirani and Friedman, 2009, Section 10.12.2). It is faster and often more accurate: as in bagging, the randomness of the samples lowers the variance. In the example above, subsampling half of the rows lowers the best validation MSE from $2.71$ to $2.38$. XGBoost adds column subsampling, borrowed from random forests (Chen and Guestrin, 2016, Section 2.3).

Second-order boosting: XGBoost#

Gradient boosting fits the tree with squared error on the gradient, an approximation that the leaf step then corrects. XGBoost (Chen and Guestrin, 2016) builds the tree for the actual loss from the start, using a second-order expansion, and adds a penalty on the tree. The objective at stage $m$ is

$$\sum_{i=1}^n L\big(y_i, F_{m-1}(x_i) + b(x_i)\big) + \gamma J + \frac{\lambda}{2} \sum_{j=1}^J w_j^2 ,$$

with a price $\gamma$ per leaf and an $L_2$ penalty $\lambda$ on the leaf values (Eq. 2). Expanding the loss to second order in $b(x_i)$ and dropping the constant,

$$\sum_{i=1}^n \Big[ g_i \, b(x_i) + \frac12 h_i \, b(x_i)^2 \Big] + \gamma J + \frac{\lambda}{2} \sum_j w_j^2 .$$

A tree is constant on each leaf, $b(x_i) = w_j$ for $x_i \in R_j$, so with $G_j = \sum_{x_i \in R_j} g_i$ and $H_j = \sum_{x_i \in R_j} h_i$ the objective is a sum of independent parabolas, $\sum_j [G_j w_j + \frac12 (H_j + \lambda) w_j^2] + \gamma J$. Each is minimized by

$$w_j^* = -\frac{G_j}{H_j + \lambda} , \qquad \text{with value} \quad -\frac12 \sum_{j=1}^J \frac{G_j^2}{H_j + \lambda} + \gamma J$$

(Eqs. 5 and 6). The value scores a tree structure, and the gain of splitting a node into a left part $L$ and a right part $R$ is the decrease of that score (Eq. 7):

$$\text{gain} = \frac12 \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda} \right] - \gamma .$$

A split is worth making only if its gain is positive, so $\gamma$ acts as a minimal gain and $\lambda$ shrinks the leaf values towards zero, more strongly in leaves with little curvature. Two special cases connect the formula to what came before. For squared loss, $g_i = F_{m-1}(x_i) - y_i$ and $h_i = 1$, so $w_j^*$ is the mean residual of the leaf shrunk by $n_j / (n_j + \lambda)$, and with $\lambda = \gamma = 0$ the gain is the drop in $\tfrac12 \sum_i r_i^2$, half the drop in the sum of squared residuals, the variance criterion of the decision-tree note. For log-loss, $w_j^*$ with $\lambda = 0$ is the Newton leaf of the table above.

A worked example with small numbers: one leaf, log-loss, current log-odds 0 so $p = 0.5$, labels $1, 1, 0$. The gradients $p - y$ are $-0.5, -0.5, 0.5$ and every Hessian is $0.25$, so $G = -0.5$ and $H = 0.75$. Without the penalty the leaf value is $0.5/0.75 = 0.667$ and the second-order approximation of the loss falls by $\frac12 \cdot 0.25/0.75 = 0.167$; the exact log-loss falls by $0.170$, close but not the same. With $\lambda = 1$ the value shrinks to $0.5/1.75 = 0.286$, and the penalized approximation, the second-order approximation plus $\frac{\lambda}{2} w^2$, falls by $0.071$. Splitting the two positives from the negative, with $\lambda = 1$, has gain $\frac12 (1/1.5 + 0.25/1.25 - 0.25/1.75) = 0.362$.

XGBoost, LightGBM and CatBoost#

The three libraries share the second-order objective and differ in how they make it fast and how they treat categories. The table lists what each paper introduces.

	XGBoost (Chen and Guestrin, 2016)	LightGBM (Ke et al., 2017)	CatBoost (Prokhorenkova et al., 2018)
Split search	exact greedy over sorted values; approximate on candidate quantiles from a weighted quantile sketch, weighted by $h_i$ (Sections 3.1–3.3)	histograms: features binned once, splits only at bin boundaries (Section 2.1)	—
Tree growth	level by level (depth-wise) in the exact algorithm, as Ke et al. note in their Section 5.1	leaf-wise: always split the leaf with the largest gain (best-first, Section 5.1)	oblivious trees: one split per level, shared by all nodes of the level (Section 5)
Rows	row and column subsampling (Section 2.3)	GOSS: keep the top fraction $a$ of points by $\lvert g_i \rvert$, sample a fraction $b$ of the rest and weight them by $(1 - a)/b$ (Section 3)	ordered boosting: the gradient of each point comes from a model that has not seen it, against the prediction shift (Section 4)
Features	sparsity-aware split with a learned default direction for missing values (Section 3.4)	EFB: bundle mutually exclusive sparse features into one (Section 4)	ordered target statistics for categories (Section 3.2)

Two of these ideas are about leakage, and they deserve a sentence each. CatBoost replaces a category by the average target of the training points with that category, smoothed by a prior, $\hat x_k = \big(\sum_{j} [x_j = x_k] \, y_j + a p\big) / \big(\sum_j [x_j = x_k] + a\big)$, where the sums run only over the points that come before $k$ in a random permutation; computed over all points, the statistic would include $y_k$ itself and leak the target into the feature, the problem of the data note. Ordered boosting applies the same principle to the gradients: the residual of a training point computed by a model trained on that point is smaller than it would be on a new point, a prediction shift that the authors identify as target leakage in boosting itself (Section 4.1). LightGBM’s leaf-wise growth reaches a lower training loss for the same number of leaves, and for that reason it needs a limit on leaves or depth to avoid deep, overfitted branches; CatBoost’s oblivious trees are the opposite choice, a strongly regularized and fast-to-evaluate shape.

Early stopping#

The number of trees $M$ is the main regularization parameter of boosting: the training loss falls monotonically, the test loss falls and then rises. Early stopping monitors the loss on a validation set after each tree and keeps the model at its minimum, or stops when the validation loss has not improved for a set number of rounds (Hastie, Tibshirani and Friedman, 2009, Section 10.12, which compares it to early stopping for neural networks).

Figure

Early stopping and the learning rate

The two learning rates show the trade-off of the previous section in one picture: with $\nu = 1$ the validation minimum comes early and is high; with $\nu = 0.1$ it comes later and is lower; both models overfit if run to the end. In practice the validation set is held out of the training data, as in the validation note, or the number of rounds is chosen by cross-validation. scikit-learn’s HistGradientBoostingClassifier, with 20% of the breast cancer training set held out for validation and a patience of 20 rounds, stops after 73 trees and reaches test accuracy $0.942$.

Stacking#

Boosting and bagging combine many models of one kind. Stacking (Wolpert, 1992; Breiman, 1996) combines a few models of different kinds, a forest, a boosted model, a linear model, a nearest-neighbour model: their predictions become the features of a meta-model, often a linear regression or a logistic regression, which learns how much to trust each.

The obvious way to build the meta-model’s training set, the base models’ predictions on their own training data, is wrong. A model that memorized its training set predicts the training targets perfectly, and the meta-model learns to trust it completely. It is target leakage in its purest form, as described in the data note. The fix is out-of-fold predictions: split the training set into $K$ folds, and predict each fold with copies of the base models trained on the other $K - 1$. Every point’s meta-feature then comes from models that did not see it, just as at test time. The meta-model is trained on the out-of-fold predictions, and the base models are refitted on all the data for prediction.

On Friedman’s function with 500 training points and three base models, 1-nearest-neighbour, ridge and a random forest, the difference is stark. A non-negative linear meta-model trained on in-sample predictions puts weights $(1, 0, 0)$ on the three: all of it on 1-NN, which reproduces its training targets exactly, and its test MSE is that of 1-NN, $13.71$. Trained on 5-fold out-of-fold predictions, the weights are $(0.03, 0.32, 0.76)$ and the test MSE is $4.29$, lower than that of the best single model, the forest at $4.76$. Restricting the weights to be non-negative is a common safeguard against unstable combinations of correlated predictions (Hastie, Tibshirani and Friedman, 2009, Section 8.8).

Blending is the holdout version: the base models are trained on one part of the data and the meta-model on their predictions for a second, held-out part. It is simpler and leaks nothing, but the meta-model sees fewer points and the base models are trained on less data. With time-ordered data, both folds and holdout must respect time, for the same reasons as validation does.

What changed#

	Bagging and random forests	Gradient boosting
Trees	deep, grown independently	small, grown sequentially
Each tree fits	a bootstrap sample of the targets	the negative gradient of the loss at the current model
Reduces	variance	bias (variance controlled by $\nu$, $M$, subsampling)
Loss	squared error or Gini inside the trees	any differentiable loss
More trees	never hurt	eventually overfit: early stopping
Tuning	little	learning rate, number of trees, depth, penalties

Limitations#

• Sequential. Trees cannot be grown in parallel across stages, only within a stage; training is slower than for a forest of the same size.
• Tuning matters. Learning rate, number of trees, tree size, subsampling and penalties interact, and the defaults are rarely optimal.
• Overfits if run too long, unlike a forest; it needs a validation set or cross-validation.
• Sensitive to label noise with losses whose gradients grow without bound, such as the exponential loss.
• Features must exist. Trees split on given features one at a time. On raw pixels, audio samples or token identities a single feature usually carries little information, and the useful structure, an edge or a phrase, lives in combinations that axis-aligned splits find only slowly. Trees on raw inputs can still be reasonable baselines, but such data usually do better with learned representations.

What you should remember#

• Boosting adds small trees one at a time, each fitted to the current errors; for squared loss the errors are residuals.
• In general each tree fits the negative gradient $-\partial L / \partial F$ at the training points by least squares, and each leaf then takes its own optimal (or Newton) step: gradient descent in function space.
• Log-loss: pseudo-residual $y - p$, Newton leaf $\sum (y_i - p_i) / \sum p_i (1 - p_i)$.
• Shrinkage $\nu \le 0.1$ with early stopping, trees of 4–8 leaves, row subsampling of about one half.
• XGBoost: second-order objective with penalties $\gamma J + \frac{\lambda}{2} \sum w_j^2$; $w_j^* = -G_j / (H_j + \lambda)$; split gain $\frac12 [G_L^2/(H_L + \lambda) + G_R^2/(H_R + \lambda) - G^2/(H + \lambda)] - \gamma$.
• LightGBM: histograms, leaf-wise growth, GOSS, EFB. CatBoost: oblivious trees, ordered target statistics, ordered boosting.
• Stacking trains a meta-model on out-of-fold predictions; in-sample predictions leak the target and reward memorization.

Code#

The second-order leaf and gain, residual fitting by hand, learning rates and subsampling with validation curves, built-in early stopping, and stacking with in-sample versus out-of-fold predictions:

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import GradientBoostingRegressor, HistGradientBoostingClassifier, RandomForestRegressor
from sklearn.linear_model import LinearRegression, Ridge
from sklearn.model_selection import cross_val_predict, train_test_split
from sklearn.neighbors import KNeighborsRegressor
from sklearn.tree import DecisionTreeRegressor

# one leaf, log-loss, current log-odds 0 (p = 0.5), labels 1, 1, 0: gradients p - y, Hessians p(1 - p)
y = np.array([1, 1, 0]); p = 0.5
g, h = p - y, p * (1 - p) * np.ones(3)
for lam in (0, 1):
    print(lam, round(-g.sum() / (h.sum() + lam), 3), round(0.5 * g.sum() ** 2 / (h.sum() + lam), 3))
# 0 0.667 0.167 | 1 0.286 0.071   (leaf value, decrease of the penalized second-order approximation)
# split gain of separating the two positives from the negative (lambda = 1, gamma = 0)
score = lambda G, H, lam=1: G ** 2 / (H + lam)
print(round(0.5 * (score(g[:2].sum(), h[:2].sum()) + score(g[2:].sum(), h[2:].sum()) - score(g.sum(), h.sum())), 3))   # 0.362

# squared loss: boosting stumps on residuals by hand for four points, learning rate 0.5
x = np.array([[1.0], [2.0], [3.0], [4.0]]); t = np.array([1.0, 3.0, 4.0, 8.0])
F = np.full(4, t.mean())
print(0, round(float(((t - F) ** 2).mean()), 3))   # 0 6.5
for m in range(3):
    stump = DecisionTreeRegressor(max_depth=1).fit(x, t - F)
    F += 0.5 * stump.predict(x)
    print(m + 1, F.round(3), round(float(((t - F) ** 2).mean()), 3))
# 1 [3.333 3.333 3.333 6.] 2.5 | 2 [2.167 3.722 3.722 6.389] 1.139 | 3 [1.694 3.25 4.194 6.861] 0.47

# Friedman's function: validation error along the iterations for learning rates 1 and 0.1, depth-3 trees
rng = np.random.default_rng(0)
f = lambda X: 10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2 + 10 * X[:, 3] + 5 * X[:, 4]
X = rng.random((1500, 10)); yv = f(X) + rng.normal(size=1500)
Xtr, Xva, Xte = X[:500], X[500:1000], X[1000:]
ytr, yva, yte = yv[:500], yv[500:1000], yv[1000:]
for lr in (1.0, 0.1):
    gb = GradientBoostingRegressor(learning_rate=lr, n_estimators=1000, max_depth=3, random_state=0).fit(Xtr, ytr)
    va = [((yva - p) ** 2).mean() for p in gb.staged_predict(Xva)]
    best = int(np.argmin(va))
    te = ((yte - list(gb.staged_predict(Xte))[best]) ** 2).mean()
    print(lr, best + 1, round(va[best], 2), round(va[-1], 2), round(te, 2))
# 1.0 8 5.72 6.75 5.7 | 0.1 189 2.71 2.74 2.66   (best round, best and final validation MSE, test MSE at the best round)
# subsampling half of the rows per tree (stochastic gradient boosting)
gb = GradientBoostingRegressor(learning_rate=0.1, n_estimators=1000, max_depth=3, subsample=0.5, random_state=0).fit(Xtr, ytr)
va = [((yva - p) ** 2).mean() for p in gb.staged_predict(Xva)]
print('subsample', int(np.argmin(va)) + 1, round(min(va), 2))   # subsample 205 2.38

# built-in early stopping on a validation fraction, log-loss, breast cancer
Xb, yb = load_breast_cancer(return_X_y=True)
Xb_tr, Xb_te, yb_tr, yb_te = train_test_split(Xb, yb, test_size=0.3, random_state=0, stratify=yb)
hgb = HistGradientBoostingClassifier(learning_rate=0.1, max_iter=1000, early_stopping=True, validation_fraction=0.2, n_iter_no_change=20, random_state=0).fit(Xb_tr, yb_tr)
print(hgb.n_iter_, round(hgb.score(Xb_te, yb_te), 3))          # 73 0.942

# stacking: a non-negative linear meta-model on in-sample predictions versus on out-of-fold predictions
base = {'1-NN': KNeighborsRegressor(1), 'ridge': Ridge(1.0), 'forest': RandomForestRegressor(200, random_state=0)}
ins = np.column_stack([m.fit(Xtr, ytr).predict(Xtr) for m in base.values()])
oof = np.column_stack([cross_val_predict(m, Xtr, ytr, cv=5) for m in base.values()])
test = np.column_stack([m.fit(Xtr, ytr).predict(Xte) for m in base.values()])
for name, Z in (('in-sample', ins), ('out-of-fold', oof)):
    meta = LinearRegression(positive=True).fit(Z, ytr)
    print(name, meta.coef_.round(2), round(((yte - meta.predict(test)) ** 2).mean(), 2))
# in-sample [1. 0. 0.] 13.71 | out-of-fold [0.03 0.32 0.76] 4.29
print({k: round(float(((yte - test[:, i]) ** 2).mean()), 2) for i, k in enumerate(base)})
# {'1-NN': 13.71, 'ridge': 6.63, 'forest': 4.76}

Next#

Every model of this section splits on features that someone provided: income, age, the count of a word. On tabular data, where each column means something, that is enough, and boosted trees remain hard to beat; a benchmark of 45 tabular datasets found tree ensembles still ahead of deep networks on medium-sized data, around ten thousand rows (Grinsztajn, Oyallon and Varoquaux, 2022). But a pixel, an audio sample or the identity of a token usually says little on its own, and a threshold on one of them is rarely a good question; what matters is a pattern across many of them. For such inputs the features themselves have to be learned. The next section starts from the linear models of this course, stacks them with nonlinearities in between, and trains the whole stack by the same gradient descent, so that the early layers compute the features that the last layer uses.

References#

• J. H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine. Annals of Statistics, 29(5), 2001. Section 3 and Algorithm 1 (gradient boosting), Algorithm 5 (two-class logistic loss with a Newton step per leaf), Section 5 (shrinkage).
• J. H. Friedman. Stochastic Gradient Boosting. Computational Statistics & Data Analysis, 38(4), 2002.
• J. Friedman, T. Hastie, R. Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28(2), 2000.
• Y. Freund, R. E. Schapire. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), 1997.
• T. Chen, C. Guestrin. XGBoost: A Scalable Tree Boosting System. KDD, 2016 (doi:10.1145/2939672.2939785). Eqs. 2–7 (regularized objective, leaf weights, structure score, split gain), Section 2.3 (shrinkage and column subsampling), Sections 3.1–3.4 (split finding, weighted quantile sketch, sparsity-aware splits).
• G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, T.-Y. Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. NeurIPS, 2017. Section 2.1 (histogram-based algorithm), Section 3 (GOSS), Section 4 (EFB), Section 5.1 (leaf-wise growth).
• L. Prokhorenkova, G. Gusev, A. Vorobev, A. V. Dorogush, A. Gulin. CatBoost: unbiased boosting with categorical features. NeurIPS, 2018. Section 3.2 (target statistics), Section 4 (prediction shift and ordered boosting), Section 5 (oblivious trees).
• D. H. Wolpert. Stacked generalization. Neural Networks, 5(2), 1992.
• L. Breiman. Stacked Regressions. Machine Learning, 24(1), 1996.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Section 8.8 (stacking), Sections 10.6 (loss functions and robustness), 10.10 (gradient boosting, Algorithm 10.3), 10.11 (tree size), 10.12 (shrinkage, subsampling, early stopping).
• L. Grinsztajn, E. Oyallon, G. Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? NeurIPS Datasets and Benchmarks, 2022.
• E. Sokolov et al. Машинное обучение (HSE). Lecture notes 2021, lecture 10: gradient boosting, lecture 11: XGBoost and stacking; practical session 12: gradient boosting, part 1, part 2: XGBoost, LightGBM, CatBoost.