EM算法的两种推导方式

EM算法有两种常见的推导方式，一种是李航老师在《统计学习方法》里面给出的，另一种是吴恩达老师在CS229课上讲到的，两种推导方式各有千秋，但都殊途同归，下面对这两种推导方式进行一个总结。由于两种推导方式里都用到了一个经典的不等式——Jensen不等式^[1]，所以下面先铺垫一下Jensen不等式。Jensen不等式的定义如下：
若$f$是凸函数，则

$$f\left(t x_1 + (1-t)x_2\right)\leq tf(x_1)+(1-t)f(x_2)$$

其中$t\in [0,1]$，若将$x$推广到$n$个时同样成立，即

$$f(t_1 x_1 + t_2x_2+...+t_nx_n)\leq t_1f(x_1)+t_2f(x_2)+...+t_nf(t_n)$$

其中$t_1,t_2,…,t_n\in[0,1],t_1+t_2+…+t_n=1$。此不等式在概率论中通常以如下形式出现

$$\varphi(E[X])\leq E[\varphi(X)]$$

其中$X$是一个随机变量，$\varphi$为凸函数，$E[X]$为随机变量$X$的期望。同理，若$f$和$\varphi$是凹函数，则只需将不等式中的$\leq$换成$\geq$即可。

EM算法的由来

假设现有一批独立同分布的样本数据$\{x_1,x_2,…,x_m\}$，它们是由某个含有隐变量的模型$p(x,z;\theta)$生成，现尝试用极大似然估计法估计此模型的参数。由对数似然函数的定义可知此时的对数似然函数为（假设$z$为离散型）

$$\begin{aligned} LL(\theta) &=\sum_{i=1}^{m} \ln p(x_i; \theta) \\ &=\sum_{i=1}^{m} \ln \sum_{z_i} p(x_i, z_i; \theta) \end{aligned}$$

显然，此时$LL(\theta)$里含有未知的隐变量$z$以及和（$z$为离散型时）或者积分（$z$为连续型时）的对数，因此无法按照传统方法直接求出使得$LL(\theta)$达到最大值的模型参数$\theta$，而EM算法则给出了一种迭代的方法来完成对$LL(\theta)$的极大化。下面给出EM算法的两种推导方式：

《统计学习方法》版^[2]

设$X=\{x_1,x_2,…,x_m\},Z=\{z_1,z_2,…,z_m\}$，则对数似然函数可以改写为

$$\begin{aligned} LL(\theta)&=\ln P(X\vert \theta)\\ &=\ln \sum_Z P(X,Z\vert\theta)\\ &=\ln \left(\sum_Z P(X\vert Z,\theta)P(Z\vert \theta)\right) \end{aligned}$$

EM算法采用的是通过迭代逐步近似极大化$L(\theta)$：假设第$t$次迭代时$\theta$的估计值是$\theta^{(t)}$，我们希望第$t+1$次迭代时的$\theta$能使$LL(\theta)$增大，也即$LL(\theta)>LL(\theta^{(t)})$。为此，考虑两者的差

$$\begin{aligned} LL(\theta)-LL(\theta^{(t)})&=\ln \left(\sum_Z P(X\vert Z,\theta)P(Z\vert \theta)\right)-\ln P(X\vert\theta^{(t)}) \\ &=\ln \left(\sum_Z P(Z\vert X,\theta^{(t)}) \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})}\right)-\ln P(X\vert\theta^{(t)}) \end{aligned}$$

由上述Jensen不等式可得

$$\begin{aligned} LL(\theta)-LL(\theta^{(t)}) &\geq \sum_Z P(Z\vert X,\theta^{(t)})\ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})}-\ln P(X\vert\theta^{(t)}) \\ &= \sum_Z P(Z\vert X,\theta^{(t)})\ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})}-1\cdot \ln P(X\vert\theta^{(t)}) \\ &= \sum_Z P(Z\vert X,\theta^{(t)})\ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})}-\sum_Z P(Z\vert X,\theta^{(t)})\cdot \ln P(X\vert\theta^{(t)}) \\ &=\sum_Z P(Z\vert X,\theta^{(t)}) \left( \ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})} - \ln P(X\vert\theta^{(t)}) \right)\\ &= \sum_Z P(Z\vert X,\theta^{(t)})\ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})P(X\vert\theta^{(t)})} \end{aligned}$$

令

$$B(\theta,\theta^{(t)})=LL(\theta^{(t)})+\sum_Z P(Z\vert X,\theta^{(t)})\ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})P(X\vert\theta^{(t)})}$$

则

$$LL(\theta)\geq B(\theta,\theta^{(t)})$$

即$B(\theta,\theta^{(t)})$是$LL(\theta)$的下界，此时若设$\theta^{(t+1)}$能使得$B(\theta,\theta^{(t)})$达到极大，也即

