はじめに

前回はOptunaの実装というよりもかなり触りの全体像のみを紹介しました。
前回ベイズ最適化とはという項でいきなりベイズ最適化という言葉を取り上げましたが、ここをもう少し詳しく説明します。

optunaの基本的な部分についてそのまま動かすことができるコードもあります。それも触ってみてください。optunaとの比較もでき、完全に一致していることが確認できると思います。
なおバージョンはv2.9.1を参考にしています。

参考

James Bergstra et al. Algorithms for Hyper-Parameter Optimization. NIPS’11, Pages 2546–2554.

SMBO

これはSequential Model-Based Global Optimizationの略で上の論文では以下のfigure1で示されているものです。

論文によると、計算コストの高い関数$f(x)$があるような状況でよく利用されます。そこで、この$f(x)$を計算しやすい代理の関数で近似するというのがポイントになっています。
これを前回は代理関数と読んでいました。この代理関数(もしくは少し変形したもの)を数値的に逐次最適化し、数値解を得るというのがこのアルゴリズムの目的になっています。

SMBOの大まかな流れ

代理関数(もしくは少し変形したもの)を最大化する値$x^∗$が次のイテレーションで$f$に提案され、計算される
その$f(𝑥^*)$を用いて代理関数を更新する
1と2を$T$回繰り返し続ける

SMBOアルゴリズムは$x^∗$をどうやって算出するかと、観測済みのデータからどうやって$f$をモデル化するかで手法が変わってくるといえます。

図でもまとめておきます。

変数定義

計算コストの高い関数 $f$
総試行回数 $𝑇$
獲得関数を最大化する値 $x^∗$
$x^∗$と$𝑓(x^∗)$の観測履歴 $ℋ$
$ℋ$をモデル化 $𝑀_t$
$x^∗$を算出するための関数(獲得関数、効用関数などと呼ばれます) $𝑆(x,𝑀_t)$

データが得られるたびに$𝑀_t$の分布を少しずつ更新していくので、ベイズ最適化などと呼ばれたりします。ただ、実際はSMBOと呼んだ方が正しいかもしれません。

GP-EIとTPE

前回に全体像、今回にSMBOを紹介したことでようやくGP-EIとTPE自体の概要の話ができるようになりました。

わかりやすさのため図を示します。

SMBOの図と違っているところは、$S$の部分が期待値最大化となっていることです。GP-EIもTPEも期待値最大化を採用しており、違うのは$𝑀_t$を更新する部分のみとなります。

期待値最大化(Expected Improvement)とは

論文にあるように期待値は以下の式で示されます。$y^*$はlossの閾値で、閾値のlossより小さくなる期待値の計算をしています。

この期待値が最も大きくなる$x$が次のイテレーションで試される$x^∗$となります。

実は期待値最大化の他には、Probability ImprovementやLower Confidence Bounds などがありますが、一番直感的なのがEIなのでこれが採用されています。
これを選ぶ部分については今後のfuture workと論文には書いてあります。

最後に

長い文章を書くのが苦手なので、今回も短いですがここで終わりにします。
SMBOアルゴリズムというものがTPEの背景にあるということがわかってもらえればいいと思います。
次はGP-EIとTPEについてもう少し掘り下げる予定です。