Trees and boosting

Most of this primer is about neural networks, because language models are neural networks. But open the models that decide whether a loan is approved, whether a card payment looks like fraud, which ad to show, or how many umbrellas a shop should stock, and very often you find no neural network at all. You find hundreds of small decision trees, added together.

Those problems share a shape: a table. Each row is a customer, a payment or a day; each column is a fact measured in its own units (age in years, income in dollars, number of late payments, a region code). On tables of modest size, ensembles of trees have stayed the model to beat, and they train in seconds on a laptop. This lesson builds them from scratch, so you can see why they work and, just as usefully, recognise when a neural network is the wrong tool.

The plan: one tree (how it chooses its questions), why a single tree overfits, how a random forest fixes that by averaging many trees, how gradient boosting fixes it differently by adding trees one after another, and finally a head-to-head against a small neural network from primer.ml.neural_net on a loan table.

Everyday picture A nurse at an emergency desk runs a flowchart: "Is the patient breathing normally? No: resuscitation room. Yes: is there chest pain? Yes: see a doctor now. No: take a seat." Each question looks at one fact and sends the patient left or right, and the last box gives the answer. A decision tree is exactly that flowchart, except the questions are chosen by the computer from past examples.

Tiny example Eight emails, each described by two facts: how many links it contains, and whether it comes from a sender you have written to before.

The tree this lesson grows from those eight rows:

flowchart TD
  Q1{"known sender?"} -->|yes| L1["not spam<br/>(emails 1, 2, 3)"]
  Q1 -->|no| Q2{"more than 0 links?"}
  Q2 -->|no| L2["not spam<br/>(email 4)"]
  Q2 -->|yes| L3["spam<br/>(emails 5, 6, 7, 8)"]

In code: spam_emails returns the table above; DecisionTree grows the tree, and DecisionTree.rules prints it as nested if/else lines.

Everyday picture You are sorting laundry into piles. A pile of only socks is pure: pull out any two items and they match. A pile that is half socks, half shirts is as mixed-up as two kinds of item can be. A good sorting question is one that leaves piles as pure as possible.

Tiny example Before any question, the eight emails are 4 spam and 4 not: a 50/50 pile. Pull out two emails at random (putting the first one back) and they disagree half the time. The pile of unknown senders is 1 "not spam" and 4 spam: purer, so two random picks disagree less often.

Gini impurity is exactly that chance of disagreement:

# four spam (1) and four not spam (0)
labels = [1, 1, 1, 1, 0, 0, 0, 0]
# p_k: the share of each label
p = [labels.count(k) / len(labels) for k in (0, 1)]
p  # → [0.5, 0.5]
# G = 1 - Σ p_k²
1 - sum(p_k ** 2 for p_k in p)  # → 0.5
# the unknown-sender pile: 1 not spam, 4 spam
p = [1 / 5, 4 / 5]
round(1 - sum(p_k ** 2 for p_k in p), 2)  # → 0.32

Why it matters the tree needs a single number to compare questions with, and it must be cheap, because a real tree scores millions of candidate questions. Gini needs only counts, one multiply per label, and no logarithm.

In code: gini computes for any list of labels.

Entropy: the same idea, counted in yes/no questions

Everyday picture Entropy asks: if I had to guess an email's label by asking yes/no questions, how many would I need on average? A 50/50 pile needs one full question. A pure pile needs none, because you already know.

Tiny example For the eight emails, one question ("is it spam?") settles it: entropy 1 bit. For the unknown-sender pile, 4 of 5 are spam, so you are usually right before asking and the average cost is about 0.72 of a question.

import math
# H = -Σ p_k log2 p_k
p = [0.5, 0.5]
-sum(p_k * math.log2(p_k) for p_k in p)  # → 1.0
p = [1 / 5, 4 / 5]
round(-sum(p_k * math.log2(p_k) for p_k in p), 3)  # → 0.722

Gini and entropy almost always pick the same question; Gini is a little cheaper. The drop in entropy a question produces is called information gain, the name the early ID3 algorithm used. See primer.notation for logarithms from scratch and primer.ml.losses for entropy's close cousin, cross-entropy.

In code: entropy computes in bits; DecisionTree takes criterion="entropy" to split by it instead of Gini.

Everyday picture A question splits one pile into two. Judge it by how messy the two new piles are, but weigh each by its size: a tiny pure pile of one email is worth less than a big pure pile of five.

