Gradient Boosting & XGBoost

Residual fitting, shrinkage, XGBoost regularisation, early stopping

The random forest module ended on a specific limit, not a vague one: averaging many de-correlated trees kills variance, but it barely touches bias. If every tree in the forest is wrong in the same direction — a feature is missing, or the signal is genuinely subtle — a thousand of them just gives you a very stable version of the same wrong answer. Throwing more trees at a forest cannot fix that; recall that a forest's trees are all trained the same way, independently, on the full problem. So the question the forest left open is real: is there any way to train trees that attacks bias directly, instead of just averaging variance away?

In 1988 two researchers, Michael Kearns and Leslie Valiant, turned that question into something sharper. Suppose all you have is a pile of *weak* learners — models barely better than a coin flip, individually far too weak to fix anyone's bias. Could you chain a pile of weak learners into one *strong* learner that is nearly always right? Nobody knew. Two years later Robert Schapire proved the answer is yes, and the construction he found is called boosting.

Schapire's original construction, later refined into AdaBoost, does something concrete: it reweights rows, not trees. Train one weak tree. Look at which rows it got wrong, and make those rows *heavier* — literally increase how much they count — before training the next weak tree. That next tree, chasing the now-heavier misclassified rows, is forced to pay attention to exactly what the first tree missed. Repeat this a few hundred times, then combine all the trees, weighting each one by how accurate it was. Every tree is weak on its own; the chain of trees, each cleaning up the last one's blind spot, is strong.

Gradient boosting keeps AdaBoost's core move — train sequentially, each tree fixing what's left over — but rebuilds the "fixing" step around something more general than reweighting rows: fitting each new tree to what the current prediction still gets wrong. Watch it happen on numbers you can check by hand.

Four houses. House A: 800 sqft, 150k. House B: 1200 sqft, 200k. House C: 2000 sqft, 400k. House D: 3000 sqft, 600k. Start with the laziest possible model: predict the same number for every house, no matter its size. What number minimises the total squared error against four unequal targets? Calculus (or just recalling how the mean is defined) says the mean: (150+200+400+600)/4 = 337.5k. Call this F₀ = 337.5k — the initial prediction, before any tree has been fit.

Now name the misses — the residual at each house, true price minus F₀. House A: 150−337.5 = −187.5k. House B: 200−337.5 = −137.5k. House C: 400−337.5 = +62.5k. House D: 600−337.5 = +262.5k. Negative means the model over-guessed (the flat 337.5k prediction is too high for a cheap house); positive means it under-guessed. The two cheap houses were badly over-guessed; the two expensive ones badly under-guessed. Notice the residuals are the only information the next step gets — not the original prices.

Pause and predict, before the arithmetic: a tiny tree (one split, two leaves) is about to be fit to those four residuals using house size as the question. Three thresholds are worth trying — separating the cheapest house alone (size < 1000), separating the two cheapest (size < 1600), or separating the three cheapest (size < 2500). Which grouping do you expect minimises the tree's error?

Run all three, by hand. A tree fitting residuals picks the split that leaves each side's residuals as close to their own group average as possible — the same "minimise squared error within each leaf" objective a plain regression tree already uses. Split at size < 1000: left = {A: −187.5}, error 0 (a single point matches its own mean exactly); right = {B, C, D: −137.5, +62.5, +262.5}, mean 62.5, squared error ≈ 80,000. Total ≈ 80,000. Split at size < 1600: left = {A, B: −187.5, −137.5}, mean −162.5, squared error 1,250; right = {C, D: +62.5, +262.5}, mean +162.5, squared error 20,000. Total = 21,250 — far lower. Split at size < 2500: left = {A, B, C}, mean −87.5, squared error 35,000; right = {D}, error 0. Total = 35,000. The winner is size < 1600, by a wide margin — because it's the only split that separates the residuals by *sign* (A, B both over-guessed; C, D both under-guessed), where size < 1000 leaves a mixed-sign group of three on its right side.

