EM算法推导详解

一、算法简介

最大期望算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin算法，是一类通过迭代进行极大似然估计（Maximum Likelihood Estimation, MLE）的优化算法，通常作为牛顿迭代法（Newton-Raphson method）的替代用于对包含隐变量（latent variable）或缺失数据（incomplete-data）的概率模型进行参数估计。

EM算法的标准计算框架由E步（Expectation-step，求期望）和M步（Maximization step，求最大值）交替组成，算法的收敛性可以确保迭代至少逼近局部极大值。

概率模型有时既含有观测变量，又含有隐变量或潜在变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法，或贝叶斯估计法估计模型参数。

但是当模型中含有隐变量时，就不能简单的使用这些估计方法。EM算法就是含有隐变量的概率模型参数的极大似然估计，或极大后验概率估计法。

---

二、EM算法推导

下面给出详细的推导过程：

给定一组训练样本$x_1,x_2,...x_n$，样本间独立，我们想找到每个样本间隐含的类别$z$，能使$p(x,z)$最大。

通过最大似然估计建立目标函数，其中$\theta$是需要估计的模型参数：
$$f(x|\theta )=\prod _{i=1}^{m}P(x_i|\theta )\text{\hspace{1em}(1)}$$

对其取对数，则所以公式（1）又可以写成公式（2）：
$$\begin{gathered} l(\theta )=logf(x|\theta )=\sum _i^{m}logP(x|\theta ) \\ =\sum _i^{m}log\sum _{z}P(x,z|\theta )\text{\hspace{1em}(2)} \end{gathered}$$

式中第一个等号是对极大似然估计取对数，第二步是对每个样例间的每个可能类别z求联合分布概率和。

通过这个式子去求$l(\theta )$还是很懵。

假如，存在一个下界$J$，使得$l(\theta )\ge J$成立

那么对于如何求解最大的$l(\theta )$就变得稍微容易点了：

对于$l(\theta )$的下界$J$，使得$J$不断增大，那么$l(\theta )$也会不断增大。当$J$收敛时，$l(\theta )$也随之达到最大值。

此时，问题就转移到了$J$这个下界的函数推导以及求其最大值上了

这时就会用到著名的Jensen不等式了：

对于每一个样本$x_i$，用$Q_i$表示该样本隐含变量z的某种分布，那么$Q_i$满足条件是:

$$\sum _z{Q}_i(z)=1，Q_i(z)\ge 0$$

于是对于（2）上下同乘以$Q_i(z^{(i)})$：

l ( θ ) = ∑ i m l o g ∑ z P ( x , z ∣ θ ) = ∑ i m l o g ∑ z Q i ( z ( i ) ) P ( x , z ∣ θ ) Q i ( z ( i ) ) (3)

$$\begin{aligned} l(\theta) &= \sum_{i}^{m}log\sum_zP(x,z|θ)\\ &= \sum_{i}^{m}log\sum_z Q_i(z^{(i)}) \frac {P(x,z|θ)} {Q_i(z^{(i)})} \tag{3} \end{aligned}$$ l(θ)​=i∑m​logz∑​P(x,z∣θ)=i∑m​logz∑​Qi​(z(i))Qi​(z(i))P(x,z∣θ)​​(3)

由于${\sum }_z{Q}_i(z)=1$。用到Jensen不等式，则有：

l ( θ ) = ∑ i m l o g ∑ z Q i ( z ( i ) ) P ( x , z ∣ θ ) Q i ( z ( i ) ) ≥ ∑ i m ∑ z Q i ( z ( i ) ) l o g P ( x , z ∣ θ ) Q i ( z ( i ) ) (4)

$$\begin{aligned} l(\theta) &= \sum_{i}^{m}log\sum_z Q_i(z^{(i)}) \frac {P(x,z|θ)} {Q_i(z^{(i)})}\\ & \geq \sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})} \tag{4} \end{aligned}$$ l(θ)​=i∑m​logz∑​Qi​(z(i))Qi​(z(i))P(x,z∣θ)​≥i∑m​z∑​Qi​(z(i))logQi​(z(i))P(x,z∣θ)​​(4)

到这里，$J$就已经出来了。即：

l ( θ ) ≥ J ( z , Q ) = ∑ i m ∑ z Q i ( z ( i ) ) l o g P ( x , z ∣ θ ) Q i ( z ( i ) ) (5)

$$\begin{aligned} l(\theta) &\geq J(z, Q)\\ &= \sum_{i}^{m}\sum_z Q_i(z^{(i)})log \frac {P(x,z|θ)} {Q_i(z^{(i)})}\tag{5} \end{aligned}$$ l(θ)​≥J(z,Q)=i∑m​z∑​Qi​(z(i))logQi​(z(i))P(x,z∣θ)​​(5)

而$J$ 中${\sum }_z{Q}_i(z^{(i)})log\frac{P(x,z|\theta )}{Q_i(z^{(i)})}$就是变量$\frac{P(x,z|\theta )}{Q_i(z^{(i)})}$的期望。

---

可能这里会有点晕。。。。稍微解释下这里。

