03 — Ensembles & Boosting

An ensemble is one prediction assembled out of many models instead of one.

There are three ways that assembly can help: averaging away instability, forcing the members to disagree, and correcting mistakes in sequence. All three fall out of one equation, derived in The decomposition everything follows from.

The chapter then follows the third of those all the way to the libraries people actually run — XGBoost, LightGBM and CatBoost, known collectively as GBDTs (gradient-boosted decision trees).

When you finish, you should be able to look at a training curve, name which term of that equation is hurting you, name the mechanism that fixes it, state what that mechanism assumes about your data, and defend every hyperparameter with arithmetic instead of folklore.

What goes in, and what comes out

Every model in this chapter has the same contract.

The input is a table: n rows, one per example, and p columns, one per feature — age, income, n_prior_claims, country. Write the table as X and the column you are trying to predict as y.

The output is one number per row. For regression that is a real number, such as a predicted claim cost. For classification it is a score squashed into a probability, such as the chance that a transaction is fraud.

Nothing in this chapter changes that contract. What changes is how the one number is produced — an average over many trees, or a running sum of many trees — and how those trees are grown.

The one building block: a decision tree

Everything here is assembled from decision trees, so here is the whole idea before it is needed.

A decision tree sorts rows by asking yes/no questions about one column at a time — “is income > 50000?” Each answer sends the row to one of two children.

Repeat, and every row eventually lands in a leaf: a terminal node where no further question is asked. Every row in a leaf receives the same prediction, normally the average label of the training rows that landed there.

Choosing a question at a node means scoring every candidate split by how much it shrinks the spread of the labels on the two sides, then keeping the best one. That shrinkage is the split gain. “Spread of the labels” has a name — impurity.

Three words for tree sizes, used throughout:

• A stump is a tree with exactly one question.
• A tree is unpruned when it was grown until its leaves hold almost identical labels.
• Pruning means cutting branches back afterwards, to make the tree smaller and less specific to the training rows.

Decision trees derives the split criteria in full, and why trees overfit is worked there too. The section you just read is all this chapter assumes.

Symbols, and the ones that collide

Several symbols in this chapter get reused for unrelated things, because two separate research literatures reached for the same letters. Each collision is called out again where it happens; this table is the one place to look them all up.

The through-line

Every method in this chapter is an attack on one of two terms in a single equation. Get the equation first and the rest of the chapter stops being a list of algorithms and becomes a sequence of fixes, each one repairing a specific weakness in the thing before it.

Bagging cuts variance, random forests cut the part of the variance bagging cannot reach, boosting cuts bias, and every GBDT since 2016 is an engineering fix to boosting’s cost or its leakage.

1. The decomposition everything follows from

Here is that equation: the three-way split of test error. The derivation is short, what it assumes matters more than it looks, and its three terms dictate the order everything afterwards has to come in.

The setup, in words

Assume y = f(x) + eps with E[eps] = 0 and Var(eps) = sigma^2.

Unpacked: there is a true underlying relationship f between the features and the label, and every observed label is that relationship plus some random noise eps (the Greek letter epsilon). That noise averages to zero and has a constant spread.

Two pieces of notation carry the whole derivation. E[...] is an expectation — the long-run average over whatever is random. Var(...) is a variance — the average squared distance from that average.

Two things are random here, and keeping them apart is the point of the exercise. One is the label noise eps. The other is which training set you happened to get: you fit a model f_hat on a random training set D, and a different draw of D would have given you a different f_hat.

Now pick one fixed input x and ask for the expected squared error there, averaging over both sources of randomness.

The derivation, one line at a time

E[(y - f_hat(x))^2]
  = E[(f(x) + eps - f_hat(x))^2]
  = E[(f(x) - f_hat(x))^2] + sigma^2                    eps independent, mean 0

now add and subtract the average prediction  Ef := E_D[f_hat(x)]:

  = E[(f(x) - Ef + Ef - f_hat(x))^2] + sigma^2
  = (f(x) - Ef)^2 + E[(Ef - f_hat(x))^2] + 2·(f(x) - Ef)·E[Ef - f_hat(x)] + sigma^2
                                              ^^^^^^^^^^^^^^^^^^^^^^^^^ = 0 by definition

  =    Bias^2      +     Variance     +   sigma^2

Line by line:

1. Substitute y = f(x) + eps.
2. Expand. The cross term between eps and everything else drops out because eps is independent of the model and has mean zero, leaving sigma^2 on its own.
3. Add and subtract Ef, the average prediction: the value you would get at x if you fit on every training set you might have drawn and averaged the results. Adding and subtracting the same quantity changes nothing, which is why you are allowed to do it.
4. Expand the square. You get three pieces plus a cross term.

The cross term is the only non-obvious move, so name it. E[Ef - f_hat(x)] is the average of “average prediction minus actual prediction” — and the average prediction is the average of the actual predictions, so that difference averages to exactly zero. The cross term vanishes by construction.

Reading the three terms

What survives is three terms, and each has a plain reading.

• Bias^2 — (f(x) - Ef)^2. The error you would still make with infinite data, because your model class cannot represent f even on average.
• Variance — E[(Ef - f_hat(x))^2]. How much your model moves when the training sample is redrawn.
• sigma^2 — the noise in the labels themselves. Unreachable.

Two of the three are addressable, and every ensemble method in this chapter addresses exactly one of them. The third one — sigma^2 — no model, no amount of data and no ensemble can remove, which makes it the floor that every score in this chapter is measured against.

What the decomposition assumes, and what breaks it

The clean additive split above needs three things to hold.

The loss is squared error. For the 0/1 loss of classification no equally tidy additive decomposition exists, so the intuition transfers but the algebra does not.

The noise is additive, mean-zero and the same size everywhere. If the noise grows with x — larger claims are noisier than small ones — then sigma^2 is a function of x, and the single number in the equation is only an average.

The expectation is over redraws of a training set of fixed size n from one fixed distribution. That requires the rows to be independent and identically distributed (i.i.d.): each row drawn the same way, and no row telling you anything about another. Time series and grouped data violate this directly — yesterday’s row predicts today’s, and two rows from the same user are not independent. Every variance estimate in this chapter, including the free validation trick in Bagging a variance fix and why it needs unstable base learners, becomes optimistic when they do.

The chapter as a picture

The diagram below is the chapter’s table of contents: it splits test error into the three terms above and hangs each family of methods off the term it attacks.

flowchart TD
    E["Test error<br/>Bias^2 + Variance + sigma^2"] --> B["Bias term<br/>model too rigid<br/>to represent f"]
    E --> V["Variance term<br/>model too sensitive<br/>to which rows it saw"]
    E --> N["Irreducible sigma^2<br/>nothing helps"]
    B --> BO["Boosting<br/>sequential, each learner<br/>fits what is left over"]
    V --> BA["Bagging<br/>average B noisy models"]
    V --> RF["Random forest<br/>average B DEcorrelated models"]
    BO --> GB["AdaBoost -> gradient boosting -><br/>XGBoost -> LightGBM -> CatBoost"]

    style B fill:#bc6c25,color:#fff
    style V fill:#1d3557,color:#fff
    style N fill:#9d0208,color:#fff

Walking it top to bottom: test error splits into a bias term (model too rigid to represent f no matter how much data it sees), a variance term (model too sensitive to which rows it saw), and the irreducible sigma^2 (nothing helps).

Bagging hangs off the variance term: it averages B noisy models. A random forest hangs off the same term but attacks it harder, by averaging B decorrelated models — models deliberately built to make different mistakes.

Boosting hangs off the bias term instead. It is sequential, because each learner fits what is left over after the ones before it. The chain from AdaBoost through gradient boosting to XGBoost, LightGBM and CatBoost is that one idea plus twenty-five years of engineering.

Numbers to anchor the rest of the chapter

The table below puts a number on each of those terms for six models on the same problem, so that “bagging fixes variance” stops being a slogan.

These figures are illustrative rather than reproducible. The table shows the shape of the effect, not the output of a run you could re-execute, because it names no data-generating function, no feature count and no seed. Treat every entry as a round number chosen to make the ordering legible.

The setting is a synthetic regression problem with n = 200 training rows and label noise sigma^2 = 0.10. The bias and variance columns are what you get by refitting each model on many redraws of the training set and applying the decomposition above pointwise. B counts the models in an average and M counts the stages in a boosted sum. MSE is mean squared error, the average of (y - prediction)^2 over the test rows.

Every row obeys Bias^2 + Variance + 0.10 = Total, so you can check the arithmetic as you read: the first row is 0.38 + 0.04 + 0.10 = 0.52.

What is real and worth carrying forward is the pattern: which column is large for which model, and which intervention moves which column.

Read the third row against the first. Both have bias^2 0.38 — the high-bias, low-variance shallow model. Bagging took that model’s variance from 0.04 down to 0.01 and left the bias exactly where it was, so the total moved 0.52 to 0.49.

Bagging 100 stumps bought almost nothing, because stumps fail from bias and bagging does not touch bias.

That single row is the reason the next three sections are ordered the way they are. Bagging comes first as a variance fix. Random forests come second, because bagging’s variance fix runs into a wall. Boosting comes third, because neither of the first two touches the bias that the stump row exposes.

What interviewers probe: “Is a random forest high bias or high variance?” The answer they want is the mechanism, not the label: a single unpruned tree is low bias and high variance; averaging leaves the bias where it was and shrinks the variance, so the forest inherits the tree’s bias and loses most of its variance.

