アルゴリズム
機械学習
ベイズ

EMアルゴリズムのメモ 「ベイズ推定とグラフィカルモデル:コンピュータビジョン基礎1 セクション7」

Udemyの「ベイズ推定とグラフィカルモデル:コンピュータビジョン基礎1」のセクション7のEMアルゴリズムの説明が非常にわかりやすかったので、EMアルゴリズムの部分だけ抽出して文章でまとめました。

なにが目的?

潜在変数(隠れ変数)をもつようなモデルの最尤推定解を求めること

そもそも潜在変数を使ったモデルなんて何が嬉しい?

潜在変数:観測されるデータ(サンプル)には現れてこない変数

$$p(x|\theta) = \sum_z p(x,z|\theta)$$
ここで、$x$は観測変数, $z$が潜在変数,$\theta$はパラメータ。
潜在変数でモデル化した場合には、潜在変数に関して周辺化することで、潜在変数がない式に変換できる。

嬉しさ:あるデータの背後にある状態を表現することができ、モデルに関する洞察を深めることができる
ex) 混合ガウス分布, 主成分分析モデル

なんでこんな難しいアルゴリズムを使う必要があるのか?

やりたいことは、データ$X=\{x_i\}$が与えられたときに、以下の対数尤度関数を最大化するようなモデルパラメータ$\theta$を求めることである。いま潜在変数は離散確率変数でK個あるとする。

$$\hat{\theta} = \mathop{\rm arg\,max}\limits_{\theta} \ln [ p(X|\theta) ]$$
$$\ln [p(X|\theta) ]=\sum_i \ln \left[ \sum_{k=1}^K p(x_i, z_k|\theta) \right]$$

素朴な疑問:微分してゼロとおけばいいのでは?
対数の中に潜在変数の周辺化のための総和があるために、$p$が指数型分布族であっても簡単な式に普通はなってくれない!

そのため、その他の最適化手法を使うほかなく、そのひとつの方法がEMアルゴリズム。

EMアルゴリズム

アルゴリズム概要

EMアルゴリズムのメインアイデアは、対数の中に総和が入るような計算はしにくいので、その式の下界を考えてみたということである。

ここで登場するのが、イェンセンの不等式
イェンセンの不等式を使うと、「ある確率変数の対数の期待値はある確率変数の期待値の対数以下」になるということがいえる。これを使うと、以下の不等式が導ける。

$$\sum_i \sum_{k=1}^K q_i(z_k)\ln \left[\frac{p(x_i, z_k|\theta)}{q_i(z_k)} \right] \leq \sum_i \ln \left[ \sum_{k=1}^K p(x_i, z_k|\theta) \right]$$

ここで、$q(z_k)$は潜在変数に関してのなんらかの確率分布である(後述)。この左辺が下界である。
EMアルゴリズムはこの下界を使って、2ステップに分けて右辺を最大化する。

ステップ 内容
Eステップ パラメータ$\theta$を固定させたもとで、${q_i(z_k)}$を変化させて下界を最大化する。これは、下界の関数自体が変化することに相当。
Mステップ ${q_i(z_k)}$を固定させたもとで、下界を最大化するようなパラメータ$\theta$を求める。

この2ステップの繰り返しにより、対数尤度は極大点に達しない限り増加することが証明できるので、これによって目的の最尤推定解を求めることが出来る。

Eステップの最適化

Eステップにおいて$q_i(z_k)$としてどんな関数にすれば下界が最大になるだろうか?
下界について以下の式変形を施す。

\begin{eqnarray}
\sum_i \sum_{k=1}^K q_i(z_k)\ln \left[\frac{p(x_i, z_k|\theta)}{q_i(z_k)} \right] &=& \sum_i \sum_{k=1}^K q_i(z_k)\ln \left[ \frac{p(z_k|x_i,\theta)p(x_i|\theta)}{q_i(z_k)} \right] \\
&=&\sum_i \sum_{k=1}^K q_i(z_k)\ln \left[ p(x_i|\theta) \right] + \sum_i \sum_{k=1}^K q_i(z_k)  \ln\left[ \frac{p(z_k|x_i, \theta)}{q_i(z_k)} \right] \\
&=& \sum_i \ln \left[ p(x_i|\theta) \right] +\sum_i \sum_{k=1}^K q_i(z_k) \ln \left[ \frac{p(z_k|x_i, \theta)}{q_i(z_k)} \right]
\end{eqnarray}

