Decision tree structure and terminology — Hinglish notes

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

WHAT is a decision tree?

WHY do we care? Kyunki trees hain:

Interpretable — tum decision path ko plain English rules ki tarah padh sakte ho.
Non-parametric — yeh koi assumption nahi karte ki boundary ek seedhi line hai.
Random Forests aur Gradient Boosting ka building block (tabular ML ke workhorses).

The anatomy (terminology)

Figure — Decision tree structure and terminology

Formula Ek leaf kya predict karta hai (derived, dumped nahi)

Ek leaf $ℓ$ ke paas training samples ka ek set $R_{ℓ}$ hai. Hume uss leaf par training loss minimize karne ke liye ek prediction $\overset{y}{^}_{ℓ}$ chunna hoga.

Classification — misclassifications minimize karo $\sum_{i \in R_{ℓ}} 1 [y_{i} \neq = \overset{y}{^}_{ℓ}]$ . Yeh most frequent class (majority vote) chunne se minimize hota hai: $\overset{y}{^}_{ℓ} = ar g max_{c} ∣ {i \in R_{ℓ} : y_{i} = c} ∣$ Kyun? Jo bhi label tum chuno, woh uss label ke na hone wale har sample ke liye "galat" hoga; sabse bada group chunne par sabse kam galat hote hain.

Regression — squared error minimize karo $\sum_{i \in R_{ℓ}} (y_{i} - \overset{y}{^}_{ℓ})^{2}$ . $\overset{y}{^}_{ℓ}$ ke w.r.t. derivative lo aur $0$ set karo:

\;\Rightarrow\; \hat y_\ell = \frac{1}{|R_\ell|}\sum_{i\in R_\ell} y_i$$ Toh ek regression leaf apne samples ka ==mean== predict karta hai.

HOW a tree carves up space

WHY axis-aligned? Ek waqt mein ek feature test karna splits ko search karna sasta rakhta hai (bas har feature sort karo aur thresholds try karo) aur rules ko human-readable bhi rakhta hai.

Worked examples

Steel-manned mistakes

Flashcards

Kaunsa node kisi bhi split se pehle poora dataset rakhta hai?

Root node.

Koi children na hone wala node jo prediction output karta hai usse kya kehte hain?

Ek leaf (terminal) node.

Standard CART internal node kaisa test use karta hai?

Axis-aligned test, "

x_{j} \leq t

?".

Ek classification leaf kya predict karta hai, aur kyun?

Majority class — yeh uss leaf mein misclassified samples ki sankhya minimize karta hai.

Ek regression leaf kya predict karta hai, aur kyun?

Apne samples ka mean — yeh squared error minimize karta hai (

\sum (y_{i} - \overset{y}{^})^{2}

ka derivative 0 set karo).

Tree depth define karo.

Sabse lambe root-to-leaf path par edges ki sankhya.

Ek akele tree ki decision surface "staircase" kyun hoti hai?

Axis-aligned splits space ko rectangles mein partition karte hain; predictions har box mein constant hoti hain → piecewise-constant.

Pruning kya hai aur kyun karte hain?

Overfitting kam karne / model complexity ghatane ke liye subtrees kaat dena.

Branch aur leaf mein kya fark hai?

Branch ek edge hai (test outcome); leaf ek terminal node hai (prediction).

Ek tree bahut deep grow karne par generalization kyun kharaab hoti hai?

Yeh noise memorize karta hai (overfits), toh training error girta hai lekin test error badhta hai.

Recall Feynman: explain to a 12-year-old

Socho ek jaanwar guess karne ka "20 Questions" ka game. Pehla sawaal ("Kya uske fur hai?") root hai. Har jawaab tumhe aur sawaalon wale path par le jaata hai (internal nodes). Jab tum kaafi sure ho jao — "Yeh ek cat hai!" — tum ruk jaate ho; woh ending ek leaf hai. Ek decision tree ek computer hai jo yeh game tumhare data ke saath khelta hai. Agar tum bahut saare chhote-chhote sawaal poochho toh tum flukes ki wajah se "andaza" laganey lagte ho — yahi overfitting hai, toh samajhdaar players jaldi ruk jaate hain (pruning).

Connections

Gini impurity and entropy — kaise har split par sabse achhaa sawaal chuna jaata hai.
CART algorithm — woh greedy recursive procedure jo upar wali structure banata hai.
Overfitting and pruning — depth aur subtree removal control karna.
Random Forests — staircase smooth karne ke liye average kiye gaye kai trees.
Gradient Boosted Trees — ek doosre ki galtiyan sudharne ke liye stack kiye gaye trees.
Bias-variance tradeoff — deep tree = low bias, high variance.