jiku log

データサイエンスの核心を掴む : 学びと発見の記録

最終更新日

「ベイズ最適化」を読む　～第8章 並列ベイズ最適化～

ベイズ最適化

はじめに

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

本記事は，「第8章 並列ベイズ最適化」に関する読書メモである。

  • 本書の紹介ページ

www.kindaikagaku.co.jp

目次

第8章 並列ベイズ最適化

本章では，ベイズ最適化を並列計算する場合について，説明している。

8.1 並列最適化とは

本章では，ブラックボックス最適化問題において並列最適化 (parallel optimization)を実行する場合について説明している。

本節では基本的な用語と，並列計算の方法である同期/非同期について，および並列ベイズ最適化とかかわりの深いバッチ最適化について説明している。

ワーカーと計算機

ある1つのトライアルを実行する計算の主体をワーカー(worker)とよぶ。1つのワーカーは，同時に1つのトライアルしか実行できないとする。

複数のワーカーを計算機に割り当てるには，いくつかの方法がある。

計算機の台数 コア スレッド
1 同じ計算機に同居 同じコアに同居 異なるスレッドごとにワーカーが存在
2 同じ計算機に同居 異なるコアにワーカーが存在 ―
3 複数台の計算機にワーカーが存在 ― ―

同期/非同期

実行されているワーカーは非同期であるとする。すなわち，あるワーカーが実行しているトライアルが終了した場合，他のワーカーのトライアルの終了を待たずに次のトライアルを実行するものとする。

一方で，並列最適化向けのいくつかのアルゴリズムは，同期的な設定に合わせて作られている。
これは，

  • 複数の探索点を選んだあとに，それらをキューに詰めておく
  • トライアルが実行され始めた段階でキューから探索点を1つ取り出す
  • もしその際にキューが空ならば，探索点を複数選びなおす

とすれば，非同期な計算を行なうワーカーに対しても，同期的な設定に合わせて作られたアルゴリズムでも利用できることになる。

バッチ最適化との関係

バッチ最適化 (batch optimization)は，ブラックボックス最適化において，一度に複数の入力に対する出力を観測できる問題設定である。すなわち，同時に複数の探索点を選ぶことになり，同期的な設定に合わせて作られた並列最適化アルゴリズムは，バッチ最適化にも利用することができる。
また非同期な並列最適化アルゴリズムについても，バッチサイズ分の探索点を選択した後にこの結果を返せば，バッチ最適化を扱うことが可能になる。

したがってバッチ最適化は，同期/非同期を問わず，並列最適化のアルゴリズムを利用することができる。

8.2 並列最適化における問題点

本節では，並列ベイズ最適化でしばしば生じる問題点について説明している。

主な問題点

並列最適化においては，実行中の他のトライアルの情報を全く利用していない。その結果，似たような探索点が実行されやすくなる(さらに，決定的なモデルや獲得関数を用いている場合は，まったく同じ探索点が実行される)という問題点がある。似たような探索点を実行している場合，幅広く探索することを目的としている並列計算の意味がないことになる。

対処法

主な対処法としては，

  • 現在実行中のトライアルの情報を，何らかの形で仮定する
  • そもそも同時に複数の点を選択する

という対策が考えられる。

ただし，それぞれの方法には，以下のようなメリット・懸念点が存在する。

対処法 メリット 懸念点
1 現在実行中のトライアルの情報を，何らかの形で仮定する 比較的高速に動作する 仮定が外れると性能が劣化する
2 そもそも同時に複数の点を選択する 実行中のトライアルを考慮する必要がなくなる 小さな並列化数・探索空間の次元でしか実行できない

8.3 嘘つき法

本節では，並列ベイズ最適化の手法の1つである嘘つき法 (constant liar method)について説明している。

嘘つき法は，実行中のトライアルの未だ観測していな目的関数の値を，適当な値に仮定する方法である。

n番目のトライアルにおいて，履歴 \mathcal{D}_n = \{ (\mathbfit{x}_i, y_i) \}_{i=1}^nが得られているとする。これらは完了済みのトライアルの集合である。
その後， j番目のトライアルにおいて， r番目の他のワーカーにおける探索点の集合を \{ \mathbfit{x}_j ^r\}とする。嘘つき法では，この探索点に対応する目的関数値に，仮の値 y_j^rを設定する。
そして，履歴と実行中の探索点を合わせて， \tilde{\mathcal{D}} = \mathcal{D}_n \cup \{ \mathbfit{x}_j^r, y_j^r \}を作り，これを用いてガウス過程回帰を行なう。

仮の値としては，履歴 \mathcal{D}_n内の y_iの最大値を用いることが多い。

8.4 局所ペナルティ法

前節で説明した嘘つき法では，ガウス過程回帰モデルを作る時のデータに工夫を行ない，獲得関数には何の工夫も行なわなかった。
本節で説明している局所ペナルティ法では，ガウス過程回帰モデルの構築には工夫を行なわず，獲得関数に工夫を行なう。


局所ペナルティ法では，他のワーカーによって実行中である探索点の集合 \mathbfit{x}_j^rについて，ペナルティ \phi(\mathbfit{x}, \mathbfit{x}_j^r)を与えて獲得関数を構築する。


\begin{align} \alpha_{\mathrm{LP}}(\mathbfit{x}) = g(\alpha(\mathbfit{x})) \prod_j \phi(\mathbfit{x}, \mathbfit{x}_j^r) \\ \end{align}