2. Bagging — a variance fix, and why it needs unstable base learners

Bagging is the variance attack in its simplest form. Two things about it are exact rather than folklore: the point at which adding more models stops helping, and the one property your base model must have for bagging to be worth running at all.

The procedure

Bagging is short for bootstrap aggregating, and it is two steps.

Step one: build a bootstrap sample. That is a new dataset of the same size n, built by drawing rows from the original table at random with replacement. Drawing with replacement means a row can be picked again, so some rows appear two or three times in the sample and roughly a third do not appear at all.

Step two: draw B such samples, fit one model per sample, and average the B predictions into one.

That average is the ensemble’s output. Averaging is the entire mechanism — nothing about the base model changes.

The diagram below contrasts bagging’s shape with boosting’s, which is the comparison this chapter keeps returning to. Look at the arrows: on the left they fan out from one source, on the right they form a chain.

flowchart LR
    subgraph BAG["Bagging - parallel, independent fits"]
        D1[(Training set)] --> S1["bootstrap 1"] --> T1["Tree 1"]
        D1 --> S2["bootstrap 2"] --> T2["Tree 2"]
        D1 --> S3["bootstrap B"] --> T3["Tree B"]
        T1 & T2 & T3 --> AV["average<br/>cuts variance only"]
    end
    subgraph BOOST["Boosting - sequential, dependent fits"]
        D2[(Training set)] --> H1["Tree 1"] --> R1["what is left over"] --> H2["Tree 2"] --> R2["what is left over"] --> H3["Tree M"]
        H3 --> AD["weighted sum<br/>cuts bias"]
    end

    style AV fill:#1d3557,color:#fff
    style AD fill:#bc6c25,color:#fff

On the left, bagging is a fan of parallel, independent fits. Every tree sees its own bootstrap of the same training set, no tree knows the others exist, and the average at the end cuts variance only.

On the right, boosting is a chain of sequential, dependent fits. Tree 1 is fit, then tree 2 is fit to what is left over, then tree 3 to what is left over after that, and the weighted sum at the end cuts bias.

That difference decides what you can parallelize. The left-hand fits do not depend on each other, so bagging parallelizes across all B trees. The right-hand fits do, so boosting cannot.

Why it works, and where it stops

If the B models were independent, each with variance sigma_t^2 (the variance of one tree’s prediction), the average would have variance sigma_t^2/B, and you could drive it to zero by raising B.

They are not independent. Every bootstrap sample is drawn from the same n rows, so the trees see mostly the same data and make mostly the same mistakes. That similarity has a name: rho (the Greek letter rho), the ordinary pairwise correlation between the predictions two different trees make at the same input. At rho = 1 the trees are effectively the same model; at rho = 0 they are unrelated.

For identically distributed variables with pairwise correlation rho, the variance of the average is:

Var( (1/B) * sum_b T_b )  =  rho·sigma_t^2  +  (1 - rho)/B · sigma_t^2
                             ^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^
                             floor, does NOT    vanishes as B grows
                             depend on B

That first term is the whole story of the next section. It has no B in it, so no amount of averaging touches it.

Substitute sigma_t^2 = 0.45 and rho = 0.35 and watch the second term collapse while the first sits still:

B = 1      0.1575 + 0.65·0.45/1     = 0.1575 + 0.2925  = 0.450
B = 10     0.1575 + 0.65·0.45/10    = 0.1575 + 0.0293  = 0.187
B = 100    0.1575 + 0.65·0.45/100   = 0.1575 + 0.0029  = 0.160
B = 1000   0.1575 + 0.65·0.45/1000  = 0.1575 + 0.0003  = 0.158
B = inf    0.1575 + 0                                  = 0.1575   <- the floor

Going from 100 trees to 1000 trees bought (0.1604 - 0.1578)/0.1604 = 1.6%. Ten times the compute for one and a half percent.

The practical consequence: B is not something to tune. It is something to set past the point where the second term is negligible, and then forget.

Why the base learner must be high variance

Bagging’s entire effect is on the variance term, which means the base model must have variance worth removing.

Take the shallow, high-bias model from the table in The decomposition everything follows from: variance 0.04, bias^2 0.38. Bagging cuts that variance by 75%, from 0.04 to 0.01. Total moves 0.52 to 0.49.

Now the deep unpruned tree: variance 0.45, bias^2 0.01. Bagging cuts that variance by 64%, from 0.45 to 0.16. Total moves 0.56 to 0.27.

That 64% is not a second arbitrary figure — it is the floor from two lines above, read as a percentage. With rho = 0.35 and sigma_t^2 = 0.45, the floor is 0.35 x 0.45 = 0.1575, which the table rounds to 0.16. Bagging cannot take the deep tree’s variance below that, so (0.45 - 0.16)/0.45 = 64% is the largest cut available.

The 75% quoted for the shallow model looks better and is worth less. It is a larger fraction of a variance that was 0.04 to begin with, and 75% of almost nothing is almost nothing.

Comparing the percentages is the mistake. Compare what they subtract — 0.03 against 0.29.

This is where the rule do not prune trees inside a bagged ensemble comes from, and it is not folklore. Pruning trades variance for bias. Bagging is about to remove that variance for free. Pruning inside a bag trades away something free for something permanent.

Out-of-bag evaluation, for free

Recall that a bootstrap sample leaves roughly a third of the rows out. That third is worth something.

The probability a given row is missing from one bootstrap sample is (1 - 1/n)^n, which converges to e^-1 = 0.368 as n grows. So about 36.8% of the trees never saw row i during training.

You can score row i with exactly those trees. They are the out-of-bag (OOB) trees for that row, and averaging their predictions gives you a validation estimate without holding anything out. That is why a random forest is the fastest model in this chapter to get an honest number from.

What bagging assumes, and what breaks it

Bagging rests on three assumptions, and each has a visible failure mode.

1. The base learner is unstable. Small changes to the training rows must produce visibly different models, or there is no variance to average away.

Deep trees qualify. So do nearest-neighbour models with small neighbourhoods. Stumps do not, nor does linear regression on few features, nor a heavily pruned tree — bagging any of those is close to a no-op. The third row of the table in The decomposition everything follows from is exactly that failure, measured.

2. The rows are i.i.d., so that a bootstrap resample is a believable stand-in for a fresh sample from the population.

With time-ordered rows, or many rows per user, the bootstrap reuses information across the split. Both the OOB estimate and the variance reduction come out optimistic. The fix is to bootstrap whole groups or whole time blocks rather than individual rows.

3. Averaging is a meaningful operation on the output. True for regression values and for class probabilities. False for predicted categories — you cannot average “France” and “Germany”, so there you vote instead.

3. Random forests — decorrelation, which matters more than the bagging

Bagging left a floor it cannot get under. Attacking that floor is the entire content of the random forest idea — and the knob it introduces turns out to have a best value in the middle rather than at either end.

The one idea

Bagging’s floor is rho·sigma_t^2. The base learner fixes sigma_t^2, so the only remaining lever is rho.

Random forests pull that lever directly: at each split, consider only a random subset of m out of the p features.

Here m is a feature count, not the boosting stage index it becomes in §4 onward. Same letter, unrelated meaning.

Why this lowers rho: if one feature is strongly predictive, every bagged tree splits on it at the root, and the trees end up structurally near-identical no matter which rows they saw. Restricting the candidate set forces different trees down different feature paths, so their errors stop coinciding.

That is what decorrelation means here. Not making the trees better individually — making their mistakes less alike, so that averaging cancels more of them.

The tradeoff, in numbers

The table below runs the variance formula from Bagging a variance fix and why it needs unstable base learners at three settings of m, with B = 200 trees, sigma_t^2 = 0.45, and p = 100 features. The middle column shows the two halves of that formula separately, so you can see the floor term shrink while the 1/B term stays tiny.

Check the middle row: 0.12 x 0.45 = 0.0540, and 0.88 x 0.45 / 200 = 0.0020. Add them for 0.056, add bias^2 0.02 and noise 0.10, and you get 0.176.

Why the best m is in the middle

Read the last column top to bottom: 0.269, then 0.176, then back up to 0.266. That is a U-shape, and one formula explains both arms.

Going down from m = p: lowering m cuts rho, which cuts the floor. Variance falls from 0.159 to 0.056.

Going too far, to m = 1: each tree now picks its splits from a candidate set that usually excludes the good feature. Individual trees get worse, and bias^2 jumps from 0.02 to 0.15 — more than wiping out the extra 0.04 of variance it saved.

The library defaults are sqrt(p) for classification and p/3 for regression, and both sit near the bottom of that curve for typical p.

One inconsistency in the table is deliberate and worth naming. Bias, variance and MSE are the squared-error decomposition of The decomposition everything follows from, so this is a regression table — yet the middle row uses sqrt(p) = 10 rather than the regression default p/3 = 33. That row exists to show how far rho can be driven down, not to reproduce a default. At p = 100, the regression default would sit between the first and second rows, with a rho and a bias^2 to match.

Now note what does not move the needle. Doubling B from 200 to 400 takes the middle row’s variance from 0.0560 to 0.0550 — one thousandth, for twice the trees.

n_estimators is a convergence parameter, not a tuning parameter. Set it high enough that the curve is flat and never touch it again. max_features is the actual knob.

What a random forest assumes, and what breaks it

