机器学习22：概率图--EM算法与GMM(高斯混合模型)

1，EM算法：

当概率图模型依赖于无法观测的隐藏变量无法单纯用MLE或者MAP。

EM算法(Expectation Maximization Algorithm, 最大期望算法)是一种迭代类型的算法，是一种在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。

EM算法（无监督算法）与K-means算法(无监督算法)相似，都是一个不断迭代优化的过程。K-means算法流程是首先初始化k个中心点，然后聚类成k个类，迭代优化这k个中心点，聚k个类……。

1.1，EM算法流程：

1），初始化隐藏变量的分布参数；

重复下列两个操作直到收敛：

2），E步骤：估计隐藏变量的概率分布期望函数；

3），M步骤：根据期望函数重新估计分布参数。

1.2，EM算法的似然函数：

给定的m个训练样本{x(1),x(2),...,x(m)}，样本间独立，找出样本的模型参数θ，极大 化模型分布的对数似然函数如下：

假定样本数据中存在隐含数据z={z(1),z(2),...,z(k)}，此时极大化模型分布的对数似然函数如下：

进一步地：利用Jensen不等式的性质

其中，Jensen不等式为，当函数f是凸函数时，

最终的优化目标为：

1.3，EM算法的一个实例：

假定样本数据x={x,x,...,x}，联合分布p(x,z;θ)，条件分布p(z|x;θ)，最大迭代次数J。具体地，EM算法的三步分别为：

1），初始化：随机初始化模型参数θ的初始值θ~。

2），迭代过程：

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

M步：极大化L函数，得到θ_j+1

迭代的中止条件：如果θ_j+1已然收敛，则算法结束，输出最终的模型参数θ，否则继续迭代处理。

事实上，隐变量估计问题也可以通过梯度下降等优化算法求解，但由于求和的项数将随着因变量的数目以指数级上升，会给梯度计算带来麻烦；而EM算法则可看作一种非梯度优化算法。

1.4，EM算法的收敛性：

证明EM算法的收敛性，只需证明似然函数的值在迭代增加即可，即：

证明如下：

2，高斯混合模型 (Gaussian misturemodel，GMM)：

EM算法可以用于生成模型的非监督学习，生成模型由联合概率分布P(X,Y)表示，可以认为非监督学习训练数据是联合概率分布产生的数据，X是观测变量，Y是未观测变量。

EM算法是最常见的隐变量估计方法，比如，EM算法的一个重要应用是高斯混合模型的参数估计，高斯混合模型应用广泛，通常情况下，EM算法是学习高斯混合模型的有效方法。

2.1，GMM解决的问题：

随机选择1000名用户，测量用户的身高；若样本中存在男性和女性，身高分别 服从高斯分布N(μ1,σ1)和N(μ2,σ2)的分布，试估计参数:μ1,σ1,μ2,σ2。如果样本是混合而成的，不能明确的区分开（假设无法观测到性别这个属性），那么就没法直接使用极大似然估计来 进行参数的估计。

可见，GMM模型由多个高斯模型线性叠加混合而成：

特别地，GMM模型用于聚类任务中，就有了高斯混合聚类模型。

2.2，GMM的参数估计-EM算法：

下面分五步详细阐述使用EM算法对高斯混合模型进行参数估计：

现在，你终于发现了EM算法与梯度下降算法何其相似呀，随机化一个初始值，然后迭代优化该初始值参数，最终参数收敛到一个最优参数的位置。因此，EM算法本质上是一个类似于梯度下降算法的参数估计算法或者参数优化算法。

3，code：

这里给出github仓库地址。

# https://github.com/Jesselinux/Mining-Algorithms