$$B(\theta^{(t+1)},\theta^{(t)}) \geq B(\theta,\theta^{(t)})$$

由于$LL(\theta^{(t)})=B(\theta^{(t)},\theta^{(t)})$，那么可以进一步推得

$$LL(\theta^{(t+1)})\geq B(\theta^{(t+1)},\theta^{(t)})\geq B(\theta^{(t)},\theta^{(t)})=LL(\theta^{(t)})$$ $$LL(\theta^{(t+1)})\geq LL(\theta^{(t)})$$

因此，任何能使得$B(\theta,\theta^{(t)})$增大的$\theta$，也可以使得$LL(\theta)$增大，于是问题就转化为了求解能使得$B(\theta,\theta^{(t)})$达到极大的$\theta^{(t+1)}$，即

$$\begin{aligned} \theta^{(t+1)}&=\mathop{\arg\max}_{\theta}B(\theta,\theta^{(t)}) \\ &=\mathop{\arg\max}_{\theta}\left( LL(\theta^{(t)})+\sum_Z P(Z\vert X,\theta^{(t)})\ln \cfrac{P(X\vert Z,\theta)P(Z\vert \theta)}{P(Z\vert X,\theta^{(t)})P(X\vert\theta^{(t)})}\right) \end{aligned}$$

略去对$\theta$极大化而言是常数的项：

$$\begin{aligned} \theta^{(t+1)}&=\mathop{\arg\max}_{\theta}\left(\sum_Z P(Z\vert X,\theta^{(t)})\ln\left( P(X\vert Z,\theta)P(Z\vert \theta)\right)\right) \\ &=\mathop{\arg\max}_{\theta}\left(\sum_Z P(Z\vert X,\theta^{(t)})\ln P(X,Z\vert \theta)\right) \\ &=\mathop{\arg\max}_{\theta}Q(\theta,\theta^{(t)}) \end{aligned}$$

到此即完成了EM算法的一次迭代，求出的$\theta^{(t+1)}$作为下一次迭代的初始$\theta^{(t)}$。综上所述即可总结出EM算法的“E步”和“M步”分别为：

E步：计算完全数据的对数似然函数$\ln P(X,Z\vert \theta)$关于在给定观测数据$X$和当前参数$\theta^{(t)}$下对未观测数据$Z$的条件概率分布$ P(Z\vert X,\theta^{(t)})$的期望，也即$Q(\theta,\theta^{(t)})$：

$$Q(\theta,\theta^{(t)})=E_Z[\ln P(X,Z\vert \theta)\vert X,\theta^{(t)}]=\sum_Z P(Z\vert X,\theta^{(t)})\ln P(X,Z\vert \theta)$$

M步：求使得$Q(\theta,\theta^{(t)})$达到极大的$\theta^{(t+1)}$。

CS229版^[3]

设$z_i$的概率质量函数为$Q_i(z_i)$，则$LL(\theta)$可以作如下恒等变形

$$\begin{aligned} LL(\theta) &=\sum_{i=1}^{m} \ln p(x_i; \theta) \\ &=\sum_{i=1}^{m} \ln \sum_{z_i} p(x_i, z_i; \theta) \\ &=\sum_{i=1}^{m} \ln \sum_{z_i} Q_i(z_i)\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)} \\ \end{aligned}$$

其中$\sum_{z_i} Q_i(z_i)\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}$可以看做是对$\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}$关于$z_i$求期望，也即

$$\sum_{z_i} Q_i(z_i)\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}=E_{z_i}\left[\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}\right]$$

那么由Jensen不等式可得

$$\ln\left(E_{z_i}\left[\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}\right]\right)\geq E_{z_i}\left[\ln\left(\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}\right)\right]$$ $$\ln\sum_{z_i} Q_i(z_i)\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}\geq \sum_{z_i} Q_i(z_i)\ln\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}$$

将此式代入$LL(\theta)$可得

$$\begin{aligned} LL(\theta) &=\sum_{i=1}^{m} \ln \sum_{z_i} Q_i(z_i)\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)} \qquad(A.1)\\ &\geq \sum_{i=1}^{m}\sum_{z_i} Q_i(z_i)\ln\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)} \end{aligned}$$

若令$B(\theta)=\sum\limits_{i=1}^{m}\sum\limits_{z_i} Q_i(z_i)\ln\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}$，则此时$B(\theta)$为$LL(\theta)$的下界函数，那么这个下界函数所能构成的最优下界是多少？也即$B(\theta)$的最大值是多少？显然，$B(\theta)$是$LL(\theta)$的下界函数，那么$LL(\theta)$就是其上界函数，所以如果能使得$B(\theta)=LL(\theta)$，那么此时的$B(\theta)$就取到了最大值。根据Jensen不等式的性质可知，如果能使得$\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}$恒等于某个常量$c$，大于等于号便可以取到等号。因此，只需任意选取满足$\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}=c$的$Q_i(z_i)$就能使得$B(\theta)$达到最大值。由于$Q_i(z_i)$是$z_i$的概率质量函数，所以$Q_i(z_i)$同时也满足约束$0\leq Q_i(z_i)\leq 1,\sum\limits_{z_i} Q_i(z_i)=1$，那么结合$Q_i(z_i)$的所有约束可以推得

