Subscribed unsubscribe Subscribe Subscribe

ニンゲンメモ

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

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

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

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

 

こないだパラメータ6種類くらいあって適切な値の組を探したいみたいなことがあったのだけど、計算機パワーで6重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)に従うサンプルとしてモデル化して、GPに基づいて目的関数を導いている。

 fに対するpriorを

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

として、既に y = f(x) + \varepsilonを評価したパラメータ集合 A_T =  \{x_1, \cdots, x_T\}、各々に対応するnoisyなサンプルの集合 {\bf y_T} = [y_1, \cdots, y_T ] ^Tを用いると、 fに対するposteriorは、

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

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

を用いて GP(\mu_T(x), \sigma^2_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が大きいとどんどん「探索」するカンジになる。

 

やることとしては、

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

というただそれだけ(だとおもう、多分)。実装カンタン、ヨカッタ!

 

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

 

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

 

 

 

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

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

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