読者です 読者をやめる 読者になる 読者になる

Obey Your MATHEMATICS.

機械学習関連の純粋数学や実験など

Taking the Human Out of the Loop -ベイズ最適化のすゝめ-

こんにちは。タイトルは次の論文から拝借しました;

Taking the Human Out of the Loop: A Review of Bayesian Optimization - IEEE Xplore Document


という訳で今話題沸騰中(????????)の

Bayesian Optimization(ベイズ最適化)についてまとめたいと思います。

また、日本語で「ベイズ最適化」とググるといくつか良い記事が見つかるのでそちらも合わせて参照してみて下さい。いくつかピックアップして、この記事の下の方に”参考記事”としてまとめておきました。

また、佐藤一誠さんの講演動画も導入としてかなり参考になると思います。20分程度なので是非!

www.youtube.com

しっかりと数学的なセッティングについて言及した記事があまりないように思われたので、そこにフォーカスして書きたいと思います。

§1. ブラックボックス関数の最適化とMotivation

まず、ベイズ最適化をする目的となるブラックボックス関数ってなんぞや?と言う話をします。

例えば、Deep Learningでモデルを作る時、

隠れ層の数、各層の素子数、学習係数、ドロップアウトの割合、l^2正則化の重み、等々

決めなければならないハイパーパラメータが無数にあると思います。

これらのハイパーパラメータに対して、目的関数(誤差関数であったりそれは目的次第)がどのように対応してるか私達に知る術はありません。もしあなたが神様でハイパーパラメータに対して目的関数の値がどうなるのか解るのであればこの記事は読まなくて良いです。

Deep Learningに限らず、このような得体の知れない関数をブラックボックス関数と呼びます。

そしてDeep Learningにかぎらず、世の中にはこの得体の知れないブラックボックス関数の値を最適化しなければならないことが山ほどあるわけです。(SVM、ランダムフォレスト、粒界構造最適化や、Si-Ge ナノ構造の自動設計*1などなど)

もちろんこの関数は文字通り闇に包まれているため、”微分して勾配計算して最適化”なんて事は出来るはずがないのです。そもそも微分可能かどうかの判定が出来ません。




ではどうやってハイパーパラメータを決めるのか?


ってことになるわけですが、通常、今まで業界で蓄積されてきたヒューリスティック達を申し分無く使い、チューニングしていくわけです。


1回の実験に莫大なお金と労力がかかるようなものでなければ、別にそれで良いんです。トライ&エラーの繰り返しでも。



ただ現実は厳しくて、お金と労力は限られますし、人間の勘に頼って非生産的な事を続けるのってなにかこう人間がやる意味ってあるんですかね??これって馬鹿馬鹿しくないですか?いつまで数学的な根拠のないempiricalな手法を人力で使い続けるの?(煽り)*2


ベイズ最適化のモチベーションはそこにあります。


ブラックボックス関数を効率良く最適化&自動化するための数学的な基盤を創りましょう


と言う事です。

§2. ベイズ最適化とは

ベイズ最適化の話をする前に、ハイパーパラメータを探すNaiveな方法としてグリッドサーチと言う手法があります[7]。

機械学習のハイパーパラメータ探索の方法として、グリッドサーチという手法がよく使われます。 グリッドサーチとは、ハイパーパラメータの探索空間を格子状 (グリッド) に区切り、交点となるハイパーパラメータの組み合わせについて、すべて調べるという方法です。*3

この手法はある種ランダムに点を取って調べていくのですが、どう考えても効率が悪いです。

それは何故か。この手法は、今まで調べてきた点とそこでのブラック関数の値(データ)を活用してないからです。


次に実験すべき点を合理的に選ぶことが出来ていない


と言う事です。その合理性を含んだ理論と手法がベイズ最適化なんです。



次の§以降で数学的にちゃんと定式化しますので、ここでは直感的に説明してみます。
以下ではブラックボックス関数を最小化したい状況を考えます。



ハイパーパラメータの空間上の関数全体のベクトル空間(関数空間と呼びます)を想像してみて下さい。推定したい(最適化したい)ブラックボックス関数 { F } はこの空間の中に住んでいます。とにかくどんな関数か分からないので、ガウス過程{ \xi }と呼ばれるこの関数空間上の普遍的で扱いやすい確率分布からサンプリングされたものだと仮定しましょう。

