K-fold cross-validation

The Problem: Limited Data & Unreliable Estimates

When we have a dataset, we face a dilemma:

WHY? We need to evaluate our model on data it hasn't seen during training
PROBLEM: If we hold out too much data for testing (say 50%), we're training only half our data → worse model
PROBLEM: If we hold out too little (say 10%), our performance estimate has high variance → one lucky/unlucky split can mislead us

K-fold cross-validation solves this by using every data point for both training AND testing (but never at the same time).

The K-fold Algorithm: Derivation from First Principles

Step-by-Step Derivation

WHAT we want: An estimate of generalization error $E[\text{error}]$ that uses all our data efficiently.

HOW we get it:

Let's denote:

Dataset $D$ with $N$ samples
Performance metric $M$ (e.g., accuracy, RMSE)
Model training procedure $T$

Step 1: Partition the data

Divide $D$ into K disjoint subsets (folds): $D = F_1 \cup F_2 \cup \ldots \cup F_K$

Each fold has approximately $\frac{N}{K}$ samples. WHY equal-sized? So each validation set represents the same proportion of data → fair comparison.

Step 2: Define the K training/validation splits

For iteration $i$ (where $i = 1, 2, \ldots, K$ ):

Validation set: $V_i = F_i$
Training set: $T_i = D \setminus F_i = \bigcup_{j \neq i} F_j$

WHY this matters: Each data point appears in exactly1 validation set and K-1 training sets.

Step 3: Train and evaluate K models

For each fold $i$ :

Train model on $T_i$ : $\theta_i = T(T_i)$
Evaluate on $V_i$ : $\text{score}_i = M(\theta_i, V_i)$

Step 4: Aggregate the results

The K-fold CV estimate is:

$\text{CV}_K = \frac{1}{K} \sum_{i=1}^{K} \text{score}_i$

WHY the mean? By the Law of Large Numbers, averaging K estimates reduces variance. Each $\text{score}_i$ is a noisy estimate of true performance; averaging gives us a more stable estimate.

The standard error tells us reliability:

$\text{SE} = \sqrt{\frac{1}{K} \sum_{i=1}^{K} (\text{score}_i - \text{CV}_K)^2}$

WHY standard error matters: If SE is large, our folds give very different scores → model is sensitive to training data (possible overfitting or data issues).

Worked Examples

Worked example Example 1: 5-Fold CV with100 Samples

Setup: 100 data points, K=5, using accuracy as metric. Step 1: Create 5 folds of 20 samples each

$F_1 =$ samples 1-20
$F_2 =$ samples 21-40
$F_3 =$ samples 41-60
$F_4 =$ samples 61-80
$F_5 =$ samples 81-100

WHY this split? Random (or stratified) assignment ensures each fold is representative.

Step 2: Iteration 1

Train on $F_2\cup F_3 \cup F_4 \cup F_5$ (80 samples)
Validate on $F_1$ (20 samples)
Get $\text{accuracy}_1 = 0.85$

WHY 80 training samples? We use $\frac{K-1}{K} = \frac{4}{5} = 80\%$ of data for training.

Step 3: Repeat for all folds

Fold 2: Train on $F_1 \cup F_3 \cup F_4 \cup F_5$ , validate on $F_2$ → accuracy = 0.82
Fold 3: Train on $F_1 \cup F_2 \cup F_4 \cup F_5$ , validate on $F_3$ → accuracy = 0.88
Fold 4: Train on $F_1 \cup F_2 \cup F_3 \cup F_5$ , validate on $F_4$ → accuracy = 0.84
Fold 5: Train on $F_1 \cup F_2 \cup F_3 \cup F_4$ , validate on $F_5$ → accuracy = 0.86

Step 4: Calculate mean and SE $\text{CV}_5 = \frac{0.85 + 0.82 + 0.88 + 0.84 + 0.86}{5} = \frac{4.25}{5} = 0.850$

$\text{SE} = \sqrt{\frac{(0.85-)^2 + (0.82-0.85)^2 + (0.88-0.85)^2 + (0.84-0.85)^2 + (0.86-0.85)^2}{5}}$ $= \sqrt{\frac{0 + 0.0009 + 0.0009 + 0.0001}{5}} = \sqrt{0.0004} = 0.02$

Interpretation: The model achieves 85.0% ± 2.0% accuracy. The low SE means the model is consistent across folds.

Worked example Example 2: Comparing K=3 vs K=10

Setup: 1000 samples, comparing two values of K.

K=3 (3-fold CV):

