XGBoost

Regularized gradient boosting on log-loss with Newton steps, sparsity-aware splits and built-in shrinkage.

17 min read1587 wordscore9 viewsupdated 2026-10-07

Definition

XGBoost (for classification) predicts the log-odds of the positive class as a sum of small trees, F(x)=F0+η∑mfm(x)F(x)=F_0+\eta\sum_m f_m(x), and turns it into a probability with the sigmoid, p=σ(F)p=\sigma(F). Each new tree is grown on the gradients gi=pi−yig_i=p_i-y_i and hessians hi=pi(1−pi)h_i=p_i(1-p_i) of the log-loss at the current predictions. Its splits are chosen by a regularized second-order gain, rows with missing values follow a learned default direction, and every leaf outputs a Newton step w∗=−G/(H+λ)w^*=-G/(H+\lambda).

At a glance

Task
Binary classification (binary:logistic), multiclass (multi:softprob), ranking; this article: binary
Input → output
feature vector xx (NaN allowed) → p(y=1∣x)=σ(F0+η∑m=1Mfm(x))p(y=1\mid x)=\sigma\big(F_0+\eta\sum_{m=1}^{M} f_m(x)\big)
Learns
MM trees; per internal node a feature, a threshold and a default direction for missing values; per leaf a log-odds weight wjw_j
Training
exact greedy O(M⋅D⋅∥x∥0)O(M\cdot D\cdot \lVert x\rVert_0) after one O(∥x∥0log⁡n)O(\lVert x\rVert_0\log n) pre-sort; histogram mode (the default since 2.0) bins features first
Prediction
O(M⋅D)O(M\cdot D) comparisons, one sigmoid
Hyperparameters
n_estimators, learning_rate η, max_depth, reg_lambda λ, gamma γ, min_child_weight, subsample, colsample_bytree, scale_pos_weight
Assumes
nothing distributional; the loss must be twice differentiable; decision boundaries are unions of axis-aligned boxes

The problem

Gradient boosting fits each tree to the negative gradient of the loss. For squared error that is clean — the gradient is the residual and every row counts the same. For log-loss it is not. A row the model already gets right with p=0.97p=0.97 and a row sitting at p=0.5p=0.5 can have similar-looking pseudo-residuals, but the loss curve is nearly flat for the first and steep for the second. A first-order method ignores this curvature: it grows the tree by least squares on the residuals, so confident and uncertain rows pull on the split equally.

Classic boosting also has no built-in brake: trees keep splitting as long as the training loss goes down, leaf values for tiny or nearly-pure leaves can explode, and real tables full of NaNs need imputation first. XGBoost (Chen & Guestrin, 2016) fixes these inside the objective itself: use the second derivative, put an explicit penalty on the trees, and learn where missing values should go.

The idea

Work in log-odds. At every round, each row gets two numbers: how hard the loss wants its log-odds to move (gig_i), and how sure that local picture is (hih_i, the curvature). A row at p=0.5p=0.5 has the largest curvature, 0.25; a row at p=0.99p=0.99 has almost none. Then grow a tree whose leaves are Newton steps: total push GG divided by total curvature HH, with λ\lambda added to HH so small leaves cannot jump far. A split is worth making only if it improves this regularized objective by more than γ\gamma, and only if both children carry enough curvature (min_child_weight). Finally, add just a fraction η\eta of the tree, recompute gg and hh, and repeat.

Vocabulary

Margin / log-odds
F(x)=log⁡p1−pF(x)=\log\frac{p}{1-p}, the raw tree sum before the sigmoid; output_margin=True returns it
base_score
the starting probability p0p_0; F0=log⁡p01−p0F_0=\log\frac{p_0}{1-p_0}. XGBoost ≥ 2 estimates it from the data (here 0.5, since 6 of 12 rows churned)
Gradient gᵢ
∂l/∂Fi=pi−yi\partial l/\partial F_i=p_i-y_i: negative for positives the model under-predicts, positive for negatives it over-predicts
Hessian hᵢ
∂2l/∂Fi2=pi(1−pi)∈(0,0.25]\partial^2 l/\partial F_i^2=p_i(1-p_i)\in(0,0.25]: the curvature, i.e. how much the row still counts
G, H (cover)
sums of gig_i and hih_i over the rows in a node; the tree dump calls HH the node's cover
Leaf weight w
the log-odds a leaf adds, before shrinkage: w∗=−G/(H+λ)w^*=-G/(H+\lambda); the stored leaf value is η w∗\eta\,w^*
Gain
how much a split lowers the regularized objective; the split is kept only if gain >γ>\gamma
Default direction
for each split, the branch that rows with a missing value are sent to — chosen during training to maximize gain

