EM算法

EM算法

EM算法基本思想

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

​ 最大期望算法基本思想是经过两个步骤交替进行计算：

​ 第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值

​ 第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。

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

EM算法推导

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

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

由于上式不能直接求出，采用缩放技巧：

上式用到了Jensen不等式：

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

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

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

综上，可得：

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

简化得：

以上即为EM算法的M步，可理解为基于条件概率分布的期望。以上即为EM算法中E步和M步的具体数学含义。

图解EM算法

​ 考虑上一节中的（a）式，表达式中存在隐变量，直接找到参数估计比较困难，通过EM算法迭代求解下界的最大值到收敛为止。

在这里插入图片描述

​ 图片中的紫色部分是我们的目标模型，该模型复杂，难以求解析解，为了消除隐变量的影响，我们可以选择一个不包含的模型，使其满足条件。

求解步骤如下：

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

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

EM算法流程

输入：观察数据，联合分布，条件分布，最大迭代次数

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

2）：

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

​ b） M步。极大化，得到:

​ c） 如果收敛，则算法结束。否则继续回到步骤a）进行E步迭代。

输出：模型参数。