It inherits both of bagging’s assumptions — unstable base learners and i.i.d. rows — and adds one of its own.

The predictive signal is spread across several features, so that a tree denied the single best feature can still find something useful among the m it was offered.

When that is false — two features out of two hundred carry all the signal and the rest are noise — a small m means most nodes are choosing between noise columns. Per-tree bias rises fast, and the m = 1 row above is what you get.

The symptom is a forest that loses to a single tuned tree. The fix is to raise max_features back toward p, or to cut the noise columns.

Extra Trees: one more notch of randomness

The table below places three variants on one axis of increasing randomness. Read the last two columns together — every drop in rho is paid for with a rise in per-tree bias.

Extra Trees is short for extremely randomized trees. Rather than searching for the best threshold within the chosen features, it picks thresholds at random.

That is faster, because no sorting is required, and it lowers rho further. The cost is needing more trees and accepting more bias per tree.

Feature importance, and the trap

A forest will hand you a ranking of features for free, and the free one is misleading.

Mean decrease in impurity — the feature_importances_ attribute in scikit-learn — adds up how much each feature reduced impurity across all splits. It is biased toward high-cardinality and continuous features.

Cardinality means the number of distinct values a column takes. A column of unique customer identifiers has the highest cardinality possible: n distinct values in n rows.

That is the trap. A feature with many candidate split points gets many chances to reduce impurity by luck, so a random unique ID column will show up as important even though it carries nothing.

Permutation importance avoids this by measuring what the feature is actually worth. Shuffle one column on held-out data, re-score the model, and record how much the metric dropped. Shuffling destroys the column’s relationship with the label while leaving everything else intact, so the drop is that column’s real contribution.

It costs p extra scoring passes, has no cardinality bias, and is what you should quote in an interview.

What interviewers probe: “You have 500 trees and accuracy stopped improving. What now?” Say the formula: the remaining variance is rho·sigma_t^2 and B cannot touch it, so lower max_features to cut rho, or accept that the remaining error is bias and switch to boosting.

4. Boosting — the bias fix

No amount of averaging touches the bias term, so cutting it takes a structural change: an ensemble that is more expressive than the models inside it.

The shape of the model

Bagging averages models fit to the same target. Boosting fits each model to what the ensemble so far still gets wrong, and adds it in.

The ensemble is built as a forward stagewise additive model: grown one stage at a time, with earlier stages never revisited.

F_0(x) = a constant
F_m(x) = F_{m-1}(x) + eta · h_m(x)         for m = 1..M,  F_{m-1} frozen

Reading the symbols: F_m is the ensemble after m stages. h_m is the small model added at stage m. M is the total number of stages. And eta (the Greek letter eta) is a number between 0 and 1 that scales down each addition.

That scaling has two names, learning rate and shrinkage, and they mean the same thing. Instead of adding the full correction that stage m proposes, you add a fraction of it and let later stages re-measure.

The greedy, never-revise structure is what makes boosting cheap. It is also what makes it sequential and un-parallelizable across m: stage m cannot start until stage m-1 has produced its predictions.

Why this attacks bias and bagging cannot

A bagged ensemble of stumps is still a collection of functions each fit to the full target, so the average is an average of equally rigid approximations. Its expressive power is that of one stump.

A boosted ensemble of stumps is a sum of stumps, each fit to a different residual signal. A residual is the part of the label the current ensemble has not explained yet — y minus the current prediction.

Sums of stumps can represent any additive function. Sums of depth-3 trees can represent three-way interactions between features.

The ensemble is more expressive than its members, which is exactly what “reduces bias” means.

The flip side

Because each stage chases what is left over, boosting will happily chase noise once the real signal is gone. Boosting overfits as M grows. Bagging does not.

That asymmetry is why early stopping is mandatory here and irrelevant for forests. Early stopping means watching the error on a held-out validation set after every stage and halting when it stops improving, so M is chosen by measurement rather than guessed in advance. Early stopping works through the mechanics.

What boosting assumes, and what breaks it

1. The base learner is weak but better than chance. Weak means deliberately low-capacity — a stump, or a depth-4 tree, not a fully grown one.

Boost fully grown trees and stage 1 removes the entire residual signal at once. Later stages have nothing left to fit but noise, and the ensemble memorizes.

2. The labels are mostly correct. A stage that chases what is left over will chase a mislabeled row forever. Adaboost reweighting and the number that falls out shows exactly how badly this goes for AdaBoost.

3. You have an honest validation signal to stop on, which means a split that respects time and grouping. Otherwise early stopping halts at the wrong M and reports a number that will not survive deployment.

09 — Model Debugging Playbook, Step 2 is the diagnostic procedure for deciding whether bias or variance is your problem in the first place.

5. AdaBoost — reweighting, and the number that falls out

AdaBoost was the first boosting algorithm that succeeded, and its update rule has a surprising exact property — one that explains what “weak learners compose into a strong one” actually means mechanically.

The algorithm

AdaBoost is short for adaptive boosting. The 1995 version handles binary classification, with labels written as -1 and +1 rather than 0 and 1 — a convention that matters later, so note it now.

It keeps a weight w_i on every training row and starts them uniform at 1/n. A weighted fit means rows with larger w_i count more when the base learner scores its candidate splits.

Each round runs these five lines.

1. fit h_m on the weighted data
2. err_m = sum_i w_i · 1[h_m(x_i) != y_i]            (weights sum to 1)
3. alpha_m = 0.5 · ln((1 - err_m) / err_m)
4. w_i <- w_i · exp(-alpha_m · y_i · h_m(x_i))       then renormalize
5. F(x) = sign( sum_m alpha_m · h_m(x) )

Line 2 uses 1[...], an indicator: 1 when the condition inside holds, 0 otherwise. So err_m is the weighted fraction of rows the new learner got wrong.

Line 3 sets alpha_m, the vote that learner gets in the final sum. It is not arbitrary — it is the exact minimizer of exponential loss sum_i exp(-y_i F(x_i)) along the direction h_m. Note that this alpha is a vote weight; the alpha in §7 and §12 is an unrelated L1 penalty.

Line 4 raises the weight of every row the learner missed and lowers the weight of every row it got right. The mechanism is the product y_i · h_m(x_i), which is +1 on a correct row and -1 on a wrong one, so the exponent flips sign accordingly.

That line has a property worth deriving, because it makes the algorithm memorable.

Worked example

Take 10 training rows, all starting at the uniform weight w_i = 0.1. The weak learner misclassifies 3 of them, so the weighted error is err = 3 x 0.1 = 0.3.

Here is the full update, with Z the normalizing constant that puts the weights back on a total of 1.

alpha = 0.5 · ln(0.7 / 0.3) = 0.5 · 0.8473 = 0.4236

misclassified: w *= exp(+0.4236) = 1.5275  ->  0.15275  (x3)
correct:       w *= exp(-0.4236) = 0.6547  ->  0.06547  (x7)
Z = 3(0.15275) + 7(0.06547) = 0.45826 + 0.45826 = 0.91652

normalized:  misclassified 0.16667 each, correct 0.07143 each
check:       3(0.16667) + 7(0.07143) = 0.5000 + 0.5000 = 1.0

The 0.5 is not a coincidence

Look at the check line: the 3 misclassified rows now hold exactly half the total weight, and the 7 correct rows hold the other half. That happens for any error rate, not just 0.3.

The algebra is two lines. Substituting exp(alpha) = sqrt((1-err)/err):

misclassified mass = err · sqrt((1-err)/err)  = sqrt(err(1-err))
correct mass       = (1-err) · sqrt(err/(1-err)) = sqrt(err(1-err))

Identical expressions, so identical halves, for every err. At err = 0.3 that is sqrt(0.3 x 0.7) = sqrt(0.21) = 0.4583 on each side — the two 0.45826 terms in the Z line above — and dividing each by their sum gives 0.5.

So AdaBoost reweights until the learner it just added is exactly a coin flip on the new distribution.

Round m+1 is therefore forced to find structure that round m provably could not use. That is the mechanism by which weak learners compose into a strong one, and it is a much better interview answer than “it focuses on hard examples.”

What AdaBoost assumes, and what breaks it

Every base learner reaches err_m < 0.5 on the current weighting. That is what keeps alpha_m positive. A learner at exactly 0.5 gets alpha_m = 0.5·ln(1) = 0, no vote at all, and the algorithm stalls. One above 0.5 gets a negative vote, which is legal but a sign the base learner is too weak for the problem.

The labels are clean. This is the serious one.

Exponential loss grows like exp(-margin), where the margin of a row is y_i · F(x_i). Margin is positive when the ensemble has the sign right, and larger the more confident it is; a badly wrong row has a large negative margin.

So a single mislabeled row sits at a large negative margin, its weight rises without bound each round, and eventually it dominates the reweighted dataset. Every later learner is fitting one bad row.

AdaBoost is famously brittle to label noise, and that is the specific reason gradient boosting with a log-loss or Huber objective replaced it. Huber loss is squared error near zero and absolute error far from it, so like log loss it grows linearly rather than exponentially in the wrong direction. One bad row stays one bad row.

6. Gradient boosting — gradient descent in function space

Now the centerpiece. Boosting is not a special-purpose trick; it is ordinary gradient descent performed on the space of predictions, which is what lets a single algorithm serve any differentiable loss. AdaBoost is one loss function with one hand-derived weight rule; gradient boosting is the general recipe, and the derivation is short.