Tiny example "Known sender?" makes a pile of 3 (all not spam, Gini 0) and a pile of 5 (1 not spam, 4 spam, Gini 0.32). "More than 2 links?" makes a pile of 4 (3 not spam, 1 spam) and another pile of 4 (1 not spam, 3 spam), Gini 0.375 each.

# known senders: 3 emails, all not spam
n_left, g_left = 3, 0.0
# unknown senders: 1 not spam, 4 spam
n_right, g_right = 5, 0.32
n = n_left + n_right
# G_split = (n_L/n)·G(L) + (n_R/n)·G(R)
round(n_left / n * g_left + n_right / n * g_right, 3)  # → 0.2
# the impurity the question removed
round(0.5 - 0.2, 3)  # → 0.3

Where do candidate questions come from? For a number such as "links", only thresholds between neighbouring values in the data can change which emails go where. The links column holds 0, 1, 3, 4, 5 and 6, so there are five thresholds worth trying (halfway points 0.5, 2, 3.5, 4.5, 5.5), plus one for the yes/no column. The tree scores all six and keeps the lowest.

In code: split_impurity is ; candidate_splits scores every question in the figure; best_split does the same search fast, by sorting each feature once and keeping running label counts, and returns a Split.

Why it matters this greedy search is the whole learning algorithm. There is no gradient and no learning rate: the tree tries every feature and every threshold and takes the best. That is why trees handle columns in any units, as the last section shows.

Everyday picture Sorting a big box of photos: first by year, then each year's pile by who is in them, then each of those by place, until every pile is tidy or too small to bother with.

Tiny example After "known sender?", the left pile (emails 1, 2, 3) is already pure: it becomes a leaf. The right pile (4, 5, 6, 7, 8) is not, so the tree searches again inside that pile only. There, "more than 0 links?" separates email 4 from the four spam emails perfectly. Both new piles are pure, so growth stops at depth 2.

flowchart TD
  S["node: the examples that reached here"] --> P{"pure, too small,<br/>or at the depth limit?"}
  P -->|yes| LEAF["make a leaf:<br/>predict the majority label<br/>(or the average number)"]
  P -->|no| SEARCH["try every feature and every threshold;<br/>keep the lowest weighted impurity"]
  SEARCH --> SPLIT["send examples left (feature ≤ threshold)<br/>or right (feature > threshold)"]
  SPLIT --> LEFT["grow the left child"] & RIGHT["grow the right child"]
  LEFT -.-> S
  RIGHT -.-> S

Each question looks at a single feature and compares it with a threshold, so every question cuts the input space with a straight line parallel to an axis. A tree therefore carves the plane into rectangles:

A regression tree, predicting a number instead of a label, is the same recipe with two swaps: the impurity is the variance of the numbers in a pile (how spread out they are), and a leaf predicts their average. Gradient boosting, below, is built from those.

In code: DecisionTree grows by the recipe in the diagram (a depth limit and a minimum leaf size are its stopping rules, and the "squared" criterion makes it a regression tree), and DecisionTree.predict routes each row down to its leaf.

Everyday picture Ask a friend to write rules for which of their emails are spam, and forbid them from stopping until every past email is sorted correctly. They will end up with rules like "an email from Pat at 9:14 on a Tuesday with 3 links is spam": perfect on the past, useless for the future.

Tiny example On the noisy moons, a tree with no depth limit grows 51 leaves and gets 100% of its 300 training points right. On 200 fresh points it gets 82%. A tree stopped at depth 2 has 4 leaves, gets 88% on training and 89.5% on the fresh points: it learned the shape rather than the noise.

A single tree is the textbook high-variance model: change a few training points and the top question can flip, and everything below it changes with it. There are two ways out. Keep trees small (limit the depth, require a minimum number of examples per leaf, or grow fully then prune back the branches that do not help on validation data). Or keep trees big and combine many of them, which is what the rest of this lesson does.

In code: depth_sweep grows one tree per depth limit on moons_split data and measures both accuracies.

Why it matters depth is the tree's capacity knob. Every tree library exposes it (along with a minimum leaf size), and choosing it on validation data is the first thing to tune.

