Stratified and leave-one-out cross-validation

Overview

While k-fold cross-validation randomly splits data, stratified cross-validation preserves the class distribution in each fold, and leave-one-out cross-validation (LOOCV) uses exactly one sample for testing. Both address specific weaknesses in standard k-fold CV.

Core Concepts

Stratified Cross-Validation: From First Principles

Why Stratification Matters

Setup: Dataset with n samples, C classes with counts $n_1, n_2, ..., n_C$ where $\sum_{i=1}^{C} n_i = n$ .

Class proportions: $p_i = \frac{n_i}{n}$ for class $i$ .

In random k-fold CV, each fold should ideally have $\frac{n}{k}$ samples with class $i$ count $\approx \frac{n_i}{k}$ . But random sampling introduces variance.

Expected deviation: For small $n_i$ (minority classes), random splits can produce folds with zero samples of that class.

Probability of missing a minority class in one fold (approximation): $P(\text{fold missing class } i) \approx \left(1 - \frac{1}{k}\right)^{n_i}$

For $k=5$ , $n_i=10$ : $P \approx (0.8)^{10} \approx 0.107$ — about 10% chance of a fold missing this class entirely.

Stratification Algorithm

Goal: Ensure each fold has exactly $\frac{n_i}{k}$ samples from class $i$ (or as close as possible when $n_i$ is not divisible by $k$ ).

Step-by-step derivation:

Partition by class: Separate dataset into C groups: $D_1, D_2, .., D_C$ where $|D_i| = n_i$
Per-class folding: For each class $i$ , create k sub-folds: $D_i^{(1)}, D_i^{(2)}, ..., D_i^{(k)}$ Size of each sub-fold: $\left\lfloor \frac{n_i}{k} \right\rfloor$ or $\left\lceil \frac{n_i}{k} \right\rceil$
Combine across classes: Fold $j$ = $D_1^{(j)} \cup D_2^{(j)} \cup ... \cup D_C^{(j)}$

Why this works: Each fold $j$ now contains: $|F_j \cap \text{class } i| = \frac{n_i}{k} \pm1$

The class proportion in fold $j$ : $\frac{|F_j \cap \text{class } i|}{|F_j|} = \frac{n_i/k}{n/k} = \frac{n_i}{n} = p_i$

The fold maintains the original class distribution!

Worked example Stratified CV Walkthrough

Dataset: 100 samples with 70negative (class 0) and 30 positive (class 1) Setup: 5-fold stratified CV Step 1 - Separate by class:

Class 0: 70 samples
Class 1: 30 samples

Step 2 - Divide each class into 5 groups:

Class 0: 5 groups of 14 samples each (70 ÷ 5 = 14)
Class 1: 5 groups of 6 samples each (30 ÷ 5 = 6)

Step 3 - Combine to form folds:

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) ✓
... and so on

Why this step? Each fold now has exactly the same 70:30 ratio as the original dataset. The model sees consistent class balance during each validation round.

Compare with random5-fold:

Fold 1 might have: 16 class-0 + 4 class-1 (80% / 20%) ✗
Fold 2 might have: 12 class-0 + 8 class-1 (60% / 40%) ✗
Inconsistent and unreliable!

Worked example Medical Diagnosis Dataset

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

Random k-fold disaster:

Some folds might get 100% healthy samples
Model trained on such a fold learns to always predict "healthy"
Appears to have 95% accuracy but completely useless

Stratified CV solution:

Each fold gets exactly 95 healthy + 5 diseased = 100 samples
Training set for each fold: 855 healthy + 45 diseased (5% positive)
Test set for each fold: 95 healthy + 5 diseased (5% positive) Why this step? The model always sees the rare disease examples during training (45 per fold instead of possibly 0). The validation metrics reflect real performance on the 5% positive rate.

Calculation check:

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

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

The Extreme Case: k = n

Standard k-fold uses< n. What happens as k increases?

k = 2: Each fold has n/2 samples, train on 50% of data k = 5: Each fold has n/5 samples, train on 80% of data k = 10: Each fold has n/10 samples, train on 90% of data k = n: Each fold has 1 sample, train on (n-1)/n ≈ 100% of data

LOOCV is the limit: maximum training data per iteration.

Bias-Variance Tradeoff in CV

The test error estimate from CV has two components:

$E[\text{CV Error}] = \text{Bias} + \text{Variance}$

Bias (how far the estimate is from true test error):

Higher k → larger training set → model closer to final model → lower bias
Lower k → smaller training set → model worse than final model → higher bias

Variance (how much the estimate fluctuates):

