ベイズ的最適化でパラメータチューニング

ブラックボックスな関数のパラメータを最適化するときに使えると噂のベイズ的最適化のアルゴリズムを実装してみたというはなし。

f:id:chika0509:20190623001109p:plain

論文ザッと流し読んでサクッと実装しただけ。

こないだパラメータ６種類くらいあって適切な値の組を探したいみたいなことがあったのだけど、計算機パワーで６重forループ全探索して探すみたいな、ナイーヴのカタマリみたいなことをしていてツラかった。*1

ので、そういうときに使えるかも？なベイズ的最適化のアルゴリズムを実装してみた*2

ベイズ的最適化に関しては、こちらのご講演の動画が初心者にもわかりやすい印象。

www.youtube.com

実装してみたのは、動画で紹介されていた

N. Srinivas, et al. Gaussian process optimization in the bandit setting: no regret and experimental design in ICML2010

のGaussian Processs Upper Confidence Bound (GP-UCB)アルゴリズム。

パラメータ $x$ に従うブラックボックス関数 $f$ を最大化する

$y^* = \max_{x} f(x) + \varepsilon$ 　　　 $\varepsilon \sim \mathcal{N}(0, \sigma^2)$

というような確率的な最適化問題を考えたいのだけど、

$f(x)$ を評価するのはexpensiveなので

別の目的関数を用意して、強化学習の要領でパラメータ探索をしてみようというストーリー。

論文では、ブラックボックス関数 $f$ をGaussian Process(GP)に従うサンプルとしてモデル化し、既に $y = f(x) + \varepsilon$ を評価した際の $x$ の集合 $A_T = \{x_1, \cdots, x_T\}$ と $y$ の集合 ${\bf y_T} = [y_1, \cdots, y_T$ ] $^T$ についてのposteriorを考えることで、パラメータ探索のための目的関数を導いている。

$f$ に対するpriorを

$GP(0, k(x, x'))$

とすると、 $f$ に対するposteriorは、

$GP(\mu_T(x), \sigma^2_T (x))$

と書ける。ここで平均 $\mu_T(x)$ は

$\mu_T (x) = {\bf k_T}(x)^T ({\bf K_T} + \sigma^2 {\bf I})^{-1} {\bf y_T}$

分散 $\sigma^2_T(x)$ は

$\sigma^2_T (x) = k_T (x, x)$ where $k_T(x, x') = k(x, x') - {\bf k_T}(x)^T ({\bf K_T} + \sigma^2 {\bf I})^{-1} {\bf k_T}(x')$

であり、 ${\bf k_T}(x) = [k(x_1, x), \cdots, k(x_T, x)$ ] $^T$ 、 ${\bf K_T}$ はカーネルのグラム行列( $\{k(x, x')\}_{x, x' \in A_T}$ ) 。

このposteriorのGPの平均と分散を用いて、探索の戦略を

$x_t = \arg \max \mu_{t-1}(x) + \sqrt{\beta} \sigma_{t-1}(x)$

としてみましたというのがこの論文。

これは強化学習っぽい戦略で、今までパラメータ評価して得た知識を「活用」するための項が $\mu_{t-1}(x)$ の項で、新しいパラメータを「探索」するための項が $\sigma_{t-1}(x)$ の項になっている。 $\beta$ が小さければあまり「探索」しないし、 $\beta$ が大きいとどんどん「探索」するカンジになる。

やることとしては、

目的関数 $\mu_{t-1}(x) + \sqrt{\beta} \sigma_{t-1}(x)$ の値を全てのパラメータ候補について求める
目的関数を最大化するパラメータを $x_t$ として選ぶ
$x_t$ を用いてブラックボックス関数を評価して $y_t = f(x_t) + \varepsilon_t$ を得る
posterior更新
1.〜4.を繰り返す

というただそれだけ（だとおもう、多分）。実装カンタン、ヨカッタ！

パラメータ１次元としてブラックボックス関数を $f(x) = x \sin (x)$ としててきとーに実装してみたけれど、思ったのは、GPのposteriorの平均・分散の計算が計算量小さいという前提なんだろうなということと、 $\beta$ が小さいとソッコーでlocal optimaにドボンすること。探索と活用のトレードオフというやつですね。*3

ベイズ的最適化、もっと難しいモノだと思っていたけど、少なくともこのアルゴリズムに関しては、なんのことはないGPのposterior使って探索するだけというカンジでした。逆に言うとsimpleで美しいとも言えるような。

*1:ベイズ的最適化というの試してみたいと思ったけど〆切直前だったので諦めた

*2:というのは建前で、本当は最近コードを書くということをしていなかったのでチャチャッと実装できそうなお題が欲しかっただけ。

*3: $\beta$ をどう設定すべきかについては論文のSection 4に書いてあるっぽい。

ニンゲンメモ

タメになりそうでタメにならない日記

ベイズ的最適化でパラメータチューニング