さて、今やりたいのは$q_i(z_k)$を変化させて下界を最大化したい。そのため、$q_i(z_k)$と関係ない第一項目は無視していい。
第2項を最大化するということは、以下の式を最大化するように$q_i(z_k)$を設定すればいいことになる。

$$\hat{q_i}(z_k) = \mathop{\rm arg\,max}\limits_{q_i(z_k)} \sum_{k=1}^K q_i(z_k) \ln \left[\frac{p(z_k|x_i, \theta)}{q_i(z_k)} \right]$$

このことは、つまり以下の式を最小化するような$q_i(z_k)$を設定することに等しい。

$$\hat{q_i}(z_k) = \mathop{\rm arg\,min}\limits_{q_i(z_k)} \{ -\sum_{k=1}^K q_i(z_k) \ln \left[ \frac{p(z_k|x_i, \theta)}{q_i(z_k)} \right] \}$$

この式は見ればわかるようになんと$p(z_k|x_i,\theta)$と$q_i(z_k)$とのKullback Leiblerダイバージェンスになっている!
実は、この式の上界が0で抑えられることを示すことができるため、結局このKLダイバージェンスを0にすることができることが証明できる。
KLダイバージェンスが0になるときというのは、$q_i(z_k) = p(z_k|x_i, \theta)$のときであるため、
$$\hat{q_i}(z_k) = p(z_k|x_i, \theta)$$
とすればよい。

Mステップの最適化

Eステップの最適化は以下のように式変形していくことができる。

\begin{eqnarray}
\hat{\theta} &=& \mathop{\rm arg\,max}\limits_{\theta}  \sum_i \sum_{k=1}^K q_i(z_k) \ln \left[ \frac{p(x_i, z_k | \theta)}{q_i(z_k)} \right] \\
&=& \mathop{\rm arg\,max}\limits_{\theta}  \sum_i[ \sum_{k=1}^K q_i(z_k) \ln  p(x_i, z_k | \theta) - \sum_{k=1}^K q_i(z_k)\ln q_i(z_k) ] \\
&=& \mathop{\rm arg\,max}\limits_{\theta}  \sum_i[ \sum_{k=1}^K q_i(z_k) \ln  p(x_i, z_k | \theta) ]
\end{eqnarray}

Mステップではこの最後の式を最大化するような$\theta$を求めればいい。
Mステップにおいては、この最後の式を最大化するようなパラメータ$\theta$は簡単にできる必要がある。
いま、対数の中に総和はなくなったので、指数型分布族であればこれは微分してゼロとすることで比較的簡単にできる(?)。

アルゴリズム

今までのことを踏まえると、EMアルゴリズムは以下のようになる。

  1. パラメータの初期値$\theta^{old}$を選ぶ
  2. (Eステップ) $p(Z|X, \theta^{old})$を計算する。
  3. (Mステップ) 以下の式で$\theta^{new}$を計算。

                 \theta^{new} = \mathop{\rm arg\,max}\limits_{\theta} Q(\theta, \theta^{old}) \\
                 Q(\theta, \theta^{old}) = \sum_Z p(Z|X, \theta^{old}) \ln p(X,Z|\theta)
    
  4. 対数尤度関数またはパラメータ値のいずれかについて、収束条件が満たされていれば終了。そうでなければ、$\theta^{old} \leftarrow \theta^{new}$を実行し、Eステップに戻る。

ここまで、読んで以下の資料にあるようなEステップとMステップを交互に行っている図をみると何をやっているかよくわかる。
- MLAC2013 数式を使わずイメージで理解するEMアルゴリズム
- 「ベイズ推定とグラフィカルモデル:コンピュータビジョン基礎1」セクション7-3

補足:EステップはExpectation Stepであるが、どこも期待値なんてとってないように見える。これはMステップで計算される期待値のことをさしており、正直わかりにくい。。。

注意点

  • 一般に尤度関数は多くの極大解があり、EMアルゴリズムはその大域的最適解に必ず収束するわけではない。局所解に収束する場合がある。
  • 下界を最大にするような$\theta$を求めることは簡単である必要がある。

参考文献