Gradient boosting

Problem

A single decision tree is readable but unstable, and a deep one memorizes its training set. A shallow one is stable but too crude to follow a curved relationship. You would like the flexibility of many splits without the variance of one big tree.

Boosting gets there by addition. Start from a constant guess, look at how wrong it is on every training row, fit a small tree to that error, add a damped copy of the tree to the guess, and repeat. On tabular data this recipe, in its XGBoost, LightGBM and scikit-learn forms, is still the model most often hard to beat.

Intuition

Think of a golfer who cannot see the hole. The first shot goes in the average direction. Each later shot is aimed at the remaining gap, but only a fraction of the way, because a bad estimate of the gap should not overshoot. The sum of many small corrections lands close, and a wrong correction early is repaired by later ones.

The formal version is gradient descent where the thing being moved is the prediction function itself. With squared error L = ½(y − F)², the negative gradient with respect to the prediction F is exactly the residual y − F. So "fit a tree to the residuals" is "fit a tree to the negative gradient". Change the loss and only the target of the next tree changes: for log loss at predicted probability p it is y − p. A tree can only be fitted to a finite set of rows, so each step moves the predictions in the direction the tree can express, not the exact gradient.

Each stage looks at the training rows, computes what the current sum gets wrong, fits a small tree to that, and adds a fraction η of it.

Mechanics

Fitting the negative gradient

For a loss ℓ(y, F), stage m computes, for each training row i, the pseudo-residual and fits a regression tree h_m to it:

r_i = − ∂ℓ(y_i, F)/∂F at F = F_m−1(x_i)     F_m = F_m−1 + η · h_m

For squared error r_i = y_i − F_m−1(x_i). For the logistic loss on a raw score F with p = σ(F), g = p − y is the gradient and r = y − p. Friedman's original algorithm then re-fits each leaf's value by a one-dimensional line search on the true loss. In scikit-learn that is _update_terminal_regions: for squared error it changes nothing, and for binary log loss it is one Newton step, the leaf's mean of r divided by the mean of p(1 − p). The initial F₀ is the constant that minimizes the loss, which is the target mean for squared error and the log-odds of the base rate for log loss.

The second-order view

XGBoost, and the histogram boosters in LightGBM and scikit-learn, use both the gradient g_i and the curvature h_i = ∂²ℓ/∂F² of the loss. Expanding the loss to second order around the current prediction and adding a penalty on the new tree's size and leaf weights gives, for a candidate tree f with T leaves and leaf weights w:

L ≈ Σ_i [ g_i f(x_i) + ½ h_i f(x_i)² ] + γT + ½ λ Σ_j w_j²

Rows that land in leaf j contribute G_j = Σ g_i and H_j = Σ h_i, so the leaf's part of the loss is G_j w + ½ (H_j + λ) w². This quadratic is minimized at:

w*_j = − G_j / (H_j + λ)     with objective value − ½ G_j² / (H_j + λ) + γ

Splitting a node into left and right children replaces one leaf with two, so the improvement is the difference of those objective values:

Gain = ½ [ G_L²/(H_L+λ) + G_R²/(H_R+λ) − (G_L+G_R)²/(H_L+H_R+λ) ] − γ

For squared error g = F − y and h = 1, so G is minus the residual sum and H is the row count, and w* is the mean residual shrunk by n/(n + λ). λ pulls leaf values toward zero; γ is the price of an extra leaf. The code differs from the paper's formula in a detail worth knowing: XGBoost's CalcGain returns G²/(H+λ) with no ½, and its loss_chg is the bracket above, compared against γ directly. So a split survives when the unhalved bracket is at least gamma, which is twice as lenient as the paper's ½[…] − γ would suggest. The worked example below checks this.

Both fits use stumps (depth-1 trees) and η = 0.5. Four weak steps already trace the hump that one step cannot.

Shrinkage, subsampling and early stopping

Multiplying each tree by a learning rate η < 1 means no single tree, which was fitted to noisy residuals, is trusted fully. Smaller η needs more rounds but generalizes better, and in practice η and the number of rounds are tuned together: lower η, more trees. Row subsampling (subsample < 1) fits each tree to a random fraction of the rows, which adds variance reduction like bagging and makes a stochastic gradient boosting; scikit-learn also reports out-of-bag improvements when it is on. Because every extra round lowers the training loss, training loss cannot say when to stop. Early stopping holds out validation rows and ends training when the validation loss has not improved for n_iter_no_change rounds, then (in XGBoost) keeps the best round.

Histograms, missing values and the fast implementations

