Intuition The core idea in one breathA decision tree, left unchecked, will keep splitting until every leaf is pure — it memorizes the training data (including its noise). Pruning is the act of cutting back an over-grown tree so it captures the real signal, not the noise. WHY do we care? Because a smaller, simpler tree usually generalizes better to unseen data (bias–variance tradeoff).
Pruning = removing subtrees (or preventing them from forming) to reduce a decision tree's complexity, trading a small increase in training error for a (hopefully larger) decrease in test error .
Two families:
Pre-pruning (early stopping): stop growing before the tree is fully built (e.g. max_depth, min_samples_leaf, minimum impurity decrease).Post-pruning: grow the full tree, then cut branches back afterward (e.g. cost-complexity / reduced-error pruning).
Intuition Why post-pruning is usually preferredPre-pruning is greedy and short-sighted : a split may look useless now , but enable two great splits below it (the XOR problem — the first split alone gives zero information gain). Post-pruning grows everything first, so it can see the whole subtree's value before deciding to keep or cut. HOW: build big, then judge.
This is the algorithm behind CART / scikit-learn's ccp_alpha. Master this and you've got 80% of exam/interview value.
WHAT do we want? A tree that is accurate and small. Let's put both wishes in one objective.
Let T T T T ~ \tilde{T} T ~
R ( T ) R(T) R ( T ) ∑ t ∈ T ~ R ( t ) \sum_{t \in \tilde{T}} R(t) ∑ t ∈ T ~ R ( t ) R ( t ) R(t) R ( t ) t t t ∣ T ~ ∣ |\tilde{T}| ∣ T ~ ∣
We penalize complexity with a knob α ≥ 0 \alpha \ge 0 α ≥ 0
α = 0 \alpha = 0 α = 0 full tree.α → ∞ \alpha \to \infty α → ∞ root (single node).
So sweeping α \alpha α 0 → ∞ 0 \to \infty 0 → ∞
Take an internal node t t t T t T_t T t
Option A — keep the subtree T t T_t T t cost = R ( T t ) + α ∣ T t ~ ∣ = R(T_t) + \alpha|\tilde{T_t}| = R ( T t ) + α ∣ T t ~ ∣ Option B — prune it to a single leaf t t t cost = R ( t ) + α ⋅ 1 = R(t) + \alpha\cdot 1 = R ( t ) + α ⋅ 1
We should prune when B is no worse than A:
R ( t ) + α ≤ R ( T t ) + α ∣ T t ~ ∣ R(t) + \alpha \le R(T_t) + \alpha|\tilde{T_t}| R ( t ) + α ≤ R ( T t ) + α ∣ T t ~ ∣
Solve for α \alpha α α ( 1 − ∣ T t ~ ∣ ) ≤ R ( T t ) − R ( t ) \alpha\big(1 - |\tilde{T_t}|\big) \le R(T_t) - R(t) α ( 1 − ∣ T t ~ ∣ ) ≤ R ( T t ) − R ( t ) ∣ T t ~ ∣ ≥ 1 |\tilde{T_t}| \ge 1 ∣ T t ~ ∣ ≥ 1 ∣ T ~ t ∣ > 1 |\tilde T_t|>1 ∣ T ~ t ∣ > 1 α ≥ R ( t ) − R ( T t ) ∣ T t ~ ∣ − 1 \alpha \ge \frac{R(t) - R(T_t)}{|\tilde{T_t}| - 1} α ≥ ∣ T t ~ ∣ − 1 R ( t ) − R ( T t )
WHY numerator R ( t ) − R ( T t ) R(t)-R(T_t) R ( t ) − R ( T t ) It's the error you gain by collapsing (the subtree was more accurate, so R ( t ) ≥ R ( T t ) R(t)\ge R(T_t) R ( t ) ≥ R ( T t ) ≥ 0 \ge 0 ≥ 0 WHY divide by ∣ T ~ t ∣ − 1 |\tilde T_t|-1 ∣ T ~ t ∣ − 1 You're spreading that error-cost over the number of leaves you remove . It's "extra error per leaf saved " — a fair per-unit price.
Grow the full tree T 0 T_0 T 0
For every internal node compute α eff \alpha_{\text{eff}} α eff
Prune the node with the smallest α eff \alpha_{\text{eff}} α eff α \alpha α
Repeat until only the root remains.
You now have a nested sequence T 0 ⊃ T 1 ⊃ ⋯ ⊃ { root } T_0 \supset T_1 \supset \dots \supset \{\text{root}\} T 0 ⊃ T 1 ⊃ ⋯ ⊃ { root } α 1 < α 2 < … \alpha_1 < \alpha_2 < \dots α 1 < α 2 < …
Pick the best α \alpha α (the tree with lowest CV error).
Definition Reduced-Error Pruning (REP)Using a separate validation set : for each internal node (bottom-up), tentatively replace its subtree with a leaf (majority class). If validation accuracy does not decrease , keep the pruned version. Repeat until no beneficial pruning remains.
WHY it works: the validation set is not what the tree memorized, so a subtree that only helped on training will hurt (or not help) on validation → safe to cut.
Knob
Meaning
Effect
max_depthmax levels
shallower tree
min_samples_splitmin samples to split a node
fewer splits
min_samples_leafmin samples per leaf
smoother leaves
min_impurity_decreaserequired impurity drop to split
blocks weak splits
ccp_alphacost-complexity α \alpha α
post-pruning
Worked example Example 1 — computingα eff \alpha_{\text{eff}} α eff t t t T t T_t T t 3 leaves . Misclassification errors (as fraction of total samples): leaf-level errors sum to R ( T t ) = 0.02 R(T_t) = 0.02 R ( T t ) = 0.02 t t t R ( t ) = 0.08 R(t) = 0.08 R ( t ) = 0.08
α eff ( t ) = R ( t ) − R ( T t ) ∣ T t ~ ∣ − 1 = 0.08 − 0.02 3 − 1 = 0.06 2 = 0.03 \alpha_{\text{eff}}(t) = \frac{R(t) - R(T_t)}{|\tilde{T_t}| - 1} = \frac{0.08 - 0.02}{3 - 1} = \frac{0.06}{2} = 0.03 α eff ( t ) = ∣ T t ~ ∣ − 1 R ( t ) − R ( T t ) = 3 − 1 0.08 − 0.02 = 2 0.06 = 0.03
Why this step? We computed the "price per leaf saved." Interpretation: only once α ≥ 0.03 \alpha \ge 0.03 α ≥ 0.03 α eff = 0.01 \alpha_{\text{eff}} = 0.01 α eff = 0.01 that one is the weaker link and gets pruned first.
Worked example Example 2 — deciding whether to keep a splitFull tree T T T R ( T ) = 0.05 R(T) = 0.05 R ( T ) = 0.05 ∣ T ~ ∣ = 10 |\tilde T| = 10 ∣ T ~ ∣ = 10 T ′ T' T ′ R ( T ′ ) = 0.07 R(T')=0.07 R ( T ′ ) = 0.07 ∣ T ~ ′ ∣ = 4 |\tilde T'| = 4 ∣ T ~ ′ ∣ = 4 α = 0.01 \alpha = 0.01 α = 0.01
R α ( T ) = 0.05 + 0.01 ( 10 ) = 0.15 R_\alpha(T) = 0.05 + 0.01(10) = 0.15 R α ( T ) = 0.05 + 0.01 ( 10 ) = 0.15 R α ( T ′ ) = 0.07 + 0.01 ( 4 ) = 0.11 R_\alpha(T') = 0.07 + 0.01(4) = 0.11 R α ( T ′ ) = 0.07 + 0.01 ( 4 ) = 0.11
Since 0.11 < 0.15 0.11 < 0.15 0.11 < 0.15 prune to T ′ T' T ′ Why? We accepted 2% more training error to shed 6 leaves — at this α \alpha α α = 0.001 \alpha = 0.001 α = 0.001 R α ( T ) = 0.06 R_\alpha(T)=0.06 R α ( T ) = 0.06 R α ( T ′ ) = 0.074 R_\alpha(T')=0.074 R α ( T ′ ) = 0.074 α \alpha α
Worked example Example 3 — REP by handA node's subtree gets 86% validation accuracy; replacing it with a majority-class leaf gets 86% too. Prune (no loss, simpler is better — Occam). If the leaf gave 80% , we'd keep the subtree.
α \alpha α Why it feels right: bigger numbers often mean "more." Reality: α \alpha α penalty on size , so bigger α \alpha α smaller tree. Fix: remember α = 0 \alpha=0 α = 0 α = ∞ \alpha=\infty α = ∞
Common mistake "Pre-pruning is always fine, why bother growing a huge tree first?"Why it feels right: stopping early saves compute and seems to avoid overfitting directly. Reality: greedy early stopping misses splits that only pay off deeper (horizon effect / XOR). Fix: prefer post-pruning (or at least tune it with CV) when accuracy matters.
Common mistake "Prune using the training set."Why it feels right: it's the data you have. Reality: training error always drops with more splits, so it never tells you to prune. Fix: use a validation set (REP) or cross-validation (to select α \alpha α
Common mistake "Pruning always reduces test error."Why it feels right: simpler = better generalization, usually. Reality: over-pruning raises bias and can underfit. Fix: the CV curve is U-shaped in α \alpha α α \alpha α
Recall Feynman: explain to a 12-year-oldImagine you drew a family tree of "yes/no" questions to guess an animal. If you keep asking questions, eventually every animal gets its own tiny box — but some questions are silly ("does its name have 7 letters?") and only work for the animals you already saw. Pruning is snipping off those silly branches so the tree stays smart about new animals it hasn't met. We test each branch: "if I cut you, do I still guess well on animals I hid earlier?" If yes → snip! Simpler tree, still smart.
Mnemonic Remember the two families & the knob"PRE stops, POST chops." And for cost-complexity: "Big α, small tree" (α is the tax on leaves — high tax, few leaves survive). Weakest link = smallest α_eff gets guillotined first .
What are the two families of tree pruning? Pre-pruning (early stopping while growing) and post-pruning (grow full, then cut back).
Write the cost-complexity objective. R α ( T ) = R ( T ) + α ∣ T ~ ∣ R_\alpha(T) = R(T) + \alpha|\tilde T| R α ( T ) = R ( T ) + α ∣ T ~ ∣ , error plus a penalty
α \alpha α times number of leaves.
What tree do you get at α = 0 \alpha=0 α = 0 α → ∞ \alpha\to\infty α → ∞ α = 0 \alpha=0 α = 0 → full unpruned tree;
α → ∞ \alpha\to\infty α → ∞ → just the root node.
Formula for a node's effective alpha. α eff ( t ) = R ( t ) − R ( T t ) ∣ T ~ t ∣ − 1 \alpha_{\text{eff}}(t) = \dfrac{R(t)-R(T_t)}{|\tilde T_t|-1} α eff ( t ) = ∣ T ~ t ∣ − 1 R ( t ) − R ( T t ) .
In weakest-link pruning, which node is pruned first? The internal node with the
smallest α eff \alpha_{\text{eff}} α eff (cheapest error-per-leaf-saved).
Why is post-pruning generally better than pre-pruning? Pre-pruning is greedy/short-sighted (horizon effect); post-pruning sees the whole subtree's value before cutting (handles XOR-like splits).
How do you choose the best α \alpha α By cross-validation (or a validation set) — pick the
α \alpha α minimizing CV error, not training error.
What is Reduced-Error Pruning? Bottom-up, replace each subtree with a majority-class leaf; keep the replacement if validation accuracy doesn't drop.
Why can't you use training error to decide pruning? Training error monotonically decreases with more splits, so it never signals to prune — you need held-out data.
Name three pre-pruning hyperparameters. max_depth, min_samples_leaf, min_impurity_decrease (also min_samples_split, ccp_alpha).
Effect of increasing α \alpha α Larger
α \alpha α → smaller tree (heavier penalty on leaves).
Danger of over-pruning? Underfitting — bias rises, both training and test error can worsen.
Pre-pruning early stopping
R_alpha = R T + alpha leaves
alpha = R t - R Tt over leaves - 1
Intuition Hinglish mein samjhoDekho, decision tree ka ek problem hai: agar usko roko mat, toh woh training data ko poora ratta maar leta hai — har chhota noise ke liye alag branch bana deta hai. Isse training pe accuracy 100% lagti hai, par naye (test) data pe woh flop ho jaata hai. Isko overfitting kehte hain. Pruning ka matlab hai — is over-grown tree ki extra branches ko kaat dena, taaki tree simple rahe aur naye data pe achha generalize kare.
Do tarike hain. Pre-pruning (early stopping): tree banate waqt hi rok do — jaise max_depth set kar do ya bolo "kam se kam itne samples ho tab hi split karo". Post-pruning : pehle poora bada tree banao, phir baad mein kaat-chhaant karo. Post-pruning zyada acha hai kyunki kabhi-kabhi ek split abhi bekaar lagta hai par uske neeche ke splits bahut valuable hote hain (XOR wala case) — pre-pruning yeh miss kar deta hai.
Sabse important formula: R α ( T ) = R ( T ) + α ∣ T ~ ∣ R_\alpha(T) = R(T) + \alpha|\tilde T| R α ( T ) = R ( T ) + α ∣ T ~ ∣ R ( T ) R(T) R ( T ) ∣ T ~ ∣ |\tilde T| ∣ T ~ ∣ α \alpha α Yaad rakho: bada α \alpha α Har node ka ek α eff = R ( t ) − R ( T t ) ∣ T ~ t ∣ − 1 \alpha_{\text{eff}} = \frac{R(t)-R(T_t)}{|\tilde T_t|-1} α eff = ∣ T ~ t ∣ − 1 R ( t ) − R ( T t ) α \alpha α cross-validation se choose karo, training error se kabhi nahi — kyunki training error toh hamesha ghatta hi rehta hai jitne zyada split karo.