Step 1 — treat the model as a vector

You want to minimize L(F) = sum_{i=1..n} l(y_i, F(x_i)), where l is the per-row loss and L is the total over the training set.

Forget that F is a function. On the training set, F is fully described by the n numbers it outputs: F = [F(x_1), ..., F(x_n)], a point in R^n (the space of vectors of n real numbers).

Now L is an ordinary function from R^n to a single number, and you already know how to minimize one of those: pick the direction in which it falls fastest and take a step. That is ordinary gradient descent (Gradient descent and why the surface shape decides everything).

Step 2 — take the gradient

The gradient is the vector of partial derivatives of the loss with respect to each of those n numbers. It points uphill, so descending means stepping along -g.

Because the loss is a plain sum over rows, the gradient decomposes per row — entry i depends only on row i:

g_i = dL/dF(x_i) = d l(y_i, z)/dz   evaluated at z = F_{m-1}(x_i)
F_m = F_{m-1} - eta · g

Step 3 — notice the problem

That vector -g has one entry per training row. It says nothing about a point you have not seen.

Apply it literally and you get a lookup table: perfect on the rows you have, useless on every row you do not.

Step 4 — the fix, which is the entire idea

Find a function that best approximates the gradient vector, and step with that function instead of with the raw vector.

The function has to come from your hypothesis class H: the set of models you are willing to consider, here “all trees of depth at most d”.

h_m = argmin_{h in H}  sum_i ( -g_i - h(x_i) )^2        a tree fit to -g by least squares
F_m = F_{m-1} + eta · h_m                               the step, in function space

argmin reads “the argument that minimizes”: among all trees in H, pick the one whose predictions come closest to -g in squared error.

Fitting by least squares against -g means the tree is trained exactly like an ordinary regression tree, except the values -g_i are used in place of the labels.

That is gradient boosting. The base learner is not modelling the target. It is modelling the gradient — and the “residuals” everyone talks about are just what the gradient happens to equal for squared loss.

That last clause is the part to check rather than believe, so here are three losses and their gradients.

squared loss   l = 0.5(y - F)^2                    ->  -g_i = y_i - F(x_i)          the residual
absolute loss  l = |y - F|                         ->  -g_i = sign(y_i - F(x_i))    direction only
log loss       l = -[y·ln p + (1-y)·ln(1-p)]       ->  -g_i = y_i - p_i             prob. residual
               with y in {0,1} and p = 1/(1+e^-F)

Those three lines are three different definitions of “what is left over”.

Under squared loss, it is the plain residual y - F. This is the case everyone pictures when they hear “boosting fits the residuals” — and it is the only case where that phrase is literally true.

Under absolute loss, it is only the sign of the residual: +1 or -1, never a magnitude. The loss therefore ignores how far off you were, which is what makes it robust to outliers — a row that is off by 100 pushes exactly as hard as one off by 1.

Under log loss, the standard classification loss (Proper scoring rules log loss and brier), it is the label minus the predicted probability.

Swapping the loss changes exactly one line of code — the gradient. That is why gradient boosting supports ranking objectives, Poisson counts, quantile targets and survival times, while AdaBoost supports one. A quantile objective predicts, say, the 90th percentile of the outcome rather than its mean. A Poisson objective is the right one for counts like “number of claims this year”. A survival objective handles rows where you only know the outcome had not happened yet when you stopped looking.

The label convention just changed, and it will corrupt your arithmetic silently

Adaboost reweighting and the number that falls out wrote AdaBoost with labels in {-1, +1}, where the logistic loss is log(1 + e^-yF).

The log-loss row above uses {0, 1} cross-entropy instead. Every remaining gradient in this chapter is {0, 1} too: Xgboost second order and a regularizer inside the split criterion writes g_i = p_i - y_i, and the code block below swaps in y - 1/(1 + np.exp(-F)).

The two conventions agree on every positive row and differ by exactly 1 on every negative one, because the label itself differs by 1.

Work it through at F = 0.7, where p = 1/(1 + e^-0.7) = 0.6682:

{0,1} convention, negative row:   y = 0    ->  -g = 0 - 0.6682 = -0.6682   correct
{-1,+1} label read into y - p:    y = -1   ->  -g = -1 - 0.6682 = -1.6682  wrong by 1.0

Carry the wrong convention and every negative row in the ensemble is pushed with a gradient a full 1.0 too large. There is no error message. You just get a model that will not fit.

The whole loop, as a diagram

Everything above assembles into one loop. Follow it from F_0 at the top around to the exit test at the bottom. The two green boxes are the heart of it: the gradient vector, and the tree that stands in for it.

flowchart TD
    F0["F_0 = argmin_c sum l(y_i, c)<br/>the best constant"] --> G["g_i = dl/dz at z = F_m-1(x_i)<br/>one number per training row"]
    G --> NEG["target = -g_i<br/>the negative gradient<br/>direction in R^n"]
    NEG --> H["fit tree h_m by least squares<br/>to the vector -g<br/>-- this is the projection<br/>onto the hypothesis class"]
    H --> W["re-solve each leaf value<br/>line search on the true loss"]
    W --> UP["F_m = F_m-1 + eta * h_m<br/>eta = learning rate = step size"]
    UP --> C{"m = M, or<br/>validation stopped<br/>improving?"}
    C -->|no| G
    C -->|yes| OUT(["F_M"])

    style NEG fill:#2d6a4f,color:#fff
    style H fill:#40916c,color:#fff
    style OUT fill:#1d3557,color:#fff

The starting point is F_0 = argmin_c sum l(y_i, c): the single constant that minimizes the loss over the whole training set. Which constant that is depends on the loss — the mean for squared loss, the median for absolute loss, and for log loss the log-odds of the base rate, meaning ln(p / (1 - p)) where p is the overall positive rate.

Then each round does five things: compute one gradient number per training row, form the target from the negative gradient, fit a tree to that target by least squares, re-solve each leaf value by a line search on the true loss, and take the step scaled by eta.

The loop exits when m reaches M or validation stops improving, whichever comes first, and returns the accumulated F_M.

Step 5 — the leaf-value correction

One box in that diagram has not been explained yet: “re-solve each leaf value”.

The tree was fit by least squares to -g, but your actual loss may not be squared error. So once the tree’s structure is fixed, discard the fitted leaf means and re-solve each leaf against the true loss:

w_j = argmin_w  sum_{i in leaf j} l( y_i, F_{m-1}(x_i) + w )

That is a one-dimensional minimization — the line search in the diagram. Hold the tree’s shape fixed and ask: what single value, added to every row in this leaf, lowers the real loss most?

For squared loss it returns the mean residual and changes nothing. For absolute loss it returns the median residual, which is a different number entirely.

The tree structure comes from the gradient. The leaf values come from the loss.

XGBoost folds this two-step into one, which is the next section.

What gradient boosting assumes, and what breaks it

The loss is differentiable in F. That rules out anything you can only evaluate, like exact top-k accuracy. The usual workaround is a surrogate: a differentiable loss that stands in for the one you actually care about.

The gradient step’s linear approximation is good near F_{m-1}. A gradient is only accurate very close to the point where you took it. Keeping eta small is exactly what buys you that, and it is why large learning rates diverge or oscillate.

The hypothesis class can approximate the gradient vector. The tree is a projection of -g onto that class — the closest thing to -g that a depth-d tree can express. If depth-2 trees cannot express the shape of -g, every step lands in the wrong direction and the ensemble stalls at a bias floor that more rounds will not clear.

Worked run, by hand

The following run is small enough to check with a calculator, and it shows the property that separates boosting from averaging.

The setup: four points, x = [1, 2, 3, 4] with labels y = [2, 4, 6, 10]. The loss is squared error. Each base learner is a depth-1 stump, so it can ask exactly one question. The learning rate is eta = 0.5.

SSE below is the sum of squared errors over the four rows. A stump has only three possible questions here — x<=1, x<=2, x<=3 — so each round can list all of them and pick the winner.

F_0 = mean(y) = 5.5                      SSE = 12.25+2.25+0.25+20.25 = 35.00

round 1:  -g = y - F_0 = [-3.5, -1.5, 0.5, 4.5]
          stump SSE by split:   x<=1: 18.67   x<=2: 10.00   x<=3: 8.00  <- best
          h_1 = -1.5 for x<=3, +4.5 for x=4
          F_1 = 5.5 + 0.5·h_1 = [4.75, 4.75, 4.75, 7.75]      SSE = 14.75

round 2:  -g = y - F_1 = [-2.75, -0.75, 1.25, 2.25]
          stump SSE by split:   x<=1:  4.67   x<=2:  2.50  <- best   x<=3: 8.00
          h_2 = -1.75 for x<=2, +1.75 for x>2
          F_2 = [3.875, 3.875, 5.625, 8.625]                  SSE =  5.5625

Each round does the same three things. Subtract the current prediction from the labels to get the negative gradient. Try every possible split point and keep the one whose two-sided means leave the smallest SSE on those residuals. Then add half of that stump — eta = 0.5 — to the running prediction.

Two numbers to verify by hand. In round 1, the best split x<=3 puts rows 1-3 in the left leaf with mean residual (-3.5 - 1.5 + 0.5)/3 = -1.5 and row 4 alone on the right at +4.5. Then F_1(x=1) = 5.5 + 0.5 x (-1.5) = 4.75, and F_1(x=4) = 5.5 + 0.5 x 4.5 = 7.75.