$$\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}=c$$ $$p(x_i, z_i; \theta)=c\cdot Q_i(z_i)$$ $$\sum_{z_i}p(x_i, z_i; \theta)=c\cdot \sum_{z_i}Q_i(z_i)$$ $$\sum_{z_i}p(x_i, z_i; \theta)=c$$ $$\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)}=\sum_{z_i}p(x_i, z_i; \theta)$$ $$Q_i(z_i)=\cfrac{p(x_i, z_i; \theta)}{\sum\limits_{z_i}p(x_i, z_i; \theta)}=\cfrac{p(x_i, z_i; \theta)}{p(x_i; \theta)}=p(z_i|x_i; \theta)$$

所以，当且仅当$Q_i(z_i)=p(z_i|x_i; \theta)$时$B(\theta)$取到最大值，将$Q_i(z_i)=p(z_i|x_i; \theta)$代回$LL(\theta)$和$B(\theta)$可以推得

$$\begin{aligned} LL(\theta) &=\sum_{i=1}^{m} \ln \sum_{z_i} Q_i(z_i)\cfrac{p(x_i, z_i; \theta)}{Q_i(z_i)} &\qquad(A.2.1)\\ &=\sum_{i=1}^{m} \ln \sum_{z_i}p(z_i|x_i; \theta)\cfrac{p(x_i, z_i; \theta)}{p(z_i|x_i; \theta)} &\qquad(A.2.2)\\ &=\sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i; \theta)\ln\cfrac{p(x_i, z_i; \theta)}{p(z_i|x_i; \theta)}&\qquad(A.2.3)\\ &=\max\{B(\theta)\} &\qquad(A.2.4)\\ \end{aligned}$$

其中，（A.2.3）是（A.1）中不等号取等号时的情形。由以上推导可知，对数似然函数$LL(\theta)$等价于其下界函数的最大值$\max\{B(\theta)\}$，所以要想极大化$LL(\theta)$可以通过极大化$\max\{B(\theta)\}$来间接极大化$LL(\theta)$，因此，下面考虑如何极大化$\max\{B(\theta)\}$。假设已知第$t$次迭代的参数为$\theta^{(t)}$，而第$t+1$次迭代的参数$\theta^{(t+1)}$通过如下方式求得

$$\begin{aligned} \theta^{(t+1)}&=\arg\max_{\theta}\max\{B(\theta)\} \qquad\qquad\qquad\qquad\qquad(A.3) \\ &=\arg\max_{\theta}\sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i;\theta^{(t)})\ln\cfrac{p(x_i, z_i; \theta)}{p(z_i|x_i; \theta^{(t)})} \\ &=\arg\max_{\theta}\sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i;\theta^{(t)})\ln p(x_i, z_i; \theta) \end{aligned}$$

将$\theta^{(t+1)}$代入$LL(\theta^{(t+1)})$则可以进一步推得

$$\begin{aligned} LL(\theta^{(t+1)}) &=\max\{B(\theta^{(t+1)})\} &\qquad(A.4.1) \\ &=\sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i; \theta^{(t+1)})\ln\cfrac{p(x_i, z_i; \theta^{(t+1)})}{p(z_i|x_i; \theta^{(t+1)})} &\qquad(A.4.2)\\ &\geq \sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i; \theta^{(t)})\ln\cfrac{p(x_i, z_i; \theta^{(t+1)})}{p(z_i|x_i; \theta^{(t)})} &\qquad(A.4.3)\\ &\geq \sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i; \theta^{(t)})\ln\cfrac{p(x_i, z_i; \theta^{(t)})}{p(z_i|x_i; \theta^{(t)})} &\qquad(A.4.4)\\ &=\max\{B(\theta^{(t)})\} &\qquad(A.4.5) \\ &=LL(\theta^{(t)})&\qquad(A.4.6) \end{aligned}$$

其中，（A.4.1）和（A.4.2）由（A.2）推得；（A.4.3）由（A.1）推得；（A.4.4）由（A.3）推得；（A.4.5）和（A.4.6）由（A.2）推得。显然，若令

$$Q(\theta,\theta^{(t)})=\sum_{i=1}^{m}\sum_{z_i} p(z_i|x_i; \theta^{(t)})\ln p(x_i, z_i; \theta)$$

