人工智能–EM算法

人工智能之EM算法

前言:人工智能机器学习有关算法内容,请参见公众号“科技优化生活”之前相关文章。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下EM算法。 ^_^

参数估计问题需要在x-y坐标系中找一个曲线的极值,然而曲线函数不能直接求导,因此之前介绍的GBM[请参见人工智能(51)]和GBDT[请参见人工智能(52)]等梯度下降法不再适用了。于是人们想到固定一个变量后,另外一个可以通过求导得到,因此可以使用坐标上升法,一次固定一个变量,对另外的求极值,最后逐步逼近极值。这就是今天要跟大家介绍的EM算法

EM算法是一种迭代算法,1977年由Dempster,Laind,Rubin提出,用于含有隐变量(Hidden Variable)的概率模型参数的极大似然估计最大后验估计,其中概率模型依赖于无法观测的隐藏变量。EM算法可以从非完整数据集中对参数进行 MLE估计,是一种非常实用的学习算法。

EM算法是一个基础算法,是很多机器学习领域算法的基础,比如隐式马尔科夫算法(HMM),LDA主题模型的变分推断等。它可以广泛地应用于处理缺损数据,截尾数据,带有噪声等所谓的不完全数据。

EM算法概念:

如果使用基于最大似然估计的模型,模型中存在隐性变量或数据缺失,就不能直接使用最大似然估计方法,于是EM算法就开始粉墨登场了。

EM算法(Expectation Maximization Algorithm)指的是最大期望算法,又译成期望最大化算法。它是一种迭代算法,在统计学中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计。

EM算法解决原函数的MLE很可能求不出问题,可能是函数太复杂或数据缺失等引起。可以用这个缺失数据的期望值来代替缺失的数据,而这个缺失的数据期望值和它的概率分布有关。那么通过对似然函数关于缺失数据期望的最大化,来逼近原函数的极大值。

EM算法本质:

EM算法本质就是这样的:假设估计知道A和B两个参数,在开始状态下二者都是未知的,并且知道了A的信息就可以得到B的信息,反过来知道了B也就得到了A。可以考虑首先赋予A某种初值,以此得到B的估计值,然后从B的当前值出发,重新估计A的取值,这个过程一直持续到收敛为止。

EM算法描述:

假定集合Z = (X,Y)由观测数据 X 和未观测数据(隐变量数据)Y 组成,X 和Z = (X,Y)分别称为不完整数据(incomplete-data)和完整数据(complete-data)-X和Y连在一起才成为完整数据。

假设Z的联合概率密度被参数化地定义为P(X,Y|Θ),其中Θ表示要被估计的参数。Θ的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的:

L(Θ;X)= log p(X|Θ) = ∫logp(X,Y|Θ)dY ----(1)

EM算法包括两个步骤:由E步M步组成,它是通过迭代地最大化完整数据的对数似然函数Lc(X;Θ)的期望来最大化不完整数据的对数似然函数,其中:

Lc(X;Θ)=log p(X,Y |Θ) ----(2)

假设在算法第t次迭代后Θ获得的估计记为Θ(t) ,则在(t+1)次迭代时,

E-步:计算完整数据的对数似然函数的期望,记为:

Q(Θ|Θ(t)) = E----(3)

M-步:通过最大化Q(Θ|Θ(t) ) 来获得新的Θ 。

通过交替使用这两个步骤,EM算法逐步改进模型的参数,使参数和训练样本的似然概率逐渐增大,最后终止于一个极大点。直观地理解EM算法,它也可被看作为一个逐次逼近算法:事先并不知道模型的参数,可以随机的选择一套参数或者事先粗略地给定某个初始参数λ0 ,确定出对应于这组参数的最可能的状态,计算每个训练样本的可能结果的概率,在当前的状态下再由样本对参数修正重新估计参数λ,并在新的参数下重新确定模型的状态,这样通过多次迭代,循环直至某个收敛条件满足为止,就可以使得模型的参数逐渐逼近真实参数。

EM算法主要目的是提供一个简单的迭代算法计算后验密度函数

注: 公式(3)是EM算法的核心,称为Q函数。

简而言之,EM算法实质是:

1)E步:固定模型参数的值,优化隐含数据的分布;

2)M步:固定隐含数据分布,优化模型参数的值;

3)交替将极值推向最大。

EM推导简介:

EM算法公式推导过程非常复杂。个人认为,理解EM算法思想远比公式推导重要。

大致介绍一下推导过程:

1)写出带有隐变量的似然函数;

2)利用Jensen不等式,取到该似然函数的下界,并确定隐变量的分布;

3)利用已知的隐变量分布去更新参数,使用MLE更新参数;

4)极大似然估计是单调增加的,因此结果最终收敛到某个固定极值。

EM算法步骤:

1.计算期望(E),利用概率模型参数的现有估计值,计算隐藏变量的期望;

2.最大化(M),利用E 步上求得的隐藏变量的期望,对参数模型进行最大似然估计。

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

EM算法具体步骤如下:

1)初始化分布参数。

2)重复直到收敛:

a) E步骤:估计未知参数的期望值,给出当前的参数估计。

b) M步骤:重新估计分布参数,以使得数据的似然性最大,给出未知变量的期望估计。

EM算法结果

EM算法不一定能保证获得全局最优解,但如果我们优化的目标函数是一个凸函数,那么一定能保证得到全局最优解。否则可能获得局部最优解。因为如果优化的目标函数有多个峰值点,则如果优化到某个不是最高的峰值点处,则会无法再继续优化下去,这样获得的是局部最优解。

EM算法优点:

1)算法简单;

2)算法稳定;

3)适用面广。

EM算法缺点:

1)容易陷入局部最优,不一定能保证获得全局最优解;

2)算法对初值选取比较敏感。

EM算法应用:

EM最大期望算法经常用在机器学习和计算机视觉的数据聚类领域。EM算法的应用范围很广,基本机器学习需要迭代优化参数的模型在优化时都可以使用EM算法。

结语:

EM算法是一个迭代算法,是很多机器学习领域算法的基础。1977年由Dempster等人提出,用于含有隐变量(Hidden Variable)的概率模型参数的极大似然估计或最大后验估计。EM算法从非完整数据集中对参数进行极大似然估计,算法每次迭代包含两步:E步-求期望;M步-求极大化。EM算法是一种非常实用的学习算法,应用范围很广,基本机器学习需要迭代优化参数的模型在优化时都可以使用EM算法。

------以往文章推荐-----

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180507G00SCM00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券