Everyday picture At a county fair, hundreds of people guess the weight of an ox. Individual guesses are wildly off in both directions, but the average of all of them lands remarkably close, because the errors point in different directions and cancel. A random forest does this with trees: grow many deep trees that each make different mistakes, then average them. The trick is making the mistakes different, since averaging copies of the same tree changes nothing.

Two sources of difference, both from Leo Breiman:

1. Bagging (bootstrap aggregating): each tree trains on its own bootstrap sample, a resample of the training rows drawn with replacement.
2. Random feature subsets: at every node, a tree may only consider a random handful of the features (commonly the square root of their number), so different trees are forced to find different questions.

flowchart LR
  D["training table<br/>(n rows)"] --> B1["bootstrap sample 1<br/>n rows drawn with replacement"] & B2["bootstrap sample 2"] & B3["..."] & BB["bootstrap sample B"]
  B1 --> T1["deep tree 1<br/>random features at each node"]
  B2 --> T2["deep tree 2"]
  B3 --> T3["..."]
  BB --> TB["deep tree B"]
  T1 & T2 & T3 & TB --> AVG["average their class shares<br/>(or their numbers)"]
  AVG --> OUT["prediction"]

Bagging: drawing names from a hat, and putting them back

Tiny example Put the eight email numbers in a hat. Draw one, write it down, put it back, and repeat eight times. One draw might give 3, 1, 3, 7, 5, 1, 8, 2: emails 1 and 3 twice, and emails 4 and 6 not at all. Each tree sees a slightly different dataset, with some rows counted double and about a third missing.

How big is "about a third"? A particular email is missed on one draw with chance , and missed on all draws with:

import math
n = 8
# (1 - 1/n)^n: missed on every one of the n draws
round((1 - 1 / n) ** n, 4)  # → 0.3436
round((1 - 1 / 100_000) ** 100_000, 4)  # → 0.3679
round(1 / math.e, 4)  # → 0.3679

The rows a tree never saw are its out-of-bag rows: a free validation set for that tree, which random forests use to estimate their own accuracy without holding data back.

In code: bootstrap_sample draws the n row indices; out_of_bag_fraction is the formula; RandomForest gives every tree its own sample and its own feature subsets.

Why averaging helps, and what limits it

Tiny example Three trees give a point spam probabilities of 0.9, 0.2 and 0.7. The forest says 0.6. If each tree's error is a coin flip that cancels out on average, three trees already wobble less than one; a hundred wobble far less. But if every tree makes the same mistake, averaging keeps it.

sigma2, rho = 1.0, 0.3
# ρσ² + (1 - ρ)σ²/B
round(rho * sigma2 + (1 - rho) * sigma2 / 10, 4)  # → 0.37
round(rho * sigma2 + (1 - rho) * sigma2 / 1000, 4)  # → 0.3007
# independent trees: the variance falls as 1/B
round(0.0 * sigma2 + (1 - 0.0) * sigma2 / 10, 4)  # → 0.1

That is why a forest adds random feature subsets on top of bagging: bagging alone leaves every tree free to pick the same strong feature at the top, so the trees stay correlated. Forcing each node to choose from a random subset pushes down, which is the only way to push the floor down. Each tree gets a little worse; the average gets better.

In code: averaged_variance is the formula; forest_curve grows one forest and scores its first k trees for each k; RandomForest.predict_proba averages the trees' class shares.

Why it matters a random forest is the most forgiving model in machine learning. Its defaults (a few hundred unpruned trees, square root of the features per node) work well on most tables with no tuning at all, which is why it is the standard first model on new tabular data.

Everyday picture Golf. Your first shot from the tee gets you near the green. Your second shot does not start over from the tee: it aims at what is left, the gap between the ball and the hole. Each shot is small and corrects what remains. Gradient boosting builds a model the same way: start with a crude guess, then add small trees one at a time, each trained only on what the model so far still gets wrong.

Where a forest grows big trees side by side and averages them, boosting grows small trees in sequence and adds them up. The forest fights variance; boosting fights bias (being systematically off), a little at a time.

flowchart LR
  F0["F₀: start with the average"] --> R["residuals:<br/>what is still wrong<br/>r = y − F"]
  R --> H["fit a small tree hₘ<br/>to the residuals"]
  H --> U["Fₘ = Fₘ₋₁ + η · hₘ<br/>take a small step"]
  U -->|"next round"| R
  U --> OUT["after M rounds:<br/>F₀ + η·(h₁ + h₂ + … + h_M)"]

