Foundations — Tree pruning techniques

This page assumes nothing. Before you touch cost-complexity pruning on the parent note, you need to genuinely see what a tree, a leaf, an error, and a penalty knob are. We build each symbol from a picture, in an order where every piece rests on the one before it.

0. The picture everything lives in: a decision tree

Every symbol on the parent page is a label attached to a part of one drawing — a tree of yes/no questions. So let's draw it first and name its parts.

WHY do we care about this vocabulary? Because pruning is literally an operation on this picture: cut the branches under some internal node, and that node becomes a leaf. Everything else is bookkeeping about which node to cut. If trees are new to you, build them first with Decision Trees (CART).

1. A data point and its "true label"

Before a tree can be right or wrong, we need something for it to be right or wrong about.

When a dot slides down and lands in a leaf, the leaf guesses a label. Two things can happen: the guess matches the true label (correct), or it doesn't (a mistake). That mismatch is the seed of error, which we define next.

2. Error at a leaf: $R(t)$

Here is the first real symbol from the parent: $R(t)$.

WHY this exact quantity? Because pruning is a bargain — "cut some branches, pay a little more error." To talk about paying error, we first need a number that measures error. $R(t)$ is that number, per box. (The "impurity" flavour of $R$ — Gini or entropy instead of raw miscount — is exactly Gini Impurity & Entropy; same role, smoother measure.)

3. Counting leaves: $\tilde{T}$ and $|\tilde{T}|$

Two symbols that look scary but mean something you can count on your fingers.

The bars $|\cdot |$ always mean "how many / how big". So $|\tilde{T}|$ is literally: count the bottom boxes.

4. A subtree: $T_t$ and $\widetilde{T_t}$

Pruning doesn't chop the whole tree — it chops one branch's worth. So we need a name for "the piece hanging below one node."

WHY is $R(t)\ge R(T_t)$ (collapsing never lowers training error)? Because the subtree had extra questions to separate the dots; throwing them away can only blur things. So the numerator $R(t)-R(T_t)$ of the effective-alpha formula is always $\ge 0$ — the extra error you accept by cutting. This is why you must never judge pruning on training data (see Cross-Validation): training error alone always votes "keep everything."

5. The penalty knob: $\alpha$

Now the star symbol: $\alpha$ (the Greek letter alpha, just a name for a number you dial).

6. The one inequality you'll see solved

The parent rearranges "prune when B is no worse than A." You just need to be comfortable that manipulating an inequality is like a see-saw: do the same thing to both sides.

One caution the parent flags: we divide by $|\widetilde{T_t}|-1$, so this only makes sense when the subtree has more than one leaf ($|\widetilde{T_t}|\ge 2$). A node whose subtree is already a single leaf isn't an internal node to prune — no division-by-zero ever happens.

How the foundations feed the topic

Each arrow is a "you need this before that." Notice cross-validation sits at the very end: once foundations give us a sequence of trees indexed by $\alpha$, Cross-Validation is how we choose which one generalizes best — and a whole forest of such trees is Random Forests.

Equipment checklist

Cover the right side; say it out loud; then reveal.