\alphaは何らかの獲得関数で，関数 gは g(z) = \log(1+e^z)のように非負の値を取る関数とする。また \phiは [ 0, 1 ]で微分可能であり， \lVert \mathbfit{x}- \mathbfit{x}_j^r \rVert に対して非減少な関数である。

局所ペナルティ法では，実行中のトライアルの探索点に関する局所的な情報を取り入れて獲得関数を構築する。ペナルティ関数を，事後分布を用いて定義することによって \mathbfit{x}_j^rにかかるペナルティを制御できる。ただし，ペナルティ関数の設計に工夫する必要がある。

8.5 モンテカルロ獲得関数

本節では，モンテカルロ獲得関数について説明している。モンテカルロ獲得関数は，獲得関数自体に修正を行なうことで事前に定めた数の探索点を一気に選べるようにする。

再パラメータ化によるトリック

期待値による獲得関数の表現

獲得関数のうち多くは，以下のように事後分布の期待値として書くことができる。


\begin{align} \alpha(\mathbfit{x}) = \int u_{\theta}(y) p(y \lvert \mathbfit{x}, \mathcal{D}_n) dy \\ \end{align}

ただし u_{\theta} : \mathbb{R} \leftarrow \mathbb{R}は何らかの関数で， \thetaは yに依存しないパラメータである。

  • 例 : 期待改善量
    • \theta = y_n^*
    • u_{\theta}(y) = \max (0, y_n^* - y)
  • 例 : エントロピー探索
    • \theta = \mathbfit{x}
    • u_{\theta}(y) = \mathrm{KL} (p_{\min} (\mathbfit{x}_* \lvert \mathcal{D}_n \cup (\mathbfit{x}, y)) \lVert u_{\mathcal{X}}(\mathbfit{x}_*) )


このように期待値で表現できることは，並列ベイズ最適化においては困難を引き起こす。例えば，一気に q個の探索点を同時に選ぶ獲得関数を設計することを考える。
X \in \mathbb{R}^{q \times d}として，獲得関数を以下のように拡張する。


\begin{align} \alpha(X) = \int u_{\theta}(\mathbfit{y}) p(\mathbfit{y} \lvert X, \mathcal{D}_n) d\mathbfit{y} \\ \end{align}

ここで p(\mathbfit{y} \lvert X, \mathcal{D}_n) は q次元の正規分布になるので，上記の積分は q次元の多重積分になり，解析的な計算および獲得関数の最大化も難しくなる。

モンテカルロ近似

モンテカルロ獲得関数は，多重積分をモンテカルロ法によって近似する手法である。


\begin{align} \alpha(X) \simeq \frac{1}{M} \sum_{j=1}^M u_{\theta}(\mathbfit{y}_j), \quad \mathbfit{y}_j \sim p(\mathbfit{y} \lvert X, \mathcal{D}_n) \\ \end{align}

この近似によって多重積分を回避することはできるが，獲得関数の Xについての勾配が計算できない。

再パラメータ化

そこで，再パラメータ化によるトリック (reparameterization trick)を用いる。

\mathbfit{y} \sim p(\mathbfit{y} \lvert X, \mathcal{D}_n ) = \mathcal{N}(\mathbfit{y} \lvert \mathbfit{\mu}_q(X), \Sigma_q(X))である。ここで，


\begin{align} \mathbfit{y} &= L_q(X) \mathbfit{z} + \mathbfit{\mu}_q (X) \\ \\ L_q(X) L_q(X)^T &= \Sigma_q(X) \\ \\ \mathbfit{z} &\sim \mathcal{N}(\mathbfit{z} \lvert \mathbfit{0}, \mathbfit{I}_d) \\ \end{align}

とする。ただし L_q(X)は \Sigma_q(X)のコレスキー分解であり，下三角行列である。

この変換は，1次元で表現すると z = (\mu - y) / \sigma \Leftrightarrow y = \sigma z + \muという標準化に相当する。

再パラメータ化を用いると，


\begin{align} \alpha(X) &= \int u_{\theta} (L_q(X) \mathbfit{z} + \mathbfit{\mu}_q (X)) \mathcal{N}(\mathbfit{z} \lvert \mathbfit{0}, \mathbfit{I}_d) d\mathbfit{z} \\ \\ &\simeq \frac{1}{M} \sum_{j=1}^M u_{\theta} (L_q(X) \mathbfit{z}_j + \mathbfit{\mu}_q (X)), \quad \mathbfit{z}_j \sim \mathcal{N}(\mathbfit{z} \lvert \mathbfit{0}, \mathbfit{I}_d) \\ \end{align}

となる。上式における u_{\theta}が微分可能であれば，上式の右辺は勾配の計算ができるので，L-BGFSなどの勾配ベースの手法を用いて最大化できる。
ただし qはあまり大きすぎない方がよいとされている。

まとめと感想

今回は，「第8章 並列ベイズ最適化」について学んだ。

計算を効率化させるために，並列計算は1つの手段としてよく挙げられるが，ベイズ最適化においては様々な工夫が必要になっていることが理解できた。
再パラメータ化のトリックは，モンテカルロ計算において入力変数 \mathbfit{x}の情報を無くさないようにするためのテクニックであるが，様々なシーンで利用できそうであった。


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

参考サイト


ランキング参加中
統計