XGBoost: A Scalable Tree Boosting System, annotated

2.1 Regularized learning objective · original

“Intuitively, the regularized objective will tend to select a model employing simple and predictive functions.”Chen and Guestrin (2016), §2.1

Everyday picture

A committee of advisers, each a small flowchart ending in a score. To predict, walk the example through every flowchart and add up the scores it lands on. Training chooses the flowcharts so the added-up scores fit the data, while a penalty charges for every leaf and for every large score, so each adviser stays modest.

Tiny example

House 4 walks through two trees. The first is a single leaf holding 4.0, the average price. The second asks “size > 2.5?” and says +2.5. The prediction is 4.0 + 2.5 = 6.5.

Reading it: each tree maps an example to one leaf, and each leaf holds a number, its weight w. Tree 1 has a single leaf, so every house gets 4.0 there. In tree 2, house 4 (size 4) answers “yes” and lands on +2.5. The bottom box adds the two landing spots. Unlike a classification tree, a leaf here holds a continuous score, not a label: the model is the sum of the scores, so no single tree needs to be right on its own.

In words: “the prediction for an example is the sum, over all K trees, of the leaf score it reaches in each.”

With the numbers: K = 2: f₁(house 4) = 4.0 and f₂(house 4) = 2.5, so ŷ = 6.5.

In Python:

# f_k: each tree maps a size to its leaf weight
def f1(size):
    return 4.0
def f2(size):
    return 2.5 if size > 2.5 else -2.5
trees = [f1, f2]
# ŷ = Σ_k f_k(x)
sum(f_k(4) for f_k in trees)  # → 6.5

Training minimizes the loss plus a penalty on every tree:

In words: “the objective is the total loss on the training data, plus, for every tree, a fixed charge per leaf and a charge on the squared size of its leaf scores.”

With the numbers: a tree with T = 2 leaves of weights −2 and +2, with γ = 1 and λ = 1, costs 1 × 2 + ½ × 1 × (4 + 4) = 6.

In Python:

gamma, lam = 1.0, 1.0
w = [-2.0, 2.0]
T = len(w)
# Ω(f) = γT + ½ λ ‖w‖²
gamma * T + 0.5 * lam * sum(w_j ** 2 for w_j in w)  # → 6.0

Why it matters

Friedman's gradient boosting controlled complexity from the outside: tree size, learning rate, number of trees. Putting γ and λ inside the objective means the split search itself refuses splits that do not pay for their leaf. With γ = λ = 0 the objective falls back to traditional gradient tree boosting, as the paper notes.

2.2 Gradient tree boosting · original

“This score is like the impurity score for evaluating decision trees, except that it is derived for a wider range of objective functions.”Chen and Guestrin (2016), §2.2

Everyday picture

Walking down a hill in fog, the slope under your feet says which way is down; knowing also how the slope is changing (the curvature) tells you how far to step before the ground starts rising again. First-order boosting uses only the slope. This paper uses slope and curvature for every example, as Newton's method does, and so gets the best step for each leaf from a formula.

Tiny example

Take squared loss l = (y − ŷ)² and the four houses predicted 4. Each house's slope is g = 2(ŷ − y) = (6, 4, −4, −6) and its curvature is h = 2 for every house. The next tree t adds f_t(x) to every prediction, and the paper approximates the new loss by its second-order Taylor expansion:

In words: “for the next tree, each example contributes its slope times the tree's output for it, plus half its curvature times that output squared; add the tree's penalty.”

With the numbers: for squared loss the approximation is exact. For a less tidy loss, take one spam email under log loss with its score at 0 (a 50% guess): g = p − y = −0.5 and h = p(1 − p) = 0.25. Stepping the score by f = 0.5, the true loss is 0.4741 and the quadratic approximation gives 0.4744.

In Python:

import math
y = [1, 2, 6, 7]
y_hat = 4.0
# squared loss (y − ŷ)²: g = 2(ŷ − y), h = 2
[2 * (y_hat - y_i) for y_i in y]  # → [6.0, 4.0, -4.0, -6.0]
# log loss for one spam email, score F = 0: p = 0.5
p = 0.5
g, h = p - 1, p * (1 - p)
g, h  # → (-0.5, 0.25)
f = 0.5
exact = math.log(1 + math.exp(-f))
approx = math.log(2) + g * f + 0.5 * h * f ** 2
round(exact, 4), round(approx, 4)  # → (0.4741, 0.4744)

Group the examples by the leaf they land in. Every example in leaf j gets the same output w_j, so the sums collapse to two numbers per leaf: G_j = Σg and H_j = Σh (equation 4). Each leaf is now a parabola in w_j, and the bottom of a parabola has a formula:

In words: “a leaf's best score is minus its total slope divided by its total curvature plus λ”: a Newton step, damped by λ.

With the numbers: the left leaf holds houses 1 and 2: G = 6 + 4 = 10, H = 2 + 2 = 4, so with λ = 1, w* = −10/5 = −2. With λ = 0 it would be −2.5, the average residual that Friedman's least-squares boosting uses: λ pulls every leaf towards zero. For the spam email alone in a leaf with λ = 0, w* = 0.5/0.25 = 2, taking its predicted probability from 0.5 to 0.881.

In Python:

import math
def w_star(G, H, lam):
    # w* = −G / (H + λ)
    return -G / (H + lam)
w_star(10.0, 4.0, 1.0)  # → -2.0
w_star(10.0, 4.0, 0.0)  # → -2.5
# one spam email: g = −0.5, h = 0.25, λ = 0
w = w_star(-0.5, 0.25, 0.0)
w, round(1 / (1 + math.exp(-w)), 3)  # → (2.0, 0.881)

Put each best score back in, and the objective of a whole tree structure q is:

In words: “a tree's quality is minus half the sum, over its leaves, of the squared total slope over the total curvature plus λ, plus the leaf charge; lower is better.”

With the numbers: the split tree for the four houses (λ = γ = 1): −½ (10²/5 + 10²/5) + 2 = −20 + 2 = −18. A single leaf holding all four: G = 0, so −½ × 0 + 1 = 1. The split tree scores 19 lower, so it is better.

In Python:

lam, gamma = 1.0, 1.0
def structure_score(leaves):
    # −½ Σ_j G_j² / (H_j + λ) + γT
    return -0.5 * sum(G ** 2 / (H + lam) for G, H in leaves) + gamma * len(leaves)
structure_score([(10.0, 4.0), (-10.0, 4.0)])  # → -18.0
structure_score([(0.0, 8.0)])  # → 1.0

Reading it: the left box is everything the tree needs from the data: one slope g and one curvature h per example. The tree sends each example to a leaf, and each leaf only adds up the g's and h's it receives (G and H). The bottom box applies equation (6) to those two numbers per leaf. Nothing else about the examples, not even their labels, is needed any more: that is why the same tree-growing code works for any loss that can supply g and h.

The split gain

Growing a tree greedily, a leaf is split in two if the score improves. The improvement is equation (6) before minus after:

In words: “a split is worth half of (the left side's score plus the right side's score minus the unsplit score), minus the price of one more leaf; if that is not positive, don't split.” (The paper writes the sums in full; G and H are shorthand for them.)

With the numbers: splitting the four houses at 2.5: ½(100/5 + 100/5 − 0/9) − 1 = 19, matching the drop from 1 to −18 above. Splitting after house 1 instead: ½(36/3 + 36/7 − 0) − 1 = 7.571. The middle split wins.

In Python:

lam, gamma = 1.0, 1.0
g, h = [6.0, 4.0, -4.0, -6.0], [2.0] * 4
def split_gain(G_L, H_L, G_R, H_R):
    return 0.5 * (G_L ** 2 / (H_L + lam) + G_R ** 2 / (H_R + lam) - (G_L + G_R) ** 2 / (H_L + H_R + lam)) - gamma
# split after house t = 1, 2, 3
[round(split_gain(sum(g[:t]), sum(h[:t]), sum(g[t:]), sum(h[t:])), 3) for t in (1, 2, 3)]  # → [7.571, 19.0, 7.571]

