Overfitting in decision trees: Question bank — AI-ML deep dive

This page is the concept-trap companion to Overfitting in decision trees. It touches Bias-Variance Tradeoff, Cross-Validation, Random Forests, Regularization, and Gini Impurity and Entropy — link back whenever a term feels shaky.

Definition Symbols used in the pruning items

Several traps below reference cost-complexity (post-)pruning. So no symbol is unearned, here is the whole vocabulary in plain words, matching the parent note:

Impurity — a number saying how "mixed" the labels in a node are (e.g. Gini or entropy); $0$ means a pure node (one class only).
$R (T)$ — the tree's total training error: the impurity/misclassification summed over its leaves. Lower = fits the training data better.
$T_{t}$ — the subtree rooted at node $t$ : node $t$ together with everything hanging below it.
$R (T_{t})$ — the training error of that subtree (of the leaves inside $T_{t}$ ).
$R (t)$ — the training error if we ==collapse $T_{t}$ into the single leaf $t$ == (throw the branches away).
$\tilde{T}_{t}$ — the set of leaves of $T_{t}$ ; the tilde marks "leaves only," and $∣ \tilde{T}_{t} ∣$ is how many leaves it has.
$α \geq 0$ — the complexity penalty per leaf: a knob that charges the tree for every leaf it keeps. Big $α$ = "leaves are expensive, stay small"; $α = 0$ = "leaves are free, grow fully." Its tie-point value for node $t$ is $α = \frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}$ , the smallest penalty at which pruning $T_{t}$ is justified.

True or false — justify

A tree with zero training error has learned the true pattern perfectly.

False — zero training error usually means it memorized the noise; each leaf may hold a single point, so it fits the exact wobble of the sample, not the underlying rule.

A deep decision tree has high bias.

False — a deep tree has low bias, high variance; it can bend to almost any training set, so its problem is instability across datasets, not systematic error.

Every split in a greedy tree lowers the node impurity it optimizes (Gini or entropy).

True — a split is chosen to maximize impurity decrease, and it can only lower that impurity or leave it unchanged (never raise it), which is why pure greed always votes to split more and nothing internal stops the growth.

Overfitting shows up as training error rising.

False — training error keeps falling toward zero; it is the validation error that turns U-shaped and rises. Watching training error alone hides overfitting entirely.

If train and validation accuracy are both 99%, the model is overfitting.

False — overfitting is diagnosed by the gap, not the height; a small train–val gap means it generalizes well regardless of how high the numbers are.

Pruning always improves test accuracy.

False — pruning trades variance for bias; over-pruning underfits and can hurt test accuracy. The right amount is chosen by cross-validation, not assumed.

Increasing

α

in cost-complexity pruning makes the tree larger.

False — larger

α

penalizes each leaf more, so more branches get pruned and the tree shrinks (more bias, less variance).

Random forests overfit less because each individual tree is shallow.

False — each forest tree is grown deep (low bias, high variance); the overfitting is killed by averaging many de-correlated trees, not by keeping any one small.

Setting min_samples_leaf = 1 is a good default for avoiding overfitting.

False — it imposes no restriction at all, permitting single-point leaves (maximal memorization); a safe default forces each leaf to hold several points so leaves are statistically meaningful.

A tree that overfits will always beat a pruned tree on the training set.

True — the overfit tree fits training noise as signal, so its training score is at least as high; this is exactly why the training score is a misleading model-selection criterion.

Spot the error

"To avoid overfitting, just set max_depth = 2 for every problem."

The error is treating a fixed tiny cap as universal — it causes underfitting on complex patterns; the right depth is problem-specific and found by cross-validation.

"Pre-pruning is strictly better than post-pruning because it saves computation."

The error is ignoring myopia — pre-pruning is greedy and short-sighted, it may reject a low-gain split that would unlock two great splits below it (the XOR case), so it can underfit where post-pruning succeeds.

"The effective-

α

denominator should be

∣ \tilde{T}_{t} ∣

, the number of leaves in the subtree."

The error is off-by-the-collapse: pruning removes

∣ \tilde{T}_{t} ∣

leaves but adds one back (the collapsed node

t

), so the net leaf drop is

∣ \tilde{T}_{t} ∣ - 1

, which must be the denominator.

"Since overfitting is a variance problem, boosting weak trees is the natural fix."

The error is mixing goals — boosting mainly reduces bias and can even overfit; the variance-reducing ensemble is bagging / random forests, which averages independent trees.

"A large train–validation gap proves the model is too simple."

The error is reversing the sign — a large gap (high train, low val) is the signature of overfitting (too complex), not underfitting; underfitting shows both scores low and close.

"Cost-complexity pruning picks the tree with the lowest

R_{α} (T)

on the training set."

The error is trusting training cost — the nested pruned sequence is generated by

R_{α}

, but the final tree is chosen by cross-validation score, not by minimizing training cost.

Why questions

Why does a tiny change in the data sometimes rewrite the whole tree?

Because splits are chosen greedily top-down; flipping the top split changes every subtree beneath it, which is exactly what "high variance" means for trees.

Why does post-pruning avoid the myopia that pre-pruning suffers?

It grows the full tree first, so it can judge an entire subtree's real value before cutting, rather than blocking a split based only on its immediate (possibly misleading) gain.

Why is

α

interpreted as "error increase per leaf removed"?

Because

α = \frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}

is the extra training error divided by the leaves you save; you prune first where this ratio is smallest — least accuracy lost per unit of simplicity.

Why do axis-aligned splits give trees such high capacity?

Each cut can isolate a region on one feature; with enough cuts a tree can carve out a box around every single point, driving training error to zero.

Why does averaging many trees cut variance roughly by

1/ n

Averaging

n

roughly-independent estimators shrinks their variance by about

1/ n

; random feature subsets de-correlate the trees so this near-independence approximately holds.

Why does cross-validation, not a single split, guide the

α

choice?

A single validation split is itself noisy; averaging error over folds gives a stabler estimate of generalization, so the chosen

α

is less accidental.

Edge cases

If a node is already pure, what does its best split gain?

Zero — a pure node has zero impurity, so no split can lower it further and the tree stops there naturally.

Two identical feature rows carry opposite labels. Can the tree separate them?

No — no axis-aligned cut distinguishes identical points, so that leaf stays impure; this is irreducible noise (

σ^{2}

) the tree cannot and should not fit.

What happens to cost-complexity pruning when

α = 0

With no leaf penalty the full unpruned tree wins, since it has the lowest training error;

α = 0

recovers the original overfit tree.

What happens as

α \to \infty

The leaf penalty dominates everything, so pruning collapses the tree to a single root leaf, the maximum-bias / minimum-variance extreme.

On pure XOR data, why does the first split show near-zero impurity gain?

Because the label depends on the combination of both features; splitting on one alone leaves each side still 50/50, so the useful structure appears only after the second split — the trap pre-pruning falls into.

If validation error keeps dropping and never turns up as depth grows, what does that mean?

The tree hasn't reached its overfitting regime yet; the data may need deeper trees, or is clean enough that added splits still capture signal — you simply keep the deepest tried.

Recall One-line self-test

Cover every answer above and re-derive the reason, not the verdict — the verdict is worthless without it. ::: If you can state why for each, you own the topic; if you only recall true/false, revisit Overfitting in decision trees.

Connections

Overfitting in decision trees — parent topic these traps drill.
Bias-Variance Tradeoff — the frame for "gap = variance."
Cross-Validation — how $α$ and depth are actually chosen.
Random Forests — the variance-averaging fix.