EM算法详细例子+推导

EM算法的详解

（EM算法）The EM Algorithm EM是我一直想深入学习的算法之一，第一次听说是在NLP课中的HMM那一节，为了解决HMM的参数估计问题，使用了EM算法。在之后的MT 中的词对齐中也用到了。在Mitchell的书中也提到EM可以用于贝叶斯网络中。 下面主要介绍EM的整个推导过程。 1. Jensen不等式 回顾优化理论中的一些概念。设f是定义域为实数的函数，如果对于所有的实数x，，那么f是凸函数。当x是向量时，如果其 hessian矩阵H是半正定的（），那么f是凸函数。如果或者，那么称f是严格凸函数。 Jensen不等式表述如下： 如果f是凸函数，X是随机变量，那么 特别地，如果f是严格凸函数，那么当且仅当，也就是说X是常量。 这里我们将简写为。 如果用图表示会很清晰： 图中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。（就像掷硬币一样）。X的期望值就是a和b的中值了，图中可以看到成立。 当f是（严格）凹函数当且仅当-f是（严格）凸函数。 Jensen不等式应用于凹函数时，不等号方向反向，也就是。 2. EM算法 给定的训练样本是，样例间独立，我们想找到每个样例隐含的类别z，能使得p(x,z)最大。p(x,z)的最大似然估计如下：

第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z求联合分布概率和。但是直接求一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。 EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化，我们可以不断地建立的下界（E步），然后优化下界（M步）。这句话比较抽象，看下面的。 对于每一个样例i，让表示该样例隐含变量z的某种分布，满足的条件是。（如果z是连续性的，那么是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。 可以由前面阐述的内容得到下面的公式： （1）到（2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（3）利用了Jensen不等式，考虑到是凹函数（二阶导数小于0），而且 就是的期望（回想期望公式中的Lazy Statistician规则） 设Y是随机变量X的函数（g是连续函数），那么 （1）X是离散型随机变量，它的分布律为，k=1,2,…。若绝对收敛，则有 （2）X是连续型随机变量，它的概率密度为，若绝对收敛，则有

EM算法作业

EM算法作业

