Real World Annotator

Machine Learning, Statistics, Finance, and Everyday Life.

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

前回は主に混合分布モデルによるEMアルゴリズムについて解説した. 計算は少々大変だが,思考の流れさえ把握できれば,その考え方は難しくないだろう. まだ読んでいない!という方は以下の記事を参照してください:

niltatsu.hatenablog.com

さて,前回はなるべく「潜在変数モデル」や「$Q$関数」などの用語を使用せずに混合分布モデルによるEMアルゴリズムを解説したが,やはりEMアルゴリズムの一般形を理解するには,これらの概念は非常に重要になってくる. そこで今回はこれらの概念,そして一般化したEMアルゴリズムについて解説する.

問題設定・潜在変数モデル

今回は混合分布モデル,さらには特定の分布を仮定しない場合のEMアルゴリズムについて紹介する. まず観測変数を$\bm{X}$とおき,モデルのパラメータを$\theta$とおく. いま,データ$\mathcal{D}$が与えられたとして,$\mathcal{D}$を用いて$p(\bm{X} | \theta)$の最尤推定を行うことを考える. この場合,解きたい最適化問題は以下のようになる: $$ \max_{\theta} \log p(\mathcal{D} | \theta) $$ これが解ければとてもハッピーなのだが,実際にこれが解けない場合を考える(混合分布モデルの場合を思い出して欲しい).

ここで突然だが,潜在変数$\bm{Z}$というものを導入する. 潜在変数とは,直接観測はされないが,モデルの中には実在する変数で,サンプル生成の背後にある状態・因果関係などを記述する際に用いられる. そして,この潜在変数を用いたモデルのことを潜在変数モデルと呼ぶ. 潜在変数モデルでは,$\theta$によって条件つけられた$\bm{X}, \bm{Z}$の同時分布$p(\bm{X}, \bm{Z}|\theta)$を考える. そして実際に観測されるのは$\bm{Z}$によって周辺化された確率分布$p(\bm{X} | \theta)$に従うサンプルであると考える. 式で言えば,以下のようになる: $$ p(\bm{X} | \theta) = \sum_{\bm{Z}} p(\bm{X}, \bm{Z}|\theta). $$ すると,上の最適化問題は以下のように置き換えることが可能になる: $$ \max_{\theta} \log p(\mathcal{D} | \theta) = \max_{\theta} \log \sum_{\bm{Z}} p(\mathcal{D}, \bm{Z}|\theta). $$ ゆえに,右辺の最適化を解くことが今回のゴールとなり,これを実現するアルゴリズムEMアルゴリズムというわけだ. 以下では説明の便宜上,上の最適化問題を $$ \max_{\theta} \log p(\bm{X} | \theta) = \max_{\theta} \log \sum_{\bm{Z}} p(\bm{X}, \bm{Z}|\theta). \tag{1} $$ のように書く.

Jensenの不等式を用いた下界の導出

さて,前回のの記事をご覧になった読者はここで気づくはずだが,最適化問題(1)の右辺が$\log$関数の中に和が入っている形になっており,解くのが大変である. そこで前回同様Jensenの不等式により下界を求め,それを最大化することで間接的に元の対数尤度を最大化することを考える. 前回の記事では$q_k^{(n)}$を導入したが,今回は$q(\bm{Z})$を導入する. ただし,$q$は$\sum_{\bm{Z}} q(\bm{Z}) = 1$を満たすとする. すると,目的関数の下界として以下が求まる: $$ \begin{aligned} \log \sum_{\bm{Z}} p(\bm{X}, \bm{Z}|\theta) &= \log \sum_{\bm{Z}} q(\bm{Z}) \dfrac{p(\bm{X}, \bm{Z}|\theta)}{q(\bm{Z})} \\ &\geq \sum_{\bm{Z}} q(\bm{Z}) \log \dfrac{p(\bm{X}, \bm{Z}|\theta)}{q(\bm{Z})} \eqqcolon \mathcal{L}(q, \theta). \end{aligned} $$ ここで,1行目から2行目の不等式においてJensenの不等式を利用した. $\mathcal{L}(q, \theta)$は変分下限と呼ばれており,対数尤度の下界として理解していただければ良い.

変分下限と対数尤度の関係

上節で,対数尤度$\log p(\bm{X}|\theta)$の変分下限$\mathcal{L}(q, \theta)$を求めた. ここで気になる人は気になるかもしれないが,この両者の差は一体何だろうか? 実際に計算してみよう. $\sum_{\bm{Z}} q(\bm{Z}) = 1$であることに注意すると, $$ \begin{aligned} \log p(\bm{X}|\theta) - \mathcal{L}(q, \theta) &= \log p(\bm{X}|\theta) \sum_{\bm{Z}} q(\bm{Z}) - \sum_{\bm{Z}} q(\bm{Z}) \log \dfrac{p(\bm{X}, \bm{Z}|\theta)}{q(\bm{Z})} \\ &= \sum_{\bm{Z}} q(\bm{Z}) \log p(\bm{X}|\theta) - \sum_{\bm{Z}} q(\bm{Z}) \log \dfrac{p(\bm{Z}|\bm{X}, \theta) p(\bm{X}|\theta)}{q(\bm{Z})} \\ &= -\sum_{\bm{Z}} q(\bm{Z}) \log \dfrac{p(\bm{Z}|\bm{X}, \theta)}{q(\bm{Z})}\\ &= \mathcal{D}_{\mathrm{KL}} \Bigl( q(\bm{Z}) \Big| \Big| p(\bm{Z}|\bm{X}, \theta) \Bigr). \end{aligned} $$ ほうほう,対数尤度と変分下限の差はKLダイバージェンスなのか...! 実はこの後このKLダイバージェンスは大切な役割を果たす.