那么由（A.4）可知，凡是能使得$Q(\theta,\theta^{(t)})$达到极大的$\theta^{(t+1)}$一定能使得$LL(\theta^{(t+1)})\geq LL(\theta^{(t)})$。综上所述即可总结出EM算法的“E步”和“M步”分别为：

E步：令$Q_i(z_i)=p(z_i|x_i; \theta)$并写出$Q(\theta,\theta^{(t)})$；

M步：求使得$Q(\theta,\theta^{(t)})$到达极大的$\theta^{(t+1)}$。

证明两种推导方式中的Q函数相等

$$\begin{aligned} Q(\theta|\theta^{(t)})&=\sum_Z P(Z|X,\theta^{(t)})\ln P(X,Z|\theta) \\ &=\sum_{z_1,z_2,...,z_m}\left\{\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\ln\left[ \prod_{i=1}^m P(x_i,z_i|\theta) \right] \right\} \\ &=\sum_{z_1,z_2,...,z_m}\left\{\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\left[ \sum_{i=1}^m\ln P(x_i,z_i|\theta) \right] \right\} \\ &=\sum_{z_1,z_2,...,z_m}\left\{\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\left[\ln P(x_1,z_1|\theta) + \ln P(x_2,z_2|\theta) +...+ \ln P(x_m,z_m|\theta)\right] \right\} \\ &=\sum_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_1,z_1|\theta) \right]+...+\sum_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_m,z_m|\theta) \right] \\ \end{aligned}$$

其中$\sum\limits_{z_1,z_2,…,z_m}\left[\prod\limits_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_1,z_1|\theta) \right] $可作如下恒等变形：

$$\begin{aligned} &=\sum\limits_{z_1,z_2,...,z_m}\left[\prod_{i=2}^mP(z_i|x_i,\theta^{(t)})\cdot P(z_1|x_1,\theta^{(t)})\cdot\ln P(x_1,z_1|\theta) \right] \\ &=\sum_{z_1}\sum\limits_{z_2,...,z_m}\left[\prod_{i=2}^mP(z_i|x_i,\theta^{(t)})\cdot P(z_1|x_1,\theta^{(t)})\cdot\ln P(x_1,z_1|\theta) \right] \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta) \sum\limits_{z_2,...,z_m}\left[\prod_{i=2}^mP(z_i|x_i,\theta^{(t)}) \right] \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta)\sum\limits_{z_2,...,z_m}\left[\prod_{i=3}^mP(z_i|x_i,\theta^{(t)})\cdot P(z_2|x_2,\theta^{(t)}) \right] \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta) \left\{\sum\limits_{z_2}\sum\limits_{z_3,...,z_m}\left[\prod_{i=3}^mP(z_i|x_i,\theta^{(t)})\cdot P(z_2|x_2,\theta^{(t)}) \right]\right\} \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta) \left\{\sum_{z_2}P(z_2|x_2,\theta^{(t)}) \sum\limits_{z_3,...,z_m}\left[\prod_{i=3}^mP(z_i|x_i,\theta^{(t)})\right]\right\} \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta) \left\{\sum_{z_2}P(z_2|x_2,\theta^{(t)})\times\sum_{z_3}P(z_3|x_3,\theta^{(t)})\times...\times\sum_{z_m}P(z_m|x_m,\theta^{(t)})\right\} \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta)\times \left\{1\times1\times...\times1\right\} \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta) \\ \end{aligned}$$

所以

$$\sum\limits_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_1,z_1|\theta) \right]=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta)$$

同理可得

$$\begin{aligned} \sum\limits_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_2,z_2|\theta) \right] &=\sum_{z_2}P(z_2|x_2,\theta^{(t)})\ln P(x_2,z_2|\theta) \\ &\vdots\\ \sum\limits_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_m,z_m|\theta) \right] &=\sum_{z_m}P(z_m|x_m,\theta^{(t)})\ln P(x_m,z_m|\theta) \end{aligned}$$

将上式代入$Q(\theta|\theta^{(t)})$可得

$$\begin{aligned} Q(\theta|\theta^{(t)})&=\sum_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_1,z_1|\theta) \right]+...+\sum_{z_1,z_2,...,z_m}\left[\prod_{i=1}^mP(z_i|x_i,\theta^{(t)})\cdot\ln P(x_m,z_m|\theta) \right] \\ &=\sum_{z_1}P(z_1|x_1,\theta^{(t)})\ln P(x_1,z_1|\theta) +...+\sum_{z_m}P(z_m|x_m,\theta^{(t)})\ln P(x_m,z_m|\theta) \\ &=\sum_{i=1}^m\sum_{z_i}P(z_i|x_i,\theta^{(t)})\ln P(x_i,z_i|\theta)\\ \end{aligned}$$

参考文献

[1] Jensen’s inequality
[2] 李航.《统计学习方法》第9章
[3] Andrew Ng.CS229-notes8</a>