Definition
XGBoost (for classification) predicts the log-odds of the positive class as a sum of small trees, , and turns it into a probability with the sigmoid, . Each new tree is grown on the gradients and hessians 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 .
At a glance
- Task
- Binary classification (
binary:logistic), multiclass (multi:softprob), ranking; this article: binary - Input → output
- feature vector (NaN allowed) →
- Learns
- trees; per internal node a feature, a threshold and a default direction for missing values; per leaf a log-odds weight
- Training
- exact greedy after one pre-sort; histogram mode (the default since 2.0) bins features first
- Prediction
- 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 and a row sitting at 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 (), and how sure that local picture is (, the curvature). A row at has the largest curvature, 0.25; a row at has almost none. Then grow a tree whose leaves are Newton steps: total push divided by total curvature , with added to so small leaves cannot jump far. A split is worth making only if it improves this regularized objective by more than , and only if both children carry enough curvature (min_child_weight). Finally, add just a fraction of the tree, recompute and , and repeat.
Vocabulary
- Margin / log-odds
- , the raw tree sum before the sigmoid;
output_margin=Truereturns it - base_score
- the starting probability ; . XGBoost ≥ 2 estimates it from the data (here 0.5, since 6 of 12 rows churned)
- Gradient gᵢ
- : negative for positives the model under-predicts, positive for negatives it over-predicts
- Hessian hᵢ
- : the curvature, i.e. how much the row still counts
- G, H (cover)
- sums of and over the rows in a node; the tree dump calls the node's cover
- Leaf weight w
- the log-odds a leaf adds, before shrinkage: ; the stored leaf value is
- Gain
- how much a split lowers the regularized objective; the split is kept only if gain
- Default direction
- for each split, the branch that rows with a missing value are sent to — chosen during training to maximize gain
The math
- current log-odds for row (sum of all trees so far)
- the label
- log-loss (binary cross-entropy) of one row
Differentiate with respect to the log-odds, not the probability. Using , the chain rule collapses beautifully:
- gradient: the signed error of the probability, in
- hessian: always positive, at most 0.25 (at ), → 0 as the model becomes confident
Round adds a tree that maps each to the weight of its leaf, . XGBoost minimizes the loss plus a penalty on the tree:
- number of leaves in the new tree
- weight of leaf (a log-odds increment)
- price per leaf (
gamma, aliasmin_split_loss, default 0) - L2 penalty on leaf weights (
reg_lambda, default 1)
Log-loss in is not quadratic, so XGBoost replaces it by its second-order Taylor expansion around the current — exactly what Newton's method does:
Drop the constant and group the rows by leaf (every row in leaf gets the same ). With and , the objective splits into one independent parabola per leaf:
Setting gives the leaf weight, and substituting it back gives the best value this tree structure can reach:
- a Newton step in log-odds: total residual over total curvature, with λ added to the curvature
- structure score: lower is better; each leaf contributes
To score a split of a node into left and right , compare the structure score with and without it. The node's own term is replaced by two children's terms, and one extra leaf costs :
- gradient and hessian sums of the rows sent left
- the same for the right child
What each hyperparameter does to the formulas
- λ (reg_lambda)
- added to every : shrinks toward 0, most strongly for leaves with small (few rows, or confident ones). Also lowers every gain, so fewer splits pass .
- γ (gamma)
- a fixed price per extra leaf: a split survives only if its gain exceeds . Pruning runs bottom-up, so a weak split can stay if a strong one sits below it.
- min_child_weight
- each child must have
min_child_weight. For log-loss , so at the default 1 means at least 4 rows, and a leaf of confident rows needs many more. - η (learning_rate)
- the model adds , not . The Taylor expansion is only accurate near the current , so small steps plus more rounds generalize better.
- α (reg_alpha)
- L1 on leaves: ; leaves with weak total push become exactly 0.
- max_delta_step
- clips ; useful for extremely imbalanced log-loss, where makes huge.
- scale_pos_weight
- multiplies and 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 it sorts only the rows where 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 , not .
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 and . Settings: stumps (max_depth = 1), , , , min_child_weight = 1.
| Row | Tenure | Calls | Churned | g (round 1) | h (round 1) |
|---|---|---|---|---|---|
| 1 | 2 | 1 | 1 | −0.5 | 0.25 |
| 2 | 4 | 5 | 1 | −0.5 | 0.25 |
| 3 | 5 | NaN | 1 | −0.5 | 0.25 |
| 4 | 7 | 2 | 0 | +0.5 | 0.25 |
| 5 | 10 | 6 | 1 | −0.5 | 0.25 |
| 6 | 14 | 2 | 0 | +0.5 | 0.25 |
| 7 | 18 | 5 | 1 | −0.5 | 0.25 |
| 8 | 22 | 0 | 0 | +0.5 | 0.25 |
| 9 | 27 | 4 | 0 | +0.5 | 0.25 |
| 10 | 33 | NaN | 1 | −0.5 | 0.25 |
| 11 | 40 | 3 | 0 | +0.5 | 0.25 |
| 12 | 48 | 1 | 0 | +0.5 | 0.25 |
Round 1, by hand
- 1Gradients and hessians. Every , so and . Root: , , so the root term .
- 2Candidate calls < 4.5, missing → right. Left = rows 1, 4, 6, 8, 9, 11, 12 (one churner, six stayers): , . Right = rows 2, 5, 7 plus the two NaN rows 3 and 10, all churners: , .
- 3Gain .
- 4Same threshold, missing → left. Then , and the right child has only rows 2, 5, 7: — blocked by
min_child_weight(its gain would have been 1.978). So the default direction for NaN is right. - 5Every other candidate scores lower (table below). The best tenure split, tenure < 6, would put the three youngest churners alone () and is also blocked; the best allowed tenure split is tenure < 12 with gain 1.818.
- 6Leaf weights. and . With shrinkage the stored leaf values are and .
- 7Update. Left rows: , . Right rows: , . Train log-loss drops from 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).
| Split | Missing → | G_L / H_L | G_R / H_R | Gain | Allowed? |
|---|---|---|---|---|---|
| calls < 4.5 | right | 2.5 / 1.75 | −2.5 / 1.25 | 5.051 | yes |
| calls < 3.5 | right | 2.0 / 1.50 | −2.0 / 1.50 | 3.200 | yes |
| tenure < 6 | — | −1.5 / 0.75 | 1.5 / 2.25 | 1.978 | no |
| calls < 4.5 | left | 1.5 / 2.25 | −1.5 / 0.75 | 1.978 | no |
| tenure < 12 | — | −1.5 / 1.25 | 1.5 / 1.75 | 1.818 | yes |
| calls < 2.5 | right | 1.5 / 1.25 | −1.5 / 1.75 | 1.818 | yes |
| calls < 3.5 | left | 1.0 / 2.00 | −1.0 / 1.00 | 0.833 | yes |
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, .
| Group | Rows | p after round 1 | g = p − y | h = p(1 − p) |
|---|---|---|---|---|
| left, churned | 1 | 0.4322 | −0.5678 | 0.2454 |
| left, stayed | 4, 6, 8, 9, 11, 12 | 0.4322 | +0.4322 | 0.2454 |
| right, churned | 2, 3, 5, 7, 10 | 0.5826 | −0.4174 | 0.2432 |
Round 2 and the prediction
- 1Best split is again calls < 4.5, NaN → right: , , , ; gain . Runner-up: calls < 3.5 with gain 2.139. Tenure < 6 (gain 1.697) is still blocked: .
- 2Leaves: and ; stored values and .
- 3Model after 2 trees: left rows , ; right rows , . Train log-loss 0.4987, accuracy 11/12.
- 4New customer: tenure 6 months, no call record. Both trees send NaN right: , so — flagged as a churn risk purely through the learned default direction.
The algorithm, step by step
XGBoost, binary:logistic
- 1Initialize. with =
base_score. - 2For : compute , , (optionally on a row subsample, with a column subsample per tree / level / node).
- 3Grow a tree from the root. At each node with sums , 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 .
- 4At each threshold between distinct values, skip it if either child has
min_child_weight; otherwise compute the gain. Keep the best (feature, threshold, default direction). - 5Split and recurse until
max_depthor no positive gain. Then prune bottom-up: any split whose children are leaves and whose gain is below is collapsed. - 6Leaves: (with the α soft-threshold and
max_delta_stepclip if set). - 7Update . Evaluate on a validation set; stop when it has not improved for
early_stopping_rounds. - 8Predict: ; class 1 if (or a tuned threshold).
Cost
- Exact greedy
- features are pre-sorted once into column blocks (); then each depth level is one linear scan over the non-missing entries: in total
- Histogram (default)
- values are bucketed into
max_bin= 256 bins; per node, accumulate per bin in and scan only the bins. Much faster for large ; also the method used on GPU - Memory
- the data matrix plus (two floats per row); histograms per node in hist mode
- Prediction
- per row, trivially parallel
Tuning in practice
| Parameter | Default | Typical range | Effect |
|---|---|---|---|
| n_estimators + early_stopping_rounds | 100 / off | up to 5000, stop after 50–100 flat rounds | number of trees; let early stopping choose it |
| learning_rate (η) | 0.3 | 0.01–0.1 | smaller = smoother, needs more trees |
| max_depth | 6 | 3–10 | interaction order; the main capacity knob |
| min_child_weight | 1 | 1–20 | minimum hessian per child: larger = fewer, more stable leaves |
| reg_lambda (λ) / reg_alpha (α) | 1 / 0 | λ 0.1–10, α 0–10 | shrink leaf weights; α zeroes weak leaves |
| gamma (γ) | 0 | 0–5 | minimum gain to keep a split |
| subsample / colsample_bytree | 1 / 1 | 0.6–0.9 | row / column sampling per tree: decorrelates trees, cuts variance |
| scale_pos_weight | 1 | #neg / #pos | rebalances g and h of positives for rare-event problems |
Variants and relatives
- Multiclass
multi:softprob: trees per round, one per class, with and (XGBoost doubles the softmax hessian)- tree_method
exact(all thresholds),approx(weighted quantile sketch: candidate thresholds at quantiles weighted by ),hist(default, fixed bins);device="cuda"for GPU- grow_policy
depthwise(default, level by level) orlossguide(best leaf first, like LightGBM)- Constraints
monotone_constraintsforces p to rise (or fall) with a feature;interaction_constraintslimits which features may share a branch- Categoricals
enable_categorical=Truewith 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
1import numpy as np23def sigmoid(z):4 return 1 / (1 + np.exp(-z))56def 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 scanned18 for i in idx:19 gA += gs[i]; hA += hs[i]20 nxt = i - 1 if miss_left else i + 121 last = not 0 <= nxt < len(xs)22 if (not last and xs[nxt] == xs[i]) or (last and not has_missing):23 continue24 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 sum26 continue27 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]) / 230 best = (gain, j, t, miss_left)31 return best3233def grow(X, g, h, lam, gamma, mcw, depth, max_depth):34 w = -g.sum() / (h.sum() + lam) # Newton step, shrunk by lambda35 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 pruning44 return {"leaf": w}45 return {"f": j, "t": t, "miss_left": miss_left, "gain": gain, "L": L, "R": R}4647def 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"]5354def 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 056 trees = []57 for _ in range(rounds):58 p = sigmoid(F)59 g, h = p - y, p * (1 - p) # log-loss gradient and hessian60 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 trees6465def predict_proba(trees, x, eta=0.3):66 return sigmoid(sum(eta * tree_value(t, x) for t in trees))6768nan = np.nan69X = 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)7273trees = fit(X, y)74for t in trees: # two stumps: print split and eta * leaf75 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 recorded79# calls < 4.5 gain 5.0505 missing -> right leaves -0.2727 0.333380# calls < 4.5 gain 3.4747 missing -> right leaves -0.2236 0.282681# 0.64931import numpy as np2from xgboost import XGBClassifier3from sklearn.metrics import log_loss45nan = np.nan6X = 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])910model = 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 calculation14)15model.fit(X, y) # NaN = missing, handled natively1617for 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))2223# 0:[f1<4.5] yes=1,no=2,missing=2,gain=5.05050468,cover=324# 1:leaf=-0.272727281,cover=1.7525# 2:leaf=0.333333373,cover=1.2526# 0:[f1<4.5] yes=1,no=2,missing=2,gain=3.47466874,cover=2.9337687527# 1:leaf=-0.223594904,cover=1.7178578428# 2:leaf=0.28256765,cover=1.2159107929# train log-loss 0.498730# p(churn | tenure 6, calls missing) 0.6493Use 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: , with and from the log-loss.
- ✓A second-order Taylor expansion turns each round into independent per-leaf parabolas: and split gain .
- ✓λ shrinks leaves, γ prices each extra leaf (bottom-up pruning), and
min_child_weightdemands 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.