The loss falls 35.00 -> 14.75 -> 5.56.

Now the detail that matters. The split point moved between rounds, from x<=3 in round 1 to x<=2 in round 2. Nothing instructed it to. The residual landscape changed after round 1, so the greedy split changed with it.

That is what “each learner fixes the previous one’s specific mistake” looks like numerically. It is also why boosted stumps can represent a staircase that no single stump, and no average of stumps, can.

The same algorithm in code. neg_grad is the only line that knows what loss you are minimizing — everything else is bookkeeping.

import numpy as np
from sklearn.tree import DecisionTreeRegressor

def fit_gbm(X, y, M=200, eta=0.05, max_depth=3):
    """Gradient descent in function space, squared loss."""
    F0 = y.mean()
    F, trees = np.full(len(y), F0), []
    for _ in range(M):
        neg_grad = y - F                      # -dL/dF for l = 0.5(y-F)^2
        t = DecisionTreeRegressor(max_depth=max_depth).fit(X, neg_grad)
        F = F + eta * t.predict(X)            # the step in function space
        trees.append(t)
    return F0, trees, eta

def predict_gbm(model, X):
    F0, trees, eta = model
    return F0 + eta * sum(t.predict(X) for t in trees)

Swap neg_grad = y - F for y - 1 / (1 + np.exp(-F)) and the same twelve lines are a classifier, because that expression is the log-loss gradient from the table above. That is the payoff of deriving boosting as descent rather than memorizing “fit the residuals.”

7. XGBoost — second order, and a regularizer inside the split criterion

Keep the second derivative of the loss as well as the first and something tidy happens: the leaf values, the split criterion and the regularization all fall out of one objective instead of being three separate settings.

Plain gradient boosting uses first-order information — the slope — and bolts regularization on from outside, through shrinkage and a depth limit.

Regularization means any deliberate restriction that trades a little training accuracy for stability on new data (Regularization why l1 zeroes and l2 does not covers the linear-model version).

XGBoost puts both the second-order information and the regularization inside the objective it optimizes.

The derivation

At round m you choose the new tree f to minimize

Obj = sum_i l( y_i, F_{m-1}(x_i) + f(x_i) ) + Omega(f)

where Omega(f) is a penalty on how complicated f is.

Now Taylor-expand that loss to second order around the current prediction F_{m-1}(x_i). A Taylor expansion approximates a function near a point using its value, its slope and its curvature — the more terms you keep, the better the approximation close to the point.

Two symbols carry that expansion: g_i is the first derivative of the loss at row i, and h_i is the second. h_i with a row subscript is a curvature number; h_m with a stage subscript, back in §6, was a whole tree. Different objects, same letter.

The regularizer is defined over a tree with T leaves and leaf values w_j.

Obj ≈ sum_i [ const + g_i·f(x_i) + 0.5·h_i·f(x_i)^2 ]  +  gamma·T + 0.5·lambda·sum_j w_j^2

a tree is constant within a leaf, so group by leaf, with
G_j = sum_{i in leaf j} g_i        H_j = sum_{i in leaf j} h_i

Obj = sum_j [ G_j·w_j + 0.5·(H_j + lambda)·w_j^2 ] + gamma·T

one 1-D quadratic per leaf, so solve exactly:

w_j* = -G_j / (H_j + lambda)
Obj* = -0.5 · sum_j G_j^2 / (H_j + lambda)  +  gamma·T

The grouping step is the one to hold on to. A tree gives every row in a leaf the same output, so the sum over rows collapses into a sum over leaves. G_j and H_j are just the gradients and curvatures of that leaf’s rows, added up.

Each leaf then becomes an independent one-variable quadratic, and a quadratic has a closed-form minimum — no search needed. That gives w_j*, the best value for leaf j.

Substitute those optimal values back and you get Obj*, which scores a tree structure: the loss it would achieve if every leaf were set optimally.

That is what makes split scoring possible. Split a leaf into a left child L and a right child R, and the split gain is the drop in Obj* — the parent’s score minus the two children’s:

Gain = 0.5 · [ G_L^2/(H_L+lambda) + G_R^2/(H_R+lambda) - (G_L+G_R)^2/(H_L+H_R+lambda) ] - gamma

Three things that were not true of plain gradient boosting

The leaf value is a Newton step. w_j* = -G_j/(H_j + lambda) divides the gradient by the curvature rather than using the gradient alone. It is automatically scaled by how sharply the loss bends there, so no separate line search is needed — step 5 of §6 disappears into the formula.

lambda regularizes from inside. The L2 penalty sits in the denominator of the leaf value, so raising it shrinks every leaf toward zero.

gamma is a literal admission fee per split, in units of loss. A split whose gain does not clear gamma is rejected. That is pre-pruning derived from the objective, rather than a separate pruning pass run afterwards.

Worked split gain

Take the logistic loss, whose derivatives are g_i = p_i - y_i and h_i = p_i(1-p_i), where p_i is the currently predicted probability for row i.

Consider a node holding 10 rows, 4 positive and 6 negative, that the model currently predicts at p = 0.5 each. So g_i = -0.5 on each positive row, g_i = +0.5 on each negative row, and h_i = 0.5 x 0.5 = 0.25 on all ten.

G = 6(0.5) + 4(-0.5) = 1.00        H = 10(0.25) = 2.50        lambda = 1, gamma = 0

candidate split:  left  = 4 pos, 1 neg  ->  G_L = 1(0.5) + 4(-0.5) = -1.50,  H_L = 1.25
                  right = 0 pos, 5 neg  ->  G_R = 5(0.5)           =  2.50,  H_R = 1.25

Gain = 0.5·[ (-1.5)^2/2.25 + (2.5)^2/2.25 - (1.0)^2/3.50 ]
     = 0.5·[ 1.0000 + 2.7778 - 0.2857 ]
     = 1.746

leaf values:  w_L = 1.50/2.25 =  0.667      w_R = -2.50/2.25 = -1.111

The split is worth taking because separating the rows lets the two children push in opposite directions: the left child raises the score by 0.667, the right lowers it by 1.111. The undivided node could only move all ten rows together, and G = 1.00 says the best it could do is a small push downward.

Now set gamma = 2. The gain becomes 1.746 - 2 = -0.254, and the split is rejected.

gamma is directly comparable to loss reduction, which is why it is the one regularizer you can reason about without a search.

min_child_weight is H_j, not a row count

This one catches people out, because the name says “weight” and everyone reads “rows”.

min_child_weight is a floor on H_j, the sum of curvatures in a leaf. How many rows that corresponds to depends on how confident the model already is.

Early in training, p ≈ 0.5 gives h_i = 0.25, so min_child_weight = 1 needs 1/0.25 = 4 rows.

Deep in training, on rows the model has nailed, p ≈ 0.99 gives h_i = 0.99 x 0.01 = 0.0099. The same setting now demands 1/0.0099 = 101.01 rows — and you cannot have a fraction of a row, so round up: 102. (Why boosted trees are under confident at the extremes quotes the same 102.)

So it is a confidence-weighted sample count. Leaves full of rows the model is already sure about must be much larger to be allowed.

That is a feature, not a quirk. It stops the model from carving splits out of already-explained data.

Sparsity-aware split finding

Missing values are not imputed — XGBoost never invents a substitute value for a blank cell.

Each split instead learns a default direction. The gain is computed twice, once sending all missing rows left and once sending them right, and the better of the two is stored with the split.

The cost is 2x the scan rather than n imputations. The payoff is that the missingness pattern itself becomes usable signal, and “this field was blank” is often predictive in its own right.

The remaining knobs, off the same objective

subsample fits each tree on a random fraction of the rows. That decorrelates the trees exactly as bagging does.

colsample_bytree gives each tree a random fraction of the columns, which decorrelates them the way a random forest does.

alpha is an L1 penalty on leaf values. Unlike lambda, which only shrinks them, L1 drives leaf values to exactly zero.

That alpha has nothing to do with AdaBoost’s alpha_m from Adaboost reweighting and the number that falls out, which was a learner’s vote weight in the final sum. The letter is simply reused, here and in the hyperparameter table of Hyperparameters what each knob does mechanically, because both literatures reached for it first. Read alpha as “L1 penalty” everywhere from this section onward.

What XGBoost’s objective assumes, and what breaks it

The loss is well approximated by a quadratic near the current prediction. That needs the loss to be twice differentiable and, in practice, convex — bowl-shaped, curving upward everywhere — so that h_i >= 0.

A non-convex custom loss can produce negative h_i. Then H_j + lambda can approach or cross zero, and the leaf value -G_j/(H_j + lambda) explodes: divide by something near zero and you get an enormous leaf. Keeping lambda strictly positive is the guard, and it is why lambda = 1 rather than 0 is the default.

The step is small. The expansion is only accurate near F_{m-1}, which is what the learning rate enforces.

Missingness carries signal, or is at worst harmless. If values go missing for a reason that will change between training and serving — an upstream field that starts being populated next quarter — the learned default direction encodes a pattern that will not hold.

8. LightGBM — histograms and leaf-wise growth

LightGBM’s contribution is cost rather than accuracy: three engineering changes that make the same algorithm tractable when n reaches millions — one of which also changes the model’s overfitting behaviour.

