EM算法公式推导

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 步，计算：
     Q ( θ , θ t ) = E Z [ log ⁡ P ( X , Z ∣ θ ) ∣ X , θ ( t ) ] = ∑ Z log ⁡ P ( X , Z ∣ θ ) P ( Z ∣ X , θ ( t ) )

     $$\begin{align} 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{align}$$ Q(θ,θt)​=EZ​[logP(X,Z∣θ)∣X,θ(t)]=Z∑​logP(X,Z∣θ)P(Z∣X,θ(t))​​
     这里 $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$ ：
H ( θ ( t ) , θ ( t ) ) − H ( θ ( t + 1 ) , θ ( t ) ) = ∫ Z P ( Z ∣ X , θ ( t ) ) log ⁡ P ( Z ∣ X , θ ( t ) ) − ∫ Z P ( Z ∣ X , θ ( t ) ) log ⁡ P ( Z ∣ X , θ ( t + 1 ) ) = ∫ Z P ( Z ∣ X , θ ( t ) ) log ⁡ P ( Z ∣ X , θ ( t ) ) P ( Z ∣ X , θ ( t + 1 ) ) = K L ( P ( Z ∣ X , θ ( t ) ) ∣ ∣ P ( Z ∣ X , θ ( t + 1 ) ) ) ≥ 0

$$\begin{align} H(\theta^{(t)},\theta^{(t)})-H(\theta^{(t+1)},\theta^{(t)})&=\int_ZP(Z|X,\theta^{(t)})\log P(Z|X,\theta^{(t)})-\int_ZP(Z|X,\theta^{(t)})\log P(Z|X,\theta^{(t+1)})\\ &=\int_ZP(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)}))\ge0 \end{align}$$ H(θ(t),θ(t))−H(θ(t+1),θ(t))​=∫Z​P(Z∣X,θ(t))logP(Z∣X,θ(t))−∫Z​P(Z∣X,θ(t))logP(Z∣X,θ(t+1))=∫Z​P(Z∣X,θ(t))logP(Z∣X,θ(t+1))P(Z∣X,θ(t))​=KL(P(Z∣X,θ(t))∣∣P(Z∣X,θ(t+1)))≥0​​
发现最后的形式是 $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 )$ 出发：
log ⁡ P ( X ∣ θ ) = log ⁡ P ( X , Z ∣ θ ) P ( Z ∣ X , θ ) = log ⁡ P ( X , Z ∣ θ ) − log ⁡ P ( Z ∣ X , θ ) = log ⁡ P ( X , Z ∣ θ ) q ( Z ) − log ⁡ P ( Z ∣ X , θ ) q ( Z )

$$\begin{align} \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{align}$$ logP(X∣θ)​=logP(Z∣X,θ)P(X,Z∣θ)​=logP(X,Z∣θ)−logP(Z∣X,θ)=logq(Z)P(X,Z∣θ)​−q(Z)logP(Z∣X,θ)​​​

• 第一步先从似然，引入隐变量 $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$ 无关，相当于对常数求期望，不变

右边 = ∫ Z q ( Z ) log ⁡ P ( X , Z ∣ θ ) q ( Z ) d Z − ∫ Z q ( Z ) log ⁡ P ( Z ∣ X , θ ) q ( Z ) d Z = E L B O + K L ( q ( Z ) ∣ ∣ P ( Z ∣ X , θ ) )

$$\begin{align} 右边&=\int_Zq(Z)\log \frac{P(X,Z|\theta)}{q(Z)}dZ-\int_Zq(Z)\log\frac{ P(Z|X,\theta)}{q(Z)}dZ\\ &=ELBO+KL(q(Z)||P(Z|X,\theta))\\ \end{align}$$ 右边​=∫Z​q(Z)logq(Z)P(X,Z∣θ)​dZ−∫Z​q(Z)logq(Z)P(Z∣X,θ)​dZ=ELBO+KL(q(Z)∣∣P(Z∣X,θ))​​

• 右边也求期望后，后一项是 $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 )$ 也达到最大。即：

θ ^ = arg ⁡ max ⁡ θ E L B O = arg ⁡ max ⁡ θ ∫ Z q ( Z ) log ⁡ P ( X , Z ∣ θ ) q ( Z ) d Z = arg ⁡ max ⁡ θ ∫ Z P ( X , Z ∣ θ ( t ) ) log ⁡ P ( X , Z ∣ θ ) P ( X , Z ∣ θ ( t ) ) ) d Z = arg ⁡ max ⁡ θ ∫ Z P ( X , Z ∣ θ ( t ) ) [ log ⁡ P ( X , Z ∣ θ ) − log ⁡ P ( X , Z ∣ θ ( t ) ) ) ] d Z = arg ⁡ max ⁡ θ ∫ Z P ( X , Z ∣ θ ( t ) ) log ⁡ P ( X , Z ∣ θ ) d Z

$$\begin{align} \hat{\theta}&=\arg\max_{\theta}ELBO\\ &=\arg\max_{\theta}\int_Zq(Z)\log \frac{P(X,Z|\theta)}{q(Z)}dZ\\ &=\arg\max_{\theta}\int_ZP(X,Z|\theta^{(t)})\log \frac{P(X,Z|\theta)}{P(X,Z|\theta^{(t)}))}dZ\\ &=\arg\max_{\theta}\int_ZP(X,Z|\theta^{(t)})[\log P(X,Z|\theta)-\log P(X,Z|\theta^{(t)}))]dZ\\ &=\arg\max_{\theta}\int_ZP(X,Z|\theta^{(t)})\log P(X,Z|\theta)dZ\\ \end{align}$$ θ^​=argθmax​ELBO=argθmax​∫Z​q(Z)logq(Z)P(X,Z∣θ)​dZ=argθmax​∫Z​P(X,Z∣θ(t))logP(X,Z∣θ(t)))P(X,Z∣θ)​dZ=argθmax​∫Z​P(X,Z∣θ(t))[logP(X,Z∣θ)−logP(X,Z∣θ(t)))]dZ=argθmax​∫Z​P(X,Z∣θ(t))logP(X,Z∣θ)dZ​​

• 当 $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()$

下面开始推导：
log ⁡ P ( X ∣ θ ) = log ⁡ ∫ Z P ( X , Z ∣ θ ) d Z = log ⁡ ∫ Z P ( X , Z ∣ θ ) q ( X ) q ( Z ) d Z = log ⁡ E q ( z ) [ P ( X , Z ∣ θ ) q ( Z ) ] ≥ E q ( z ) log ⁡ [ P ( X , Z ∣ θ ) q ( Z ) ]

$$\begin{align} \log P(X|\theta)&=\log\int_ZP(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{align}$$ logP(X∣θ)​=log∫Z​P(X,Z∣θ)dZ=log∫Z​q(X)P(X,Z∣θ)​q(Z)dZ=logEq(z)​[q(Z)P(X,Z∣θ)​]≥Eq(z)​log[q(Z)P(X,Z∣θ)​]​​

• 同样是引入隐变量 $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. 机器学习白板推导