AutoML HPO 学习笔记(五)- BOHB

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  最近阅读了提出 BOHB[1] 算法的论文,它主要将 Bayes OptimizationHyperband 结合起来

HPO desiderata

  首先作者提出了 HPO(Hyperparamater Optimization)问题的几个 desiderata:

  • Strong Anytime Performance:要求 HPO 算法需要有很快的速度
  • Strong Final Performance:要求 HPO 算法需要有很好的性能
  • Effective Use of Parallel Resources:要求 HPO 算法可以并行
  • Scalability:要求 HPO 算法有很强的可拓展性
  • Robustness & Flexibility:要求 HPO 算法有很好的鲁棒性和灵活性
  • Simplicity:要求 HPO 算法要简洁,容易验证
  • Computational efficiency: 需要 HPO 算法提高的计算的效率,当 evaluation function 被简化后,acquisition function 也会成为性能的瓶颈

  作者指出 Bayes Optimization(BO)的问题主要是太慢,而 Hyperband 在 time budget 较小或者中等时,相比于 BO 和 random search,性能要好很多,但是当 time budget 很大时,因为 Hyperband 是基于随机采样 configuration 的,所以它的收敛速度会减慢,相比于 BO 和 random search,就没有那么大的优势了,而 BOHB 可以解决上述所有问题,实验如下所示:

BOHB

  下图是 Hyperband 使用 SuccessiveHalving 的算法,它对 budget 作了一个 trade-off:

  BOHB 的名字其实就是来自 Bayes Optimization(BO)和 Hyperband(HB),因此它的算法大体思想其实就是结合这两个算法。将 BO 结合进 Hyperband 主要是为了让 Hyperband 摆脱随机采样 configuration,让它也能利用到之前 run 过的那些 configuration,已达到更快的收敛速度。需要注意的是,论文里作者使用的 BO 是使用 TPE 方法的,并且作者指出这里的 TPE 也可以很容易的被其他的 GP-based BO 所替换。
  BOHB 中对 configuration 采样的伪代码如下:

  其中的公式 (2) 指的是: \[ \begin{aligned} l(\boldsymbol{x}) &=p(y<\alpha | \boldsymbol{x}, D) \\ g(\boldsymbol{x}) &=p(y>\alpha | \boldsymbol{x}, D) \end{aligned} \]   公式 (3) 指的是: \[ \begin{array}{l}{N_{b, l}=\max \left(N_{\min }, q \cdot N_{b}\right)} \\ {N_{b, g}=\max \left(N_{\min }, N_{b}-N_{b, l}\right)}\end{array} \]   \(N_b\) 指的是 the number of observations for budget b,公式 (3) 可以保证对于两个 densities 都有足够的 data points 去建模,当 data points 很少时,它们可能会有一些 overlap。
  可以看出过程很像 TPE,一个主要的不同点是,BOHB 中使用了 a single multidimensional KDE,而 TPE 中使用了 hierarchy of one-dimensional KDEs,这样是为了更好的处理 input space 里的 interaction effects。
  随着 optimazation 的进行,configuration 会在更大的 budget 上进行 evaluate,通过算法第二行我们可以看出,BOHB 总是挑选 \(|D_b|\) 最大,也就是 observation 最充足,这样可以最终通过依靠保真度最高的结果,避免因预算较小而得出的错误结论。
  算法中的 \(l^{\prime}(x)\),其实就是 \(l(x)\) 乘上一个 \(b_w\),这样对于 promising configurations,会更加鼓励 expolration,作者指出这会提升收敛,尤其是在 optmization 的后期阶段,因为这一阶段,对于 biggest budget,model 会经常被 query,但是很少被 update。
  还需要注意的是 \(\rho\),这是为了保证 HB 中的随机性,这样在经过 \(m \cdot\left(s_{m a x}+1\right)\) 次 SuccessiveHalving(SH) 后,\(b_{max}\) 上会有 \(\rho \cdot m \cdot\left(s_{m a x}+1\right)\) 个 random configuration 被 evaluate。每个 SH 消耗的一个 budget 至多为 \((s_{max} + 1) \cdot b_{max}\),与此同时,random search 相比 BOHB 在 largest budget 上 evaluate 了 \(\left(\rho^{-1} \cdot\left(s_{m a x}+1\right)\right)\) 倍的 configuration。这说明,在最坏的情况下(低保真的结果造成误导),BOHB 至多比 random search 慢 \(\rho\) 倍,但是还是可以保证最终收敛,HB 也可以保证。

Parallelization

  BOHB 的并行性主要是结合了 TPE 和 HB 的并行性:

  • TPE 的并行主要是利用多样性,利用 configuration 的 neighbour 去优化 EI 函数
  • HB 的并行主要有两方面,一方面是同时开始不同的的 iterations(也就是 \(s_{max}\)\(s_{max-1},...同时进行\)),另一方面是在每个 SH 里并行的 evaluate 每个 configuration。

  BOHB 结合两者的特点,有了这样的并行策略。
  首先从顺序执行 HB 的第一次 SH 开始(most aggresive,lowest budget),使用 HOBO 的采样算法采样 configuration,直到:

  1. all worker busy
  2. enough sampled configurations for this

  在第一种情况下中,我们只要有 worker 空闲,然后采样新的 configuration,在第二种情况中,我们开始并行运行下一个SH,并继续采样新的 configuration。observation \(D\)(以及由此产生的模型)在所有 SH runs 共享。BOHB 也是 anytime 的算法,可在每个时间点跟踪实现最佳验证性能的配置,也可以给定 SH run 的 maximum budget。

Refer

[1] Falkner, Stefan, Aaron Klein, and Frank Hutter. "BOHB: Robust and efficient hyperparameter optimization at scale." arXiv preprint arXiv:1807.01774 (2018).

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. HPO desiderata
  3. 3. BOHB
    1. 3.1. Parallelization
  4. 4. Refer
  5. 5. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...