Tiny example Four houses of size 1, 2, 3 and 4 sold for 1, 2, 6 and 7 (hundreds of thousands, say). Boost with stumps (trees with a single question) and learning rate :

is the average price, the best single guess. The stump's best question on the residuals is "size ≤ 2.5?", and each leaf predicts its average residual: −2.5 for the small houses, +2.5 for the big ones. Adding half of that moves every guess toward its price. The mean squared error falls from 6.5 to 1.8125 in one round, and a second round brings it to 0.64.

Residuals are the negative gradient

Why is this called gradient boosting? Because "fit what is still wrong" is a special case of gradient descent (primer.ml.optimizers), taken in the space of predictions instead of weights.

y, F, eps = 7.0, 4.0, 1e-6
# ∂L/∂F, measured by nudging F both ways
slope = (0.5 * (y - (F + eps)) ** 2 - 0.5 * (y - (F - eps)) ** 2) / (2 * eps)
round(slope, 6)  # → -3.0
# r = -∂L/∂F is the plain residual y - F
round(-slope, 6), y - F  # → (3.0, 3.0)

The payoff of the gradient view: swap in any loss with a slope and the same loop still works. For yes/no labels with the log loss (primer.ml.losses), is a score in log-odds and the negative gradient is , the label minus the predicted probability ( is the sigmoid, which squashes a score into 0 to 1). Each tree then fits "how surprised were we by each example".

In code: GradientBoosting.negative_gradient returns for loss="squared" and for loss="log".

The update, and the learning rate

prices = [1, 2, 6, 7]
eta = 0.5
# F_0: the average price
F0 = sum(prices) / len(prices)
F0  # → 4.0
residuals = [y - F0 for y in prices]
residuals  # → [-3.0, -2.0, 2.0, 3.0]
# h_1: the stump predicts each side's average residual
small, big = (residuals[0] + residuals[1]) / 2, (residuals[2] + residuals[3]) / 2
h1 = [small, small, big, big]
h1  # → [-2.5, -2.5, 2.5, 2.5]
# F_1 = F_0 + η h_1
F1 = [F0 + eta * h for h in h1]
F1  # → [2.75, 2.75, 5.25, 5.25]
# mean squared error before and after the round
sum((y - F0) ** 2 for y in prices) / 4  # → 6.5
sum((y - f) ** 2 for y, f in zip(prices, F1)) / 4  # → 1.8125

Why not take the whole correction ()? Each tree is fitted to the training data, noise included. Taking the whole step lets the first few trees commit hard to whatever they saw; taking small steps means many trees must agree before the model moves far, which averages away some of the noise. The price is more rounds.

In code: GradientBoosting runs the loop and records the training loss after each round; GradientBoosting.staged_loss scores held-out data after each round; boosting_worked_example is the four-house table; boosting_curves sweeps the learning rate on sine_data.

Why it matters gradient-boosted trees (through libraries such as XGBoost, LightGBM and CatBoost) are the most common winning model on tabular data in practice. They add refinements this lesson leaves out, such as a second-order (Newton) step for each leaf's value, penalties on tree size, fast histogram-based split search, and native handling of missing values, but the loop is the one above. The two knobs that matter most are the ones you have met: tree depth and the learning rate, with the number of rounds chosen by early stopping.

Everyday picture A spreadsheet and a photograph are both grids of numbers, but they carry meaning differently. In a spreadsheet each column means something on its own: "income is under 30,000" is a sentence a loan officer would write. In a photo, "pixel (212, 40) is brighter than 0.7" means nothing; the meaning is in how thousands of pixels are arranged. A tree asks questions of one column at a time, which is perfect for the spreadsheet and hopeless for the photo. A neural network builds its own features out of combinations of inputs, which is what the photo needs.

Tiny example A toy loan table: 800 training rows and 400 validation rows, five columns in their natural units: age in years, income in dollars (spanning a factor of 100), a count of late payments, a region code 0 to 5 (where region 4 is not "twice region 2"), and one column of pure random noise. The label follows rules of the kind a lender writes (four or more late payments; under 30,000 and under 30 years old; two late payments in certain regions or on a very low income), with 5% of labels flipped at random.

