EM算法理解

一、准备知识：

1.贝叶斯公式：

贝叶斯公式是用来确定事件A在事件B发生的条件下发生的概率，所以贝叶斯公式又称为最大后验概率公式，公式表示为：

http://s14/bmiddle/002YDHC3zy6KR3ALQmxed&690            （1-1）

其中Pr（A）为A的先验概率，Pr（A|B）为在B发生的条件下A发生的概率。

2.高斯分布：

高斯分布，又称正态分布，对于一个随机变量X若其分布如下图所示，则称其分布为高斯分布。其中μ和σ为分布的参数，分别为高斯分布的期望和方差。当有确定值时，p(x)也就确定了，特别当μ=0，σ^2=1时，X的分布为标准正态分布。

http://s5/bmiddle/002YDHC3zy6KR3Bvk1ed4&690

高斯分布的主要特征：

 1，集中性：正态分布的高峰位于正中央，即均数所在的位置。

 2，对称性：正态曲线以均数为中心，左右对称，曲线两端永远不与横轴相交。

 3，均匀变动性：正态曲线由均数所在处开始，分别向左右两侧逐渐均匀下降。

 4，正态分布有两个参数，即期望μ和标准差σ，可记作N(μ,σ):期望决定正态曲线的中心位置，标准差σ决定正态曲线的陡峭或扁平程度。σ越小，曲线越陡峭；σ越大，曲线越扁平。

3.拉格朗日乘数法：

拉格朗日乘数法是一种处理单变量带有一个或多个约束条件下的极值问题。通过化有约束条件极值化为无约束条件极值，通过求偏导来求解条件极值。

设给定二元函数z=ƒ(x,y)和附加条件φ(x,y)=0，为寻找z=ƒ(x,y)在附加条件下的极值点，

先做拉格朗日函数L(x,y)=ƒ(x,y)+λφ(x,y)，其中λ为参数。求L(x,y)对x 和y 的一阶偏导数，令它们等于零，并与附加条件联立，即

L＇x(x,y)=ƒ＇x(x,y)+λφ＇x(x,y)=0，

L＇y(x,y)=ƒ＇y(x,y)+λφ＇y(x,y)=0，

φ(x,y)=0

由上述方程组解出x，y 及λ，如此求得的(x,y)，就是函数z=ƒ(x,y)在附加条件φ(x,y)=0下的可能极值点。

4.相对熵：

相对熵（relative entropy）又称为KL散度（Kullback–Leibler divergence，简称KLD），信息散度（information divergence），信息增益（information gain）相对熵是两个概率分布非对称性的度量。

设p(x)和q(x)为随机变量X 的两个不同的分布密度，则他们的相对熵定义为：

http://s7/bmiddle/002YDHC3zy6KR3CmMvQ06&690                 （1-2）

性质：1.相对熵是不对称的；

      2.相对熵不满足三角距离公式。

二、EM算法简介：

EM算法是一种经典最大似然的方法，主要用于解决样本数目不足或似然函数中含有参数的方法。

下面用图描述这个系统，能够更加明确：

http://s1/bmiddle/002YDHC3zy6KR3DahGw90&690

上图为一个EM算法的示例其中：

已知数据包括：

1.      系统模型是已知的，系统模型可以简单的理解为系统的概率分布，如高斯混合模型模型等；

2.      能观察要的一部分输出数据，我们称之为样本数据。

未知数据包括：

1.      模型的参数，在高斯混合模型中有均值向量和协方差矩阵等；

2.      未知的一部分参数。

要从样本数据中准确求取模型的参数是EM算法的主要目的。

三、EM算法理论公式：

设X为观测变量，Z为隐形变量，http://s7/bmiddle/002YDHC3zy6KR3E2bgq76&690为模型参数，P为概率密度函数，则有_【注1】：

http://s7/bmiddle/002YDHC3zy6KR3EJFBka6&690   （3-1）

其中q（Z）为z的概率密度函数。

等式两边同时乘以q（Z）并对Z求和，可得：

http://s2/bmiddle/002YDHC3zy6KR3GU3Rvc1&690（3-2）

由于Z与http://s1/bmiddle/002YDHC3zy6KR3Ia4AE40&690则：

http://s13/bmiddle/002YDHC3zy6KR3JNHTS5c&690     （3-3）

EM算法的结果是使得似然函数最大化，有相对熵可得上式第二项大于0，因此上式第一项决定了似然函数的下界，EM算法的思想就是不断提高似然函数的下界使得似然函数收敛的过程。

将式（3-3）等式右边两项化简可得：

http://s6/bmiddle/002YDHC3zy6KR3KUrpb85&690                            （3-4）

http://s15/bmiddle/002YDHC3zy6KR3McjD03e&690                            （3-5）

则式（3-3）可以化简为：

http://s10/bmiddle/002YDHC3zy6KR3NMJgl19&690                  （3-6）

下面分析EM算法的具体步骤：

E步：固定一个http://s1/bmiddle/002YDHC3zy6KR3Rc85G50&690最大。

分析：由于Z与http://s13/bmiddle/002YDHC3zy6KR3YDKX26c&690

M步：固定一个q（Z）（通过E步求得的），求一个http://s4/bmiddle/002YDHC3zy6KR42a1Uv43&690最大化，

分析：由E步已知http://s5/bmiddle/002YDHC3zy6KR43ulYU14&690的值，则

http://s13/bmiddle/002YDHC3zy6KR44Yd5yac&690

上式中后两项相对于http://s11/bmiddle/002YDHC3zy6KR49kJgm5a&690，将求得的最大值代入E步，继续迭代，直到两次求解的值差别小于给定阈值。