EM算法

EM算法是一种迭代算法，用于含有隐变量(hidden variable)的概率模型参数的极大似然估计，或极大后验概率估计。
EM算法的每次迭代由两步组成：

• E步，求期望(expectation)；
• M步，求极大( maximization )，
  所以这一算法称为期望极大算法(expectation maximization algorithm)，简称EM算法。

一、EM算法的引入

EM算法

image.png

Q函数

image.png

使用EM算法的栗子：三硬币模型

image.png

该问题没有解析解，EM迭代法
EM方法：

image.png

EM算法的导出

通过近似求解观测数据的对数似然函数的极大化问题来导出EM算法，由此可以清楚地看出EM算法的作用。面对一个含有隐变量的概率模型，目标是极大化观测数据(不完全数据)Y关于参数theta 的对数似然函数，即

极大化（不完全数据）Y关于参数θ的极大似然函数

image.png

难点：有未观测数据，包含和的对数

EM通过迭代逐步近似极大化L(θ)，希望

image.png

考虑两者的差：

image.png
利用Jensen不等式得到其下界： image.png

EM算法的直观解释

image.png

图中上方曲线为L(theta)，下方曲线为B(theta, theta(i))，为对数似然函数L(theta)的下界，且在 theta=theta(i)处相等。EM算法找到下一个点theta(i+1)使函数B(theta, theta(i))极大化，也使函数Q(theta, theta(i))极大化。函数B的增加，保证对数似然函数L在每次迭代中也是增加的。EM算法在点theta(i+1)重新计算Q函数值，进行下一次迭代。在这个过程中，对数似然函数L不断增大。从图可以推断出EM算法不能保证找到全局最优值。

3、EM算法在非监督学习中的应用

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

二、EM算法的收敛性

EM算法提供一种近似近似含有隐变量概率模型的极大似然估计的方法。最大优点：简单性和普适性。

EM算法收敛性定理

image.png
image.png

EM算法的收敛性包含关于对数似然函数序列L的收敛性和关于参数估计序列theta的收敛性两层意思，前者并不蕴涵后者。此外，定理只能保证参数估计序列收敛到对数似然函数序列的稳定点，不能保证收敛到极大值点。所以在应用中，初值的选择变得非常重要，常用的办法是选取几个不同的初值进行迭代，然后对得到的各个估计值加以比较，从中选择最好的。

三、EM算法在高斯混合模型学习中的应用

1、高斯混合模型

image.png

2、高斯混合模型参数估计的EM算法

假设观测数据由高斯混合模型生成：

image.png

用EM算法估计参数

（1） 明确隐变量。写出完全数据的对数似然函数

image.png

• 完全数据

  
  image.png

• 似然函数

  
  image.png

• 完全数据的对数似然函数为

  
  image.png
  

  （2） EM算法的E步:确定Q函数

  
  image.png

（3） 确定EM算法的M步

image.png

采用求导的方法

image.png

高斯混合模型参数估计的EM算法

image.png

四、EM算法的推广

EM算法还可以解释为：

• F函数(F function)的极大-极大算法(maximization-maximization algorithm)，
• 广义期望极大(generalized expectation maximization, GEM)算法。

1、F函数的极大-极大算法

F函数

image.png image.png
image.png image.png image.png

2、GEM算法

image.png image.png image.png