Higher k → more folds, more overlapping training sets → higher variance
Lower k → fewer folds, more independent training sets → lower variance

LOOCV bias: $\text{Bias}_{\text{LOOCV}} \approx 0$

Why? Training on n-1 samples is almost identical to training on n samples. The model being validated is essentially the final model.

LOOCV variance: $\text{Var}_{\text{LOOCV}} \approx \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} \text{Cov}(\epsilon_i, \epsilon_j)$

The n training sets overlap by n-2 samples, creating high correlation between error estimates.

Formula LOOCV Error Estimate

For a dataset with n samples, the LOOCV error is: $\text{CV}_{\text{LOOCV}} = \frac{1}{n} \sum_{i=1}^{n} L(y_i, \hat{f}^{(-i)}(x_i))$

where $\hat{f}^{(-i)}$ is the model trained on all samples except sample $i$ , and $L$ is the loss function.

Derivation:

Setup: n samples $(x_1, y_1), ..., (x_n, y_n)$
Iteration i:

Training set: all samples except $(x_i, y_i)$ → $n-1$ samples
Test set: $(x_i, y_i)$ → 1 sample
Train model: $\hat{f}^{(-i)}$ on the n-1 samples
Error: $e_i = L(y_i, \hat{f}^{(-i)}(x_i))$

Average across all iterations: $\text{CV}_{\text{LOCV}} = \frac{1}{n} \sum_{i=1}^{n} e_i$

Why this step? Each of the n samples gets used exactly once as the test set, and exactly n-1 times in training sets. This exhausts all information the dataset.

Worked example LOOCV Computation

Dataset: 5 samples with squared error loss

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

Iteration 1 (leave out sample 1):

Train on samples 2,3,4,5
Fit: $\hat{f}^{(-1)}(x) = 0.7x + 2.5$ (linear regression)
Test on sample 1: $\hat{y}_1 = 0.7(1) + 2.5 = 3.2$
Error: $e_1 = (2 - 3.2)^2 = 1.44$

Why this step? We're estimating how well a model trained on 4 samples predicts the held-out 5th sample.

Iteration 2 (leave out sample 2):

Train on samples 1,3,4,5
Fit: $\hat{f}^{(-2)}(x) = 0.8x + 1.8$
Test on sample 2: $\hat{y}_2 = 0.8(2) + 1.8 = 3.4$
Error: $e_2 = (4 - 3.4)^2 = 0.36$ Continue for iterations 3, 4, 5...

Suppose: $e_3 = 0.64$ , $e_4 = 0.25$ , $e_5 = 0.49$

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

Why this step? This single number summarizes expected error on unseen data, using every possible training configuration.

Computational Cost Analysis

Standard k-fold: Train k models, each on $\frac{k-1}{k} \cdot n$ samples

LOOCV: Train n models, each on n-1 samples

Ratio: LOOCV requires $\frac{n}{k}$ times more training than k-fold.

For k=10, n=1000: LOOCV requires 100× more computation.

Special case - Linear models: Closed-form shortcut exists. For ordinary least squares:

$\text{CV}_{\text{LOOCV}} = \frac{1}{n} \sum_{i=1}^{n} \left(\frac{y_i - \hat{y}_i}{1 - h_{ii}}\right)^2$

where $\hat{y}_i$ is the prediction from the model trained on all n samples, and $h_{ii}$ is the leverage (diagonal of the hat matrix).

Why this works? The leave-one-out prediction can be computed from the full model without refitting. Training once gives all n LOOCV errors. Computation cost drops from O(n) model fits to O(1) model fit.

When to Use Each Method

Formula Selection Criteria

Use Stratified CV when: $\min_i(p_i) < \frac{2}{k}$

where $p_i$ is the proportion of class $i$ and $k$ is the number of folds.

Derivation: If the smallest class has proportion $p_i$ , random k-fold expects $\frac{n \cdot p_i}{k}$ samples of that class per fold. For reliable statistics, you need at least 2-3 samples per fold.

Setting $n \cdot p_i / k \geq 2$ : $p_i \geq \frac{2k}{n} = \frac{2}{k} \cdot \frac{k}{n}$

But each fold has $n/k$ samples, so per-fold proportion should be: $p_i \geq \frac{2}{n/k} = \frac{2k}{n}$ Simplifying for decision rule: $p_i < 2/k$ means the class is underrepresented.

Use LOOCV when:

Dataset is very small (n < 50-100)
Model training is fast
You need minimum bias in your error estimate
You can afford the computational cost

Avoid LOOCV when:

Dataset is large (n > 1000)
Model training is expensive
You need quick iteration
High variance in error estimate is problematic

Worked example Decision Tree

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