The math

pi=σ(Fi)=11+e−Fi,l(yi,Fi)=−[yilog⁡pi+(1−yi)log⁡(1−pi)]p_i=\sigma(F_i)=\frac{1}{1+e^{-F_i}},\qquad l(y_i,F_i)=-\big[y_i\log p_i+(1-y_i)\log(1-p_i)\big]
FiF_i
current log-odds for row ii (sum of all trees so far)
yi∈{0,1}y_i\in\{0,1\}
the label
ll
log-loss (binary cross-entropy) of one row

Differentiate with respect to the log-odds, not the probability. Using σ′(F)=σ(F)(1−σ(F))\sigma'(F)=\sigma(F)(1-\sigma(F)), the chain rule collapses beautifully:

gi=∂l∂Fi=pi−yi,hi=∂2l∂Fi2=pi(1−pi)g_i=\frac{\partial l}{\partial F_i}=p_i-y_i,\qquad h_i=\frac{\partial^2 l}{\partial F_i^2}=p_i(1-p_i)
gig_i
gradient: the signed error of the probability, in (−1,1)(-1,1)
hih_i
hessian: always positive, at most 0.25 (at pi=0.5p_i=0.5), → 0 as the model becomes confident

Round mm adds a tree fmf_m that maps each xx to the weight of its leaf, fm(x)=wq(x)f_m(x)=w_{q(x)}. XGBoost minimizes the loss plus a penalty on the tree:

L(m)=∑i=1nl(yi, Fi+fm(xi))+γT+12λ∑j=1Twj2\mathcal{L}^{(m)}=\sum_{i=1}^{n} l\big(y_i,\ F_i+f_m(x_i)\big)+\gamma T+\tfrac12\lambda\sum_{j=1}^{T}w_j^2
TT
number of leaves in the new tree
wjw_j
weight of leaf jj (a log-odds increment)
γ\gamma
price per leaf (gamma, alias min_split_loss, default 0)
λ\lambda
L2 penalty on leaf weights (reg_lambda, default 1)

Log-loss in FF is not quadratic, so XGBoost replaces it by its second-order Taylor expansion around the current FiF_i — exactly what Newton's method does:

l(yi,Fi+f)≈l(yi,Fi)+gi f+12hi f2l(y_i,F_i+f)\approx l(y_i,F_i)+g_i\,f+\tfrac12 h_i\,f^2

Drop the constant and group the rows by leaf (every row in leaf jj gets the same f=wjf=w_j). With Gj=∑i∈jgiG_j=\sum_{i\in j}g_i and Hj=∑i∈jhiH_j=\sum_{i\in j}h_i, the objective splits into one independent parabola per leaf:

L~=∑j=1T[Gj wj+12(Hj+λ)wj2]+γT\tilde{\mathcal{L}}=\sum_{j=1}^{T}\Big[G_j\,w_j+\tfrac12\big(H_j+\lambda\big)w_j^2\Big]+\gamma T

Setting ∂L~/∂wj=Gj+(Hj+λ) wj=0\partial\tilde{\mathcal L}/\partial w_j=G_j+(H_j+\lambda)\,w_j=0 gives the leaf weight, and substituting it back gives the best value this tree structure can reach:

wj∗=−GjHj+λ=∑i∈j(yi−pi)∑i∈jpi(1−pi)+λ,L~∗=−12∑j=1TGj2Hj+λ+γTw_j^*=-\frac{G_j}{H_j+\lambda}=\frac{\sum_{i\in j}(y_i-p_i)}{\sum_{i\in j}p_i(1-p_i)+\lambda},\qquad \tilde{\mathcal L}^*=-\frac12\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T
wj∗w_j^*
a Newton step in log-odds: total residual over total curvature, with λ added to the curvature
L~∗\tilde{\mathcal L}^*
structure score: lower is better; each leaf contributes −12Gj2/(Hj+λ)-\tfrac12 G_j^2/(H_j+\lambda)

To score a split of a node into left LL and right RR, compare the structure score with and without it. The node's own term G2/(H+λ)G^2/(H+\lambda) is replaced by two children's terms, and one extra leaf costs γ\gamma:

Gain=GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ,keep the split if Gain>γ\text{Gain}=\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},\qquad\text{keep the split if Gain}>\gamma
GL,HLG_L,H_L
gradient and hessian sums of the rows sent left
GR,HRG_R,H_R
the same for the right child

What each hyperparameter does to the formulas

λ (reg_lambda)
added to every HH: shrinks w∗w^* toward 0, most strongly for leaves with small HH (few rows, or confident ones). Also lowers every gain, so fewer splits pass γ\gamma.
γ (gamma)
a fixed price per extra leaf: a split survives only if its gain exceeds γ\gamma. Pruning runs bottom-up, so a weak split can stay if a strong one sits below it.
min_child_weight
each child must have H≥H\ge min_child_weight. For log-loss H=∑pi(1−pi)H=\sum p_i(1-p_i), so at p=0.5p=0.5 the default 1 means at least 4 rows, and a leaf of confident rows needs many more.
η (learning_rate)
the model adds η w∗\eta\,w^*, not w∗w^*. The Taylor expansion is only accurate near the current FF, so small steps plus more rounds generalize better.
α (reg_alpha)
L1 on leaves: w∗=−sign⁡(G)max⁡(∣G∣−α,0)/(H+λ)w^*=-\operatorname{sign}(G)\max(|G|-\alpha,0)/(H+\lambda); leaves with weak total push become exactly 0.
max_delta_step
clips ∣w∗∣|w^*|; useful for extremely imbalanced log-loss, where H→0H\to0 makes −G/H-G/H huge.
scale_pos_weight
multiplies gig_i and hih_i of positive rows; a common start is (number of negatives) / (number of positives).

Sparsity-aware split finding

Real tables have holes. Instead of imputing, XGBoost learns a default direction for every split. For a candidate threshold on feature jj it sorts only the rows where xjx_j is present and scans them twice: once with all missing rows added to the right child, once with them added to the left. Whichever gives the larger gain wins, and the direction is stored in the node. At prediction time a NaN simply follows that branch. The scan touches only non-missing entries, so on sparse data (one-hot columns, bag-of-words) the cost is proportional to the number of non-zeros ∥x∥0\lVert x\rVert_0, not n⋅dn\cdot d.

Worked example: will this customer churn?

Twelve subscription customers. Features: tenure in months and support calls last quarter (two customers have no call record — NaN). Label: churned (1) or stayed (0). Six of each, so p0=0.5p_0=0.5 and F0=0F_0=0. Settings: stumps (max_depth = 1), η=0.3\eta=0.3, λ=1\lambda=1, γ=0\gamma=0, min_child_weight = 1.

RowTenureCallsChurnedg (round 1)h (round 1)
1211−0.50.25
2451−0.50.25
35NaN1−0.50.25
4720+0.50.25
51061−0.50.25
61420+0.50.25
71851−0.50.25
82200+0.50.25
92740+0.50.25
1033NaN1−0.50.25
114030+0.50.25
124810+0.50.25
Churn data. Highlighted: the 5 rows sent right by the first split (calls ≥ 4.5 or missing).

