M2-087M2: Classical Machine LearningEvaluation Metrics & Hyperparameter TuningMedium
⚡Flashcard Drill➔Mastery:

Comparing Grid Search, Random Search, and Bayesian Optimization

📐 Mathematical Definition
BO: max⁡ EI(x)=E[max⁡(0,f(x)−f∗)]\text{BO}:\ \max\ \mathrm{EI}(x)=\mathbb E[\max(0,f(x)-f^*)]
⚡ One-Sentence Core Answer
Grid search suffers from exponential dimensional explosion; Random search explores continuous spaces efficiently; Bayesian optimization constructs probabilistic surrogates to balance exploration and exploitation.

📌 Key Takeaways

  • •
    Grid search: exhaustive evaluation, catastrophic O(kd)O(k^d) exponential scaling with dimension dd
  • •
    Random search: statistically superior under low effective dimensionality, samples distinct values on every trial
  • •
    Bayesian optimization (GP/TPE): models P(y∣x)P(y|x) with Gaussian Processes or Parzen Estimators, guided by Acquisition Functions (EI, UCB)

📐 Mathematical Derivations

Theoretical comparisons: ① Why Random Search beats Grid Search: In typical hyperparameter tuning, only a small subset of hyperparameters have high effective importance (low intrinsic dimensionality). In a 3×33 \times 3 grid with 9 evaluations, only 3 distinct values are tested for each parameter. Random search tests 9 distinct values for every parameter across the same 9 trials, achieving triple the coverage density on the critical dimensions. ② Bayesian Optimization Framework: Given prior observations D1:t−1={(xi,yi)}\mathcal{D}_{1:t-1} = \{(x_i, y_i)\}, fit surrogate model f(x)∼GP(μ(x),k(x,x′))f(x) \sim \mathcal{GP}(\mu(x), k(x, x')). Compute the next point using an Acquisition Function such as Expected Improvement (EI): EI(x)=E[max⁡(0,f(x)−f(x+))]=(μ(x)−f(x+))Φ(Z)+σ(x)ϕ(Z)\text{EI}(x) = \mathbb{E}[\max(0, f(x) - f(x^+))] = (\mu(x) - f(x^+)) \Phi(Z) + \sigma(x) \phi(Z), where Z=μ(x)−f(x+)σ(x)Z = \frac{\mu(x) - f(x^+)}{\sigma(x)}. μ(x)\mu(x) drives exploitation, while uncertainty σ(x)\sigma(x) drives exploration.

🏭 Production Trade-offs

Practical tooling choice: ① Few iterations / cheap models: Random search is trivially parallelizable across clusters without synchronization overhead. ② Expensive models (Deep Learning / large tabular): Bayesian Optimization (Optuna TPE / Ray Tune) converges in significantly fewer trials. ③ Resource allocation: Combine Bayesian optimization with early-stopping pruning algorithms like Hyperband / ASHA.
⚠️ Common Interview Pitfalls
  • ✕
    Running high-dimensional grid search across 6+ hyperparameters, wasting compute on unpromising combinations
  • ✕
    Using Gaussian Process Bayesian Optimization in high dimensions (d>30d > 30) or with thousands of trials, where GP cubic complexity O(n3)O(n^3) stalls search
🎯 Interviewer Follow-up Inquiries
  • ?
    How does Tree-structured Parzen Estimator (TPE) scale better than Gaussian Process-based Bayesian Optimization?
  • ?
    How does the Successive Halving Algorithm (ASHA) prune unpromising hyperparameter configurations early?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

Explore the comprehensive technical article, exam cards, and global architecture tree.

← PreviousM2-086: Common Evaluation Metrics for Classification, Regression, and Ranking📋Back to BankNext →M2-088: Hyperparameter Importance Hierarchy and Efficient Tuning Strategies
中文速览与面试要点

比较网格搜索、随机搜索与贝叶斯优化

网格穷举但指数爆炸;随机搜索在高维更高效;贝叶斯优化用代理模型指导采样。

核心要点

  • 三种方法的对比:① 网格搜索 ——在每个超参的离散网格上穷举。缺点: 维度诅咒 ——p 个超参各取 k 个值需 k^p 次评估(p=5、k=5 时 3125 次);且若某些超参不重要,网格在它们上面的取值组合浪费了大量评估。② 随机搜索 (Bergstra & Bengio 2012)——在超参空间随机采样。 关键洞察 :若只有少数超参真正重要('低有效维度'),随机搜索在相同预算下能覆盖更重要超参的更多取值——因为网格在重要维度上的取值数被不重要维度'摊薄'。理论上随机搜索优于网格搜索,且实现简单、天然可并行。③ 贝叶斯优化 ——用 代理模型 (高斯过程或 TPE)建模'超参→性能'的函数,用 采集函数 (如 EI:期望改进)选择下一个评估点,平衡探索(不确定性高的区域)与利用(当前最优附近)。优点:在评估昂贵时(如训练大模型)样本效率最高;缺点:实现复杂、难以并行(每次选择依赖前次结果)、对高维(>20 维)效果下降。
  • 实践要点与选择:① 优先随机搜索 ——简单、可并行、在多数场景与贝叶斯优化接近;是默认起点。② 贝叶斯优化的适用 ——单次评估昂贵(数小时到数天)、维度较低( 早停加速 —— Hyperband 用'连续减半'(successive halving):先用小预算评估大量配置,淘汰差的,对好的加大预算; ASHA 是异步版本(无需等待全部完成,适合并行)。这类方法利用'差的配置在小预算下就能看出'的性质,比纯搜索快数倍。④ 参数空间的设定 ——学习率等参数应在 对数尺度 上搜索(数量级差异比线性差异更重要);并设置合理范围(过宽浪费预算)。⑤ 并行与异步 ——网格/随机天然并行;贝叶斯优化需特殊处理(如批量采集函数、异步 BO);Hyperband/ASHA 天然适合异步并行。⑥ 调参顺序 ——先调最重要的超参(学习率、正则强度、模型容量),再调次要的;可先粗后细(多阶段)。⑦ 随机种子的影响 ——小数据/小模型上方差大,需多次种子重复评估,否则调参会被噪声主导。
  • 随机搜索在低有效维度下接近最优
  • Hyperband/ASHA 用早停加速

常见陷阱

  • 在低维空间用网格搜索(随机搜索更高效)
  • 在线性尺度上搜索学习率(应对数尺度)