EM（expectation–maximization）アルゴリズムの基礎

観測されるデータをまとめて$y$と書くことにし, 次の対数尤度関数を最大にする$\theta$を求めたいとする.

$$ \ell(\theta) = \log p(y|\theta) $$

ここで$p(\cdot)$は確率変数ごとに定義された密度を表す記号とした（つまり$p(y)$と$p(z)$が同じ関数とは限らない）.

適当な確率変数$z$を用いて,
$$ p(y|\theta) = \int p(y, z|\theta) \, dz $$
と書けるとしよう. ここでの積分記号は定義域全区間に渡る積分を意味する.
この記事ではそれ以外の範囲での積分は出てこないので混乱することは多分ないだろうと思う.

条件付き確率より,
$$ p(z|y,\theta) = p(y, z|\theta) / p(y|\theta) $$
であるから, 両辺の対数の期待値を取り,
$$ \log p(y|\theta) = E[\log p(y, z|\theta)] - E[\log p(z|y,\theta)] \tag{1} $$
も成り立つ. ここでの期待値は「$y$を所与としたときの$z$の条件付き期待値」,
$$ E[f(z)] = \int f(z) p(z|y) \, dz $$
である. これも単に$E[\cdot]$という記号で書いてしまったが, この記事ではこれ以外の分布による期待値は出てこない.

さて, EMアルゴリズムでは, (1)式の第1項を求め（期待値を取る操作なのでこれをEステップと呼ぶ）, 第1項が大きくなるようにパラメータを更新する（最大化を目指す操作なのでこれをMステップと呼ぶ）.

EMアルゴリズムでは右辺の第2項は明示的に計算する必要がない.

なぜならば, ある$\theta_0$を固定して任意の$\theta$を考えると,
\begin{align*} & E[\log p(z|y,\theta)] -E[\log p(z|y,\theta_0)]\\ &= \int \log \left(\frac{p(z|y,\theta)}{p(z|y,\theta_0)}\right) p(z|y,\theta_0) \, dz \\ & \le \log\left( \int \frac{p(z|y,\theta)}{ p(z|y,\theta_0)} p(z|y,\theta_0) \, dz \right) = \log 1 =0\\ \end{align*}
が成り立つ. 3行目はイェンセンの不等式による.

よって, 「第1項が大きくなるようにパラメータを更新する」すなわち
$$ E[\log p(y, z|\theta)] -E[\log p(y,z|\theta_0)] \ge 0 $$
が満たされていれば,
$$ \log p(y|\theta) -\log p(y|\theta_0) \ge 0 $$
も成り立つことがわかる.

これがEMアルゴリズムの基礎である.

MAP推定の場合も, 尤度に事前分布の密度をかけ合わせるだけで全く同様の議論ができる.