「増補改訂版ベイズ最適化」を読む　～第5章ベイズ最適化の理論解析 ⑨(補足)最大情報獲得量の評価の流れ(全体編)～

はじめに

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

本記事は，「第5章　ベイズ最適化の理論解析」における，最大情報獲得量の解析に関する参考論文の読書メモである。

5.4.2 最大情報獲得量の解析の補足

5.4.2節では，最大情報獲得量の上界評価の結果を示していた。この評価の導出は，
S. Vakili et al. "On Information Gain and Regret Bounds in Gaussian Process Bandits" にまとめられていた。

arxiv.org

この論文をもとに，上界評価に関する証明の流れを確認した。なお本論文において，上界評価の証明はかなり丁寧に説明されているが，本記事では証明のおおまかな流れをまとめている。また扱っている変数は，この論文ではなく本書の表記にできるだけ合わせた。

本記事は，「増補改訂版ベイズ最適化」を読む～第5章ベイズ最適化の理論解析 ⑧(補足)最大情報獲得量の評価の流れ(準備編)～ - jiku logの続きである。

目的

この評価の目的は，最大情報獲得量 $\gamma_t$ に関する不等式に基づき，この上界を評価することである。
最大情報獲得量は，情報獲得量

$\begin{align} I(\boldsymbol{y}_t; \boldsymbol{f}_t) = \frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} \boldsymbol{K}_t ] \\ \\ \end{align}$

の最大値として定義される。

$\begin{align} \gamma_T = \sup_{\boldsymbol{x}_i \in \mathcal{X}, i=1,...,T} I(\boldsymbol{y}_t; \boldsymbol{f}_t) \\ \\ \end{align}$

基本方針

情報獲得量にはカーネル関数が含まれているので，このカーネル関数に関する評価を行なうことになる。そのままだと評価がしづらいので，Mercerの定理により再生核ヒルベルト空間(RKHS)上の固有関数に展開する(Mercer表現)ことを考えるが，この固有関数は無限次元であり扱いづらい。

そのため，Mercer表現を有限次元空間に射影してから評価を行なう。有限次元の成分を取り出すことで，この部分は行列に関する不等式によって，評価を行なうことが可能になる。

準備

準備として，「増補改訂版ベイズ最適化」を読む～第5章ベイズ最適化の理論解析 ⑧(補足)最大情報獲得量の評価の流れ(準備編)～ - jiku log　にカーネル行列の分解に関する説明を行なった。

最大情報獲得量の上界評価の流れ

以下では，本書の定理5.4.8の証明の流れを，参考論文のAppendices A に沿って確認した。

Step 1. 最大情報獲得量の分解

カーネル行列の分解 $\boldsymbol{K} = \boldsymbol{K}_{P, t} + \boldsymbol{K}_{O, t}$ を用いて，情報獲得量を

$\begin{align} I(\boldsymbol{y}_t; \boldsymbol{f}_t) &= \frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} \boldsymbol{K}_t ] \\ \\ &= \frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} (\boldsymbol{K}_{P, t} + \boldsymbol{K}_{O, t}) ] \\ \\ \end{align}$

と表す。このようにすると， $\boldsymbol{K}_{P, t}$ に関する部分である $\frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} \boldsymbol{K}_{P, t} ]$ と， $\boldsymbol{K}_{O, t}$ に関する部分に分解できる。

Step 2. Kpに関する部分の評価

$\boldsymbol{K}_{P, t}$ に関する部分である

$\begin{align} \frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} \boldsymbol{K}_{P, t} ] \\ \\ \end{align}$

の評価を行なう。

Step 2-1. Weinstein–Aronszajn identity

$\boldsymbol{K}_{P, t}$ の部分を評価するために，

$\begin{align} \boldsymbol{K}_{P, t} = (\boldsymbol{\Phi}_{t, D} \boldsymbol{\Lambda}_{D}^{1/2}) (\boldsymbol{\Lambda}_{D}^{1/2} \boldsymbol{\Phi}_{t, D}^T) \\ \\ \end{align}$

のように表す。

ここで， $\det (I + AB) = \det (I + BA)$ という等式(Weinstein–Aronszajn identity)を用いると，グラム行列

