Tree pruning techniques — Hinglish notes

2.3.4 · AI-ML › Tree-Based & Instance Methods

WHAT hai pruning?

Cost-Complexity Pruning (important 20%)

Yeh algorithm CART / scikit-learn ke ccp_alpha ke peeche hai. Ise master kar lo aur tumhare paas exam/interview ki 80% value aa jaayegi.

Criterion ko scratch se derive karna

WHAT chahiye humein? Ek tree jo accurate bhi ho aur chhota bhi. Dono wishes ko ek objective mein daalen.

Maano $T$ ek tree hai jiske terminal nodes (leaves) $\tilde{T}$ hain. Define karo:

$R (T)$ = tree ki total error (ya impurity) = $\sum_{t \in \tilde{T}} R (t)$ , jahan $R (t)$ leaf $t$ par error hai.
$∣ \tilde{T} ∣$ = leaves ki sankhya (hamara complexity measure).

Hum complexity ko ek knob $α \geq 0$ ke saath penalize karte hain:

$α = 0$ : koi penalty nahi → full tree rakho.
$α \to \infty$ : penalty dominant ho jaati hai → root tak collapse ho jaao (single node).

Toh $α$ ko $0 \to \infty$ sweep karne se sabse bade se sabse chhote tak trees ki ek sequence milti hai.

Kya subtree kaatna worth hai? (key derivation)

Ek internal node $t$ aur usmein rooted subtree $T_{t}$ lo. Do options compare karo:

Option A — subtree $T_{t}$ rakho: cost $= R (T_{t}) + α ∣ \tilde{T_{t}} ∣$ . Option B — ise ek single leaf $t$ tak prune karo: cost $= R (t) + α \cdot 1$ .

Hum prune karein jab B, A se bura na ho: $R (t) + α \leq R (T_{t}) + α ∣ \tilde{T_{t}} ∣$

$α$ ke liye solve karo: $α (1 - ∣ \tilde{T_{t}} ∣) \leq R (T_{t}) - R (t)$ Kyunki $∣ \tilde{T_{t}} ∣ \geq 1$ hai, divide karne par kuch khatranaak nahi hota jab $∣ \tilde{T}_{t} ∣ > 1$ : $α \geq \frac{R ( t ) - R ( T _{t} )}{∣ T _{t} ~ ∣ - 1}$

WHY numerator $R (t) - R (T_{t})$ ? Yeh woh error hai jo collapse karne par tum gain karte ho (subtree zyada accurate tha, isliye $R (t) \geq R (T_{t})$ , numerator $\geq 0$ ). WHY $∣ \tilde{T}_{t} ∣ - 1$ se divide karo? Tum us error-cost ko un leaves ki sankhya par spread kar rahe ho jo tum remove karte ho. Yeh "extra error per leaf saved" hai — ek fair per-unit price.

Weakest-link pruning algorithm

Full tree $T_{0}$ grow karo.
Har internal node ke liye $α_{eff}$ compute karo.
Sabse chhote $α_{eff}$ wale node ko prune karo → ek chhota tree milo; woh $α$ record karo.
Tab tak repeat karo jab tak sirf root na bache.
Ab tumhare paas ek nested sequence hai $T_{0} \supset T_{1} \supset \dots \supset {root}$ increasing $α_{1} < α_{2} < \dots$ ke saath.
Best $α$ cross-validation se chunno (sabse kam CV error wala tree).

Reduced-Error Pruning (simpler alternative)

Pre-pruning knobs (scikit-learn)

Knob	Meaning	Effect
`max_depth`	max levels	shallower tree
`min_samples_split`	ek node split karne ke liye min samples	kam splits
`min_samples_leaf`	leaf ke liye min samples	smoother leaves
`min_impurity_decrease`	split karne ke liye required impurity drop	weak splits block karta hai
`ccp_alpha`	cost-complexity $α$	post-pruning

Worked Examples

Common Mistakes (Steel-manned)

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho tumne ek animal guess karne ke liye "haan/na" sawaalon ka ek family tree draw kiya. Agar tum questions poochte raho, eventually har animal ka apna chhota sa box ho jaata hai — lekin kuch questions bekar hote hain ("kya uske naam mein 7 letters hain?") aur sirf unhi animals ke liye kaam karte hain jo tumne pehle se dekhe hain. Pruning un bekar branches ko kaat-chhaantna hai taaki tree naaye animals ke baare mein bhi samajhdaar rahe jinhe usne kabhi nahi dekha. Hum har branch test karte hain: "agar main tumhe kaat doon, kya main unhi animals ko sahi guess kar paunga jo maine pehle chhupaye the?" Agar haan → snip! Simpler tree, phir bhi smart.

Connections

Decision Trees (CART) — pruning CART ka built-in overfitting cure hai.
Bias-Variance Tradeoff — pruning thodi bias ke liye variance trade karta hai.
Cross-Validation — isse hum $α$ choose karte hain.
Random Forests — pruning ka ek alternative: variance kam karne ke liye kai unpruned trees ka average.
Regularization — $α ∣ \tilde{T} ∣$ ek L0-style complexity penalty hai, same spirit as ridge/lasso.
Gini Impurity & Entropy — classification ke liye $R (t)$ define karte hain.

Flashcards

Tree pruning ki do families kya hain?

Pre-pruning (growing karte waqt early stopping) aur post-pruning (poora grow karo, phir kaato).

Cost-complexity objective likho.

R_{α} (T) = R (T) + α ∣ \tilde{T} ∣

, error plus ek penalty

α

times number of leaves.

α = 0

par konsa tree milta hai vs

α \to \infty

par?

α = 0

→ full unpruned tree;

α \to \infty

→ sirf root node.

Node ke effective alpha ka formula.

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

Weakest-link pruning mein konsa node pehle prune hota hai?

Woh internal node jiska sabse chhota

α_{eff}

ho (sabse sasta error-per-leaf-saved).

Post-pruning generally pre-pruning se better kyun hai?

Pre-pruning greedy/short-sighted hai (horizon effect); post-pruning kaatne se pehle poore subtree ki value dekhta hai (XOR-like splits handle karta hai).

Best

α

kaise choose karte hain?

Cross-validation se (ya validation set se) — woh

α

chuno jo CV error minimize kare, training error nahi.

Reduced-Error Pruning kya hai?

Bottom-up, har subtree ko majority-class leaf se replace karo; agar validation accuracy na gire toh replacement rakho.

Pruning decide karne ke liye training error kyun use nahi kar sakte?

Training error zyada splits ke saath monotonically decrease hoti hai, isliye yeh kabhi prune karne ka signal nahi deti — tumhe held-out data chahiye.

Teen pre-pruning hyperparameters batao.

max_depth, min_samples_leaf, min_impurity_decrease (aur bhi: min_samples_split, ccp_alpha).

α

badhane ka tree size par kya asar hota hai?

Bada

α

→ chhota tree (leaves par bhaari penalty).

Over-pruning ka khatraa kya hai?

Underfitting — bias badhta hai, training aur test error dono kharab ho sakte hain.