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

作って遊ぶ機械学習。

~基礎的な確率モデルから最新の機械学習技術まで~

MCMCと変分近似

変分近似 MCMC 動く

今回は代表的な2つの確率分布の近似推定手法であるMCMCと変分近似を比較します。変分近似に関しては複数回にわけて記事にしているのでそちらを参照されるとよいです。

変分近似(Variational Approximation)の基本(1)

変分近似(Variational Approximation)の基本(2)

変分近似(Variational Approximation)の基本(3)

さて、MCMC(Markov Chain Monte Carlo)は、サンプリング手法の一種です。サンプリングでは、解析的に計算できない事後分布の統計量などを、データをサンプリングすることによって近似的に求めます。今回はMCMCの中でも一番シンプルで便利なギブスサンプリング(Gibbs sampling)と呼ばれる手法を紹介します。

前回取り上げた2次元ガウス分布の近似問題をまた例に取り上げます。今回はこの分布を近似推定するギブスサンプリングのアルゴリズムを導き、過去に導出した変分近似による推定アルゴリズムと簡単な比較してみたいと思います。

 

[必要な知識]

下記をさらっとだけ確認しておくといいです。

 

 

ギブスサンプリングでは、推定したい多変数の事後分布$p(z_1, z_2|x)$に対して、下記のような手続きで$n+1$個目のサンプル値$z_1^{(n+1)}$と$z_2^{(n+1)}$を拾ってきます。

\[ z_1^{(n+1)} \sim p(z_1|z_2^{(n)}, x) \\ z_2^{(n+1)} \sim p(z_2|z_1^{(n+1)}, x) \]

他の変数のサンプル値で条件付けされた分布から新たにサンプル取る、というような手続きですね。これ以上の多変数の場合も同様です。事後分布から一度にすべての変数のサンプルを取るのが難しいのであれば1つずつ変数をサンプルしてしまえばいい、という発想です。この方法が真の事後分布からサンプルしていることを証明することができるのですが、今回は割愛します。*1

 

さて、変分近似の更新則と比較してみると面白いです。 

<変分近似>

- より単純な事後分布の関数形を仮定し、積分を解析的に行えるようにする。

- 注目している確率分布$q(z_1)$以外の確率分布に関して期待値を取ることにより、$q(z_1)$を得る。

<ギブスサンプリング>

- より単純な条件付き分布からサンプルし、積分をサンプルで近似する。

- 注目している確率変数$z_1$以外の確率変数をサンプルされた値で固定し、$z_1$をサンプルする。

 

こうして比較してみると、ギブスサンプリングと変分近似が兄弟のような関係になっていることがわかります。あとで見るように、実際にアルゴリズムを導いてみると同じような式が出てきます。

 

さて、前回と同様、今回ギブスサンプリングで推定したいのは下記のような2次元ガウス分布です。

