これなら分かるEMアルゴリズム③

さて，EMアルゴリズムの最終回．今回は第1回で扱った混合分布モデルの最尤推定と，第2回で扱ったEMアルゴリズムの一般系のつなぎについて書いていきたいと思っている．と言いつつも，実はほとんどの要点は今までの記事に散りばめられている．なので今回はそのまとめの回と考えていただきたい．なお，前回，前々回の記事をご覧になっていない読者の方は以下の記事を参考にしてくださいませ．

niltatsu.hatenablog.com

混合分布モデルの最尤推定とEMアルゴリズム一般形の関係
- E-Step
- M-Step
まとめ

混合分布モデルの最尤推定とEMアルゴリズム一般形の関係

まず混合分布モデルの最尤推定の問題では，以下の最適化問題を解くことがゴールだった: $$ \max_{ \bf{1}^\top \bm{\pi} = 1} \sum_{i = 1}^n \log p(\bm{x}_i | \Theta) = \max_{ \bf{1}^\top \bm{\pi} = 1} \sum_{i = 1}^n \log \left( \sum_{k=1} ^K \pi_k p(\bm{x}_i | \bm{\theta}_k) \right). \tag{1} $$ EMアルゴリズムの一般形では，上記のような最尤推定が解けない場合を想定し，潜在変数$\bm{Z}$を導入した．では，混合分布モデルの場合はどのような潜在変数を導入すれば良いのだろうか．

そこで，以下を満たすような潜在変数$Z_i$を導入する．ただし，$Z_i$は$1, 2, \ldots, K$のうちのいずれかの値をとるとする．気持ちとしては...

混合分布モデルをモデリングするとき，各々のデータがどのクラスタ由来であるかを明示したい．
しかし，現状のモデルの仕方だと，どのデータがどのクラスタ由来なのかは不明である．=> これが潜在変数になる！！！
$Z_i = k$は，「データ$i$は，クラスタ$k$から由来する」ことを意味指す．

「各データがどのクラスタ由来なのか」という情報が隠れて潜んでいるから，これが潜在変数になるというわけだ．ふむふむ．

さて，導入した潜在変数についての確率モデルは以下のようになる(突然なんでこんな式出てくるの？と思う人もいると思うが，上で書いた潜在変数の「気持ち」をしっかり汲んであげれば以下の解釈もすんなり受け入れられるだろう):

事前分布: $p(Z_i = k) = \pi_k$
$Z_i$のもとでの$\bm{x}_i$の分布: $p(\bm{x}_i|Z_i = k, \Theta) = p(\bm{x}_i | \bm{\theta}_k)$
$Z_i$と$\bm{x}_i$の同時分布: $p(\bm{x}_i, Z_i = k | \Theta) = p(\bm{x}_i|Z_i = k, \Theta) p(Z_i = k)$
$Z_i$の事後分布: $p(Z_i = k|\bm{x}_i, \Theta) = \dfrac{p(\bm{x}_i, Z_i = k | \Theta)}{\sum_{l=1}^K p(\bm{x}_i, Z_i = l | \Theta)}$

事後分布の計算はただのベイズの定理であることに注意！なお，第1回の記事でこれが分類問題の場合に$p(y=k|\bm{x})$的な説明をわざと入れたのは，実はこの気持ちを知って欲しいからである． 3回の記事全てを読んでくださった読者はこの気持ちをきっと汲んでくれたはずw

E-Step

道具は揃ったので，以下では実際にEMアルゴリズムの一般形をもとに，混合分布モデルの最尤推定アルゴリズムを再構築してみよう．まずはE-Step． E-Stepでは，$\Theta = \Theta'$に固定し，$q(Z_i = k) = p(Z_i = k|\bm{x}_i, \Theta')$を計算すれば良い．これは上の考察から実はもう答えは出ている．ここでは，混合正規分布モデルの場合における計算を下にのせる: $$ \begin{aligned} q(Z_i = k) = p(Z_i = k|\bm{x}_i, \Theta') &= \dfrac{p(\bm{x}_i, Z_i = k | \Theta')}{\sum_{l=1}^K p(\bm{x}_i, Z_i = l | \Theta')} \\ &= \dfrac{p(Z_i = k) p(\bm{x}_i | Z_i = k, \Theta')}{\sum_{l=1}^K p(Z_i = l) p(\bm{x}_i | Z_i = l, \Theta')} \\ &= \dfrac{\pi_k' \mathcal{N}(\bm{x}_i|\bm{\mu}_k', \varSigma_k')}{\sum_{l=1}^K \pi_l' \mathcal{N}(\bm{x}_i|\bm{\mu}_l', \varSigma_l')}. \end{aligned} $$ さて，第1回の記事を真面目に読んでいただいた方はここで気づくかもしれない．そう，ここの$q(Z_i = k)$だが，これは実は第1回の記事で導入した$q_k^{(i)}$に対応しているのである．

M-Step

次にM-Stepについてだが，これは以下の最適化問題を解けば良いのであった: $$ \begin{aligned} \theta' = \operatorname{argmax}_{\theta} Q(\theta, \theta') = \operatorname{argmax}_{\theta} \sum_{\bm{Z}} p(\bm{Z}|\bm{X}, \theta') \log p(\bm{X}, \bm{Z}|\theta). \tag{2} \end{aligned} $$ 混合正規分布の場合，この最適化問題の目的関数は以下のようになる: $$ Q(\theta, \theta') = \sum_{i=1}^n \sum_{k=1}^K q(Z_i = k) \log \Big( \pi_k \mathcal{N}(\bm{x}_i|\bm{\mu}_k, \varSigma_k) \Big). $$ さて，この式と第1回の記事の(4)式を比べてみて欲しい．いま，$q_k^{(i)}$が固定されていることに注意すると，この両者は全く同じ最適化問題を解いていることが分かる．ゆえに，第1回の記事同様，ラグランジュ関数を作って微分して，最適性条件を調べれば(2)の最適化問題は解けるということになる．これで，M-Stepにおける対応関係も確認できた．

まとめ

さて，最後に一般版EMアルゴリズムと，混合正規分布モデルにおけるEMアルゴリズムのまとめを以下に記しておく．

	一般版	混合正規分布モデル版
初期化	$\theta'$を初期化	$\pi_k, \bm{\mu}_k, \varSigma_k$の初期化
E-Step	$q(\bm{Z}) = p(\bm{Z} \| \bm{X}, \theta')$を計算	$q(Z_i = k) = \dfrac{\pi_k' \mathcal{N}(\bm{x}_i\|\bm{\mu}_k', \varSigma_k')}{\sum_{l=1}^K \pi_l' \mathcal{N}(\bm{x}_i\|\bm{\mu}_l', \varSigma_l')}$
M-Step	$\theta' = \operatorname{argmax}_{\theta} Q(\theta, \theta')$を計算	$\pi_k', \bm{\mu}_k', \varSigma_k'$の更新(第1回の記事参照)