Random forest algorithm — Hinglish notes

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

Random Forest KYA hota hai?

Randomness ke do sources (rows + features) hi poora trick hai. Yeh trees ko apni errors mein disagree karate hain taaki averaging help kare.

Averaging kyun help karta hai? (First principles se derive karo)

Maano humare paas $B$ trees hain, har ek ek prediction produce karta hai jo variance $σ^{2}$ ke saath ek random variable hai. $ρ$ do trees ki predictions ke beech average pairwise correlation ho. Average $\overset{ˉ}{f} = \frac{1}{B} \sum_{b = 1}^{B} f_{b}$ ka variance kya hai?

Step 1 — sum ka variance. Kisi bhi random variables ke liye, $Var (\sum_{b} f_{b}) = \sum_{b} Var (f_{b}) + \sum_{i \neq = j} Cov (f_{i}, f_{j}) .$ Yeh step kyun? Sum ka variance individual variances mein plus har covariance pair mein split hota hai — yeh sum par apply ki gayi variance ki definition hai.

Step 2 — identical variances aur correlations plug karo. $B$ diagonal terms hain har ek $σ^{2}$ , aur $B (B - 1)$ off-diagonal terms hain har ek $Cov = ρ σ^{2}$ : $Var (\sum_{b} f_{b}) = B σ^{2} + B (B - 1) ρ σ^{2} .$

Step 3 — $B^{2}$ se divide karo (kyunki $\overset{ˉ}{f} = \frac{1}{B} \sum f_{b}$ , aur $Var (a X) = a^{2} Var (X)$ ): $Var (\overset{ˉ}{f}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$

Ise kaise build karte hain (algorithm)

Worked example Random Forest training loop

Data ${(x_{i}, y_{i})}_{i = 1}^{n}$ , $p$ features, $B$ trees diya hua hai:

for b = 1 ... B:
    1. Draw a bootstrap sample D_b of size n (rows sampled WITH replacement)
    2. Grow a tree T_b on D_b:
         at each node:
           - pick m of the p features at random
           - choose the best split only among those m
         grow FULLY (no/low pruning)
Predict:
    classification -> majority vote of {T_b(x)}
    regression     -> average of {T_b(x)}

Typical $m = p$ (classification) ya $m = p /3$ (regression). Yeh step kyun? Chhota $m$ ⇒ trees alag-alag features par majboor ⇒ lower $ρ$ ; lekin bahut chhota ⇒ har tree bahut weak. $p$ empirical sweet spot hai.
Trees deep aur unpruned grow kiye jaate hain. Kyun? Hum chahte hain high-variance/low-bias individuals; averaging variance ko fix karta hai.

Free lunch: Out-of-Bag (OOB) error

Probability ki ek given row bootstrap sample mein nahi hai. $n$ draws mein se har ek us row ko probability $\frac{n - 1}{n}$ se miss karta hai. $n$ draws par independently: $P (row left out) = (1 - \frac{1}{n})^{n} n \to \infty e^{- 1} \approx 0.368.$ Yeh step kyun? $(1 - 1/ n)^{n}$ $e^{- 1}$ ki classic limit definition hai.

Feature importance (bonus interpretability)

Do common measures:

Mean Decrease in Impurity (MDI): har feature jo impurity reduction (Gini/entropy) cause karta hai usse sum karo, saare trees par average karke.
Permutation importance: ek feature ki values shuffle karo aur measure karo ki OOB accuracy kitna drop hoti hai. Bada drop ⇒ important feature.

Common Mistakes (Steel-man + fix)

Active Recall

Recall DO randomness sources kya hain aur har ek kya achieve karta hai?

(1) Bootstrap rows → bagging, averaging se variance reduce karta hai. (2) Har split par random feature subset → trees ko de-correlate karta hai, $ρ$ lower karta hai, variance floor $ρ σ^{2}$ shrink karta hai.

Recall Trees ko deep aur unpruned kyun grow karte hain?

Hum chahte hain low-bias, high-variance learners; bahut saare trees par averaging variance kill kar deta hai, isliye bias woh hai jo hum per tree minimize karte hain.

Recall Averaged ensemble ka variance derive karo.

$Var (\overset{ˉ}{f}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ ; doosra term → 0 jab $B \to \infty$ , floor $ρ σ^{2}$ bachta hai.

Recall Har tree ke liye data ka kitna fraction OOB hota hai aur kyun?

$\approx 36.8%$ , kyunki $(1 - 1/ n)^{n} \to e^{- 1}$ .

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

Socho ek bahut clever dost jo kabhi-kabhi beh jaati hai aur ajeeb answers deti hai. Sirf uski sunne ki bajaye, tum 100 doston se poochte ho, lekin har dost ko sirf kuch clues aur kuch past examples hi dekhne dete ho. Phir tum woh maante ho jo unme se zyada kehte hain. Kyunki unhone alag-alag cheezein dekhi thheen, unki silly mistakes align nahi hoti — isliye bheed ka answer zyada stable aur usually sahi hota hai. Decision-tree "doston" ki yahi bheed ek random forest hai.

80/20 — sabse zaroori baatein

Do randomnesses: rows (bagging) + features per split (de-correlation).
Variance law: $Var (\overset{ˉ}{f}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ → $ρ$ kam karna sabse zyada matter karta hai.
Deep unpruned trees; average/vote; ~37% OOB free validation ke liye.

Connections

Decision Trees — har forest ke andar base learner.
Bagging (Bootstrap Aggregating) — RF ka row-sampling waala half.
Bias-Variance Tradeoff — kyun low-bias/high-variance trees ko average karna kaam karta hai.
Gradient Boosting — contrasting ensemble: sequential, bias-reducing, variance-reducing nahi.
Cross-Validation — OOB error se free mein replace ho jaata hai.
Feature Importance — MDI & permutation importance.
Gini Impurity & Entropy — har tree ke andar use kiye jaane waale split criteria.

Plain bagging se aage Random Forest ko kya define karta hai?

Har split par random feature-subset selection, jo trees ko de-correlate karta hai (ρ lower karta hai).

B trees ke averaged ensemble ka variance, variance σ² aur pairwise correlation ρ ke saath?

Var = ρσ² + (1−ρ)/B · σ².

B→∞ hone par ensemble variance kiske paas jaata hai?

ρσ² — tree correlation se set hone wala irreducible floor.

Forest trees ko deep aur unpruned kyun grow karte hain?

Bias low rakhne ke liye; bahut saare trees par averaging variance handle karta hai.

Har tree ke liye rows ka kitna fraction out-of-bag hota hai aur kyun?

≈36.8%, kyunki (1−1/n)^n → e⁻¹.

Classification vs regression ke liye typical m (features per split)?

Classification ke liye √p, regression ke liye p/3.

RF mein feature importance measure karne ke do tarike?

Mean Decrease in Impurity (MDI) aur permutation importance.

RF classification vs regression ke liye predict kaise karta hai?

Trees ka majority vote / tree outputs ka average.

Zyada trees error ko zero tak kyun nahi le ja sakte?

Variance floor ρσ² B se independent hai; sirf ρ kam karna help karta hai.

OOB error ka purpose?

Un rows ko use karke built-in validation jo har tree ne train nahi kiya — free CV-jaisa estimate.