期望最大化（Expectation Maximization）算法介绍
一. 前言
期望最大化（Expectation Maximization）算法（EM算法）在实际的应用中受到的关注不是特别的重，但是在学术中EM算法是其它很多算法的基础，如隐马尔科夫算法（HMM），LDA主题模型的变分推断等等。所以，理解EM算法对其它算法的学习还是很重要的。本文是对期望最大化算法（EM算法）做一个总结。
概率模型有时既含有观测变量，又含有隐变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法或贝叶斯估计法估计参数模型。但是，当模型含有隐变量或者含有缺失值的时候，就不能简单地使用这些方法估计了。EM算法就是一个在数据集中有缺失值或者含有隐变量的时候能有效的计算最大似然估计的迭代过程。
EM算法包含两个步骤，E步和M步。E步也就是我们求期望的步骤，M步将E步所求的期望最大化，重复E步和M步直到收敛，也就是我们估计的模型参数不再发生变化或者变化幅度很小。这就是EM算法的基本概括，下面我们来详细的介绍EM算法。
二. EM算法描述
输入：观测数据，联合分布
，条件分布
，其中y是隐变量；
输出：模型参数；
（1）随机初始化参数的初值；
（2）重复（a）和（b）直到模型参数收敛：
（a）E步：记为第
次迭代参数
的估计值，在第
次迭代的E步，计算：
期望：
（b）M步：最大化期望，得到
：
以上就是EM算法的算法流程，接下来我们详细的推到EM算法。
三. EM算法分析
首先要明确我们的目标是给定观测数据，我们求观测概率最大的时的模型参数
，所以我们可以用最大似然估计法，极大化模型分布的对数似然函数，如下：
我们取如下，并引入隐变量y：
由于上式并没有一个很好的闭合解，所以上式根本就不好优化，没有办法求出我们的目标，所以我们使用了一些技巧，在介绍技巧之前我们向介绍一下Jensen不等式。
Jensen不等式：如果是定义在区间
上的凸函数，如果
，
且
时，则：
证明如下：
所以，即
其中（1）和（2）用到了凸函数的定义：
介绍完了jensen不等式，接下来我们继续介绍EM算法。我们谈到求时用到了一些技巧，如下：
其中，由jensen不等式可知，对任意和
都有：
且
在中，
是上一次迭代的参数，所以
是一个定值，从而
在观测样本给定时是一个常数，我们的目标是最大化
时的参数取多少并不在意最大值取多少，所以我们可以简化
为
，而
可以理解为
基于条件概率分布
的期望。
有一个有趣的性质如下：
所以，由上面可得到，是
的下界，我们只要不断的使
的最大值增大，就可以使
不断的增大。所以此时我们的目标就是最大化
，找到一个参数
使得：
又由于是
的下界，所以：
所以由上面的式子可以看出确实是一个比
好的参数，接下来通过一步一步的迭代就可以使
到达最大值点，从而使
到达局部最大值点。
四. EM算法图形解释
EM算法用图形来解释如下图：
由上图可知，当
时，
。EM算法目标是找到
使得函数
最大化，这时由于
，函数
的增加，保证对数似然函数
在每次迭代中也是增加的。EM算法在点
会重新计算函数
，进行下一次迭代。在这个过程中，对数似然函数
不断增大，从而到达局部最大值，但EM算法不能保证找到全局最大值。
五. EM算法的收敛性
EM算法提供一种近似计算含有隐变量概率模型的极大似然估计的方法。EM算法的流程并不复杂，但是关于EM算法我们不得不思考一下EM算法能够保证收敛吗？
接下来我们就来讨论一下关于EM算法的收敛性。
要证明EM算法能收敛到极大值，即证明单调递增且有上界，由于我们的样本为有限个样本，所以
一定使有上界的。此时我们证明
单调递增即可，即证明下式成立：
即证明：
为了证明方便，上式用向量形式表示，如下：
，
证明上式如下：
由于
对上式两边取对数有：
由前面的讨论可知：
令：
于是对数似然函数可以写成：
将上式中分别取
和
，然后相减得：
要证明，只需证明上式右边大于等于0即可；
由于前面已经证明使
达到极大，所以有：
对于右边第二项：
（jensen不等式）
所以，成立，从而
，即可证EM算法的收敛性。
从上面的讨论可以看出，EM算法可以保证收敛到一个极大值点，但却不不能保证收敛到全局的最大值点，因此EM算法是一个局部最优算法。所以在应用中，EM算法的初值的选择变得非常的重要，常用的办法是选取几个不同的初值进行迭代，然后对得到的各个估计值加以比较，从中选择最好的。
以上就是对EM算法的总结。
六. 参考文献
（1）《统计学习方法》第9章