Boosted trees,
from a constant
to a strong learner.
Most winning models on spreadsheet-shaped data aren't neural nets: they're gradient-boosted decision trees. This guide builds the whole idea up from one if/else split, draws every step, and hands you working code. Everything you scroll past is running real trees in your browser.
The data is a table, so respect the table
Tabular data is rows of records with heterogeneous columns: age next to zip code next to "number of logins last week." The columns have different units, different scales, and the useful signal is usually non-smooth and full of interactions: "risk jumps once balance crosses $0 and the account is older than 90 days."
Neural networks love smooth, continuous, translation-invariant signals (pixels, audio, text). They struggle to carve sharp, axis-aligned thresholds out of a pile of unrelated columns. A decision tree does exactly that and nothing else: it slices one column at a time. Stack hundreds of small trees and you get a model that is fast, needs almost no preprocessing, ignores feature scale, eats missing values, and routinely tops the leaderboard on tabular problems.
A neural net bends a smooth surface to fit your data; a tree chops the space into boxes and predicts a flat value inside each box. For tables, chopping wins.
Here's the road: a single tree → how it picks a split → why we use many trees → boosting (fit the leftover error) → the calculus that makes "gradient" boosting general → from-scratch code → the production engines → the practical playbook.
A tree is just nested if/else over feature space
A decision tree is a program you didn't write by hand. Each internal node asks one yes/no question about one feature (is x ≤ 3.4?); each leaf hands back a prediction. Geometrically, every question is a straight cut perpendicular to an axis, so the tree carves the feature space into rectangles and predicts one constant per rectangle.
The dataset below is a classic trap: the two classes sit in opposite corners (an XOR pattern). No single cut can separate them, but a couple of stacked cuts can. Drag the depth and watch the boxes (and the tree) grow.
At depth 1 the tree must pick one cut for the whole plane and gets ~half wrong. Add depth and each region can be split independently: that's how a tree expresses interactions (the effect of x depends on y) for free, without you specifying them. Push depth too far and each box wraps around single points: that's overfitting, the thing boosting will carefully control.
Greedy search: try every cut, keep the best
A tree has no clever optimizer. To split a node it makes the most literal choice: scan every candidate threshold on every feature, score the resulting two groups, and keep the single best cut. Then it recurses into each side.
The score is "how much purer / less noisy are the two children than the parent." For regression (predicting a number) the natural score is squared error: a child's cost is how far its points sit from the child's mean. The leaf will predict that mean, so tight clusters are cheap and spread-out clusters are expensive.
Why does the leaf predict the mean? Because among all possible constants c you could guess, the one that minimizes total squared error is the mean. Plot SSE(c) against your guess and it's a bowl: slide the guess and watch it bottom out exactly at ȳ.
Drag the threshold below. The two horizontal bars are each side's predicted mean; the gray curve is the split score at every possible threshold. The ★ marks the global best: the exact cut the tree would actually choose.
Swap squared error for an impurity measure (Gini = 1 − Σ pk² or entropy) that is zero when a node is all one class and maximal when it's a 50/50 mix. The leaf then predicts the class proportions. The algorithm is identical: try every cut, keep the one that drops impurity the most. Everything else in this guide builds on this single greedy step.
Both impurity measures say the same thing geometrically: a node is worst when it's a 50/50 mix (you can't guess the class) and perfect (zero) when it's all one class. Drag the mix and watch the curves rise to a peak in the middle and fall to zero at the pure ends: that arch is what a split is trying to escape.
Two ways to combine trees, pulling opposite directions
A single deep tree is high-variance: jiggle the data and the cuts jump around. A single shallow tree is high-bias: too coarse to capture the pattern. Ensembles fix one problem each.
Bagging: Random Forest
Grow many deep, independent trees, each on a random bootstrap of rows and a random subset of features. Average their votes. Each tree overfits in its own direction; averaging cancels the noise. This attacks variance. Trees are parallel and the method is famously hard to break.
Boosting: the focus of this guide
Grow many shallow, dependent trees in sequence. Each new tree is trained to fix the mistakes the current ensemble is still making. Predictions are summed, not averaged. This attacks bias and, done with restraint, reaches lower error than bagging on most tabular tasks.
Watch both build the same target curve, one tree at a time. On the left, each new tree is deep, fit to a random bootstrap of the rows, and the drawn prediction is the average of all trees so far: jagged single trees, smooth average. On the right, each new tree is shallow, fit to the current residual, and predictions are summed: the fit climbs from flat toward the signal. Step each side and compare how the error falls.
Random Forest is a committee of experts voting at once: add trees and the average barely moves once it has settled, it just gets a touch smoother (variance shrinking). Boosting is an apprentice line: each worker only touches what the previous ones got wrong, so the fit keeps climbing toward the signal (bias shrinking). The next section makes "fix the mistakes" precise.
Start with the average. Then fit the leftovers. Repeat.
Here is the entire algorithm for regression, in plain language:
- Predict a single constant for everyone: the mean of
y. It's wrong, but unbiased. - Compute the residuals = how far off each point still is (
y − prediction). - Fit a small tree to the residuals: a tree whose job is to predict the error.
- Add a shrunken slice of that tree to the running prediction:
prediction += ν · tree(x). - Go back to step 2. Each pass nudges the prediction closer.
The shrink factor ν (the learning rate) keeps each tree from overcorrecting: small steps, many of them, generalize better than a few big lunges. Step through it:
Start at ν = 1.0, depth 3, and hit "+ Add 10" twice: train MSE marches toward zero while the validation curve bottoms out early and then climbs, the visible signature of overfitting. Now Reset, set ν = 0.1, and add many trees: each tree barely moves the line, but validation descends smoothly and lands lower with no upturn. Lower learning rate + more trees is the central dial of every boosting library, and the reason n_estimators and learning_rate must be tuned together.
"Residual" is just the gradient in disguise
Step 2 said "fit the residual y − F." Where did that come from? It falls out of calculus. Write the squared-error loss for one point and differentiate with respect to the model's prediction F:
See it directly. For one point with target y, the loss is a bowl in the prediction F. The slope you're standing on is the gradient; its size is how far F sits from the bottom (i.e. the residual). Slide F, then hit "step downhill" to move against the gradient toward the perfect prediction at F = y:
So the residual is exactly the negative gradient of the loss. Each boosting round is a step of gradient descent, but in function space, where the "step" is a whole tree fit to the negative gradient. That reframing is the key that unlocks everything else:
Replace squared error with any differentiable loss and the recipe is unchanged: just fit each tree to that loss's negative gradient. For classification, use the logistic loss: the gradient becomes g = p − y (predicted probability minus the label). Same loop, new problem solved. Quantile loss → quantile regression. Ranking loss → learning-to-rank. One algorithm, many tasks.
That g = p − y is less scary than it looks. The model outputs a raw score F (the log-odds); the sigmoid squashes it into a probability p. The gradient is then just the gap between your probability and the truth. Confidently wrong → big gap → big push. Flip the label and watch the gradient flip sign:
Newton boosting: also use the curvature
Modern engines (XGBoost) go one better. Instead of only the first derivative g, they also use the second derivative h (the Hessian, the loss's curvature), giving a Newton step. With a regularizer that penalizes big, confident leaves, the optimal value for a leaf has a clean closed form:
G, H are the summed gradients and Hessians of the points in a leaf. Read it as intuition: G = how wrong and in which direction; H = how confident/curved the loss is there; λ shrinks leaf values toward zero (less overconfidence); γ is a tax each split must beat to exist (automatic pruning). For plain squared error h = 1, so w* = G/(n+λ): the leaf mean residual. You already understood the simple case; this just adds curvature and a brake.
The leaf value is a Newton jump to the bottom of a local bowl. Near the current prediction the loss looks like a parabola G·w + ½(H+λ)·w²; its minimum sits at w* = −G/(H+λ). Crank λ and the bowl gets narrower, so its floor slides toward zero. The regularizer literally pulls every leaf toward "do nothing":
Give every leaf a quality score = G²/(H+λ), large when its points all push the prediction the same way (a confident, coherent group). The gain formula is then just a before/after comparison:
A split earns its place only if cutting the group in two raises the combined quality by more than the toll γ. λ deflates every score so tiny noisy groups can't look impressive; γ refuses splits that barely help. Together they prune the tree while it grows, no separate pruning pass needed.
~70 lines of numpy is the honest version
Two objects: a RegressionTree that does the greedy split from §2, and a GradientBoostingRegressor that runs the loop from §4. The boosting loop is shorter than the tree: that is the result. The library you'll use in production is this plus speed and regularization.
Three edits turn the snippet above into the shape of XGBoost: (1) replace residual = y - F with the negative gradient of your chosen loss; (2) set each leaf to -G/(H+λ) using gradients and Hessians; (3) add early stopping on a validation set. Everything else (histograms, GPU kernels, missing-value routing) is performance, not concept.
What XGBoost, LightGBM & CatBoost actually add
All three are gradient boosting with the §5 objective. They differ in the engineering tricks that make them fast and accurate at scale. Four ideas cover most of it.
1 · Histogram binning: stop scanning every value
The naive split search sorts every feature and tries every midpoint. Instead, pre-bucket each feature into ~256 bins once, then only consider bin edges as candidate cuts. Accuracy barely changes; speed and memory improve by an order of magnitude. Slide the bin count:
2 · How the tree grows: level-wise vs leaf-wise
Level-wise (XGBoost default)
Grow every node at the current depth before going deeper. Balanced, predictable trees; easy to regularize with max_depth. Safer default.
Leaf-wise / best-first (LightGBM)
Always split the leaf that reduces loss most, wherever it is. Reaches lower error with fewer splits, but grows lopsided trees that overfit small data; control it with num_leaves and min_child_samples.
3 · LightGBM's speed tricks
GOSS keeps every high-gradient (still-wrong) row but randomly down-samples the easy, already-correct rows: focus compute where the error is. EFB bundles mutually-exclusive sparse features (think one-hot columns that are never 1 together) into one, shrinking feature count without losing information.
4 · CatBoost & categoricals done right
Encoding a category by its average target (target encoding) leaks the label and overfits. CatBoost's ordered target statistics compute each row's encoding using only rows that came before it in a random permutation. No peeking at its own label. The same "ordered" principle is applied to boosting itself to remove a subtle bias. Net effect: you can hand it raw category columns and it just works.
| Engine | Reach for it when… | Signature trait |
|---|---|---|
| XGBoost | You want the dependable, battle-tested default with fine-grained control. | Level-wise growth, strong regularization, ubiquitous. |
| LightGBM | Large datasets, many features, you need speed. | Leaf-wise growth + GOSS/EFB; fastest to train. |
| CatBoost | Lots of high-cardinality categoricals; minimal tuning. | Ordered target stats; great out-of-the-box defaults. |
On a typical problem the three land within a percent of each other once tuned. Pick one, learn its knobs deeply, and don't agonize. Default suggestion: start with LightGBM for speed, switch to CatBoost if categoricals dominate.
From a fit() call to a model you trust
Preprocessing: do less than you think
- No scaling or normalization. Trees split on thresholds; multiplying a column by 1000 changes nothing. Skip the
StandardScalerreflex. - Missing values: leave them as
NaN. XGBoost/LightGBM learn a default direction at each split for missing rows, usually better than your imputation. - Categoricals: native handling (CatBoost, LightGBM) > target encoding > one-hot for high cardinality. One-hot is fine for a handful of levels.
- Feature engineering still matters most. Trees find interactions but can't invent ratios, dates-since, or aggregations: that's where your edge is.
Validation & early stopping: the highest-leverage habit
Hold out data the model never trains on. Set n_estimators very high and let early stopping halt when validation loss stops improving: it tunes the single most important hyperparameter for you, for free. Use k-fold cross-validation for reliable estimates; use time-based splits if your data has a temporal order (never let the future leak into the past).
The knobs that matter, in tuning order
| Hyperparameter | What it controls | Move it when… |
|---|---|---|
| learning_rate + n_estimators | Step size × number of steps. The core trade. | Always. Lower rate + more trees + early stopping = strong baseline. |
| max_depth / num_leaves | Tree complexity → interaction depth. | Overfitting → shrink; underfitting → grow. Start 3–8 depth. |
| min_child_weight / min_child_samples | Minimum evidence to make a leaf. | Raise to fight overfitting on noisy data. |
| subsample + colsample | Row & column sampling per tree (stochastic boosting). | Add randomness ≈ regularization; 0.7–0.9 is common. |
| reg_lambda / reg_alpha / gamma | L2 / L1 leaf penalties and split tax. | Fine-tuning once the above are set. |
Measure the right thing
- Regression: RMSE (penalizes big misses) vs MAE (robust to outliers): pick to match what hurts the business.
- Classification: log-loss / AUC for ranking quality; check calibration if you need the probabilities to mean something, not just the ordering.
- Imbalance: use
scale_pos_weightor class weights; watch precision/recall, not raw accuracy.
Explain it
Gain-based feature importance is quick but biased toward high-cardinality features. For trustworthy attributions use SHAP values: they decompose each individual prediction into per-feature contributions and have a fast exact algorithm for trees.
Perception data (images, audio, raw text) → deep nets. Problems needing extrapolation beyond the training range → trees predict a flat line past the edge of the data; use a linear/parametric model. Genuinely smooth physical relationships, or tiny datasets where a simple model is safer. Trees are the default for tables, not a universal hammer.
You can now reason about every line
- A tree is nested if/else that partitions feature space into boxes, chosen by greedy SSE/Gini search.
- Boosting sums shallow trees, each fit to the current error; learning rate keeps the steps small.
- The "error" is the negative gradient of the loss, so the same loop solves regression, classification, ranking.
- XGBoost adds the Hessian + regularized leaf formula; histograms, growth strategy, and categorical tricks are the rest.
- In practice: skip scaling, keep NaNs, lean on early stopping, tune learning_rate↔n_estimators first, explain with SHAP.
- Default move on a new table: a tuned LightGBM/XGBoost/CatBoost with early stopping, then go beat it.
Open the code blocks, paste the from-scratch booster into a notebook, and watch its loss curve match the interactive one above. Then pip install lightgbm and feel how little conceptual distance is left between the toy and the tool.