Cross-validation pitfalls and nested CV

2.6.15 · AI-ML › Model Evaluation & Selection

Standard CV tumse kyun jhooth bol sakta hai

Data leakage ka trap

KYA hota hai: Tum data split karte ho → CV se hyperparameters tune karte ho → best CV score report karte ho.

YEH kyun galat hai: Tumhare hyperparameter search ne validation folds dekhe the. Ab model configuration un specific splits ke liye optimize ho chuka hai. CV score optimistically biased hai—yeh ab generalization ka independent estimate nahi raha.

Bias ki derivation: Ise formalize karte hain. Tumhare paas dataset $D$ hai, $K$ folds mein split kiya hua. Har hyperparameter config $\lambda$ ke liye: $\text{CV}(\lambda )=\frac{1}{K}{\sum }_{k=1}^K\text{Loss}(f_{\lambda ,{\mathcal{D}}_{-k}},{\mathcal{D}}_k)$ jahan $f_{\lambda ,{\mathcal{D}}_{-k}}$ woh model hai jo $k$ ko chhodkar baaki sabhi folds par train hua.

Tum select karte ho: ${\lambda }^{\ast }=\arg {\min }_{\lambda }\text{CV}(\lambda )$

Ab, $\text{CV}({\lambda }^{\ast })$ $\mathbb{E}[\text{Loss}(f_{{\lambda }^{\ast }},D_{\text{new}})]$ ka unbiased estimate nahi hai, kyunki:

1. Tumne $m$ configurations par search kiya
2. Chance se, kuch $\lambda$ in specific folds par achha perform karenge
3. $m$ random variables ka minimum negative bias rakhta hai (yeh hamesha mean se ≤ hota hai)

Bias badhta hai:

• Zyada hyperparameters search karne par ($m$ ↑)
• Chhote dataset par (CV scores mein zyada variance)
• Zyada complex models par (validation par overfit karna aasaan hota hai)

Outer loop model selection mein kabhi participate nahi karta. Har outer fold ko ek fresh hyperparameter search milta hai.

Nested CV estimator ki derivation

Step 1: Outer split Outer fold $i=1,\dots ,K_{\text{outer}}$ ke liye:

• Training: ${\mathcal{D}}_{\text{train}}^{(i)}$ (outer fold $i$ ko chhodkar saara data)
• Test: ${\mathcal{D}}_{\text{test}}^{(i)}$ (outer fold $i$, bilkul held out)

Step 2: ${\mathcal{D}}_{\text{train}}^{(i)}$ par Inner CV Is training set ke andar, $K_{\text{inner}}$ folds mein split karo. Har $\lambda$ ke liye: ${\text{CV}}_{\text{inner}}^{(i)}(\lambda )=\frac{1}{K_{\text{inner}}}{\sum }_{j=1}^{K_{\text{inner}}}\text{Loss}\left(f_{\lambda ,{\mathcal{D}}_{\text{train}}^{(i)}\setminus {\text{fold}}_j},{\text{fold}}_j\right)$

Select karo: ${\lambda }^{\ast (i)}=\arg {\min }_{\lambda }{\text{CV}}_{\text{inner}}^{(i)}(\lambda )$

YEH step kyun? Hum wahi mimic kar rahe hain jo hum production mein karte: available training data par tune karo. Lekin yeh tuning har outer fold ke liye independent hai.

Step 3: Final model train karo aur outer test par evaluate karo $f_{{\lambda }^{\ast (i)},{\mathcal{D}}_{\text{train}}^{(i)}}$ ko inner CV ke best hyperparameter se train karo, phir ${\mathcal{D}}_{\text{test}}^{(i)}$ par evaluate karo: ${\text{Error}}^{(i)}=\text{Loss}\left(f_{{\lambda }^{\ast (i)}},{\mathcal{D}}_{\text{train}}^{(i)},{\mathcal{D}}_{\text{test}}^{(i)}\right)$

Step 4: Outer folds mein average karo $\text{Nested CV Error}=\frac{1}{K_{\text{outer}}}{\sum }_{i=1}^{K_{\text{outer}}}{\text{Error}}^{(i)}$

YEH unbiased kyun hai: Har ${\mathcal{D}}_{\text{test}}^{(i)}$ hyperparameter tuning ke dauran kabhi nahi dekha gaya. Outer loop poore pipeline ki performance estimate karta hai (hyperparameter search sameta).

Nested CV (unbiased): ${\hat{E}}_{\text{nested}}=\frac{1}{K_{\text{outer}}}{\sum }_{i=1}^{K_{\text{outer}}}\left[\text{Loss}\left(f_{{\lambda }^{\ast (i)},{\mathcal{D}}_{\text{train}}^{(i)}},{\mathcal{D}}_{\text{test}}^{(i)}\right)\right]$ jahan ${\lambda }^{\ast (i)}=\arg {\min }_{\lambda }{\text{CV}}_{\text{inner}}^{(i)}(\lambda )$

