-
目标
EM算法是為了找到含有隐變量的模型的最大似然解，Z為隐變量
極大似然的對數解如下所示
ln p ( X ∣ θ ) = ln { ∑ Z p ( X , Z ∣ θ ) } (1) \ln p(\mathbf{X} \mid \theta)=\ln \left\{\sum_{Z} p(\mathbf{X}, \mathbf{Z} \mid \theta)\right\} \tag{1} lnp(X∣θ)=ln{Z∑p(X,Z∣θ)}(1)
-
總體流程
我們考慮隐變量在後驗分布 ln p ( Z ∣ X , θ ) \ln p(\mathbf{Z} \mid \mathbf{X}, \mathbf{\theta} ) lnp(Z∣X,θ)下的期望值
在M步最大化E步估計的期望，如果目前對參數的估計為 θ o l d \theta^{old} θold, 那麼經過下一輪的E和M步之後修正過的參數為 θ n e w \theta^{new} θnew
-
E步
用 θ o l d \theta^{old} θold找到隐變量後驗分布 p ( Z ∣ X , θ ) p(\mathbf{Z} \mid \mathbf{X}, \mathbf{\theta} ) p(Z∣X,θ)，然後用該後驗找到完全資料指數似然 p ( X , Z ∣ θ ) p(\mathbf{X}, \mathbf{Z} \mid \theta) p(X,Z∣θ)對于常用參數 θ \theta θ評估的期望，用以下形式表示：
Q ( θ , θ old ) = ∑ Z p ( Z ∣ X , θ old ) ln p ( X , Z ∣ θ ) (2) Q\left(\theta, \theta^{\text {old }}\right)=\sum_{Z} p\left(\mathbf{Z} \mid \mathbf{X}, \theta^{\text {old }}\right) \ln p(\mathbf{X}, \mathbf{Z} \mid \theta) \tag{2} Q(θ,θold )=Z∑p(Z∣X,θold )lnp(X,Z∣θ)(2)
-
M步
通過最大似然上述期望得到更新的參數：
θ n e w = arg max Q ( θ , θ old ) (3) \theta^{new}= \arg \max \mathcal{Q}\left(\theta, \theta^{\text {old }}\right) \tag{3} θnew=argmaxQ(θ,θold )(3)
由于log操作直接作用于聯合分布 ln p ( X , Z ∣ θ ) \ln p(\mathbf{X}, \mathbf{Z} \mid \theta) lnp(X,Z∣θ)，是以M步是可以處理的
以下為通用EM算法步驟
-
一般形式的EM算法
目标是最大化下面的似然函數
p ( X ∣ θ ) = ∑ Z p ( X , Z ∣ θ ) (4) p(\mathbf{X} \mid \theta)=\sum_{Z} p(\mathbf{X}, \mathbf{Z} \mid \theta) \tag{4} p(X∣θ)=Z∑p(X,Z∣θ)(4)
直接對 p ( X ∣ θ ) p(\mathbf{X} \mid \theta) p(X∣θ) 進行優化是不可取的，但對于完全資料似然 p ( X , Z ∣ θ ) p(\mathbf{X}, \mathbf{Z} \mid \theta) p(X,Z∣θ) 卻是簡單的。
引入 q ( Z ) q(\mathbf{Z}) q(Z)定義隐變量，對于任意的 q ( Z ) q(\mathbf{Z}) q(Z)有以下：
ln p ( X ∣ θ ) = L ( q , θ ) + K L ( q ∣ ∣ p ) (5) \ln p(\mathbf{X} \mid \theta)=\mathcal{L}(q, \theta)+K L(q|| p)\tag{5} lnp(X∣θ)=L(q,θ)+KL(q∣∣p)(5)
定義 L ( q , θ ) = ∑ Z q ( Z ) ln { p ( X , Z ∣ θ ) q ( Z ) } K L ( q ∣ ∣ p ) = − ∑ Z q ( Z ) ln { p ( Z ∣ X , θ ) q ( Z ) } (6) \begin{aligned} \mathcal{L}(q, \theta) &=\sum_{Z} q(\mathbf{Z}) \ln \left\{\frac{p(\mathbf{X}, \mathbf{Z} \mid \theta)}{q(\mathbf{Z})}\right\} \\ K L(q|| p) &=-\sum_{Z} q(\mathbf{Z}) \ln \left\{\frac{p(\mathbf{Z} \mid \mathbf{X}, \theta)}{q(\mathbf{Z})}\right\} \tag{6} \end{aligned} L(q,θ)KL(q∣∣p)=Z∑q(Z)ln{q(Z)p(X,Z∣θ)}=−Z∑q(Z)ln{q(Z)p(Z∣X,θ)}(6)
其中 L ( q , θ ) \mathcal{L}(q, \theta) L(q,θ)一般被稱為ELBO（evidence lower bound）是一個下界值
為了證明（5）式，首先利用機率的product rule
ln p ( X , Z ∣ θ ) = ln p ( Z ∣ X , θ ) + ln p ( X ∣ θ ) (7) \ln p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta})=\ln p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta})+\ln p(\mathbf{X} \mid \boldsymbol{\theta}) \tag{7} lnp(X,Z∣θ)=lnp(Z∣X,θ)+lnp(X∣θ)(7)
ln p ( X ∣ θ ) = ln p ( X , Z ∣ θ ) − ln p ( Z ∣ X , θ ) (8) \ln p(\mathbf{X} \mid \boldsymbol{\theta}) =\ln p(\mathbf{X}, \mathbf{Z} \mid \boldsymbol{\theta}) - \ln p(\mathbf{Z} \mid \mathbf{X}, \boldsymbol{\theta})\tag{8} lnp(X∣θ)=lnp(X,Z∣θ)−lnp(Z∣X,θ)(8)
對8式左右同時對Z求和并且引入隐變量分布即可得到5式
如果KL消失，則ELBO等于X的對數似然函數
E步中 L ( q , θ o l d ) \mathcal{L}(q, \theta^{old}) L(q,θold)關于q(Z)最大化，同時保持 θ o l d \theta^{old} θold固定，最大值出現在KL散度消失的時候
M步中q(Z)固定， L ( q , θ ) \mathcal{L}(q, \theta) L(q,θ)關于關于參數最大化并且得到新的參數 θ n e w \theta^{new} θnew,這會引起ELBO和似然函數的增大。最大化的量是完全資料對數似然 p ( X , Z ∣ θ ) p(\mathbf{X}, \mathbf{Z} \mid \theta) p(X,Z∣θ) 的期望