Why it matters

This is the heart of the paper and of modern boosting: one formula scores any split for any twice-differentiable loss, with regularization built in. Friedman's logistic TreeBoost already used a Newton step for its leaf values (see the gradient boosting machine companion, §4.5); here the same curvature also chooses the splits. The lesson's GradientBoosting is first-order, fitting each tree to GradientBoosting.negative_gradient by squared error; the lesson names the second-order step as one of the refinements it leaves out.

2.3 Shrinkage and column subsampling · original

“According to user feedback, using column sub-sampling prevents over-fitting even more so than the traditional row sub-sampling (which is also supported).”Chen and Guestrin (2016), §2.3

Everyday picture

Two more brakes on overfitting. Shrinkage (Friedman's learning rate, here called η) takes only part of each tree's correction. Column subsampling lets each tree see only a random subset of the input columns, the trick random forests use to make their trees disagree.

Tiny example

With η = 0.1, the right leaf's +2 moves house 4 from 4 to 4.2. With half the columns sampled per tree, a model with 28 inputs would give each tree 14 of them to choose from.

Why it matters

Column sampling is borrowed straight from Breiman (see the random forests companion, §3): decorrelating the trees helps boosting too, and it also makes each tree cheaper. The paper's experiments in §6 show it can cost a little accuracy on one dataset and gain a little on another.

3.1 Basic exact greedy algorithm · original

Everyday picture

To find the best threshold on one input, line the examples up in order of that input and walk along the line, keeping a running total of g and h on your left. At every gap, the right side's totals are just “everything minus the left”, so the gain of every possible split costs one addition and one formula.

Try it: the split scanner

Ten emails, labelled spam (1) or not (0), all currently predicted 50% spam, so every email has h = 0.25 and g = 0.5 − y (+0.5 for legitimate, −0.5 for spam). The input is the number of links; two emails have no link count recorded. Drag the threshold and watch the running sums and the gain of equation (7). Then change λ and γ, and choose where the two emails with missing values go.

Reading it: each chip is one email, sorted by its link count, with its slope g just above it; the two chips marked “?” have no link count. Chips going to the left child are outlined. The bars below show the gain of every threshold at once for the current λ, γ and missing-value direction, and the readout gives the running sums at your threshold. With missing values sent right and λ = 1, the best threshold is “links < 3.5”, gain 1.746: left of it the emails are mostly legitimate, right of it all spam, and the two unknowns (both spam) belong with the spam. Send them left instead and the same threshold only gains 0.545. Raise γ past the best gain and every bar goes negative: the leaf charge now outweighs any split, so the tree stops growing here.

Why it matters

Sorting once and sweeping with running sums is exactly how the lesson's best_split finds its splits quickly (with label counts in place of g and h). Algorithm 1 in the paper is that sweep, run over every feature.

3.2 Approximate algorithm · original

Everyday picture

When the data do not fit in memory, or live on many machines, trying every threshold is too slow. Instead, propose a few dozen candidate thresholds per feature (at percentiles), drop every example into its bucket, add up g and h per bucket, and run the same sweep over buckets instead of examples.

What the paper finds

Candidates can be proposed once per tree (global) or again after every split (local). On the Higgs 10M data (Figure 3), local proposals with ε = 0.3 (about 1/ε, so roughly three, buckets) matched exact greedy, while global proposals needed a finer ε = 0.05 (about 20 buckets) to match it; global with ε = 0.3 fell clearly behind.

Why it matters

Bucketing turns split finding into adding up small histograms, which is fast and easy to distribute. The lesson mentions “fast histogram-based split search” as one of the refinements modern libraries add to the basic loop.

3.3 Weighted quantile sketch · original

Everyday picture

Where should the bucket boundaries go? Evenly by count would spend as many candidates on examples the model already predicts confidently as on the ones it is still unsure about. The paper spaces them evenly by curvature h instead, so uncertain examples get finer buckets.

Tiny example

Four examples with feature values 1, 2, 3 and 4 and curvatures 0.25, 0.25, 0.09 and 0.01 (the last two are nearly certain). The weighted rank of the value 3 is the share of total curvature strictly below it: (0.25 + 0.25)/0.6 = 0.833. By count it would be 0.5.

In words: “the weighted rank of a value is the share of total curvature carried by examples whose feature value is below it.”

With the numbers: r(3) = (0.25 + 0.25) / (0.25 + 0.25 + 0.09 + 0.01) = 0.5 / 0.6 = 0.833.

In Python:

x = [1, 2, 3, 4]
h = [0.25, 0.25, 0.09, 0.01]
z = 3
# r_k(z) = Σ_{x < z} h / Σ h
round(sum(h_i for x_i, h_i in zip(x, h) if x_i < z) / sum(h), 3)  # → 0.833

The candidates s₁ … s_l must be close in weighted rank:

In words: “neighbouring candidate thresholds may be at most ε apart in weighted rank, and the first and last are the smallest and largest values”, which gives roughly 1/ε candidates.

With the numbers: ε = 0.3 allows about 1/0.3 ≈ 3 buckets; ε = 0.05 about 20, the two settings of Figure 3.

In Python:

# roughly 1/ε candidate points
[round(1 / eps) for eps in (0.3, 0.05)]  # → [3, 20]

Reading it: the twelve bars are examples in order of their feature value, and each bar's height is its curvature h. The dashed vertical lines are the candidate thresholds the rule in (9) proposes. With weighting on, candidates crowd into the regions with tall bars (examples the model is still unsure about) and the confident middle stretch gets few or none. Untick the box and every example counts the same, so the candidates spread evenly by count. Drag ε: smaller ε, more candidates, closer to the exact search.

Why curvature is the right weight

Completing the square turns equation (3) into a weighted squared error:

In words: “each boosting step is a least-squares fit to the targets −g/h, with example i weighted by h_i”: so h is literally each example's weight.

With the numbers: for the spam email (g = −0.5, h = 0.25), the target is −g/h = 2, the Newton step found above. The paper prints this line with (f_t(x_i) − g_i/h_i)² and “labels g_i/h_i”; expanding the square shows the sign must be +, with labels −g_i/h_i. The weights h_i, which are the point of the passage, are unaffected.

In Python:

g, h, f = -0.5, 0.25, 1.3
# g f + ½ h f² equals ½ h (f + g/h)² minus a constant g²/(2h)
round(g * f + 0.5 * h * f ** 2, 5)  # → -0.43875
round(0.5 * h * (f + g / h) ** 2 - g ** 2 / (2 * h), 5)  # → -0.43875
# the least-squares target −g/h
-g / h  # → 2.0

Finding such candidates on huge, distributed, weighted data is a known hard problem for unweighted data (quantile sketches) and had no solution with guarantees for weighted data; the paper's appendix supplies one.

Why it matters

Weighting by h makes the buckets finest where the next tree has the most to learn. The same idea, h as the weight of an example, is what lets one tree-growing routine serve every loss.

3.4 Sparsity-aware split finding · original

“XGBoost handles all sparsity patterns in a unified way.”Chen and Guestrin (2016), §3.4

Everyday picture

Real tables are full of holes: missing values, columns that are mostly zero, and the many zeros one-hot encoding creates. Rather than guess a value to fill in, give every split a default direction: a road that examples with the value missing always take. Learn which road is better from the data.

Tiny example

The split scanner above is Algorithm 3. For the threshold “links < 3.5”, the algorithm sweeps once with the two missing-value emails sent right (gain 1.746) and once with them sent left (gain 0.545), and keeps right as the default. Both sweeps visit only the eight emails that have a value: the missing ones are handled through the totals G and H.

What the paper finds

Because only non-missing entries are visited, the cost is linear in the number of non-missing entries. On the Allstate-10K data, sparse mainly because of one-hot encoding, the sparsity-aware algorithm ran more than 50 times faster than a version that ignores sparsity (Figure 5).

Why it matters

Learned default directions are how XGBoost lets you pass data with missing values straight in, the “native handling of missing values” the trees and boosting lesson lists among modern refinements.