EMアルゴリズムの概略

さて,ここまでで混合分布モデルではなく,一般のモデルの場合でも使える変分下限を導出した. ここで一度EMアルゴリズムの概略を一回眺めてみよう.

EMアルゴリズム(一般形)

  1. 初期化: $\theta, q$を適当に初期化
  2. While 収束していない do:
    1. E-step: 現在の$\theta$を用いて$q$を計算
    2. M-step: 現在の$q$を用いて$\theta$を計算

前回の記事を読んでいただいた方は混合分布モデルの場合と照らし合わせて考えると分かりやすいかもしれない. このE-Step,M-Stepは一般の場合ではどのようにして計算できるのか,以下でそれを見ていきたいと思う.

E-Stepの計算

前回の記事で書いたが,混合正規分布モデルの場合は$\theta$を固定し,$\mathcal{L}(q, \theta)$の$q$について最大化,つまり「$q$について微分=0」の方程式を解けば良かった. では一般形の場合はどうすれば良いのか. ここで使用するのが変分下限と対数尤度の関係である: $$ \log p(\bm{X}|\theta) = \mathcal{L}(q, \theta) + \mathcal{D}_{\mathrm{KL}} \Bigl( q(\bm{Z}) \Big| \Big| p(\bm{Z}|\bm{X}, \theta) \Bigr). $$ $\theta$を$\theta'$に固定し,上の式とにらめっこして,$\mathcal{L}(q, \theta)$の$q$について最大化について考えると,以下の知見が得られる:

  • $\log p(\bm{X}|\theta')$は$q$によらない関数 = $q$を動かしても左辺は変わらない
  • この場合,「$\mathcal{L}(q, \theta')$の最大化 = $\mathcal{D}_{\mathrm{KL}} \Bigl( q(\bm{Z}) \Big| \Big| p(\bm{Z}|\bm{X}, \theta') \Bigr)$の最小化」
  • KLダイバージェンスの非負性から,$\mathcal{D}_{\mathrm{KL}} \Bigl( q(\bm{Z}) \Big| \Big| p(\bm{Z}|\bm{X}, \theta') \Bigr)$の最小値は$0$で,最小値を達成するときの$q(\bm{Z}) = p(\bm{Z}|\bm{X}, \theta')$

ゆえに,結局$\mathcal{L}(q, \theta')$の$q$について最大化の最適解は$q(\bm{Z}) = p(\bm{Z}|\bm{X}, \theta')$となる. 前回の記事の場合E-Stepの計算をするために微分したりしたが,実は上のようにKLダイバージェンスを使用すればあっさりと解けてしまうのである.

M-Stepの計算

次にE-Stepで得られた$q$を用いて$\theta$について$\mathcal{L}(q, \theta)$を最大化する. まずE-Stepの結果を変分下限に適用すると, $$ \begin{aligned} \mathcal{L}(q, \theta) &= \sum_{\bm{Z}} q(\bm{Z}) \log \dfrac{p(\bm{X}, \bm{Z}|\theta)}{q(\bm{Z})} \\ &= \sum_{\bm{Z}} p(\bm{Z}|\bm{X}, \theta') \log \dfrac{p(\bm{X}, \bm{Z}|\theta)}{p(\bm{Z}|\bm{X}, \theta')} \\ &= \sum_{\bm{Z}} p(\bm{Z}|\bm{X}, \theta') \log p(\bm{X}, \bm{Z}|\theta) - \sum_{\bm{Z}} p(\bm{Z}|\bm{X}, \theta') \log p(\bm{Z}|\bm{X}, \theta') \\ &= Q(\theta, \theta') + \mathrm{const} \end{aligned} $$ となる. 3行目の第2項は$\theta$を含まないので,$\theta$についての最大化に際しては単なる定数である. 一方第1項は$\theta$が含まれるので,$\mathcal{L}(q, \theta)$の最大化は実質この項の最大化に等しい. この第1項は$Q$関数と呼ばれている. ゆえに,M-Stepですべき$\mathcal{L}(q, \theta)$の$\theta$についての最大化は, $$ \operatorname{argmax}_{\theta} Q(\theta, \theta') $$ と等価である.

一般のEMアルゴリズムのまとめ

さて,以上の知見をもとに一般の場合のEMアルゴリズムを再構成すると,以下のようになる:

EMアルゴリズム(一般形)

  1. 初期化: $\theta, q$を適当に初期化
  2. While 収束していない do:
    1. E-step: $q(\bm{Z}) = p(\bm{Z}|\bm{X}, \theta')$を計算
    2. M-step: $\theta' = \operatorname{argmax}_{\theta} Q(\theta, \theta')$を計算

実際にこれを図にすると以下の図のようになる.

f:id:niltatsu:20180731181700p:plain

やっていることとしては,$\log p(\bm{X} |\theta)$の最大値を求めるために,青線や緑線のような変分下限を考え,その下限の最大値を次のステップのパラメータとして使用する. これを繰り返すことで,徐々に$\log p(\bm{X} |\theta)$の最大値に近づけていく,という作戦である. このように上下限を利用することで最適値を達成する点を求めるアルゴリズムはたくさんあり,例えば近接勾配法などがある. 是非これを気に調べてもらえると良い.

まとめ

今回は特定のモデルを仮定せずに,一般の場合のEMアルゴリズムについて紹介した. なるべく分かりやすく紹介したつもりだが,この記事を読んでも初心者にはこの一般版EMアルゴリズムと混合分布モデルEMアルゴリズムの繋がりが見えないかもしれない. (長くなってしまったので)そこで次回はこの2者の関連と,さらには混合分布モデルにおけるスムージングについて紹介する.

niltatsu