一般のEMアルゴリズム - 機械学習基礎理論独習

一般のEMアルゴリズムについて説明します。

導入

全ての観測データの集合を ${\bf X}$ で表します。
全ての潜在変数の集合を ${\bf Z}$ で表します。
全てのモデルパラメータの集合を $\boldsymbol\theta$ で表します。
この時、対数尤度は以下のようになります。

$\begin{eqnarray} \ln p({\bf X}|{\boldsymbol\theta})=\ln\sum_{\bf Z}p({\bf X},{\bf Z}|{\boldsymbol\theta})\tag{1}\\ \end{eqnarray}$

今、 $\ln p({\bf X}|{\boldsymbol\theta})$ の最適化は難しいが、
完全データの対数尤度関数 $\ln p({\bf X},{\bf Z}|{\boldsymbol\theta})$ の最適化可能であるとします。

潜在変数についての分布 $q({\bf Z})$ を導入し、以下のように対数尤度関数を分解します。

$\begin{eqnarray} \ln p({\bf X}|{\boldsymbol\theta})={\mathcal L}(q,{\boldsymbol\theta})+{\rm KL}(q||p)\tag{2}\\ \end{eqnarray}$

対数尤度関数の変形

$\ln p({\bf X}|{\boldsymbol\theta})={\mathcal L}(q,{\boldsymbol\theta})+{\rm KL}(q||p)$ の導出を行います。

$\begin{eqnarray} \ln p({\bf X}|{\boldsymbol\theta})&=&\ln\sum_{\bf Z}p({\bf X},{\bf Z}|{\boldsymbol\theta})\\ &=&\ln\sum_{\bf Z}q({\bf Z})\frac{p({\bf X},{\bf Z}|{\boldsymbol\theta})}{q({\bf Z})}\\ &\geq&\sum_{\bf Z}q({\bf Z})\ln\frac{p({\bf X},{\bf Z}|{\boldsymbol\theta})}{q({\bf Z})}\tag{3}\\ \end{eqnarray}$

$(3)$ ではイェンゼンの不等式 $\ln {\mathbb E}[X]\geq {\mathbb E}[\ln X]$ を用いました。
ここで $\mathcal{L}(q,{\boldsymbol\theta})$ を以下のようにおきます。

$\begin{eqnarray} &&\mathcal{L}(q,{\boldsymbol\theta})=\sum_{\bf Z}q({\bf Z})\ln\frac{p({\bf X},{\bf Z}|{\boldsymbol\theta})}{q({\bf Z})}\tag{4}\\ \end{eqnarray}$

$\ln p({\bf X}|{\boldsymbol\theta})$ と $\mathcal{L}(q,{\boldsymbol\theta})$ の差が ${\rm KL}(q||p)$ になっていることを確認します。

$\begin{eqnarray} \ln p({\bf X}|{\boldsymbol\theta})-\mathcal{L}(q,{\boldsymbol\theta})&=&\ln p({\bf X}|{\boldsymbol\theta})-\sum_{\bf Z}q({\bf Z})\ln\frac{p({\bf X},{\bf Z}|{\boldsymbol\theta})}{q({\bf Z})}\\ &=&\ln p({\bf X}|{\boldsymbol\theta})\sum_{\bf Z}q({\bf Z})-\sum_{\bf Z}q({\bf Z})\ln\frac{p({\bf X},{\bf Z}|{\boldsymbol\theta})}{q({\bf Z})}\\ &=&\sum_{\bf Z}q({\bf Z})\ln p({\bf X}|{\boldsymbol\theta})-\sum_{\bf Z}q({\bf Z})\ln\frac{p({\bf Z}|{\bf X},{\boldsymbol\theta})p({\bf X}|{\boldsymbol\theta})}{q({\bf Z})}\\ &=&\sum_{\bf Z}q({\bf Z})\ln p({\bf X}|{\boldsymbol\theta})-\sum_{\bf Z}q({\bf Z})(\ln p({\bf Z}|{\bf X},{\boldsymbol\theta})+\ln p({\bf X}|{\boldsymbol\theta})-\ln q({\bf Z}))\\ &=&-\sum_{\bf Z}q({\bf Z})\ln \frac{p({\bf Z}|{\bf X},{\boldsymbol\theta})}{q({\bf Z})}\\ &=&{\rm KL}(q({\bf Z})||p({\bf Z}|{\bf X},{\boldsymbol\theta}))\geq0\tag{5}\\ \end{eqnarray}$

