「ベイズ最適化」を読む　～第3章ベイズ最適化のアルゴリズム ③期待改善量獲得関数・信頼下限獲得関数～

はじめに

データを使って仮説の生成と検証を行なうための方法であるベイズ最適化を学ぶために，今村秀明・松井孝太著「ベイズ最適化　ー適応的実験計画の基礎と実践ー」を読むことにした。

本記事は，「第3章　ベイズ最適化のアルゴリズム」における，期待改善量獲得関数と信頼下限獲得関数に関する読書メモである。

本書の紹介ページ

www.kindaikagaku.co.jp

3.3 期待改善量獲得関数

本節では，期待改善量(expected improvement)と呼ばれる獲得関数について説明している。
この獲得関数は，あるトライアルで分かっている最適な実現値に対して，その $\boldsymbol{x}$ を選ぶことで実現値がどの程度改善するかという量を，その改善量の期待値で測ったものである。

目的関数の評価値

3.2節の改善確率量獲得関数と同様に，目的関数の事後分布を考える。

目的関数 $f$ には，ガウス過程回帰を用いる。また，データ $\mathcal{D}_n = \{ (\boldsymbol{x}_i, y_i)_{i=1}^n \}$ が得られているとする。
目的関数の事後分布はガウス過程となり，その平均関数 $\mu_n$ およびカーネル関数 $\kappa_n$ は以下のようになる。

$\begin{align} \mu_n(\boldsymbol{x}) &= \boldsymbol{k}_n (\boldsymbol{x})^T (\boldsymbol{K}_n + \sigma^2 \boldsymbol{I}_n)^{-1} \boldsymbol{y}_n \\ \\ \kappa_n(\boldsymbol{x}, \boldsymbol{x'}) &= k(\boldsymbol{x}, \boldsymbol{x'}) - \boldsymbol{k}_n (\boldsymbol{x})^T (\boldsymbol{K}_n + \sigma^2 \boldsymbol{I}_n)^{-1} \boldsymbol{k}_n (\boldsymbol{x}) \\ \end{align}$

である。

目的関数の評価値 $y$ の事後分布は， $y = f(\boldsymbol{x}) + \varepsilon, \varepsilon \sim \mathcal{N}(0, \sigma^2)$ より，

$\begin{align} y &\sim \mathcal{N}(\mu_n(\boldsymbol{x}), \sigma_n^2 (\boldsymbol{x})) \\ \\ \sigma_n^2 (\boldsymbol{x}) &= \kappa_n(\boldsymbol{x}, \boldsymbol{x}) + \sigma^2 \\ \end{align}$

となる。

期待改善量獲得関数の定義

$n$ 回目のトライアルまでの目的関数の評価値のうち最小のものは， $y_n^* = \min _{1 \leq i \leq n} y_i$ と書ける。

この $y_n^*$ と任意の $\boldsymbol{x}$ に対して，観測値 $y=y(x)$ の $y_n^*$ からの改善量は $\max(0, y_n^* - y)$ である。

期待改善量獲得関数とは，この改善量の期待値を最大化するように $\boldsymbol{x}$ を選ぶ獲得関数である。

改善確率量

$\begin{align} \alpha_{EI}(\boldsymbol{x}) = \mathbb{E}[\max(0, y_n^*- y) ] \\ \end{align}$

観測値 $y$ は正規分布にしたがう。またこの期待値は解析的に求めることができ，標準正規分布の確率密度関数 $\phi(x)$ と累積分布関数 $\Phi(z)$ を用いると，計算結果は以下のようになる。

$\begin{align} \alpha_{EI}(\boldsymbol{x}) = (y_n^* - \mu_n(\boldsymbol{x})) \Phi \left( \frac{y_n^* - \mu_n(\boldsymbol{x}) }{ \sigma_n(\boldsymbol{x}) } \right) + \sigma_n(\boldsymbol{x}) \phi \left( \frac{y_n^* - \mu_n(\boldsymbol{x}) }{ \sigma_n(\boldsymbol{x}) } \right) \\ \end{align}$

計算量

改善確率量獲得関数の計算量は，改善確率量獲得関数と同様に，

$\begin{align} O(CN + dN^3 + dTN^2) \\ \end{align}$

で表される。ただし，

$C$ : 候補点 $\boldsymbol{x}_{n+1}$ を目的関数 $f$ に与えて観測値 $y_{n+1}$ を得る時間
$N$ : トライアル回数
$d$ : 入力データの次元数
$T$ : 勾配計算(例えばBFGS法)の反復回数

である。

獲得関数の性質

期待改善量獲得関数は，関数値や勾配が解析的に計算でき，比較的高速に最大化できることがメリットである。

また改善確率量獲得関数において， $y_n^*$ は，これまでに獲得した観測値 $y_i$ に依存するので，探索と活用のトレードオフを十分に取ることができないというデメリットがあった。
一方で期待改善量獲得関数では， $y_n^*$ は実用上良い性能を発揮することが知られている。そのため実用において期待改善量獲得関数は，まず試すべき獲得関数の1つである。

3.4 信頼下限獲得関数

本節では，信頼下限(lower confidence bound)と呼ばれる獲得関数について説明している。
この獲得関数は，事後分布の期待値と標準偏差を上手いバランスで足し合わせ，これを最大化するように次の探索点を選ぶというものである。
単純であるため理論的な解析をしやすい反面，実用的な性能はそれほど高くない。

獲得関数の定義

目的関数の評価値 $y$ の事後分布が $\mathcal{N}(\mu_n(\boldsymbol{x}), \sigma_n^2(\boldsymbol{x}))$ にしたがうとすると，信頼下限獲得関数は以下のようになる。

$\begin{align} \alpha_{LCB}(\boldsymbol{x}) = -(\mu_n(\boldsymbol{x}) - \sqrt{\beta_n} \sigma_n(\boldsymbol{x})) \\ \end{align}$

ただし $\beta_n$ は事前に決めるべきハイパーパラメータで， $\beta = c \log n$ ( $c$ は定数)のように決める。

計算量

信頼下限獲得関数の計算量は，期待改善量獲得関数と同様に，

$\begin{align} O(CN + dN^3 + dTN^2) \\ \end{align}$

で表される。

獲得関数の性質

信頼下限獲得関数は，計算が高速に行なえるというメリットがあるが，探索と活用のトレードオフの探索に寄りすぎる，という傾向がある。

まとめと感想

今回は，「第3章ベイズ最適化のアルゴリズム」のうち，最も基本的な獲得関数である，期待改善量獲得関数について学んだ。

期待改善量獲得関数は，確率量獲得関数と異なりデメリットがあまり紹介されていなかった。期待値は，確率密度関数のパラメータを推定したり，リスクを評価する際にも用いられる一般的な演算であるので，獲得関数にも用いられるのは自然な発想であると感じた。今後実際に使っていく中で，デメリットについても把握していきたい。

本記事を最後まで読んでくださり，どうもありがとうございました。