EM算法公式推導

EM 算法是一種用來進行含有隱變量的概率生成模型參數估計的迭代算法。

EM算法步驟

EM 算法通過迭代求 $L(\theta )=\log P(X|\theta )$ 的極大似然估計，每次迭代包含兩部：E步，求期望；M步，求極大化。

算法流程：

• 輸入：觀測變量數據 $X$，隱變量數據 $Z$，聯合分布 $P(X,Z|\theta )$ ，條件分布：$P(Z|X,\theta )$ ；

• 輸出：模型參數 $\theta$ ；

• 步驟

  1. 選擇參數的初值 ${\theta }^0$ ，開始迭代；

  2. E 步：記 ${\theta }^t$ 為第 $t$ 次迭代參數 $\theta$ 的估計值，在第 $i+1$ 次迭代的 E 步，計算：
     $$\begin{array}{rl}Q(\theta ,{\theta }^t)& ={\mathbb{E}}_Z[\log P(X,Z|\theta )|X,{\theta }^{(t)}]\\ & =\sum _Z\log P(X,Z|\theta )P(Z|X,{\theta }^{(t)})\end{array}\text{\hspace{1em}?}$$
     這里 $P(Z|X,{\theta }^{(t)})$ 為給定觀測數據 $X$ 和當前參數估計 ${\theta }^{(t)}$ 下隱變量數據 $Z$ 的條件概率分布；

  3. M 步：求使 $Q(\theta ,{\theta }^{(t)})$ 極大化的 $\theta$ ，確定第 $t+1$ 次迭代的參數估計值 ${\theta }^{t+1}$ :
     $${\theta }^{(t+1)}=\arg \underset{\theta }{\max }Q(\theta ,{\theta }^t)$$

  4. 重復 2、3 兩步，直到收斂。

函數 $Q(\theta ,{\theta }^{(t)})$ 是 EM 算法的核心，稱為 $Q$ 函數。

EM算法收斂性證明

EM 迭代算法終歸要求的是 $\log P(X|\theta )$ 的極大似然估計，因此，要證明它的收斂性，即要證明：
$$\log P(X|{\theta }^{(t+1)})\ge \log P(X|{\theta }^{(t)})$$
下面開始證明：
$$\log P(X|\theta )=\log \frac{P(X,Z|\theta )}{P(Z|X,\theta )}=\log P(X,Z|\theta )?P(Z|X,\theta )$$
接下來我們同時對等式兩邊乘 $P(Z|X,{\theta }^{(t)})$ 在對 $Z$ 求積分：
$$左邊={\int }_{Z}P(Z|X,{\theta }^{(t)})\log P(X,Z|\theta )dZ=\log P(X,Z|\theta ){\int }_{Z}P(Z|X,{\theta }^{(t)})dZ=\log P(X,Z|\theta )$$
即，左邊相當于沒變。
$$右邊={\int }_{Z}P(Z|X,{\theta }^{(t)})\log P(X,Z|\theta )?{\int }_{Z}P(Z|X,{\theta }^{(t)})\log P(Z|X,\theta )=Q(\theta ,{\theta }^{(t)})?H(\theta ,{\theta }^{(t)})$$
分別將上式兩項記為 $Q(\theta ,{\theta }^{(t)})$ 和 $H(\theta ,{\theta }^{(t)})$ 。我們要證的是 $\log P(X|{\theta }^{(t+1)})\ge \log P(X|{\theta }^{(t)})$ ，這里可以通過證明
$$\log P(X|{\theta }^{(t+1)})?\log P(X|{\theta }^{(t)})=Q({\theta }^{(t+1)},{\theta }^{(t)})?Q({\theta }^{(t)},{\theta }^{(t)})+H({\theta }^{(t)},{\theta }^{(t)})?H({\theta }^{(t+1)},{\theta }^{(t)})\ge 0$$
來得到。對于 $Q(\theta ,{\theta }^{(t)})$ ，明顯是通過迭代過程的 $\arg \max$ 可以保證。因此，我們只需證明 $H({\theta }^{(t)},{\theta }^{(t)})?H({\theta }^{(t+1)},{\theta }^{(t)})\ge 0$ ：
$$\begin{array}{rl}H({\theta }^{(t)},{\theta }^{(t)})?H({\theta }^{(t+1)},{\theta }^{(t)})& ={\int }_{Z}P(Z|X,{\theta }^{(t)})\log P(Z|X,{\theta }^{(t)})?{\int }_{Z}P(Z|X,{\theta }^{(t)})\log P(Z|X,{\theta }^{(t+1)})\\ & ={\int }_{Z}P(Z|X,{\theta }^{(t)})\log \frac{P(Z|X,{\theta }^{(t)})}{P(Z|X,{\theta }^{(t+1)})}\\ & =KL(P(Z|X,{\theta }^{(t)})||P(Z|X,{\theta }^{(t+1)}))\ge 0\end{array}\text{\hspace{1em}?}$$
發現最后的形式是 $P(Z|X,\theta {)}^{(t)}$ 和 $P(Z|X,{\theta }^{(t+1)})$ 的 KL 散度，故可以直接得到上式大于等于零，收斂性得證。這里也可以由詹森不等式證得。