So tree 1's rule is: size < 1600 → predict −162.5k (the left group's own mean residual); size ≥ 1600 → predict +162.5k. That's the tree's raw output — but gradient boosting never adds a tree's raw output straight in. It scales it first by the learning rate, usually written η (eta) — a fraction, chosen before training, that shrinks every tree's contribution to keep any single step cautious. Use η = 0.5 here. Tree 1's actual contribution becomes 0.5 × ∓162.5 = ∓81.25k.

New predictions, F₁ = F₀ + tree 1's shrunk contribution: House A and B (size < 1600): 337.5 − 81.25 = 256.25k. House C and D (size ≥ 1600): 337.5 + 81.25 = 418.75k. New residuals: A: 150−256.25 = −106.25k. B: 200−256.25 = −56.25k. C: 400−418.75 = −18.75k. D: 600−418.75 = +181.25k. The average miss size (mean absolute error) drops from 162.5k to 90.625k — a 44% drop — and the mean squared error drops from 31,718.75 to 11,914.06, a 62.4% drop, after touching only one shallow tree.

Fit tree 2 to these new residuals — same three candidate thresholds, same size feature. Split at size < 1000: total squared error ≈ 32,603. Split at size < 1600 (tree 1's own split, tried again): 1,250 + 20,000 = 21,250 — identical arithmetic to before, because A/B and C/D's *within-group* spread hasn't changed even though the numbers themselves have. Split at size < 2500: left = {A, B, C: −106.25, −56.25, −18.75}, mean ≈ −60.42, squared error ≈ 2,101 + 17 + 1,736 ≈ 3,854; right = {D: +181.25}, error 0. Total ≈ 3,854 — now the clear winner, a full split away from where tree 1 drew its line.

The split moved because the *residual pattern* moved. Tree 1 already fixed the small-vs-big gap; the biggest miss left standing is House D alone, still under-priced by 181.25k. Tree 2 isolates exactly that. This is the whole mechanism in miniature: boosting never re-groups by the original target — only by whichever residual is currently largest.

Tree 2's leaves: left (A, B, C) mean ≈ −60.42, scaled by η=0.5 → −30.21k; right (D) mean = 181.25, scaled → +90.63k. New predictions F₂: A and B → 226.04k, C → 388.54k, D → 509.38k. New residuals: −76.04, −26.04, +11.46, +90.63. Mean squared error falls to ≈3,701 — an 88.3% cumulative drop from F₀'s 31,718.75, after exactly two shallow trees. Two careful steps closed most of the gap; this module's separate boosting-rounds interactive carries the same idea further on a new curve, running eight rounds total and letting you watch training and held-out error diverge once the steps get too large.

Here is the idea that turns this from a neat trick into a general engine. You already know gradient descent: nudge a model's *numbers* a little in the direction that lowers the loss, repeat. Boosting does the same thing to a *function* instead — each round nudges the whole prediction function by bolting on one more small tree. And the "residual" fit at every round is not just intuitively the right target — for squared-error loss it *is* the negative gradient of the loss with respect to the current prediction, exactly. Swap in a different loss and only the formula for "residual" changes: for log loss it becomes (actual − predicted probability); for ranking or for a specific quantile it's something else again. The recipe itself never changes — fit a tree to the negative gradient, shrink it, add it on. That is why gradient boosting chases almost any goal you can write down as a loss.

For binary classification, that swap looks like this: the trees never see the raw 0/1 label. They fit the gradient of log loss in logit (log-odds) space, which works out to (actual − predicted probability) — the same residual idea, just computed after the sigmoid. So the trees accumulate margins/logits, and only at the very end does a sigmoid function σ(z) = 1/(1+e⁻ᶻ) [maps any real logit into a probability between 0 and 1] turn the summed logit into a probability — the same final step logistic regression uses, but with a sum of trees producing the logit instead of a linear equation.

Two dials, established above, keep this from wrecking itself, and recall why each exists: trees are kept deliberately shallow (depth 3–5) — the opposite of a random forest's "deeper is fine," because here each tree is one gradient step and a big greedy one overshoots the current residual's noise. And η, which you've now watched shrink two real contributions to ∓81.25k and then ∓30–90k, trades step size for step count — smaller η needs more trees but tends to land somewhere better. A third dial replaces guessing the tree count entirely: early stopping — keep adding trees, watch a held-out score, stop the moment it stops improving.

Plain gradient boosting, exactly as run by hand above, already works. So what was left for XGBoost to invent? Two things: it doesn't fully trust the tree-fitting step used above (minimise within-leaf squared error), because that specific rule only works cleanly for squared-error loss — for log loss or ranking, "minimise squared error of the residual" isn't even the right objective. And it has no built-in brake on split-happy trees beyond depth and η. XGBoost fixes both with one regularized objective, made explicit rather than left implicit:

$Obj = Σᵢ L(yᵢ, ŷᵢ) + Σₜ [γTₜ + ½λ‖wₜ‖²]$

Tₜ is the number of leaves in tree t (a count XGBoost controls directly), wₜ its leaf values, γ a penalty per leaf and λ an L2 penalty shrinking leaf values — both are hyperparameters fixed before training, dials you set, not anything learned. To make this workable for *any* differentiable loss, XGBoost doesn't minimise the true loss at each step — it Taylor-expands the loss around the current prediction, keeping terms up to second order: L(yᵢ, Fₜ₋₁(xᵢ)+f) ≈ L(yᵢ,Fₜ₋₁(xᵢ)) + gᵢf + ½hᵢf². gᵢ is the gradient (first derivative) — the same residual-flavoured quantity used above. hᵢ is the Hessian (second derivative) — how sharply the loss curves at that prediction — new, and worth asking why it's needed at all.

Recompute g and h for the four houses at F₀, using the convention L = ½(y−ŷ)² (chosen so the derivatives come out clean): gᵢ = ŷᵢ−yᵢ = −(residual), hᵢ = 1 for every sample, always, for squared-error loss. House A: g=187.5, h=1. House B: g=137.5, h=1. House C: g=−62.5, h=1. House D: g=−262.5, h=1. Every Hessian is exactly 1 — flat, carrying no information beyond "one sample counted here." So here's a fair objection: if the curvature term is just a constant 1, why does XGBoost bother computing it for regression at all?

Two answers, both checkable. First: the gain formula that uses g and h must also work for losses where the Hessian is *not* constant — for log loss, hᵢ = pᵢ(1−pᵢ), the predicted probability's own variance. A confidently-classified row at p=0.95 has h = 0.95×0.05 = 0.0475; a maximally uncertain row at p=0.50 has h = 0.5×0.5 = 0.25 — over 5× larger. The Hessian is measuring exactly how much the loss curves at that prediction, and for squared error it happens to curve the same everywhere (flat parabola, curvature 2 for every point, or 1 under the ½ convention used here) — the constant-1 case is the *boring* special case, not the general rule. Second, and directly checkable on the house data: XGBoost's split-scoring gain formula, expressed with g and h, has to reduce to exactly what tree 1 computed by hand above when h is constant — which is exactly the sanity check below.

Gain(split) = ½[G²_L/(H_L+λ) + G²_R/(H_R+λ) − G²_root/(H_root+λ)] − γ, where G_L = Σ gᵢ over the left group, H_L = Σ hᵢ over the left group (same for R and root). Take λ=0, γ=0 and re-score tree 1's three candidate splits. Root: G=187.5+137.5−62.5−262.5=0, H=4. Split at size<1600 (A,B | C,D): G_L=325, H_L=2; G_R=−325, H_R=2. Gain = ½[325²/2 + 325²/2 − 0] = ½[52,812.5+52,812.5] = 52,812.5. Split at size<1000: G_L=187.5,H_L=1; G_R=−187.5,H_R=3 → Gain = ½[35,156.25 + 11,718.75] = 23,437.5. Split at size<2500: G_L=262.5,H_L=3; G_R=−262.5,H_R=1 → Gain = ½[22,968.75+68,906.25] = 45,937.5. Same winner, same order, as the plain-SSE calculation above — because with h=1 and λ=0, Gain is exactly ½ × the SSE the split removes (52,812.5 = ½ × (126,875−21,250) = ½×105,625). The formula generalises the exact same idea "reduce squared error" so it still works when the loss isn't squared error.

λ earns its keep once it's non-zero. The leaf's optimal weight, derived by minimising the Taylor expansion with respect to the leaf value, is w* = −G/(H+λ) — at λ=0 this is just −G/H, the plain group mean used above (−325/2 = −162.5, matching tree 1's left leaf exactly). Set λ=2: w*_L = −325/(2+2) = −81.25 — half of the unregularized value. Set λ=6: w*_L = −325/(2+6) = −40.625 — smaller still, and a leaf with more samples (higher H) resists the same λ more than a sparse one, since λ competes against H, not against a flat multiplier. This is a genuinely different mechanism from η: η shrinks every tree's total output uniformly, after fitting; λ shrinks the optimal weight *inside* each leaf, during fitting, and shrinks sparse leaves harder than well-supported ones. Both regularize, neither replaces the other.

γ is the plainest of the three: a split must clear it or it doesn't happen. At λ=2, split at size<1600 scores Gain = ½[26,406.25+26,406.25−0] = 26,406.25. Set γ = 30,000 and that split is refused — the node stays a single leaf, even though a real residual pattern is sitting right there, because the improvement doesn't clear the cost of adding two more leaves to the tree. That is the "minimum-benefit bar" made numeric.

One more engineering problem plain gradient boosting doesn't solve: what does a tree do with a feature value that's simply *missing*? Add a second, hypothetical feature to the four houses — renovation_year, recorded as 2010 for House B and 2015 for House D, missing for A and C. Try a candidate split at year < 2012. Rows B and D have a real value to compare; A and C do not. XGBoost's answer is sparsity-aware split finding: try sending every missing row left, score it; try sending them all right, score it; keep whichever direction scores higher as that split's permanent default. Missing → left: left = {A,B,C} (G=262.5,H=3), right = {D} (G=−262.5,H=1) → Gain = ½[68,906.25/3 + 68,906.25] = 45,937.5. Missing → right: left = {B} (G=137.5,H=1), right = {A,C,D} (G=−137.5,H=3) → Gain = ½[18,906.25 + 6,302.08] = 12,604.17. Missing-left wins by more than 3.6×, so "left" is stored as this split's learned default — any future row missing renovation_year is routed left automatically, with no imputation step at all.

Scale is the last piece. Four houses have only three candidate size-thresholds to test — cheap to try all of them exhaustively, which is exactly what was done above. A real feature column can carry millions of distinct values, and testing every one at every split, at every tree, is the actual bottleneck of training. XGBoost's weighted quantile sketch approximates the search: instead of every unique value, it buckets candidates into a few hundred thresholds, chosen as percentiles of the feature — but weighted by each row's Hessian, not by a plain row count. Recall the p=0.5 vs p=0.95 contrast above (h=0.25 vs h=0.0475): a row near p=0.5 carries roughly 5× the weight of a confident one in the sketch, so the limited bucket budget gets spent where the loss is most curved and least settled — exactly the region where getting the threshold right actually matters, not wasted on already-confident predictions.

Two more dials borrow bagging's trick without renaming it: subsample gives each tree a random fraction of the *rows* (say 80%), and colsample_bytree gives each split a random fraction of the *columns* — so on a dataset with 20 features, one tree might only ever consider 16 of them per split. Neither changes the gain formula; both reduce how correlated consecutive trees' mistakes are, the same diversity argument the random forest module made for bagging, reused here for a different reason (speed and mild variance control, since bias-reduction is boosting's whole job already).

Know the resulting hyperparameters by name: `learning_rate` (η) — step size; `n_estimators` — tree count (let early stopping set it); `max_depth` — shallow, 3–6; `min_child_weight` — minimum Σh per leaf, a stronger overfitting guard than a raw sample count since it accounts for each row's curvature; `gamma` — the minimum split gain; `subsample` / `colsample_bytree` — row/column sampling; `reg_lambda` (λ, L2) / `reg_alpha` (L1) on leaf weights; `scale_pos_weight` for imbalance; `eval_metric` for early stopping. The high-leverage trio to tune first is learning_rate × n_estimators (traded off against each other) plus max_depth.

Because boosting relentlessly hunts whatever residual is largest, it will happily latch onto a leaky feature and inflate a validation score in a way a forest's averaging would partly wash out. Validation discipline matters more here than anywhere: time-based splits for temporal data, group-based splits when rows cluster per entity, and early stopping run on a genuine validation fold — never the test set, or the test set has leaked into model selection. A boosting model that looks suspiciously good usually has a leak.

XGBoost exposes three importance types and they disagree: weight (how often a feature is split on), cover (how many samples its splits touch), and gain (how much its splits actually improved the loss — usually the most meaningful of the three). Never quote "feature importance" without saying which one. And as with forests, correlated features distort all three — cross-check with permutation importance or SHAP.

XGBoost, LightGBM, and CatBoost are not interchangeable. XGBoost is the stable, general-purpose default — everything derived above is its mechanism. LightGBM grows trees leaf-wise instead of level-wise and buckets feature values more aggressively, so it's usually much faster on large data (at a slightly higher overfitting risk on small data). CatBoost handles categorical features natively via ordered target statistics and often wins on categorical-heavy data with less preprocessing. Rough guide: large data → LightGBM; lots of categoricals → CatBoost; safe default → XGBoost.

Under class imbalance, boosting handles rare classes better than most models by default, but still tune `scale_pos_weight` (roughly negatives/positives) to up-weight the minority, move the decision threshold, and judge with PR-AUC or recall@K rather than raw accuracy. Check calibration too — heavy imbalance plus regularisation can leave predicted probabilities off even when the ranking of predictions is good.

Zoom out to the crisis this module opened with. A random forest reduces variance and stops — it cannot touch bias, because every tree attacks the same problem independently. Gradient boosting attacks bias directly, by training trees in a sequence where each one's entire job is the residual the team has left over — and that residual is the negative gradient of whatever loss you hand it, so the same recipe reaches regression, classification, and ranking alike. XGBoost's contribution sits one layer beneath that: a Taylor-expanded, regularized objective that scores every candidate split with both gradient and Hessian, so the exact same gain formula that reduces cleanly to plain SSE-reduction for regression also holds together for losses where the curvature genuinely varies — which is precisely why it, and its descendants, still win most tabular-data competitions.

Key points

• What gradient boosting is, and when to reach for it: trees trained in a line, each one fixing the team's leftover mistakes. Once it is tuned, gradient boosting is usually the most accurate thing you can run on tabular data — it chips away at both bias and variance, where a random forest only fights variance. That accuracy is why it wins most structured-data competitions. Use XGBoost or LightGBM instead of the basic scikit-learn version: both are faster, come with regularisation built in, and support early stopping out of the box. Lean on LightGBM for very large datasets (its leaf-by-leaf growth is quicker) and XGBoost for smaller ones, where the extra caution against overfitting helps.
• The trap: fixing the number of trees up front instead of letting early stopping choose it. With a learning rate of 0.1 and 1000 trees hard-coded, the held-out loss usually bottoms out somewhere around 200–400 trees and then starts climbing as the extra trees begin memorising noise. Hard-code the count and you sail right past the best point into an overfit model. Instead, always turn on early stopping (stop after about 50 rounds with no improvement) and let the model pick its own tree count. Then, to squeeze out a little more, lower the learning rate and re-run — smaller steps often reach a slightly better place.
• The check to run: plot the training loss and the held-out loss against the number of trees. Held-out loss still falling means you are underfitting — add trees or lower the learning rate. Held-out loss flat and close to the training loss means you are in good shape. Held-out loss creeping up while training loss keeps dropping means you are overfitting — stop earlier, use shallower trees, or let each tree see only a random subset of the rows. If the held-out loss never comes down at all, your learning rate is probably too high; start it around 0.05 to 0.1.
• Place it in the family and know the objective: AdaBoost reweights rows, gradient boosting fits the gradient of any loss, and XGBoost regularises explicitly. AdaBoost up-weights misclassified rows; gradient boosting generalises that to fitting each tree to the negative gradient of a differentiable loss (AdaBoost ≈ gradient boosting with exponential loss). For binary classification the trees fit the log-loss gradient (actual − predicted probability) in logit space and are squashed to probabilities only at the end. XGBoost's objective is loss + γT + ½λ‖w‖², and it scores splits with gradients *and* Hessians minus γ — a split must clear γ to be made.
• Second-order matters even though squared-error's Hessian is a constant 1: the same gain formula must also work when it isn't. XGBoost Taylor-expands the loss to second order per sample — gradient g and Hessian h — instead of only using the residual. For squared-error loss h=1 for every row, so the extra term looks pointless there; but for log loss h = p(1−p), which swings from 0.25 at maximum uncertainty (p=0.5) down to about 0.05 at high confidence (p=0.95). The Hessian is literally how much the loss curves at that prediction — flat and constant for squared error, sharply variable for log loss — and the gain formula, Gain = ½[G²_L/(H_L+λ) + G²_R/(H_R+λ) − G²_root/(H_root+λ)] − γ, has to hold together for both. With λ=0 it reduces to exactly half the squared-error reduction a plain regression-tree split removes — a checkable sanity floor, not just an assertion.
• λ and η are two different regularisers, not the same dial twice — and missing values get a learned route, not an imputed value. η (learning rate) rescales every tree's total output uniformly, after the tree is fit. λ (L2 on leaf weights) shrinks the *optimal* leaf weight w*=−G/(H+λ) during fitting itself, and shrinks a sparsely-supported leaf harder than a well-populated one, since λ competes against each leaf's own Σh. Missing feature values get sparsity-aware split finding: XGBoost tries routing them both directions at each candidate split and keeps whichever scores higher gain as that split's permanent default — no imputation. And at scale, exhaustively testing every unique feature value is the real bottleneck, so XGBoost's weighted quantile sketch buckets candidates by Hessian-weighted percentiles instead, spending its resolution on the uncertain, high-curvature region of the data rather than treating every row equally.
• Boosting is leakage-sensitive, so tune the right knobs and validate honestly. Because it hunts the residual, boosting will exploit a leaky feature that a forest averages away — so use time-based or group-based splits and run early stopping on a validation fold, never the test set. Key knobs: `learning_rate`×`n_estimators` (traded off), `max_depth`, `min_child_weight`, `gamma`, `subsample`/`colsample_bytree`, `reg_lambda`/`reg_alpha`, and `scale_pos_weight` for imbalance. Rough library map: large data → LightGBM (leaf-wise, fast), categorical-heavy → CatBoost (native handling), safe default → XGBoost. And name which importance you mean — weight, cover, or gain (gain is usually most meaningful) — since they disagree and correlated features distort all three.

Recap

• Random forest fixes variance, not bias — gradient boosting attacks bias directly: trees trained in a line, each fitting the team's current residual.
• Residual = negative gradient of the loss → fit a tree to it, shrink by η, add it in, repeat — gradient descent in function space.
• Handles any differentiable loss this way: regression residual, or (actual − predicted probability) in logit space for classification, squashed by sigmoid only at the end.
• Two control dials, one recipe: trees stay shallow (3–5) so no single step overshoots; η shrinks each step; early stopping (not a fixed tree count) sizes the ensemble.
• XGBoost's objective: Obj = Σ L(y,ŷ) + Σ[γT + ½λ‖w‖²] — Taylor-expand the loss to gradient g and Hessian h per sample (h=1 for squared error, h=p(1−p) for log loss).
• Gain = ½[G²_L/(H_L+λ) + G²_R/(H_R+λ) − G²_root/(H_root+λ)] − γ — reduces to ½×SSE-reduction when λ=0,h=1; a split must clear γ or the node stays a leaf.
• λ ≠ η: λ shrinks the optimal leaf weight w*=−G/(H+λ) during fitting (harder on sparse leaves); η rescales every tree's whole output after fitting.
• Sparsity-aware routing: missing values tried both directions per split, higher-gain direction becomes the learned default — no imputation.
• Weighted quantile sketch: approximates split search via Hessian-weighted buckets, spending resolution where the loss curves most.
• Family: AdaBoost reweights rows, gradient boosting fits the gradient, XGBoost regularises explicitly + uses curvature.
• Leakage-sensitive — tune the right knobs (learning_rate×n_estimators, max_depth, min_child_weight, subsample/colsample) and validate with time- or group-based splits.

Check your understanding