参考文献: Hyperband: Bandit-Based Configuration Evaluation for Hyperparameter Optimization https://openreview.net/pdf?id=ry18Ww5ee
I. 传统优化算法
机器学习中模型性能的好坏往往与超参数 (如 batch size,filter size 等) 有密切的关系. 最开始为了找到一个好的超参数, 通常都是靠人工试错的方式找到 "最优" 超参数. 但是这种方式效率太慢, 所以相继提出了网格搜索(Grid Search, GS) 和 随机搜索(Random Search,RS).
但是 GS 和 RS 这两种方法总归是盲目地搜索, 所以贝叶斯优化(Bayesian Optimization,BO) 算法闪亮登场. BO 算法能很好地吸取之前的超参数的经验, 更快更高效地最下一次超参数的组合进行选择. 但是 BO 算法也有它的缺点, 如下:
对于那些具有未知平滑度和有噪声的高维, 非凸函数, BO 算法往往很难对其进行拟合和优化, 而且通常 BO 算法都有很强的假设条件, 而这些条件一般又很难满足.
为了解决上面的缺点, 有的 BO 算法结合了启发式算法(heuristics), 但是这些方法很难做到并行化
II. Hyperband 算法
1. Hyperband 是什么
为了解决上述问题, Hyperband 算法被提出. 在介绍 Hyperband 之前我们需要理解怎样的超参数优化算法才算是好的算法, 如果说只是为了找到最优的超参数组合而不考虑其他的因素, 那么我们那可以用穷举法, 把所有超参数组合都尝试一遍, 这样肯定能找到最优的. 但是我们都知道这样肯定不行, 因为我们还需要考虑时间, 计算资源等因素. 而这些因素我们可以称为 Budget, 用 \(B\)表示.
假设一开始候选的超参数组合数量是 \(n\), 那么分配到每个超参数组的预算就是 \(\frac{B}{n}\). 所以 Hyperband 做的事情就是在 \(n\)与 \(\frac{B}{n}\)做权衡(tradeoff).
上面这句话什么意思呢? 也就是说如果我们希望候选的超参数越多越好, 因为这样能够包含最优超参数的可能性也就越大, 但是此时分配到每个超参数组的预算也就越少, 那么找到最优超参数的可能性就降低了. 反之亦然. 所以 Hyperband 要做的事情就是预设尽可能多的超参数组合数量, 并且每组超参数所分配的预算也尽可能的多, 从而确保尽可能地找到最优超参数.
2. Hyperband 算法
Hyperband 算法对 Jamieson & Talwlkar(2015) https://arxiv.org/abs/1502.07943 提出的 SuccessiveHalving 算法做了扩展. 所以首先介绍一下 SuccessiveHalving 算法是什么.
其实仔细分析 SuccessiveHalving 算法的名字你就能大致猜出它的方法了: 假设有 \(n\)组超参数组合, 然后对这 \(n\)组超参数均匀地分配预算并进行验证评估, 根据验证结果淘汰一半表现差的超参数组, 然后重复迭代上述过程直到找到最终的一个最优超参数组合.
基于这个算法思路, 如下是 Hyperband 算法步骤:
r: 单个超参数组合实际所能分配的预算;
R: 单个超参数组合所能分配的最大预算;
\(s_{max}\): 用来控制总预算的大小. 上面算法中 \(s_{max}=\lfloor log_\eta(R) \rfloor\), 当然也可以定义为 \(s_{max}=\lfloor log_\eta(n_{max}) \rfloor\)
B: 总共的预算,\(B=(s_{max}+1)R\)
\(\eta\): 用于控制每次迭代后淘汰参数设置的比例
get_hyperparameter_configuration(n): 采样得到 n 组不同的超参数设置
run_then_return_val_loss(t,ri): 根据指定的参数设置和预算计算 valid loss.\(L\)表示在预算为 \(r_i\)的情况下各个超参数设置的验证误差
top_k(\(T,L,\lfloor \frac{n_i}{\eta}\rfloor\)): 第三个参数表示需要选择 top k(\(k=\frac{n_i}{\eta}\rfloor\))参数设置.
注意上述算法中对超参数设置采样使用的是均匀随机采样, 所以有算法在此基础上结合贝叶斯进行采样, 提出了 BOHB:Practical Hyperparameter Optimization for Deep Learning https://openreview.net/forum?id=HJMudFkDf
3. Hyperband 算法示例
文中给出了一个基于 MNIST 数据集的示例, 并将迭代次数定义为预算(Budget), 即一个 epoch 代表一个预算. 超参数搜索空间包括学习率, batch size,kernel 数量等.
令 \(R=81,\eta=3\), 所以 \(s_{max}=4,B=5R=5*81\).
下图给出了需要训练的超参数组和数量和每组超参数资源分配情况.
由算法可以知道有两个 loop, 其中 inner loop 表示 SuccessiveHalving 算法. 再结合下图左边的表格, 每次的 inner loop, 用于评估的超参数组合数量越来越少, 与此同时单个超参数组合能分配的预算也逐渐增加, 所以这个过程能更快地找到合适的超参数.
右边的图给出了不同 \(s\)对搜索结果的影响, 可以看到 \(s=0\)或者 \(s=4\)并不是最好的, 所以并不是说 \(s\)越大越好.
MARSGGBO♥原创
2018-12-22
来源: https://www.cnblogs.com/marsggbo/p/10161605.html