Bayesian hyperparameter optimization

The Core Problem

WHY this approach? Training models is expensive—each evaluation of $f(\lambda)$ might take hours. We can't afford grid search when we have 10+ hyperparameters. Bayesian optimization makes every evaluation count by balancing:

• Exploitation: search near known good configurations
• Exploration: try unexplored regions that might be better

Derivation from First Principles

Step 1: The Surrogate Model (Gaussian Process)

WHAT: We model the unknown function $f(\lambda)$ as a Gaussian Process (GP).

WHY: A GP gives us not just a prediction, but also uncertainty—crucial for balancing exploration/exploitation.

A Gaussian Process is defined by:

• Mean function $\mu(\lambda)$: our best guess of $f(\lambda)$
• Covariance (kernel) function $k(\lambda, \lambda')$: how corelated $f(\lambda)$ and $f(\lambda')$ are

Starting from scratch: After observing $n$ evaluations $\mathcal{D}_n = \{(\lambda_i, y_i)\}_{i=1}^n$ where $y_i = f(\lambda_i) + \epsilon$ (noise), the GP posterior at new point $\lambda$ is:

$\mu_n(\lambda) = \mu(\lambda) + k^T K^{-1} (y - \mu)$ $\sigma_n^2(\lambda) = k(\lambda, \lambda) - k(\lambda)^T K^{-1} k(\lambda)$

Derivation:

1. Prior: $f \sim \mathcal{GP}(\mu, k)$ means for any set of points, $f$ is multivariate Gaussian
2. Likelihood: $y | f \sim \mathcal{N}(f, \sigma_{noise}^2 I)$
3. Posterior (Bayes' rule): Given observations, the posterior is also a GP with updated mean and covariance

Here:

• $k(\lambda) = [k(\lambda, \lambda_1), \ldots, k(\lambda, \lambda_n)]^T$ (vector)
• $K$ is the $n \times n$ covariance matrix $K_{ij} = k(\lambda_i, \lambda_j)$
• $y = [y_1, \ldots, y_n]^T$, $\mu = [\mu(\lambda_1), \ldots, \mu(\lambda_n)]^T$

WHY these formulas? The GP posterior is the conditional distribution of a joint Gaussian. The mean $\mu_n(\lambda)$ is our prediction, and $\sigma_n^2(\lambda)$ quantifies uncertainty—high where we haven't sampled.

WHY this kernel? It encodes smoothness: nearby hyperparameters should have similar performance. Small $\ell$ → wiggly function, large $\ell$ → smooth.

Step 2: The Acquisition Function

WHAT: An acquisition function $\alpha(\lambda)$ scores how "valuable" it is to evaluate $f$ at $\lambda$ next.

WHY: The GP gives us $\mu_n(\lambda)$ and $\sigma_n(\lambda)$ everywhere. We use these to pick $\lambda_{n+1}$ that best balances exploration and exploitation.

Expected Improvement (EI)

Intuition: How much do we expect $f(\lambda)$ to improve over the current best observation $f^+ = \max_{i=1}^n y_i$?

Derivation from scratch: The improvement at $\lambda$ is $I(\lambda) = \max(0, f(\lambda) - f^+)$. Since $f(\lambda)$ is a random variable (GP posterior), we compute: $\text{EI}(\lambda) = \mathbb{E}[I(\lambda)] = \mathbb{E}[\max(0, f(\lambda) - f^+)]$

With $f(\lambda) \sim \mathcal{N}(\mu_n(\lambda), \sigma_n^2(\lambda))$, we can derive:

(\mu_n(\lambda) - f^+) \Phi(Z) + \sigma_n(\lambda) \phi(Z) & \text{if } \sigma_n(\lambda) > 0 \\ 0 & \text{if } \sigma_n(\lambda) = 0 \end{cases}$$ where: $$Z = \frac{\mu_n(\lambda) - f^+}{\sigma_n(\lambda)}$$ and $\Phi, \phi$ are the standard normal CDF and PDF. **Derivation steps:** 1. Let $u = f(\lambda) - f^+$, then $u \sim \mathcal{N}(\mu_n(\lambda) - f^+, \sigma_n^2(\lambda))$ 2. $\mathbb{E}[\max(0, u)] = \int_0^\infty u \cdot \frac{1}{\sigma_n} \phi\left(\frac{u -(\mu_n - f^+)}{\sigma_n}\right) du$ 3. Substitute $z = \frac{u - (\mu_n - f^+)}{\sigma_n}$, $u = \sigma_n z + (\mu_n - f^+)$ 4. After integration (using $\int z\phi(z)dz = -\phi(z)$), we get the formula above **WHY this works:** - High $\mu_n(\lambda)$ (exploitation): likely to be good - High $\sigma_n(\lambda)$ (exploration): uncertain, might be great - The formula **automatically balances** both via $\Phi(Z)$ and $\phi(Z terms #### Alternative: Upper Confidence Bound (UCB) $$\text{UCB}(\lambda) = \mu_n(\lambda) + \kappa \sigma_n(\lambda)$$ **WHY:** Directly combines mean (exploitation) and standard deviation (exploration). $\kappa$ controls the tradeoff (typically $\kappa \approx 2$). ### Step 3: The Algorithm **Bayesian Optimization Loop:** ``` 1. Initialize with random samples: D_0 = {(λ_i, y_i)} for i=1..n_init 2. For iteration n = n_init, n_init+1, ..., n_max: a. Fit GP to D_n → get μ_n(λ), σ_n(λ) b. Find λ_next = argmax α(λ) (optimize acquisition function) c. Evaluate y_next = f(λ_next) d. Update D_{n+1} = D_n ∪ {(λ_next, y_next)} 3. Return λ* = argmax_{λ ∈ D} f(λ) ``` **WHY each step:** - **a.** GP learns from all past evaluations - **b.** Acquisition function proposes the most informative next point - **c.** We pay the cost of one expensive evaluation - **d.** GP gets updated with new data, uncertainty shrinks around explored regions ## Worked Examples > [!example] > **Example 1: Tuning Neural Network Learning Rate** **Setup:** Optimize validation accuracy of a neural net w.r.t. learning rate $\lambda \in [10^{-5}, 10^{-1}]$ (log scale). **Iteration 1:** Random initialization evaluates: - $\lambda_1 = 0.01$, $y_1 = 0.85$ - $\lambda_2 = 0.001$, $y_2 = 0.70$ - $\lambda_3 = 0.05$, $y_3 = 0.80$ Current best: $f^+ = 0.85$ **Iteration 2:** Fit GP with RBF kernel. At $\lambda = 0.005$: - $\mu_2(0.005) = 0.83$ (interpolates between 0.001 and 0.01) - $\sigma_2(0.005) = 0.06$ (some uncertainty) - $Z = \frac{0.83 - 0.85}{0.06} = -0.33$ - $\text{EI}(0.005) = (0.83 - 0.85) \Phi(-0.33) + 0.06 \phi(-0.33)$ - $= -0.02 \cdot 0.37 + 0.06 \cdot 0.38 = -0.0074 + 0.0228 = 0.0154$ At $\lambda = 0.08$ (unexplored): - $\mu_2(0.08) = 0.78$ (extrapolating, but uncertain) - $\sigma_2(0.08) = 0.12$ (high uncertainty) - $Z = \frac{0.78 - 0.85}{0.12} = -0.58$ - $\text{EI}(0.08) = -0.07 \cdot 0.28 + 0.12 \cdot 0.33 = -0.0196 + 0.0396 = 0.02$ **WHY this step?** $\text{EI}(0.08) > \text{EI}(0.005)$ despite lower mean because uncertainty is higher—exploration wins. **Action:** Evaluate $\lambda_4 = 0.08$, get $y_4 = 0.87$ → new best! **Iteration 3:** GP now knows0.08 is good, focuses search around it with lower uncertainty there. > [!example] > **Example 2: Multi-dimensional — SVM with C and γ** **Setup:** Optimize SVM with: - $C \in [10^{-2}, 10^3]$ (regularization) - $\gamma \in [10^{-4}, 10^1]$ (RBF kernel width) After 5 random points, GP learns: - High $C$, low $\gamma$: overfits (accuracy 0.75) - Low $C$, high $\gamma$: underfits (accuracy 0.70) - Mid-range: best so far $C=10, \gamma=0.1$, accuracy 0.88 **Acquisition function** suggests $C=15, \gamma=0.08$ (near best but unexplored): - $\mu(\text{this point}) = 0.87$ (close to 0.88) - $\sigma(\text{this point}) = 0.08$ (moderate uncertainty) - High EI because it's in a promising region with some uncertainty **Evaluate:** Get0.89 → new best. **WHY it works:** Instead of grid-searching $50 \times 50 = 2500$ points, Bayesian optimization finds near-optimal in ~20-30 evaluations by **learning the landscape**. ## Common Mistakes > [!mistake] > **Mistake 1: Using default GP hyperparameters without tuning** **Why it feels right:** "The GP will figure it out from the data." **The problem:** Poor kernel hyperparameters (e.g., wrong length scale) → bad surrogate model → bad acquisition decisions. If $\ell$ is too large, the GP is over-smooth and mises important variations. If too small, it's over-wiggly and doesn't generalize. **Steel-man:** You want the algorithm to be automatic and not require meta-tuning. **The fix:** ==Optimize kernel hyperparameters== by maximizing the **marginal likelihood** (evidence): $$\log p(y | \lambda_1, \ldots, \lambda_n, \theta) = -\frac{1}{2} y^T K^{-1} y - \frac{1}{2} \log |K| - \frac{n}{2} \log 2\pi$$ where $\theta = \{\sigma_f, \ell, \sigma_{noise}\}$. Most libraries (e.g., scikit-optimize, GPyOpt) do this automatically, but verify it's enabled. > [!mistake] > **Mistake 2: Not normalizing/scaling hyperparameters** **Why it feels right:** "I'll just use the raw ranges [0.001, 100]." **The problem:** GP kernels compute distances $\|\lambda - \lambda'\|$. If one hyperparameter spans [0, 1] and another spans [1, 10000], the second dominates distance calculations, making the GP think they're always far apart. **Steel-man:** The math should handle any scale. **The fix:** ==Transform to uniform scale== before optimization: - Log-scale for learning rates, regularization: $\tilde{\lambda} = \log_{10} \lambda$ - Standardization for mixed types: $\tilde{\lambda} = (\lambda - \mu) / \sigma$ Libraries often have `Real(..., prior='log-uniform')` options. > [!mistake] > **Mistake 3: Insufficient initialization** **Why it feels right:** "Bayesian optimization is smart, I'll start with 2-3 points." **The problem:** GP needs enough data to build a reasonable model. With too few points, the surrogate is unreliable and acquisition function might propose bad points. The rule of thumb: **at least $2d$ to $5d$** random initializations where $d$ is the dimensionality. **Steel-man:** You want to minimize total evaluations, so start small. **The fix:** Balance initialization and optimization phases: - **Low-D** ($d \leq 5$): 5-10 random points - **High-D** ($d > 5$): $3d$ to $5d$ random points or use **Sobol sequences** (quasi-random) for better coverage ## Connections to Other Methods **Connects to:** - [[2.6.11-Grid-Search]] — BO dramatically reduces evaluations (30 vs. 10,000) - [[2.6.12-Random-Search]] — BO uses random initialization but learns from results - [[3.4.2-Gaussian-Processes]] — GP is the probabilistic model powering BO - [[4.3.1-Multi-Armed-Bandits]] — Acquisition functions solve exploration-exploitation (like UCB in bandits) - [[2.6.15-Neural-Architecture-Search]] — BO can optimize discrete choices (architectures) with appropriate kernels **Contrast with:** - **Evolutionary algorithms** (genetic algorithms): population-based, no probabilistic model - **Gradient-based meta-optimization** (MAML): requires differentiable hyperparameters - **Hyperband**: adaptive resource allocation (early stopping), complementary to BO ## Key Formulas Summary > [!formula] > **Gaussian Process Posterior:** > $$\mu_n(\lambda) = k(\lambda)^T K^{-1} y, \quad \sigma_n^2(\lambda) = k(\lambda, \lambda) - k(\lambda)^T K^{-1} k(\lambda)$$ **Expected Improvement:** $$\text{EI}(\lambda) = (\mu_n(\lambda) - f^+) \Phi(Z) + \sigma_n(\lambda) \phi(Z), \quad Z = \frac{\mu_n(\lambda) - f^+}{\sigma_n(\lambda)}$$ **RBF Kernel:** $$k(\lambda, \lambda') = \sigma_f^2 \exp\left(-\frac{\|\lambda - \lambda'\|^2}{2\ell^2}\right)$$ > [!recall]- > **Explain to a 12-year-old:** Imagine you're trying to find the yummiest cookie recipe. You can change things like butter amount, sugar amount, and baking time. But making cookies takes time! You can't try every combination. So here's the trick: after you bake a few batches and taste them, you start remembering which combinations were good and which weren't. Then, instead of just guessing randomly, you think: "Hmm, the ones with more butter were tasty, but I haven't tried MUCH more butter yet—let me try that." Or: "Medium sugar was okay, but I'm really unsure about low sugar, so let me check that." Bayesian optimization is like having a smart notebook that: 1. Remembers all your past cookie experiments 2. Guesses how good any new combination might be (that's the GP) 3. Tells you which experiment to do next to learn the most (that's the acquisition function) It helps you find the best recipe with the fewest batches of cookies! > [!mnemonic] > **BO = "Best Optimized"** > - **B**ayes: Use probability to model the unknown function > - **O**ptimize: Acquisition function picks next point > - **GP** (Gaussian Process): "**G**ood **P**redictions" with uncertainty > - **EI** (Expected Improvement): "**E**xplore **I**nteligently" Think: **"Build model, Optimize acquisition, Get next point"** → BO-loop ## Practical Implementation ```python from skopt import gp_minimize from skopt.space import Real, Integer def objective(params): lr, batch_size = params # Train model, return validation accuracy accuracy = train_and_evaluate(lr, batch_size) return -accuracy # Minimize negative accuracy space = [ Real(1e-5, 1e-1, prior='log-uniform', name='lr'), Integer(16, 256, name='batch_size') ] result = gp_minimize( objective, space, n_calls=50, # Total evaluations n_initial_points=10, # Random initialization acq_func='EI', # Expected Improvement random_state=42 ) best_params = result.x best_score = -result.fun ``` **WHY this code structure:** - `prior='log-uniform'` handles wide range learning rates - `n_initial_points` ensures good GP initialization - Minimize **negative** accuracy (libraries minimize by convention) #flashcards/ai-ml What is the core idea of Bayesian hyperparameter optimization? :: Build a probabilistic surrogate model (Gaussian Process) of the objective function, then use an acquisition function to intelligently select the next hyperparameter configuration to evaluate, balancing exploration and exploitation. What are the two components of a Gaussian Process? ::: Mean function μ(λ) which predicts the objective value, and covariance/kernel function k(λ, λ') which models similarity between points and quantifies uncertainty. Write the Expected Improvement formula :: EI(λ) = (μ_n(λ) - f^+) Φ(Z) + σ_n(λ) φ(Z), where Z = (μ_n(λ) - f^+)/σ_n(λ), f^+ is current best, Φ is standard normal CDF, φ is PDF. What does the acquisition function balance? ::: Exploitation (searching near known good configurations with high μ) and exploration (trying uncertain regions with high σ). Why use log-scale for hyperparameters like learning rate? ::: Learning rates span orders of magnitude (1e-5 to 1e-1). On log scale, distances are meaningful—moving from 0.01 to 0.001 is as significant as 0.001 to 0.001. This prevents the GP kernel from treating all small learning rates as "equally distant." What is the RBF kernel formula and what does the length scale ℓ control? ::: k(λ, λ') = σ_f² exp(-||λ - λ'||²/(2ℓ²). Length scale ℓ controls smoothness: small ℓ means function varies quickly (nearby points can differ), large ℓ means slow variation (distant points are similar). How many random initialization points should you use for d hyperparameters? ::: At least 2d to 5d points, or 5-10 for low dimensions. This ensures the GP has enough data to build a reliable surrogate model before optimization begins. How does UCB (Upper Confidence Bound) acquisition work? ::: UCB(λ) = μ_n(λ) + κσ_n(λ), directly combining exploitation (mean) and exploration (std dev). κ ≈ 2 controls the tradeoff—higher κ means more exploration. Why optimize GP kernel hyperparameters during Bayesian optimization? ::: Poor kernel parameters (wrong length scale) lead to bad surrogate models. We maximize marginal likelihood log p(y|λ₁...ₙ, θ) to find kernel hyperparameters θ that best explain observed data, improving GP predictions. What advantage does Bayesian optimization have over grid search? ::: BO learns from evaluations and focuses search on promising regions, typically finding near-optimal configurations in 20-50 evaluations instead of thousands required by grid search, crucial when training is expensive. ## 🖼️ Concept Map ```mermaid flowchart TD Problem[Expensive black-box f lambda] -->|motivates| BayesOpt[Bayesian Optimization] GridRandom[Grid and Random search] -->|inefficient baseline| BayesOpt BayesOpt -->|goal| Argmax[Find lambda star maximizing f] BayesOpt -->|builds| Surrogate[Surrogate model] Surrogate -->|implemented as| GP[Gaussian Process] GP -->|defined by| Mean[Mean function mu] GP -->|defined by| Kernel[Covariance kernel k] Data[Observations D_n] -->|Bayes rule| GP GP -->|yields| Posterior[Posterior mean and variance] Posterior -->|feeds| Acq[Acquisition function] Acq -->|balances| Explore[Exploration vs Exploitation] Acq -->|selects next| NextEval[Next lambda to evaluate] NextEval -->|updates| Data ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Bayesian Hyperparameter Optimization ka core idea yeh hai ki hum hyperparameters (jaise learning rate, batch size) ko tune karte waqt **har experiment seekhte hain**. Agar tumne 5 models train kiye aur dekha ki learning rate 0.01 pe accuracy 85% hai, to aglibaar randomly koi bhi value try karne ke bajaye, algorithm **intelligently** decide karta hai ki "0.01 ke as-pas ya unexplored regions mein kahan try karna chahiye." > > Iska mechanism simple hai: ek **Gaussian Process (GP)** banate hain jo past results ke basis pe predict karta hai ki kisi bhi hyperparameter configuration performance kya hogi, aur **kitna uncertainty** hai. Phir ek **acquisition function** (jaise Expected Improvement) use karte hain jo decide karta hai: "High mean (exploitation) ya high uncertainty (exploration)—dono mein se kaunsa zyada useful hai?" Jo point sabse zyada valuable hai, wahi next evaluate karte hain. > > Yeh technique tab bahut powerful hai jab training expensive ho—suppose ek model train karne mein 2 ghante lagte hain. Grid search mein shayad 1000 configurations try karni padein (2000 ghante!), lekin Bayesian optimization mein sirf 20-30 trials mein near-optimal mil jata hai. Industry mein yeh **AutoML pipelines** aur **neural architecture search** mein heavily use hota hai, kyunki yeh compute cost drastically reduce kar deta hai. > > Ek aur important baat: hyperparameters ko sahi scale pe rakhna zaroori hai. Learning rates jaise parameters log-scale pe hone chahiye (0.001, 0.01, 0.1), warna GP kernel sahi distances calculate nahi kar payega aur optimization bekaar ho jayega. Libraries jaise `scikit-optimize` ya `Optuna` yeh sab handle kar leti hain, but concept samajhna zaroori hai taki tum debug kar sako jab kuch galat ho. ![[audio/2.6.14-Bayesian-hyperparameter-optimization.mp3]]