EM Algorithm

観測変数$X$と、潜在変数$Z$を持つ何かしらの確率モデルの対数尤度$\log p(X|\theta)$を最大化するパラメータ$\theta$を求めたい問題を考える。

このとき、以下の条件が満たされるなら、EMアルゴリズムの登場となる。

• 対数尤度$\log p(X|\theta)$の最大化は難しいが、完全データ対数尤度$\log p(X,Z|\theta)$の最大化は簡単

これだけ言われてもわかりづらいと思うけど、例はあとで見るのでとりあえず今は $\log p(X|\theta)$の計算を$\log p(X,Z|\theta)$の計算に帰着させればOKと思って欲しい。

対数尤度をゴリゴリ変形する。

$\log p(X|\theta) = \log \sum_Z p(X,Z|\theta)$

ここで、任意の確率分布$q(Z)$を導入して、

$= \log \sum_Z q(Z) \frac{p(X,Z|\theta)}{q(Z)}$

イェンセンの不等式を用いると

$\geq \sum_Z q(Z) \log \frac{p(X,Z|\theta)}{q(Z)} \\ = L(q, \theta)$

ここで、$L(q, \theta)$は対数尤度$\log p(X|\theta)$の下限になっている。なので、EMアルゴリズムでは$L(q, \theta)$を最大化する$q$と$\theta$を求めることで対数尤度$\log p(X|\theta)$を最大化する。

$L(q,\theta)$の式を見ると、その中に$\log p(X|\theta)$はなく、$\log p(X,Z|\theta)$しか無いことが分かる。つまり簡単に計算できるようになったわけだ。

で、$L(q,\theta)$を最大化する$q$と$\theta$を求めるんだけど、

• $\theta$を固定して$q$について$L(q,\theta)$を最大化するE-step
• $q$を固定して$\theta$について$L(q,\theta)$を最大化するM-step

を交互に繰り返す。この繰り返しで対数尤度$\log p(X|\theta)$が必ず単調増加していくというのがEMアルゴリズムのポイントなんだけどその証明はいたるところにあるのでここでは省略。

E-step

$\theta$を固定して、$L(q,\theta)$を最大化する$q$を求める。

天下り的だけどまず

$\log(X|\theta) = L(q,\theta) + KL(q||p)$

を示す。ここで$KL(q||p)$は確率分布$p$と確率分布$q$の間のKLダイバージェンスを示す。

以下、$L(q,\theta)$を変形して$L(q,\theta) = -KL(q||p) + \log p(X|\theta)$を示す。

$L(q,\theta) = \sum_Z q(Z) \log \frac{p(X,Z|\theta)}{q(Z)} \\ = \sum_Z q(Z) \log \frac{p(Z|X,\theta)p(X|\theta)}{q(Z)} \\ = \sum_Z q(Z) \log \frac{p(Z|X,\theta)}{q(Z)} - \sum_Z q(Z) \log p(X|\theta) \\ = \sum_Z q(Z) \log \frac{p(Z|X,\theta)}{q(Z)} - \log p(X|\theta) \\ = - \sum_Z q(Z) \log \frac{q(Z)}{p(Z|X,\theta)} - \log p(X|\theta) \\ = -KL(q||p) + \log p(X|\theta)$

以上より示された。

超重要ポイントが一つ。$q(Z)$の選び方について、確率分布であること以外はなんの仮定も置いていない。つまり、$q(Z)$は何を選んでも良い。別の言い方をすると、どんな$q(Z)$を選んでも$\log p(X|\theta)$の値にはなんの影響も与えない。

つまり、$KL(q||p)$を$0$にする$q$を選べば、（$\log p(X|\theta)$は変化しないから）$L(q,\theta)$が最大になることが分かる。

そして、KLダイバージェンスは$q=p$の時に限って$0$になるため、$q(Z) = p(Z|X,\theta)$とすれば$L(q,\theta)$が$q$について最大化されることが分かる。

M-step

$q$を固定して$L(q,\theta)$を最大化する$\theta$を求める。

Mステップでは、前回のEステップの結果、$q(Z) = p(Z|X,\theta')$が与えられていると考える。$\theta$ではなく$\theta'$となっているのは、今回最大化する$\theta$に$p(Z|X,\theta')$は関係ないということを意味している。つまり、$p(Z|X,\theta')$は定数であると考える。

以下、$L(q,\theta)$を変形する

$L(q,\theta) = \sum_Z p(Z|X,\theta') \log \frac{p(X,Z|\theta)}{p(Z|X,\theta')} \\ = \sum_Z p(Z|X,\theta') \log p(X,Z|\theta) - \sum_Z p(Z|X,\theta') \log p(Z|X,\theta')$

第二項は$\theta$に関係ないから

$= \sum_Z p(Z|X,\theta') \log p(X,Z|\theta) + const$

つまり、$L(q,\theta)$を最大化するためには、$\sum_Z p(Z|X,\theta') \log p(X,Z|\theta)$を最大化する$\theta$を求めれば良いことが分かる。これを、Q関数

$Q(\theta, \theta') = \sum_Z p(Z|X,\theta') \log p(X,Z|\theta)$

と言う。

以上より、Mステップでは、$q(Z) = p(Z|X,\theta')$と固定されたうえで、$L(q,\theta)$を最大化する$\theta$を求める。$L(q,\theta)$を最大化するには$Q(\theta,\theta')$を最大化する$\theta$を求めれば良い。

まとめ

• Eステップでは$\theta$を固定して$p(Z|X,\theta)$を計算する
• Mステップでは$q(Z)=p(Z|X,\theta')$と固定して$Q(\theta, \theta')$を最大化する$\theta$を求める。