Grid search and random search — Hinglish notes

2.6.13 · AI-ML › Model Evaluation & Selection

The Hyperparameter Tuning Problem

The Goal: Hyperparameter configuration $h^{*} = {h_{1}, h_{2}, \dots, h_{k}}$ dhundna jo validation performance maximize kare:

h^{*} = ar g h \in H max score_{val} (h)

jahaan $H$ hyperparameter space hai.

Yeh Hard Kyun Hai:

Koi gradient information nahi (hyperparameters validation loss ke w.r.t. differentiable nahi hote)
Har evaluation ke liye full model training chahiye (expensive hai)
Space high-dimensional aur combinatorial hai
Hyperparameters ke beech interactions non-linear hain

Grid Search: Exhaustive Exploration

How Grid Search Works

Step-by-step:

Har hyperparameter ke liye ek grid define karein:
- Learning rate: $α \in {0.001, 0.01, 0.1}$
- Regularization: $λ \in {0.01, 0.1, 1.0, 10.0}$
Saare combinations generate karein: $(0.001, 0.01), (0.001, 0.1), \dots, (0.1, 10.0)$
Har combination ke liye:
- Un hyperparameters ke saath training set par model train karein
- Validation set par evaluate karein
- Validation score record karein
Best validation score wala configuration select karein
Best config ke saath full training+validation data par retrain karein, hold-out test set par test karein

Computational Cost: Agar hamare paas $α$ ke liye 3 values, $λ$ ke liye 4, aur max depth ke liye 5 hain:

Total models = 3 \times 4 \times 5 = 60 models

5-fold CV ke saath, woh $60 \times 5 = 300$ training runs hain.

Worked example Grid Search Example

Task: SVM ko RBF kernel ke saath tune karna. Hyperparameters: $C$ (regularization), $γ$ (kernel coefficient). Grid:

C_values = [0.1, 1, 10, 100]
gamma_values = [0.001, 0.01, 0.1, 1]

Process:

Combination 1: $C = 0.1, γ = 0.001$ → Train → Val score = 0.82
Combination 2: $C = 0.1, γ = 0.01$ → Train → Val score = 0.85
...
Combination 16: $C = 100, γ = 1$ → Train → Val score = 0.91

Yeh step kyun? Hum performance surface ko map kar rahe hain. High $C$ with moderate $γ$ overfit kar sakta hai. Low $C$ with high $γ$ underfit kar sakta hai. Combinations try karne padte hain kyunki woh interact karte hain. Result: Best config $C = 10, γ = 0.1$ hai jiska val score 0.93 hai.

Advantages of Grid Search

Grid ke andar best configuration dhundne ki guarantee (exhaustive)
Implement aur samajhne mein simple
Reproducible (deterministic)
Achha jab hyperparameters ke clear discrete choices hon (e.g., activation functions: ReLU, tanh, sigmoid)

Limitations of Grid Search

Additional Limitation: Grid search resolution waste karta hai. Agar aap learning rate ko 5 values aur batch size ko 5 values dete hain, toh 25 combinations milti hain. Lekin agar learning rate zyada important hai, toh aap learning rate ke liye 15 values aur batch size ke liye 3 chahenge (phir bhi 45 combinations, lekin important dimension ka better coverage).

Random Search: Efficient Sampling

How Random Search Works

Step-by-step:

Har hyperparameter ke liye distributions define karein:
- Learning rate: $α \sim LogUniform (1 0^{- 4}, 1 0^{- 1})$
- Regularization: $λ \sim LogUniform (1 0^{- 3}, 1 0^{1})$
- Dropout: $p \sim Uniform (0.1, 0.5)$
$n$ random configurations sample karein (e.g., 60 samples)
Har sample ke liye:
- Un hyperparameters ke saath model train karein
- Validation set par evaluate karein
Best configuration select karein
(Optional) Zoom in: best region ke aas-paas distributions narrow karein aur zyada sample karein

Random Kyun? First principles se derivation:

Ek 2D hyperparameter space consider karein jahaan hyperparameter $h_{1}$ important hai aur $h_{2}$ unimportant hai.

Grid search with budget of 9 trials:

$h_{1}$ ke liye 3 values: ${a, b, c}$
$h_{2}$ ke liye 3 values: ${x, y, z}$
Tries: $(a, x), (a, y), (a, z), (b, x), (b, y), (b, z), (c, x), (c, y), (c, z)$
Important $h_{1}$ ke liye try ki gayi unique values: Sirf 3 values $(a, b, c)$

Random search with budget of 9 trials:

9 random $(h_{1}, h_{2})$ pairs sample karein
Har sample independently continuous distribution se $h_{1}$ choose karta hai
Important $h_{1}$ ke liye try ki gayi unique values: 9 alag values (sab distinct)

Key insight: Random search har dimension mein zyada coverage deta hai. $k$ dimensions mein $n$ trials ke liye:

Grid with $n^{1/ k}$ values per dimension: har hyperparameter ke liye sirf $n^{1/ k}$ unique values try karta hai
Random: har hyperparameter ke liye $n$ unique values try karta hai (expectation mein)

Mathematical justification: Agar objective function hai:

f (h_{1}, h_{2}) = g (h_{1}) + ϵ (h_{2})

jahaan $g$ important hai aur $ϵ$ noise hai, toh $n$ random points sample karne se $h_{1}$ ke $n$ alag values ka evaluation milta hai, jabki $n \times n$ grid sirf $n$ alag $h_{1}$ values evaluate karta hai.

Worked example Random Search Example

Task: Same SVM tuning problem. Budget: 60 trials (grid search $4 \times 4 \times 4$ grid ke jaisa). Distributions:

C ~ LogUniform(0.01, 1000)      # Wide range
gamma ~ LogUniform(0.001, 10)   # Wide range

Process:

Trial 1: Sample $C = 0.73, γ = 0.042$ → Train → Score = 0.87
Trial 2: Sample $C = 15.2, γ = 0.0089$ → Train → Score = 0.91
Trial 3: Sample $C = 2.1, γ = 0.15$ → Train → Score = 0.93
...
Trial 60: Sample $C = 0.051, γ = 1.2$ → Train → Score = 0.81

Yeh step kyun? Har sample ek unique point explore karta hai. Hum grid tak limited nahi hain, isliye discover kar sakte hain ki $C = 2.1$ better kaam karta hai $C = 1$ ya $C = 10$ se (woh values jo hum grid mein try karte).

Result: Best config $C = 2.1, γ = 0.15$ hai jiska score 0.93 hai. Humne 60 unique $(C, γ)$ pairs explore kiye vs. grid mein sirf 16 unique combinations (agar hum 4×4 grid use karte).

Advantages of Random Search

High dimensions mein zyada efficient: Har hyperparameter ke liye zyada unique values try karta hai
Continuous spaces naturally handle karta hai: Discretize karne ki zarurat nahi
Parallelize karna aasaan: Saare trials independent hain
Kabhi bhi rok sakte hain: Agar 100 trials ka budget hai lekin 60 par results plateau kar jaayein, toh ruk sakte hain
Important/unimportant hyperparameter scenarios ke liye better: Automatically important dimensions par zyada coverage milti hai

When to Use Which?

Grid Search tab use karein jab:

Kam hyperparameters hon (≤3)
Discrete choices hon (e.g., optimizer type: 'adam' vs 'sgd')
Chota, well-understood search space ho
Har tried combination report karni ho (reproducibility requirements)

Random Search tab use karein jab:

Zyada hyperparameters hon (≥4)
Continuous hyperparameters hon
Bada ya unknown search space ho
Aapko shak ho ki kuch hyperparameters doosron se zyada important hain
Computational budget limited ho

Practical Implementation Details

Cross-Validation Integration

Dono methods ko performance estimate karne ke liye cross-validation use karni chahiye:

Configuration $h$ ke liye:

score (h) = \frac{1}{k} i = 1 \sum k metric (h, fold_{i})

Kyun? Ek single train/val split lucky ya unlucky ho sakti hai. CV is variance ko average out karta hai.

Worked example Grid Search with Cross-Validation

Setup: $α$ ke liye 3 values, $λ$ ke liye 4 values, 5-fold CV. Ek configuration ke liye process ( $α = 0.01, λ = 0.1$ ):

Fold 1: Folds 2,3,4,5 par train karein → Fold 1 par validate karein → Score = 0.85
Fold 2: Folds 1,3,4,5 par train karein → Fold 2 par validate karein → Score = 0.87
Fold 3: Folds 1,2,4,5 par train karein → Fold 3 par validate karein → Score = 0.83
Fold 4: Folds 1,2,3,5 par train karein → Fold 4 par validate karein → Score = 0.86
Fold 5: Folds 1,2,3,4 par train karein → Fold 5 par validate karein → Score = 0.84

Average score: $(0.85 + 0.87 + 0.83 + 0.86 + 0.84) /5 = 0.85$

