EM算法

1.基础知识

1.1.高斯混合模型

高斯混合模型是有如下形式的概率分布模型：

其中 为混合系数, , , ，多元变量 , 为第 个高斯混合成分的参数。

假设观测数据 由 个组分的高斯混合模型生成。

高斯混合分布的对数最大化似然函数为:

对数里面有加和，无法直接通过求偏导解方程的方法求取最大值。
可以用EM算法解决这种难以计算的问题，EM算法是一种近似逼
近的迭代计算方法。

1.2.全概率公式

对于任一事件 ,若有互不相容的事件 且 ,则事件 的概率可用下式计算：

上式称为全概率公式。

1.3.Jensen不等式

如果 是凸函数, 是随机变量，那么 ,如果 是凹函数, 是随机变量，那么 ,如果 是严格凹或凸函数, 那么 当且仅当 ,也就是 是常量。如下图：

2.EM算法原理及推导

实际问题中可能有一些数据是我们无法观测到的，假设观测数据,缺失数据,观测数据与缺失数据组合成完整数据,模型的参数 有待估计。其中缺失数据 由 个分布组成，这 个分布的参数可能不同，每个观测数据 来自于这 个分布其中之一。这就造成观测数据下的似然函数难以求得解析解，即 难以求解。但是完全数据下的似然函数 容易求解，观测数据条件下的隐变量概率 容易求得。

EM算法

对于观测数据 样例间独立,我们想找到每个样例隐含的类别(分布) ，能使得 最大.对于每个样例 假设 是关于隐含变量 的概率分布，则 .比如要将班上学生按身高聚类，假设隐藏变量 是性别（男女的身高分布，即连续的高斯分布）。

根据Jensen不等式，想要等式成立，有如下条件:

可以推出：

则：

即 为在给定 情况下 属于分类 的概率。将 带入可得：

上式中第二项与 无关为常数项（熵），令：

可得最大化似然函数等同于：

EM算法流程

由以上推导可知EM算法通过迭代求 的最大似然估计，每次迭代步骤如下：

(1)选择参数的初始值 开始迭代

(2)E步（求期望）:

(3)M步：最大化第二步的期望值，然后对参数求偏导等于0后求得下一步迭代的参数:

(4)重复E步和M步直至：

停止迭代，返回 .

EM算法是利用下边界逼近真实值，如下图：

3.EM算法收敛性

观测数据的似然函数:

令

则对数似然函数可以写成：

由于 使 达到极大，所以有

第二项：

因此 是单调递增的，且有上界，因此收敛。

4.EM算法在高斯混合模型中的应用

高斯混合模型在第一节中已经提过，下面以单变量为例。

明确隐变量，写出完整的对数似然函数

完整数据可表示为

完整数据的似然函数可表示为：

E-步

M-步

多元高斯混合模型

与单元求解类似（注意向量和矩阵求导的细节即可）

参考

1. 周志华 《机器学习》
2. 詹森不等式（Jensen's inequality）
3. Jensen's inequality
4. （EM算法）The EM Algorithm
5. 如何感性地理解EM算法？
6. 怎么通俗易懂地解释EM算法并且举个例子?