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

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

PRML 9.4 The EM Algorithm in General の証明

目的

Latent variable \mathbf Z を持つ確率分布 p(\mathbf X,\mathbf Z \mid \mathbf \theta) について、

 \ln p(\mathbf X \mid \mathbf \theta) = \ln \sum_{\mathbf Z}p(\mathbf X,\mathbf Z \mid \mathbf \theta)

を極大にする  \mathbf \theta を求めること。

説明

 p(\mathbf X \mid \mathbf \theta) = \frac{p(\mathbf X, \mathbf Z \mid \mathbf \theta)}{p(\mathbf Z \mid \mathbf X, \mathbf \theta)} より、

 \ln p(\mathbf X \mid \mathbf \theta) = \ln p(\mathbf X, \mathbf Z \mid \mathbf \theta) - \ln p(\mathbf Z \mid \mathbf X, \mathbf \theta)

任意の確率分布 q(\mathbf Z) を両辺に掛けて、{\mathbf Z} の和をとると下記が証明される。

 \ln p(\mathbf X \mid \mathbf \theta) = \mathscr L (q,\mathbf \theta) + {\rm KL}(q \,||\, p) ―― (1)

ここに、

 \mathscr L (q,\mathbf \theta) = \sum_{\mathbf Z}q(\mathbf Z)\ln\frac{p(\mathbf X, \mathbf Z \mid \mathbf \theta)}{q(\mathbf Z)}

 {\rm KL}(q \,||\, p) = - \sum_{\mathbf Z}q(\mathbf Z)\ln\frac{p(\mathbf Z \mid \mathbf X, \mathbf \theta)}{q(\mathbf Z)}

ここで、{\rm KL}(q \,||\, p) は、Kullback-Leibler divergence なので、{\rm KL}(q \,||\, p) \ge 0、かつ、

 q(\mathbf Z) =  p(\mathbf Z \mid \mathbf X, \mathbf \theta)(すなわち、q(\mathbf Z)\mathbf Z の事後分布に一致する)の時に、{\rm KL}(q \,||\, p) = 0 となる。

そこで、ある固定した \mathbf \theta = \mathbf \theta_{\rm old} に対して、

  q(\mathbf Z) =  p(\mathbf Z \mid \mathbf X, \mathbf \theta_{\rm old})

を計算しておき、この  q(\mathbf Z) の下で (1) を使って、\ln p(\mathbf X \mid \mathbf \theta_{\rm old})\ln p(\mathbf X \mid \mathbf \theta_{\rm new}) を比較する。

まず、

 \ln p(\mathbf X \mid \mathbf \theta_{\rm old}) = \mathscr L (q,\mathbf \theta_{\rm old})

 =\sum_{\mathbf Z} q(\mathbf Z)\ln p(\mathbf X, \mathbf Z \mid \mathbf \theta_{\rm old}) - \sum_{\mathbf Z} q(\mathbf Z)\ln q(\mathbf Z)

 =Q(\mathbf\theta_{\rm old},\mathbf\theta_{\rm old}) - \sum_{\mathbf Z} q(\mathbf Z)\ln q(\mathbf Z)

同じく、

 \ln p(\mathbf X \mid \mathbf \theta_{\rm new}) = \mathscr L (q,\mathbf \theta_{\rm new}) + {\rm KL}(q \,||\, p)

 =\sum_{\mathbf Z} q(\mathbf Z)\ln p(\mathbf X, \mathbf Z \mid \mathbf \theta_{\rm new})- \sum_{\mathbf Z} q(\mathbf Z)\ln q(\mathbf Z)+ {\rm KL}(q \,||\, p)

 =Q(\mathbf\theta_{\rm new},\mathbf\theta_{\rm old}) - \sum_{\mathbf Z} q(\mathbf Z)\ln q(\mathbf Z) + {\rm KL}(q \,||\, p)

ここに、

 Q(\mathbf\theta,\mathbf\theta_{\rm old}) := \sum_{\mathbf Z}q(\mathbf Z)\ln p(\mathbf X, \mathbf Z \mid \mathbf \theta)

従って、{\rm KL}(q \,||\, p) \ge 0 に注意すると、次の関係が得られる。

 Q(\mathbf\theta_{\rm new},\mathbf\theta_{\rm old}) \ge Q(\mathbf\theta_{\rm old},\mathbf\theta_{\rm old})\,\,\Rightarrow\,\,\ln p(\mathbf X \mid \mathbf \theta_{\rm new}) \ge\ln p(\mathbf X \mid \mathbf \theta_{\rm old})

EM Algorithm

以上をまとめると、

  q(\mathbf Z) =  p(\mathbf Z \mid \mathbf X, \mathbf \theta_{\rm old})

の下に、

 Q(\mathbf \theta,\mathbf\theta_{\rm old}) = \sum_{\mathbf Z}q(\mathbf Z)\ln p(\mathbf X, \mathbf Z \mid \mathbf \theta)

を最大化する \mathbf \theta = \mathbf \theta_{\rm new} を求めることで、

 \ln p(\mathbf X \mid \mathbf \theta_{\rm new}) \ge\ln p(\mathbf X \mid \mathbf \theta_{\rm old})

が成立する。そこで、\mathbf \theta_{\rm new} を新たに \mathbf \theta_{\rm old} として上記の計算を繰り返すことで、\ln p(\mathbf X \mid \mathbf \theta) を極大にする \mathbf\theta が得られる。