Yeh step kyun? Is ek configuration ke liye 5 training runs chahiye. Hum yeh saari 12 configurations ke liye repeat karte hain, jisse $12 \times 5 = 60$ total training runs milte hain. Averaged score single split se zyada reliable hota hai.

Choosing Distributions for Random Search

Log-uniform un hyperparameters ke liye jo orders of magnitude span karte hain:

h \sim LogUniform (a, b) ⟹ lo g h \sim Uniform (lo g a, lo g b)

Example: Learning rate $1 0^{- 5}$ se $1 0^{- 1}$ tak.

Log-uniform kyun? Agar hum uniform use karein, toh hum $1 0^{- 1}$ ke paas (upper end par) zyada values sample karenge, lekin $1 0^{- 5}$ aur $1 0^{- 4}$ ke beech ka space utna hi important hai jitna $1 0^{- 2}$ aur $1 0^{- 1}$ ke beech. Log-uniform har order of magnitude ko equal probability deta hai.

Bounded hyperparameters ke liye Uniform: Example: Dropout probability 0.0 se 0.5 tak.

Discrete counts ke liye Integer uniform: Example: Hidden units ki sankhya 50 se 500 tak.

Nested Cross-Validation for Unbiased Evaluation

Common mistake Test Set Leakage Through Hyperparameter Tuning

Galat approach:

Data ko train aur test mein split karein
Train set par CV ke saath grid/random search use karein, best hyperparameters dhundein
Best CV score ko apne model ki performance ke roop mein report karein Yeh sahi kyun lagta hai: Aapne directly test set par kabhi train nahi kiya.

Problem: Aapne implicitly CV mein use ki gayi validation sets se "seekha". Kai configurations try karke, aap validation folds par overfit kar lete ho. Best CV score overly optimistic hota hai.

Yeh fail kyun karta hai: Validation sets ko decisions lene ke liye use kiya gaya (hyperparameters choose karna). Woh ab model ke independent nahi hain.

Fix: Nested cross-validation use karein:

Outer loop: Performance estimation ke liye K-fold CV
Inner loop: Hyperparameter selection ke liye cross-validation ke saath Grid/random search

Har outer fold ke liye, hyperparameters independently sirf us fold ke training data se select kiye jaate hain.

Nested CV formula unbiased performance estimate ke liye:

score_{unbiased} = \frac{1}{K} i = 1 \sum K score_{test} (h_{i}^{*})

jahaan $h_{i}^{*}$ sirf outer fold $i$ ke training data se paayi gayi best configuration hai.

Comparing Grid and Random Search

Bergstra & Bengio (2012) Theoretical Result

Theorem (informal): Ek hyperparameter space ke liye jahaan $d$ dimensions mein se sirf $k$ important hain, $n$ trials ke saath random search har important dimension mein $O (n)$ unique values sample karta hai, jabki $n$ trials ke saath grid search har dimension mein $O (n^{1/ d})$ unique values sample karta hai.

Proof sketch:

$n$ trials ke saath grid search: har dimension ke liye $n^{1/ d}$ values allocate karein → $O (n^{1/ d})$ coverage
Random search: har trial independently har dimension se sample karta hai → har dimension ko $O (n)$ unique samples milte hain

Implication: Jab $d$ bada ho aur $k ≪ d$ ho, toh random search exponentially zyada efficient hai.

Empirical Comparison

Study: Bergstra & Bengio ne various ML tasks (neural nets, deep belief networks) par test kiya.

Result: Random search ne grid search se 2-3× kam evaluations use karke optimal ke 3% andar configurations dhundein.

Kyun? Zyaatar tasks mein 5-10 total mein se sirf 1-3 important hyperparameters the. Random search ki better per-dimension coverage dominant rahi.

Connections

Cross-Validation - Har hyperparameter configuration ko reliably evaluate karne ke liye use hoti hai
Overfitting and Underfitting - Hyperparameters model complexity control karte hain, bias-variance tradeoff affect karte hain
Regularization - $λ$ ek common hyperparameter hai jo search kiya jaata hai
Learning Rate Scheduling - Learning rate $α$ aksar sabse important hyperparameter hota hai tune karne ke liye
Bayesian Optimization - Zyada advanced search jo objective ka surrogate model build karta hai
Ensemble Methods - Perfect hyperparameter tuning ki zarurat kam kar sakta hai models ko average karke
Training-Validation-Test Split - Framework jiske andar hyperparameter search operate karta hai
Early Stopping - Ek aur hyperparameter (patience) jo tune kiya ja sakta hai

Recall Ek 12-Saal ke Bachche ko Explain Karein

