Home / Learn / Data & AI / ML foundations / Lesson 5.5
All lessons

Module 5: Decision trees · Lesson 5.5 · about 20 min

Deep trees overfit: depth limits and pruning

Left alone, a tree splits until every leaf is pure and memorises the noise. Limit its depth, set a smallest leaf size, or grow it fully and prune it back. Find the best depth on the two-moons data.

Key points, meanings and formulas on one page: choose "Save as PDF" in the print box.

Module 5 · about 20 minutes · read first: 3.7, 5.3. You’ll be able to spot an overfitted tree, choose its depth and leaf size, and explain how pruning works.

A tree left alone keeps asking questions until it has memorised every training row, noise and all; limits and pruning keep only the questions that pay for themselves.

1. Why this matters

A single decision tree is the textbook example of a model that overfits easily. Every tree library has the same few settings to stop it (max_depth, min_samples_leaf, ccp_alpha), and knowing what they do is half of tuning trees. The other half, averaging many trees, is Module 6.

2. Why deep trees overfit

A tree can always keep splitting until each leaf holds one class, or one row. Then it gets every training row right, including the noisy ones: a box drawn round a single mislabelled point. It is like a student who memorises last year’s exam answers, typos included. On new data those little boxes are wrong more often than right.

Try it: how deep should the tree grow?
leaves
training accuracy
test accuracy
A deep tree keeps splitting until every box is pure, drawing little boxes round single noisy points: 100 % on training data, worse on new data. Two dials stop it: a maximum depth, and a smallest number of rows allowed in a leaf. Raise the smallest leaf to 10 or so and even a deep tree stays sensible. Training accuracy (dashed) always rises with depth; test accuracy (solid) tells the truth.

Watch the lower chart: training accuracy only climbs with depth; test accuracy climbs, levels off, then sags. That is the overfitting curve of Lesson 3.7 again, with depth as the flexibility dial.

3. Three ways to stop it

  • Maximum depth. No path may ask more than d questions. Simple and common; depths of 3 to 10 are typical for a single tree.
  • Smallest leaf (or smallest box to split). A leaf must hold at least m rows, so no box can be drawn round one point. Often the most effective single setting.
  • Pruning. Grow the full tree, then cut back branches whose splits don’t earn their keep, like a gardener trimming a hedge. Because it looks at the whole tree before deciding, it can keep a weak split that leads to a strong one below, which an early stop would miss.

Choose each setting with a validation set or cross-validation (Lessons 7.2 and 7.3), never with the test set.

4. Pruning by cost

Cost-complexity pruning gives every leaf a price, α (alpha). The tree’s “cost” is its training error plus α for each leaf it keeps. A branch survives only if the error it saves is worth more than the leaves it uses.

A branch with 3 leaves. With it, the tree's training error is 0.10.

Collapse it into 1 leaf. The training error rises to 0.13: a rise of 0.03. But the tree saves 2 leaves.

Compare costs. Keeping costs 0.10 + 3α. Collapsing costs 0.13 + α. Collapsing is cheaper when 2α > 0.03.

The break-even price. α > 0.015: above that price per leaf, the branch is cut.

Turn the dial. As α rises from 0, weak branches go first, then stronger ones, until only the root is left. Cross-validation picks the α whose tree does best on unseen data.

error(T)
How often tree T is wrong on the training data (or its squared error, for numbers).
|T|
The number of leaves in tree T: a measure of how complicated it is.
α
The price charged per leaf. 0 keeps the full tree; a large α leaves only the root.
Physical meaning
Editing an essay. Write it all, then cut every sentence that doesn't pay for the space it takes. α is how strict the editor is.

“100 % training accuracy shows the tree has learned the data perfectly.” For a tree it shows almost nothing. Any tree with no limits can reach 100 % by memorising, noise included. Only the score on data the tree has never seen tells you whether it has learned something that carries over.

Maths and principle

Principle: prefer the smallest tree that fits nearly as well as a big one (Occam’s razor, as a penalty).

Cost-complexity pruning (used by CART and scikit-learn): for a penalty α≥0 per leaf, choose the subtree T that minimises

Cα(T)=error(T)+α|T|

where |T| is the number of leaves and error is the training misclassification rate (or squared error). At α=0 the full tree wins; as α grows, branches are cut one by one until only the root is left. Each α gives one tree; cross-validation picks α.

When is a branch worth keeping? Collapsing a branch with L leaves into one leaf raises the error by Δ and saves L−1 leaves. It is pruned once α>Δ/(L−1).

Try it: a branch has 3 leaves; collapsing it to one leaf raises training error from 0.10 to 0.13. For which α is it pruned? (Δ=0.03, saving 2 leaves: pruned when α>0.015.)

5. Worked example

Made-up numbers. A churn tree, scored by 5-fold cross-validation:

max depth leaves training accuracy cross-validated accuracy
2 4 78 % 77 %
4 15 86 % 84 %
6 41 92 % 83 %
none 212 100 % 76 %

Depth 4 has the best cross-validated score. Depth 6 is about as good on validation but needs 41 leaves to say it; with “the simplest model within a whisker of the best”, choose depth 4. The unlimited tree is the worst of all on new data, despite its perfect training score.

6. Practice

  1. In the simulation, set depth 14 and smallest leaf 1, then raise the smallest leaf to 15. What happens to training and test accuracy?
  2. Why might pruning beat a depth limit?
  3. Why is “training accuracy 100 %” a warning, not a boast, for a tree?
Answers
  1. Training accuracy falls (no more boxes round single points) while test accuracy holds or rises: less overfitting.
  2. A depth limit stops every branch at the same depth. Pruning looks at the finished tree, keeps deep branches where they help and cuts shallow ones where they don’t.
  3. Any unlimited tree can reach it by memorising, noise included; it says nothing about new data.
  • Unlimited trees memorise noise: perfect on training data, worse on new data.
  • Maximum depth and smallest leaf size stop the tree early; pruning cuts it back after growing.
  • Cost-complexity pruning charges α per leaf; a branch is cut when α is more than its error saving per leaf saved.
  • Choose depth, leaf size or α by cross-validation, never on the test set.

Try it on your own data: the small model trainer has a maximum depth and a smallest leaf setting; watch training and test accuracy as you change them.

New words: maximum depth, minimum leaf size, pre-pruning (early stopping), post-pruning, cost-complexity pruning.

Check yourself

1A tree grown with no limits scores 100 % on training data and 81 % on test data. What happened?
2Raising the "smallest leaf" setting from 1 to 20 rows makes the tree:
3Cost-complexity pruning picks the subtree that minimises:

Sources

Your ticks stay in this browser. Save them as a file on the course home.

Updated 2026-11-22. Numbers in the examples are made up to show the idea unless a source is given. Simulations run in your browser; nothing you type is sent anywhere.