さあ、実験を始めます。とりあえずテキトーに(ヒューリスティックでもなんでも良いので)一点{ X_1 }を選んで実験し、ブラックボックス関数の値{ F(X_1) }を得ます。

次に実験する点は以下のように決めます。まず、データ{ \mathcal{D}_1 := \{( (X_1,F(X_1)) \} }があるので、””{  \mathcal{D}_1  }と言う条件を満たす関数””と言う条件付き分布が関数空間上に得られます。そして嬉しい事にこの分布は、最初に事前分布としてガウス過程と言う扱いやすいものを設定したおかげで、ハイパーパラメータに対応する関数の値の予測平均と予測分散が解析的に求めることが出来ます。この平均と分散を使って””平均が小さくて分散が大きい点”” { X_2 }を選んだ方が、ブラックボックス関数の最小点である確率が高いので、次の実験対象とします。

さあ、2回目の実験をしたら値{ F(X_2) }が得られました。従ってデータ{  (X_2,F(X_2))  }を新たに得られたので、データを更新{ \mathcal{D}_2 := \{(X_1,F(X_1)),(X_2,F(X_2))\} }して、同じような手順で3つ目の点を選んで実験します............以下同様

と言った感じです。合理的な意思決定のため、そして、計算しやすさのために、関数空間上の事前分布としてガウス過程を導入しています。

§3. ブラックボックス関数最適化問題の定式化

いよいよ数学的にベイズ最適化をしていきます。*4

最適化したいハイパーパラメータの空間を{ \mathbb{X} \subset \mathbb{R}^d (d \geq 1)}と表記し、コンパクトであると仮定します。*5
{ \Omega := \mathbb{R}^\mathbb{X} }{ \mathbb{X} }上の実数値関数全体が成すベクトル空間として、次のような集合(Cylinder setsと呼びます)が生成する{ \sigma }-Algebra{ \mathcal{A} }を考えます;

{ \left\{ G \in \Omega \ \ | \ \  a_i < G(w_i) < b_i  \ , \ \ i=1,...,N \right\} }.

測度空間{ (\Omega,\mathcal{A}) }に対して、確率分布{ \mathbb{P} }をこの測度空間上に1つ取り確率空間{ (\Omega,\mathcal{A}, \mathbb{P})}が得られます。

このセッティングの下、大域最適化のアルゴリズム(以下では戦略と呼ぶ事にします。)を決めることは、

関数 {  \mathbb{S} : \Omega  \rightarrow \mathbb{X}^\mathbb{N} \ , \ \  F \mapsto (X_1(F),X_2(F),X_3(F),...  )} を選ぶ事

と同値になります。点の選び(選ばれ)方が関数{F}に依存するような戦略を立てる事です。そしてその{ F }は関数空間上の確率分布{ \mathbb{P} }によってサンプリングされていると考えると、この意味で{X_n : \Omega \rightarrow \mathbb{X} }は確率変数となります。

戦略{ \mathbb{S}=(X_1,X_2,X_3,...  ) }と言う点の選び方に対する自然な条件として、{n+1 }番目の点を選ぶ確率変数{ X_{n+1} }{ F(X_1(F)),F(X_2(F)),...,F(X_n(F))}にのみ依存して決まっている、と言う条件を課します。これまで実験して得られたデータを下に次に選ぶべき点の分布を定める、と言うものです。自然ですよね。


さて、グリッドサーチ戦略の欠点は

データ{ F(X_1(F)),F(X_2(F)),...,F(X_n(F))}を上手く活用して確率変数{ X_{n+1} }を決定していない

と言う事に数学的に言い換える事が出来るでしょう。

以下では、目的のブラックボックス関数{ F \in \Omega : \mathbb{X} \rightarrow \mathbb{R} }は確率分布{ \mathbb{P} }からサンプルされたと仮定し、グリッドサーチの欠点を克服するようなベイズ最適化と呼ばれる戦略{ \mathbb{S}}を決めます。

§4. ガウス過程とEIアルゴリズム

さあ、本題です。皆さんご存知のガウス過程と呼ばれる確率変数(またはそれによって誘導されるガウス確率測度)を使ってベイズ最適化を書き下していきましょう。*6

念のためにガウス過程について復習しておきます。*7

確率空間 { (\Omega',\mathcal{A}', \mathbb{P}')  }に対して、確率変数{ \xi : \Omega' \rightarrow \Omega=\mathbb{R}^{\mathbb{X}} }{ \mathbb{X} }上のガウス過程であるとは、任意の有限個の点{(x_1,..,x_n) }に対して確率変数{ \xi(x_1),...,\xi(x_n) }が定める*8{ \mathbb{R}^n}上の確率分布がGaussianである。また、ガウス過程により定まる関数空間{ \mathbb{X}}上の確率測度をGaussian測度と呼ぶ。

また、重要な性質として、カーネル関数 { k : \mathbb{X} \times \mathbb{X} \rightarrow \mathbb{R} }と平均関数 { \mu : \mathbb{X} \rightarrow \mathbb{R} } を決めることでガウス過程{ \xi}は一意に決まり、{ k(x,y) = Cov(\xi(x),\xi(y)) }{ \mu(x) = \mathbb{E}[ \xi(x)] }と言う性質持ちます。*9

以下では確率変数{ \xi}を固定し、このガウス過程が誘導する確率分布を{ \mathbb{P} }として考えます。
どのようにカーネルと平均を適切に選ぶか、についてはこれまた別の議論なので次の§で述べます。

目的のブラックボックス関数{ F}を固定し、これを最大化したい状況を考えましょう。

天下り的にかつ帰納的に以下のように戦略を立てます。

Step1.
{ X_1(F) }はテキトウにヒューリスティックでもなんでも良いのでランダムに選ぶ

Step(n+1).
 { (X_1(F),X_2(F),...,X_n(F)) }における実験が終わっているので、値 { M_n := \max(F(X_1(F)),F(X_2(F)),...,F(X_n(F)) ) }を計算する。そして関数

 { a_{n+1}(X) := \mathbb{E} [ \left( \xi(X) - M_n \right) | \xi(X_i)=F(X_i(F))(i=1,..,n) ] }

を最大化するよう{X_{n+1} }選ぶ。

このように点を選んでいく戦略をベイズ最適化におけるExpected Improvement (EI)戦略と呼びます。

関数 { a_{n+1}(x)}を獲得関数と呼び、ここでは天下り的に定義しましたが、この関数の選び方によってまた別の種類のベイズ最適化が得られます。*10

EI戦略はその獲得関数の定義から、

今あるベストの値との差からの改善の期待値が最も大きくなる点を選び続ける

と言い換える事ができます。*11



ただこのままの { a_{n+1}(x)}の定義だと、全く計算出来る気配がしないので、(EI戦略に限らず)別の形に書き直す必要がありますが、そこでガウス過程の性質+ベイズの定理*12を使って、点の予測平均と分散をカーネルと平均関数を使って解析的に書き表すことが出来、実装可能になるわけです。


この辺の計算は[1]の§2で非常に分かりやすくかつ丁寧に書かれているので参照されたいです。

・数値実験など含め下の方にある3つの参考記事を参照されたいです。

・EIアルゴリズムの収束証明は[4]や[9]にあります。

§5. DNNを使ったカーネル関数と平均関数の最適化

最後になりましたが、カーネル関数と平均関数ってどうやって選ぶの??みたいな疑問が残っているので考えてみます。

アルゴリズムの収束のために””変な””カーネル関数を選んではいけないことは分かると思います。

一般的には平均関数は恒等的に0として、カーネル関数は例えば

 { k(x,y)=\exp\left( -\dfrac{1}{2} \|x-y \|^2 \right) }

こんなものや、カーネル関数にもハイパーパラメータ{ \theta_0,...,\theta_d }を導入して*13

 { k(x,y)= \theta_0 \exp\left( -\dfrac{1}{2} r(x,y)^2 \right) \ , where \ \ r(x,y)=\sum_{i=1}^d (x_i-y_i)^2 /\theta_i }

 { k(x,y)= \theta_0 \left( 1 + \sqrt{5r(x,y)^2} + \dfrac{5}{3}r(x,y)^2 \right) \exp\left(  -\sqrt{5r(x,y)^2 } \right) }

とか言うものが使われたりします([5]参照)。

しかし、ガウス過程を関数上の””事前分布として””使ってベイズの定理を使って点を選んでいく以上、もうちょっとPrior Informationを反映したようなガウス過程を作ったほうが精度が上がるはずなのです。

そこで[2]で提案されたのが皆さんお馴染みDeep Neural Networkを使ってカーネルも平均も学習して作っちゃおうと言う手法です。

[8]にある次のコメントが、この手法の新しさというかユニークさを示しています:

Although the notion of using a non-trivial Gaussian process prior mean is not new, it is usually expected to encode domain expert knowledge or known structure in the response surface. To the best of the authors’ knowledge, only one recent work has considered using the prior mean as a regularization term and it was primarily to avoid selecting points along boundaries and in corners of the bounding box[Snoek et al., 2015] *14

[2]で提案された手法を簡単に説明すると

 { \mathbb{X} }を入力空間そして1次元の出力とするDNNを考え 、ブラックボックス関数 { F }を通常の手法(確率的勾配法など)を使ってモデリングする。その後、隠れ層の最後の層までのネットワークを { \mathbb{X} }非線形変換する基底関数だと考え、Bishop上の3章によく書かれているように線形ベイズで予測平均と分散を計算し、カーネルを計算。


この手法の良いところは予測平均と予測分散の計算に必要な逆行列の計算量が実験の数に対してDNNの最終隠れ層の数のオーダーで増えていく事所だそうです。*15Naiveにカーネルを定めてから計算するとデータの数の二乗O(N^2)なのでそれに比べるとだいぶ少ないです。


少しまとまりのない記事になってしまいましたが、この辺で終わりたいと思います。では。

§7 参考文献とコメント

[1] [1012.2599] A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
ベイズ最適化のチュートリアルです。まず最初はこれを読みました。
[2] [1502.05700] Scalable Bayesian Optimization Using Deep Neural Networks
ガウス過程のカーネル関数と平均関数をDNNで学習しちゃいましょうって論文です。
[3] http://papers.ai/nips.2016.6117
これも[2]と同じ感じ?だと思います(ほとんど読んでない)
[4] [0712.3744] Convergence properties of the expected improvement algorithm
EIアルゴリズムの確率論的収束証明です。あまり知られてないみたい?[9]のほうが有名っぽい。
[5] [1206.2944] Practical Bayesian Optimization of Machine Learning Algorithms
ガウス過程のパラメータを積分消去して使うって論文
[6] Taking the Human Out of the Loop: A Review of Bayesian Optimization - IEEE Xplore Document
最新(?)のベイズ最適化のサーベイ(?)
[7] Random search for hyper-parameter optimization
グリッドサーチの論文
[8] [1508.03666] Unbounded Bayesian Optimization via Regularization
有界な領域でベイズ最適化しましょって論文。たぶん。
[9] [1101.3501] Convergence rates of efficient global optimization algorithms
EIアルゴリズム収束の証明。こっちのほうが有名らしい。
[10]言わずもがなPRMLの上

*1:この例は機械学習以外にもないのかよ!って思われないために書きました→ http://coop-math.ism.ac.jp/files/233/Abstract_Tsuda.pdf

*2:もちろん、ヒューリスティックを裏付ける数学的根拠を見つける、みたいな理論研究もあるわけですが、そういう方向性は今回考えないことにします。

*3:https://book.mynavi.jp/manatee/detail/id=59393

*4:[4]を参考にしました。

*5:コンパクトであることはある意味で本質的でありませんが、数学的には収束の証明をするためにはMustです。このような制限を取り払って非有界(コンパクトでない領域)でベイズ最適化しようと試みているのが[8]です(たぶん)。 

*6:ガウス過程以外に使えないのか?と言う疑問は尤もです。統計学的に扱いやすくて理論も整備されている、と言う点でガウス過程を使っているのです。

*7:気が向いたらガウス過程の存在証明とかの記事書こうと思います。

*8:確率変数によって確率変数の行き先に定まる測度を確率分布と呼ぶのでした。この辺は測度論的確率論の基礎です。

*9:これによって{ \xi(x_1),...,\xi(x_n) }が定める同時分布が一意に決まる事は言うまでもありません。

*10:PI戦略やUBC戦略などがあります→[1]参照。

*11:他の有名な戦略の説明はこの記事が分かりやすいです→https://book.mynavi.jp/manatee/detail/id=59393

*12:これが「ベイズ最適化」と呼ばれる所以です。

*13:このパラメータを積分消去するみたいな話が[5]にあります。

*14:この論文が[2]の事で、この引用は [8]§1.1の最初にあるコメントです。

*15:[2]の§3.1のちょっと上