# XGBoost

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

Source: https://www.mlfoundry.in/learn/xgboost  
Section: ML Algorithms › Supervised · Classification  
Level: core · 17 min read · updated 2026-10-07

**XGBoost (for classification):** predicts the **log-odds** of the positive class as a sum of small trees, $F(x)=F_0+\eta\sum_m f_m(x)$, and turns it into a probability with the sigmoid, $p=\sigma(F)$. Each new tree is grown on the **gradients** $g_i=p_i-y_i$ and **hessians** $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+\lambda)$.

- **Task:** Binary classification (`binary:logistic`), multiclass (`multi:softprob`), ranking; this article: binary
- **Input → output:** feature vector $x$ (NaN allowed) → $p(y=1\mid x)=\sigma\big(F_0+\eta\sum_{m=1}^{M} f_m(x)\big)$
- **Learns:** $M$ trees; per internal node a feature, a threshold and a default direction for missing values; per leaf a log-odds weight $w_j$
- **Training:** exact greedy $O(M\cdot D\cdot \lVert x\rVert_0)$ after one $O(\lVert x\rVert_0\log n)$ pre-sort; histogram mode (the default since 2.0) bins features first
- **Prediction:** $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.97$ and a row sitting at $p=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 ($g_i$), and how *sure* that local picture is ($h_i$, the curvature). A row at $p=0.5$ has the largest curvature, 0.25; a row at $p=0.99$ has almost none. Then grow a tree whose leaves are **Newton steps**: total push $G$ divided by total curvature $H$, with $\lambda$ added to $H$ 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 $g$ and $h$, and repeat.

**Vocabulary**

- **Margin / log-odds:** $F(x)=\log\frac{p}{1-p}$, the raw tree sum before the sigmoid; `output_margin=True` returns it
- **base_score:** the starting probability $p_0$; $F_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ᵢ:** $\partial l/\partial F_i=p_i-y_i$: negative for positives the model under-predicts, positive for negatives it over-predicts
- **Hessian hᵢ:** $\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 $g_i$ and $h_i$ over the rows in a node; the tree dump calls $H$ the node's **cover**
- **Leaf weight w:** the log-odds a leaf adds, before shrinkage: $w^*=-G/(H+\lambda)$; the stored leaf value is $\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

$$
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]
$$

- $F_i$: current log-odds for row $i$ (sum of all trees so far)
- $y_i\in\{0,1\}$: the label
- $l$: log-loss (binary cross-entropy) of one row

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

$$
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)
$$

- $g_i$: gradient: the signed error of the probability, in $(-1,1)$
- $h_i$: hessian: always positive, at most 0.25 (at $p_i=0.5$), → 0 as the model becomes confident

Round $m$ adds a tree $f_m$ that maps each $x$ to the weight of its leaf, $f_m(x)=w_{q(x)}$. XGBoost minimizes the loss **plus a penalty on the tree**:

$$
\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
$$