flowchart TD
  START{"what does one input look like?"} -->|"a row of a table:<br/>each column means<br/>something alone"| SIZE{"how much data?"}
  START -->|"pixels, audio samples,<br/>words, sequences"| NN["neural network<br/>(often a pretrained one)"]
  SIZE -->|"thousands to millions of rows"| GBT["gradient-boosted trees<br/>or a random forest first"]
  SIZE -->|"huge, or mixed with<br/>text or images"| MIX["neural network, or trees<br/>on top of neural embeddings"]
  GBT --> CHECK["compare against a neural net<br/>only if the gap matters"]

Why trees fit tables so well, each point visible in this lesson's code:

• Units don't matter. A tree only asks "is this bigger than that?", so any order-keeping change to a column (dollars to thousands, a logarithm, a square) leaves every prediction unchanged. A neural net multiplies and adds columns, so their scales collide.
• Thresholds are native. Rules like "four or more late payments" are one question to a tree; a net must approximate the sharp edge with smooth curves.
• Irrelevant columns are mostly ignored, because a column that never wins a split is never used.
• Modest data is enough. A few hundred rows can grow a useful tree; a net with thousands of weights needs far more to pin them down.

Where neural networks win, and trees cannot follow:

• Perceptual and sequential data: images, audio, text. The useful features are built from arrangements of raw values, which is what convolutions (primer.ml.cnn_rnn) and attention (primer.ml.transformer) learn.
• Huge data and pretraining. A net's capacity keeps paying off as data grows, and a pretrained model brings knowledge from billions of examples. A tree starts from nothing every time.
• Smooth trends and extrapolation. A tree's leaves hold averages of training values, so it can never predict outside the range it saw. The four-house model predicts the same price for a house of size 40 as for size 4.
• End-to-end training with other neural parts, since a tree has no gradient to pass along.

In a careful benchmark on 45 tabular datasets of about 10,000 rows each (Grinsztajn, Oyallon and Varoquaux, 2022), tuned tree-based models remained ahead of tuned deep learning models. Their analysis names three reasons that match this lesson: trees shrug off uninformative columns, they respect each column's own axis, and they fit irregular, step-like functions easily. Research on neural networks for tables is active and the gap may narrow; the practical rule is to start with boosted trees on a table and make any other model beat them on your validation data.

In code: make_tabular builds the loan table; tabular_showdown trains every model in the table above (the net is primer.ml.neural_net.MLP); engineer_features is the hand-made preparation the net needed.

Feature importance, and its limits

Everyday picture After a football season you want to know which players mattered. One way: count how often each player touched the ball in training. Another: bench each player for a real match and see how much the score suffers. The first is quick but credits whoever is busy; the second measures what the team actually depends on.

Trees offer the first kind for free. Impurity importance adds up, for each feature, the impurity its splits removed (weighted by how many examples reached each split), measured on the training data. Permutation importance is the second kind: take held-out data, shuffle one column so it no longer lines up with the labels, and measure how much accuracy drops.

Tiny example The 30-tree forest scores 96.0% on the 400 validation rows. Shuffle the late-payments column and it scores 77.5%: a drop of 18.5 points, so the model leans on that column heavily. Shuffle the noise column and it scores 95.75%, a drop of 0.25 points (one row in 400).

# validation rows answered correctly, out of 400
correct_of_400 = {"intact": 384, "late_payments shuffled": 310, "noise shuffled": 383}
acc = {k: v / 400 for k, v in correct_of_400.items()}
# I_j = acc(X_val) - acc(X_val with column j shuffled)
round(acc["intact"] - acc["late_payments shuffled"], 4)  # → 0.185
round(acc["intact"] - acc["noise shuffled"], 4)  # → 0.0025

The limits worth remembering:

• Impurity importance favours columns with many distinct values (continuous numbers, IDs), since they offer more thresholds to overfit with. Measure on held-out data instead.
• Correlated columns split the credit. If income appears twice (in dollars and in thousands), each copy looks half as important, and shuffling one does little because the other covers for it.
• Importance is not cause. It says what this model relies on to predict, not what would change the outcome in the world.

A single shallow tree is the one truly readable model here: print DecisionTree.rules and you are reading the entire model. A forest of hundreds of deep trees is not readable, and importances are a summary of it, not an explanation.

In code: permutation_importance shuffles one column at a time on held-out data; DecisionTree.feature_importances and RandomForest.feature_importances are the impurity kind.

Answer each one out loud or on paper before you open it. If you can explain it, you know it.