こんにちは！ @tsum_tsum です！
今回は、かつて紹介した「カーネルトリックは何が"トリック"なのか？？？」に関連して、ベイズ最適化について解説していきたいと思います。
今回は前振りも控えめにして、さっそくベイズ最適化について説明していきましょう。いつもまわりくどい
はじめに
今回は難しい説明が連続するので、こちらに一覧をまとめておきましょう。
- ベイズ最適化ってなに？
- ベイズ最適化の具体的な方法
ベイズ最適化ってなに？
まず、ベイズ最適化とは何か解説していきましょう。ベイズ最適化とは、「ブラックボックス関数の大域的な最適解を見つけるための計算手法」のことです。しかし、この文章だと少し分かりにくいですね。特に、
- ブラックボックス関数って何？
- 大域的な最適解って何？
と思われた方が多いかもしれません。それらの疑問について、順を追って解説していきましょう。
ブラックボックス関数
ブラックボックス関数とは、「ある値（またはそのペア）に対して、対応する値のみが得られている関数」のことです。もっと簡単にいうと、「入力値と出力値のペアだけが分かっている関数」と思っていただければ問題ありません。例として、中学生や高校生のときに習った関数を思い出してみましょう。例えば下記のような関数ですね。
\begin{eqnarray}
y &=& x^2-x-2, \\
y &=& \sin(x) - \sqrt{3} \cos(x), \\
y &=& \log \left(\frac{1-x}{1+x}\right).
\end{eqnarray}
これらは、関数がどんな形なのか具体的に表すことができましたね。一方、ブラックボックス関数は $y=f(x)$ がどんな形で表されるか分からない関数です。つまり、
\begin{eqnarray}
f(1) &=& 2, \\
f(-4) &=& -2, \\
f(\sqrt{7}) &=& \frac{2}{5},
\end{eqnarray}
のように具体的な入力値と出力値だけが与えられている関数のことです。まさに「ブラックボックス」って感じですね。
大域的な最適解
次に大域的な最適解とはどのような解を指しているのか説明していきましょう。「何が最適なのか」は人間側が設定しますが、本記事では関数が最小値を取りうる値を指します。つまり、下記のような値（またはそのペア）を求めることに他なりません。
x^* = \underset{x \in {\mathcal X}} {\operatorname{argmin}} f(x).
もし、最大値を求めたい場合は「$-f(x)$ の最小値を求める」と解釈すればいいですね。式に表すと下記のようになります。
\underset{x \in {\mathcal X}}
{\operatorname{argmax}} f(x) = \underset{x \in {\mathcal X}} {\operatorname{argmin}} (-f(x)).
また、$f(x)=\frac{1}{3}$ となる $x$ を求めたければ、
\underset{x \in {\mathcal X}} {\operatorname{argmin}} \left|f(x) - \frac{1}{3}\right|
とすればいいですね。
ベイズ最適化が使われるタイミング
ここまでの話をまとめた上で、ベイズ最適化の用途について説明していきましょう。まずベイズ最適化とは、ブラックボックス関数の大域的な最適解を見つけるための計算手法でしたね。つまり、得体の知れない関数の最小値を求めるための計算手法のことです（ここでは最小値と表現しておきます）。
そもそも、なぜブラックボックス関数の最小値を求める必要があるのでしょうか？これには様々な理由が考えられますが、最近のディープラーニングを用いた機械学習の台頭が一因になっているかと思います。
ディープラーニングの話はQiitaにも数多くあると思われますので、ここでは詳しく述べません。機械学習やディープラーニングの目的は、入力データ $\mathcal{X}$ に対し、出力値の集合 $\mathcal{Y}$ があって、
f: \mathcal{X} \rightarrow \mathcal{Y}, \ x \mapsto y=f(x)
を満たす $f$ を求めることに他なりませんね。ただし、ディープラーニングの場合、複雑な構造を持っていることから、$f$ の表現を得ることはできません（厳密には、可能な場合もあるが現実的に表記するのが難しいですね）。そういった、$f$ の表現を得ることは難しいけど、$f$ の最小値を求めないといけない状況で現在でも使われている手法なんですね。
ここまでのまとめ
ここまで、下記のようなことについて話していきました。
- ベイズ最適化とは？
- ブラックボックス関数とは？
- 大域的な最適解ってなに？
- ベイズ最適化っていつ使われる手法なの？
個人的には、早くに qiita に記事を書いてみたいと思うほど好きな手法なんですよね。記事を書かれている多くの方と同じように、筆者も『ガウス過程と機械学習』でベイズ最適化を知りました。当時は、機械学習を勉強し始めた私にとっては少し難しく、しばらく本棚に眠っておりました。その後、統計検定2級や準1級を取得する過程で再度読んでみると、何となく理解できるようになっていきました。現在では、カーネル法と合わせて非常に興味のある概念の1つになっております。
閑話休題、本題に戻りましょう。
ベイズ最適化とは、ブラックボックス関数の大域的な最適解を見つけるための計算手法と述べました。しかし、「どうやって最適解を探すのか」という問いには答えていませんね。次の話として、どうやって最適解を探すのか？について解説してまいりたいと思います。
"最適な答え"の探し方
ベイズ最適化とは、ブラックボックス関数の大域的な最適解を見つけるための計算手法というくらいですから、見つけるための具体的な計算方法があるはずです。この"具体的な計算方法"を知るには、ガウス過程について知る必要があります。
知ってる人向けの注意点
本記事では、参考文献に従いガウス過程を代理関数として仮定します。代理関数とはブラックボックス関数を"代理する"関数のことです。どんな形で表されるか分からないブラックボックス関数を、ある程度知られている関数を用いて表示しようという考えですね。
一般的には、求めたいブラックボックス関数によってどんな代理関数が最適なのか変わってくるので、それに合わせた代理関数を設定する必要があります。この辺りの理論は、筆者も詳しくないため、この辺りで説明を締めたいと思います。
ガウス過程
ガウス過程とは、ガウス分布と確率過程を組み合わせたような概念です。厳密には、下記のように表されます。
ガウス過程の定義
$\mathcal{X}$ を入力データの集合とします。また、任意の $N \in \mathbb{Z}_{>0}$ に対し、${\rm x}_1, {\rm x}_2, \cdots, {\rm x}_N \in {\mathcal X}$ とします。この時、ベクトル
{\rm f} = (f({\rm x}_1), f({\rm x}_2), \cdots, f({\rm x}_N))
が平均ベクトルが
{\rm \mu} = (\mu({\rm x}_1), \mu({\rm x}_2), \cdots, \mu({\rm x}_N))
で、共分散行列を
{\rm K} = (k({\rm x}_i, {\rm x}_j))_{1\le i,j \le N} =
\begin{pmatrix}
k({\rm x}_1, {\rm x}_1) & k({\rm x}_1, {\rm x}_2) & \cdots & k({\rm x}_1, {\rm x}_N) \\
k({\rm x}_2, {\rm x}_1) & k({\rm x}_2, {\rm x}_2) & \cdots & k({\rm x}_2, {\rm x}_N) \\
\vdots & \vdots & \ddots & \vdots \\
k({\rm x}_N, {\rm x}_1) & k({\rm x}_N, {\rm x}_2) & \cdots & k({\rm x}_N, {\rm x}_N) \\
\end{pmatrix}
とする多変数ガウス分布 ${\mathcal N}({\rm \mu}, {\rm K})$ に従うとき、$f$ はガウス分布に従うといい、
f \sim {\rm GP} ({\rm \mu}, k)
と表す。
ガウス過程の補足
先ほど紹介したガウス過程の定義はどうでしたか？少し難しい定義だったかもしれませんね。この定義の難しいポイントは $f$ が関数という点にあると思います。
例えば、ガウス分布を想像してみてください。 $X \sim {\mathcal N}(\mu, \sigma^2)$ と表せば、${\mathcal N}(\mu, \sigma^2)$ という分布から値を取ることをイメージされると思います（少し荒っぽい解説になっていますがご容赦ください）。
一方、ガウス過程は関数を取っているというイメージです。対比して表すと、このようなイメージでしょうか。
- 確率分布 → 値をサンプリングする
- 確率過程 → 関数をサンプリングする
ちなみに、$k$ は正定値カーネルです。正定値カーネルとは何か知りたい方はこちらをご覧ください（ただのダイマ）。
さて、ガウス過程にはある数学的性質があります。ベイズ最適化を知るにはその数学的性質を理解している必要がありますので、それについて見ていきましょう。
ガウス過程の事後分布
ここではガウス過程のある数学的性質を見ていきます。入力データおよび対応する出力値の集合を
\begin{eqnarray}
{\mathcal X} &=& \{ {\rm x}_i \ | i=1,2,\cdots, N \}, \\
{\mathcal Y} &=& \{ y_i=f({\rm x}_i) \ | i=1,2,\cdots, N \}
\end{eqnarray}
とします。また、簡単のため $y = f({\rm x})$ は平均が ${\rm 0}$ になるように正規化されているとします。ただし、関数 $f$ は平均 ${\rm 0}$ のガウス過程
f \sim {\rm GP} (\mu, k({\rm x},{\rm x}'))
から生成されているとします。さて、このガウス過程から新しい入力データ ${\rm x}^* $ が与えられたとき、対応する出力値 $y^* =f({\rm x}^* ) $の事後分布 $P(y^* \ | \ {\mathcal Y})$ はどんな分布になるでしょうか？
これを求めるには、ガウス過程というものを思い出さないといけません。ガウス過程から、
(y_1,y_2,\cdots,y_N) \sim {\mathcal N}({\rm 0}, {\rm K})
であることが分かります。つまり、$(y_1,y_2,\cdots,y_N)$ は $N$ 次元のガウス分布に従うのでした。同様に、$(y_1,y_2,\cdots,y_N, y^* )$ は $N+1$ 次元のガウス分布に従うことも分かります。つまり、
(y_1,y_2,\cdots,y_N, y^* ) \sim {\mathcal N}({\rm 0},
\begin{pmatrix}
{\rm K} & {\rm k}_* \\
{\rm k}_*^T & k_{**}
\end{pmatrix}
)
が成り立ちます。ここで、
\begin{eqnarray}
{\rm k}_* &=& (k({\rm x}^* , {\rm x}_1), k({\rm x}^* , {\rm x}_2), \cdots, k({\rm x}^* , {\rm x}_N))^T \\
k_{**} &=& k({\rm x}^* ,{\rm x}^*)
\end{eqnarray}
です。そして、実は事後分布 $P(y^* | \ {\mathcal Y})$ もガウス分布になることが知られており、下記のような式で表されます。
P(y^* | \ {\mathcal Y}) = {\mathcal N}(k_*^T {\rm K}^{-1}{\rm y}, k_{**}-k_*^T{\rm K}^{-1}{\rm k}_*).
この等式の証明については、参考文献の p.53 をご確認ください（いつか別記事にした方がいいかもしれない）。「こうなるんだな」と思っていただければ問題ありません。
最適な答えの"探し方"
ようやく全ての前提知識が出揃いましたので、最適な答えをどうやって探すか説明してまいりましょう。そのために問題設定を再度確認しておきます。
求めたいブラックボックス関数を $ y=f({\rm x})$ とします。また、いくつかのデータが得られているとします。得られているデータと特徴量をそれぞれ、${\mathcal X} = \{x_1, x_2, \cdots, x_N \}, \ {\mathcal Y} = \{y_1, y_2, \cdots, y_N \}$ とします。つまり、
y_i = f(x_i) \ (i=1, 2, \cdots, N)
です。このとき $f$ はブラックボックス関数なので、もちろんどんな関数で表されるか分かりませんね。そこで、ガウス過程であるという仮定を利用します。つまり、
(y_1, y_2, \cdots, y_N) = (f(x_1), f(x_2), \cdots, f(x_N))
は、平均ベクトル
{\rm \mu} = (\mu({\rm x}_1), \mu({\rm x}_2), \cdots, \mu({\rm x}_N)),
共分散行列
{\rm K} = (k({\rm x}_i, {\rm x}_j))_{1\le i,j \le N}
のガウス分布に従うと仮定します。
さて、最適な点を探すには、最適な点の候補を選ぶ必要があります。そこで、獲得関数というものが用いられます。
獲得関数の概要
さて、皆さんが最適な点の候補を選ぶ場合、どのようにして探すでしょうか？大きく分けて2種類の考え方があるかと思います。
- 最適な点に近そうな点
- まだ探索したことのない点
1に関しては、皆さんもイメージがつきやすいと思います。この辺りに最適な点があることを既に知っている場合、近しい場所を探索することで最適な点を見つけられそうです。既に近くにお宝があることが分かっていれば、皆さんもその近くを探すでしょう。
2に関しては、まだ探索していない点です。こちらは、最適な点があるかどうかわからないが、その可能性を秘めていると考えることができます。お宝の場所の手がかりが見つからなければ、まだ探していない場所を探すでしょう。
ベイズ最適化でも同じことをします。ガウス過程では平均ベクトルと共分散行列が定められています。この平均ベクトルと共分散行列を参考にして次の点を探していくんですね。
具体的な獲得関数
では実際に、どんな獲得関数があるか見ていきましょう。その前に再び繰り返しになりますが、仮定を確認します。求めたいブラックボックス関数を $ y=f({\rm x})$ とします。また、いくつかのデータが得られているとします。得られているデータと特徴量をそれぞれ、${\mathcal X} = \{x_1, x_2, \cdots, x_N \}, \ {\mathcal Y} = \{y_1, y_2, \cdots, y_N \}$ とします。つまり、
y_i = f(x_i) \ (i=1, 2, \cdots, N)
です。
また、代理関数としてガウス過程を仮定します。真実がどんな $f$ なのか私たちは知る由もないですが、ガウス過程を用いて仮定することで計算の都合が色々よくなったりするんですね。その具体的な例が、新しい点 $x^*$ を観測した時の事後分布 $P(y^* | \ {\mathcal Y})$ です。これは、
P(y^* | \ {\mathcal Y}) = {\mathcal N}(k_*^T {\rm K}^{-1}{\rm y}, k_{**}-k_*^T{\rm K}^{-1}{\rm k}_*).
のように正規分布で表すことができるというのが特徴です。
では、具体的に獲得関数を説明していきましょう。
-
信頼上限（UCB, Upper Confidence Bound）
次の観測点 $x_{next}$ を下記の式によって、決定します。x_{next} = \underset{x \in {\mathcal X}}{\rm argmin} (\mu(x) - k \cdot \sigma(x)).ここで、
\begin{eqnarray} \mu(x) &=& k_*^T {\rm K}^{-1}{\rm y}, \\ \sigma(x) &=& k_{**}-k_*^T{\rm K}^{-1}{\rm k}_* \end{eqnarray}です。これが、ガウス過程を代理関数にした理由ですね。これによって、「次の観測点を求める」→「ガウス過程を更新する」 というのを繰り返していきます。こんな感じで観測点を集めてブラックボックス関数の形を求めていくというのを実現しています。
また、$k$ はハイパーパラメータで
k = \sqrt{\frac{\log N}{N}}がよく使われるようです。$N$は観測点の個数なので、大きくなれば大きくなるほど $0$ に近づきます。よって、観測点が少ないうちは $\sigma$ の影響が大きくなり、観測点が増えれば増えるほど $\sigma$ の影響が小さくなっていきます。
その他、様々な獲得関数がありますが、ベイズ最適化の概要をお伝えできれば十分かと思い、詳細は参考文献をご確認ください。
- 信頼下限（LCB, lower confidence bound）
- 期待改善度（EI, Expected Improvement）
- 改善確率（PI, Probability of Improvement）
- トンプソン抽出（TS, Thompson sampling）
- エントロピー探索（ES, Entropy Search）
- 予測エントロピー探索（PES, predictive entropy search）
まとめ
今回は、ベイズ最適化が「何をどんな風に最適化しているのか？」について説明してまいりました。ディープラーニングなどによって、関数がどんなものか分からないということがケースとして増えたというのも、ベイズ最適化が注目されるきっかけになったでしょうか。ベイズ最適化については筆者も素人のため、誤字誤解があるかもしれません。その時はご連絡ください。
ここまで拙い文章ですが、読んでいただきありがとうございました！