Definition
Gradient boosting (for classification) builds a log-odds score as a sum of many small regression trees, , and turns it into a probability with the sigmoid, . Each new tree is fit to the negative gradient of the log-loss of the model built so far — the pseudo-residuals — so every round takes one gradient-descent step in the space of functions.
At a glance
- Task
- Binary and multiclass classification (the same machinery handles regression and ranking with other losses)
- Input → output
- → log-odds → probability → class (threshold ½ or argmax of softmax)
- Learns
- shallow regression trees (depth 1–8) whose leaves hold log-odds corrections
- Training
- strictly sequential: tree fits, each about (or with histogram binning)
- Prediction
- comparisons, then one sigmoid
- Hyperparameters
- learning rate , number of trees , tree depth / leaves, row subsample, min samples per leaf, L2 on leaf values
- Assumes
- nothing distributional; a differentiable loss; features need no scaling (trees only look at order)
The problem
A single decision tree has to choose between two failures. Shallow, it is too blunt to capture the real boundary (high bias); deep, it memorises noise (high variance). Random forests and Extra Trees fix the variance side: grow many deep, decorrelated trees independently and average them. But averaging cannot remove bias — if every tree misses the same structure, so does their mean.
Boosting attacks bias. Start with a model that is clearly too simple, and keep adding small trees exactly where the current model is wrong. AdaBoost did this first by re-weighting misclassified points, but its recipe is tied to one loss (the exponential loss) and to hard class votes. Gradient boosting generalises it: pick any differentiable loss — for classification, the log-loss that calibrated probabilities need — and let its gradient say what "wrong" means.
The idea
Keep a running score in log-odds units, starting from the base rate. For every training point, ask: in which direction, and how hard, should my score move to lower the loss? For log-loss the answer is simply : a churner predicted at 0.3 wants ; a stayer predicted at 0.3 wants . Those numbers are not labels any more — they are continuous targets — so we fit a small regression tree to them. The tree groups points that want similar pushes, each leaf decides one push size, and we add a fraction of it to the score. Repeat.
Two consequences follow. First, points that are already confidently right () have residuals near zero, so later trees focus on the hard, misclassified or uncertain points — the same intuition as AdaBoost, derived instead of designed. Second, because the score is in log-odds, many small additive corrections compose cleanly and the final sigmoid always lands in .
Vocabulary
- Weak learner
- a model only slightly better than a constant — here a shallow regression tree; a depth-1 tree is a stump
- Raw score / margin $F(x)$
- the ensemble's output before the sigmoid, in log-odds:
- Initial model $F_0$
- the best constant score: the log-odds of the training base rate
- Pseudo-residual $r_i$
- the negative gradient of the loss with respect to ; for log-loss
- Hessian $h_i$
- the second derivative of the loss, ; it measures how curved the loss is at that point
- Leaf value $gamma$
- the constant a leaf adds to ; chosen by a Newton step, over the leaf
- Shrinkage / learning rate $ u$
- the fraction of each tree actually added; small = small, cautious steps
- Stage / round / iteration
- one cycle of compute residuals → fit tree → update; the model after rounds is
- Early stopping
- choosing as the round where validation loss is lowest
The math
Labels are , the model outputs a score , and the predicted probability is its sigmoid. The loss for one point is the binary cross-entropy (log-loss):
- true label, 0 or 1
- the model's raw score (log-odds) for this point
- predicted probability of class 1
- the logistic sigmoid
Training minimises . Substituting gives , whose derivatives with respect to the score are remarkably simple (use ):
- gradient of the loss at point i
- second derivative (Hessian) at point i; largest at p = ½, tiny when p is near 0 or 1
Gradient descent in function space. Think of the vector of predictions as the parameters. Steepest descent would move each one by . But a raw vector of numbers says nothing about new inputs, so we approximate the negative gradient with a tree: fit a least-squares regression tree to the targets . The tree's structure (its splits) defines regions that generalise to unseen .
- pseudo-residual of point i in round m
- the region covered by leaf j of tree m
- the model after m − 1 rounds
Leaf values by a Newton step. The tree's own leaf means would be gradient-step sizes in the wrong units (probability, not log-odds). Instead, for each leaf we choose the constant that minimises the real loss over the points in it, using a second-order Taylor expansion around the current scores:
- value of leaf j in tree m, in log-odds units
- current loss of point i (a constant in the minimisation)
Setting the derivative to zero gives the formula. This is exactly what scikit-learn's GradientBoostingClassifier does (Friedman's one Newton step), and XGBoost and LightGBM go one step further by also using and to choose the splits (see the XGBoost article).
- learning rate (shrinkage), 0 < ν ≤ 1
- number of leaves per tree (2 for a stump)
- fraction of positives in the training set
is the best constant: minimising means , so and is the log-odds of the base rate. Multiclass with classes uses the softmax and grows trees per round, one per class, each fit to — so a 10-class problem with 300 rounds trains 3,000 trees.
What each hyperparameter does to the math
- Learning rate ν
- scales every step. With each Newton step is taken in full and the model reaches the training data in a few rounds; with small it moves a fraction of the way, so later trees still get a say and the noise of any one tree is averaged out. Needed rounds scale roughly like .
- Number of trees M
- number of descent steps. The training loss decreases monotonically in (to 0 on separable data, by sending ); validation loss is U-shaped. is the main regulariser — choose it by early stopping.
- Depth / leaves J
- a depth- tree can express interactions between at most features; stumps give an additive model . More leaves = bigger steps in more directions per round.
- Subsample
- fit each tree on a random fraction of rows (stochastic gradient boosting): noisier gradient estimates, decorrelated trees, less overfitting, faster.
- Min samples / Hessian per leaf
- keeps in the Newton denominator away from 0. Without it, a tiny leaf of already-confident points ( or 1, ) produces an enormous .
- L2 on leaves λ
- (XGBoost / LightGBM / HistGB) shrinks the leaf value to — the same fix, made explicit.
Worked example: who will churn?
Ten customers, one feature — how many support tickets they filed last quarter — and whether they churned. 4 of 10 churned. The labels are deliberately noisy: customer 4 churned with few tickets and customer 9 stayed with many. We boost stumps with learning rate for 3 rounds.
| Customer | Tickets x | Churned y |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 3 | 0 |
| 4 | 4 | 1 |
| 5 | 5 | 0 |
| 6 | 6 | 0 |
| 7 | 7 | 1 |
| 8 | 8 | 1 |
| 9 | 9 | 0 |
| 10 | 10 | 1 |
Three rounds by hand (ν = 0.5)
- 1Initialise. , so and every . Training log-loss ; predicting "stay" for all gets 6/10 right.
- 2Round 1 — residuals. : churners get , stayers . Every .
- 3Round 1 — split. Try the 9 midpoints; the squared error of a stump on the residuals is smallest at : , down from with no split (the next best, , leaves ).
- 4Round 1 — leaves. Left (customers 1–6): , , . Right (7–10): , , . Note the right leaf moves more: fewer points share the same total push.
- 5Round 1 — update. : left (), right (). Log-loss ; 8/10 correct (only customers 4 and 9 are wrong).
- 6Round 2. New residuals: for customers 1–3, 5, 6; for customer 4; for 7, 8, 10; for 9. Best split (SSE vs ). Leaves: , . Log-loss .
- 7Round 3. Best split (SSE vs ), isolating customer 10. , — a single point with small gets a large step. Log-loss .
- 8Predict a new customer with 8 tickets: they fall right of 6.5, right of 3.5, left of 9.5, so and → predict churn. A customer with 4 tickets gets , → stay.
| Tickets | y | p₀ | F₁ | p₁ | F₂ | p₂ | F₃ | p₃ |
|---|---|---|---|---|---|---|---|---|
| 1–3 | 0 | 0.400 | −0.892 | 0.291 | −1.597 | 0.169 | −1.726 | 0.151 |
| 4 | 1 | 0.400 | −0.892 | 0.291 | −0.638 | 0.346 | −0.768 | 0.317 |
| 5–6 | 0 | 0.400 | −0.892 | 0.291 | −0.638 | 0.346 | −0.768 | 0.317 |
| 7–8 | 1 | 0.400 | 0.324 | 0.580 | 0.577 | 0.640 | 0.448 | 0.610 |
| 9 | 0 | 0.400 | 0.324 | 0.580 | 0.577 | 0.640 | 0.448 | 0.610 |
| 10 | 1 | 0.400 | 0.324 | 0.580 | 0.577 | 0.640 | 1.358 | 0.795 |
- 1F₀ ← log(p̄ / (1 − p̄))
- 2for m = 1 … M:
- 3 pᵢ ← σ(F(xᵢ)); rᵢ ← yᵢ − pᵢ
- 4 split ← argmin Σ(rᵢ − r̄_leaf)²
- 5 γ_leaf ← Σrᵢ / Σpᵢ(1 − pᵢ)
- 6 F(x) ← F(x) + ν·γ_leaf(x)
- 7predict: churn if σ(F_M(x)) > ½
4 of 10 customers churned, so the best constant is the log-odds F₀ = log(0.4/0.6) = -0.405: every customer gets p = 0.400 (log-loss 0.673).
The algorithm, step by step
GradientBoostingClassifier (binary log-loss)
- 1Initialise for every point.
- 2For :
- 3 Probabilities and gradients. , , . (With subsampling, draw the rows used this round.)
- 4 Fit the tree structure. Grow a regression tree of the chosen depth on using squared error (scikit-learn: Friedman MSE), respecting min samples per leaf.
- 5 Set leaf values. For each leaf : .
- 6 Update. . Evaluate training and validation log-loss; stop if validation loss has not improved for rounds.
- 7Predict ; class 1 if (or a threshold tuned to your costs).
Complexity
- Training
- with exact sorted splits per depth level; histogram methods bin each feature into ~256 buckets once and then cost . Multiclass multiplies by .
- Parallelism
- rounds are inherently sequential; only the split search inside one tree can be parallelised (over features or histogram bins).
- Prediction
- per input (×K for multiclass) — fast, but slower than a single tree; hundreds to thousands of trees is typical.
- Memory
- the -vector of scores , plus the trees: nodes.
Tuning: ν, M and early stopping
Learning rate and number of trees trade against each other. The table boosts depth-2 trees on a noisy two-moons problem (300 training, 300 validation points) for 1,000 rounds and records the round with the lowest validation log-loss.
| ν | Best M | Val log-loss @ best M | Val accuracy @ best M | Val log-loss @ 1000 | Val accuracy @ 1000 |
|---|---|---|---|---|---|
| 1.0 | 3 | 0.397 | 0.850 | 2.288 | 0.840 |
| 0.3 | 11 | 0.356 | 0.847 | 1.609 | 0.847 |
| 0.1 | 36 | 0.356 | 0.853 | 0.732 | 0.850 |
| 0.03 | 106 | 0.356 | 0.847 | 0.443 | 0.857 |
Practical recipe
- 1. Fix ν
- 0.05–0.1 for the final model; 0.3 for quick experiments.
- 2. Pick M by early stopping
- set a large cap (1,000–10,000) and stop when validation log-loss stalls for 20–50 rounds. On the moons data with ν = 0.1 and
n_iter_no_change=10, scikit-learn stopped at 34 trees. - 3. Depth
- 3–6 levels (or 15–63 leaves) for most tabular data. On the moons, best loss at ν = 0.1: depth 1 → 0.355 (140 trees), depth 3 → 0.369 (28), depth 6 → 0.358 (17): deeper trees need far fewer rounds and overfit faster.
- 4. Subsample
- 0.5–0.8 of rows per tree; with 0.5 on the moons the best validation loss was 0.355 at 33 trees, with a gentler rise afterwards (0.751 at 1,000).
- 5. Leaf regularisation
- min samples per leaf 20+ on large data; L2 λ = 1 in the libraries that have it.
- 6. Imbalanced classes
- already absorbs the base rate; use class weights or tune the decision threshold rather than resampling.
| Implementation | Split search | Leaf values | Distinctive features |
|---|---|---|---|
| sklearn GradientBoostingClassifier | exact, squared error on r | Newton step Σr / Σh | reference implementation; slow on large n |
| sklearn HistGradientBoostingClassifier | histograms, gradient + Hessian gain | −Σg / (Σh + λ) | native missing values and categoricals, built-in early stopping |
| XGBoost | second-order gain, exact or histogram | −Σg / (Σh + λ) | L1/L2 and γ split penalty, sparsity-aware splits |
| LightGBM | histograms, leaf-wise growth | −Σg / (Σh + λ) | GOSS row sampling, feature bundling; very fast |
| CatBoost | symmetric (oblivious) trees | Newton or gradient | ordered boosting and target statistics for categoricals |
In code
1import numpy as np23def sigmoid(f):4 return 1 / (1 + np.exp(-f))56def build(X, r, h, depth, min_leaf=1):7 """Least-squares tree on residuals r; Newton value sum(r)/sum(h) in each leaf."""8 best = None9 if depth > 0:10 for j in range(X.shape[1]):11 v = np.unique(X[:, j])12 for t in (v[:-1] + v[1:]) / 2:13 L = X[:, j] <= t14 if L.sum() < min_leaf or (~L).sum() < min_leaf:15 continue16 sse = ((r[L] - r[L].mean()) ** 2).sum() + ((r[~L] - r[~L].mean()) ** 2).sum()17 if best is None or sse < best[0]:18 best = (sse, j, t)19 if best is None:20 return {"value": r.sum() / max(h.sum(), 1e-12)}21 _, j, t = best22 L = X[:, j] <= t23 return {"j": j, "t": t,24 "left": build(X[L], r[L], h[L], depth - 1, min_leaf),25 "right": build(X[~L], r[~L], h[~L], depth - 1, min_leaf)}2627def tree_predict(node, X):28 if "value" in node:29 return np.full(len(X), node["value"])30 L = X[:, node["j"]] <= node["t"]31 out = np.empty(len(X))32 out[L] = tree_predict(node["left"], X[L])33 out[~L] = tree_predict(node["right"], X[~L])34 return out3536def fit_gb(X, y, M=100, lr=0.1, depth=1):37 F0 = np.log(y.mean() / (1 - y.mean())) # best constant: log-odds of the base rate38 F, trees = np.full(len(y), F0), []39 for _ in range(M):40 p = sigmoid(F)41 r = y - p # negative gradient of log-loss42 h = p * (1 - p) # second derivative (Hessian)43 tree = build(X, r, h, depth)44 F += lr * tree_predict(tree, X)45 trees.append(tree)46 return F0, trees4748def predict_proba(F0, trees, X, lr=0.1):49 return sigmoid(F0 + lr * sum(tree_predict(t, X) for t in trees))5051x = np.arange(1, 11, dtype=float).reshape(-1, 1) # support tickets52y = np.array([0, 0, 0, 1, 0, 0, 1, 1, 0, 1], float) # churned?53F0, trees = fit_gb(x, y, M=3, lr=0.5, depth=1)54print("F0 =", round(F0, 4))55for t in trees:56 print(f"split x <= {t['t']}: left {t['left']['value']:.4f}, right {t['right']['value']:.4f}")57print("p(train) =", predict_proba(F0, trees, x, lr=0.5).round(4))58print("p(x=8) =", predict_proba(F0, trees, np.array([[8.0]]), lr=0.5).round(4))1import numpy as np2from sklearn.ensemble import GradientBoostingClassifier3from sklearn.metrics import log_loss45x = np.arange(1, 11).reshape(-1, 1) # support tickets6y = np.array([0, 0, 0, 1, 0, 0, 1, 1, 0, 1]) # churned?78gb = GradientBoostingClassifier(n_estimators=3, learning_rate=0.5, max_depth=1).fit(x, y)9for m, p in enumerate(gb.staged_predict_proba(x), start=1):10 print(f"round {m}: log-loss {log_loss(y, p):.4f}")11print("p(train) =", gb.predict_proba(x)[:, 1].round(4))12print("p(x=8) =", gb.predict_proba([[8]])[:, 1].round(4))13print("F(x=8) =", gb.decision_function([[8]]).round(4))1from sklearn.ensemble import HistGradientBoostingClassifier23gb = HistGradientBoostingClassifier(4 learning_rate=0.1, max_iter=2000, max_leaf_nodes=31, l2_regularization=1.0,5 early_stopping=True, validation_fraction=0.15, n_iter_no_change=30,6 scoring="loss", # monitor log-loss, not accuracy7).fit(X_train, y_train)8print(gb.n_iter_) # trees actually kept9proba = gb.predict_proba(X_test)[:, 1]Use when
- +Tabular data where accuracy and well-ranked probabilities matter — gradient-boosted trees are the default winner on structured data.
- +Mixed numeric and categorical features, missing values, unscaled and skewed inputs, non-linear interactions.
- +You need a custom or non-standard objective: any differentiable loss with a gradient (and ideally a Hessian) plugs in.
- +You can afford a validation set for early stopping and a modest tuning budget.
Avoid when
- −Images, audio, raw text — neural networks learn much better representations.
- −Very noisy labels or tiny datasets: later rounds chase mislabeled points, as customers 4 and 9 show above.
- −You need extrapolation or smooth boundaries: the score is piecewise constant and flat beyond the training range.
- −Training must be massively parallel or online: rounds are sequential, and the model must be refit to absorb new data.
Where it's used
Credit risk & fraud
Default-probability and transaction-fraud scoring on hundreds of tabular features, where calibrated probabilities feed directly into pricing and review queues.
Customer churn & conversion
Predicting which subscribers will cancel or which visitors will buy, from usage, billing and support history — the worked example in miniature.
Click-through & ranking
Ad CTR prediction and learning-to-rank (LambdaMART is gradient boosting on a ranking loss) in search engines.
Physics & medicine
Signal-vs-background event selection at particle colliders and risk scores from electronic health records.
Check yourself
A churner (y = 1) currently has predicted probability p = 0.3. What is its pseudo-residual for log-loss, and which way will the next tree push its score?
Check yourself
A leaf holds four points, all currently at p = 0.4, with labels 1, 1, 0, 1. What is its Newton leaf value γ?
Check yourself
Training data has 4 positives out of 10. What is the initial score F₀ of a log-loss gradient-boosting classifier?
Check yourself
With ν = 1 on the moons data, validation accuracy at 1,000 trees (0.840) is close to its value at the best round (0.850), yet validation log-loss is 2.288 instead of 0.397. What happened?
Remember
- ✓The model is a log-odds score , turned into a probability by the sigmoid; is the log-odds of the base rate.
- ✓Each round fits a regression tree to the pseudo-residuals — the negative gradient of log-loss — so boosting is gradient descent in function space.
- ✓Leaf values are Newton steps , in log-odds units; tiny confident leaves need min-leaf or L2 limits.
- ✓ and trade off (best ); choose by early stopping on validation log-loss, because training loss always goes to zero.
- ✓Depth controls interaction order; subsampling and leaf regularisation add robustness. XGBoost, LightGBM and CatBoost are engineered versions of this same loop.