XGBoost’s exact split finder sorts every feature at every node and scans it: O(n_node · p) comparisons per node, plus the sorting. That is the bottleneck once n reaches millions.

The three fixes below all attack that scan.

Fix 1 — bin once, then never look at raw values

Discretize each feature into k = 255 bins up front. Each stored value becomes a uint8 — an unsigned 8-bit integer, holding 0 through 255 in a single byte.

At each node, make one pass over the rows and accumulate (sum g, sum h, count) into those 255 buckets. That accumulation is a histogram.

Now evaluate splits by scanning 255 bucket boundaries instead of every distinct value in the column.

The arithmetic below is for one node — the root — on a million-row table. Compare the two “split evaluations” lines; the build cost is the same either way, and the search cost is what collapses.

n = 1,000,000 rows, p = 100 features, k = 255 bins

exact, at the root:  split evaluations = p · n     = 100,000,000
histogram, at root:  build             = p · n     = 100,000,000  (adds, no sort, cache-friendly)
                     split evaluations = p · k     =      25,500  <- 3,900x fewer

memory:  exact needs sorted float32 values + int32 indices  ≈ 800 MB
         histogram needs one uint8 per value                ≈ 100 MB

The build pass is still O(n·p), so 100,000,000 operations either way. But it is a sequential integer add rather than a sort, and sequential access is cache-friendly: the processor can fetch the next values it needs before they are asked for.

The split search is the part that collapses — 100,000,000 / 25,500 = 3,922, so roughly 3,900x fewer evaluations. And that search is repeated for every candidate at every node, not once.

The memory arithmetic tells the same story. Exact splitting stores a 4-byte float plus a 4-byte index per value, so 8 bytes against the histogram’s 1: 8 x 10^8 bytes = 800 MB against 1 x 10^8 = 100 MB.

Fix 2 — the subtraction trick

A parent’s histogram equals the sum of its two children’s histograms. Every row in the parent lands in exactly one child, so the counts add.

So build the histogram for the smaller child only, and get the sibling by subtracting it from the parent’s.

An even split halves the work. On a typical unbalanced split where one child holds 20% of the rows, you pay 0.2 of the cost instead of 1.0.

Fix 3 — leaf-wise growth

XGBoost grows level by level: every leaf at depth d splits before anything moves to depth d+1.

LightGBM keeps a global priority queue instead, and splits the single highest-gain leaf anywhere in the tree.

The two diagrams below are the same leaf budget spent two ways. The red node on the left is the cost of level-wise symmetry; the two green nodes on the right are where leaf-wise put the budget instead.

flowchart TD
    subgraph LW["Level-wise - every leaf splits, gain or not"]
        A1(("root")) --> B1(("."))
        A1 --> B2(("."))
        B1 --> C1(("leaf"))
        B1 --> C2(("leaf"))
        B2 --> C3(("leaf"))
        B2 --> C4(("low gain,<br/>split anyway"))
    end
    subgraph LF["Leaf-wise - budget spent where gain is highest"]
        A2(("root")) --> D1(("."))
        A2 --> D2(("leaf"))
        D1 --> E1(("."))
        D1 --> E2(("leaf"))
        E1 --> F1(("highest gain,<br/>split chosen"))
        E1 --> F2(("highest gain,<br/>split chosen"))
    end

    style C4 fill:#9d0208,color:#fff
    style F1 fill:#2d6a4f,color:#fff
    style F2 fill:#2d6a4f,color:#fff

The left tree is level-wise and symmetric. The node labelled “low gain, split anyway” is the cost of that symmetry: a node whose best split is worth almost nothing gets split regardless, because its siblings are being split and the level has to be completed.

The right tree is leaf-wise and lopsided. The two nodes labelled “highest gain, split chosen” are where its budget went — the deep path that keeps winning the priority queue — while shallow leaves are left alone.

For a fixed leaf budget, leaf-wise reaches a strictly lower training loss. It never spends a leaf on a split worth less than one it skipped.

That is also its failure mode. With 31 leaves it can build a depth-31 chain isolating a handful of rows, and on a small dataset that is memorization, not learning.

Three guards exist. num_leaves is the real capacity knob. min_data_in_leaf sets a row floor per leaf. max_depth is a hard cap on the chain length.

The rule that matters: num_leaves must sit well below 2^max_depth, not at it.

Here is why. max_depth = 7 allows 2^7 = 128 leaves. Set num_leaves = 128 and the only tree that fits the budget is the fully balanced one — which throws away the entire point of leaf-wise growth and is simultaneously the highest-capacity, most overfit configuration available. Pairing num_leaves = 31 with max_depth = 7 is the sane choice: deep paths allowed, but only 31 of them.

GOSS and EFB

GOSS is gradient-based one-side sampling. It keeps the a fraction of rows with the largest |gradient|, then draws a further b fraction at random from the rows it did not keep, and multiplies those sampled rows’ gradients by (1-a)/b so the total gradient stays unbiased.

a and b are fractions of 1 rather than percentages, and both are counted against the full row count. That is what makes the upweight come out exact.

LightGBM’s defaults are a = 0.2 (top_rate) and b = 0.1 (other_rate). So one pass touches 0.2 + 0.1 = 30% of the rows. The sampled 10% has to stand in for the 80% it was drawn from, and the scale factor (1 - 0.2)/0.1 = 8 does exactly that: 0.1 x 8 = 0.8.

It works because rows the model already fits contribute little gradient, so dropping most of them costs little.

EFB is exclusive feature bundling. It packs mutually exclusive sparse features — one-hot columns that are never nonzero at the same time — into a single feature by offsetting their value ranges, which cuts the effective p on wide sparse data.

What LightGBM assumes, and what breaks it

255 bins is enough resolution for every feature. It fails when the split you need sits inside a bin. On a heavily skewed feature where 99% of the mass falls into one bin, that split may be unrepresentable. The fix is a transform, or more bins.

There are enough rows that a deep, narrow path is still supported by real data. Below roughly a few tens of thousands of rows, leaf-wise growth is a memorization machine unless min_data_in_leaf is raised.

GOSS assumes small-gradient rows are genuinely well fit — rather than rows the model happens to be confidently wrong about. That is not true early in training, or under heavy label noise.

EFB assumes the bundled columns really are mutually exclusive. A nonzero conflict rate silently corrupts the bundled feature’s meaning, with no error to tell you.

9. CatBoost — the categorical leak, shown

CatBoost’s contribution is a bug fix rather than a speedup. The standard way of turning a categorical column into a number leaks the label — below is the leak itself, its signature in the training logs, and the two ordering tricks that remove it.

The encoding, and the leak inside it

Target encoding replaces a category with the mean label of its rows. So country = FR becomes “the average fraud rate among French rows”.

It is the strongest categorical representation for GBDTs, and done naively it is a data leak.

The smoothed target statistic for category k is:

enc(k) = ( sum over rows in category k of y_i  +  a·p ) / ( count(k) + a )

Two new symbols there. p is the prior — the overall positive rate across all rows — and a is the smoothing strength. (This p is not the feature count p from §1, and this a is not GOSS’s a from §8.)

The smoothing pulls rare categories toward the global rate p, so a category seen twice does not get a confident encoding. 01 — Feature Engineering derives the same mechanism from the feature side.

Now the problem: row i’s own label y_i is sitting inside row i’s own encoding.

Take a category that appears exactly once, with a = 1 and p = 0.5. Substitute:

y_i = 1  ->  enc = (1 + 1·0.5) / (1 + 1) = 1.5 / 2 = 0.75
y_i = 0  ->  enc = (0 + 1·0.5) / (1 + 1) = 0.5 / 2 = 0.25

Every singleton category has been handed its own label, scaled and shifted. A single split at enc <= 0.5 now separates positives from negatives perfectly, on the training set, forever.

What the leak looks like in the log

On a user-ID-like column the trace is unmistakable. AUC below is the area under the ROC (receiver operating characteristic) curve: 1.0 for a perfect ranking, 0.5 for a coin flip (Roc auc is a probability and here is the derivation).

The log is an illustrative sketch of that signature, not a captured run — no dataset or seed is named. Three shapes in it carry all the information: train AUC pinned, valid AUC at chance, one feature holding the importance.

iteration  train-auc  valid-auc          feature importance
       10     0.9998     0.5121          user_id_target_enc   0.94
       50     1.0000     0.5093          amount_bucket        0.03
      200     1.0000     0.5044          ...

Train AUC is pinned at 0.9998 by iteration 10 and hits 1.0000 by iteration 50. Validation never leaves 0.51, which is chance. And user_id_target_enc holds 0.94 of the importance, against 0.03 for the next feature down.

Any time a feature’s importance exceeds ~0.8 and train AUC saturates immediately, suspect that the feature contains the label.

Fix 1 — ordered target statistics

Fix a random permutation of the rows. Then compute row i’s encoding from only the rows that precede it in that permutation:

enc(x_i) = ( sum over j < i with cat_j = cat_i of y_j  +  a·p )
           / ( count of j < i with cat_j = cat_i  +  a )

Row i’s own label is now structurally excluded from row i’s encoding. There is nothing left to leak.

The cost: early rows in the permutation have almost no history, so their encodings are high-variance — the first row of a category gets nothing but the prior. CatBoost handles that by maintaining several independent permutations, four by default, and averaging across them.

The table below compares four ways of computing a target encoding. TS is short for target statistic; OOF is out-of-fold, meaning a value computed only from folds that excluded the row.