Training set size: $\frac{2000}{3} \approx 667$ samples per fold
Each model is trained on ~66.7% of data
Bias: Higher (model trained on less data than final model will use)
Variance: Lower (only 3 estimates to average)
Speed: Fast (only 3 model traings)

WHY higher bias? If our final model uses all1000 samples, but CV models use only 667, we're underestimating performance. The gap between 667 and 1000 introduces pessimistic bias.

K=10 (10-fold CV):

Training set size: 900 samples per fold
Each model trained on 90% of data
Bias: Lower (closer to final model's training size)
Variance: Higher (averaging 10 noisier estimates)
Speed: Slower (10 model trainings)

WHY lower bias? Training on 900/1000 samples is much closer to the final 1000, so performance estimate is more accurate.

WHICH TO CHOOSE?

K=5 or K=10: Standard choice, good bias-variance balance
K=3: When computation is expensive (deep learning, large datasets)
K=N (LOOCV): When data is very scarce (< 100 samples) and you need minimum bias

Worked example Example 3: Stratified K-fold for Imbalanced Data

Problem: You have 100 samples with 90class A and 10 class B (90-10 imbalance). Regular K-fold risk: Random split might put all 10 class B samples in 1-2 folds → some folds have no class B in validation → meaningless accuracy.

Solution: Stratified K-fold

Ensure each fold maintains the same class distribution (90-10)
For K=5: each fold gets 18 class A + 2 class B WHY this matters: Each validation fold is representative of the true data distribution.

HOW to implement:

Separate data by class: $D_A$ (90 samples), $D_B$ (10 samples)
Apply K-fold to each class separately
Merge the corresponding folds: $F_i = F_i^A \cup F_i^B$ Result: Every fold has exactly 9:1 ratio, matching the overall dataset.

Common Mistakes & Fixes

Common mistake Mistake 1: Data Leakage Across Folds

What people do wrong: Preprocess (normalize, scale) the entire dataset BEFORE splitting into folds.

WHY this feels right: "I need to normalize my data first, then split it for validation."

WHY it's wrong: When you compute mean/std on the full dataset, the validation fold has already "seen" information from the training folds. This is data leakage. Example:

# WRONG
X_normalized = (X - X.mean()) / X.std()  # Uses info from ALL data
for train_idx, val_idx in kfold.split(X_normalized):
    # Validation set has leaked info!

The fix: Fit preprocessing on training folds only, apply to validation fold:

# RIGHT
for train_idx, val_idx in kfold.split(X):
    X_train, X_val = X[train_idx], X[val_idx]
    scaler = StandardScaler().fit(X_train)  # Learn from training only
    X_train_scaled = scaler.transform(X_train)
    X_val_scaled = scaler.transform(X_val)  # Apply same transformation

Steel-man: The original intuition (normalize first) works for simple train/test split. The mistake is not updating the mental model when folds are involved.

Common mistake Mistake 2: Using K-fold for Hyperparameter Tuning Directly

What people do wrong: Run K-fold CV for each hyperparameter combination, pick the best, report that K-fold score as final performance.

WHY it's wrong: You've now used the validation folds to make decisions (hyperparameter selection). The K-fold score is optimistically biased.

The fix: Nested Cross-Validation

Outer loop: K-fold for performance estimation
Inner loop: K-fold for hyperparameter selection within each outer fold Structure:

For each outer fold i:
    Training set = outer_traini
    Test set = outer_test_i
    For each hyperparameter config:
        Inner K-fold CV on outer_train_i → select best config
    Train final model with best config on outer_train_i
    Evaluate on outer_test_i → score_i
Report: mean(score_i)

WHY this works: The outer test folds never participate in hyperparameter selection, so the score is unbiased.

Common mistake Mistake 3: Ignoring Time Dependencies (Time Series)

What people do wrong: Apply random K-fold to time series data.

WHY it's wrong: You're training on future data and testing on past data → unrealistic, inflated performance.

The fix: Time Series Cross-Validation

Always keep temporal order
Use expanding or sliding window Expanding window example (K=4):

Fold 1: Train [1:100], Test [101:125]
Fold 2: Train [1:125], Test [126:150]
Fold 3: Train [1:150], Test [151:175]
Fold 4: Train [1:175], Test [176:200]

WHY this works: You only predict the future, never the past.

The Math Behind Bias and Variance

Question: Why does K-fold with larger K have lower bias but higher variance?

Bias derivation:

Let $\theta_N$ be the model trained on all N samples (our target), and $\theta_{(K-1)N/K}$ be the model trained on $(K-1)N/K$ samples (each fold).

The estimation bias comes from the difference: $\text{Bias} \propto |E[\text{error}(\theta_{(K-1)N/K})] - E[\text{error}(\theta_N)]|$

WHY larger K reduces bias: As $K \to N$ , $\frac{(K-1)N}{K} \to N$ , so the training set size approaches the full dataset. The model's performance approaches what it would be if trained on all data.

Variance derivation:

The variance of the K-fold estimator is: $\text{Var}(\text{CV}_K) = \text{Var}\left(\frac{1}{K}\sum_{i=1}^K \text{score}_i\right) = \frac{1}{K^2} \sum_{i=1}^K \text{Var}(\text{score}_i) + \frac{2}{K^2}\sum_{i<j}\text{Cov}(\text{score}_i, \text{score}_j)$

$\frac{3}{4}$ $\text{CV}_K = \frac{1}{K} \sum_{i=1}^{K} M(\theta_i, F_i)$ where each model θᵢ is trained on all folds except Fᵢ, and evaluated on Fᵢ.

Why does larger K reduce bias in cross-validation?

Larger K means each training set is closer in size to the full dataset (e.g., K=10 uses 90% of data). This makes the CV estimate closer to the performance of a model trained on all data.

Why does larger K increase variance in cross-validation?

Larger K creates more folds with smaller validation sets (noisier estimates) and higher overlap between training sets (positive correlation between scores), both of which increase variance.

What is the typical choice of K and why?

K=5 or K=10. This balances bias (training on 80-90% of data is close to full dataset) and variance (not too many corelated estimates) while being computationally reasonable.

What is data leakage in K-fold CV?

When preprocessing (normalization, feature selection) is done on the entire dataset before splitting, the validation folds contain information from training folds. Fix: fit preprocessing on training folds only, then apply to validation.

What is stratified K-fold and when is it needed?

Stratified K-fold maintains the same class distribution in each fold as in the full dataset. Essential for imbalanced datasets to ensure every validation fold is representative.

What is nested cross-validation?

Outer K-fold loop for performance estimation, inner K-fold loop for hyperparameter tuning. Prevents optimistic bias from using validation data for model selection.

Why can't you use regular K-fold for time series?

It would train on future data and test on past data, violating temporal causality. Use time series CV with expanding/sliding windows that only predict future from past.

What does high standard error across folds indicate?

The model's performance is very sensitive to which data it's trained on, suggesting possible overfitting, data quality issues, or that the model is not robust.

What is Leave-One-Out Cross-Validation (LOOCV)? :: The extreme case where K=N (number of samples). Each model is trained on N-1 samples and validated on 1. Minimum bias but maximum variance and computational cost.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

K-fold cross-validation samajhne ke liye ek simple examplete hain. Maan lo tumhare pas 100 student records hain aur tum ek model banana chahte ho jo predict kare ki student pass hoga ya fail. Agar tum sirf ek baar data ko split karo (80 train, 20 test), toh ho sakta hai luck se tumhare test set mein easy cases aa gaye aur model acha lag raha ho, ya phir unlucky split mein sab difficult cases aa gaye aur model bura lag raha ho. Yeh unreliable estimate hai.

K-fold ka concept yeh hai: data ko K equal parts mein divide karo (for example, K=5 means 5 parts of 20 students each). Ab5 baar model train karo - har baar ek alag part ko validation ke liye rakho aur baki 4 parts pe train karo. Isse har studentek baar validation mein ata hai aur baki times training mein. End mein in 5 results ka average nikalo - yeh average bahut zyada reliable estimate hai kyunki tumne model ko 5 different "exams" pe test kara hai, na ki sirf ek lucky/unlucky split pe.

Yeh technique limited data ko efficiently use karti hai. Single train-test split mein agar 20% holdout rakha toh wo 20 samples waste ho gaye sirf testing ke liye. K-fold mein har sample training aur testing dono ke liye use hota hai (alag alag iterations mein). Plus, tumhe performance ki stability bhi pata chalti hai - agar 5 folds mein bahut zyada variation hai toh model inconsistent hai ya data mein issues hain. Machine learning competitions aur research mein K-fold standard practice hai model evaluation ke liye, kyunki yeh honest aur robust estimate deta hai bina data waste kiye.

The Problem: Limited Data & Unreliable Estimates

The K-fold Algorithm: Derivation from First Principles

Step-by-Step Derivation

Worked Examples

Common Mistakes & Fixes

The Math Behind Bias and Variance

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Model Evaluation & Selection

Connections