Round 1, by hand

  1. 1Gradients and hessians. Every pi=σ(0)=0.5p_i=\sigma(0)=0.5, so gi=0.5−yi=∓0.5g_i=0.5-y_i=\mp0.5 and hi=0.25h_i=0.25. Root: G=0G=0, H=3H=3, so the root term G2/(H+λ)=0G^2/(H+\lambda)=0.
  2. 2Candidate calls < 4.5, missing → right. Left = rows 1, 4, 6, 8, 9, 11, 12 (one churner, six stayers): GL=−0.5+6(0.5)=2.5G_L=-0.5+6(0.5)=2.5, HL=1.75H_L=1.75. Right = rows 2, 5, 7 plus the two NaN rows 3 and 10, all churners: GR=−2.5G_R=-2.5, HR=1.25H_R=1.25.
  3. 3Gain =2.521.75+1+(−2.5)21.25+1−0=2.273+2.778=5.051=\frac{2.5^2}{1.75+1}+\frac{(-2.5)^2}{1.25+1}-0=2.273+2.778=5.051.
  4. 4Same threshold, missing → left. Then GL=1.5G_L=1.5, HL=2.25H_L=2.25 and the right child has only rows 2, 5, 7: HR=0.75<1H_R=0.75<1 — blocked by min_child_weight (its gain would have been 1.978). So the default direction for NaN is right.
  5. 5Every other candidate scores lower (table below). The best tenure split, tenure < 6, would put the three youngest churners alone (HL=0.75H_L=0.75) and is also blocked; the best allowed tenure split is tenure < 12 with gain 1.818.
  6. 6Leaf weights. wL∗=−2.51.75+1=−0.909w_L^*=-\frac{2.5}{1.75+1}=-0.909 and wR∗=−−2.51.25+1=+1.111w_R^*=-\frac{-2.5}{1.25+1}=+1.111. With shrinkage the stored leaf values are ηw∗=−0.273\eta w^*=-0.273 and +0.333+0.333.
  7. 7Update. Left rows: F=−0.273F=-0.273, p=σ(−0.273)=0.432p=\sigma(-0.273)=0.432. Right rows: F=0.333F=0.333, p=0.583p=0.583. Train log-loss drops from log⁡2=0.6931\log 2=0.6931 to 0.5781, and 11 of 12 rows are on the correct side of 0.5 (row 1, a 2-month customer with one call, is not).
SplitMissing →G_L / H_LG_R / H_RGainAllowed?
calls < 4.5right2.5 / 1.75−2.5 / 1.255.051yes
calls < 3.5right2.0 / 1.50−2.0 / 1.503.200yes
tenure < 6—−1.5 / 0.751.5 / 2.251.978no
calls < 4.5left1.5 / 2.25−1.5 / 0.751.978no
tenure < 12—−1.5 / 1.251.5 / 1.751.818yes
calls < 2.5right1.5 / 1.25−1.5 / 1.751.818yes
calls < 3.5left1.0 / 2.00−1.0 / 1.000.833yes
Round 1 candidates on the library's gain scale (λ = 1). Blocked = a child has H < min_child_weight = 1.

Round 2. The hessians are no longer equal, and the gradients now carry what round 1 got wrong. Row 1 is the only churner on the left and has the largest pull, g1=0.432−1=−0.568g_1=0.432-1=-0.568.

GroupRowsp after round 1g = p − yh = p(1 − p)
left, churned10.4322−0.56780.2454
left, stayed4, 6, 8, 9, 11, 120.4322+0.43220.2454
right, churned2, 3, 5, 7, 100.5826−0.41740.2432
Inputs to tree 2. Sums: G = −0.0615, H = 2.9338 (down from 3: the model is less uncertain).

