Stratified and leave-one-out cross-validation

2.6.5 · AI-ML › Model Evaluation & Selection

Overview

Jab k-fold cross-validation randomly data split karta hai, stratified cross-validation har fold mein class distribution preserve karta hai, aur leave-one-out cross-validation (LOOCV) testing ke liye exactly ek sample use karta hai. Dono standard k-fold CV ki specific weaknesses ko address karte hain.

Core Concepts

Intuition Humein Ye Variants Kyun Chahiye

Problem: Standard k-fold CV aisi folds bana sakta hai jisme classes unbalanced hon. 90% negative aur 10% positive samples ke saath, ek random fold mein 95% negative ya phir 100% negative samples bhi aa sakte hain. Aapka model skewed data pe train hota hai aur aapke validation metrics unreliable ho jaate hain.

Stratified CV: Ensure karta hai ki har fold puri dataset ki class distribution mirror kare. Agar aapke paas overall 80% cats aur 20% dogs hain, toh har fold yahi 80:20 ratio maintain karta hai. Model saari folds mein consistent class balance dekhta hai. LOOCV: k-fold ko extreme tak le jaata hai — agar aapke paas n samples hain, toh aap n folds banate hain, jisme se har ek mein n-1 training samples aur 1 test sample hota hai. Maximum training data, maximum computational cost.

Stratified Cross-Validation: First Principles Se

Stratification Kyun Matters Karta Hai

Setup: n samples wala dataset, C classes jinke counts $n_{1}, n_{2}, ..., n_{C}$ hain jahan $\sum_{i = 1}^{C} n_{i} = n$ .

Class proportions: $p_{i} = \frac{n _{i}}{n}$ class $i$ ke liye.

Random k-fold CV mein, har fold mein ideally $\frac{n}{k}$ samples hone chahiye jisme class $i$ ka count $\approx \frac{n _{i}}{k}$ ho. Lekin random sampling variance introduce karta hai.

Expected deviation: Chote $n_{i}$ ke liye (minority classes), random splits aise folds bana sakti hain jisme us class ka ek bhi sample na ho.

Ek fold mein minority class ke missing hone ki probability (approximation): $P (fold missing class i) \approx (1 - \frac{1}{k})^{n_{i}}$

$k = 5$ , $n_{i} = 10$ ke liye: $P \approx (0.8)^{10} \approx 0.107$ — lagbhag 10% chance ki ek fold is class ko bilkul miss kar de.

Stratification Algorithm

Goal: Ensure karna ki har fold mein class $i$ ke exactly $\frac{n _{i}}{k}$ samples hon (ya jitna possible ho jab $n_{i}$ , $k$ se divisible na ho).

Step-by-step derivation:

Class ke hisaab se partition karo: Dataset ko C groups mein separate karo: $D_{1}, D_{2}, .., D_{C}$ jahan $∣ D_{i} ∣ = n_{i}$
Per-class folding: Har class $i$ ke liye, k sub-folds banao: $D_{i}^{(1)}, D_{i}^{(2)}, ..., D_{i}^{(k)}$ Har sub-fold ka size: $⌊ \frac{n _{i}}{k} ⌋$ ya $⌈ \frac{n _{i}}{k} ⌉$
Classes ke across combine karo: Fold $j$ = $D_{1}^{(j)} \cup D_{2}^{(j)} \cup ... \cup D_{C}^{(j)}$

Ye kaam kyun karta hai: Har fold $j$ mein ab yeh hoga: $∣ F_{j} \cap class i ∣ = \frac{n _{i}}{k} \pm 1$

Fold $j$ mein class proportion: $\frac{∣ F _{j} \cap class i ∣}{∣ F _{j} ∣} = \frac{n _{i} / k}{n / k} = \frac{n _{i}}{n} = p_{i}$

Fold original class distribution maintain karta hai!

Worked example Stratified CV Walkthrough

Dataset: 100 samples jisme 70 negative (class 0) aur 30 positive (class 1) Setup: 5-fold stratified CV Step 1 - Class ke hisaab se alag karo:

Class 0: 70 samples
Class 1: 30 samples

Step 2 - Har class ko 5 groups mein divide karo:

Class 0: 14-14 samples ke 5 groups (70 ÷ 5 = 14)
Class 1: 6-6 samples ke 5 groups (30 ÷ 5 = 6)

