読者です 読者をやめる 読者になる 読者になる

画像処理とか機械学習とか

画像処理や機械学習関連の事について気まぐれで書いていきます。歩行者検出関係が多いと思います。ハリネズミもたまに出現します。

EMアルゴリズム

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

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

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

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

{ \displaystyle \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とおく計算が難しくなります。
また、重み{ \displaystyle \pi }を足し合わせて1であるという条件と、共分散行列{ \displaystyle \Sigma_j }が正定値であるという条件のもと、{ \displaystyle \theta }を最大にするのは困難です。つまり、この問題は解析的に解けません。

  • 隠れ変数の定義

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

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

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

{ \displaystyle 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について周辺化することで混合ガウスモデルが得られるという事を表しています。

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

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

{ \displaystyle 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の不等式より、最大化したい尤度よりも常に小さい尤度の下界を{ \displaystyle B[\{q_i(z_i)\},\theta]}として定義し、この下界を大きくすることで尤度の最大化を行おうというのが、EMアルゴリズムです。

{ \displaystyle B[\{q_i(z_i)\},\theta]}を最大化するために、{ \displaystyle \theta}{ \displaystyle q_i(z_i)}を交互に求めて少しずついいものにしていきます。

・Eステップ
{ \displaystyle \theta}を固定して{ \displaystyle q_i(z_i)}を変更し、下界を最大化する

・Mステップ
{ \displaystyle q_i(z_i)}を固定して、下界を最大にする{ \displaystyle \theta}を求める

このようにEステップとMステップを繰り返すことにより、尤度を最大化し、最適なパラメータ{ \displaystyle \theta}を求めます。
f:id:hiro2o2:20160212202753p:plain
EMアルゴリズムの図的なイメージ

ただし、注意して頂きたいのが、最尤推定と同じく局所最適化などの問題を孕んでいる点など、様々な面において最尤推定の悪い部分も引き継いでいます。
しかし、実装の容易さと理解のしやすさから混合ガウスモデルのパラメータ推定によく用いられます。