Round 2 and the prediction

  1. 1Best split is again calls < 4.5, NaN → right: GL=2.0257G_L=2.0257, HL=1.7179H_L=1.7179, GR=−2.0871G_R=-2.0871, HR=1.2159H_R=1.2159; gain =1.5098+1.9659−0.0010=3.475=1.5098+1.9659-0.0010=3.475. Runner-up: calls < 3.5 with gain 2.139. Tenure < 6 (gain 1.697) is still blocked: HL=0.732H_L=0.732.
  2. 2Leaves: wL∗=−2.0257/2.7179=−0.745w_L^*=-2.0257/2.7179=-0.745 and wR∗=2.0871/2.2159=+0.942w_R^*=2.0871/2.2159=+0.942; stored values ηw∗=−0.224\eta w^*=-0.224 and +0.283+0.283.
  3. 3Model after 2 trees: left rows F=−0.273−0.224=−0.496F=-0.273-0.224=-0.496, p=0.378p=0.378; right rows F=0.333+0.283=0.616F=0.333+0.283=0.616, p=0.649p=0.649. Train log-loss 0.4987, accuracy 11/12.
  4. 4New customer: tenure 6 months, no call record. Both trees send NaN right: F=0+0.333+0.283=0.616F=0+0.333+0.283=0.616, so p(churn)=σ(0.616)=0.649p(\text{churn})=\sigma(0.616)=0.649 — flagged as a churn risk purely through the learned default direction.
F₂ after 2 trees · ● churned ● stayed · dot area ∝ hᵢ · drag ★0123456n/asupport calls01020304050tenure (months)★p = 0.649tree 2: fit to gᵢ = pᵢ − yᵢ, hᵢ = pᵢ(1 − pᵢ) · ΣG = −0.061 · ΣH = 2.934yesno + n/acalls < 4.5gain 3.475w* = −0.745G +2.03 · H 1.727 rows · η·w = −0.224w* = +0.942G −2.09 · H 1.225 rows · η·w = +0.283
round 2/30
max_depth
η
λ
γ
min_child_weight
train log-loss 0.4987accuracy 11/12★ tenure 6, calls n/a: F = +0.616 → p(churn) = 0.649
leaves show w* = −G/(H+λ); the model adds η·w*.
fig.XGBoost on the 12 churn rows: tenure on x, support calls on y, and a dashed strip below for rows whose calls are missing. The shading is p(churn) of the current model and the white line is p = 0.5; dot area is each row's hessian hᵢ = pᵢ(1 − pᵢ), the weight it gets in the tree shown below (leaves list G, H and w* = −G/(H+λ)). It opens at round 2 of the worked example: two calls < 4.5 stumps, train log-loss 0.4987, 11/12 correct, and the ★ (tenure 6, calls missing) at p = 0.649. Press play: by round 30 log-loss is 0.3187 but row 1 is still wrong, because with min_child_weight = 1 no child can hold fewer than about 4 rows — max_depth = 2 changes nothing. Set min_child_weight to 0.5 and depth 2: tenure splits appear, the dots of confident rows shrink, and round 30 reaches log-loss 0.1316 with 12/12. Try λ = 10 (smaller leaves), γ = 2 (weak splits pruned: log-loss 0.4419 at depth 2) or min_child_weight = 2 (no split is possible: p stays 0.5). Drag ★ to follow a new customer through the current tree.

The algorithm, step by step

XGBoost, binary:logistic

  1. 1Initialize. Fi=F0=log⁡p01−p0F_i=F_0=\log\frac{p_0}{1-p_0} with p0p_0 = base_score.
  2. 2For m=1,…,Mm=1,\dots,M: compute pi=σ(Fi)p_i=\sigma(F_i), gi=pi−yig_i=p_i-y_i, hi=pi(1−pi)h_i=p_i(1-p_i) (optionally on a row subsample, with a column subsample per tree / level / node).
  3. 3Grow a tree from the root. At each node with sums G,HG,H, for every feature: take the present values in sorted order (sorted once, up front) and scan them left-to-right with NaN rows on the right, then right-to-left with NaN rows on the left, accumulating GL,HLG_L,H_L.
  4. 4At each threshold between distinct values, skip it if either child has H<H< min_child_weight; otherwise compute the gain. Keep the best (feature, threshold, default direction).
  5. 5Split and recurse until max_depth or no positive gain. Then prune bottom-up: any split whose children are leaves and whose gain is below γ\gamma is collapsed.
  6. 6Leaves: wj∗=−Gj/(Hj+λ)w_j^*=-G_j/(H_j+\lambda) (with the α soft-threshold and max_delta_step clip if set).
  7. 7Update Fi←Fi+η wq(xi)F_i\leftarrow F_i+\eta\,w_{q(x_i)}. Evaluate on a validation set; stop when it has not improved for early_stopping_rounds.
  8. 8Predict: p(x)=σ(F0+η∑mwqm(x)(m))p(x)=\sigma\big(F_0+\eta\sum_m w^{(m)}_{q_m(x)}\big); class 1 if p>0.5p>0.5 (or a tuned threshold).