Step 3 - Folds banane ke liye combine karo:

Fold 1: 14 class-0 + 6 class-1 = 20 samples (70% / 30% split) ✓
Fold 2: 14 class-0 + 6 class-1 = 20 samples (70% / 30% split) ✓
... aur aise hi aage

Ye step kyun? Ab har fold mein exactly wahi 70:30 ratio hai jo original dataset mein hai. Model har validation round mein consistent class balance dekhta hai.

Random 5-fold se compare karo:

Fold 1 mein ho sakta hai: 16 class-0 + 4 class-1 (80% / 20%) ✗
Fold 2 mein ho sakta hai: 12 class-0 + 8 class-1 (60% / 40%) ✗
Inconsistent aur unreliable!

Worked example Medical Diagnosis Dataset

Scenario: Rare disease detection jisme 950 healthy aur 50 diseased patients hain (5% positive rate) Setup: 10-fold CV

Random k-fold disaster:

Kuch folds mein 100% healthy samples aa sakte hain
Aisi fold pe train hua model hamesha "healthy" predict karna seekh leta hai
95% accuracy lagti hai lekin bilkul useless hai

Stratified CV solution:

Har fold mein exactly 95 healthy + 5 diseased = 100 samples aate hain
Har fold ke liye training set: 855 healthy + 45 diseased (5% positive)
Har fold ke liye test set: 95 healthy + 5 diseased (5% positive) Ye step kyun? Model training mein hamesha rare disease examples dekhta hai (45 per fold, 0 ki jagah). Validation metrics 5% positive rate pe real performance reflect karte hain.

Calculation check:

Original: 950/1000 = 95% healthy
Har test fold: 95/100 = 95% healthy ✓
Har training fold: 855/900 = 95% healthy ✓

Leave-One-Out Cross-Validation: First Principles Se

Extreme Case: k = n

Standard k-fold, k ko < n use karta hai. Jaise-jaise k badhta hai kya hota hai?

k = 2: Har fold mein n/2 samples, 50% data pe train karo k = 5: Har fold mein n/5 samples, 80% data pe train karo k = 10: Har fold mein n/10 samples, 90% data pe train karo k = n: Har fold mein 1 sample, (n-1)/n ≈ 100% data pe train karo

LOOCV limit hai: har iteration mein maximum training data.

CV Mein Bias-Variance Tradeoff

CV se test error estimate ke do components hain:

$E [CV Error] = Bias + Variance$

Bias (estimate kitna true test error se dur hai):

Zyada k → bada training set → model final model ke kareeb → kam bias
Kam k → chota training set → model final model se worse → zyada bias

Variance (estimate kitna fluctuate karta hai):

Zyada k → zyada folds, overlapping training sets → zyada variance
Kam k → kam folds, zyada independent training sets → kam variance

LOOCV bias: $Bias_{LOOCV} \approx 0$

Kyun? n-1 samples pe training karna n samples pe training karne se almost identical hai. Jo model validate ho raha hai wo essentially final model hi hai.

LOOCV variance: $Var_{LOOCV} \approx \frac{1}{n ^{2}} \sum_{i = 1}^{n} \sum_{j = 1}^{n} Cov (ϵ_{i}, ϵ_{j})$

N training sets n-2 samples se overlap karte hain, jisse error estimates mein high correlation create hoti hai.

Worked example LOOCV Computation

Dataset: Squared error loss ke saath 5 samples

Sample	x	y
1	1	2
2	4
3	5
4	4
5	5

Iteration 1 (sample 1 leave out karo):

Samples 2,3,4,5 pe train karo
Fit: $\hat{f}^{(- 1)} (x) = 0.7 x + 2.5$ (linear regression)
Sample 1 pe test karo: $\overset{y}{^}_{1} = 0.7 (1) + 2.5 = 3.2$
Error: $e_{1} = (2 - 3.2)^{2} = 1.44$

Ye step kyun? Hum estimate kar rahe hain ki 4 samples pe train hua model held-out 5th sample ko kitna achha predict karta hai.

Iteration 2 (sample 2 leave out karo):

Samples 1,3,4,5 pe train karo
Fit: $\hat{f}^{(- 2)} (x) = 0.8 x + 1.8$
Sample 2 pe test karo: $\overset{y}{^}_{2} = 0.8 (2) + 1.8 = 3.4$
Error: $e_{2} = (4 - 3.4)^{2} = 0.36$ Iterations 3, 4, 5 ke liye continue karo...

