EMアルゴリズム - 画像処理とか機械学習とか

今回は、前回の混合ガウスモデルに引き続き、混合ガウスモデルのパラメータ推定の手法に使えるEMアルゴリズムについて紹介したいと思います。

混合ガウスモデルを例に挙げますので、混合ガウスモデルが分からない方は前回の記事を参照してください。
hiro2o2.hatenablog.jp

なぜ最尤推定で解けないか？

混合ガウスモデルは以下の式で表せました。
$p(x|\theta)=\sum_{j=1}^K \pi_jN(x|\mu_j,\Sigma_j)$
何か近似したい確率密度分布（真の分布）がある際に、混合ガウスモデルを使って近似する場合、最も真の分布に近づくような、パラメータ $\theta$ が分かれば良いです。

このパラメータ $\theta$ の学習に、通常のガウスモデルと同じように最尤推定を用い、対数尤度の最大化のアプローチで解けるでしょうか？

$\hat{\theta}={\rm argmax}\sum_{i=1}^I\log(p(x_i|\theta))\\ ={\rm argmax}\sum_{i=1}^I\log(\sum_{j=1}^K\pi_jN(x_i|\mu_j,\Sigma_j))$

このように、正規分布の和のlogの部分で、微分して0とおく計算が難しくなります。
また、重み $\pi$ を足し合わせて1であるという条件と、共分散行列 $\Sigma_j$ が正定値であるという条件のもと、 $\theta$ を最大にするのは困難です。つまり、この問題は解析的に解けません。

隠れ変数の定義

ここで、 $z\in{1,...K}$ のような変数 $z$ を定義します。この変数 $z$ を以下のように導入します。

$p(x|z,\theta)=N(x|\mu_z,\Sigma_z)$ ・・・(1)
$p(z|\theta)=\pi_z, \sum_{l=1}^K \pi_l=1$ ・・・(2)

ここで、混合ガウスモデル $p(x|\theta)$ は以下のようになります。

$p(x|\theta)=\sum_{j=1}^K p(x,z=j|\theta)\\ = \sum_{j=1}^K p(x|z=j,\theta)p(z=j|\theta)\\ = \sum_{j=1}^K \pi_jN(x|\mu_j,\Sigma_j)$

まず一行目ではxの分布がxとzの同時分布を周辺化した物で表せることを示しており、二行目では、ベイズの定理よりxの分布とzの事前分布に分けられます。そして、(1)(2)式より、zを導入した式が、混合ガウスモデルになる事が分かりました。
f:id:hiro2o2:20160212200737p:plain
上の図を見ると分かるように、隠れ変数zはどの正規分布かを表し、xとzの同時確率というのは、一つの正規分布を表します。また、それらをzについて周辺化することで混合ガウスモデルが得られるという事を表しています。

EMアルゴリズム

やっと本題に入ります。隠れ変数zを含めた対数尤度の式は以下のようになります。

$\hat{\theta}={\rm argmax}\sum_{i=1}^I\log(\int p(x_i,z_i|\theta)dz_i)$

$B[\{q_i(z_i)\},\theta] = \sum_{i=1}^I\int q_i(z_i)\log(\frac{p(x_i,z_i|\theta)}{q_i(z_i)})dz_i \le \sum_{i=1}^I\log(\int p(x_i,z_i|\theta)dz_i)$
Jensenの不等式より、最大化したい尤度よりも常に小さい尤度の下界を $B[\{q_i(z_i)\},\theta]$ として定義し、この下界を大きくすることで尤度の最大化を行おうというのが、EMアルゴリズムです。