Imagine karein aap ek video game character ke liye best settings dhundne ki koshish kar rahe hain (speed, strength, defense). Aapke paas ek training mode hai jahaan aap alag combinations test kar ke apna score dekh sakte hain.

Grid search waise hai jaise har single combination try karna: speed=1 with strength=1, phir speed=1 with strength=2, etc. Agar aapke paas 3 settings mein se har ek ke liye 10 options hain, toh woh 10×10×10 = 1,000 tests hain! Bahut time lagta hai lekin aap definitely jo try kiya usmein se best combination dhundh lenge.

Random search waise hai jaise aankhein band karke randomly 1,000 baar settings pick karna. Silly lagta hai, lekin yahan trick hai: imagine karein speed bahut matter karti hai lekin defense zyada nahi. Grid search ke saath, aap sirf 10 alag speeds try kar sakte hain (kyunki aap apne tests saari settings mein spread kar dete hain). Lekin random search ke saath, saare 1,000 tests alag random speeds use karte hain! Toh aap important setting (speed) ko bahut better explore karte hain.

Lesson: Jab kuch cheezein doosron se zyada matter karti hain, toh randomly try karna actually systematic try karne se smarter ho sakta hai. Yeh waise hi hai jaise ek naye shehar ko randomly ghoomne se kabhi kabhi aisi cool jagahein milti hain jo map par nahi thi!

Flashcards

#flashcards/ai-ml

Hyperparameters kya hain aur woh model parameters se kaise alag hain? :: Hyperparameters woh settings hain jo training se pehle configure ki jaati hain (learning rate, regularization strength, tree depth) jo learning process control karti hain. Model parameters training ke dauran data se seekhe jaate hain (weights, biases). Hyperparameters choose karne padte hain, seekhe nahi jaate.

Grid search kya hai?

Grid search predefined grid of hyperparameter values se har combination ko exhaustively evaluate karta hai. k hyperparameters ke liye jinka n_i values hain, yeh ∏n_i models train karta hai aur best validation score wala configuration select karta hai.

Random search kya hai?

Random search specified distributions (uniform, log-uniform) se n trials ke liye hyperparameter combinations randomly sample karta hai. Yeh random configurations ke saath n models train karta hai aur best performer select karta hai.

High dimensions mein random search grid search se aksar zyada efficient kyun hai?

n trials aur d dimensions ke liye, grid search har hyperparameter ke liye sirf n^(1/d) unique values try karta hai, jabki random search approximately n unique values try karta hai. Jab d bada hota hai, n^(1/d) bahut chota ho jaata hai (e.g., 256^(1/4)=4 vs 256).

Random search ke liye log-uniform distribution kab use karni chahiye?

Log-uniform un hyperparameters ke liye use karein jo multiple orders of magnitude span karte hain (learning rate: 10^-5 se 10^-1 tak). Yeh ensure karta hai ki har order of magnitude ke liye equal sampling probability ho, jo uniform sampling se hone wale larger values ki taraf bias ko prevent karta hai.

Nested cross-validation kya hai aur yeh kyun zaroori hai?

Nested CV mein outer loop (performance estimation ke liye K-fold CV) aur inner loop (CV ke saath hyperparameter search) hota hai. Yeh test set leakage prevent karta hai jo tab hoti hai jab hyperparameter tuning ka best CV score report kiya jaata hai, jo overly optimistic hota hai kyunki validation sets ne model selection decision ko influence kiya.

3 hyperparameters ke saath grid search ki computational cost kya hai jinka 4, 5, aur 6 values hain aur 5-fold CV ke saath?

Total models = 4 × 5 × 6 = 120 configurations. 5-fold CV ke saath: 120 × 5 = 600 training runs.

Grid search hyperparameter space mein resolution kyun waste karta hai?

Grid search importance ki parwah kiye bina saare hyperparameters ko equal numbers of values allocate karta hai. Agar learning rate critical hai lekin batch size nahi, toh dono ko 5 values dena batch size par resolution waste karta hai. Better hoga learning rate ko 15 values aur batch size ko 3 dena.

Random search ke mukable grid search ka main advantage kya hai?

Grid search defined grid ke andar best configuration dhundne ki guarantee deta hai (exhaustive). Yeh deterministic aur reproducible hai. Chote discrete spaces (≤3 hyperparameters) ke liye clear choices ke saath achha hai.

100 trials ke saath random search ek important hyperparameter ke liye kitne unique values sample karta hai?

Approximately 100 unique values (har trial independently sample karta hai). Compare karein grid search se jo 4D space mein 100 trials ke saath: sirf 100^(1/4) ≈ 3.16 values per dimension.