EM算法（Expectation Maximization）可以解决的问题示例：
- GMM和HMM的参数估计（统计学习方法 第9、10章）
- Mitchell书中提到可以用于贝叶斯网络
问题定义
给定的训练样本是$\brace{x^{(1)},x^{(2)},\cdots,x^{(m)} }$，样本间独立，我们想找到每个样本隐含的类别$z$，能使得$p(x,z)$最大。$p(x,z)$的最大似然估计如下：
\[\begin{aligned} \ell(\theta) & = \sum_{i=1}^m \log p(x;\theta) \\ &=\sum_{i=1}^m \log \sum_z p(x,z;\theta). \end{aligned}\]第一步是对极大似然取对数，第二步是对每个样例的每个可能类别$z$求联合分布概率和。但是直接求$\theta$一般比较困难，因为有隐藏变量$z$存在，但是一般确定了$z$后，求解就容易了。
EM是一种解决存在隐含变量优化问题的有效方法。既然不能直接最大化$\ell(\theta)$，但可以不断地建立$\ell$的下界（E步），然后优化下界（M步）。
推导思路
利用$\log$的凹函数性质，把分子分母都乘以$z$的概率变成期望来套上Jensen不等式，推导出似然的下界，然后不断优化下界来逼近极大值。
\[\begin{align} \sum_i \log p(x^{(i)};\theta) &= \sum_i \log\sum_{z^{(i)}} p(x^{(i)},z^{(i)};\theta) \tag{1} \\ &= \sum_i \log\sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)},z^{(i)};\theta)} {Q_i(z^{(i)})} \tag{2} \\ &\ge \sum_i \sum_{z^{(i)}} Q_i(z^{(i)}) \log\frac{p(x^{(i)},z^{(i)};\theta)} {Q_i(z^{(i)})} \tag{3} \end{align}\]从$(2)$到$(3)$利用了Jensen不等式，若等式成立，需要随机变量为常数，可以进一步推导得到$Q_i(z^{(i)})$：
\[\begin{aligned} Q_i(z^{(i)}) &= \frac{p(x^{(i)},z^{(i)};\theta)}{\sum_z p(x^{(i)},z^{(i)};\theta)} \\ &= \frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)} \\ &= p(z^{(i)} | x^{(i)};\theta) \end{aligned}\]EM算法
循环重复直到收敛：
（E步）对于每一个样本$i$，计算
\[Q_i(z^{(i)}) := p(z^{(i)} | x^{(i)};\theta)\]（M步）计算
\[\theta := \arg\max_\theta \sum_i\sum_{z^{(i)}} Q_i(z^{(i)}) \log\frac{p(x^{(i)},z^{(i)};\theta)} {Q_i(z^{(i)})}\]代码示例：求解混合高斯模型参数。
参考
- PRML Chapter 9
- 《统计学习方法》李航, EM算法及其推广
- http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html