Cost

Exact greedy
features are pre-sorted once into column blocks (O(∥x∥0log⁡n)O(\lVert x\rVert_0\log n)); then each depth level is one linear scan over the non-missing entries: O(M⋅D⋅∥x∥0)O(M\cdot D\cdot\lVert x\rVert_0) in total
Histogram (default)
values are bucketed into max_bin = 256 bins; per node, accumulate G,HG,H per bin in O(rows)O(\text{rows}) and scan only the bins. Much faster for large nn; also the method used on GPU
Memory
the data matrix plus g,hg,h (two floats per row); histograms per node in hist mode
Prediction
O(M⋅D)O(M\cdot D) per row, trivially parallel

Tuning in practice

ParameterDefaultTypical rangeEffect
n_estimators + early_stopping_rounds100 / offup to 5000, stop after 50–100 flat roundsnumber of trees; let early stopping choose it
learning_rate (η)0.30.01–0.1smaller = smoother, needs more trees
max_depth63–10interaction order; the main capacity knob
min_child_weight11–20minimum hessian per child: larger = fewer, more stable leaves
reg_lambda (λ) / reg_alpha (α)1 / 0λ 0.1–10, α 0–10shrink leaf weights; α zeroes weak leaves
gamma (γ)00–5minimum gain to keep a split
subsample / colsample_bytree1 / 10.6–0.9row / column sampling per tree: decorrelates trees, cuts variance
scale_pos_weight1#neg / #posrebalances g and h of positives for rare-event problems
The knobs that matter, defaults in xgboost 3, and a sensible search range.

Variants and relatives

Multiclass
multi:softprob: KK trees per round, one per class, with gik=pik−yikg_{ik}=p_{ik}-y_{ik} and hik=2 pik(1−pik)h_{ik}=2\,p_{ik}(1-p_{ik}) (XGBoost doubles the softmax hessian)
tree_method
exact (all thresholds), approx (weighted quantile sketch: candidate thresholds at quantiles weighted by hih_i), hist (default, fixed bins); device="cuda" for GPU
grow_policy
depthwise (default, level by level) or lossguide (best leaf first, like LightGBM)
Constraints
monotone_constraints forces p to rise (or fall) with a feature; interaction_constraints limits which features may share a branch
Categoricals
enable_categorical=True with the pandas category dtype splits on category sets directly
Siblings
LightGBM grows leaf-wise on histograms with GOSS / EFB for speed; CatBoost targets categorical features with ordered target statistics and symmetric trees. The regression version of this article is XGBoost regression.

In code