Fix 2 — ordered boosting, for the same bug one level up

The leak is not only in encodings. The same shape of mistake sits inside plain gradient boosting, with no categorical feature involved at all.

At round m you compute g_i from F_{m-1}. But F_{m-1} was trained on a dataset that contains row i.

So the model has already partly memorized row i, which makes g_i systematically too small on training rows. The tree at round m is fit to a biased gradient vector.

This is prediction shift, and it is why a GBDT’s training residuals understate its true error.

Ordered boosting computes row i’s gradient from a model trained only on rows preceding i in the permutation. The exact version would need n separate models, one per prefix; CatBoost keeps O(log n) of them and interpolates.

Fix 3 — oblivious trees

Every node at a given depth uses the same split, which makes the tree perfectly symmetric.

A depth-6 oblivious tree is therefore 6 comparisons producing a 6-bit index into a 64-entry array (2^6 = 64 leaves). Inference is branch-free: the processor runs the same six comparisons for every row and never has to guess which way a row will go.

The symmetry is also a strong regularizer, because the tree cannot specialize one subtree to a handful of rows — any split it makes, it makes everywhere at that depth.

What CatBoost assumes, and what breaks it

The rows are exchangeable — a random permutation is as legitimate an ordering as any other. Both ordered target statistics and ordered boosting depend on this.

It is exactly false for time series, where the only honest ordering is chronological and a random permutation lets later rows inform earlier ones. With time-ordered data you should be encoding by time, not by a random permutation (Temporal features and lookahead leakage).

The problem tolerates a symmetric tree structure. When a genuinely different rule is needed in one branch, the oblivious tree needs extra depth to express it and loses to an asymmetric competitor.

Picking between the three libraries

All three implement the same descent from Gradient boosting gradient descent in function space. The table below is what each one added on top, and the condition that makes that addition worth having.

10. Stacking and blending

One ensemble method combines different kinds of model, and a single implementation detail decides whether it helps or actively hurts.

Bagging and boosting combine models of the same kind. Stacking combines models of different kinds — say a random forest, a GBDT and a logistic regression.

It does this by training a second model on top. That second model is the meta learner: its input features are the first models’ predictions, and its output is the final prediction. The first models are the base models.

The diagram below is the whole procedure. Note that it has two separate paths out of the training set — one produces the meta learner’s training data, the other produces the base models that will actually run at serving time.

flowchart LR
    D[(Training set)] --> K["K-fold split"]
    K -->|"fit on K-1 folds,<br/>predict the held-out fold"| O["OOF matrix<br/>n rows x M models<br/>every prediction is<br/>out-of-sample"]
    O --> ML["Meta learner<br/>ridge or non-negative LS"]
    D --> FULL["Refit each base model<br/>on all training rows"]
    FULL --> TP["Base predictions<br/>on test rows"]
    ML --> AP["apply learned weights"]
    TP --> AP
    AP --> OUT(["Final prediction"])

    style O fill:#2d6a4f,color:#fff
    style ML fill:#40916c,color:#fff

Reading the left path: start from a K-fold split, which cuts the training rows into K equal parts. For each base model and each fold, fit on K-1 folds and predict the held-out fold. Write those predictions into the OOF matrix — n rows by M models — where every prediction is out-of-sample, because no model ever predicted a row it was trained on. Fit the meta learner on that matrix.

Two choices for the meta learner appear in the box: ridge regression, or non-negative LS, meaning non-negative least squares — a fit whose coefficients are not allowed to go below zero.

Reading the right path: separately refit every base model on all the training rows, and have them predict the test rows.

Then combine. Apply the weights the meta learner learned to those test predictions, and that is the final prediction.

Why out-of-fold predictions are non-negotiable

Train the meta learner on base predictions made on rows the base models were fit on, and you have handed it a column that is nearly the label.

The numbers below are illustrative figures showing the shape of the effect — no dataset, model configuration or seed is named, so they are not a run you can reproduce. What is real is the sign and the ordering, which is what every actual instance of this looks like. Compare the last two columns.

base model     train AUC   valid AUC     in-sample stack weight   OOF stack weight
random forest      1.000       0.861                       0.95               0.35
gradient boost     0.941       0.892                       0.05               0.65
logistic reg       0.831       0.828                       0.00               0.00

resulting ensemble valid AUC:            in-sample 0.865      OOF 0.902

The in-sample meta learner gave 0.95 of the weight to the random forest — the most overfit base model, whose train AUC is a perfect 1.000 against a valid AUC of 0.861. On training rows that model looks flawless, so the meta learner believes it.

The OOF meta learner gave 0.65 to the gradient booster instead, which is the model that actually generalizes best (valid AUC 0.892, the highest of the three). The ensemble score moves from 0.865 to 0.902 as a result.

Stacking without OOF does not combine models. It runs a contest to find which base model memorized hardest.

Blending, the cheap variant

Blending uses one holdout split instead of K folds.

It is simpler, but both sides lose data: the meta learner trains on only the holdout rows, and the base models never see those rows at all.

Use it when a fold’s worth of refits is genuinely too expensive. Otherwise use OOF.

Keep the meta learner simple

OOF columns from good models are correlated at 0.90+ — they are all predicting the same label, after all.

Ordinary least squares on collinear features — features that are near-duplicates of one another — produces huge coefficients with flipped signs, one large positive weight cancelling one large negative weight. That is not a finding about the models. It is noise fitting, and it will not reproduce on the next fold.

Ridge regression, which penalizes large coefficients, is the standard fix. So is non-negative least squares with weights summing to 1.

The non-negativity constraint does something extra: it makes the output a genuine interpolation of the base models, which caps how much damage one unstable column can do.

The code below is the OOF procedure end to end. The two comments mark the lines where the honesty comes from.

import numpy as np
from sklearn.model_selection import KFold
from sklearn.linear_model import RidgeCV

def stack(models, X, y, X_test, n_splits=5, seed=0):
    """OOF stacking. Every meta feature is an out-of-sample prediction."""
    kf = KFold(n_splits=n_splits, shuffle=True, random_state=seed)
    oof = np.zeros((len(X), len(models)))
    test_meta = np.zeros((len(X_test), len(models)))
    for j, make in enumerate(models):
        for tr, va in kf.split(X):
            oof[va, j] = make().fit(X[tr], y[tr]).predict(X[va])   # never sees va
        test_meta[:, j] = make().fit(X, y).predict(X_test)         # refit on all
    meta = RidgeCV(alphas=[0.1, 1.0, 10.0]).fit(oof, y)
    return meta.predict(test_meta), meta.coef_

Returns diminish steeply. A tuned GBDT plus one genuinely different model — a neural net, or a linear model on different features — captures nearly all of the stacking gain. A fifth GBDT with a new seed adds a correlated column and near-zero signal.

What stacking assumes, and what breaks it

The base models make different errors. Combining near-identical predictions gains nothing, which is the same rho argument from Random forests decorrelation which matters more than the bagging in a different costume.

The folds are honest. Time-ordered or grouped data needs time-aware or group-aware folds, or the OOF columns leak exactly like the in-sample ones do.

The relationship the meta learner found still holds at serving time. This one fails under drift, because the base models degrade at different rates and the weights that were right last quarter are wrong this quarter (Drift three different failures with three different signals).

11. Why GBDTs still beat neural nets on tabular data

The claim in the title is not an opinion — it rests on four mechanisms, each naming a property of tabular data that a tree exploits and that a neural network has to learn from scratch. MLP below means multi-layer perceptron, the plain fully connected neural network (Dense the layer with no prior).

1. Axis-aligned splits match how tabular targets are actually shaped

A split is axis-aligned: it tests one column against one threshold. So income > 50000 — a real decision boundary in a real dataset — is represented exactly, by one split.

An MLP has no such primitive. It builds a step out of smooth pieces, and needs many units plus a lot of data to sharpen the transition into something step-like.

Worse, MLPs have a documented bias toward smooth, slowly varying functions. Tabular targets are frequently the opposite: discontinuous, made of thresholds, brackets and regulatory cutoffs.

2. MLPs are rotation-invariant; tabular features are not interchangeable

A dense layer’s first operation is Wx — multiply the input vector by a weight matrix. Rotate the input space and the class of functions the layer can represent is unchanged, because the rotation can be absorbed into W.

That sounds like a strength. On tabular data it is a weakness.

Each column in a table means something individually — age, zip, n_prior_claims — and the informative structure is aligned with those original axes, not with some rotation of them. A model that cannot tell the original basis from a rotated one has to learn which basis matters, from data.

A tree only ever splits on original columns, so that knowledge is built in rather than learned.

This also explains why uninformative columns hurt MLPs much more. A rotation mixes noise columns into every unit. A tree just never splits on them.

3. No preprocessing surface to get wrong

Splits depend only on the order of a feature’s values. So any monotone transform — one that never changes which of two values is larger, such as log, standardize or rank — produces an identical tree.

That makes a whole category of preprocessing mistakes impossible. Mixed types, wildly different scales, heavy tails and outliers in X all cost nothing. Missing values get a learned default direction instead of an imputation you had to invent.

An MLP needs scaling, needs an imputation choice, and is sensitive to both.

4. Sample efficiency

Boosting fits one small tree at a time against a shrinking residual, so it produces a usable model at n = 1,000.

