Appearance
12.3.4 — Trees, Forests and Boosting
Cartwise's fraud analysts describe fraud the way people naturally describe rules: "If the account is new, be suspicious. If it is not new but the order was placed at night, be a bit suspicious. Otherwise, relax." That is not a weighted sum. It is a sequence of questions, each one depending on the answer to the last. Logistic regression from 12.3.1 cannot express "it depends", because it can only add up separate pushes and cut the data with one straight line.
A decision tree is exactly that sequence of questions, learned from data. On its own a single tree is fragile. But combine hundreds of them in the right way and you get random forests and gradient-boosted trees, which are, as of today, the most accurate models available for data that comes in rows and columns. Most fraud models, credit scores, demand forecasts and pricing models in production are gradient-boosted trees. This page builds them from a single question upwards.
1. A decision tree: twenty questions, learned
Here are ten past orders with two yes-or-no facts each: was the account new, and was the order placed at night?
| Order | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| New account | yes | yes | no | no | yes | no | no | no | no | no |
| At night | yes | yes | yes | yes | no | no | no | no | no | no |
| Fraud | yes | yes | yes | no | yes | no | no | no | no | no |
A decision tree asks one question, splits the orders into two groups by the answer, then asks another question inside each group, and so on, until each group is mostly one class. The last groups, which give the answers, are called leaves. Here is the tree that the data above produces:
Read it from the top. A new account sends you left, and all three such orders were fraud, so that leaf predicts fraud with full confidence. An established account sends you right, to a second question about the time. Daytime orders from established accounts were never fraud. Night-time ones were one fraud and one genuine, so that leaf can only say 50–50. To make a prediction for a fresh order, you follow its answers down to a leaf, and the leaf's mix of fraud and genuine becomes the probability.
How the tree chooses its questions
The algorithm tries every possible question and keeps the one that makes the two resulting groups most pure, meaning most dominated by a single class. Purity needs a number, and the most common one is Gini impurity:
\text{Gini} = 1 - \sum_{k} p_k^2
Read it as "one minus the sum of the squared class proportions". Here p_k is the fraction of the group in class k. It has a concrete meaning: pick two orders at random from the group; Gini is the chance they belong to different classes. A pure group has Gini 0. A 50–50 group has Gini 1 - (0.5^2 + 0.5^2) = 0.5, the most mixed a two-class group can be. The name comes from the Italian statistician Corrado Gini, who devised a related measure in 1912 to describe how unequally income is spread across a population.
At the top, 4 of the 10 orders are fraud, so \text{Gini} = 1 - (0.4^2 + 0.6^2) = 1 - 0.52 = 0.48. Now compare the two possible first questions.
Split on "new account". The yes side has 3 orders, all fraud: Gini 0. The no side has 7 orders, 1 fraud: 1 - \left((1/7)^2 + (6/7)^2\right) = 1 - 37/49 \approx 0.245. Weight each side by its share of the orders: 0.3 \times 0 + 0.7 \times 0.245 \approx 0.171.
Split on "at night". The yes side has 4 orders, 3 fraud: 1 - (0.75^2 + 0.25^2) = 0.375. The no side has 6 orders, 1 fraud: 1 - \left((1/6)^2 + (5/6)^2\right) \approx 0.278. Weighted: 0.4 \times 0.375 + 0.6 \times 0.278 \approx 0.317.
The "new account" split brings the impurity down from 0.48 to 0.171, a drop of 0.309. The "night" split only brings it to 0.317, a drop of 0.163. The bigger drop wins, so "new account" becomes the first question. Then the same procedure runs again inside each group, and that is the whole training algorithm: greedily pick the best question, split, and repeat inside each half. "Greedy" means it picks whatever looks best right now without planning ahead, which is fast but not guaranteed to find the best possible tree overall.
You will also see entropy used instead of Gini. It is Shannon's measure of surprise from 12.2.6, -\sum_k p_k \log_2 p_k, and the drop in entropy from a split is called information gain. In practice Gini and entropy almost always choose the same splits, and Gini is slightly faster to compute because it has no logarithm.
For a number column like order amount, the algorithm sorts the values and tries a cut between every pair of neighbours, "amount ≤ 18,000?", "amount ≤ 22,500?", and keeps the best. For regression, where the leaf predicts a number, the purity measure is simply the variance of the values in each group, and each leaf predicts their average.
What a tree can do that a line cannot
The figure shows the real advantage. Every question a tree asks is "is this feature above or below some value?", which is a cut parallel to one axis. A sequence of such cuts carves the space into rectangles, and with enough cuts you can isolate any pocket, however oddly placed. That is why trees capture interactions ("night matters, but only for small orders") and non-linear effects ("risk jumps above ₹50,000") with no feature engineering. They also need no standardisation of features, because a cut at "amount ≤ 50,000" works the same whatever the scale, and the best tree libraries handle missing values on their own.
Why a single tree is not enough
Let a tree keep splitting and it will continue until every leaf holds a single training order, perfectly pure. That tree has memorised the training data, noise and all. It is the degree-9 curve of 12.3.3 in another form: zero training error, poor test error. Single trees are also unstable: change a few training orders and the very first question can change, which reshapes the entire tree beneath it. That is high variance. You can limit the depth or require a minimum number of orders per leaf, which helps, but the real fix is to stop relying on one tree.
2. Random forests: many different trees, averaged
The idea behind a random forest is the wisdom of crowds. Ask one person to guess the number of sweets in a jar and they will be well off. Ask a thousand people and average their guesses, and the average is usually remarkably close, because individual mistakes in opposite directions cancel. That only works if the guessers make different mistakes. A thousand copies of the same person, making the same mistake, average to the same mistake.
The maths says exactly this. If you average n models that each have variance \sigma^2 and whose errors have correlation \rho (the Greek letter rho, how much their mistakes move together, from 0 for unrelated to 1 for identical), the variance of the average is:
\text{Var}(\text{average}) = \rho\,\sigma^2 + \frac{1 - \rho}{n}\,\sigma^2
Read the two terms. The second shrinks towards zero as you add more models: that is the crowd cancelling out mistakes. The first does not shrink at all, however many models you add: that is the shared mistake that every model makes together. So the trick is to make the trees as different from each other as possible, to push \rho down. A random forest, introduced by the statistician Leo Breiman in 2001, does it with two kinds of randomness:
- Each tree sees a different random sample of the rows. For each tree, draw as many rows as the training set has, but with replacement, so some rows appear twice and about a third never appear at all. This is called bootstrapping, from the phrase "pulling yourself up by your own bootstraps", because it creates many training sets out of the one you have.
- Each split sees a random subset of the features. At every question, the tree may only choose among a random handful of the features, often the square root of the total number. Without this, every tree would pick the same one dominant feature, such as "new account", for its first question, and the trees would end up similar. Forcing them to sometimes do without it makes them genuinely different.
Each tree is grown deep and allowed to overfit. Then, to predict, every tree votes, and the forest reports the average. Training many models independently on bootstrapped samples and averaging them is called bagging, short for bootstrap aggregating.
Random forests are hard to get badly wrong. They need little tuning, they rarely overfit as you add more trees (more trees only lowers the second term above), and they give a free validation estimate: each tree can be tested on the third of the rows it never saw, called out-of-bag rows. They are an excellent second baseline after logistic regression.
3. Gradient boosting: each tree fixes the last one's mistakes
Bagging builds trees side by side and averages them. Boosting builds them one after another, and each new tree is trained to fix the mistakes left by all the trees before it.
Think of a team of golfers sharing one ball on a long putt. The first golfer hits it and it stops ten feet short and slightly right. The second golfer does not go back to the start. She walks to where the ball lies, looks only at the remaining gap, and putts to close it, overshooting slightly to the left. The third golfer walks to that spot and taps it the last bit. Nobody tries to make the whole putt alone. Each one only corrects what is left.
In gradient boosting, the "remaining gap" is the residual from 12.3.1: the truth minus the current prediction. Each new tree is trained to predict those residuals, and its predictions are added, scaled down by a learning rate, to the running total. Let us run it by hand on the four deliveries from 12.2.4, using the smallest possible tree, a single question, called a stump, and a learning rate of 0.5.
| Parcel | Distance | True days | Round 0 | Round 1 | Round 2 |
|---|---|---|---|---|---|
| A | 1 | 2 | 4.000 | 3.250 | 2.875 |
| B | 2 | 3 | 4.000 | 3.250 | 2.875 |
| C | 3 | 5 | 4.000 | 4.750 | 5.125 |
| D | 4 | 6 | 4.000 | 4.750 | 5.125 |
| Mean squared error | 2.500 | 0.813 | 0.391 |
Round 0. Start with the simplest possible guess: the average of all four, 4 days. The residuals are 2 - 4 = -2, 3 - 4 = -1, +1 and +2. The error is (4 + 1 + 1 + 4)/4 = 2.5.
Round 1. Fit a stump to those residuals. The best single question is "distance ≤ 2.5?": the two short parcels have residuals averaging -1.5, and the two long ones +1.5. That stump's predictions are -1.5 for A and B and +1.5 for C and D. Add half of that (the learning rate of 0.5) to the running guess: A and B become 4 - 0.75 = 3.25, C and D become 4 + 0.75 = 4.75. The new residuals are -1.25, -0.25, +0.25, +1.25, and the error drops to 0.813.
Round 2. Fit another stump to the new residuals. The same question wins again, with averages of -0.75 and +0.75. Add half: A and B become 3.25 - 0.375 = 2.875, C and D become 4.75 + 0.375 = 5.125. The error drops to 0.391.
Each round, the remaining error shrinks, and every tree only ever has to model a small correction. With hundreds of rounds, trees of depth four to eight, and real features, this produces extremely accurate models.
Why "gradient"? Because the residual is exactly the negative gradient of the squared error with respect to the prediction (the slope of (y - \hat{y})^2 with respect to \hat{y} is -2(y - \hat{y})). Each tree is a step of gradient descent from 12.2.4, but taken in the space of predictions rather than weights. For classification, the trees fit the gradient of the cross-entropy loss instead, which turns out to be our old friend y - p, and the same recipe applies. This view of boosting as gradient descent was set out by the statistician Jerome Friedman in a 2001 paper.
The learning rate matters here exactly as it did for gradient descent. Without it, each tree would try to close the whole gap at once, overshoot on noise, and overfit quickly. With a small learning rate, say 0.05, each tree contributes a little, many trees are needed, and the result generalises better. Unlike a random forest, boosting can overfit if you add too many rounds, because each new tree keeps chasing the residuals, including the noise. So boosting is always run with early stopping: watch the validation error after each tree, and stop when it stops falling.
The libraries you will actually use
Three open-source libraries do gradient boosting fast enough for real data, and they dominate tabular machine learning:
- XGBoost ("extreme gradient boosting"), released by Tianqi Chen in 2014, which made boosting fast, added regularisation of the trees themselves, and won a long run of data science competitions.
- LightGBM, released by Microsoft in 2016, which speeds training further by sorting each feature's values into a small number of bins (often 255) before training, so that finding the best cut means scanning a few hundred bins instead of millions of raw values.
- CatBoost, released by Yandex in 2017, which is especially good at categorical features, columns like "city" or "payment method" whose values are names rather than numbers.
scikit-learn includes its own version of the LightGBM approach, HistGradientBoostingClassifier, which is a fine choice when you would rather not add another library. All of them handle missing values by learning which side of each split the missing rows should go.
4. In code
python
import numpy as np
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.ensemble import GradientBoostingRegressor
# The ten orders from section 1: [night, new_account]
X = np.array([[1,1],[1,1],[1,0],[1,0],[0,1],[0,0],[0,0],[0,0],[0,0],[0,0]])
y = np.array([ 1, 1, 1, 0, 1, 0, 0, 0, 0, 0])
tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X, y) # (1)
print(export_text(tree, feature_names=["night", "new"])) # (2)
# |--- new <= 0.50
# | |--- night <= 0.50
# | | |--- class: 0
# | |--- night > 0.50
# | | |--- class: 0
# |--- new > 0.50
# | |--- class: 1
# The four parcels from the boosting table
d = np.array([[1], [2], [3], [4]])
days = np.array([2.0, 3.0, 5.0, 6.0])
gb = GradientBoostingRegressor(n_estimators=2, learning_rate=0.5,
max_depth=1).fit(d, days) # (3)
print(gb.predict(d)) # → [2.875 2.875 5.125 5.125]Line (1) fits a tree of at most two levels. max_depth is the simplest guard against the memorising tree of section 1. Line (2) prints the tree as text, and it is the tree from the figure: the first question is "new" (written as new <= 0.50, which for a 0-or-1 feature means "not new"), and the second is "night". The night-time leaf says class 0 because its two orders are tied one-to-one, and the library breaks the tie towards the first class; predict_proba would show the honest 0.5. Line (3) reproduces the boosting table: two rounds of stumps with a learning rate of 0.5 give exactly 2.875 and 5.125.
On a real fraud dataset with millions of rows, you would write something like this, with early stopping built in:
python
from sklearn.ensemble import HistGradientBoostingClassifier
model = HistGradientBoostingClassifier(
learning_rate=0.05, # (1) small steps, many trees
max_leaf_nodes=31, # (2) each tree's size
max_iter=2000, # (3) an upper limit on trees…
early_stopping=True, # (4) …stop when validation stops improving
validation_fraction=0.1,
)
# model.fit(X_train, y_train); model.predict_proba(X_test)[:, 1]Line (1) is the learning rate from the golf putt: small steps generalise better. Line (2) caps each tree's size. Lines (3) and (4) set a generous ceiling on the number of trees and let the validation error decide the real number. For time-ordered data like fraud, you would pass your own date-based validation set rather than a random 10 percent, for the reason in 12.3.3.
5. Stacking, and when to use which
There is a third way to combine models, called stacking. Train several genuinely different models, say a logistic regression, a random forest and a gradient-boosted model, then train one more small model whose inputs are their predictions. That final model learns which of them to trust in which situations. Stacking squeezes out a little extra accuracy and is popular in competitions, but it multiplies the work of maintaining the system, so in production it is used sparingly.
Why do trees beat neural networks on tabular data, when neural networks win on images and text? Several reasons combine. Tabular features are each meaningful on their own (amount, account age), so there is no need to learn features from raw pixels, which is deep learning's great strength. Important effects in tables are often sharp thresholds ("over ₹50,000"), which trees express in one cut and smooth networks approximate awkwardly. Tables often contain many useless columns, which trees simply never pick, while networks have to learn to ignore them. And tabular datasets are often only thousands to millions of rows, which suits trees and starves networks. Studies comparing the two on benchmark tables keep finding boosted trees ahead or level, at a fraction of the training effort.
So the practical ladder for a Cartwise table problem is: logistic regression first (the honest, explainable baseline), then gradient-boosted trees (usually the accuracy winner), and only then anything more elaborate, if the gain pays for the upkeep. The case study in Chapter 12.3.7 climbs exactly that ladder.
What the interviewer will push on
"How does a decision tree choose a split?" They are checking that you can describe greedy search over features and thresholds by impurity reduction. A good answer defines Gini as the chance two random items differ in class and walks one split. The wrong answer is "it picks the most important feature" without saying how importance is measured.
"Random forest versus gradient boosting?" They want parallel-and-averaged versus sequential-and-corrective, and the consequence: forests mainly reduce variance and rarely overfit with more trees, boosting reduces bias and can overfit, so it needs a small learning rate and early stopping. The tell is mentioning feature subsampling as the way forests decorrelate trees.
"Why does averaging trees help?" The strong answer gives the variance formula, or at least its message: averaging cancels independent mistakes but not shared ones, so diversity is the point.
"Why do trees beat neural networks on tabular data?" They are checking practical judgement: meaningful hand-made features, sharp thresholds, irrelevant columns, and dataset size. Saying "neural networks are always better" is the wrong answer.
Volunteer this: the most common real-world bug with boosted models is not the model but the validation set. Early stopping on a random split of time-ordered data stops at the wrong point, because the validation rows are too similar to the training rows, and the model looks better than it will be in production.
Recall
- A decision tree asks a sequence of "feature ≤ value?" questions, chosen greedily to make groups purer. Gini impurity is the chance two random items in a group differ in class; entropy is the alternative.
- Trees capture interactions and thresholds, need no scaling, and handle missing values, but one deep tree memorises and is unstable.
- A random forest averages many deep trees trained on bootstrapped rows with random feature subsets (bagging). Averaging cancels independent mistakes; the shared part \rho\sigma^2 remains, so diversity is the point.
- Gradient boosting adds trees one after another, each fitted to the current residuals (the negative gradient), scaled by a learning rate. It is the most accurate tabular method and can overfit, so use early stopping. XGBoost, LightGBM and CatBoost are the main libraries.
- Stacking trains a model on other models' predictions. On tables, climb from logistic regression to boosted trees before anything heavier.
Self-test: Compute the Gini impurity of a group with 2 fraud and 8 genuine orders. In the boosting table, what would round 1 give for parcel A with a learning rate of 1.0, and why is that riskier? Why does a forest pick a random subset of features at each split?
Next: 12.3.5 The Other Classical Tools — nearest neighbours, naive Bayes and support vector machines each solve a problem in their own way, and one of them is the direct ancestor of how modern search engines work.