设Y是随机变量X的函数，Y = g(X)，那么：

若X是离散型变量，它的分布律有$P(X=x_k)=p_k，k=1,2,3,...。$
若${\sum }_{k=1}^{\infty }g(x_k)p_k$绝对收敛，则：

$$E(Y)=E(g(X))=\sum _{k=1}^{\infty }g(x_k)p_k$$

对于上面的式子（5），Y是$\frac{p(x^{(i)},z^{(i)};\theta )}{Q_i(z^{(i)})}$，X对应于$z^{(i)}$，$Q_i(z^{(i)})$是$p_k$。

故：${\sum }_z{Q}_i(z^{(i)})log\frac{P(x,z|\theta )}{Q_i(z^{(i)})}$就是变量$\frac{P(x,z|\theta )}{Q_i(z^{(i)})}$的期望。

---

$l(\theta )\ge J(z,Q)$，那么我们可以通过不断最大化这个下界，来使得$l(\theta )$不断提高，最终达到它的最大值。

其实到这里，E步基本就完成了。

整个E步过程可以看作是对$l(\theta )$求了下界。

对于$Q_i$的选择，有许多种可能，那么哪一种更好呢？不妨假定$\theta$已经给定，那么$l(\theta )$的值就取决于$Q_i(z^{(i)})$和$p(x^{(i)},z^{(i)})$了。通过调整这两个参数使得下界不断上升，以逼近$l(\theta )$的真实值。

那么什么时候算是调整好了呢？当然是当等号成立时，说明调整后的值等价于$l(\theta )$了。

按照这个思路，我们要找到等式成立的条件，根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值：

也就是$X_1=X_2=...=X_k$，进而$g(X_1)=g(X_2)=...=g(X_k)$。

即：$g(x_k)=C$，其中c为常数，并不依赖于$z^{(i)}$。

也就得到：

$$g(X_k)=\frac{p(x^{(i)},z^{(i)}|\theta )}{Q_i(z^{(i)})}=C\text{\hspace{1em}(6)}$$

所以：
C = ∑ z p ( x ( i ) , z ( i ) ∣ θ ) ∑ z Q i ( z ( i ) ) = ∑ z p ( x ( i ) , z ( i ) ∣ θ ) (7)

$$\begin{aligned} C &= \frac{\sum_zp(x^{(i)},z^{(i)}|\theta)}{\sum_zQ_{i}(z^{(i)})} \\ &= \sum_zp(x^{(i)},z^{(i)}|\theta) \tag{7} \end{aligned}$$ C​=∑z​Qi​(z(i))∑z​p(x(i),z(i)∣θ)​=z∑​p(x(i),z(i)∣θ)​(7)

即：$C={\sum }_{z}p(x^{(i)},z^{(i)}|\theta )$。

将该式子带回到（6）中：

$$\frac{p(x^{(i)},z^{(i)}|\theta )}{Q_i(z^{(i)})}=\sum _{z}p(x^{(i)},z^{(i)}|\theta )\text{\hspace{1em}(8)}$$

所以：

Q i ( z ( i ) ) = p ( x ( i ) , z ( i ) ∣ θ ) ∑ z p ( x ( i ) , z ( i ) ∣ θ ) = p ( x ( i ) , z ( i ) ∣ θ ) p ( x i ∣ θ ) = p ( z ( i ) ∣ x ( i ) , θ ) (9)

$$\begin{aligned} Q_{i}(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)}|\theta)}{\sum_zp(x^{(i)},z^{(i)}|\theta)} \\ &= \frac{p(x^{(i)},z^{(i)}|\theta)}{p(x_{i}|\theta)}\\ &= p(z^{(i)}|x^{(i)},\theta) \tag{9} \end{aligned}$$ Qi​(z(i))​=∑z​p(x(i),z(i)∣θ)p(x(i),z(i)∣θ)​=p(xi​∣θ)p(x(i),z(i)∣θ)​=p(z(i)∣x(i),θ)​(9)

至此，我们在固定参数 $\theta$后，$Q_i(z^{(i)})$的计算公式就是后验概率，接下来就是M步，就是在给定$Q_i(z^{(i)})$后，调整$\theta$，去极大化$l(\theta )$的下界$J(z,Q)$。

当$J(z,Q)$收敛时，$l(\theta )$的最大值也迭代出来了。

---

其实，整个EM算法归纳下来理解还是比较容易的：

（1）E-Step：
对于每一个i，计算：
$$Q_i(z^{(i)})=p(z^{(i)}|x^{(i)},\theta )$$

（2）M-Step：
计算：
$$\theta =\underset{\theta }{\mathrm{argmax}}\sum _i^m\sum _z{Q}_i(z^{(i)})log\frac{P(x,z|\theta )}{Q_i(z^{(i)})}$$

---

参考：

1. 《统计学习方法》李航著
2. http://www.cnblogs.com/Determined22/p/5776791.html
3. https://blog.csdn.net/m0_37570854/article/details/88838267
4. https://blog.csdn.net/qq_16000815/article/details/80384024