An MLP at n = 1,000 with 50 features is estimating tens of thousands of weights from a thousand examples. At that ratio the regularization choices, not the data, dominate the result.

When the neural net does win

Say this part unprompted. The table below lists the four situations where the argument above stops applying.

Two terms in that table need unpacking. An embedding, in the second row, is a learned vector of, say, 32 numbers assigned to each identifier and trained along with the model, so that similar identifiers end up near each other (Embeddings). SGD, in the last row, is stochastic gradient descent: it updates weights from one small batch at a time, which lets a network absorb new data without a full retrain.

The strong interview answer is the hybrid. Use the network to produce embeddings for the unstructured columns, then feed those embeddings as features to the GBDT.

You get the representation learning where it matters, and keep the tree’s built-in assumption that axis-aligned splits on original columns are the right shape — everywhere else.

12. Hyperparameters — what each knob does mechanically

Every knob you will actually set maps back to a mechanism from an earlier section, and the order to tune them in is not arbitrary. XGB and LGBM below are XGBoost and LightGBM, which use different names for several of the same settings.

Read the middle column of the table first — it names the mechanism from an earlier section that the knob is turning. The “typical” column is a starting range, not a recommendation.

Two rows need decoding.

“Max interaction order per tree”, in the max_depth row, means the number of features a single tree can combine in one decision. A depth-3 tree can express a rule that depends on three columns at once — income > 50000 and country = FR and age < 30 — and no more.

min_sum_hessian, LightGBM’s name for min_child_weight, says the same thing in the language of Xgboost second order and a regularizer inside the split criterion. The hessian is the second derivative h_i, so the sum of hessians in a leaf is exactly the H_j that the Newton step divides by.

The learning rate / n_estimators interaction

These two knobs are not independent, and treating them as if they were wastes most of a hyperparameter search.

The model is F_M = F_0 + eta · sum_{m=1..M} h_m. To first order, the total amount of fitting is proportional to the product eta · M — so halving eta roughly doubles the M at which validation bottoms out.

The runs below, on one dataset, show that product staying nearly constant. best_iteration is the round early stopping selected, and RMSE is root mean squared error. Watch the third column.

eta     best_iteration   eta·M    valid RMSE   relative fit time
0.30               120     36.0        0.4118              1.0x
0.10               380     38.0        0.4009              3.2x
0.05               810     40.5        0.3982              6.8x
0.02             2,100     42.0        0.3971             17.5x

Two things read off that table.

First, eta·M drifts upward slightly as eta falls, from 36.0 to 42.0. Smaller steps are also better-aimed steps, because the gradient is re-evaluated after every one — exactly as in ordinary gradient descent.

Second, the return collapses. Going from eta = 0.05 to eta = 0.02 buys 0.3982 - 0.3971 = 0.0011 RMSE for 17.5 / 6.8 = 2.6x the compute.

So eta and M are not two hyperparameters. They are one hyperparameter (eta) plus a quantity you get for free from early stopping. Never grid-search n_estimators.

Early stopping

Early stopping is the mechanic that supplies M — and it introduces a statistical bias if you then report the number it stopped on.

The code below sets n_estimators to a deliberately absurd 20,000 and lets early_stopping_rounds decide where to stop. The three-way split at the top is the part people skip.

import numpy as np
import xgboost as xgb
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split

# Three splits, not two: train fits, valid stops, test reports. Stand-in data.
X = np.random.default_rng(0).normal(size=(3_000, 20))
y = X[:, 0] * 2 + X[:, 1] ** 2 + np.random.default_rng(1).normal(scale=0.4, size=3_000)
X_fit, X_test, y_fit, y_test = train_test_split(X, y, test_size=0.2, random_state=0)
X_train, X_valid, y_train, y_valid = train_test_split(X_fit, y_fit,
                                                      test_size=0.25, random_state=0)

def evaluate(m, X_, y_):
    return mean_squared_error(y_, m.predict(X_)) ** 0.5     # RMSE

model = xgb.XGBRegressor(
    n_estimators=20_000,          # deliberately far too many
    learning_rate=0.05,
    max_depth=6,
    subsample=0.8,
    colsample_bytree=0.8,
    min_child_weight=5,
    reg_lambda=2.0,
    early_stopping_rounds=100,    # patience, in rounds
    eval_metric="rmse",
)
model.fit(X_train, y_train, eval_set=[(X_valid, y_valid)], verbose=200)
print(model.best_iteration, model.best_score)
final_rmse = evaluate(model, X_test, y_test)   # a THIRD split, untouched

Three mechanics are worth knowing.

Patience. The early_stopping_rounds argument is the number of rounds without improvement you tolerate before halting. It exists because validation curves are noisy: with eta = 0.05 a single round moves the metric by less than the round-to-round noise, so a patience of 1 would stop on a coin flip. Fifty to a hundred rounds is the usual band, and it should scale inversely with eta — smaller steps mean more rounds of noise to ride out.

Predict with best_iteration. That is the round with the best validation score, not the last round trained. Predict with the last round and the whole exercise was decorative.

The validation score you stopped on is optimistically biased. Early stopping selects M on the validation set, which means you picked the best point on a noisy curve — and part of what made that point best was noise you selected for.

Report the number on a third split instead. And if you also tuned other parameters against that same validation set, the bias compounds with every parameter.

(05 — Training & Optimization shows the other half of this story: early stopping acts as a regularizer in its own right.)

What early stopping assumes, and what breaks it. It assumes the validation split is drawn the same way as the data you will serve, and that it is large enough that the curve’s minimum is real rather than a noise dip. On time-ordered data a random validation split satisfies neither, and it will select an M tuned to information from the future.

Tuning order, and why it is that order

Search in this order, and the reason for each position is the reason it is not negotiable.

1. Fix eta at 0.05-0.1 and take M from early stopping. First because M has an exact optimum given everything else, obtainable from one fit, and because every other change moves that optimum — so M must be re-derived inside every subsequent trial rather than searched alongside them.
2. Tree capacity: max_depth / num_leaves, min_child_weight, min_data_in_leaf. Second because after M this is the largest single lever on the bias-variance split. Depth 3 versus depth 8 typically moves validation error an order of magnitude more than lambda does.
3. Sampling: subsample, colsample_bytree. Third because it is nearly free variance reduction — the same rho-lowering mechanism as a random forest, applied to boosting — and it is only a two-parameter search.
4. Explicit regularization: lambda, alpha, gamma. Fourth because it is fine adjustment that largely overlaps with steps 2 and 3. If tuning here produces a large gain, that is a signal step 2 is wrong, not that you found a great lambda.
5. Lower eta and refit. Last because it buys the final fraction of a percent while multiplying the cost of every search above it. Pay it once, at the end, on the configuration you are shipping.

Reading the curves

Four training traces and what each one tells you to change. In each block, the columns are the round number, then the training metric, then the validation metric — so the gap between the last two columns is what you are reading.

OVERFITTING                          UNDERFITTING
iter  train    valid                 iter  train    valid
 300  0.201    0.339                  100  0.401    0.408
 500  0.142    0.338  <- best        1000  0.377    0.381
 900  0.081    0.347                 3000  0.371    0.374  still falling together
1500  0.043    0.371
gap widening, valid turned up        gap ~0, both high and flat
-> variance: shallower trees,        -> bias: deeper trees, higher eta,
   subsample, min_child_weight up       more and better features

LEAKAGE                              DISTRIBUTION SHIFT
iter  train-auc  valid-auc           random split:  train 0.94  valid 0.93
  12     0.9997     0.9981           time split:    train 0.94  valid 0.71
  50     1.0000     0.9989
top importance: refund_issued 0.91   -> the random split is lying to you;
-> a post-outcome column is in X        re-split by time and retune

The first two are the bias/variance question from The decomposition everything follows from, read off a curve.

Overfitting: train falls from 0.201 to 0.043 while valid bottoms out at 0.338 and then climbs to 0.371. A widening gap with validation turning up is variance.

Underfitting: train 0.371 and valid 0.374 at round 3,000, still falling together. Both curves high, flat and nearly touching is bias.

The third is leakage: a column that encodes the outcome and would not exist at prediction time. refund_issued is known only after the fraud was confirmed, so it cannot be an input (09 — Model Debugging Playbook, Step 1d).

The fourth is distribution shift: the model scores 0.93 on rows shuffled at random and 0.71 on rows from a later period. The random split never tested the thing that will actually happen.

Near-perfect validation reached within a few dozen iterations is almost never a good model. A real signal takes hundreds of rounds to extract. A leaked label takes one split.

13. Cheat sheet

This table is the chapter compressed into symptom, mechanism and fix. Look up the left column when something is wrong; the middle column is the section that explains why.

Three abbreviations in that table are worth spelling out. CV is cross-validation, the K-fold procedure from Stacking and blending used to score a configuration. NNLS is non-negative least squares, the constrained meta learner from that same section. And a GAM is a generalized additive model, a sum of smooth one-dimensional functions of each feature, which is the right shape when the target is additive and smooth rather than made of thresholds (Generalized linear models).

The one-line version of the whole chapter: test error splits into bias, variance, and noise; bagging attacks variance and hits a floor at rho·sigma_t^2; random forests lower rho; boosting attacks bias by descending the loss in function space, one tree per step; and XGBoost, LightGBM, and CatBoost are second-order accuracy, histogram speed, and leak-free encoding bolted onto that same descent.

Next: 04 — Neural Layers & Architectures.