python
1import numpy as np
2
3def sigmoid(z):
4 return 1 / (1 + np.exp(-z))
5
6def best_split(X, g, h, lam, mcw):
7 """Exact greedy, sparsity-aware: every threshold, both default directions for missing values."""
8 G, H = g.sum(), h.sum()
9 best = (0.0, None, None, None) # (gain, feature, threshold, missing_left)
10 for j in range(X.shape[1]):
11 ok = ~np.isnan(X[:, j])
12 order = np.argsort(X[ok, j], kind="stable")
13 xs, gs, hs = X[ok, j][order], g[ok][order], h[ok][order]
14 has_missing = not ok.all()
15 for miss_left in ([False, True] if has_missing else [True]):
16 idx = range(len(xs) - 1, -1, -1) if miss_left else range(len(xs))
17 gA = hA = 0.0 # stats of the side being scanned
18 for i in idx:
19 gA += gs[i]; hA += hs[i]
20 nxt = i - 1 if miss_left else i + 1
21 last = not 0 <= nxt < len(xs)
22 if (not last and xs[nxt] == xs[i]) or (last and not has_missing):
23 continue
24 gB, hB = G - gA, H - hA # the other side (incl. missing rows)
25 if min(hA, hB) < mcw - 1e-9: # min_child_weight acts on the hessian sum
26 continue
27 gain = gA**2 / (hA + lam) + gB**2 / (hB + lam) - G**2 / (H + lam)
28 if gain > best[0]:
29 t = xs[i] + (-1e-6 if miss_left else 1e-6) if last else (xs[i] + xs[nxt]) / 2
30 best = (gain, j, t, miss_left)
31 return best
32
33def grow(X, g, h, lam, gamma, mcw, depth, max_depth):
34 w = -g.sum() / (h.sum() + lam) # Newton step, shrunk by lambda
35 if depth == max_depth:
36 return {"leaf": w}
37 gain, j, t, miss_left = best_split(X, g, h, lam, mcw)
38 if j is None:
39 return {"leaf": w}
40 left = np.where(np.isnan(X[:, j]), miss_left, X[:, j] < t)
41 L = grow(X[left], g[left], h[left], lam, gamma, mcw, depth + 1, max_depth)
42 R = grow(X[~left], g[~left], h[~left], lam, gamma, mcw, depth + 1, max_depth)
43 if gain < gamma and "leaf" in L and "leaf" in R: # bottom-up gamma pruning
44 return {"leaf": w}
45 return {"f": j, "t": t, "miss_left": miss_left, "gain": gain, "L": L, "R": R}
46
47def tree_value(node, x):
48 while "leaf" not in node:
49 v = x[node["f"]]
50 go_left = node["miss_left"] if np.isnan(v) else v < node["t"]
51 node = node["L"] if go_left else node["R"]
52 return node["leaf"]
53
54def fit(X, y, rounds=2, eta=0.3, lam=1.0, gamma=0.0, mcw=1.0, max_depth=1):
55 F = np.zeros(len(y)) # base_score 0.5 -> log-odds 0
56 trees = []
57 for _ in range(rounds):
58 p = sigmoid(F)
59 g, h = p - y, p * (1 - p) # log-loss gradient and hessian
60 tree = grow(X, g, h, lam, gamma, mcw, 0, max_depth)
61 trees.append(tree)
62 F = F + eta * np.array([tree_value(tree, x) for x in X])
63 return trees
64
65def predict_proba(trees, x, eta=0.3):
66 return sigmoid(sum(eta * tree_value(t, x) for t in trees))
67
68nan = np.nan
69X = np.array([[2, 1], [4, 5], [5, nan], [7, 2], [10, 6], [14, 2],
70 [18, 5], [22, 0], [27, 4], [33, nan], [40, 3], [48, 1]], float)
71y = np.array([1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0], float)
72
73trees = fit(X, y)
74for t in trees: # two stumps: print split and eta * leaf
75 print(["tenure", "calls"][t["f"]], "<", t["t"], "gain", round(t["gain"], 4),
76 "missing ->", "left" if t["miss_left"] else "right",
77 "leaves", round(0.3 * t["L"]["leaf"], 4), round(0.3 * t["R"]["leaf"], 4))
78print(round(predict_proba(trees, np.array([6, nan])), 4)) # new customer, calls not recorded
79# calls < 4.5 gain 5.0505 missing -> right leaves -0.2727 0.3333
80# calls < 4.5 gain 3.4747 missing -> right leaves -0.2236 0.2826
81# 0.6493
From scratch: Newton boosting on log-loss with exact, sparsity-aware splits, min_child_weight and γ-pruning. Prints the two stumps of the worked example and p = 0.6493 for the new customer.
python
1import numpy as np
2from xgboost import XGBClassifier
3from sklearn.metrics import log_loss
4
5nan = np.nan
6X = np.array([[2, 1], [4, 5], [5, nan], [7, 2], [10, 6], [14, 2],
7 [18, 5], [22, 0], [27, 4], [33, nan], [40, 3], [48, 1]], float)
8y = np.array([1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0])
9
10model = XGBClassifier(
11 n_estimators=2, max_depth=1, learning_rate=0.3,
12 reg_lambda=1.0, gamma=0.0, min_child_weight=1.0,
13 base_score=0.5, tree_method="exact", # match the hand calculation
14)
15model.fit(X, y) # NaN = missing, handled natively
16
17for tree in model.get_booster().get_dump(with_stats=True):
18 print(tree)
19p = model.predict_proba(X)[:, 1]
20print("train log-loss", round(log_loss(y, p), 4))
21print("p(churn | tenure 6, calls missing)", round(float(model.predict_proba([[6, nan]])[0, 1]), 4))
22
23# 0:[f1<4.5] yes=1,no=2,missing=2,gain=5.05050468,cover=3
24# 1:leaf=-0.272727281,cover=1.75
25# 2:leaf=0.333333373,cover=1.25
26# 0:[f1<4.5] yes=1,no=2,missing=2,gain=3.47466874,cover=2.93376875
27# 1:leaf=-0.223594904,cover=1.71785784
28# 2:leaf=0.28256765,cover=1.21591079
29# train log-loss 0.4987
30# p(churn | tenure 6, calls missing) 0.6493
The same model with the xgboost library. The dump shows the gains, covers (H) and stored leaf values (η·w*) from the hand calculation.