$\begin{align} \boldsymbol{G}_t = (\boldsymbol{\Lambda}_{D}^{1/2} \boldsymbol{\Phi}_{t, D}^T) (\boldsymbol{\Phi}_{t, D} \boldsymbol{\Lambda}_{D}^{1/2})\\ \\ \end{align}$

を用いて

$\begin{align} \frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} \boldsymbol{K}_{P, t} ] = \frac{1}{2} \log \det [ \boldsymbol{I}_D + \sigma^{-2} \boldsymbol{G}_t ]\\ \\ \end{align}$

のように表すことができる。なおこのグラム行列は，正定値行列である。

Step 2-2. 正定値行列に関する不等式

参考論文で証明されているように，正定値行列 $\boldsymbol{P} \in \mathbb{R}^{n \times n}$ について，

$\begin{align} \log \det (\boldsymbol{P}) \leq n \log (\mathrm{tr}(\boldsymbol{P}) / n) \\ \\ \end{align}$

が成り立つ。これは相加相乗平均の関係から導かれる。

Step 2-3. Kpに関する部分の評価

先に示したグラム行列 $\boldsymbol{G}_t$ のトレースは，カーネル関数で表現することができ，

$\begin{align} \lVert \boldsymbol{\phi}_D (\boldsymbol{x}) \boldsymbol{\Lambda}_D^{1/2} \rVert \leq \bar{k} \\ \\ \end{align}$

のように上界評価ができる。なおここで，仮定5.4.2の2番目の仮定を用いた。

これと，Step 2-2. の正定値行列に関する不等式を用いると，最終的に

$\begin{align} \frac{1}{2} \log \det [ \boldsymbol{I}_t + \sigma^{-2} \boldsymbol{K}_{P, t} ] \leq \frac{D}{2} \log \left( 1 + \frac{\bar{k}t}{\tau D} \right)\\ \\ \end{align}$

(ただし， $\tau = \sigma^{-2}$ )が得られる。

Step 3. Koに関する部分の評価

2つの正定値行列のトレースに関する不等式

$\begin{align} \mathrm{tr} (P_1 P_2) \leq \bar{\lambda}_{P_1} \mathrm{tr}(P_2) \\ \\ \end{align}$

(ただし $\leq \bar{\lambda}_{P_1}$ は $P_1$ の最大固有値)を用いると，情報獲得量の $\boldsymbol{K}_{O, t}$ に関する部分の上界は， $\mathrm{tr}(\boldsymbol{K}_{O, t})$ となる。

これと，仮定5.4.2の3番目の仮定および不等式 $\log (1+z) \leq z$ を用いると，最終的に

$\begin{align} \text{情報獲得量の$\boldsymbol{K}_{O, t}$に関する部分} \leq \frac{t \xi_D}{2 \tau} \\ \\ \end{align}$

Step 4. 最大情報獲得量の上界評価

Step 1. ～ Step 3.の結果より，情報獲得量について

$\begin{align} I(\boldsymbol{y}_t; \boldsymbol{f}_t) \leq \frac{D}{2} \log \left( 1 + \frac{\bar{k}t}{\tau D} \right) + \frac{t \xi_D}{2 \tau} \\ \\ \end{align}$

が得られる。よって最大情報獲得量について，

$\begin{align} \gamma_T = \sup_{\boldsymbol{x}_i \in \mathcal{X}, i=1,...,T} I(\boldsymbol{y}_t; \boldsymbol{f}_t) \leq \frac{D}{2} \log \left( 1 + \frac{\bar{k} T}{\tau D} \right) + \frac{T \xi_D}{2 \tau} \\ \\ \end{align}$

となり上界の評価が得られた。

まとめと感想

今回は，「第5章　ベイズ最適化の理論解析」における，最大情報獲得量の解析に関する参考論文を読み，証明の流れをまとめた。

最大情報獲得量 $\gamma_T$ の上界評価について，その導出手順を確認した。
カーネル関数をMercer展開により固有関数へ分解し，有限次元部分と無限次元部分に切り分けることで，有限次元成分に対して行列不等式を適用できる形に変換している。

有限次元成分は固有値が大きい上位 $D$ 個に対応し，残差成分は固有値が小さい高次元成分として扱われる。この分解により，情報獲得量を有限次元部分と残差部分に分け，それぞれに仮定に基づく上界評価を適用する流れが明確になった。特に，Weinstein–Aronszajn identity の利用により，行列式の評価をより扱いやすい形に変形している点が重要である。