AutoML HPO 学习笔记(三)- SMAC

  |     |   本文总阅读量:

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

引言

  最近阅读了提出 SMAC[1] 算法的论文,本文简单的对 SMAC 做一些记录,SMAC 是一种基于 SMBO 的参数选择算法,它也是第一个可以处理类别参数的算法,很适合 CASH 算法。与 TPE 等算法不同的是,它是基于 random forest regression 的。

SMBO

  SMBO 的概念我们不再赘述,论文里作者也提出了当时 SMBO 所遇到的三个主要的限制:

  1. it only supports numerical parameters
  2. it only optimizes target algorithm performance for single instances
  3. it lacks a mechanism for terminating poorly performing target algorithm runs early

  本文提出的 ROAR 和 SMAC 算法那解决了前两个问题,并且使算法更加通用。本文中作者是这样定义 SMBO 的:

ROAR

  在介绍 SMAC 前,我们先需要了解下 ROAR(Random Online Aggressive Racing)。
  ROAR 在处理 multiply instances 的时候用到了一个 Intensify procedure,也称为 intensification mechanism,它主要决定对每个 configuration 需要有多少次的 evaluations,并且何时能将它作为目前最优的 configuration,除此之外还需决定在每次 run 时需要用到哪些 instances。具体算法如下:

  上面的伪代码已经非常清晰了,需要注意的是,针对 incumbent 的 \(\boldsymbol{\theta}_{inc}\),我们一开始需要对进行一次额外的 run,然后我们在 为 \(\boldsymbol{\theta}_{new}\) 进行 run,比较它们的 empirical cost(比较用的是它们都 run 过的 instance),\(N\) 也是每次翻倍增长的。
  介绍完 intensification mechanism,ROAR 实际上就非常好理解了,它是一个非常简单并且 model-free 的处理 SMBO 问题的框架,它实际上也就是由四个主要部分组成:

  • Initialize
  • FitModel
  • SelectConfigurations
  • Intensify

  理解了 ROAR 的原理后,我们也可以理解下它名字的由来:

  • Random:指的就是它随机挑选 candidate
  • Online:指的是它是一个在线算法则不需要重新训练,每次都可以在线的拒绝 candidate
  • Aggressive:指的是在收集到足够的数据以支持具有统计意义的结论之前,我们会积极做出在线决策
  • Racing:指的是对于每个 candidate,只有当它足够 competitive 的时候,我们才会使用它

SMAC

  SMAC(Sequential Model-based Algorithm Configuration )可以看作是 ROAR 的一个拓展版本,不同的是,它挑选 configurations 时基于一个 model 的,而不是 uniformly at random。下面我们介绍下它的几个特性,它支持类别参数,他支持 multiply instances,它使用一个 model 去挑选 configurations,这些特性也使得 SMAC 更加泛化。

Models for Categorical Parameters

  在 SMAC 提出前,已存的 SMBO 方法都是被限制为只能处理数值型参数的,而 SMAC 可以处理类别性参数,为了做到这一点,SMAC 使用了 Random Forest Regression,RF 已经被证明了在输入是类别特征时具有很好的性能。
  RF 可以得到更加准确的 predictions,而且可以量化这些 predictions 的 uncertainty。
  我们用 \(B\) 棵回归树构建一个随机森林,每棵树用 \(n\) 个 data points 来构建,这些 data points 通过从训练集 \(\left\{\left(\boldsymbol{\theta}_{1}, o_{1}\right), \ldots,\left(\boldsymbol{\theta}_{n}, o_{n}\right)\right\}\) 里可放回的随机采样得到。每棵树的 split point 通过 \(d\) 的一个随机子集 \(\lceil d \cdot p\rceil\) 来确定,其中 \(d\) 是 data points 的个数,\(p\) 是 split ratio,作者还指定了 \(n_{\text {min}}\),它表示每个叶子节点包含的最少的 data points 的个数。