• Outer test sets hyperparameter search se kabhi touch nahi hote
• Performance ko har independent tuning ke baad average karta hai

Standard CV (5-fold):

For each α:
  - Compute5-fold CV error on all100 samples
Best α = 1.0, CV error = 0.23
Report: "Our model achieves 0.23 error"

Kyun galat hai: Choice $\alpha =1.0$ isliye ki gayi kyunki isne in 5 folds par best perform kiya. Chance se, shayad $\alpha =10$ better generalize karta, lekin in specific splits par bura perform kiya.

Nested CV (5 outer, 5 inner):

Outer fold 1 (20 samples held out):
  - Inner 5-fold CV on remaining 80 samples
  - Best α = 0.1, train on 80, test on 20 → error = 0.31
Outer fold 2:
  - Inner CV finds best α = 1.0, error = 0.19
...
Outer fold 5:
  - Best α = 1.0, error = 0.27
  
Average = (0.31 + 0.19 + 0.25 + 0.21 + 0.27)/5 = 0.246
Report: "Our model + tuning procedure achieves ~0.25 error"

YEH step kyun? Har outer fold ka test set us fold ke inner hyperparameter search ke dauran kabhi nahi dekha gaya. Average 0.246 ek honest estimate hai.

Kyun galat hai: Feature selection ne poore dataset ko dekha, validation folds sameta. Tumne information leak ki.

Bias ki derivation: Jab tum sabhi $n$ samples par features select karte ho, phir CV karte ho, to features un validation samples mein bhi $y$ ke saath correlation maximize karne ke liye choose kiye gaye the.

Maano $S(D)$ tumhara feature selection function hai. Biased estimator hai: ${\hat{E}}_{\text{biased}}=\text{CV}(f_{S(D)},D)$

Lekin hum new data par pipeline $S\circ f$ ki performance estimate karna chahte hain: $E_{\text{true}}={\mathbb{E}}_{D_{\text{train}},D_{\text{test}}}[\text{Loss}(f_{S(D_{\text{train}})},D_{\text{test}})]$

Biased estimator $S(D)$ use karta hai jisne $D_{\text{test}}$ dekha tha, isliye ${\hat{E}}_{\text{biased}}<E_{\text{true}}$.

Correct nested approach:

Outer fold i:
  - On training 90%, select top 10 features
  - Inner CV to tune model on those features
  - Evaluate on test 10% (which wasn't used for feature selection)

Itna bada gap kyun? 1000 features aur 100 samples ke saath, kaafi features chance se in specific samples mein $y$ ke saath correlate karte hain. Standard CV ne woh features select kiye jo noise ko fit karte the, phir usi data par validate kiya jis par woh features choose kiye gaye the.

Kyun sahi lagta hai: Tumne data hold out kiya! Tumne uspar train nahi kiya!

Steel-man: Tum sahi ho ki tumne validation folds par train nahi kiya. Galti subtle hai—tumne uspar train nahi kiya, lekin tumne unke based par decisions liye (kaun se hyperparameters use karne hain, kaun se features rakhne hain, search kab rokni hai). Jo bhi decision validation performance se informed tha, woh us validation set ko kam independent banata hai.

Fix: Nested CV ya ek sach mein held-out test set jo kabhi kisi bhi decision-making ke liye use na ho.

Kyun sahi lagta hai: Tumne nested CV sahi se run ki, aur usne ise properly find kiya.

Steel-man: Tumne nested CV sahi se run ki, lekin phir ek fold se inner score cherry-pick kiya. Inner CV score us fold ke hyperparameter search ke liye optimistic hai.

Fix: Outer CV average report karo. Inner scores sirf selection ke liye hain. Agar tum jaanna chahte ho ki production ke liye kaun sa hyperparameter use karna hai, to sabse zyada commonly selected inner ${\lambda }^{\ast }$ ke saath saare data par retrain karo, lekin tumhara performance estimate outer average hai.

Kyun galat hai: Normalization ne test folds se statistics compute ki. Data leakage.

Derivation: Agar $\mu$ aur $\sigma$ sabhi $n$ samples se compute kiye gaye hain, to fold $k$ mein test sample $x_{\text{test}}$ ke liye: $x_{\text{test}}^{\text{normalized}}=\frac{x_{\text{test}}-\mu }{\sigma }$ jahan $\mu =\frac{1}{n}{\sum }_{i=1}^n{x}_i$ mein $x_{\text{test}}$ khud bhi shamil hai. Tumne test data ko transform karne ke liye test information use ki.

Correct: Preprocessing dono loops ke andar honi chahiye:

For each outer fold:
  For each inner fold:
    - Compute μ, σ on inner training set only
    - Apply to inner validation set
  - Compute μ, σ on outer training set
  - Apply to outer test set

Lekin yahan ek trick hai: kya tumne sach mein spell karna seekha, ya tumne bas un specific 100 words ko memorize kar liya?

Yeh pata karne ke liye, tumhe words ki ek fresh list chahiye hogi jo tumne pehle kabhi nahi dekhi. Yahi ek real test set hota hai.

Ab, nested cross-validation kuch aisa hai: Socho tum sirf ek baar practice nahi karte—tum paanch practice sessions karte ho, har ek mein alag 80-word subset ke saath. Har session ke liye, tum alag study techniques try karte ho (flashcards, unhe likhna, etc.) aur us session ke liye best choose karte ho. Phir tum un 20 words par khud ko test karte ho jo tumne us session mein study nahi kiye. Tum yeh paanch baar alag 20-word test groups ke saath dohraate ho, aur apne scores ka average karte ho.

Kyun? Kyunki har baar, woh 20 test words tumhare "mujhe kaun si study technique use karni chahiye?" decision ka hissa kabhi nahi tha. Tumhe ek honest measure milta hai ki tumhara learning method kitna achha kaam karta hai, na ki sirf tumne kitna memorize kiya.

Ek teen-layer tower picture karo:

• Upar (Test): Pure evaluation floor, locked door, koi wahan end tak nahi jaata
• Beech mein (Tune): Workshop floor jahan tum alag tools try karte ho aur dekhte ho kya kaam karta hai
• Neeche (Train): Assembly line jahan models chosen tools se bante hain

Sirf middle floor top se ek one-way mirror ke through baat karta hai—yeh test data nahi badal sakta, bas results report karta hai.

Nested CV kab use karna chahiye

Nested CV use karo jab:

1. Tum hyperparameters tune kar rahe ho (data par based koi bhi model selection)
2. Tumhara dataset small/medium hai (typically <10,000 samples)
3. Tumhe ek unbiased performance estimate chahiye
4. Tum alag model families ya pipelines compare kar rahe ho
5. Tum feature selection, preprocessing tuning, ya koi bhi data-driven decision kar rahe ho

Nested CV skip karo jab:

1. Tumhare paas ek massive dataset hai aur tum true held-out test set afford kar sakte ho (20%+)
2. Tum hyperparameter search nahi kar rahe (sirf ek fixed model train kar rahe ho)
3. Computational cost prohibitive hai aur tum biased estimates accept karte ho (lekin ise document karo!)

Computational cost: Nested CV expensive hai. Agar outer $K_o=5$, inner $K_i=5$, aur tum $m=100$ hyperparameters search karte ho: $\text{Total fits}=K_o\times K_i\times m=5\times 5\times 100=2500\text{ model fits}$

Alternative: Agar tumhare paas kaafi data hai to single train/validation/test split use karo (jaise 60/20/20). Validation par tune karo, test par report karo. Aasaan hai, lekin zyada bade $n$ ki zaroorat hai.

Doosre concepts se connections

• 2.6.1-Train-test-split-and-holdout-method: Nested CV iska principled extension hai jab tumhe hyperparameter tuning chahiye
• 2.6.2-K-fold-cross-validation: Inner aur outer dono loops k-fold use karte hain
• 2.6.12-Hyperparameter-tuning-strategies: Grid/random search inner CV loop ke andar honi chahiye
• 2.6.16-Data-leakage: Nested CV model selection ke dauran leakage rok ta hai
• 2.7.3-Bias-variance-tradeoff: Standard CV mein optimistic bias hota hai; nested CV ise reduce karta hai
• 3.4.5-Early-stopping: Agar validation-based early stopping use kar rahe ho, to yeh inner loop mein hona chahiye

Key takeaways

1. Hyperparameter tuning ke saath standard CV biased (optimistic) estimates deta hai
2. Nested CV tuning (inner) ko evaluation (outer) se alag karta hai bias hatane ke liye
3. Outer CV average report karo; inner CV sirf selection ke liye hai
4. Preprocessing, feature selection, aur saare data-dependent choices CV ke andar hone chahiye
5. Cost: $K_{\text{outer}}\times K_{\text{inner}}\times m$ fits, lekin honest estimates milte hain

#flashcards/ai-ml

Hyperparameter tuning ke baad CV score report karne mein fundamental problem kya hai? :: CV score optimistically biased hai kyunki hyperparameters un specific folds par woh score minimize karne ke liye select kiye gaye the—validation data model selection mein participate kar chuka hai.

Concept Map