EM algorithm
EMアルゴリズムに関する勉強には、産総研赤穂氏のページを参考にすることを勧める。
EMアルゴリズムは、E(expecttion)ステップとM(maximization)ステップを反復的に繰り返すことで、パラメータを逐次改良し、観測データが観測される確率がより高いパラメータを推定する。
観測できない隠れ変数\( h \)と観測できる変数 \( v \) との同時分布 \( P(h, v|\theta) \)のパラメータ\( \theta \)を\( v \)から推定するためのEMゴリズムの、t+1回目のステップは次のように定式化される.
Eステップ: 次式で定義されるQ関数を計算する.これは完全データの真の対数尤度\( \log P(h,v|\theta) \) の推定したパラメータに基づく分布\( P(h|v, \theta^{(t)}) \)による期待値である.
\[
Q(\theta | \theta^{(t)}) = \sum_{h} P(h | v,\theta^{(t)}) \log P(v,h| \theta)
\]
Mステップ: \( Q(\theta|\theta^{(t)}) \) を最大化する \( \theta \)を \( \theta^{(t+1)} \) とおく.
\[
\theta^{(t+1)} = {argmax}_\theta \left[ Q(\theta | \theta^{(t)}) \right]
\]
EMアルゴリズムにおける対数尤度の単調増加性の証明
観測データの対数尤度を \( L(\theta) \) と置くと
\[ L(\theta) \equiv \log P(v|\theta) = \log P(v,h |\theta) – \log P(h |v,\theta)
\] となる. 両辺を \( P(h| v, \theta^{(t)}) \) で期待値をとる. \( L(\theta) = \log P(v|\theta) \)は\( h \)によらないので
\[
L(\theta)
= \sum_{h} \left[ \log P(v,h|\theta) – \log P(h |v, \theta) \right] ( P(h| v, \theta^{(t)}) \\
= Q(\theta | \theta^{(t)}) – \sum_{h} \log P(h |v, \theta) ( P(h| v, \theta^{(t)})
\] したがって、\( t+1 \) ステップ目と \( t \) ステップ目の対数尤度の差は、
\[
L(\theta^{(t+1)}) – L(\theta^{(t)})
= \left[ Q(\theta^{(t+1)} | \theta^{(t)}) – Q(\theta^{(t)} | \theta^{(t)}) \right]
+ \sum_h P(h| v, \theta^{(t)}) \frac{\log P(h |v, \theta^{(t)})}{\log P(h |v,\theta^{(t+1)})}
\]
第1項は\( \theta^{(t+1)} \) の定義から非負、第2項は2つの確率分布 \(P(h |v,\theta^{(t)} \)と\(P(h |v,\theta^{(t+1)} \)のKullback Leibler情報量と呼ばれるもので、非負である. したがって、対数尤度\( L(\theta) = \log P(v|\theta) \)は単調増加する.