Scanning every distinct value as a threshold costs a sort per feature per node. The histogram method bins each feature once, into at most max_bin quantile-based bins (256 in XGBoost, 255 in scikit-learn's HistGradientBoosting, plus one more bin there for missing values). After that, a node's histogram holds (G, H) per bin, so a split search is a scan over a few hundred bins regardless of the row count, and a child's histogram can be obtained by subtracting its sibling's from the parent's. Missing values need no imputation: the split search tries sending the missing rows to the left and then to the right, and the better direction is stored as the node's default. XGBoost does this by scanning the bins in both directions. The cost is a coarser threshold set; with 256 bins that rarely matters.

The main knobs

• learning rate η. 0.1 in scikit-learn, 0.3 in XGBoost's default. Lower is safer and slower.
• Number of rounds. 100 by default in scikit-learn; set it high and let early stopping pick.
• Tree size. max_depth 3 for GradientBoostingRegressor, 6 in XGBoost, unlimited with max_leaf_nodes=31 in HistGradientBoosting. Depth sets how many features may interact in one tree.
• Regularization. reg_lambda (λ, default 1 in XGBoost), gamma (min split loss, 0), min_child_weight (smallest H in a child, 1), min_samples_leaf (20 in HistGradientBoosting).
• Subsampling. subsample for rows, and column sampling in XGBoost.

Worked example

The same trees, damped or not. A small η trades more rounds for a lower and flatter minimum.

Implementation

from sklearn.ensemble import GradientBoostingRegressor, HistGradientBoostingClassifier
import xgboost as xgb

# exact-split booster: stages are explicit and inspectable
gbr = GradientBoostingRegressor(
    n_estimators=500, learning_rate=0.05, max_depth=3, subsample=0.8,
    n_iter_no_change=20, validation_fraction=0.1, random_state=0,
).fit(X_train, y_train)
gbr.n_estimators_                       # rounds actually used after early stopping
for pred in gbr.staged_predict(X_val):  # prediction after each round
    pass

# histogram booster: binned features, NaN allowed, early stopping on by default for large n
hgb = HistGradientBoostingClassifier(
    learning_rate=0.1, max_leaf_nodes=31, l2_regularization=1.0,
    early_stopping=True, random_state=0,
).fit(X_train, y_train)

# XGBoost: second-order trees with explicit validation and early stopping
dtrain, dval = xgb.DMatrix(X_train, label=y_train), xgb.DMatrix(X_val, label=y_val)
params = {"objective": "binary:logistic", "eta": 0.05, "max_depth": 4,
          "lambda": 1.0, "gamma": 0.0, "min_child_weight": 1,
          "tree_method": "hist", "eval_metric": "logloss"}
bst = xgb.train(params, dtrain, num_boost_round=2000,
                evals=[(dval, "val")], early_stopping_rounds=50)
bst.best_iteration

In the loop, every round takes the loss's gradient (and Hessian) at the current predictions, builds one histogram tree from them, scales its leaf weights by the learning rate and adds them to the running scores; prediction is the sum of all trees' outputs passed through the link function. There is no feature scaling anywhere, since trees only compare against thresholds.

Tradeoffs

• Why use it. Excellent accuracy on tabular data with little preprocessing: mixed scales, interactions, missing values and monotone transformations all just work. Many loss functions are available by changing g and h.
• Sequential and sensitive. Trees depend on each other, so training cannot be parallelized across rounds (only within a tree), and results depend on η, rounds, depth and regularization together. Tune them with a validation set, not by hand on training error.
• Overfitting. Unlike a forest, adding rounds eventually hurts, as the curves above show. Use early stopping, a small η, shallow trees, subsampling and regularization.
• Noisy labels. Residual fitting chases outliers under squared error; a robust loss such as Huber or absolute error helps.
• No extrapolation. Like its trees, the ensemble is piecewise constant and flat outside the training range.
• Interpretability. Hundreds of trees are not readable. Use feature importance (with the caveats from the decision trees page), permutation importance, partial dependence or SHAP values.
• Alternatives compared. Against a random forest: boosting reduces bias while a forest reduces variance; a forest is easier to tune but is usually a little less accurate. Against neural networks: boosting is usually stronger on small and medium tabular data, while networks win on images, text and sequences.

Check yourself

Connections

References

• Friedman. Greedy function approximation: a gradient boosting machine. Annals of Statistics 29(5), 2001. doi:10.1214/aos/1013203451.
• Chen and Guestrin. XGBoost: a scalable tree boosting system. KDD 2016. arXiv:1603.02754.
• Ke et al. LightGBM: a highly efficient gradient boosting decision tree. NeurIPS 2017.
• Hastie, Tibshirani and Friedman. The Elements of Statistical Learning, chapter 10: boosting and additive trees.
• scikit-learn 1.9.1: _fit_stage, _split_gain.
• XGBoost v3.4.2: CalcGain, EnumerateSplit.