AutoML HPO 学习笔记(四)- Hyeperband

  |     |   本文总阅读量:

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

引言

  最近阅读了提出 Hyperband[1] 算法的论文,它解决的问题主要是在 hyperparameter optimization 中如何加快 random search,途径是通过一个自适应的资源分配机制和 early-stopping 的机制,本文对它们做一些简单的记录,原文中有许多章节在进行数学推理,这里我们这边就不介绍了,主要还是记录下它的思想。

Hyperparamater Optimization 和 Bandit Problems

  多臂赌博机问题这里就不说了,在论文里,作者把 hyperparameter optimization 问题看作是一个 pure-exploration NIAB(Non-stochastic Infinite-Armed Bandit) 问题,大体意思就是多臂赌博机的臂的数量是无限的,每个臂代表的参数都是随机采样得到的。论文中还有些关于 NIAB 证明的一些数学原理,这里就不多说了,有兴趣可以看看原文。

SuccessiveHalving

  SuccessiveHalving 是之前提出来的一种 hyperparameter optimization 的算法,它的思想其实很简单,就是给定一个 time budget \(B\),然后均匀分配给一系列的 configurations,evaluate 这些 configurations,丢掉表现最差的一半,继续 evaluate 剩下的一半,再不断丢弃一半,直到只剩一个 configuration。
  SuccessiveHalving 也有问题,它需要 configurations 总共的个数 \(n\) 来作为输入,这样平均每个 configuration 就被分配了 \(B / n\) 的资源,这也其实就带来了两个问题:

  • 如果 \(n\) 很大,每个 configuration 平均分到的资源太少了,是否足够去 train 呢?
  • 如果 \(n\) 很小,每个 configuration 平均分到的资源太多了,是否是一种浪费呢?

  所以用户往往需要做个 trade-off 来缓解这两个问题,下图是一个 trade-off 的示意图,主要用到了 envelope function 来描述。

Hyperband

  Hyperband 试图解决这个问题,具体伪代码如下:

  算法还是非常容易理解的,整个 Hyperband 其实就是一个两层循环,作者把内层循环称作一个 bracket,它也就是一次 SuccessiveHalving,下面列出这个算法中的几个关键参数和方法:

  • \(R\):单个 configuration 所能分配的最大预算
  • \(r\):单个 configuration 实际所能分配的预算
  • \(s_{\mathrm{max}}\):用来控制总预算的大小
  • \(B\):外层循环每次总共的预算,\(B=(s_{\mathrm{max}} + 1)R\),一次 Hyperband 花的总时间为 \((s_{\mathrm{max}} + 1)B\)
  • \(\eta\):用于控制每次迭代后淘汰参数设置的比例
  • get_hyperparameter_configuration(n):采样得到\(n\)组不同的超参数设置,这里使用的事随机均匀采样
  • run_then_return_val_loss(t, r):根据指定的参数设置和预算计算 valid loss
  • top_k(configs, losses, k):表示需要选择最好的 \(k(k = n_{i} / \eta)\) 个configuration

  bracket 其实就是对 \(n\)\(B / n\) 来做trade-off。Hyperband 是从 \(s_{\mathrm{max}}\) 开始的,可以使 \(n\) 最大化 exploration,这样可以保证至少有一个 configuration 用到了 \(R\) 资源。之后 \(n\)\(\eta\) 作指数衰减,到 \(s = 0\) 时,每个 configuration 都可以用到 \(R\) 资源。
  上面我们的资源都是用运行时间来表示,其实通常还可用数据集采样和特征采样来作为资源。
  我们可以看到 \(R\)\(\eta\) 是 Hyperband 唯二需要输入的参数,也是会影响 Hyperband 速度的两个参数,我们来分别分析下它们的取值。

\(R\)

  \(R\) 应当有个上界,但是这个上界往往很难给出。

infinite horizon version

  对于 \(R\) 不可知时,Hyperband 也提供了一个 infinite horizon 的版本,它结合了我们之前提到的 NIAB 的思想,伪代码如下:

  在这种算法下,\(B \in\{2,4,8,16, \ldots\}\) 每次都被翻倍了,\(n \in\left\{2^{k}: k \in\left\{1, \ldots, \log _{2}(B)\right\}\right\}\)也可以取到不同的值,\(R=\frac{B}{2 \log _{2}(n)}\) 也随着 \(B\) 增长。

finite horizon version

  既然有 infinite horizon version,那么肯定有 finite horizon version,它更 standard 一些,伪代码如下:

\(\eta\)

  \(\eta\) 往往跟用户的经验有关,因为 \(\eta\) 会影响 bracket 的个数。

Conclusion

  Hyperband 的提出主要是为了解决 Successive 的一个 trade-off 问题,也就是资源和需要被 evaluate 的 configuration 个数的问题,即 trade-off \(B\)\(B/n\),它可以动态的选择一个合适的 configuration 的个数去做 SuccessiveHalving。

Refer

[1] Li, Lisha, et al. "Hyperband: A novel bandit-based approach to hyperparameter optimization." arXiv preprint arXiv:1603.06560 (2016).

相关内容


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



文章目录
  1. 1. 引言
  2. 2. Hyperparamater Optimization 和 Bandit Problems
  3. 3. SuccessiveHalving
  4. 4. Hyperband
    1. 4.1. \(R\)
      1. 4.1.1. infinite horizon version
      2. 4.1.2. finite horizon version
    2. 4.2. \(\eta\)
  5. 5. Conclusion
  6. 6. Refer
  7. 7. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

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