EMアルゴリズム簡単まとめ

EMアルゴリズムとは何か、またその全体の流れについて簡単にまとめています。

目次

1.EMアルゴリズムとは
2.EMアルゴリズムの全体像
3.使用例

1.EMアルゴリズムとは

EMアルゴリズム(expectation–maximization algorithm)は「隠れ変数$\boldsymbol{Z}$がある場合に尤度関数$p(\boldsymbol{X}$| $\theta$ )を$\theta$について最大化する(最尤推定値$\theta$を求める)手法の1つ」で、観測不可能な隠れ変数$\boldsymbol{Z}$の事後確率がパラメータ$\theta$に依存する場合に用いられます。
$\boldsymbol{X}$：観測データの集合
$\theta$：パラメータ
$\boldsymbol{Z}$：隠れ変数の集合
EMアルゴリズムはEステップとMステップを対数尤度の変化が極めて小さくなるまで繰り返すことで、パラメータ$\theta$の最尤推定値を得ます。

2.EMアルゴリズムの全体像

EMアルゴリズムでは以下の流れで実施します。

1. パラメータ$\theta$の初期化
   $\theta^{old}$を初期値を選択します

2. Eステップ
   隠れ変数$\boldsymbol{Z}$の事後確率$p$($\boldsymbol{Z}$|$\boldsymbol{X}$, $\theta^{old}$)を計算します

3. Mステップ
   次式で与えられる$\theta^{new}$を計算します

\theta^{new}=arg max_{\theta} Q(\theta ,\theta^{old})

ただし、

Q(\theta ,\theta^{old})=\sum_{\boldsymbol{Z}}p(\boldsymbol{Z}|\boldsymbol{X}, \theta^{old})ln p(\boldsymbol{X}, \boldsymbol{Z}|\theta)

4.収束判定
収束条件(例えば、隠れ変数$\boldsymbol{Z}$の事後確率$p$($\boldsymbol{Z}$|$\boldsymbol{X}$, $\theta^{new}$) - $p$($\boldsymbol{Z}$|$\boldsymbol{X}$, $\theta^{old}$)$<10^{-5}$)を満たしていない場合は2.Eステップに戻る

3.使用例

観測不可能な隠れ変数$\boldsymbol{Z}$が存在する場合など、最尤推定値を直接求めることができない場合に使用します。
例えば、混合正規分布モデルでクラスタリングを行う場合、尤度$p$($\boldsymbol{X}$, $\boldsymbol{Z}$|$\theta$)を最大にするパラメータを求める際、隠れ変数$\boldsymbol{Z}$があるため、最尤推定値を直接求めることができません。

参考

平井有三(2016)「はじめてのパターン認識」森北出版

混合ガウスモデルとEMアルゴリスム
https://www.slideshare.net/TakayukiYagi1/em-66114496

混合モデルとEMアルゴリズム(PRML第9章）
https://www.slideshare.net/takao-y/20131113-em