EM 算法简单 介绍及应用 EM 算法是当存在数据缺失问题时，极大似然估计（MLE ）的一种常用迭代算法，由于其每次迭代都分两步：E 步，求期望（expectation ）;M 步，求极大（maximization ），所以称之为EM 算法。EM 算法主要适用于以下常见的两种情况的参数估计:（1）观测到的数据不完善；（2）似然函数不是显然的或者函数的形式非常复杂导致难以用极大似然传统方法进行估计。 该报告首先通过简单的实例对EM 算法的原理及其计算方法进行说明，然后简单介绍了EM 算法的的收敛性，最后就EM 算法在GMM 参数估计中的应用进行了详细的说明并通过程序实现迭代得到参数估计. 一.实例分析 设一次实验可能有四个结果，其发生的概率分别 为4 ,41,41,421θθθθ+--其中)1,0(∈θ，现进行了197次试验，四种结果的发生次数分别为75,18,70,34.求θ的MLE. 以4 3 2 1 ,,,y y y y 表示四种结果发生的次数，此时总体分

布为多项分布，故其似然函数 4 3214 321)1()1()-(2 ) 4 ()41()41()421();(y y y y y y y y y L θθθθθθθθθ+-∝+--∝ 由此式求解θ的MLE 比较麻烦，可以考虑用EM 算法添加数据，通过引入两个潜变量2 1 ,z z ，使得求 解比较容易。现假设第一种结果可以分成两部 分，4 1θ-和41 ，令1 z 和1 1 z y -分别表示落入这两部分的次数；再假设第三种结果分 成两部分，其发生的概率分别为4θ和4 1 ，令2 z 和2 3 z y -分别表示落入这两部分的次数。则在完全数据 ) ,(z y 下的对数似然函数 2 1424 2231211) 1( ) 4()41()41()41(),;(y z y z y z z y z y z y z y L +++-+--∝-∝θθθθθ 其对数似然为 ) 1ln()()ln()(),;(2142θθθ-+++=y z y z z y l 虽然在该题目中仅知道y ，不知道z 的值，但是当 y 和θ已知时，得到 )1,(~),21, (~3211θ θθθ+--y b z y b z 下面根据EM 算法分两步进行迭代： E 步：在已有观测数据y 和第i 步估计值) (i θ的条件 下，求基于完全数据的对数似然函数的期望（即

EM算法理论及其应用_杨基栋

2009年11月第15卷第4期 安庆师范学院学报(自然科学版) Jou rn al of A nqing Teachers College(Natural S cience E dition) Nov.2009 Vol.15No.4 EM算法理论及其应用 杨基栋 (华东师范大学金融与统计学院,上海200062) 摘要:E M算法是一种迭代算法,主要用来计算后验分布的众数或极大似然估计,广泛地应用于缺损数据、截尾数据、成群数据、带有讨厌参数的数据等所谓的不完全数据的统计推断问题。在介绍EM算法的基础上,针对E M算法收 敛速度慢的缺陷,具体讨论了加速EM算法:EM B算法和M EM B算法;针对EM算法计算的局限性,给出了EM算法的 推广:GEM和M CEM算法。最后给出了EM的实值实例,结果精确。 关键词:E M算法;极大似然估计;GEM算法;M CE M算法;EM B算法;M EM B算法 中图分类号:O212.8文献标识码:A文章编号:1007-4260(2009)04-0030-06 0引言 在统计领域里,统计计算技术近年来发展很快,它使许多统计方法,尤其是Bay es统计得到广泛的运用。Bay es计算方法有很多,大体上可分为两大类:一类是直接应用于后验分布以得到后验均值或后验众数的估计,以及这种估计的渐进方差或其近似;另一类算法可以总称为数据添加算法,这是近年发展很快而且应用很广的一种算法,它是在观测数据的基础上加一些/潜在数据0,从而简化计算并完成一系列简单的极大化或模拟,该/潜在数据0可以是/缺损数据0或未知参数。其原理可以表述如下:设我们能观测到的数据是Y,H关于Y的后验分布p(H|Y)很复杂,难以直接进行各种统计计算,假如我们能假定一些没有能观测到的潜在数据Z为已知(譬如,Y为某变量的截尾观测值,则Z为该变量的真值),则可能得到一个关于H的简单的添加后验分布p(H|Y,Z),利用p(H|Y,Z)的简单性我们可以对Z的假定作检查和改进,如此进行,我们就将一个复杂的极大化或抽样问题转变为一系列简单的极大化或抽样。EM算法就是一种常用的数据添加算法。 1EM算法及其理论 先考虑一个简单情形。设某元件的失效时间Y关于某个变量x有直线回归关系,假设在一次试验中得到一批观测数据,见右图,/@0表示该种元件的失 效时间对应的值,/o0对应元件的(右)截尾时间 (比实际失效时间要小)。如果直线斜率和截距的估 计值已知,则我们可以在真实数据不小于截尾数据 的前提下,将各个被截尾的失效时间估计出来(譬 如,若E(Y|x)>Z,则用E(Y|x)作为真实数据, 否则取Z作为真实数据),从而得到所谓的/完全数 据0,由此/完全数据0,我们可以对直线斜率和截距 进行估计(如极大似然估计),估计出新的斜率和截 距后,在重新估计各个被截尾的失效时间,得到新的完全数据,如此重复,我们将一个复杂的估计时间替换成一系列简单的估计问题。将之一般化,我们可以给出EM算法。 EM算法是一种迭代方法,最初由Dem pster等于1977年首次提出,主要用来计算后验分布的众数或极大似然估计。近十年来引起了统计学家们的极大兴趣,在统计领域得到广泛应用。这种方法可以广 *收稿日期:2009-05-21 作者简介:杨基栋,女,安徽安庆人,华东师范大学金融与统计学院助理工程师。

EM算法作业

EM 算法简单介绍及应用 EM 算法是当存在数据缺失问题时，极大似然估计（MLE ）的一种常用迭代算法，由于其每次迭代都分两步：E 步，求期望（expectation ）;M 步，求极大（maximization ），所以称之为EM 算法。EM 算法主要适用于以下常见的两种情况的参数估计:（1）观测到的数据不完善；（2）似然函数不是显然的或者函数的形式非常复杂导致难以用极大似然传统方法进行估计。 该报告首先通过简单的实例对EM 算法的原理及其计算方法进行说明，然后简单介绍了EM 算法的的收敛性，最后就EM 算法在GMM 参数估计中的应用进行了详细的说明并通过程序实现迭代得到参数估计. 一.实例分析 设一次实验可能有四个结果， )1,0(∈θ，现进行了197次试验，四种结果的发生次数分别为75,18,70,34.求θ的MLE. 以4321,,,y y y y 表示四种结果发生的次数，此时总体分布为多项分布，故其似然函数 由此式求解θ的MLE 比较麻烦，可以考虑用EM 算法添加数据，通过引入两个潜变量21,z z ，使得求解比较容易。现假设第一种结果可以分成两部分， 令1z 和11z y -分别表示落入这两部分的次数；再假设第三种结果分成两部分，其发生的概率分别为4θ和4 1 ，令2z 和2 3z y -分别表示落入这两部分的次数。则在完全数据),(z y 下的对数似然函数

其对数似然为 )1ln()()ln()(),;(2142θθθ-+++=y z y z z y l 虽然在该题目中仅知道y ，不知道z 的值，但是当y 和θ已知时，得到 )1,(~),21, (~3211θθθθ+--y b z y b z 下面根据EM 算法分两步进行迭代： E 步：在已有观测数据y 和第i 步估计值)(i θ的条件下，求基于完全数据的对数似然函数的期望（即把其中与z 有关的部分积分掉）： ).,;(),()(z y l E y Q z i θθθ= M 步：求),()(i y Q θθ关于θ的最大值)1(+i θ，即找)1(+i θ使得 ). ,(max ),()()()1(i i i y Q y Q θθθθθ =+ 这样就完成了由)(i θ到)1(+i θ的一次迭代。重复上面两步，直至收敛即可得到θ的MLE. 算法的收敛性 算法简单、收敛稳定是EM 算法的最大优点，下面的定理说明EM 算法得到的估计序列是收敛的。 定理1：设)(P θx 为观测数据的似然函数，)(i θ为EM 算法得到的参数估计序列，)()(i x p θ为对应的似然函数序列，则)()(i x p θ是单调递增的，即） （)()1()(i i x p x p θθ≥+. 可见在EM 算法E 步与M 步的交替运算下，都提高了观察数据的似然函数的值。 定理2：设)(ln θx p 为观测数据的对数似然函数，)(i θ为EM 算法的得到的参

em算法

em算法 EM算法也称期望最大化（Expectation-Maximum,简称EM）算法，它是一个基础算法，是很多机器学习领域算法的基础，比如隐式马尔科夫算法（HMM），LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。 1. EM算法要解决的问题 我们经常会从样本观察数据中，找出样本的模型参数。最常用的方法就是极大化模型分布的对数似然函数。 但是在一些情况下，我们得到的观察数据有未观察到的隐含数据，此时我们未知的有隐含数据和模型参数，因而无法直接用极大化对数似然函数得到模型分布的参数。怎么办呢？这就是EM算法可以派上用场的地方了。 EM算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含数据（EM算法的E步），接着基于观察数据和猜测的隐含数据一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐藏数据是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。不过没关系，我们基于当前得到的模型参数，继续猜测隐含数据（EM算法的E步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。 从上面的描述可以看出，EM算法是迭代求解最大值的算法，同时算法在每一次迭代时分为两步，E步和M步。一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。 一个最直观了解EM算法思路的是K-Means算法，见之前写的K-Means聚类算法原理。在K-Means聚类时，每个聚类簇的质心是隐含数据。我们会假设KK 个初始化质心，即EM算法的E步；然后计算得到每个样本最近的质心，并把样本聚类到最近的这个质心，即EM算法的M步。重复这个E步和M步，直到质心不再变化为止，这样就完成了K-Means聚类。 当然，K-Means算法是比较简单的，实际中的问题往往没有这么简单。上面对EM算法的描述还很粗糙，我们需要用数学的语言精准描述。 2. EM算法的推导

em算法

em算法是指期望最大化算法（期望最大化算法，也翻译为期望最大化算法），是一种迭代算法，用于包含潜在变量概率估计的概率参数模型的最大似然估计或最大后验。 在统计计算中，最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。 最大期望算法经过两个步骤交替进行计算: 第一步是计算期望(E)，利用概率模型参数的现有估计值，计算隐藏变量的期望; 第二步是最大化(M)，利用E 步上求得的隐藏变量的期望，对参数模型进行最大似然估计。 M 步上找到的参数估计值被用于下一个E 步计算中，这个过程不断交替进行。 总体来说，EM的算法流程如下: 1.初始化分布参数 2.重复直到收敛: E步骤:估计未知参数的期望值，给出当前的参数估计。 M步骤:重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。 迭代使用EM步骤，直至收敛。 可以有一些比较形象的比喻说法把这个算法讲清楚。比如说食堂

的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。 EM 算法是Dempster，Laind，Rubin 于1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行MLE 估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据，截尾数据，带有噪声等所谓的不完全数据(incomplete data)。 假定集合Z = (X,Y)由观测数据X 和未观测数据Y 组成，X 和Z = (X,Y)分别称为不完整数据和完整数据。假设Z的联合概率密度被参数化地定义为P(X,Y|Θ)，其中Θ表示要被估计的参数。Θ的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的: L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ; EM算法包括两个步骤:由E步和M步组成，它是通过迭代地最大化完整数据的对数似然函数Lc(X;Θ)的期望来最大化不完整数据的

EM算法matlab程序

X=zeros(600,2); X(1:200,:) = normrnd(0,1,200,2); X(201:400,:) = normrnd(0,2,200,2); X(401:600,:) = normrnd(0,3,200,2); [W,M,V,L] = EM_GM(X,3,[],[],1,[]) 下面是程序源码： 打印帮助 function[W,M,V,L] = EM_GM(X,k,ltol,maxiter,pflag,Init) % [W,M,V,L] = EM_GM(X,k,ltol,maxiter,pflag,Init) % % EM algorithm for k multidimensional Gaussian mixture esti mation % % Inputs: % X(n,d) - input data, n=number of observations, d=dimension of variable % k - maximum number of Gaussian components allowed % ltol - percentage of the log likelihood difference between 2 iterations ([] for none) % maxiter - maximum number of iteration allowed ([] for none) % pflag - 1 for plotting GM for 1D or 2D cases only, 0 otherwise ([] for none) % Init - structure of initial W, M, V: Init.W, Init.M, Init.V ([] for none) % % Ouputs: % W(1,k) - estimated weights of GM % M(d,k) - estimated mean vectors of GM % V(d,d,k) - estimated covariance matrices of GM % L - log likelihood of estimates % % Written by % Patrick P. C. Tsui, % PAMI research group % Department of Electrical and Computer Engineering % University of Waterloo, % March, 2006 % %%%% Validate inputs %%%% ifnargin <= 1, disp('EM_GM must have at least 2 inputs: X,k!/n') return elseifnargin == 2, ltol = 0.1; maxiter = 1000; pflag = 0; Init = []; err_X = Verify_X(X); err_k = Verify_k(k); iferr_X | err_k,return;end elseifnargin == 3, maxiter = 1000; pflag = 0; Init = []; err_X = Verify_X(X); err_k = Verify_k(k);

EM算法作业

E M算法作业 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII

EM 算法简单介绍及应用 EM 算法是当存在数据缺失问题时，极大似然估计（MLE ）的一种常用迭代算法，由于其每次迭代都分两步：E 步，求期望（expectation ）;M 步，求极大（maximization ），所以称之为EM 算法。EM 算法主要适用于以下常见的两种情况的参数估计:（1）观测到的数据不完善；（2）似然函数不是显然的或者函数的形式非常复杂导致难以用极大似然传统方法进行估计。 该报告首先通过简单的实例对EM 算法的原理及其计算方法进行说明，然后简单介绍了EM 算法的的收敛性，最后就EM 算法在GMM 参数估计中的应用进行了详细的说明并通过程序实现迭代得到参数估计. 一.实例分析 )1,0(∈θ，现进行了197次试验，四种结果的发生次数分别为75,18,70,34.求θ的MLE. 以4321,,,y y y y 表示四种结果发生的次数，此时总体分布为多项分布，故其似然函数 由此式求解θ的MLE 比较麻烦，可以考虑用EM 算法添加数据，通过引入两个潜变量21,z z ，使得求解比较容易。现假设第一种结果可以分成两部分，其发生 ，令1z 和11z y -分别表示落入这两部分的次数；再假设第三种结果分成两部分，其发生的概率分别为4θ和4 1 ，令2z 和23z y -分别表示 落入这两部分的次数。则在完全数据),(z y 下的对数似然函数 其对数似然为 )1ln()()ln()(),;(2142θθθ-+++=y z y z z y l 虽然在该题目中仅知道y ，不知道z 的值，但是当y 和θ已知时，得到 )1,(~),21, (~3211θθθθ+--y b z y b z 下面根据EM 算法分两步进行迭代：

EM算法简介

最大期望算法（Expectation Maximization Algorithm，又译期望最大化算法），是一种迭代算法，用于含有隐变量（hidden variable）的概率参数模型的最大似然估计或极大后验概率估计。 EM算法 在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。 最大期望算法经过两个步骤交替进行计算： 第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值； 第二步是最大化（M），最大化在E 步上求得的最大似然值来计算参数的值。 M 步上找到的参数估计值被用于下一个E 步计算中，这个过程不断交替进行。 总体来说，EM的算法流程如下： 1.初始化分布参数 2.重复直到收敛： E步骤：估计未知参数的期望值，给出当前的参数估计。 M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。 EM算法简述 迭代使用EM步骤，直至收敛。 可以有一些比较形象的比喻说法把这个算法讲清楚。比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。 EM 算法是Dempster，Laind，Rubin 于1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行MLE 估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据，截尾数据，带有噪声等所谓的不完全数据(incomplete data)。 假定集合Z = (X,Y)由观测数据X 和未观测数据Y 组成，X 和Z = (X,Y)分别称为不完整数据和完整数据。假设Z的联合概率密度被参数化地定义为P(X,Y|Θ)，其中Θ表示要被估计的参数。Θ的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的： L(Θ;X)= log p(X|Θ) = ∫log p(X,Y|Θ)dY ； EM算法包括两个步骤：由E步和M步组成，它是通过迭代地最大化完整数据的对数似然函数Lc(X;Θ)的期望来最大化不完整数据的对数似然函数，其中： Lc(X;Θ) =log p(X,Y |Θ) ； 假设在算法第t次迭代后Θ获得的估计记为Θ(t) ，则在(t+1)次迭代时， E-步：计算完整数据的对数似然函数的期望，记为： Q(Θ|Θ(t)) = E{Lc(Θ;Z)|X;Θ(t)}； M-步：通过最大化Q(Θ|Θ(t) ) 来获得新的Θ。 通过交替使用这两个步骤，EM算法逐步改进模型的参数，使参数和训练样本的似然概率逐