论文中设置\(B=10\)\(p=5 / 6\)\(n_{\text {min}} = 10\)

  作者还用 RF 为每一个新的 configuration \(\theta\) 计算了 predictive mean \(\mu_{\boldsymbol{\theta}}\) 和 variance \(\sigma_{\boldsymbol{\theta}}^{2}\),将它作为每棵子树的 predictions 的 empirical mean 和 empirical variance。
  除此之外,作者也提到了优化目标,也就是 cost metric,论文中用的算法的 runtime \(r_i\),作者发现对它进行 log 操作,会使 model 得到更好的效果,即优化 \(o_{i}=\ln \left(r_{i}\right)\)

Models for Sets of Problem Instances

  SMAC 会显示地将 instance 的信息集成到 response surface models 中,它会学习一个模型同时来处理 parameter configurations 和 instance features。

Use models to select promising parameter configuration

  SMAC 里的 SelectConfiguration 的过程是利用一个 model 选出一些 promising parameter configuration,不仅仅一个。这里用到的还是 \(EI\)

\[ E I(\boldsymbol{\theta}):=EI[\operatorname{exp}(\boldsymbol{\theta})]=f_{\min } \Phi(v)-e^{\frac{1}{2} \sigma_{\boldsymbol{\theta}}^{2}+\mu_{\theta}} \cdot \Phi\left(v-\sigma_{\boldsymbol{\theta}}\right) \\ v:=\frac{\ln \left(f_{\min }\right)-\mu_{\theta}}{\sigma_{\theta}} \]   制定出 \(EI(\theta)\) 后关键就是在于如何找到较大 \(EI(\theta)\)\(\boldsymbol{\theta}\),之前的 SMBO 方法都是简单的随机采样,比方说采样 10000 个 \(\theta\) 来计算 \(EI(\theta)\),但是对于一些稀疏参数空间这明显是不够的。
  SMAC 才用了一种名为 multi-start local search 的方法,它会计算之前 run 过的一些 configurations 的 \(EI\),挑选出 10 个最大的,来对它们分别做 local search。所谓的 lcoal search,SMAC 是才用了一种名为 randomized one-exchange neighbourhood 的方法,它会根据一个 configuration 改变它的一个类别参数的值(如果有的话),随机对每个数值参数改变四个值,数值参数的值都会被 normalize 到 \([0,1]\) 间,然后通过高斯多元分布随机采样四个值(mean 为当前参数的值,deviation 为 0.2),然后计算它们的 \(EI\),local search 结束的标志是再也没有更好的 neighbour 了。
  通过这种方式,SMAC 将 sampled uniformly at random 也结合了进来,在 Intensify 的过程中,每轮迭代中至少有 1 个randomly sampled configuration 被 evaluate,也就是说参数空间里的每个参数都有可能被选中,SMAC 会在最终收敛到一个 optimal 的 configuration。

Conclusion

  总结下论文提出的 ROAR 和 SMAC 算法,实际上也是对解决 SMBO 问题提供了四个更加泛化的方法:

  • An Intensification Mechanism for Multiple Instances
  • Models for Categorical Parameters
  • Models for Sets of Problem Instances
  • Using the Model to Select Promising Configurations in Large Mixed Numerical/Categorical Configuration Spaces

Refer

[1]. Hutter, Frank, Holger H. Hoos, and Kevin Leyton-Brown. "Sequential model-based optimization for general algorithm configuration." International conference on learning and intelligent optimization. Springer, Berlin, Heidelberg, 2011.

相关内容


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



文章目录
  1. 1. 引言
  2. 2. SMBO
  3. 3. ROAR
  4. 4. SMAC
    1. 4.1. Models for Categorical Parameters
    2. 4.2. Models for Sets of Problem Instances
    3. 4.3. Use models to select promising parameter configuration
  5. 5. Conclusion
  6. 6. Refer
  7. 7. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

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