PRML下巻_9章 EMアルゴリズム 読解メモ #9
#8では8章のグラフィカルモデルについてまとめました。
#9では9章の読解メモをまとめていければと思います。（7~8割の理解を目標においた読解にあたってのメモなので、要旨を掴みたい方向けです）
9章ではEMアルゴリズムに関して取り扱われています。
以下目次になります。
1. 9章の内容に関して概要
2. 詳細
2.1 K-meansクラスタリング(9.1)
2.2 混合ガウス分布(9.2)
2.3 EMアルゴリズムのもう一つの解釈(9.3)
2.4 一般のEMアルゴリズム(9.4)
3. まとめ＆所感
1. 9章の内容に関して概要
9章では2.3.9で論じられた混合ガウス分布において潜在変数の導入によって複雑な分布をより単純な分布から構成するにあたって実際に変数の値を求める手法として、EM(expectation-maximization)アルゴリズムについてまとめられています。
また、K-meansを混合モデルに包含して議論することでアルゴリズムの全体像を掴みやすくしてくれています。
EMアルゴリズムはパラメータの決定において最尤推定を行うにあたって近似的な解を求める手法の一つであり、10章の変分推論法、11章のサンプリング、4章で言及のあったニュートンラフソン法、5章で言及のあった勾配法などと同様の目的で用いられます。
2. 詳細
9.1では混合モデルなどについて取り扱うにあたっての準備として、データ点集合のクラスタリング問題に関して、K-meansアルゴリズムと呼ばれる非確率的なアプローチについて論じられています。9.2では潜在変数を用いた混合分布の解釈についての導入や大雑把なEMアルゴリズムの説明を行っています。9.3ではEMアルゴリズムのより詳細な取り扱いを行い、K-meansが混合ガウス分布におけるEMアルゴリズムの非確率的表現として解釈できることについてまとめられています。9.4ではEMアルゴリズムの一般化についてまとめられています。
2.1 K-meansクラスタリング(9.1)
9.1ではK-meansクラスタリングについてまとめられています。まず最適化を行う対象の目的関数の定義からですが、(9.1)式でまとめられています。この目的関数のJは歪み尺度(distortion measure)とも呼ばれているそうです。式の意味の解釈としては、rがクラスタへのサンプル割り当てを表しておりクラスタに割り当てられている時にrは1になりそれ以外の時は0であることと、二乗の中身のxは各サンプルμは各クラスタの中心を表していることに注意すれば意味はわかると思います。
ここでポイントなのが目的がJを最小にするrとμを求めることです。これを解くにあたってK-meansアルゴリズムがあり、μの初期値を決め、rについて最適化し(Eステップ)、最適化したrについてμをまた求め(Mステップ)これを繰り返していく手法です。9.3節でこれがEMアルゴリズムの極限として表現できるので、EステップとMステップという言葉で諸々が説明されています。9.1.1では画像圧縮の例をもとに具体的に説明されています。図9.3のように画像をいくつかの輝度のRGB値だけで表すにあたってK-means法が用いられています。
K-means自体はさほど難しい概念ではないので、本の記述が難しければ他の入門書などで先に確認する方が良いと思います。
k平均法 - Wikipedia
上記のWikipediaで十分だと思いますが、視覚的な方が分かりやすければYoutubeで動画を検索するのもありだと思います。
2.2 混合ガウス分布(9.2)
9.2では離散的な潜在変数(latent variable)を用いて混合ガウス分布(Mixtures of Gaussians)の定式化を行っています。9.2.1では9.1で言及した歪み尺度と同様な目的関数として、(9.14)式の対数尤度関数が定められています。lnの中身は(9.7)式で表現されている混合ガウス分布の式です。(9.7)式はガウス分布の線形結合で混合ガウス分布が表せることについて示唆しています。
9.2.2では(9.14)式を用いた最適化を行うにあたってEMアルゴリズムを用いており、P.154~P.155の「混合ガウス分布のためのEMアルゴリズム」に計算の手順がまとめられています。(9.23)式のEステップの計算においては(9.13)式の負担率(responsibility)を用いています。この負担率の解釈としては、混合要素kがxの観測（実際に観測したデータ）を負担する割合とされています。(9.24)〜(9.27)式のMステップの計算に置いては、Eステップで定めた負担率を使って、平均や分散などのパラメータ値を再計算しています。EとMのステップを何度か計算した上で、(9.28)式を用いて対数尤度を計算し、収束性を確認し値によって計算を終了するというのがEMアルゴリズムの一連の流れです。
2.3 EMアルゴリズムのもう一つの解釈(9.3)
9.1ではK-means、9.2では混合ガウス分布におけるEMアルゴリズムを用いたパラメータの推定を行っていますが、9.3では9.1のK-meansを9.2のEMアルゴリズムに関連づけた解釈についてまとめられています。
この議論を行うにあたり、導入部の(9.29)〜(9.34)式で抽象的な設定におけるEMアルゴリズムの計算についてまとめられています。
9.3.1では混合ガウス分布について再度確認し、9.3.2では(9.42)式においてεの0に近づく極限を取ることによってK-meansを導出しています。これを解釈することで、K-meansアルゴリズムはデータ点を各クラスタにハードに割り当てることに対し、EMアルゴリズムは事後確率に基づくソフトな割り当てを行うということができるとされています。
9.3.3、9.3.4は一旦飛ばしました。
2.4 一般のEMアルゴリズム(9.4)
9.4ではより一般的にEMアルゴリズムが議論されています。(9.70)式のように対数尤度関数を下界とKLダイバージェンスに分解し、二段階の最適化を図9.14のように行っていくという話の流れになっています。
3. まとめ＆所感
EMアルゴリズムの説明についてここまでクオリティ高く書いてある本はなかなかない（観測範囲だと他に知らない）ので、8章と同様何度も読み返すのが良いのではという印象でした。全体像は十分つかめたと思うので、必要に応じて読み返す形にできればと考えています。
