Intuition The ONE core ideaA decision tree learns by chopping your data into smaller and smaller boxes until each box is "pure" — but if you let it chop forever it ends up drawing a tiny box around every single training point, memorizing the random noise instead of the real pattern. Overfitting is exactly that memorization, and this page builds — from zero — every symbol, picture and word you need before you can read the parent note.
Before you can understand why trees overfit or how cost-complexity pruning fixes it, you have to be fluent in the small alphabet of symbols the parent note throws around. We will earn each one: plain words → a picture → why the topic needs it. Nothing is assumed.
Imagine each training example is a dot placed on a graph. Each axis of that graph is one feature (a measurable property — height, temperature, pixel brightness…). We give the features names: call the first axis x 1 x 2 which feature we mean. The whole graph — every possible position a dot could sit — is the feature space . If you have 2 features it's a flat sheet; with 3 it's a room; with more it's a space we can't draw but can still reason about.
Definition Axis-aligned splitA decision tree makes decisions by asking a yes/no question about one feature at a time , e.g. "is the first feature x 1 straight cut parallel to an axis through the feature space, slicing it into two pieces. It can only cut horizontally or vertically — never diagonally. That restriction is what "axis-aligned" means.
Look at the figure: each cut (yellow line) splits one region into two. Stack enough cuts and you carve the plane into little rectangular cells . Each final cell is a leaf of the tree — a box that gives one prediction to everything inside it.
Intuition Why this matters for overfittingBecause the tree can keep adding cuts, it can shrink boxes until each box holds exactly one dot . A box around a single point fits that point perfectly — including if that point was a random fluke. That is the seed of overfitting, and every symbol below measures or controls this shrinking.
x x whole list of feature values bundled together — its coordinates in feature space, written out as ( x 1 , x 2 , … ) x
y y answer we actually recorded for that example: the colour written next to the dot, or a measured number. Crucially, this recorded value can be slightly wrong — sensors wobble, humans mislabel, coin-flips happen.
f ( x ) f ( x ) perfect, noiseless rule that nature would give if there were no measurement wobble — the ideal answer for input x f wish we could learn.
ε y = f ( x ) + ε ε random noise nudge added on top of the true value each time we record a label. The honest model of where our data comes from is
y = f ( x ) + ε , E [ ε ] = 0 , Var ( ε ) = σ 2 . plus a zero-averaged random jiggle whose typical squared size is σ 2 source of the irreducible-noise term in Section 4 — without it, that term would appear out of nowhere.
f ^ ( x ) ^ "estimated / predicted, not the truth." So f ^ ( x ) "f-hat of x" = the tree's prediction for input x — its attempt to recover f ( x ) f ^ ( x ) x
Common mistake Don't confusey f ( x ) f ^ ( x ) f ( x ) y = f ( x ) + ε noisy truth we actually see; f ^ ( x ) f ^ ( x ) y f ( x )
y − f ^ ( x ) residual is observed label minus guess: how far off the prediction is for one point. If the tree nails it, this is 0
Intuition Why square the residual?A residual can be positive (guessed too low) or negative (guessed too high). If we just added residuals up, a + 5 − 5 0 Squaring kills the sign (a square is never negative) and punishes big misses more than small ones. That's why the bias–variance formula uses ( y − f ^ ( x ) ) 2
R ( T ) R ( T ) total error of tree T n ( x i , y i ) i 1 , 2 , … , n Regression: R ( T ) = ∑ i = 1 n ( y i − f ^ ( x i ) ) 2 , Classification: R ( T ) = n 1 ∑ i = 1 n 1 [ y i = f ^ ( x i ) ] . 1 [ ⋅ ] indicator : it equals 1 0 R ( T ) fraction of training points the tree gets wrong (the misclassification rate). Lower R ( T ) T which tree we're measuring.
E [ ⋅ ] E expected value = the average you'd get if you repeated the experiment infinitely many times. E [( y − f ^ ( x ) ) 2 ] "the average squared error you'd suffer over all possible fresh datasets and test points." We need an average because a single dataset is one lucky/unlucky draw; the true quality of a method is its behaviour on average .
This is the heart of why the parent note calls overfitting a "variance problem." Recall from Section 1 the honest data model y = f ( x ) + ε true value f ( x ) ε f ( x ) f ^ ( x )
Definition Bias — the formal statementBias is how far the average prediction sits from the true value:
Bias ( x ) = E [ f ^ ( x )] − f ( x ) . E [ f ^ ( x )] f ( x ) under-fitting .
Definition Variance — the formal statementVariance is how scattered the predictions are around their own average:
Var ( x ) = E [ ( f ^ ( x ) − E [ f ^ ( x )] ) 2 ] . centre of the dart cloud E [ f ^ ( x )] over-fitting .
σ 2 σ ε σ 2 = Var ( ε ) f ^ = f label itself carries the wobble ε
Intuition WHY the three terms add upStart from the total miss y − f ^ ( x ) f ( x ) E [ f ^ ( x )] y − f ^ ( x ) = y − f ( x ) ε + − Bias ( f ( x ) − E [ f ^ ( x )] ) + − scatter ( E [ f ^ ( x )] − f ^ ( x ) ) . ε 0 cross-term vanishes and only the three squared pieces survive:
E [( y − f ^ ( x ) ) 2 ] = Bias ( x ) 2 + Var ( x ) + σ 2 . separate geometric facts about the dart cloud — one is where it sits, the other is how wide it spreads — so they simply add, on top of the label's own noise floor σ 2
Definition Node, internal node, leafA node is any decision point in the tree. An internal node is a node that asks a question and splits — it has children hanging below it (like the yellow cuts in Section 0). A leaf is a node that asks nothing and just predicts — a final box the tree does not split further. Rule of thumb: internal node = a fork in the road; leaf = the destination. Every prediction comes from a leaf.
∣ T ~ ∣ T ~ leaves of tree T ∣ ⋅ ∣ "count how many" — the same bars you'd use for the size of a set. So ∣ T ~ ∣ how many leaf-boxes the tree has . More leaves = more boxes = a more complicated, higher-capacity tree. This count is our stand-in for "complexity."
T t t t T t t prune T t t R ( t ) R ( T t )
α α penalty we charge for each leaf . Setting α α = 0 α ≥ 0
Intuition Reading the trade-off
Big tree: R ( T ) α ∣ T ~ ∣
Tiny tree: α ∣ T ~ ∣ R ( T )
Somewhere in between sits the sweet spot — the same U-shape the parent note draws against depth.
Definition Cross-validation (one line)To choose the best α without peeking at the final test set, we split the training data into chunks, train on some, check on the held-out chunk, and rotate. The α Cross-Validation .
"Purity" is how single-coloured a box is. A leaf with only red dots is pure; a 50/50 mix is maximally impure. Trees split to reduce impurity, measured by Gini or entropy — see Gini Impurity and Entropy . The parent's min_impurity_decrease knob refuses a split that doesn't purify enough.
The roadmap below (also written out in words underneath, in case the diagram does not render) shows how these foundations feed the topic. In words: the geometry — feature space → axis-aligned splits → counting leaves — gives you the notion of tree size. Impurity (Gini/entropy) is what drives the splits. Separately, the observed label y f ^ R ( T ) , then averaging with E , which pins down that overfitting is a high-variance condition. The leaf-count and the error R ( T ) complexity penalty α , which builds the penalized cost R α ; that plus the variance insight plus cross-validation is exactly cost-complexity pruning .
Observed label y vs guess f-hat
Expectation = average over data
Bias Variance Noise split
Overfitting = high Variance
Trace any path and you reach the parent topic: Overfitting in Decision Trees Hinglish version ). Ensembling many trees to kill variance is the road to Random Forests .
Intuition WHY the pruning formula looks like that (before we plug numbers)We compare two costs for a subtree T t α
Keep it: cost = R ( T t ) + α ∣ T ~ t ∣ all its leaves).Prune to one leaf: cost = R ( t ) + α ⋅ 1 one leaf to fine).
Pruning is worthwhile the moment the prune-cost is ≤ R ( t ) + α = R ( T t ) + α ∣ T ~ t ∣ ⟹ α ( ∣ T ~ t ∣ − 1 ) = R ( t ) − R ( T t ) ⟹ α = ∣ T ~ t ∣ − 1 R ( t ) − R ( T t ) . ∣ T ~ t ∣ − 1 removes ∣ T ~ t ∣ 1 , a net loss of ∣ T ~ t ∣ − 1 α per leaf removed " — prune first where that price is smallest.
Common mistake The corner case: anegative break-even α R ( t ) < R ( T t ) lower training error than keeping it. Since α ≥ 0 a subtree whose leaves don't even lower training error should always be kept... or rather, such a subtree would never have been grown by a greedy learner in the first place (every split it makes must not increase error). In practice, growing always gives R ( T t ) ≤ R ( t ) R ( t ) − R ( T t ) ≥ 0 α α
R α α ∣ T ~ t ∣ = 4 R ( T t ) = 0.02 R ( t ) = 0.08 α = ∣ T ~ t ∣ − 1 R ( t ) − R ( T t ) = 4 − 1 0.08 − 0.02 = 3 0.06 = 0.02. R α α = 0.02 0.02 + 0.02 ⋅ 4 = 0.10 0.08 + 0.02 ⋅ 1 = 0.10 0.02 4 − 1 = 3 net leaves removed (lose 4, add 1 back).
Cover the answers and test yourself — you're ready for the parent note when every line is instant.
What does the feature space represent? The graph of all possible input positions; each training example is a dot with coordinates x = ( x 1 , x 2 , … )
What is an axis-aligned split, geometrically? A straight cut parallel to one axis (a yes/no test on a single feature), slicing a region into two rectangular pieces.
What is the difference between an internal node and a leaf? An internal node asks a question and splits (a fork); a leaf asks nothing and just predicts (the destination box).
What is the data model relating y f ( x ) ε y = f ( x ) + ε Var ( ε ) = σ 2
What does the hat in f ^ ( x ) "Estimated / predicted" — the tree's attempt to recover the true f ( x )
What is a residual and why do we square it? y − f ^ ( x )
Write out R ( T ) The misclassification rate n 1 ∑ i 1 [ y i = f ^ ( x i )]
What does E [ ⋅ ] The long-run average over infinitely many random datasets.
State the formal definition of Bias( x ) Bias ( x ) = E [ f ^ ( x )] − f ( x )
State the formal definition of Var( x ) Var ( x ) = E [( f ^ ( x ) − E [ f ^ ( x )] ) 2 ]
What is σ 2 Var ( ε ) y = f ( x ) + ε
What does ∣ T ~ ∣ The number of leaves in tree T
What are T t t R ( T t ) R ( t ) t T t R ( T t ) R ( t )
Where does α = ∣ T ~ t ∣ − 1 R ( t ) − R ( T t ) Setting keep-cost R ( T t ) + α ∣ T ~ t ∣ R ( t ) + α
What if the effective α Then R ( t ) < R ( T t ) α ≥ 0 R ( T t ) ≤ R ( t )
What does α R α ( T ) = R ( T ) + α ∣ T ~ ∣ Charges a penalty per leaf, trading fit against simplicity; bigger α
Why does overfitting count as a variance problem? A deep tree has low bias but its predictions swing wildly with each new dataset — the Var term dominates the error.