Maano: $e_{3} = 0.64$ , $e_{4} = 0.25$ , $e_{5} = 0.49$

Final LOOCV error: $CV_{LOOCV} = \frac{1}{5} (1.44 + 0.36 + 0.64 + 0.25 + 0.49) = \frac{3.18}{5} = 0.636$

Ye step kyun? Yeh single number unseen data pe expected error summarize karta hai, har possible training configuration use karke.

Computational Cost Analysis

Standard k-fold: k models train karo, har ek $\frac{k - 1}{k} \cdot n$ samples pe

LOOCV: n models train karo, har ek n-1 samples pe

Ratio: LOOCV ko k-fold se $\frac{n}{k}$ guna zyada training chahiye.

k=10, n=1000 ke liye: LOOCV ko 100× zyada computation chahiye.

Special case - Linear models: Closed-form shortcut exist karta hai. Ordinary least squares ke liye:

$CV_{LOOCV} = \frac{1}{n} \sum_{i = 1}^{n} (\frac{y _{i} - y ^ _{i}}{1 - h _{ii}})^{2}$

jahan $\overset{y}{^}_{i}$ saare n samples pe train hue model ki prediction hai, aur $h_{ii}$ leverage hai (hat matrix ka diagonal).

Ye kaam kyun karta hai? Leave-one-out prediction full model se bina refit kiye compute ki ja sakti hai. Ek baar train karne se saare n LOOCV errors milte hain. Computation cost O(n) model fits se ghatkar O(1) model fit ho jaati hai.

Kab Kaun Sa Method Use Karein

Formula Selection Criteria

Stratified CV tab use karo jab: $min_{i} (p_{i}) < \frac{2}{k}$

jahan $p_{i}$ class $i$ ka proportion hai aur $k$ folds ki sankhya hai.

Derivation: Agar sabse choti class ka proportion $p_{i}$ hai, random k-fold expect karta hai ki har fold mein us class ke $\frac{n \cdot p _{i}}{k}$ samples hon. Reliable statistics ke liye aapko har fold mein kam se kam 2-3 samples chahiye.

$n \cdot p_{i} / k \geq 2$ set karke: $p_{i} \geq \frac{2 k}{n} = \frac{2}{k} \cdot \frac{k}{n}$

Lekin har fold mein $n / k$ samples hain, isliye per-fold proportion hona chahiye: $p_{i} \geq \frac{2}{n / k} = \frac{2 k}{n}$ Decision rule ke liye simplify karo: $p_{i} < 2/ k$ matlab class underrepresented hai.

LOOCV tab use karo jab:

Dataset bahut chota ho (n < 50-100)
Model training fast ho
Aapko apne error estimate mein minimum bias chahiye
Aap computational cost afford kar sako

LOOCV se tab bacho jab:

Dataset bada ho (n > 1000)
Model training expensive ho
Aapko quick iteration chahiye
Error estimate mein high variance problematic ho

Worked example Decision Tree

Scenario 1: 10,000 samples, balanced classes (5000/5000)

Random 10-fold CV theek hai
Har fold mein ~500 of each class
Stratification zyada kuch nahi badalta
LOOCV overkill hai (10,000 model fits)

Scenario 2: 10,000 samples, imbalanced (9,500/500 = 95%/5%)

Stratified 10-fold use karo
Har fold ko 50 minority samples chahiye (500/10)
Random mein folds ko 30-70 minority samples mil sakte hain
Stratified 50 per fold guarantee karta hai
Phir bhi LOOCV se bacho (bahut expensive)

Scenario 3: 50 samples, balanced (25/25)

LOOCV consider karo
10-fold mein sirf 5 samples per test fold hote
LOOCV training data maximize karta hai (49 samples per iteration)
50 model fits manageable hai

Scenario 4: 50 samples, imbalanced (45/5 = 90%/10%)

Stratified 5-fold use karo
Har fold ko 1 minority sample milta hai (5/5)
LOOCV kaam karega lekin stratified 5-fold faster hai
Dono minority class preserve karte hain

Common Mistakes

Common mistake Galti 1: "Stratification hamesha better hai"

Galat idea: Stratified CV zyada sophisticated hai, isliye mujhe ise hamesha use karna chahiye, chahe dataset balanced ho.

