今天，让我们讲一讲一个著名的算法：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