Random10-fold CV is fine
Each fold has ~500 of each class
Stratification doesn't change much
LOOCV is overkill (10,000 model fits)

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

Use stratified 10-fold
Each fold needs 50minority samples (500/10)
Random might give folds with 30-70 minority samples
Stratified guarantees 50 per fold
Still avoid LOOCV (too expensive)

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

Consider LOOCV
10-fold would only have 5 samples per test fold
LOOCV maximizes training data (49 samples per iteration)
50 model fits is manageable

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

Use stratified 5-fold
Each fold gets 1 minority sample (5/5)
LOOCV would work but stratified 5-fold is faster
Both preserve the minority class

Common Mistakes

Common mistake Mistake 1: "Stratification is always better"

The wrong idea: Stratified CV is more sophisticated, so I should always use it, even for balanced datasets.

Why it feels right: More control seems better. Stratification guarantees class balance, which sounds like an improvement.

The reality: For balanced datasets, stratification adds complexity with negligible benefit. Random k-fold naturally creates approximately balanced folds when classes are balanced.

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

Random fold: Expected 50±7 of each class (binomial variance)
Stratified fold: Exactly 50 of each class
Model performance difference: < 0.1% in most cases

The fix: Use stratification when class imbalance exists ( $\max_i(p_i) / \min_i(p_i) > 2$ ) or when dealing with small minority classes. Otherwise, standard k-fold is simpler and sufficient.

Rule: If your smallest class has < 10 samples per fold, stratify. Otherwise, don't bother.

Common mistake Mistake 2: "LOOCV gives the most accurate error estimate"

The wrong idea: Since LOOCV uses the most training data and tests on every sample, it must give the best error estimate.

Why it feels right: More is better—LOOCV is the most exhaustive form of CV possible. It uses all available information.

The reality: LOOCV has high variance because the n training sets overlap heavily. The error estimates are highly corelated.

Mathematical insight:

k-fold with k=10: Training sets overlap by 80% → moderate correlation
LOOCV: Training sets overlap by ~100% → very high correlation
High correlation → high variance in the mean estimate $\text{Var}(\bar{e}) = \frac{1}{n^2} \sum_{i,j} \text{Cov}(e_i, e_j) \approx \frac{\sigma^2}{n} \cdot n = \sigma^2$

