Xin Qiao

/home

/tools

/obsidian

~/Obsidians/ Kandasamy2020TuningHyperparametersGrad

Kandasamy2020TuningHyperparametersGrad

Intro #

  • blackbox optimization 的一个典型例子是 hyper parameter tuning
    • 一般不具有 convex 性质，并且没有梯度信息，并且带有 noise
  • BO 的思想是基于当前的 posterior 构建一个 acquisition function，找到使得这个 function 最大的测量点，测量的结果用于更新 posterior
  • this work (Dragonfly) 的作用是在 BO 之外增加了一些 utility 使其 scalable，比如处理高维空间输入、利用 low fidelity 信息等
  • 此外还更新了随机化方法，使 BO 方法不依赖于其本身的超参

GP and BO #

  • Gaussian Process 中任何有限点的集合都是 Gaussian 分布，一般 kernel function 定义为 Squared Exponential 或者 Matérn 形式
    • 被观测值更新的 posterior 仍然是 GP 形式
  • BO 的核心是 acquisition function，其中两种形式是 Thompson sampling 和 GP-UCB
    • GP-UCB (eq3) 的两项体现了对 exploration/exploitation 的最大化的追求，二者分别代表「模型不确定性更高」和「模型的函数值更高」

Scale up #

  • BO 在高于 10 维的空间上表现不佳，原因是计算复杂度的增加
    • 假设高维空间中的函数具有 additive structure，可以分解为多个低维空间的子函数之和
    • solution 是使用 ADD-GP-UCB 函数进行 acquisition
  • low fidelity 信息指的是超参数调优过程中用小部分数据/低迭代次数得到的不完全准确的信息
    • 在 fidelity space 中建模的方法称作 BOCA
  • 将 BO 的应用空间从 Euclidean 向描述 Neural Network 的 neural architecture search 转变
    • NASBOT 框架可以度量两个 NN 之间的距离，并且应用变异/演化算法寻找最优架构
      • 假设每一层网络具有一定的质量，距离定义为将一个网络的质量搬运到另一个网络的最小代价
  • 还做了并行化处理，并且偏好异步处理

Robustness #

  • 核心的想法是调整 BO 自身的随机化方法和超参以增强 robustness
  • acquisition function 的选择策略是：最初给每种 function 赋予相同的权重并且随机选择，之后根据每次采集的效果奖励/惩罚所用的函数（修改对应权重）
  • 超参一般采用最大似然或者 posterior 方式进行调整
    • 最大似然倾向于 exploitation，而后验积分的方式倾向于 exploration
    • this work 的处理方式是随机化混合两种方法（同样采取类似 weight 的方式）

Dragonfly #

  • domain 包括 Euclidean 以及整数、discrete、Neural Network 等空间
  • kernel 包括 squared exponential 以及 Matérn kernel，默认值采取了一般认为性能最佳的 2.5 Matérn kernel
    • 对于离散变量采用 Hamming kernel
  • 初始化采用 Latin hypercube sampling
  • Algorithm1 给出了详细的算法过程描述

Experiments #

  • 列出了一些和 dragonfly 进行对比的 blackbox 优化工具：EA、HyperOpt、SMAC
  • 预设的优化问题来自于一些低维测试函数：Branin、Hartmann3、Park1/2
  • benchmark 来自 simple regret：算法找到的最优值和实际最优值之间的差值
  • tab1 证明 dragonfly 的效果是最优的
  • 在真实 astrophysics 问题上进行了检验
    • 在 9D euclidean 空间中优化宇宙学参数以实现 LRG 观测的最大似然（这里指的是 SDSS LRG）
    • 用 type Ia SNe 推断 Hubble constant、DM/DE fraction 三个参数，限定相同的 CPU wall time

Thoughts #

  • 宇宙学参数的分布一般都是比较规则的高维椭球，直接跑 MCMC 都没有问题

Supplement #

GP #

  • https://aistudio.google.com/prompts/1c5r6xqorzVsoGWISQ0hux2loJLidfWG8
  • 随机过程指的是一个函数，在每个固定的时间/空间点都类似一个随机变量
    • 相当于为函数而非单个数字建立概率模型
  • 可以理解为无限维度的多元 Gaussian 分布，由均值 $m(x)$ 和 kernel $k(x,x’)$ 描述，后者可以理解为无限维的 covariance matrix
  • 最常见的应用是 GP Regression，也就是已知一系列函数值，推断函数在某一点的取值
    • 可以得到对应点的完整分布　
    • 一般 kernel function 有特定的形式，比如 squared exponential (radial basis)，包括 length scale 和 signal variance 两个超参数，这些超参数可以通过最大似然来优化
  • kernel function 的选择非常重要，不合适的函数会导致 inductive bias
    • squared exponential 的假设是函数是平滑变化的
    • Matérn 自由度更高，超参 $\nu$ 可以控制函数的光滑程度，比如 $\nu=1/2$ 的时候产生连续而不可导的函数
    • 一些 kernel 具有周期性质
    • kernel function 可以组合发挥作用
  • 在 BO 上的具体应用步骤是
    • 假设存在一个函数 $f(x)$，目标是找到最大化这个函数的 $x$
    • 首先用全部数据训练一个模拟的 GP model
    • 根据 acquisition function 决定下一次测量在哪里进行
      • acquisition function 的输入由 GP 给出
      • 这个 function 会倾向于在均值较高、不确定度较大（平衡 exploration/exploitation）的位置进行计算/采集
  • 最后 Mercer/Bochner 定理的部分跳过了，总之就是 kernel 和 Fourier 变换有很强的关联（kernel 和 spectral density 通过 Fourier 变换联系起来）

Benchmark for optimization #

Multi-Armed Bandit #

  • exploration/exploitation 的平衡是 optimization 中一个非常基本的问题
  • 常见的 solution 包括贪心算法、UCB 以及 TS
back to top