《EM算法简介分析综述》8000字

EM算法简介分析综述目录TOC\o"1-2"\h\u24183EM算法简介分析综述 1297441.1算法概述 1234471.2最大似然估计 2302981.3Jensen不等式 356041.4EM算法推导 4250361.5EM算法的改进 589721.5.1改进E步 5192781.5.2改进M步 6157951.6算法步骤 10223911.7EM算法估计GMM参数 10245801.7.1混合模型 1027541.7.2单高斯模型 10111441.7.3高斯混合模型 111.1算法概述EM(expectation-maximization)算法，即期望最大化算法。最大期望算法是一种利用极大似然估计求取参数的优化参数算法。其最大的特点是可以进行极大似然的估计非完整的数据集中的参数，主要应用于处理截尾数据，残缺数据和一些被污染的数据来说是效果突出的。通过以上描述，我们可以得知EM算法的几个优点，EM算法本身简单，收敛稳点，可以估计非完整数据。但是也会带来一些问题，比如收敛速度较慢，容易陷入局部最优值。EM算法来源于数据统计领域，其中非常热门的领域有极大似然估计和贝叶斯统计，从算法上分析来说贝叶斯统计和极大似然估计的计算过程存在部分相似，比如极大似然函数估计在计算的方法，与贝叶斯的后验概率的计算是近乎相同的。在学习统计之后，我们可以了解到，贝叶斯是分为两种的大类的，一种是拥有显式的后验分布，可以应用于似然函数的计算；另外一种是数据增添的方法，但数据处理会遇到问题，数据会存在缺失或者需要计算的似然函数非显性，这时候就可以应用数据增添，它可以通过增加”潜在数据”的方式，使我们缺失的数据得到补充，完成极大化的工作。EM算法就是我们常用的一种数据添加法，将在下面详细介绍。几十年前，当时正处于数据快速增长得信息爆炸时代，这对处理信息能力提出了巨大挑战。存在的问题不仅信息量大，还有信息不完善的问题，面对这些问题，专家学者们提出了很多方案，但是最终还是EM算法成为了处理这些问题的第一选择。最主要的原因在于EM算法运用数据增添的方法，通过引入数据，降低问题复杂度，减少了数据缺失带来的影响，相较于当时流行的神经网络拟合，填补法，卡尔曼滤波法能够有效的解决我们的问题。这种简化策略，为处理信息的效率带来了不可忽视的影响。并且这种算法步骤简单，可以很可靠的找到最优的收敛值，。理解EM算法的作用，首先要理解“潜在数据”。“潜在数据”是比较难以直接观测的数据，但包含“潜在数据”的数据组本身并未缺失。为了方便处理这类问题，通常会添加额外的变量，让此类问题变得更容易处理。下面举一个简单的例子：假设数据X是已知的观测数据，数据Y是一组缺失的或者为观测完全的数组，Z是由XY联合观测得到的，即Z=(X，Y)为完全数据。考虑解决这个问题，如果我们从数据X出发，对其进行最大似然估计，就不得不考虑数据缺失带来的影响。所以我们应该从Y，Z的概率密度入手。EM算法就是利用这个原理，通过比较容易获得的数据，绕过了P(0|X)数据不完整的陷阱。尽管有很多好处，我们也应该注意到EM算法也存在有以下缺点:一、如果数据缺失量大，计算这些缺失数据就需要更多时间，收敛的速度较慢。二、EM算法中的E步的期望显式的获得收到制约，有时候并不能得出E步需要的结果。三、受制于似然函数的估计的局限，在一些较为复杂情况下，要完成算法中的M步难度较大。1.2最大似然估计通过学习最大似然估计问题，我们可以了解EM算法的基本思想。举一个简单的例子，一个信息处理问题可以表述为，已知一个概率密度函数p()，其中θ为参数集。这里假设概率密度函数的形式已知，未知的只是参数。例如，对于高斯分布，p为高斯概率密度函数，θ为均值和方差。假定我们已有从分布p中抽取出的长度为N的数据，即X=。如果这些数据都是独立同分布，其概率密度由下式给出:(1.1)我们称函数为似然函数，或称是给定数据的参数似然。可将式子似然看作是固定数据集X关于参数θ的函数。在极大似然估计问题中，目标是得出能最大化的θ。也就是，希望找到满足下式的。(1.2)为了方便计算和分析，通常也最大化的对数，即log()，称为对数似然，记为。p()的形式决定了极大似然估计问题求解的难易程度。例如，如果p()只是单变量高斯分布，那么θ=，运用数学知识，可以对log()求导并令其等于0，直接可以解出μ和。但是，实际问题往往更复杂，不能简单的取求解，只能借助EM算法及类似方法进行简化计算。作为一种基本方法的EM算法，采取的方法是搜寻潜在概率分布参数的极大似然估计，以补全不完全数据或有缺失数据的给定数据集。EM算法有两种主要应用场景，第一种是数据有缺失值，这种确实是由于测量技术的限制或其他原因而导致。第二种是简化似然函数。可以假设存在缺失(隐含)的参数，然后对于当前分析困难的似然函数进行简化。这种简化的方法在图形处理应用上更为普遍。1.3Jensen不等式先定义凸函数的概念。假设一个定义域为实域的函数f，如果对于所有的实数x，都有二阶导数f"(x)≥0，则f为凸函数。对于向量x，如果其Hessian矩阵(二阶偏导数构成的方阵)H是半正定的，即H≥0，则f为凸函数。如果f"(x)>0或H>0，则称f为严格凸函数。Jensen不等式可表述为:如果f为凸函数，X为随机变量，则E[f(X)]≥f(EX)。为简化书写，将f(E[X])简写为f(EX)。特别地，如果f为严格凸函数，则当且仅当p(x=E[X])=1，即X为常量时，有E[f(X)]=f(EX)。Jensen不等式用图来表示更为清晰。如图4-1所示，曲线所表示f为凸函数，X为随机变量，x取值为的概率为，取值为的概率为=1-。X的期望E[X]就在和之间且E[X]=，f(EX)位于凸函数f上，E[f(X)]就在f()和f()连线上，E[f(X)]=。可以看到，E[f(X)]≥f(EX)成立。图3-1图解Jensen不等式上图的E[f(X)]≥f(EX)可写为：(1.3)可将上式推广至更一般的形式。如果满足=1，则(1.4)即(1.5)如果使用g()来替换，可得:(1.6)将Jensen不等式在凹函数上进行应用，凸函数与不等号方向相反，即f(EX)]≥E[f(X)。1.4EM算法推导对于N个训练样本，每个样本都对应一个隐含的类别。我们的目标是找到隐变量，使得p(x,z)最大，其极大似然估计为:(1.7)其中，为对数似然函数。由于对数log内有求和运算，并且有隐变量，直接求解似然函数并不容易。如果能够确定，求解就变得相对容易。EM算法适合优化含有隐变量的问题，基本思路是:既然无法直接极大化，可以先使用E步骤来不断建立的下界，然后用M步骤来优化提升的下界，进行重复迭代。对于任意的第i个样本，用来表示该样本的隐变量的某种分布，必须满足的条件为。这里假设为离散型，如果为连续型，那么q应为概率密度函数，我们可以将求和符号进行改写，变为积分符号。对数似然函数可以表示为:(1.8)其中，上式利用了Jensen不等式。由于log(x)的二阶导数为-1/，小于0，因此为凹函数，根据凹函数的Jensen不等式，有:上述过程可以看作是对求下界。分布有多种可能的选择，需要选择更好的。假设О已知，的值就由和p决定，可以通过迭代计算拟合这两个概率使下界不断向上提高，以逼近的真实值。当不等式变成等式，迭代过程终止。说明计算的值能够等价于。要让等式成立，根据Jensen不等式，需要将随机变量变成常数，即:(1.9)其中，c为常数。对不依赖于的常数c，选择≈p就能让上式成立。我们已经知道是一种分布，满足=1，可推出下式:(1.10)这样，就可以简单设置为给定和参数θ后的后验分布。至此，我们已经知道如何设置，这就是E步骤，它建立了的下界。下面的M步骤就是在给定后，调整参数θ来极大化的下界。重复执行上述两个步骤就是EM算法的核心步骤。1.5EM算法的改进通过对于EM算法的基础了解，我们知道了EM算法的最大优点就是执行够简单，上升的算法稳定，可以得到似然函数最优解或者是局部最优解。因此，EM算法在工程实践中拥有极强可操作性和广泛地适用性，但是面对上面提出的三个主要问题，我们希望找到一些解决方法。所以接下来将介绍一下为了将EM算法应用实践能力的提升,专家学者们进行了那些研究。对于EM算法的改进将为两部分,第一部分是介绍E步算法改进,另一部分是M步算法的改进。1.5.1改进E步在之前的介绍中，面对简单问题，E步所需要求解的问题可以直接解决。,但是面对复杂问题，E步的计算想要在已知的非完整的数据的条件下，对于”缺失数据”求期望，再根据所求的期望，进行似然函数的估计。这个问题的重点是在求期望的过程中对于非完全数据的计算，因为在这种情况下显式是难以通过期望轻易求取的，这种情况大大限制了算法的适用性。因此就有一些学者提出了MCEM算法的产生，这个方法主要利用近似的手段进行求解问题，下面将详细的阐述下这个算法:在计算过程中,第k+1个E步被下面两个步骤取代:E1:构成独立同分布的缺失数据集，从(y|x,)中随机抽取个数,将这m(k)个作为数据的添加，用来求解问题，这样我们就有一个新的数据集z(j)=(x,)李柏椿.EM算法及其改进算法在参数估计中的研究[D].2017。李柏椿.EM算法及其改进算法在参数估计中的研究[D].2017E2:计算下面的公式:(1.11)计算上面的两步骤，利用Monte,Carlo估计得到的结论，在M步中对Q(θ|θ(k))的进行极大化求解,从而得到θ(k+1)代替θ(k).MCEM算法的实践中有几个需要注意的问题:一、如何确定m(k),m(k)的选择很大程度上决定了MCEM算法的结果精度,想要提升精度，就不得不选择更多m(k)，举一个极端的例子，如果选择m(k)选择数量多到和集合Y一样，就等同于并未做优化，所以m(k)个数的选择成为了算法速度提升的关键点。一般使用的策略是在算法开始前选择较小m(k)，在经过初始判断后逐渐增大m(k)，直到选取到合适值，这样的策略更有利于以上两步优化效果的发挥。二、判断算法收敛性。根据上述理论，我们可以看出MCEM算法和EM算法收敛方式不同，通过MCEM算法得到的θ(k)只能在理想最大值周围波动，不会像EM算法一样收敛，随着迭代的进行，这种波动也不会变小张宏东.EM算法及其应用[D].2017。所以在MCEM算法中，要有好的阈值判定MCEM张宏东.EM算法及其应用[D].20171.5.2改进M步介绍完E步改良后，我们也应当提升M步效率。回归到算法本身，EM算法优势就在于简化极大似然估计，在不完整数据的条件下，对Q(θ|θ(k))进行极大化计算。其原理在于完全数据下的似然计算)与Q(θ|θ(k)基本一致。然而，在比较复杂情况下,M步的计算过程并不容易，对于Q(θ|θ(k))的求解难度较大。通过不断地努力研究，算法工程师提出了多种改进策略，以提升M步的效率。第一个有效的方法是减少M步的出现次数。通过主动选择在每次M步计算中提升Q函数的值，即Q(θ(k+1|θ(k))>Q(θ(k)|θ(k))，而不是极大化Q函数，这样可以减少M步的迭代。基于这个原理提出了GEM算法，GEM算法增大似然函数的值，将其运用于每个迭代步骤中，但由于缺少函数增大的数据采集完善，所以收敛性难以得到保证。经过不断研究1993年，Men和Rubin提出了ECM算法，这种算法是GEM算法的一种优化提升，有更广泛的应用空间。为了避免出现迭代的M步，ECM算法用来代替M步的基本思路是进行拆分。这种拆分的具体方法是用几个简单的的条件极大化(CM)步进行替代原本的步骤，它用算法设计的一个简单的优化问题代替p求函数Q的极大化，一次CM循环包括这一系列初级的条件极大化步骤，经过这样的替换之后，ECM算法也就等同于k次CM迭代与E步迭代的组合。上文说到的CM循环的步骤有如下两步:每个CM循环里CM步的个数用N表示，迭代次数从1一直增加到N，对于第k次迭代过程的第k次CM循环，有以下限定：(1.12)θ(k+(s-1)/s)是第k次CM循环的第n个CM步得到的值，下一步求函数Q(θ|θ(k))的最大化。经过S次CM步的循环计算后，进行下一次EM步循环的同时。令θ(k+l)=θ(k+n/N)。因为每一次CM步都增加了函数Q，Q(θ(k+n/N)|θ(k))>Q(θ(k)|θ(k))，所以显然ECM算法是GEM的一个子类。同GEM一样，为了保证算法的收敛性，需要确保每次的CM步的循环都是在任意的方向上搜索函数Q(θ|θ(k))的最大值点。才能使p的原始空间上进行极大化应用于ECM算法那，最终收敛与一个稳定的极大值点和EM算法一样，并且有相同的收敛域。脱胎于GEM算法的ECM算法对于收敛到全局极大点或者局部最优值也不能做出保证。与EM算法相似，对于收敛速度进行考虑，ECM算法的全局收敛速度表示如下:(1.13)通过计算看出，ECM算法要比EM算法快，主要是因为迭代次数的减少而在迭代速度方面，EMC与常规的EM算法迭代速度近乎一样。但是矩阵()的最大特征值等于迭代算法的收敛率P，由于缺失信息比例越大也会让P值相应增加，收敛速度因此变慢，因此1-P就是ECM算法的收敛速度。由理论可以看出，我们仍需要强化ECM步骤中的技巧，完成更好的EMC结构构建。例如可以对需要对限制条件进行选择。根据上述算法的把θ均匀分割为N个，写作子向量θ=(,,,…,)。然后在第S个CM步中，为求函数Q的极大化，可以固定θ其余的元素。这相当于用g(θ)=(,,,…,)作为约束条件。这种方法被称为条件迭代策略。通过以上描述，可以总结ECM算法的优点:在一定条件下CM循环通常能简化计算，降低运算的代价。作为ECM的升级，ECME算法在1994年被Lin和Rubin提出来，ECME算法简化了某些CM步，作为ECM算法的一种升级方案，在CM步极大化的基础上，ECME发展处出全新的特点，对于对数似然函数的期望Q(θ|θ(k))，在这个函数完整数据收到约束的情况下进行极大似然估计，并且对受约束ed实际似然函数L(θ|Z)进行部分极大化。ECME算法的第k+1次迭代的CM步形式:(1.14)E步和CM步相互交替，经过迭代后计算得到θ(k+1)，继续进行下一次E步计算，循环往复直至收敛于极大值。由此可见，这一算法并没有失去单调稳定收敛，操作简单原理易懂特性，保持着EM，ECM的优点。在收敛速度方面，这一算法青出于蓝而胜于蓝，单词迭代速度更短，迭代次数更少，迭代收敛所需时间更短。这一改进主要有两个原因：一、在ECME算法中的完全数据的实际似然函数把某些极大化步条件极大化了，这是一种对于提升单一循环速度很有效的策略;第二，ECME算法提升了收敛速度，受到约束的数值进行极大化后不再有对于判决门限的需求，这样的计算方法效率更高。和EM、ECM算法一样，对ECME算法的收敛速度，由斜率决定着，这个斜率所代表的就是θ(k)-θ(k+1)映射在上的导数。用观测数据、不完整数据、完全数据信息阵来计算，经过实验证明，ECME算法的收敛速度在相同条件下确实比EM,ECM更快，但计算方法相对而言比较复杂;因为完全数据对数似然函数的期望Q(θ|θ(k))，实际似然函数L(θ|z)在CM步上极大化，经过极大化的处理，因为Q函数是近似的，因此精确度有较大提升。总的来说，问题比较复杂时候，ECME算法能取得较好的成效。AECM算法从另一个角度入手，它的名称是期望条件极大化算法，经过对于ECME的研究，与ECM、ECME算法相同，AECM算法在CM步采用极大化的方法，但ACME会极大化另外一些不同的值。AECM的迭代也是将一大步分解为循环组成的，假设在数据无缺失的情况下，E步：每个循环由两部分进行定义，包括完整数据组和缺失数据组；CM步：由于E步定义要求相互呼应的CM计算式组成。AECM迭代就由重新定义循环构成的集合完整确定下来，这种算法由着和ECME一样的优点，可以提高计算效率。PX—EM算法在1998年被提出，这种算法的提出是为了提升EM算法的收敛速度。为了得到更多关于完全数据的信息，修正M步进行协方差的调整角度出发进行研究。原本在EM算法中，由于参与不同的原因，完全数据下p(z|θ)和观测数据下p(x|θ)也不相同。所以PX—EM算法抓住这一突破口，扩充参数集，引入附加参数。通过这样的方法，如果在数据集中参数为θ，新扩展的参数空间为(，α)，就可以计算得出与EM算法中是相同维数的。且如果我们得到(z|θ)=p(z|参数空间)，即得到原来的模型，此时有α与α(θ)相等。在运用PX—EM算法时，有以下三点限制:我们可以使用一种变换R，使得θ=R(,α)，且这种方法是可实现的。2.当α=α(θ)时，扩展我们选择的模型，使得α的信息不会出现在已经观测到的数据集X中，即(1.15)选择模型进行扩展时，完全数据Z=(X，Y)是可识别参数的。从而我们可以的到PX—EM算法迭代模型，它的第k+1次迭代形式。PX—E:(1.16)PX—M步:(1.17)令PX—E,PX—M步不断地重复,直到收敛.PX—EM算法的每一步都增大p(x|,α)，当α=α(0)时，它等于p(x|)，PX—EM算法的每一轮迭代都增大了有关的似然函数p(x|)，与此同时，也保持了EM算法在收敛特性上的优点，PX—EM算法一定会收敛到一个稳定点。下面需要考虑的是PX—EM算法的收敛速度。在适当的变换θ=R(,α)下，之前提到对一切a，a’存在p(x|,α)=p(x|)，根据p(z|,α)，经过计算，就可以得出已观测数据和完整数据下的信息矩阵△:(1.18)(1.19)(1.20)缺失信息比率为:(1.21)可以看出确实信息速率比和EM算法收敛类似。缺失信息比例如下:(1.22)由此可见，在矩阵之差为半正定的情况下，PX—EM的缺失信息比例更小。因为确实比例越大，收敛越慢。我们通过缺失信息的大小可以判断,PX—EM算法的收敛速度是要比EM要更优。原因也正如上面所说，通过拓展参数空间的方法增加参数a，将完全信息量进行增加。通过对于缺失数据的填补,减少的缺失信息所占比例,使信息变得更完整，加速算法。最后总结以下PX—EM的优点:对EM算法修改幅度小,设计并不复杂；将有效信息充分利用，拓展完全,可以取得比EM算法更快收敛速度，不影响EM算法的单调收敛性。1.6算法步骤面对数据残缺或数据不完整的情况，用EM算法可以较为简单的求出求极大似然函数估计值。常用的EM算法分两步，即E步（Expectation-step）和M步（Maximizationstep）。E步确定似然函数，并计算似然函数的期望值。M步在E步之后进行，通过M步估计期望值计算极大似然函数参数。EM算法详细描述如下:将分布参数进行初始化；重复E步骤、M步骤，进行门限进行判决，确定是否收敛；E步骤:计算出隐性变量的后验概率，带入参数初始值或上一次迭代所得参数值，作为隐性变量的现估计值:(1.23)M步骤：将似然函数最大化，并作为下一次E步的参数：(1.24)1.7EM算法估计GMM参数1.7.1混合模型混合模型（MixtureModel）是一个含有K个子分布的概率模型的集合，换句话说，观测数据在总体中的概率分布就是混合模型，K个子分布组成相互独立，共同组成的混合分布。混合模型在观测数据时，并不对子分布的信息做出要求，而是通过计算概率观测数据在总体分布中的分布情况。1.7.2单高斯模型单高斯模型(GaussianModel)当样本数据X是一维数据时，例如X={1,3,3,1}。一维高斯分布遵从下方概率密度函数：(1.25)其中为数据标准差，μ为数据均值（期望）。如果我们想拟合高纬度的模型，高斯分布遵从下方概率密度函数：(1.26)其中，μ为数据均值（期望），为协方差（Covariance），D为数据维度。1.7.3高斯混合模型高斯混合模型(GMM，Gaussianmixturemodel)就是混合模型和单高斯模型的联合应用，吸纳了二者的优点。利用高斯概率密度函数精确地拟合数据，也利用混合模型的特点，包含组合多种不同的高斯概率密度函数，可以用来处理复杂问题，是一种精准量化手段的体现。如果将高斯混合模型看作是K个单高斯概率密度函数组合而成的集合，如何选取这K个单高斯模型的概率，也就是隐变量（Hiddenvariable）。因为高斯分布具备便于计算的特点以及极强的拟合能力，所以在这个混合模型中我