上面我們是給出最終的公式，然后證明它的收斂性，即 $\log P(X|{\theta }^{(t+1)})\ge \log P(X|{\theta }^{(t)})$ ，這樣來說明 EM 算法確實可以以迭代的形式來最大化 $P(X|\theta )$ 。但是這個公式是怎么得到的呢？下面兩小節我們分別從 KL 散度的角度和 Jensen 不等式的角度來推導 EM 算法的導出。

EM算法的導出——KL散度

我們再回顧一下整個算法的設定：

• 觀測數據：$X$

• 隱變量：$Z$

• 完整數據：$(X,Z)$

• 參數：$\theta$

• MLE：${\hat{\theta }}_{MLE}=\log P(X|\theta )$

• EM 公式
  $$\begin{gathered} {\theta }^{(t+1)}=\arg \underset{\theta }{\max }\int \log P(X,Z|\theta )P(Z|X,{\theta }^{(t)})dZ \\ E步：P(Z|X,{\theta }^{(t)})\to {\mathbb{E}}_{Z|X,{\theta }^{(t)}}[\log P(X,Z|\theta )] \\ M步：{\theta }^{(t+1)}=\arg \underset{\theta }{\max }{\mathbb{E}}_{Z|X,{\theta }^{(t)}}[\log P(X,Z|\theta )] \end{gathered}$$

E 步求對數條件聯合概率 $\log P(X,Z|\theta )$ 關于后驗 $Z|X,{\theta }^{(t)}$ 的期望，M 步選擇一個新的 ${\theta }^{(t+1)}$ 使得上述期望達到最大。從而迭代地使得 $\log P(X|\theta )$ 達到最大。上面已經證明了這個算法的收斂性。

下面開始推導公式的導出。我們還是從對數似然 $\log P(X|\theta )$ 出發：
$$\begin{array}{rl}\log P(X|\theta )& =\log \frac{P(X,Z|\theta )}{P(Z|X,\theta )}\\ & =\log P(X,Z|\theta )?\log P(Z|X,\theta )\\ & =\log \frac{P(X,Z|\theta )}{q(Z)}?\frac{\log P(Z|X,\theta )}{q(Z)}\end{array}\text{\hspace{1em}?}$$

• 第一步先從似然，引入隱變量 $Z$ ，根據聯合概率分布的公式進行改寫；

• 然后通過對數的性質寫開；

• 引入關于 $Z$ 的概率分布 $q(Z)$ ，兩個對數里面同時除 $q(Z)$

• 然后兩邊同時求關于 $q(Z)$ 的期望

$$左邊={\int }_{Z}q(Z)\log P(X|\theta )dZ=\log P(X|\theta ){\int }_{Z}q(Z)dZ=\log P(X|\theta )\times 1$$

• 左邊原來就與 $Z$ 無關，相當于對常數求期望，不變

$$\begin{array}{rl}右邊& ={\int }_{Z}q(Z)\log \frac{P(X,Z|\theta )}{q(Z)}dZ?{\int }_{Z}q(Z)\log \frac{P(Z|X,\theta )}{q(Z)}dZ\\ & =ELBO+KL(q(Z)||P(Z|X,\theta ))\end{array}\text{\hspace{1em}?}$$

• 右邊也求期望后，后一項是 $q(Z)$ 對 $P(Z|X,\theta )$ 的相對熵，也就是 KL 散度。而前一項我們通常稱為 ELBO （Evidence Lower BOund）證據下界。很明顯的， KL 散度是恒正的，因此前一項 ELBO 是 $\log P(X|\theta )$ 的一個下界。當且僅當后一項相對熵為零，即兩個分布完全相同 $q(Z)=P(Z|X,{\theta }^{(t)})$ 時取到等號。

  EM 算法的思想就是通過使得 ELBO 取得最大，從而使得對數似然 $\log P(X|\theta )$ 也達到最大。即：

