机器学习基础算法 -- 期望最大（Expectation Maximization）

本文主要记录 EM 相关算法核心公式推导。

迭代公式

EM 算法就是含有隐变量的概率模型参数的极大似然估计或极大后验概率估计方法。

MLE 估算公式为：。EM 算法的难点在于增加了隐变量，导致模型参数不能直接计算求得。

解决方法是采用迭代法，其一般公式为

其中， 为增加的辅助隐变量，且

为当前已知迭代项。

易知，该迭代算法能够实现的前提是极大似然项能单调递增，即以下公式一直成立

证明如下。

另一方面，由联合概率公式可知

其中，

可以看成是 在概率分布为 ​ 下的期望。 由定义可知

从而有

​​ 此外，

上述不等式的结果可由 Jensen 不等式推出。

综合以上各式，有

基本步骤

由前述推导及最终公式可以看出，EM 在迭代过程中主要就是两步操作：

• 期望（Expectation）计算：通过初始或上一步得到的 项计算 在概率分布为 ​ 下的期望；
• 最大化（Maximize）期望：利用极大似然估计最大化的期望得到参数得到 项供下一次迭代使用；

上述算法的停止条件可设定为两次迭代误差小于某个参考值。

需要注意的是 EM 算法依赖于初始值的选择，且算法最终可能会收敛到局部最优值。

Reference

机器学习 (nju.edu.cn)

统计学习方法 (豆瓣) (douban.com)

Expectation–maximization algorithm - Wikipedia