Use when

  • +Tabular data with mixed numeric features, non-linear effects and interactions: XGBoost is a top performer out of the box.
  • +Data has missing values or is sparse (one-hot, counts): NaN routing is learned and the cost scales with non-zeros.
  • +You need log-loss-trained probabilities, monotone constraints, or a custom differentiable objective (you supply g and h).
  • +Production scoring must be fast: prediction is a few hundred tree lookups.

Avoid when

  • −Images, audio, raw text: neural networks learn the representations trees cannot.
  • −Tiny datasets (hundreds of rows): a regularized logistic regression is often as good and far easier to explain.
  • −You need to extrapolate beyond the training range: trees predict a constant outside it.
  • −Many high-cardinality categoricals: CatBoost's ordered target statistics usually handle them with less work.

Where it's used

Credit scoring & fraud

Default or fraud probability from transaction and account features; scale_pos_weight and monotone constraints for rare, regulated targets.

Churn & conversion

Which customers or sessions will leave or buy — exactly the shape of the worked example, with plenty of missing fields.

Click-through prediction

Sparse, high-dimensional ad and user features; the sparsity-aware scan was designed for this.

Tabular competitions

Gradient-boosted trees from XGBoost, LightGBM and CatBoost win most structured-data competitions, often ensembled together.

Check yourself

A positive row (y = 1) currently has p = 0.8. Its gradient and hessian under log-loss are…

Check yourself

A leaf has G = −2.5 and H = 1.25, with λ = 1 and η = 0.3. How much log-odds does it add to its rows?

Check yourself

With binary:logistic, all predictions at p = 0.5 and min_child_weight = 1, what is the smallest number of rows a child node can have?

Check yourself

At prediction time a row has NaN for the feature tested at a node. XGBoost…

Remember

  • ✓XGBoost boosts in log-odds: p=σ(F0+η∑mfm(x))p=\sigma(F_0+\eta\sum_m f_m(x)), with gi=pi−yig_i=p_i-y_i and hi=pi(1−pi)h_i=p_i(1-p_i) from the log-loss.
  • ✓A second-order Taylor expansion turns each round into independent per-leaf parabolas: w∗=−G/(H+λ)w^*=-G/(H+\lambda) and split gain GL2HL+λ+GR2HR+λ−G2H+λ\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{G^2}{H+\lambda}.
  • ✓λ shrinks leaves, γ prices each extra leaf (bottom-up pruning), and min_child_weight demands enough curvature per child — for log-loss, confident rows carry little.
  • ✓Missing values get a learned default direction per split; the scan costs only the non-missing entries.
  • ✓In practice: small learning rate + early stopping on validation log-loss, then tune depth / min_child_weight, then sampling and regularization.
← back to ML Algorithms roadmap