Ye sahi kyun lagta hai: Zyada control better lagta hai. Stratification class balance guarantee karta hai, jo ek improvement lagta hai.

Reality: Balanced datasets ke liye, stratification negligible benefit ke saath complexity add karta hai. Random k-fold naturally approximately balanced folds banata hai jab classes balanced hoti hain.

Example: 1000 samples jisme 500/500 classes hain, 10-fold CV

Random fold: Har class ke Expected 50±7 (binomial variance)
Stratified fold: Exactly 50 of each class
Model performance difference: Zyaatar cases mein < 0.1%

Fix: Stratification tab use karo jab class imbalance ho ( $max_{i} (p_{i}) / min_{i} (p_{i}) > 2$ ) ya choti minority classes ke saath kaam ho. Warna, standard k-fold simpler aur sufficient hai.

Rule: Agar aapki sabse choti class mein fold per < 10 samples hain, toh stratify karo. Warna, bother mat karo.

Common mistake Galti 2: "LOOCV sabse accurate error estimate deta hai"

Galat idea: Kyunki LOOCV sabse zyada training data use karta hai aur har sample pe test karta hai, yeh sabse achha error estimate zaroor deta hoga.

Ye sahi kyun lagta hai: Zyada better hai — LOOCV CV ka sabse exhaustive form possible hai. Yeh saari available information use karta hai.

Reality: LOOCV mein high variance hoti hai kyunki n training sets heavily overlap karte hain. Error estimates highly correlated hoti hain.

Mathematical insight:

k-fold with k=10: Training sets 80% overlap karte hain → moderate correlation
LOOCV: Training sets ~100% overlap karte hain → bahut high correlation
High correlation → mean estimate mein high variance $Var (\overset{e}{ˉ}) = \frac{1}{n ^{2}} \sum_{i, j} Cov (e_{i}, e_{j}) \approx \frac{σ ^{2}}{n} \cdot n = σ^{2}$

(correlation ki wajah se variance n ke saath decrease nahi karta!)

Fix: Best bias-variance tradeoff ke liye 5-fold ya 10-fold CV use karo. LOOCV sirf tiny datasets ke liye appropriate hai jahan aap 20% data hold out afford nahi kar sakte.

Rule: n < 50 ke liye, LOOCV consider karo. n > 100 ke liye, 5-fold ya 10-fold se kaam chalaao.

Common mistake Galti 3: "Stratified CV regression ke saath kaam karta hai"

Galat idea: Agar stratification classification mein help karta hai, toh mujhe apne regression targets bhi stratify karne chahiye (jaise har fold mein similar mean/variance of y ensure karo).

Ye sahi kyun lagta hai: Fairness aur balance har jagah apply hote hain. Folds mein similar target distributions ensure karna achhi practice lagti hai.

Reality: Stratification ke liye discrete classes chahiye. Regression targets continuous hote hain. Aapko targets bin karne padte, jo:

Arbitrary threshold decisions introduce karta hai
Continuous nature ke baare mein information kho deta hai
Zyaatar cases mein minimal benefit deta hai

Kab target stratification matters karta hai: Jab target distribution multi-modal ho ya extreme outliers hon, aur random splits aise folds bana sakti hain jo target space ke pure regions miss kar dein. Fix: Regression ke liye, random k-fold CV use karo jab tak aapke paas evidence na ho ki aapki target distribution problematic hai (jaise har fold mein target distribution visualize karo aur systematic differences check karo). Zaroorat padne par, bined targets pe stratified sampling last resort ke roop mein use karo.

Alternative: Group k-fold (time series ya grouped data ke liye) ya repeated k-fold (fold ko multiple baar alag random seeds ke saath run karo aur average lo).

Active Recall Practice

Recall Ek 12-saal ke bachche ko stratified CV explain karo

Imagine karo aapke paas 100 marbles ka ek bag hai: 70 lal aur 30 neele. Aap unhe ek game khelne ke liye 5 groups mein split karna chahte ho.

Random split: Aap aankhein band karke ek baar mein 20 marbles uthate ho. Kabhi 18 lal aur 2 neele milte hain, kabhi 12 lal aur 8 neele. Saare groups alag-alag hain!

Stratified split: Aap pehle lal aur neele alag karte ho. Phir har group ke liye 14 lal (70÷5) aur 6 neele (30÷5) lete ho. Ab har group mein exactly waही 14 lal + 6 neele ka mix hai!