図示すると以下のようになります。

f:id:olj611:20210304124818p:plain

Eステップ

$\mathcal{L}(q,{\boldsymbol\theta})$ を $q({\bf Z})$ について最大化します。
${\boldsymbol\theta}$ は固定します。現在の値を ${\boldsymbol\theta}^{old}$ とします。
$\ln p({\bf X}|{\boldsymbol\theta})$ の値は $q$ に依らないので、
$\mathcal{L}(q,{\boldsymbol\theta})$ を最大化するには、 ${\rm KL}(q||p)$ を最小化すればよいことが分かります。
${\rm KL}(q||p)$ は $q=p$ のときに最小値0となるので $q({\bf Z})=p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})$ となります。
この時、 $\mathcal{L}(q,{\boldsymbol\theta}^{old})$ は $\ln p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})$ と等しくなります。

f:id:olj611:20210304131924p:plain

ここで、 $\mathcal{L}(q,{\boldsymbol\theta})$ を変形します。

$\begin{eqnarray} \mathcal{L}(q,{\boldsymbol\theta})&=&\sum_{\bf Z}q({\bf Z})\ln\frac{p({\bf X},{\bf Z}|{\boldsymbol\theta})}{q({\bf Z})}\\ &=&\sum_{\bf Z}p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})\ln p({\bf X},{\bf Z}|{\boldsymbol\theta})-\sum_{\bf Z}p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})\ln q({\bf Z})\\ &=&\sum_{\bf Z}p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})\ln p({\bf X},{\bf Z}|{\boldsymbol\theta})+\mathrm{const.}\\ &=&\mathcal{Q}({\boldsymbol\theta},{\boldsymbol\theta}^{old})+\mathrm{const.}\tag{6}\\ \end{eqnarray}$

この $\mathcal{Q}({\boldsymbol\theta},{\boldsymbol\theta}^{old})$ は完全データの対数尤度関数の ${\bf Z}$ の事後分布に関する期待値になっていることが分かります。
次のMステップでは、この $\mathcal{Q}$ 関数を最大化します。

Mステップ

$\mathcal{Q}({\boldsymbol\theta},{\boldsymbol\theta}^{old})$ を ${\boldsymbol\theta}$ について最大化します。
$q({\bf Z})$ は固定します。
式で表すと以下のようになります。

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} &&{\boldsymbol\theta}^{new}\leftarrow\argmax_{\boldsymbol\theta}\mathcal{Q}({\boldsymbol\theta},{\boldsymbol\theta}^{old})\tag{7}\\ \end{eqnarray}$

この時、 $\mathcal{L}(q,{\boldsymbol\theta}^{new})\geq\mathcal{L}(q,{\boldsymbol\theta}^{old})$ です。
また、 $p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})$ と $p({\bf Z}|{\bf X},{\boldsymbol\theta}^{new})$ は ${\rm KL}(p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})||p({\bf Z}|{\bf X},{\boldsymbol\theta}^{new}))\geq0$ となります。
従って、 $\ln p({\bf X}|{\boldsymbol\theta}^{new})\geq\ln p({\bf X}|{\boldsymbol\theta}^{old})$ です。

f:id:olj611:20210304134159p:plain

まとめ

1.初期化
${\boldsymbol\theta}^{old}$ を初期化します。

2. Eステップ

$p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})$ を計算します。
${\mathcal Q}$ 関数を計算します。

$\begin{eqnarray} \mathcal{Q}({\boldsymbol\theta},{\boldsymbol\theta}^{old})=\sum_{\bf Z}p({\bf Z}|{\bf X},{\boldsymbol\theta}^{old})\ln p({\bf X},{\bf Z}|{\boldsymbol\theta})\tag{8} \end{eqnarray}$

3. Mステップ

${\boldsymbol\theta}$ を更新します。

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} {\boldsymbol\theta}^{new}\leftarrow\argmax_{\boldsymbol\theta}\mathcal{Q}({\boldsymbol\theta},{\boldsymbol\theta}^{old})\tag{9}\\ \end{eqnarray}$

4. 収束確認
$\ln p({\bf X}|{\boldsymbol\theta})$ を計算し、収束しているか調べます。
収束している場合、終了します。
収束していない場合、 ${\boldsymbol\theta}^{old}\leftarrow{\boldsymbol\theta}^{new}$ とし、2に戻ります。