EM アルゴリスム

EMアルゴリズムは、混合分布モデルのパラメータの推定にも利用できる不完全 データからの学習アルゴリズムであり、最急降下法と同様に解を逐次改良する ことにより次第に最適な解に近づけて行く手法である。直感的にわかりやすく、 しかも初期段階での収束性が速いことが知られている。その基本的な考え方は、 統計学では古くから知られてたが、EMアルゴリズムの一般的な定式化は Dempster等によって行われた[56]。また、最近、AmariはEMアル ゴリズムの幾何学的な意味を明らかにし、なぜアルゴリズムがうまく働くかの 直感的なイメージを与えた[57]。

平均 $\mbox{\boldmath$\mu$}_j$、共分散行列 $\Sigma_j = \sigma_j^2 I$ の正規分布の混 合分布の場合、もしデータがどの正規分布から生成されたのかが全て分かって いれば非常に簡単になる。しかし、実際には、どの正規分布から生成されたの かも含めて推定する必要がある。EMアルゴリズムを適用するためには、どの正 規分布から生成されたのか番号 $z$ を含めたもの $(\mbox{\boldmath$x$},z)$ を完全デー タとみなし、 $\mbox{\boldmath$x$}$ を不完全データとみなす。この場合、完全データ $(\mbox{\boldmath$x$},z)$ の分布は、

$$f(\mbox{\boldmath$x$},z) = \omega_z p(\mbox{\boldmath$x$}\vert z)$$ (53)

のように書ける。また、この分布に従う $N$ 個の完全データに対する対数尤 度は、

$$\hat{l} = \sum_{n=1}^N \log f(\mbox{\boldmath$x$}_n,z_n) = ... ...=1}^N \log \{ \omega_{z_n} p(\mbox{\boldmath$x$}_n\vert z_n)\}$$ (54)

となる。

EMアルゴリズムでは、パラメータの適当な初期値 $\mbox{\boldmath$\theta$}^{(0)}$ から 初めて、Eステップ(Expectation step)とMステップ(Maximization step)と呼 ばれる二つの手続きを繰り返すことにより、パラメータの値を逐次更新する。 今、繰り返し回数 $t$ でのパラメータの推定値を $\mbox{\boldmath$\theta$}^{(t)}$ とす ると、EステップとMステップでは、それぞれ、

Eステップ:

完全データの対数尤度 $\hat{l}$ のデータ $\mbox{\boldmath$x$}$ とパラ メータ $\mbox{\boldmath$\theta$}^{(t)}$ に関する条件付き期待値

$$Q(\mbox{\boldmath$\theta$}\vert\mbox{\boldmath$\theta$}^{(t... ...$},z)\vert\mbox{\boldmath$x$},\mbox{\boldmath$\theta$}^{(t)})]$$ (55)

を計算する

Mステップ:

$Q(\mbox{\boldmath$\theta$}\vert\mbox{\boldmath$\theta$}^{(t)})$ を最大とするパラメータ を求め新しい推定値 $\mbox{\boldmath$\theta$}^{(t+1)}$ とする

のような計算を行う。このようなEステップと Mステップの繰り返しで得られ るパラメータは尤度を単調に増加させることが知られている。

平均 $\mbox{\boldmath$\mu$}_j$、共分散行列 $\Sigma_j = \sigma_j^2 I$ の正規分布の混 合分布の場合には、 $Q(\mbox{\boldmath$\theta$}\vert\mbox{\boldmath$\theta$}^{(t)})$ を最大とするパラ メータは陽に求まり、EMアルゴリズムの繰り返し計算は、

$$\hat{\omega}_j^{(t+1)} = \frac{1}{N} \sum_{n=1}^N P(j\vert\mbox{\boldmath$x$}_n,\mbox{\boldmath$\theta$}^{(t)})$$ (56)

$$\hat{\mbox{\boldmath$\mu$}}_j^{(t+1)} = \frac{\sum_{n=1}^N P(j\vert\mbox{\boldmath$x$}_n,\mbox{\boldmath$... ..._n}{\sum_{n=1}^N P(j\vert\mbox{\boldmath$x$}_n,\mbox{\boldmath$\theta$}^{(t)})}$$ (57)

$$\hat{\sigma}_j^{2 \ (t+1)} = \frac{1}{d} \frac{\sum_{n=1}^N P(j\vert\mbox{\boldmath$x$}_n,\mbo... ...^2}{\sum_{n=1}^N P(j\vert\mbox{\boldmath$x$}_n,\mbox{\boldmath$\theta$}^{(t)})}$$ (58)

のようになる。これは、先に導出した式(52)と全く同じであり、 各要素への帰属度を表す事後確率の現時点での推定値 $P(j\vert\mbox{\boldmath$x$}_n,\mbox{\boldmath$\theta$}^{(t)})$ を重みとして、パラメータを更新するこ とを繰り返せば良いことになる。

このような EM アルゴリズムは各繰り返しのステップで尤度を単調に増加させ ることから、他の同様な反復アルゴリズムに比べより数値的に安定な挙動を示 すことが知られている。また、逆行列の計算が必要なく、Newton 法等の非線 形最適化手法に比べて簡単である。しかも、多くの実例では他の手法に比べて 良い解に収束することが知られており、繰り返しの初期の段階では Newton 法 と同定度に速い。ただし、解の近くでは収束が遅くなるので、注意が必要であ る。また、大域的な収束は保証されていないので、初期値の選び方を工夫しな ければならない場合もある。