Out-of-bag error estimation — Hinglish notes

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

Ek "free" validation set jo bagging se apne aap nikal aata hai — koi alag hold-out ki zaroorat nahi.

The Setup: OOB exist kyun karta hai?

WHAT hai OOB error?

WHY ye kaam karta hai? Kisi bhi ek training point $x_{i}$ ke liye, jo trees us point ko exclude karti hain wo ek sub-ensemble banati hain jo $x_{i}$ ko unseen data ki tarah treat karti hain. Un trees ke upar predictions aggregate karna $x_{i}$ ke liye ek honest, out-of-sample prediction deta hai.

Magic number derive karna: ~37% hain out-of-bag

Chalo derive karte hain wo probability jisme ek specific point ek bootstrap sample mein NAHI choose hota.

Probability ki point $i$ ek draw mein nahi pick hota: $P (miss in 1 draw) = 1 - \frac{1}{n}$

Ye step kyun? Har draw $n$ points mein se exactly ek uniformly pick karta hai; "not $i$ " baaki $n - 1$ ko cover karta hai, to probability $= \frac{n - 1}{n} = 1 - \frac{1}{n}$ .

Probability ki point $i$ saare $n$ independent draws mein kabhi nahi pick hota: $P (OOB for i) = (1 - \frac{1}{n})^{n}$

Ye step kyun? Draws independent hain, to per-draw miss probability ko $n$ baar multiply karo.

Ab limit lo jab $n \to \infty$ : $lim_{n \to \infty} (1 - \frac{1}{n})^{n} = e^{- 1} \approx 0.368$

Ye step kyun? Ye classic definition hai $lim_{n \to \infty} (1 + \frac{x}{n})^{n} = e^{x}$ jisme $x = - 1$ .

OOB error actually compute kaise karte hain (the algorithm)

Har training point $x_{i}$ ke liye, set $S_{i} = {b : x_{i} \in / bootstrap (b)}$ dhundho — wo trees jinke liye $x_{i}$ OOB hai.
Sirf un trees ki predictions aggregate karo:
- Classification: $\overset{y}{^}_{i} = majority vote {T_{b} (x_{i}) : b \in S_{i}}$
- Regression: $\overset{y}{^}_{i} = \frac{1}{∣ S _{i} ∣} \sum_{b \in S_{i}} T_{b} (x_{i})$
Saare points ke upar OOB error compute karo:

$OOB error = \frac{1}{n} \sum_{i = 1}^{n} L (y_{i}, \overset{y}{^}_{i})$

jahan $L$ tumhara loss hai (classification ke liye 0/1 loss, regression ke liye squared error).

$S_{i}$ mein sirf trees kyun? Koi aisi tree jo $x_{i}$ pe train hui ho use karna label leak kar dega — tree $x_{i}$ ko memorize kar sakti hai, jo estimate ko optimistically biased bana deta. $S_{i}$ pe restrict karna ise honest rakhta hai.

Worked Example 1 — Kaun se points OOB hain?

In-bag = unique picked = ${1, 2, 4}$ . Kyun? Ye indices kam se kam ek baar appear karte hain, to tree ne inhe train kiya.
OOB for tree $b$ = ${3, 5}$ . Kyun? Indices 3 aur 5 kabhi appear nahi hote → tree ne unhe kabhi nahi dekha → ye tree ko test karte hain.

Fraction check karo: OOB fraction $= 2/5 = 0.40$ , theoretical $0.368$ ke kaafi close hai (small $n$ ka noise).

Worked Example 2 — Ek point ke liye OOB prediction compute karna

$T_{2} (x_{7}) = 1, T_{5} (x_{7}) = 0, T_{9} (x_{7}) = 1, T_{11} (x_{7}) = 1$

Majority vote $= 1$ (teen 1's vs ek 0). Kyun? Hum sirf un 4 trees ko aggregate karte hain jinne $x_{7}$ pe train nahi kiya — honest sub-ensemble.
OOB prediction $\overset{y}{^}_{7} = 1 = y_{7}$ → 0/1 loss mein $0$ contribute karta hai.

Hum baaki saari trees (maan lo $T_{1}, T_{3}, \dots$ ) ko $x_{7}$ ke liye ignore karte hain kyunki unhone us pe train kiya tha.

Worked Example 3 — Full OOB error

$i$	$y_{i}$	$\overset{y}{^}_{i}$ (OOB)	$(y_{i} - \overset{y}{^}_{i})^{2}$
1	10	12	4
2	20	19	1
3	30	27	9

$OOB MSE = \frac{4 + 1 + 9}{3} = \frac{14}{3} \approx 4.67$

$n = 3$ se divide kyun? Saare training points ke upar average karo, har ek ko apne OOB trees ke set se prediction milti hai.

Common Mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Socho 100 doston mein se har ek ek bade box se random flashcards ki pile uthake quiz ki taiyari karta hai (repeats ke saath). Pure chance se, har dost lagbhag 37% cards chhod deta hai. Ab, agar jaanna ho ki doston ne sach mein seekha hai (sirf memorize nahi kiya), to tum har dost ko test karte ho sirf un cards pe jo unhone kabhi padhe hi nahi. Unke unseen cards pe performance ka average batata hai ki poora group naye questions pe kitna achha hai — bina alag quiz khareedhe! Wo average score-mistake hi OOB error hai.

Flashcards

Out-of-bag (OOB) sample kya hota hai?

Ek training point jo kisi given tree ke bootstrap sample mein SELECT nahi hua; wo us tree ke liye unseen test data ki tarah kaam karta hai.

Har tree ke liye OOB mein data ka kitna fraction hota hai (large n)?

Lagbhag 36.8% (

e^{- 1}

); ~63.2% in-bag hota hai.

OOB fraction derive karo.

P (miss) = (1 - 1/ n)^{n} \to e^{- 1} \approx 0.368

jab

n \to \infty

Ek point ka OOB label kaun si trees predict karti hain?

Sirf wo trees jinke liye wo point out-of-bag tha (jinne us pe train NAHI kiya).

OOB prediction se in-bag trees ko kyun exclude karte hain?

Unhone training ke dauran point dekha tha → label leakage → optimistically biased (bahut low) error.

OOB error vs training error?

Training error memorizing trees ka use karta hai (bahut optimistic); OOB sirf unseen-tree votes use karta hai → test error estimate karta hai.

Classification OOB aggregation rule kya hai?

Un trees mein majority vote jo point ko out-of-bag rakhte the.

Regression OOB aggregation rule kya hai?

Un trees ki average prediction jo point ko out-of-bag rakhte the.

OOB kab unreliable hoti hai?

Jab trees ki sankhya

B

chhoti ho (har point ke liye kam OOB votes, high variance, possibly undefined).

Cross-validation ke mukable OOB ka kya advantage hai?

Ye essentially free hai — training ke dauran compute hoti hai, koi alag hold-out ya extra model fits nahi chahiye.

Connections

Bootstrap Aggregating (Bagging) — OOB replacement ke saath sampling ka byproduct hai.
Random Forests — OOB error ka standard consumer model evaluation ke liye.
Cross-Validation — alternative generalization estimate; OOB ise sasta approximate karta hai.
Bias-Variance Tradeoff — bagging variance reduce karta hai; OOB resulting test error measure karta hai.
Bootstrap Sampling — with-replacement draw jo 63/37 split create karta hai.
Decision Trees — base learners jo aggregate ho rahe hain.