## 定義 EMアルゴリズム(EM algorithm, Dempster et al., 1977)は、直接最大化が難しい尤度関数を、観測されていない潜在変数(latent variable)でデータを補う(data augmentation)ことで反復的に最大化する一般的な最尤推定手続きである。観測データを$Z$、潜在(欠測)データを$Z_m$、完全データを$T=(Z,Z_m)$とし、完全データ対数尤度を$\ell_0(\theta;T)$とすると、Eステップとmステップを収束まで交互に繰り返す。 - **Eステップ**: 現在の推定値$\hat\theta^{(j)}$のもとで完全データ対数尤度の条件付き期待値$Q(\theta',\hat\theta^{(j)})=E(\ell_0(\theta';T)\mid Z,\hat\theta^{(j)})$を、ダミー引数$\theta'$の関数として計算する。 - **Mステップ**: $Q(\theta',\hat\theta^{(j)})$を$\theta'$について最大化し、新しい推定値$\hat\theta^{(j+1)}$を得る。 (Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.5.2, 式8.43) ## 2成分ガウス混合モデルでの具体化 $Y=(1-\Delta)Y_1+\Delta Y_2$、$Y_1\sim N(\mu_1,\sigma_1^2)$、$Y_2\sim N(\mu_2,\sigma_2^2)$、$\Delta\in\{0,1\}$を潜在変数とする2成分混合モデルでは、対数尤度$\ell(\theta;Z)=\sum_i\log[(1-\pi)\phi_{\theta_1}(y_i)+\pi\phi_{\theta_2}(y_i)]$の直接最大化は対数の中に和があるため数値的に困難である。$\Delta_i$が既知であれば最大化は容易(各成分の標本平均・分散になる)なので、未知の$\Delta_i$をその条件付き期待値である**責任度(responsibility)** $\gamma_i(\theta) = E(\Delta_i\mid\theta,Z) = \Pr(\Delta_i=1\mid\theta,Z)$ で置き換える。Eステップでは各観測を両モデルへ「ソフトに」割り当てる責任度を計算し、Mステップでは責任度で重み付けた平均・分散として$\mu_1,\sigma_1^2,\mu_2,\sigma_2^2,\pi$を更新する。尤度の真の最大化点は、あるデータ点に無限大の尖度を置く縮退解($\hat\sigma_k^2=0$)にあり無限大の尤度を持つが有用でないため、実際には$\hat\sigma_1^2,\hat\sigma_2^2>0$の良い局所最大値を求める必要があり、複数の局所最大値が存在しうるため複数の初期値で試し最良の結果を採用する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.5.1, 式8.36-8.42) ## 単調収束性と一般化EM(GEM) $\ell(\theta';Z)=Q(\theta',\theta)-R(\theta',\theta)$と分解できる(ここで$R(\theta^*,\theta)=E[\ell_1(\theta^*;Z_m\mid Z)\mid Z,\theta]$)。ジェンセンの不等式により$R(\theta^*,\theta)$は$\theta^*=\theta$のとき($\theta$を固定して)最大化されるため、$Q(\theta',\theta)$を最大化する$\theta'$を選べば $\ell(\theta';Z) - \ell(\theta;Z) = [Q(\theta',\theta)-Q(\theta,\theta)] - [R(\theta',\theta)-R(\theta,\theta)] \ge 0$ が成り立ち、**EMの反復は観測データ対数尤度を単調に減少させない**ことが証明される。この議論から、Mステップで完全な最大化を行う必要はなく、$Q(\theta^{(j+1)},\theta^{(j)}) > Q(\theta^{(j)},\theta^{(j)})$を満たす(=$Q$を増加させる)だけでよいことがわかる。この一般化を**一般化EM(GEM: generalized EM)**と呼ぶ。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.5.2, 式8.44-8.47) ## 同時最大化(maximization–maximization)としての見方 潜在データ$Z_m$上の任意の分布$\tilde P(Z_m)$とパラメータ$\theta'$の関数 $F(\theta',\tilde P) = E_{\tilde P}[\ell_0(\theta';T)] - E_{\tilde P}[\log\tilde P(Z_m)]$ を考えると、$\tilde P(Z_m)=\Pr(Z_m\mid Z,\theta')$のときの$F$の値は観測データ対数尤度に一致する。EMは、$F$を$\theta'$と$\tilde P(Z_m)$について交互に最大化する同時最大化手続きとして再解釈できる。**Eステップは固定した$\theta'$のもとで$\tilde P(Z_m)$について$F$を最大化すること($\tilde P(Z_m)=\Pr(Z_m\mid Z,\theta')$を与える)に、Mステップは固定した$\tilde P$のもとで$\theta'$について$F$を最大化することにそれぞれ対応する**。$F$と観測データ対数尤度は$\tilde P(Z_m)=\Pr(Z_m\mid Z,\theta')$のとき一致するため、前者の最大化は後者の最大化を達成する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.5.3, 式8.48-8.49) ## ギブスサンプリングとの関係 指数型分布族モデルでは、事後分布からのギブスサンプリング([[ベイズ推定]]の計算手段の一つ)とEMアルゴリズムの間に密接な対応がある。EM手続きの潜在データ$Z_m$をギブスサンプラーのもう1つのパラメータとみなすと、2成分ガウス混合モデルのギブスサンプラーの各ステップは、EMのEステップ・Mステップにそれぞれ構造的に対応する。ただし、**責任度$\gamma_i$を計算する(最大化する)代わりに潜在データ$\Delta_i$を条件付き分布$\Pr(\Delta_i\mid\theta,Z)$から抽出し、事後分布のモード(最大化点)を計算する代わりに条件付き分布$\Pr(\mu_1,\mu_2\mid\Delta,Z)$から抽出する**点が異なる。すなわちEMが「最大化する」操作を、ギブスサンプリングは「サンプリングする」操作に置き換える。事後分布に不適切な(improper)事前分布を用いると、混合比率がすべて1つの成分に偏る縮退した事後分布に陥りうる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.6) ## 横断的知見 - **第13章は、第8章が数式で定式化した「責任度によるソフトな割当」を、K-meansとの直接対比を通じてプロトタイプ法の文脈に位置づけ直す**: 第8章 §8.5.1は2成分ガウス混合モデルのEステップで、各観測$i$を両モデルへソフトに割り当てる責任度$\gamma_i(\theta)=\Pr(\Delta_i=1\mid\theta,Z)$を導入する。[[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.2.3は同じ2ステップの反復を、クラスタリング手法としてのK-meansと明示的に並べて示す: K-meansのEステップに相当する割当ステップでは各観測が単一クラスタへ重み1・他クラスタへ重み0という**ハードな**割当を受けるのに対し、ガウス混合のEステップでは責任度によって複数クラスタへ**ソフトに**按分される。この対比から、ガウス混合モデルは「K-meansの確率的一般化」あるいは「K-meansはガウス混合の共分散を$\sigma\to0$へ縮退させた極限」として統一的に理解できる(ESL Exercise 13.1もこの極限関係を明示的に問う)。さらに図13.2のキャプションは、混合モデルのEMを**K-meansの解を初期値として**開始したことを述べており、本ページの未解決の問い(k-meansによる初期値選択)に対する具体的な実装例を与える。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.5.1, [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]] §13.2.3) - **MML第11章は、本ページが未解決の問いとして挙げていた「尤度が非有界になる縮退解はEMアルゴリズム自体でどう現れるか」に直接答える**: ESL第8章はギブスサンプリングにおける不適切な(improper)事前分布が縮退した事後分布を生む問題を指摘するのみで、事前分布を持たない最尤推定(EM自体)での対応する現象は本ページの未解決の問いとして残されていた。[[@2020__Cambridge__Mathematics for Machine Learning - Chapter 11 Density Estimation with Gaussian Mixture Models|MML第11章]] §11.5は、混合ガウスモデルの最尤推定において、ある成分の平均が1つのデータ点に一致し共分散が0に収縮すると尤度が無限大に発散する縮退解を明示する。これはギブスサンプリング(ベイズ的)側の「不適切な事前分布による退化」と対をなす、最尤推定(頻度主義的)側の退化現象であり、EMアルゴリズムが確率的な事前分布の有無によらずいずれの枠組みでも縮退解の危険を持つことを示している。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.6, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 11 Density Estimation with Gaussian Mixture Models]] §11.5) - **MML第11章とESL第8章は、導出の順序が逆(具体→一般 vs 一般→具体)でありながら同一のQ関数に収束する**: MMLはまず責任度$r_{nk}=\pi_k\mathcal N(x_n\mid\mu_k,\Sigma_k)/\sum_j\pi_j\mathcal N(x_n\mid\mu_j,\Sigma_j)$(ESLの$\gamma_i(\theta)$に対応する同一の量)を対数尤度の勾配計算から具体的に導入し(§11.2.1)、次に§11.4.3で同じ量をベイズの定理による事後確率$p(z_k=1\mid x)$として再導出し、最後に§11.4.5でESLの$Q(\theta',\theta^{(j)})=E(\ell_0(\theta';T)\mid Z,\theta^{(j)})$と同型の期待対数尤度$Q(\theta\mid\theta^{(t)})=E_{z\mid x,\theta^{(t)}}[\log p(x,z\mid\theta)]$に到達する(具体→一般の順)。ESLは逆に、Q関数を§8.5.2で最初から一般形として導入し、2成分ガウス混合モデルはその具体化として§8.5.1で示される(一般→具体の順)。導出の順序が逆の2つの教科書が同一のQ関数に収束すること自体が、EMアルゴリズムが特定の応用に依存しない普遍的構造を持つことの傍証であり、さらに両ソースが独立にK-means法とのハード/ソフト割当対比を行っている(ESL第13章§13.2.3、MML第11章§11.5)ことも、この類推が教科書をまたいで再現される安定した理解の枠組みであることを裏付ける。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.5.1-§8.5.2, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 11 Density Estimation with Gaussian Mixture Models]] §11.2.1, §11.4.3, §11.4.5, §11.5) ## 未解決の問い - EMアルゴリズムの収束速度(反復回数と対数尤度の増加量の関係)は、潜在変数の「情報量の割合」にどう依存するか。ESL第8章・MML第11章はいずれも単調収束性のみを示し、収束速度の理論的評価は扱っていない。 - 第13章はK-means解によるEM初期化の一例を示すが、この初期化が複数の局所最大値のうちどの程度良いものへ収束を導くかは体系的に検証されていない。K-means自体も初期値依存の局所最適化であるため、「K-meansで初期化したEM」の再現性・安定性は未検証の問いとして残る。 - ESLはMステップで完全な最大化を要求しない一般化EM(GEM: $Q(\theta^{(j+1)},\theta^{(j)})>Q(\theta^{(j)},\theta^{(j)})$を満たせばよい)を導入するが、MML第11章のGMM向けEM(§11.3, §11.4.5)はMステップで常に3つの更新式(11.20, 11.30, 11.42)による完全な最大化を行う具体例のみを示し、GEMに相当する「部分的な改善で妥協する」バリエーションには触れない。GMMのM-stepを完全最大化しない場合(例えば1回の勾配ステップのみ)でも収束するかは、MML側のソースからは確認できない。 ## 関連 - source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 13 Prototype Methods and Nearest-Neighbors]](ガウス混合をK-meansのソフトな一般化として位置づける) / [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 11 Density Estimation with Gaussian Mixture Models]](GMMへのEMの具体的導出と、潜在変数モデルからの原理的な再導出) - concept: [[ベイズ推定]](ギブスサンプリングによる事後サンプリング) / [[ブートストラップ法]](同章内での計算的類似手法) / [[クラスタリング]](K-means・混合モデルの一般的な位置づけ) / [[最近傍法]](プロトタイプ法としてのガウス混合) / [[混合ガウスモデル]](本アルゴリズムが解く対象モデル) / [[ガウス分布の閉性]](GMMがEMを必要とする根本理由である非閉性) ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 8, §8.5-§8.6; Chapter 13, §13.2.3. - Deisenroth, Faisal, Ong, *Mathematics for Machine Learning*, Cambridge University Press, 2020, Chapter 11, §11.2-§11.5.