一般的な定式化

観測値 $x$ が与えられたとき，確率モデ ル $p(x;\ \theta)$ の最尤推定量を求めることが問題である． 観測される変 数 $x$ は，背後にある完全な確率変数 $y$ の不完全な観測値であるとする． すなわち $y$ から $x$ への多対一の写像 $x = x(y)$が存在するとする． またその逆像を $Y(x)$ とする． 具体的には $y$ の一部の成分だけが $x$ として観測されるという例が典型的 であり，後で述べるように混合分布の場合もそれにあたる．

EM アルゴリズムは適当な初期値 $\theta^{(0)}$ から始め，以下の E と M の各ステップを繰り返すことによって解を更新する． (E と M を合わせて 1 ステップと数えたとき) $t$ ステップ目のパラメータの値を $\theta\tth$ とする．

1. E (Expectation) ステップ : 次で定義される完全データの対数尤度の条件付き期待値 を計算する．
   $$\begin{eqnarray*} Q(\theta\mid x;\ \theta\tth ) &=& {\rm E}_{\theta\tth }\left[... ...t_{Y(x)} p(y\mid x;\ \theta\tth ) \log p(y;\ \theta)\,{\rm d}y. \end{eqnarray*}$$
   
   
   
   
   

2. M (Maximization) ステップ : $Q(\theta\mid x;\ \theta\tth )$ を $\theta$ について 最大化したものを $\theta\tpth$ とおく

特に，完全データの分布 $p(y;\ \theta)$ が指数分布族，

$$p(y;\ \theta) = \exp\{\sum_i F_i(y)\theta_i - \varphi(\theta) + C(y)\},$$ (3.15)

ならば，$Q$ を微分した式がパラメータについての線形方程式になるため，EM ステップは次のような簡単な形で書き表すことができる．

$$\eta_i\tpth = {\rm E}_{\theta\tth }\left[\,F_i(y)\mid x\,\right].$$ (3.16)

ただし，$\eta_i$ は期待値パラメータ $\eta_i = {\rm E}_{\theta}\left[\,F_i(y)\,\right]$ である． $\eta$ と $\theta$ は互いに双対座標系になっており， Legendre 変換により互いに変換することができる． 指数分布族に対してこのような簡単な形の式が得られるの は，3.4.7 で述べる幾何学的な意味づけに関係する．

さて，Dempster らは，EM アルゴリズムが $x$ の尤度を単調に増加させるこ とを示した．

定理 1 (Dempster[30])   EM アルゴリズムは $x$ の尤度を単調に増加させる．

ここではその証明の概略を示しておく． まず，ベイズの定理から，完全 確率変数 $y$ と不完全確率変数 $x$ の分布の間に次の関係が成り立つ．

$$p(y\mid x;\ \theta) = {p(y;\ \theta)\over p(x;\ \theta)}.$$ (3.17)

両辺の対数を取ると，$x$ の対数尤度は

$$\log p(x;\ \theta) = \log p(y;\ \theta) - \log p(y\mid x;\ \theta),$$ (3.18)

となる． そこで両辺を，パラメータ $\theta\tth$ を持ち，観測された $x$ についての $y$ の条件付き分布で期待値を計算すると，

$$\log p(x;\ \theta) = {\rm E}_{\theta\tth }\left[\,\log p(y;\ ... ..._{\theta\tth }\left[\,\log p(y\mid x;\ \theta)\mid x\,\right],$$ (3.19)

となる． 右辺第 1 項は E ステップで計算される $Q$ である． ここで，第 2 項を

$$H(\theta\mid x;\ \theta\tth ) = \int_{Y(x)} p(x\mid y;\ \theta\tth ) \log p(x\mid y;\ \theta)\,{\rm d}y,$$ (3.20)

とおき， $\theta=\theta\tpth$ とおくと，M ステップで $Q$ を最大化するので，

$$Q(\theta\tpth\mid x;\ \theta\tth ) \ge Q(\theta\tth\mid x;\ \theta\tth ),$$ (3.21)

を満たす． 一方 Jensen の不等式より $H$ は $\theta=\theta\tth$ で最大値を 取るので，

$$H(\theta\tpth\mid x;\ \theta\tth ) \le H(\theta\tth\mid x;\ \theta\tth ),$$ (3.22)

を満たす． この両者から，

$$\log p(x;\ \theta\tpth ) \ge \log p(x;\ \theta\tth ),$$ (3.23)

が成り立ち，$x$ に関する尤度の単調性が示された． 収束性に関する厳密な 議論は Wu[91] によって行われ，EM アルゴリズムが適当な正則条件 のもとで局所最適解または鞍点に収束することが示されている．

次に，EM アルゴリズムの収束の速度について知られている結果を述べる． 真 の解 $\theta^*$ の近傍での EM アルゴリズムの振舞いは次のように一次近似 できる．

$$\theta\tpth - \theta^* = I_c^{-1}(\theta^*; x) I_m(\theta^*; x) (\theta\tth - \theta^*).$$ (3.24)

ここで， $I_c(\theta; x)$ は完全変数の分布の条件付き Fisher 情報量

$$I_c(\theta; x) = -{\rm E}_{\theta}\left[\,{\partial^2\log p... ... \partial\theta\partial\theta^{\rm T}}\Biggm\vert x\,\right],$$ (3.25)

であり， $I_m(\theta, x)$ は条件付き分布の条件付き Fisher 情報量

$$I_m(\theta; x) = -{\rm E}_{\theta}\left[\,{\partial^2\log p... ... \partial\theta\partial\theta^{\rm T}}\Biggm\vert x\,\right],$$ (3.26)

である． $I_c^{-1} I_m$ は定性的には観測されない情報の割合を表 している． したがって式 (3.24) は，$x$ の 不完全性が増す に連れ収束が遅くなることを示している．