今天，让我们讲一讲一个著名的算法：EM算法（期望最大化算法）。

在讲EM算法之前，先让我们认识一个不等式：Jensen不等式

对于凸函数 $f$, 如果 $X$ 是一个随机变量，那么总有 $E[f(x)]\geq f(EX)$

在这里我们不提供严格证明，提供以下图片方便理解

好了，学会了这个不等式，我们就可以出发了~

EM算法的主体思想是：找到一个下界函数，去逼近原函数，然后通过求下界函数的最大值来迭代求解原函数，类似下图：

接下来我们来看具体的流程

对于任意的训练集 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ ,如果我们用模型 $p(x,z)$ 去拟合，可以得到下面的似然函数：

$$\begin{align} \iota (\theta ) &= \sum _{i=1}^{m}\log p(x;\theta ) \\ &=\sum _{i=1}^{m}\log\sum _{z}p(x,z;\theta ) \end{align}$$

我们令 $Q_i$ 为 $z$ 的某些分布（ $\sum_z Q_i(z)=1$ && $Q_i(z)\geq 0$）,则有

$$\begin{align} \sum _i \log p(x^{(i)};\theta ) &= \sum _i \log \sum _{z^{(i)}}p(x^{(i)},z^{(i)};\theta ) \\ & = \sum _i \log \sum _{z^{(i)}}Q_i(z^{(i)}) \frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \\ & \geqslant \sum _i \sum _{z^{(i)}} Q_i(z^{(i)}) \log \frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \end{align}$$

这里用到了Jensen不等式。因为对数函数是凹函数，所以这里不等号需要反过来。

我们已经找到了原函数的下界函数，现在要做的是去逼近原函数。注意Jensen不等式的取等条件，当 $F(x)=c$ 时等号成立。

所以有， $\frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}=c$ ,也即 $Q_i(z^{(i)})\propto p(x^{(i)},z^{(i)};\theta)$

因为 $Q_i$ 是 $z^{(i)}$ 的分布，所以有：

$$\begin{align} Q_i(z^{(i)}) & = \frac {p(x^{(i)},z^{(i)};\theta)}{\sum _z p(x^{(i)},z;\theta)} \\ & = \frac {p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)} \\ & = p(z^{(i)}|x^{(i)};\theta ) \end{align}$$

将值带入，我们就得到了一个在 $\theta_0$ 处“紧贴”原函数的下界函数。然后，我们去求令该下界函数取值最大的 $\theta_1$

总结一下EM算法：

repeat until convergence {

(E-step)For each i, set $$Q_i(z^{(i)}) = p(z^{(i)}|x^{(i)};\theta )$$ (M-step)Set $$\theta = argmax_\theta \sum _i \sum _{z^{(i)}} Q_i(z^{(i)}) \log \frac {p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$$ }

EM算法的收敛性就不在本文证明，有兴趣的同学可以看CS229的讲义

下面给出两个EM算法的实践：KMeans和GMM