(variance doesn't decrease with n due to correlation!)

The fix: Use 5-fold or 10-fold CV for the best bias-variance tradeoff. LOCV is only appropriate for tiny datasets where you can't afford to hold out 20% of data.

Rule: For n < 50, consider LOOCV. For n > 100, stick with 5-fold or 10-fold.

Common mistake Mistake 3: "Stratified CV works with regression"

The wrong idea: If stratification helps with classification, I should stratify my regression targets too (e.g., ensure each fold has similar mean/variance of y).

Why it feels right: Fairness and balance apply everywhere. Ensuring folds have similar target distributions seems like good practice.

The reality: Stratification requires discrete classes. Regression targets are continuous. You'd need to bin the targets, which:

Introduces arbitrary threshold decisions
Loses information about the continuous nature
Provides minimal benefit in most cases

When target stratification matters: When the target distribution is multi-modal or has extreme outliers, and random splits might create folds that miss entire regions of the target space. The fix: For regression, use random k-fold CV unless you have evidence that your target distribution is problematic (e.g., visualize the target distribution in each fold and check for systematic differences). If needed, use stratified sampling on bined targets as a last resort.

Alternative: Group k-fold (for time series or grouped data) or repeated k-fold (run-fold multiple times with different random seeds and average).

Active Recall Practice

Recall Explain stratified CV to a12-year-old

Imagine you have a bag of 100 marbles: 70 red and 30 blue. You want to split them into 5 groups play a game.

Random split: You close your eyes and grab 20 marbles at a time. Sometimes you get 18red and 2 blue, sometimes 12 red and 8 blue. The groups are all different!

Stratified split: You separate the reds and blues first. Then take 14 red (70÷5) and 6 blue (30÷5) for each group. Now every group has exactly the same 14 red + 6 blue mix!

Why it matters: If you're testing how well your friend can guess marble colors, you want each test to be fair. With random splits, some tests are easier (more of one color) and some harder. With stratified splits, every test is equally hard because they all have the same mix.

LOOCV is even more extreme: Instead of 5 groups of 20 marbles, you make 100 groups—each group has 99 marbles for practice and 1 marble for testing. You test your friend 100 times! This takes forever but you learn the most about their guessing ability.

Connections 2.6.01-Training-validation-and-test-sets - Stratified CV is still a validation technique within train/val split

2.6.03-K-fold-cross-validation - Stratified CV is a refinement of k-fold; LOOCV is k-fold with k=n
2.6.04-Bias-variance-tradeoff-in-cross-validation - LOOCV minimizes bias but maximizes variance
3.2.05-Handling-imbalanced-classes - Stratified CV is essential when classes are imbalanced
2.3.08-Sampling-methods - Stratification is a form of stratified sampling applied to CV
5.4.02-Time-series-cross-validation - Time series requires different CV; can't use LOOCV or random splits

#flashcards/ai-ml

What is the key difference between stratified CV and standard k-fold CV? :: Stratified CV preserves the class distribution in each fold by splitting each class separately then combining, while standard k-fold randomly splits all samples together which can create imbalanced folds

Why does LOOCV have lower bias than k-fold CV?

LOOCV trains on n-1 samples (almost all data), making the validated model nearly identical to the final model trained on all n samples, minimizing the gap between CV performance and true test performance

What is the computational cost ratio of LOOCV vs k-fold?

LOOCV requires n/k times more training than k-fold; for k=10 and n=1000, LOCV needs 100× more computation (1000 model fits vs 10)

Write the LOOCV error formula :: $\text{CV}_{\text{LOOCV}} = \frac{1}{n} \sum_{i=1}^{n} L(y_i, \hat{f}^{(-i)}(x_i))$ where $\hat{f}^{(-i)}$ is trained on all samples except i

When should you use stratified CV? :: When class imbalance exists and $\min_i(p_i) < \frac{2}{k}$ (smallest class proportion is less than 2/k), or when minority classes have fewer than 10 samples per fold

Why does LOOCV have high variance despite using all data?

The n training sets overlap by-2 samples, creating high correlation between error estimates; variance doesn't decrease with n because

\text{Var}(\bar{e}) \approx \sigma^2

due to correlation

How does stratified CV ensure class balance?

It splits each class into k groups separately, then combines one group from each class to form each fold, guaranteeing each fold has proportional class representation

What is the special property of LOOCV for linear models?

For OLS, LOOCV can be computed from a single model fit using

\frac{1}{n}\sum(\frac{y_i - \hat{y}_i}{1-h_{ii}})^2

where

h_{ii}

is leverage, reducing cost from O(n) to O(1) fits

When is LOOCV preferred over k-fold?

When dataset is very small (n < 50-100), model training is fast, and you need minimum bias; avoid when n > 1000 or training is expensive

What happens if you use random5-fold on a 95%/5% imbalanced dataset?

Some folds might get 100% majority class or very few minority samples, causing the model to learn biased patterns and producing unreliable validation metrics

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Chalo ise simple tarike se samajhte hain. Jab hum normal k-fold cross-validation karte hain, toh data randomly split hota hai. Problem yeh hai ki agar aapke paas imbalanced data hai — jaise 90% negative aur sirf 10% positive samples — toh random split se koi fold mein shayad 100% negative hi aa jaayein aur positive samples bilkul na aayein. Aisa hone par model galat cheez seekhta hai aur aapke validation numbers reliable nahi rehte. Stratified cross-validation yahi problem solve karta hai — yeh ensure karta hai ki har fold mein original dataset waali hi class ratio maintain rahe. Matlab agar poore data mein 70% cats aur 30% dogs hain, toh har fold mein bhi 70:30 ratio hi milega.

Iska logic bhi seedha hai: pehle data ko class ke hisaab se alag karo, phir har class ko k barabar groups mein todo, aur phir har fold banane ke liye har class se ek-ek group utha ke combine kar do. Is tarah har fold mein saari classes proportional matra mein aa jaati hain. Doosra variant hai LOOCV (Leave-One-Out), jahan hum k ko extreme tak le jaate hain — agar n samples hain toh n folds banate hain, har baar n-1 samples pe train karke sirf 1 sample pe test. Isse maximum training data milta hai, lekin computational cost bhi utni hi zyaada ho jaati hai kyunki aapko n baar model train karna padta hai.

Yeh cheezein isliye important hain kyunki real-world data aksar imbalanced hota hai — medical diagnosis, fraud detection, rare disease prediction, in sabme minority class kam hoti hai lekin sabse important hoti hai. Agar aap stratification use nahi karenge toh aapka model evaluation galat picture dikhayega aur aapko lagega model achha kaam kar raha hai, jabki asal mein woh minority class ko pehchaan hi nahi pa raha. Isliye jab bhi imbalanced dataset ho, stratified CV default choice honi chahiye, aur jab data bahut kam ho tabhi LOOCV ka istemaal karein kyunki wahaan har ek sample keemti hota hai.