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$ が得られる。