\[ p(x_1,x_2|\mu_1,\mu_2, \Lambda) = \mathcal{N} \Bigl(\left[\begin{array}{r} x_1 \\ x_2 \end{array}\right] \bigg| \left[ \begin{array}{r} \mu_1 \\ \mu_2 \end{array} \right], \left[ \begin{array}{cc} \Lambda_{1,1} & \Lambda_{1,2} \\ \Lambda_{2,1} & \Lambda_{2,2} \end{array} \right]^{-1} \Bigr) \\ \propto exp\Bigl\{ \Bigl(\left[\begin{array}{r} x_1 \\ x_2 \end{array}\right] - \left[ \begin{array}{r} \mu_1 \\ \mu_2 \end{array} \right] \Bigr)' \left[ \begin{array}{cc} \Lambda_{1,1} & \Lambda_{1,2} \\ \Lambda_{2,1} & \Lambda_{2,2} \end{array} \right] \Bigl(\left[\begin{array}{r} x_1 \\ x_2 \end{array}\right] - \left[ \begin{array}{r} \mu_1 \\ \mu_2 \end{array} \right]\Bigr) \Bigr\} \]

前にも触れましたが、推定したい分布が2次元ガウス分布だとわかっているので、実はあんまり意味のない問題を解いていることになります。しかしこの単純な例を使うと、真の分布との間の近似誤差を解析的に計算できるので、2つの手法の近似精度を定量的に比較できるというメリットがあります。というわけで、今回は「1次元のガウス分布は簡単にサンプルできるけど、2次元になるとサンプルできない」という架空の想定で進めたいと思います。

では、実際に条件付き分布を求めてみましょう。$x_2^{(n)}$を固定されたサンプル値であるとして、$x_1$の確率分布を求めてみます。

\[ p(x_1 | x_2^{(n)}, \mu, \Lambda) \propto p(x_1, x_2^{(n)} | \mu, \Lambda) \\ \propto exp\bigl\{-\frac{1}{2} \{x_1^{2}\Lambda_{1,1} -2 x_1 (\Lambda_{1,1} \mu_1 - \Lambda_{1,2}( x_2^{(n)} - \mu_2)) \} \bigr\} \]

これを正規化することにより1次元のガウス分布が得られます。

\[ p(x_1 | x_2^{(n)}, \mu, \Lambda) = \mathcal{N}(x_1| m_1, \Lambda_{1,1}^{-1}) \]

ただし、

\[ m_1 = \mu_1 - \Lambda_{1,1}^{-1}\Lambda_{1,2}(x_2^{(n)} - \mu_2) \]

です。

1次元のガウス分布によるサンプリングは「簡単」なんでしたね。変分近似と似ていますが、分布を細かくした結果が十分に簡単にサンプリングできるような形になっている必要があります*2。また実装でこの式から$x_1^{(n+1)}$をサンプルするには、お使いのプログラミング言語にたぶんあるrandn()のような1次元ガウス分布からサンプルを取るライブラリーを使えばOKです。 

$x_2^{(n+1)}$のサンプルも全く同様なので省略します。

さて、目的は2次元のガウス分布を近似したかったんでした。上の手続きで$N$個のサンプルを得た後、求めたい分布の統計量(平均、分散)は次のように推定することができます。

\[ \hat{\mu} = \frac{1}{N} \sum_{n=1}^{N} \left[\begin{array}{r} x_1^{(n)} \\ x_2^{(n)} \end{array}\right] \\ \hat{\Lambda}^{-1} = \frac{1}{N} \sum_{n=1}^{N} \left[\begin{array}{r} x_1^{(n)} \\ x_2^{(n)} \end{array}\right]\left[\begin{array}{r} x_1^{(n)} \\ x_2^{(n)} \end{array}\right]' - \hat{\mu}\hat{\mu}' \]

 

では実際に動作させてみましょう。 

f:id:sammy-suyama:20160203200821g:plain 

 青い楕円が推定したい真の2次元ガウス分布で、赤い楕円が推定中の分布です。ピンク色の点が実際のサンプルです。最終的に形状(共分散)も含めてきちんと正解の分布に収束していっていることが分かります。これは分解してしまった変数間の相関を補足できない変分近似とは対照的です。(前回の記事参照

次にギブスサンプリングと前回導いた変分近似の近似能力を比較してみたいと思います。評価は、真の分布(2次元ガウス分布)とのKL divergenceを直接計算することにより定量的に求めたいと思います。繰り返しになりますが、今回は既知の2次元ガウス分布を使っているためこのような比較ができるのですが、実際は真の確率分布に対するKL divergenceは解析的には求まりません。

f:id:sammy-suyama:20160203201223p:plain

 本当は2つの手法を比較するためには横軸は実計算時間を取らないとだめなのですが、どっちもこの例では高速すぎるので繰り返し回数にしました。一般的には変分近似の方がギブスサンプリングよりも早く収束するのですが、この例だと分布が十分に簡単なので、ギブスサンプリングの方が少ない繰り返し数であっという間に変分近似(最適値.46)を抜き去っています。

 

以上、今回の記事からわかる範囲と個人的な見解にもとづいて変分近似とギブスサンプリングの利点欠点をまとめます。

<変分近似>

- 良い点

計算が早い。収束判定がしやすく、バグも発見しやすい(目的関数があるので)。

- 悪い点

導出がちょっと大変。近似の仕方によっては重要な相関が取れなくなる。

<ギブスサンプリング>

- 良い点

理論的には真の事後分布からサンプルしていることになる。導出が比較的簡単。並列化しやすい。変分法より適用範囲が広い。*3

- 悪い点

大規模なモデルでは収束が遅い。またどれくらいサンプルすればいいのか判断がしにくい。

 

一般的には小規模問題ならギブスサンプリング、大規模問題なら変分近似、という風に解釈もできますが、計算環境や問題によっても変わってくるので出来れば両方試すのが理想です。

発展的な話題として、2つの技術を組み合わせたような手法を作ることも可能です。他にも、崩壊ギブスサンプリング(collapsed Gibbs sampling)という、日本語だと少し中2病こじらせたような名前の手法があり、これに関してもまた別の機会で書きたいと思います。

*1:サンプリングの手続きが不変(invariant)であることと、エルゴディック(ergodic)であることを示す必要があります。ギブスサンプリングは証明済みであるので安心して使えます。

*2:今回の例のように必ずしも正規化できる必要はありません。よくわからない確率分布が出てきても、例えば棄却サンプリングのような方法を使えばうまく点がサンプルできる可能性があります。

*3:そもそもサンプリング手法が積分を近似するために利用されてきたという背景もあり、ギブスサンプリングの方が積分計算を伴う変分近似より若干適用範囲が広いです。