怎么给自己的网站更换域名,wordpress例行维护,中国建筑集团网,网站设计导航栏高度EM算法也称期望最大化(Expectation-Maximum,简称EM)算法#xff0c;它是一个基础算法#xff0c;是很多机器学习领域算法的基础#xff0c;比如隐式马尔科夫算法(HMM)#xff0c; LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。EM算法要解决的问题我们经常会…EM算法也称期望最大化(Expectation-Maximum,简称EM)算法它是一个基础算法是很多机器学习领域算法的基础比如隐式马尔科夫算法(HMM) LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。EM算法要解决的问题我们经常会从样本观察数据中找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。但是在一些情况下我们得到的观察数据有未观察到的隐含数据此时我们未知的有隐含数据和模型参数因而无法直接用极大化对数似然函数得到模型分布的参数。怎么办呢这就是EM算法可以派上用场的地方了。EM算法解决这个的思路是使用启发式的迭代方法既然我们无法直接求出模型分布参数那么我们可以先猜想隐含数据(EM算法的E步)接着基于观察数据和猜测的隐含数据一起来极大化对数似然求解我们的模型参数(EM算法的M步)。由于我们之前的隐藏数据是猜测的所以此时得到的模型参数一般还不是我们想要的结果。不过没关系我们基于当前得到的模型参数继续猜测隐含数据(EM算法的E步)然后继续极大化对数似然求解我们的模型参数(EM算法的M步)。以此类推不断的迭代下去直到模型分布参数基本无变化算法收敛找到合适的模型参数。从上面的描述可以看出EM算法是迭代求解最大值的算法同时算法在每一次迭代时分为两步E步和M步。一轮轮迭代更新隐含数据和模型分布参数直到收敛即得到我们需要的模型参数。一个最直观了解EM算法思路的是K-Means算法见之前写的K-Means聚类算法原理。在K-Means聚类时每个聚类簇的质心是隐含数据。我们会假设K个初始化质心即EM算法的E步然后计算得到每个样本最近的质心并把样本聚类到最近的这个质心即EM算法的M步。重复这个E步和M步直到质心不再变化为止这样就完成了K-Means聚类。当然K-Means算法是比较简单的实际中的问题往往没有这么简单。上面对EM算法的描述还很粗糙我们需要用数学的语言精准描述。EM算法的推导对于m个样本观察数据找出样本的模型参数极大化模型分布的对数似然函数如下如果我们得到的观察数据有未观察到的隐含数据此时我们的极大化模型分布的对数似然函数如下上面这个式子是没有 办法直接求出的。因此需要一些特殊的技巧我们首先对这个式子进行缩放如下上面第(1)式引入了一个未知的新的分布第(2)式用到了Jensen不等式或者说由于对数函数是凹函数所以有:此时如果要满足Jensen不等式的等号则有由于是一个分布所以满足从上面两式我们可以得到如果, 则第(2)式是我们的包含隐藏数据的对数似然的一个下界。如果我们能极大化这个下界则也在尝试极大化我们的对数似然。即我们需要最大化下式去掉上式中为常数的部分则我们需要极大化的对数似然下界为上式也就是我们的EM算法的M步那E步呢注意到上式中是一个分布因此可以理解为基于条件概率分布的期望。至此我们理解了EM算法中E步和M步的具体数学含义。EM算法流程现在我们总结下EM算法的流程。输入观察数据联合分布条件分布最大迭代次数J。1) 随机初始化模型参数的值2) for j from 1 to J开始EM算法迭代 a) E步计算联合分布的条件概率期望 b) M步极大化得到 c) 如果已收敛则算法结束。否则继续回到步骤a)进行E步迭代。输出模型参数。EM算法收敛性思考EM算法的流程并不复杂但是还有两个问题需要我们思考1) EM算法能保证收敛吗2) EM算法如果收敛那么能保证收敛到全局最大值吗首先我们来看第一个问题, EM算法的收敛性。要证明EM算法收敛则我们需要证明我们的对数似然函数的值在迭代的过程中一直在增大。即由于令上两式相减得到在上式中分别取为和并相减得到要证明EM算法的收敛性我们只需要证明上式的右边是非负的即可。由于使得极大因此有:而对于第二部分我们有其中第(4)式用到了Jensen不等式只不过和第二节的使用相反而已第(5)式用到了概率分布累积为1的性质。至此我们得到了证明了EM算法的收敛性。从上面的推导可以看出EM算法可以保证收敛到一个稳定点但是却不能保证收敛到全局的极大值点因此它是局部最优的算法当然如果我们的优化目标是凸的则EM算法可以保证收敛到全局最大值这点和梯度下降法这样的迭代算法相同。至此我们也回答了上面提到的第二个问题。