- $T$: number of leaves in the new tree
- $w_j$: weight of leaf $j$ (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 $F$ is not quadratic, so XGBoost replaces it by its second-order Taylor expansion around the current $F_i$ — exactly what Newton's method does:

$$
l(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 $j$ gets the same $f=w_j$). With $G_j=\sum_{i\in j}g_i$ and $H_j=\sum_{i\in j}h_i$, the objective splits into one independent parabola per leaf:

$$
\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 $\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:

$$
w_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
$$

- $w_j^*$: a Newton step in log-odds: total residual over total curvature, with λ added to the curvature
- $\tilde{\mathcal L}^*$: structure score: lower is better; each leaf contributes $-\tfrac12 G_j^2/(H_j+\lambda)$

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

$$
\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
$$

- $G_L,H_L$: gradient and hessian sums of the rows sent left
- $G_R,H_R$: the same for the right child

> **The factor ½:** The paper writes $\tfrac12[\dots]-\gamma$. The library computes the bracket without the ½ — that is the `gain` printed in tree dumps — and prunes a split when this unhalved gain is below $\gamma$. All gains in this article are on the library's scale, so they match `get_dump(with_stats=True)`.

**What each hyperparameter does to the formulas**

- **λ (reg_lambda):** added to every $H$: shrinks $w^*$ toward 0, most strongly for leaves with small $H$ (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\ge$ `min_child_weight`. For log-loss $H=\sum p_i(1-p_i)$, so at $p=0.5$ the default 1 means **at least 4 rows**, and a leaf of confident rows needs many more.
- **η (learning_rate):** the model adds $\eta\,w^*$, not $w^*$. The Taylor expansion is only accurate near the current $F$, so small steps plus more rounds generalize better.
- **α (reg_alpha):** L1 on leaves: $w^*=-\operatorname{sign}(G)\max(|G|-\alpha,0)/(H+\lambda)$; leaves with weak total push become exactly 0.
- **max_delta_step:** clips $|w^*|$; useful for extremely imbalanced log-loss, where $H\to0$ makes $-G/H$ huge.
- **scale_pos_weight:** multiplies $g_i$ and $h_i$ of positive rows; a common start is (number of negatives) / (number of positives).

> **Why the hessian matters for classification:** Take a leaf of 3 positives the model already scores at $p=0.95$. Each has $g=-0.05$, $h=0.0475$, so $G=-0.15$, $H=0.1425$. A pure Newton step would add $-G/H=1.053$ log-odds — a large jump for rows that are already right. With $\lambda=1$ it becomes $0.15/1.1425=0.131$, and with `min_child_weight` = 1 the leaf is not even allowed ($H<1$). The hessian is how XGBoost knows that confident rows no longer deserve their own leaves. (Friedman's classic gradient boosting also uses $\sum r/\sum p(1-p)$ for its *leaf values*, but it chooses the *splits* by least squares on residuals; XGBoost uses $g$, $h$ and $\lambda$ in the split score too.)

## 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 $j$ it sorts only the rows where $x_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 $\lVert x\rVert_0$, not $n\cdot d$.

> **Do not impute what XGBoost can route:** Filling NaN with 0 or the mean merges *not recorded* with a real value. If missingness itself carries signal — in the example below, both customers with no call record churned — the learned direction captures it, and imputation destroys it. Keep NaN as NaN (`missing=np.nan` is the default), and if your data uses a sentinel such as −999, declare it with `missing=-999`.

## 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 $p_0=0.5$ and $F_0=0$. Settings: stumps (`max_depth` = 1), $\eta=0.3$, $\lambda=1$, $\gamma=0$, `min_child_weight` = 1.

Churn data. Highlighted: the 5 rows sent right by the first split (calls ≥ 4.5 or missing).

| 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**

1. **Gradients and hessians.** Every $p_i=\sigma(0)=0.5$, so $g_i=0.5-y_i=\mp0.5$ and $h_i=0.25$. Root: $G=0$, $H=3$, so the root term $G^2/(H+\lambda)=0$.
2. **Candidate calls < 4.5, missing → right.** Left = rows 1, 4, 6, 8, 9, 11, 12 (one churner, six stayers): $G_L=-0.5+6(0.5)=2.5$, $H_L=1.75$. Right = rows 2, 5, 7 plus the two NaN rows 3 and 10, all churners: $G_R=-2.5$, $H_R=1.25$.
3. **Gain** $=\frac{2.5^2}{1.75+1}+\frac{(-2.5)^2}{1.25+1}-0=2.273+2.778=5.051$.
4. **Same threshold, missing → left.** Then $G_L=1.5$, $H_L=2.25$ and the right child has only rows 2, 5, 7: $H_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. **Every other candidate scores lower** (table below). The best tenure split, tenure < 6, would put the three youngest churners alone ($H_L=0.75$) and is also blocked; the best *allowed* tenure split is tenure < 12 with gain 1.818.
6. **Leaf weights.** $w_L^*=-\frac{2.5}{1.75+1}=-0.909$ and $w_R^*=-\frac{-2.5}{1.25+1}=+1.111$. With shrinkage the stored leaf values are $\eta w^*=-0.273$ and $+0.333$.
7. **Update.** Left rows: $F=-0.273$, $p=\sigma(-0.273)=0.432$. Right rows: $F=0.333$, $p=0.583$. Train log-loss drops from $\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).

Round 1 candidates on the library's gain scale (λ = 1). Blocked = a child has H < min_child_weight = 1.

| 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, $g_1=0.432-1=-0.568$.

Inputs to tree 2. Sums: G = −0.0615, H = 2.9338 (down from 3: the model is less uncertain).

| 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**

1. **Best split** is again calls < 4.5, NaN → right: $G_L=2.0257$, $H_L=1.7179$, $G_R=-2.0871$, $H_R=1.2159$; gain $=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: $H_L=0.732$.
2. **Leaves:** $w_L^*=-2.0257/2.7179=-0.745$ and $w_R^*=2.0871/2.2159=+0.942$; stored values $\eta w^*=-0.224$ and $+0.283$.
3. **Model after 2 trees:** left rows $F=-0.273-0.224=-0.496$, $p=0.378$; right rows $F=0.333+0.283=0.616$, $p=0.649$. Train log-loss 0.4987, accuracy 11/12.
4. **New customer:** tenure 6 months, **no call record**. Both trees send NaN right: $F=0+0.333+0.283=0.616$, so $p(\text{churn})=\sigma(0.616)=0.649$ — flagged as a churn risk purely through the learned default direction.

> Figure: 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. **Initialize.** $F_i=F_0=\log\frac{p_0}{1-p_0}$ with $p_0$ = `base_score`.
2. **For** $m=1,\dots,M$: compute $p_i=\sigma(F_i)$, $g_i=p_i-y_i$, $h_i=p_i(1-p_i)$ (optionally on a row subsample, with a column subsample per tree / level / node).
3. **Grow a tree from the root.** At each node with sums $G,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 $G_L,H_L$.
4. At each threshold between distinct values, skip it if either child has $H<$ `min_child_weight`; otherwise compute the gain. Keep the best (feature, threshold, default direction).
5. Split 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. **Leaves:** $w_j^*=-G_j/(H_j+\lambda)$ (with the α soft-threshold and `max_delta_step` clip if set).
7. **Update** $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. **Predict:** $p(x)=\sigma\big(F_0+\eta\sum_m w^{(m)}_{q_m(x)}\big)$; class 1 if $p>0.5$ (or a tuned threshold).

**Cost**

- **Exact greedy:** features are pre-sorted once into column blocks ($O(\lVert x\rVert_0\log n)$); then each depth level is one linear scan over the non-missing entries: $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,H$ per bin in $O(\text{rows})$ and scan only the bins. Much faster for large $n$; also the method used on GPU
- **Memory:** the data matrix plus $g,h$ (two floats per row); histograms per node in hist mode
- **Prediction:** $O(M\cdot D)$ per row, trivially parallel

## Tuning in practice

The knobs that matter, defaults in xgboost 3, and a sensible search range.

| 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 |

> **One recipe that rarely fails:** Fix `learning_rate` at 0.05, set `n_estimators` high with `early_stopping_rounds` = 100 on a validation split, then tune `max_depth` and `min_child_weight` together, then `subsample` / `colsample_bytree`, then λ / γ. Finally lower the learning rate and let early stopping add trees.

**Variants and relatives**

- **Multiclass:** `multi:softprob`: $K$ trees per round, one per class, with $g_{ik}=p_{ik}-y_{ik}$ and $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 $h_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
import numpy as np

def sigmoid(z):
    return 1 / (1 + np.exp(-z))

def best_split(X, g, h, lam, mcw):
    """Exact greedy, sparsity-aware: every threshold, both default directions for missing values."""
    G, H = g.sum(), h.sum()
    best = (0.0, None, None, None)                       # (gain, feature, threshold, missing_left)
    for j in range(X.shape[1]):
        ok = ~np.isnan(X[:, j])
        order = np.argsort(X[ok, j], kind="stable")
        xs, gs, hs = X[ok, j][order], g[ok][order], h[ok][order]
        has_missing = not ok.all()
        for miss_left in ([False, True] if has_missing else [True]):
            idx = range(len(xs) - 1, -1, -1) if miss_left else range(len(xs))
            gA = hA = 0.0                                # stats of the side being scanned
            for i in idx:
                gA += gs[i]; hA += hs[i]
                nxt = i - 1 if miss_left else i + 1
                last = not 0 <= nxt < len(xs)
                if (not last and xs[nxt] == xs[i]) or (last and not has_missing):
                    continue
                gB, hB = G - gA, H - hA                  # the other side (incl. missing rows)
                if min(hA, hB) < mcw - 1e-9:             # min_child_weight acts on the hessian sum
                    continue
                gain = gA**2 / (hA + lam) + gB**2 / (hB + lam) - G**2 / (H + lam)
                if gain > best[0]:
                    t = xs[i] + (-1e-6 if miss_left else 1e-6) if last else (xs[i] + xs[nxt]) / 2
                    best = (gain, j, t, miss_left)
    return best

def grow(X, g, h, lam, gamma, mcw, depth, max_depth):
    w = -g.sum() / (h.sum() + lam)                       # Newton step, shrunk by lambda
    if depth == max_depth:
        return {"leaf": w}
    gain, j, t, miss_left = best_split(X, g, h, lam, mcw)
    if j is None:
        return {"leaf": w}
    left = np.where(np.isnan(X[:, j]), miss_left, X[:, j] < t)
    L = grow(X[left], g[left], h[left], lam, gamma, mcw, depth + 1, max_depth)
    R = grow(X[~left], g[~left], h[~left], lam, gamma, mcw, depth + 1, max_depth)
    if gain < gamma and "leaf" in L and "leaf" in R:     # bottom-up gamma pruning
        return {"leaf": w}
    return {"f": j, "t": t, "miss_left": miss_left, "gain": gain, "L": L, "R": R}

def tree_value(node, x):
    while "leaf" not in node:
        v = x[node["f"]]
        go_left = node["miss_left"] if np.isnan(v) else v < node["t"]
        node = node["L"] if go_left else node["R"]
    return node["leaf"]

def fit(X, y, rounds=2, eta=0.3, lam=1.0, gamma=0.0, mcw=1.0, max_depth=1):
    F = np.zeros(len(y))                                 # base_score 0.5 -> log-odds 0
    trees = []
    for _ in range(rounds):
        p = sigmoid(F)
        g, h = p - y, p * (1 - p)                        # log-loss gradient and hessian
        tree = grow(X, g, h, lam, gamma, mcw, 0, max_depth)
        trees.append(tree)
        F = F + eta * np.array([tree_value(tree, x) for x in X])
    return trees

def predict_proba(trees, x, eta=0.3):
    return sigmoid(sum(eta * tree_value(t, x) for t in trees))

nan = np.nan
X = np.array([[2, 1], [4, 5], [5, nan], [7, 2], [10, 6], [14, 2],
              [18, 5], [22, 0], [27, 4], [33, nan], [40, 3], [48, 1]], float)
y = np.array([1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0], float)

trees = fit(X, y)
for t in trees:                                     # two stumps: print split and eta * leaf
    print(["tenure", "calls"][t["f"]], "<", t["t"], "gain", round(t["gain"], 4),
          "missing ->", "left" if t["miss_left"] else "right",
          "leaves", round(0.3 * t["L"]["leaf"], 4), round(0.3 * t["R"]["leaf"], 4))
print(round(predict_proba(trees, np.array([6, nan])), 4))   # new customer, calls not recorded
# calls < 4.5 gain 5.0505 missing -> right leaves -0.2727 0.3333
# calls < 4.5 gain 3.4747 missing -> right leaves -0.2236 0.2826
# 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
import numpy as np
from xgboost import XGBClassifier
from sklearn.metrics import log_loss

nan = np.nan
X = np.array([[2, 1], [4, 5], [5, nan], [7, 2], [10, 6], [14, 2],
              [18, 5], [22, 0], [27, 4], [33, nan], [40, 3], [48, 1]], float)
y = np.array([1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0])

model = XGBClassifier(
    n_estimators=2, max_depth=1, learning_rate=0.3,
    reg_lambda=1.0, gamma=0.0, min_child_weight=1.0,
    base_score=0.5, tree_method="exact",            # match the hand calculation
)
model.fit(X, y)                                     # NaN = missing, handled natively

for tree in model.get_booster().get_dump(with_stats=True):
    print(tree)
p = model.predict_proba(X)[:, 1]
print("train log-loss", round(log_loss(y, p), 4))
print("p(churn | tenure 6, calls missing)", round(float(model.predict_proba([[6, nan]])[0, 1]), 4))

# 0:[f1<4.5] yes=1,no=2,missing=2,gain=5.05050468,cover=3
#     1:leaf=-0.272727281,cover=1.75
#     2:leaf=0.333333373,cover=1.25
# 0:[f1<4.5] yes=1,no=2,missing=2,gain=3.47466874,cover=2.93376875
#     1:leaf=-0.223594904,cover=1.71785784
#     2:leaf=0.28256765,cover=1.21591079
# train log-loss 0.4987
# 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.

> **Reading the dump:** `missing=2` means NaN goes to node 2, the right child. `cover` is the hessian sum H, not a row count: 1.75 = 7 rows × 0.25. On real data, drop the exact tree method (the default `hist` is far faster) and pass a validation set with `eval_set` plus `early_stopping_rounds`.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **Overfitting with the default η = 0.3 and no early stopping:** Training log-loss always keeps falling. Without a validation set and `early_stopping_rounds`, 1000 trees at η = 0.3 will memorize noise. Lower the learning rate and let the validation log-loss pick the number of trees.

> **scale_pos_weight distorts probabilities:** Up-weighting positives shifts the whole log-odds scale, so `predict_proba` no longer estimates the true rate. If you need calibrated probabilities, train unweighted and move the decision threshold instead (or recalibrate afterwards).

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

- A. g = 0.2, h = 0.8
- B. g = −0.2, h = 0.16
- C. g = −0.8, h = 0.2
- D. g = 0.2, h = 0.16

**Answer:** B. g = −0.2, h = 0.16 — $g=p-y=0.8-1=-0.2$ (negative: the model wants to raise its log-odds) and $h=p(1-p)=0.8\cdot0.2=0.16$.

**Question:** 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?

- A. 2.000
- B. 1.111
- C. 0.600
- D. 0.333

**Answer:** D. 0.333 — $w^*=-G/(H+\lambda)=2.5/2.25=1.111$, and the model adds $\eta w^*=0.3\cdot1.111=0.333$ — the right leaf of tree 1 in the worked example.

**Question:** 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?

- A. 1
- B. 2
- C. 4
- D. 10

**Answer:** C. 4 — min_child_weight bounds the hessian sum, not the row count. At $p=0.5$ each row has $h=0.25$, so $H\ge1$ needs at least 4 rows — and more once the model grows confident and $h$ shrinks.

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

- A. replaces it with the training mean of that feature
- B. sends it down both branches and averages the leaves
- C. follows the default direction learned for that node during training
- D. raises an error unless the data were imputed

**Answer:** C. follows the default direction learned for that node during training — During split finding the missing rows were tried on both sides and the side with the higher gain was stored as the node's default direction; NaN simply follows it.

**Key points**

- XGBoost boosts in log-odds: $p=\sigma(F_0+\eta\sum_m f_m(x))$, with $g_i=p_i-y_i$ and $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+\lambda)$ and split gain $\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
