2.14　EM算法

最大期望算法（Expectation-Maximization Algorithm，EM算法），是一类通过迭代进行极大似然估计的优化算法，通常作为牛顿迭代法的替代，用于对包含隐变量或缺失数据的概率模型进行参数估计。

2.14.1　EM算法的基本思想

EM算法的基本思想经过两个步骤交替计算。

（1）计算期望（下文称为“E步”），利用对隐藏变量的现有估计值，计算其极大似然估计值。

（2）最大化（下文称为“M步”），最大化在E步上求得的极大似然值来计算参数的值。

M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

2.14.2　EM算法推导

对于m个样本观察数据，现在想找出样本的模型参数θ，其极大化模型分布的对数似然函数为：

如果得到的观察数据有未观察到的隐含数据，那么极大化模型分布的对数似然函数则为：

因为上式不能直接求出θ，所以采用缩放技巧：

上式用到了Jensen不等式：

并且引入了一个未知的新分布。

此时，如果需要满足Jensen不等式中的等号，所以有：

由于是一个分布，所以满足

综上，可得：

如果，则式（2-90）是我们的包含隐藏数据的对数似然的一个下界。如果能极大化这个下界，则也在尝试极大化对数似然。即需要最大化下式：

简化得：

以上即为EM算法的M步。此外，注意到上式中是一个分布，因此可理解为基于条件概率分布的期望，即为E步。

2.14.3　图解EM算法

考虑到式（2-89）中存在隐变量，直接找到参数估计比较困难，我们通过EM算法迭代求解下界的最大值到收敛为止。EM算法求解示意图如图2-23所示。

在图2-23中，目标模型p（x|θ）复杂，难以求解析解，为了消除隐变量的影响，可以选择一个不包含的模型r（x|θ），使其满足条件。

求解步骤如下。

（1）选取θ1，使得，然后对此时的r求取最大值，得到极值点θ2，实现参数的更新。

（2）重复以上过程到收敛为止，在更新过程中始终满足r≤p。

2.14.4　EM算法流程

输入：观察数据，联合分布p（x，z；θ），条件分布p（z|x；θ），最大迭代次数J。

（1）随机初始化模型参数θ的初值θ0。

（2）设当前迭代次数为j，j从1到J进行迭代：

• E步。计算联合分布的条件概率期望：

• M步。极大化L（θ，θj），得到θj+1

• 如果θj+1收敛，则算法结束，否则继续进行E步迭代。

输出：模型参数θ。