$$\begin{array}{rl}\hat{\theta }& =\arg \underset{\theta }{\max }ELBO\\ & =\arg \underset{\theta }{\max }{\int }_{Z}q(Z)\log \frac{P(X,Z|\theta )}{q(Z)}dZ\\ & =\arg \underset{\theta }{\max }{\int }_{Z}P(X,Z|{\theta }^{(t)})\log \frac{P(X,Z|\theta )}{P(X,Z|{\theta }^{(t)}))}dZ\\ & =\arg \underset{\theta }{\max }{\int }_{Z}P(X,Z|{\theta }^{(t)})[\log P(X,Z|\theta )?\log P(X,Z|{\theta }^{(t)}))]dZ\\ & =\arg \underset{\theta }{\max }{\int }_{Z}P(X,Z|{\theta }^{(t)})\log P(X,Z|\theta )dZ\end{array}\text{\hspace{1em}?}$$

• 當 $q(Z)=P(Z|X,{\theta }^{(t)})$ 時取到等號，代入進去
• 在經過一次變換后，我們發現中括號中后面一項與 $\theta$ 無關，因此丟掉。注意，在迭代算法中 ${\theta }^{(t)},{\theta }^{(t+1)}$ 都是常數，$\theta$ 才是變量
• 最終得到了 EM 的公式

EM算法的導出——Jensen不等式

下面我們再從 Jensen 不等式的角度來進行推導。

先來介紹一下 Jensen 不等式，這里只介紹 EM 算法推導需要用到的程度：

設 $c=ta+(1?t)b$，對于一個凸函數 $f(x)$ 來說，有 $f(c)=f(ta+(1?t)b)\ge tf(a)+(1?t)f(b)$ 。

我們如果取 $t=\frac{1}{2}$ ，則有 $f(\frac{1}{2}a+\frac{1}{2}b)\ge \frac{1}{2}f(a)+\frac{1}{2}f(b)$ 。即對凸函數來說，均值的函數值大于等于函數值的均值。而在概率論中，均值就是期望，即有 $f(\mathbb{E})\ge \mathbb{E}f()$

下面開始推導：
$$\begin{array}{rl}\log P(X|\theta )& =\log {\int }_{Z}P(X,Z|\theta )dZ\\ & =\log {\int }_Z\frac{P(X,Z|\theta )}{q(X)}q(Z)dZ\\ & =\log {\mathbb{E}}_{q(z)}[\frac{P(X,Z|\theta )}{q(Z)}]\\ & \ge {\mathbb{E}}_{q(z)}\log [\frac{P(X,Z|\theta )}{q(Z)}]\end{array}\text{\hspace{1em}?}$$

• 同樣是引入隱變量 $Z$， 這次轉換為對聯合概率分布積分的形式；
• 變形，上下同乘 $q(X)$；
• 我們通常講積分寫成期望的形式；
• log 函數是凸函數，這里使用 Jensen 不等式，其實這里得到的期望就是 ELBO

這里的等號當且僅當 $\frac{P(X,Z|\theta )}{q(Z)}$ 是常數時取到，即：
$$\begin{gathered} \frac{P(X,Z|\theta )}{q(Z)}=C \\ q(Z)=\frac{1}{C}P(X,Z|\theta ) \\ {\int }_{Z}q(Z)dZ={\int }_Z\frac{1}{C}P(X,Z|\theta )dZ \\ 1=\frac{1}{C}{\int }_{Z}P(X,Z|\theta )dZ=\frac{1}{C}P(X|\theta ) \end{gathered}$$

• 做一個變形；
• 等式兩邊同時對 $Z$ 求積分；
• 左邊就是 1，右邊把 $Z$ 積掉；
• 得到 $C=P(X|\theta )$，代回到原式中：

$$\begin{gathered} \frac{P(X,Z|\theta )}{q(Z)}=P(X|\theta ) \\ q(Z)=\frac{P(X,Z|\theta )}{P(X|\theta )}=P(Z|X,\theta ) \end{gathered}$$

可以看到 $q(Z)$ 就是后驗 $P(Z|X,{\theta }^{(t)})$ ，這與我們在上一小節的結論是一致的，再后面就與上一小節一樣了，不在贅述。

Ref

1. 統計學習方法——李航
2. 機器學習白板推導