Ye kyun matters karta hai: Agar aap test kar rahe ho ki aapka dost marble colors kitna achha guess kar sakta hai, toh aap chahte ho ki har test fair ho. Random splits ke saath, kuch tests easy hote hain (ek color zyada) aur kuch harder. Stratified splits ke saath, har test equally hard hai kyunki sabmein same mix hai.

LOOCV aur bhi extreme hai: 20 marbles ke 5 groups ki jagah, aap 100 groups banate ho — har group mein practice ke liye 99 marbles aur testing ke liye 1 marble. Aap apne dost ko 100 baar test karte ho! Isme hamesha ka time lagta hai lekin aap unki guessing ability ke baare mein sabse zyada seekhte ho.

Connections 2.6.01-Training-validation-and-test-sets - Stratified CV abhi bhi train/val split ke andar ek validation technique hai

2.6.03-K-fold-cross-validation - Stratified CV, k-fold ka ek refinement hai; LOOCV, k-fold hai jisme k=n
2.6.04-Bias-variance-tradeoff-in-cross-validation - LOOCV bias minimize karta hai lekin variance maximize karta hai
3.2.05-Handling-imbalanced-classes - Jab classes imbalanced hon toh stratified CV essential hai
2.3.08-Sampling-methods - Stratification, CV pe apply ki gayi stratified sampling ka ek form hai
5.4.02-Time-series-cross-validation - Time series ke liye alag CV chahiye; LOOCV ya random splits use nahi kar sakte

#flashcards/ai-ml

Stratified CV aur standard k-fold CV mein key difference kya hai? :: Stratified CV har class ko alag split karke phir combine karke, har fold mein class distribution preserve karta hai, jabki standard k-fold saare samples randomly split karta hai jo imbalanced folds bana sakta hai

LOOCV mein k-fold CV se kam bias kyun hoti hai?

LOOCV n-1 samples pe train karta hai (almost saara data), jisse validated model lagbhag final model jaisa hi hota hai jo saare n samples pe train hua, CV performance aur true test performance ke beech ka gap minimize karta hai

LOOCV aur k-fold ka computational cost ratio kya hai?

LOOCV ko k-fold se n/k guna zyada training chahiye; k=10 aur n=1000 ke liye, LOOCV ko 100× zyada computation chahiye (1000 model fits vs 10)

LOOCV error formula likhiye :: $CV_{LOOCV} = \frac{1}{n} \sum_{i = 1}^{n} L (y_{i}, \hat{f}^{(- i)} (x_{i}))$ jahan $\hat{f}^{(- i)}$ sample i ko chhodkar baaki saare samples pe train hua hai

Stratified CV kab use karna chahiye? :: Jab class imbalance ho aur $min_{i} (p_{i}) < \frac{2}{k}$ (sabse choti class ka proportion 2/k se kam ho), ya jab minority classes mein fold per 10 se kam samples hon

Saara data use karne ke baad bhi LOOCV mein high variance kyun hoti hai?

N training sets n-2 samples se overlap karte hain, jisse error estimates mein high correlation create hoti hai; variance n ke saath decrease nahi karta kyunki

Var (\overset{e}{ˉ}) \approx σ^{2}

correlation ki wajah se

Stratified CV class balance kaise ensure karta hai?

Yeh har class ko alag-alag k groups mein split karta hai, phir har class se ek group combine karke har fold banata hai, jisse har fold mein proportional class representation guaranteed hoti hai

Linear models ke liye LOOCV ki khaas property kya hai?

OLS ke liye, LOOCV ek single model fit se

\frac{1}{n} \sum (\frac{y _{i} - y ^ _{i}}{1 - h _{ii}})^{2}

use karke compute ki ja sakti hai jahan

h_{ii}

leverage hai, cost O(n) se ghatkar O(1) fits ho jaati hai

LOOCV ko k-fold par kab prefer kiya jaata hai?

Jab dataset bahut chota ho (n < 50-100), model training fast ho, aur minimum bias chahiye; jab n > 1000 ho ya training expensive ho tab avoid karo

Ek 95%/5% imbalanced dataset pe random 5-fold use karne se kya hota hai?

Kuch folds mein 100% majority class ya bahut kam minority samples aa sakte hain, jisse model biased patterns seekhta hai aur unreliable validation metrics produce hoti hain