（交通信息工程及控制专业论文）EM算法及其改进在混合模型参数估计中的应用研究.pdf

摘要 有限混合模型是分析复杂现象的一个灵活而强有力的建模工具，它提供了用 简单结构模拟复杂密度的一个有效方法，给出了模拟同质性和异质性的一个自然 框架和半参数结构。 e m 算法为有限混合模型的极大似然估计提供了一个标准框架。本文简单推 导了有限混合高斯分布的e m 算法，并针对其收敛速度慢的缺点设计了一种有效 选取参数初始值的方法，数值实验表明，该方法有助于e m 算法以较快的速度在 参数真值附近收敛。 e m 算法思想简单，易于实现。但是，e m 算法往往获得的只是一个局部最 优解，这是因为它本质上是一个迭代算法，只能保证达到局部最优，而遗传算法 具有强大的全局搜索能力，因此，本文将采用遗传算法来改进e m 算法，提出一 种以遗传算法为主、结合e m 迭代算法的混合算法( 即g ae m 算法) 。在前面 的研究中，我们总是提前定义一个混合模型的分支数，但在大多实际应用中，最 优分支数是未知的，所以为混合模型选择一个最优分支数是一个相当重要又困难 的问题。本文将使用g a - e m 算法来学习未知支数的多元高斯混合模型，算法中 使用m d l 准则作为选择最优分支数的信息准则。采用e m 算法和遗传算法混合 编程的目的是为了更好地利用两种算法各自的优点，基于随机搜索优化技术遗传 算法的种群极大地拓展了e m 算法的搜索空间，有效地降低了基本e m 算法对初 始值的依赖程度，改善了其收敛到局部最大值的缺陷。数值实验也表明，g ae m 算法不仅继承了e m 算法的单调收敛性，对模型参数初始值也更加稳健：1 ) 在 同样的迭代终止条件下，g ae m 算法能够得到比e m 算法更好的m d l 值。2 ) g a _ e m 算法克服了e m 算法选择最优分支数的正确率会随着分支数的增加而迅 速降低的缺陷。 关键字：混合模型，极大似然估计，e m 算法，最优分支数，遗传算法。 a b s t r a c t f i n i t em i x t u r em o d e li saf l e x i b l ea n dp o w e r f i i lt o o lf o ra n a l y z i n ec o m p l i c a t e d p h e n o m e n a ，w h i c hp t o v i d ea ne f f i c i e n tm c t h o do fs i m u l a t i n gc o m p l j c a t e dd e n s i t y w i t hs i m p l es t 九l c t u r e sa n dp r e s e n tan a t u r a lf r a m ea n ds e m i - p a r a m e t e rs t m c t u r eo f m o d e l i n gu n o b s e r v e dp o p u l a t i o nh o m o g e n e i t ya n d h e t e r o g e n e i t y t 1 l ee x p e c t a t i o n - m a x i m i z a t j o n ( e m ) a l g o r i t h mi sas t a n d a r df r 啪ef o rm a x i m u m l i k e l i h o o de s t i m a t i o ni n f i n i t em i x t u r em o d e l s 1 m ee mi t e r a t i v ef 0 册u l a sf o r g a u s s i a nm i x t u r e sa r ed e r i v e di nt h ep r e s e n tp a p e r a n dw ep r o p o s ea ne f ：f j c j e n t i n i t i a l i z a t i o nm e t h o df o rt h e s ei t e r a t i v ef o 册u i a st oa c c e l e r a t et h ee ma l g o r i t h m s p e e do fc o n v e f g e n c e e x p e r i e n c e so fn u m e r i c a is i m u l a t i o ns h o wt h a tt h ep m p o s e d i n i t j a lm e t h o dc o n t r i b u t e st oa c c e l e r a t et h ea l g o r i t h m ss p e e do f n v e r g e n c e ，t h e m o r ea c c u r a t er e s u l t s 伽b eo b t a i n e d t 1 l ee ma l g o r i t h mi sr c a l i z e de a s i l yb e c a u s eo fi t ss i m p l i f y u n f o n u n a t e l y o p t i m a l r e s u l t sa r en o ta l w a y sa c h i e v e db e c a u s et h ee ma l g o r i t h m ，i t e r a t i v ei nn a t u r c ，i so n l y g u a r a n t e e dt op r o d u c eal o c a lm a x j m u m a sw ek n o w n ，t h eg 删e 疵口咖“抽m ( g a ) h a sm u c hs t m n g e r 目o b a ls e a r c h i n ga b i l j t y ，w ei m p o r tt h eg aa i g o r i t h mf o ri m p m v i n g t h ee ma l g o r i t h m ，a i l dp r o p o s eag e n e t i c - b a s e de x p e c t a t i o n - m 积i m i z a t i o n ( g a e m ) a l g o r i t h m t h ee ma l g o r i t h mi sr e s t r i c t e di oap r e d e f i n e dn u m b e ro fc o m p o n e n t s h o w e v e r i nm a i l yp r a d i c a la p p l i c a t i o n s ，t h eo p t i m a ln u m b e r0 f m p o n e n t si s u n l 【l l o w n ，t h e r e f o r e ，f i n d i n gt h eo p t i m u mn u m b e ro fc o m p o n e n t si nt h em j x t u r cj sa n i m p o r t a n tb u tv e r yd i f f i c u l tp m b l e m w c i ll e a mg a u s s i a nm j x t u r cm o d e l sf m m m u i t i v a r i a t ed a t at h eg a e ma l g o r i t h m 拍i sa l g o r i t h mi sc a b a l l i n go fs e l e c t i n gt h e n u m b e ro fc o m p o n e n t so ft h em o d e lu s i n gt h e 肌胁f m “历d 酷c r 咖f 如珂胁g 踊( m d l ) c r i t e r i o n 0 u ra l g o r i t h mb e n e f i t sf r o mt h ep m p e n i e so f 托e r f cn 劬“m m ( g a ) a i i d e ma 1 2 0 r i t h mb vc o m b i n a t i o no fb o t hj n t oas i n g l ep r o c e d u r e t h ep o p u l a t i o n - b a s e d s t o c h a s t i cs e a i c ho ft h eg ae x p i o r e st h es e 盯c hs p a c em o r et h o r o u g h i yt h a nt h ee m a l g o r i t h m ，t h e r e f o r c ，o u ra l g o r i t h me n a b l e se s c a p i n gf m ml o c a lo p t j m a ls 0 i u t i o n s s i n c et h ea l g o r i t h mb e c o m e sl e s ss e n s i t i v et oi t si n i t i a l i z a t i o n t h ee x p e r i m e n t so n s i m u l a t e dd a t as h o wt h a t i h eg a e ma i g o r i i h mm a i n t a i n st h em o n o t o i i i cc o n v e r g e n c c p r 叩e n yo ft h ee ma 1 9 0 f i t h m ，t a l 【i n g 咖ag o o dt 0 b u s t n e s st o i n i t i a lv a l u e so f p a r a m e t e r s ：1 ) w eh a v eo b t a j n e dab e t t e rm d ls r ew h i l eu s i n ge x a c t l yt h es 锄e t e 加i n a t i o nc o n d i t i o nf o rb o t ha l g o r i t h m 2 ) o u ra p p r o a c hi d e n t i f i e st h en u m b e ro f c o m p o n e n t sw h i c hw e r eu s e dt o 龋n e r a t et h eu n d e r l y i n ed a t am o r eo f l e nt h a i lt h ee m a l g o r i t h m k e y w o r d s ：m i x t u 陀m o d e l ，m a x j m u ml i k e l j h 0 0 de s i i m a i i o n ，e ma l g o r i t h m ，o p t i m a ln u m b e r o f c o m p o n e n t s ，g e n e t i ca l g o r i t h m 论支嗷纠佳声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行 研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表的成 果。 本声明的法律责任由本人承担。 论文作者签名：望辱辂 加厂年月日 论支知识产仅仅属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：照学牟龟 导师签名：砌盼 硼1 年窍6 日 加石日 第一章研究背景 在信息与数据膨胀的今天，数据挖掘技术为人类挖掘数据中隐藏的信息和知 识提供了有力的工具。聚类分析就是其中的核心技术之一它为数据挖掘预处理数 据提供了有力的支持。目前聚类分析已成为数据挖掘领域的重要研究课题之一。 基于模型的聚类方法是数据挖掘中聚类分析的一种重要方法，这种方法主要 有两类：统计学方法和神经网络方法。对于数据的描述，建模是一种比较好的选 择方法。通过建模可以推理数据中的潜在规律，如果把数据想象为由一个潜在的 概率函数产生，那么可以用概率混合模型来描述和建模数据。有限混合模型是以 概率统计为基础的分析数据的工具，它不但灵活而且功能强大，已在统计学和模 式识别中得到了广泛的应用【”。它的最有特色的应用就是用有限混合分布模型聚 类，除此之外还可用它进行密度估计和判别分析等。 1 1 有限混合模型的研究现状 在实践中，如果现象是由若干随机因素的某一个( 或几个) 所引起，则可考 虑建立混合模型来研究这一复杂现象。实践证明，无论是对但变量还是多变量数 据，有限混合模型都是一个灵活而强有力的概率分析数据工具，其有效性已在许 多领域得到了普遍的认可，主要表现在以下几个方面： ( 1 ) 它采用了简单结构模拟复杂结构的方法。 ( 2 ) 它提供了一个模拟同质性和异质性数据的方法。当模型分支数等于1 时，混合分布( 密度) 总体是一个单一的分布( 密度) ，因而数据是同质的。当 分支数大于1 时，模型就有多个成分，反映了混合数据的异质性。 ( 3 ) 当混合变量数目未知时，混合模型在参数框架内也提供了一个非常可 行的建模环境。这样以来它既兼备了参数模型的解析优势又有非参数模型的灵活 性，可以看成是半参数模型，因而有更多的建模优势。 在众多文献中，有许多方法被用来估计混合密度的参数，如矩( m o m e n t ) 方 法，m l ( 岫x i m u ml i k e l i h o o d ，m l ) 方法及b a y e s 方法。然而，有限混合模型参 数的解析公式般不可获得。即使对g a u s s i a n 混合密度，m l 方法也得不到混合 比例、分支均值和方差的值。直到1 9 7 7 年d e m p s t e r 等人提了计算不完全 数据的极大似然估计的e m 算法，并给出了混合模型的不完全数据结构，m l 方 法发展迅速，现已成为混合模型拟合的主流方法。这以后，有限混合模型的计算 和应用研究得到了空前的发展，每年都在涌现出许多新的方法及应用文献。 一般的混合模型的研究中存在着两大难题：第一是怎样估计混合模型的参 数：第二是混合模型分支数的确定。对于第个问题，极大似然方法仍然是混合 模型的有效的参数估计方法，随着计算机性能的提高，e m 算法为极大似然估计 的计算提供了强有力的工具，同时也能优化聚类的过程，近年来已经有许多e m 算法的变体算法出现。然而估计模型参数极大似然的e m 算法( 或其变体) 是一 个局部最优搜索算法，常常会陷入局部最优解，使得它的搜索结果对初始化敏感， 从这儿可以看出，第一个问题实际上已经变成了怎样解决初始化敏感的问题了。 在建立混合模型解决实际问题的过程中，如何为它选择一个合理的分支数是 一个十分重要但又相当困难的问题。许多文献基于不同原理提出了解决这一难题 的多种方案，可事实上这一问题至今还没有得到彻底解决。一般的混合模型常用 七一均值算法，模糊聚类算法等，数据量较小的时候可用基于模型的层次聚类算 法，先估计出数据集可能划分的最大分支数目，然后用模型选择的准则选出最佳 混合模型的分支数。最为经典的方法当属f i g u e i r e d o 和j a i n 提出的基于最小 信息编码( m m l ) 准则和e m 框架的算法【1 3 l ，它真正实现了同时处理分支数和 模型参数这两个问题，其特点是它将参数估计与模型选择紧密结合到一个单一的 e m 算法中。目前已有好几位作者尝试研究了不同模型大小间有效转移的方法， 基于e m 的凝聚聚类算法就是经历了一个分支数单调递减的过程，它通过比较不 同模型大小间准则的似然大小达到模型间的转移，而确定性退火d a e m 算法【硐则 采用先经历一个分支数目增加的过程，然后利用退火策略，进行成分递减，判断 出最佳数目的模型1 2 9 】。 1 2e m 算法简介 e m 算法是一种缺失数据情况下参数估计的特别算法。它之所以被称为e m 算 法是因为算法的每一次迭代是由一个期望步( e x p e c t a t i o ns t e p ) 和极大步 ( m a x j m i z a t i o ns t e p ) 构成。这个名字首先是由d e m p s t e r ，l a j r d 和r u b i n ( 1 9 7 7 ) 毽； 一 玉 告 t o ( 以下简称d l r ) 给出的。其基本思想是首先在给出缺失数据初值的条件下，估 计出模型参数的值；然后再跟据参数值估计出缺失数据的值。根据估计出的缺失 数据的值再对参数值进行更新，如此反复迭代，直至收敛，迭代结束。 所谓存在缺失数据可以有两种解释，一种情况是由于问题本身的原因或观察 条件的限制导致观察数据存在缺失变量，另一种情况是缺失变量本身并不存在， 但是观察数据似然的优化比较复杂，而如果添加额外的变量( 或称为缺失变量) 后的完全数据似然估计则比较简单，根据这种思想可以把许多统计模型纳入到 e m 算法的框架中来，比如说，混合模型( m i x t u r em o d e l ) ，对数线性模型( l o g l i n e a rm o d e l ) 以及潜变量结构( l a t e n tv a r i a b l e ss t r u c t u r e ) 等，在这些情 况下利用e m 算法可以使得复杂的极大似然估计变得简单，e m 算法可以运用到几 乎所有的统计问题或那些统计问题可以运用到的领域，如医学造影( m e d i c a l i 帕g i n g ) ，a i d 流行病学研究等。 e m 算法是一种迭代算法，它的优点很明显，主要表现在以下几个方面：一 方面在于它所涉及的理论的简单化和一般性，二是在大多数情况下，它实质上是j 一 一个优化算法( o p t i m i z a t i o na l g o r i t h i n ) ，并且能够收敛到局部极值，再者就 是在于许多的应用都能纳入到e m 算法的范畴，e m 算法成为统计学上的一个标准 工具。当完全数据来源于一个指数分步族时，极大似然计算就比较简单，相应的，、： e m 算法的每一个极大化的计算也比较简单。 1 3 本文的主要工作 有限混合模型具有系统性、灵活性等优点，在许多领域内得到了广泛的有效 的应用，其中研究最多的是多元高斯混合模型，因此混合模型聚类的研究现状基 本上是由多元高斯混合模型的研究现状反映的。本文研究的主要内容也将集中在 对多元高斯混合模型的参数估计的问题上。针对上面提出的混合模型参数估计中 存在的问题，本文将从以下几个方面对e m 算法做出改进： 1 加快e m 算法的迭代速度 从前面的介绍我们可以看出，e m 算法对初始值的依赖性很强，那么选取合适 的参数初始值必将可以减少e m 算法的迭代次数，加快e m 算法的迭代速度。从聚类 的概念我们可以得到这样一个感观的认识，聚类可以把一组数据样本在某种依据 下划分为互不重叠的类。具体到混合模型参数估计这块，也就是我们可以通过一 定的聚类方法获取部分隐含信息( 数据置属于混合模型分布的哪一个分支) 。聚 类算法多种多样，有k 一均值法、非线性最优化、模糊k 一均值法等。在各类聚类算 法中，k 一均值聚类算法的应用最为广泛。在这儿我们将采用简单实用的k 一均值法 的结果作为e m 算法的初始值。然而k 一均值法本质上是种局部搜索技术，它采用 了所谓的梯度下降法来寻找最优解。因此容易陷入局部最小值，而得不到全局最 优解，所以从某种程度上加剧了e m 算法局部收敛的缺陷。 2 如何改善e m 算法初始值的敏感度以及局部收敛的缺陷 正如上面提及的e m 算法是基于梯度上升的算法，它可以保证每一次迭代后模 型对训练数据的似然概率是递增的。但是，作为一个基于梯度上升的爬山算法有 个很大的缺陷，往往只能得到一个局部最优解。本文将力求找到一种能够在一定 程度上解决局部极值问题，使算法收敛精度较高的优化工具，遗传算法就具有这 样的性能。于传统的优化方法相比，遗传算法是一种随机搜索优化技术，同时使 用多个点的搜索信息极大地拓展了e m 算法的搜索空间，有效地降低了基本e m 算法对初始值的依赖程度，可以改善其收敛到局部最大值的缺陷。因此，我们拟 采用遗传算法对传统的e m 迭代算法进行改进，提出以遗传算法为主、结合e m 迭代算法的混合算法( 即g ae m 算法) ，并将该算法用于未知支数的高斯混合 模型的参数估计，在算法中使用最小长度描述m d l 准则作为选择最优分支数的 信息准则，提出m d l 准则和g a e m 框架相结合的估计最优分支数的算法 ( m d i 广g a e m 算法) 。 全文的主要内容安排如下： 第一章：主要介绍本论文研究工作的意义，研究背景，论文的章节安排以及 主要工作内容。 第二章：主要介绍e m 算法的基本概况，包括算法的提出、原理，性质及发 展； 第三章：简要介绍了有限混合模型的基本知识，然后在假定分支数已知的条 件下，重点推导了高斯混合模型密度极大似然估计量的e m 框架，并针对该模型 了一个e m 算法的数值计算例子，分析e m 算法的收敛行为、优缺点，就其收敛速 度慢的缺点提出了改进措施。 4 第四章：重点讨论了最优分支数的选取问题。首先综述了未知支数混合模型 参数估计的主要方法，介绍了一些遗传算法的基本知识，并从遗传算法的角度对 e m 算法进行改进，进而提出种以遗传算法为主、结合e m 迭代算法的混合算 法( 即g a e m 算法) 寻求高斯混合模型的最优分支数。大量数值试验证明，改 进后的算法能以相当高的正确率选择出最优分支数，改善了m m l 广e m 算法对参 数初始值有一定依赖性、选择最优分支数的正确率会随分支数初始值的增大而迅 速降低的缺陷。 第五章：结束语，是本文的主要工作总结及今后的研究展望。探讨了本研究 方向的进一步改进和研究的热点。 2 1e m 算法概述 第二章e m 算法 在统计领域里，主要有两大类计算问题，一类是极大似然估计的计算，另一 类是b a y e s 计算。由于极大似然估计的计算类似于b a y e s 的后验众数的计算，因 此，我们可以从b a v e s 的角度来介绍统计计算方法。 b a v e s 计算方法已有很多，大体上可分为两类一类是直接应用于后验分布 以得到后验均值或后验众数的估汁，以及这种估计的渐近方差或其近似另一类 算法可以总称为数据添加算法，这是近年来发展很快且应用很广的一种算法，它 不是直接对复杂的后验分布进行极大化或进行模拟，而是在观因数据的基础上加 上一些“潜在数据”，从而简化计算并完成一系列简单的极大化或模拟，e m 算法 是一种一般的从“不完全数据”中求解模型参数的极大似然的方法，所谓“不完 全数据”一般有两种情况：一种是观察过程本身的限制或者错误，造成观察数据 成为错漏的不完全数据，一种是参数的似然函数直接优化十分困难，而引入额外 的参数( 隐含的或丢失的) 后就比较容易优化，于是定义原始数据加上额外数据 组成“完全数据”，原始观察数据自然就成为“不完全数据”。 基本原理可表述如下：设我们能观测到的数据是y ，完全数据x = ( y ，z ) ，z 是缺失数据，疗是模型参数。p 是关于y 后验分布p p i y ) 很复杂，难以进行各种 不同统计计算，假如我们能假定一些没能观测到的潜在数据z 为己知，则可能得 到一个关于口的简单的添加后验分布( p ( p i _ ) ，z ) ，利用p p i y ，z ) 的简单性我们可 以进行各种统计计算。然后回过头来，我们义可以对z 的假定作检查和改进，如 此进行我们就将一个复杂的极大化或抽样问题转变为一系列简单的极大化或抽 样问题 e m 算法是一种迭代算法，最初由d l r 提出，并主要用于求后验分布的众数( 即 极大似然估计) ，考虑不完全数据模型： 假定有两个样本空间x 和y ，x 是完全数据，】，是不完全数据。 ：x y 是 x 到y 的多对一映射。以g ( 日陟) 表示口的基于观察数据y 的后验分布密度函数， 称为观察后验分布。，( 口i y ，z ) 表示添加数据z 后得到的关于日的后验分布密度函 数，称为添加后验分布。七( z i _ ) ，口) 表示在给定8 和观察数据y 下潜在数据z 的条 件分布密度函数，我们的目的是计算观察后验分布g ( pj y ) 的众数。于是，e m 算 法如下进行，已为为第f + 1 次迭代开始时参数的估计值，则第f + 1 次迭代的两 步为 e 步：对，( p f y ，z ) 或i d g 厂( p f _ ) ，z ) 求条件期望，从而把z 积掉。 即q p ，) 。巨【l o g ，p l y ，z ) i _ ) ，】一厂i o g ，p i _ ) ，z 冲0 1 只) 出 ( 2 一1 ) m 步：将q ( p ，) 极大化，找到一个点口，使得q ( “，) = m a x q ( p ，) 。即 p “1 = a r g m a x q ( 口，疗) ( 2 2 ) 如此形成一次迭代日- “，将上述e 步和m 步反复迭代直至耖”一日0 或 陋( + 1 p ，y ) 一q ( p ，_ ) ，) j j 充分小时停止。 2 2 酬算法的主要性质 e m 算法的最大优点是简单和稳定，其目的主要是提供一个简单的程序来计 算未知分布参数的极大似然估计。那么，e m 算法能否达到这一预期要求就是一 个自然要问的问题，也就是说，e m 算法得到的估计序列是否收敛，如果收敛其 结果是否就是我们所要的原不完全数据极大似然估计量m l e 或是它的对数似然 函数的最大值点或局部最大值。这一问题在许多文献中讨论过，这儿只是不加证 明地引用几个重要结论来说明叫算法的收敛行为。 已e m 算法得到的估计序列为 ) ，f 。l ，2 ( p 阶= l o g p ( p l y ) 。 定理1 ：e m 算法在每一次迭代后均提高( 观察数据) 后验分布的众数( 或 极大似然估计量) ，即 p ( “f y ) 苫p ( 臼y ) 如果p ( 口i y ) 有上界，则l ( p i l ，) 可以收敛到f 。 推论：如果对于任意的不属于f ，有( 1j y ) 上( y ) ， 是似然函数l 的稳定点集合。 定理2 ：如果q ( 虻口) 关于口和都连续，则在关于l 的很般的条件下， 由e m 算法得到的估计序列的收敛值日+ 是l 的稳定点。 在一般的情况下，e m 算法的结果只能保证收敛到后验分布密度函数的稳定 点，并不能保证收敛到极大值点，事实上，任何一种算法都很难保证其结果为极 大值点。e m 算法得到广泛应用的一个重要原因是在m 步中，求极大值的方法与 完全数据下求极大值的方法完全一样。在许多场合下，这样的极大化有显示的表 达式，然而并不总是这样，有时要找一个使q ( ，矿1 ) q ( ，) ，这种e m 算法 称为广义的e m 算法( g e n e r a l i z e de ma l g o r i t h m ) ( 简称g e m 算法) 。由于每一 个迭代算法都隐含着一个映射，我们用m ) 来表示g e m 算法所隐含的映射，即 对任意的口，有q ( m 徊) ，日) q ( 8 ，口) 。 定理3 ：对于g e m 算法，有( m ( 口) l y ) 工( 口i 】，) ，且当q ( m p ) ，日) = q ( 疗，p ) 和 七( z i h m p ) ) = 七( z l _ ) ，o ) 均成立时，等号成立。 推论1 ：假如对于任意的疗，存在一些口，有( 口+ j y ) 三( 口j y ) ，那么有 ( m ( p ) i y ) = l ( 日l y ) ，q ( ，( 日) ，p + ) = q ( 日，口) ，女( z i _ ) ， f ( 日) ) 。七( z i ) ，疗) 。也京t 是 说，如果e m 算法收敛到一个全局最优解，则似然函数在这些点上的值是不变的。 推论2 ：加入存在一些口，对于任意的口一，有l ( 口i y ) 三( 口l y ) ( 比如说 口可以是唯一的全局最优解) ，那么对g e m 算法而言，有m p + ) = p 。也就是 说，如果e m 算法收敛到唯一的全局最优解，则参数8 在每一次的迭代中均保持 不变口= 口。 2 3e m 算法的改进版本 ，近年来，学者们已经提出了许多关于e m 算法的改进和扩展，来解决该算法 的局部最优问题、初始化问题以及收敛速度慢的缺点。我们这儿只是简要的介绍 几种改进方案。 2 3 1e c m 算法 e m 算法得到广泛应用的一个重要原因是在m 步中，求极大化的方法与完全 数据下求极大化的方法完全一样，在许多场合下，这样的极大化有显示表示，然 而不总是这样，有时要找使( 2 2 ) 式右端达最大的口是困难的，一个较较简单 的方法是找一个口( “”，使得 q p “1 p “，y ) q p p “，l ，) ( 2 3 ) 由( 2 1 ) 和( 2 3 ) 组成的e m 算法称为广义e m 算法( g e m 算法) 当一是一维参数时，现已有许多极大化方法可以使用，因而没有必要考虑g e m 算法。对多维参数8 = ( q ，见，吃) ，m e n g 和r u b i n ( 1 9 9 3 ) 提出了一种特殊的 g e m 算法，他们称之为e c ( e x p e c t a t i o n c o n d i t i o n a lm a x i m i z a t i o n ) 算法【捌。 e c m 算法保留了e m 算法的简单性和稳定性，其基本思想是用一系列的计算更加 简单的c m 步来代替一个复杂的m 步。它将原先e m 算法中的m 步( 极大化) 分解 为d 次条件极大化；在第i + 1 次迭代中，记口；( b o ，岛“，吃) ，在得到 q ( 8 p ，y ) 后，首先在卵，岛，吼保持不变的条件下求使q ( 8 l p ( 1 l ，y ) 达到最 大的q o “，然后在q = b “”，q = b “，= - 2 ，3 ，d 的条件下求使q ( 口i p “，y ) 达到最大的只“”，如此继续，经过d 次条件极大化，我们得到了一个口( “”，完 成了一次迭代。该e c m 算法简单，它是一种g e m 算法，满足g e m 算法的所有性质， 譬如收敛性。 e c m 算法的优点有： ( 1 ) 当m 步没有显示的表达式时，c m 步通常有显示的表达式。 ( 2 ) 即使c m 步没有显示的表达式，但e c m 算法通常更加稳定，因为它的极大 化是在更低维度( d i m e n s i o n ) 的参数空间进行的。 2 3 2p x e m 算法 e m 类型的算法是十分流行的参数估计方法，但它们有个很大的缺陷就是收 9 敛速度慢，l i u ，r u b i n 和w u 提出了p x e m 算法1 2 ”，其收敛速度要明显高于基本 e m 算法。p x e m 算法基本思想是通过协方差调整来修j 下m 步的计算，捕获完全 数据的额外信息，从而达到加速收敛的目的。 p x e m 算法的主要优点是： ( 1 ) 只要对它作小的修改就能应用到e m 算法。 ( 2 ) 保持了e m 算法的单调收敛的性质。 1 基本概念 x = ( y ，z ) 是完全数据，y 是观察数据，z 是隐含数据( 标签信息) ，口是参 数，g ( 口i ) ，) 表示口的基于观察数据y 的后验分布密度函数，称为观察后验分布。 厂p l y ，z ) 表示添加数据z 后得到的关于疗的后验分布密度函数，称为添加后验分 布。t ( z i y ，日) 表示在给定口和观察数据y 下潜在数据z 的条件分布密度函数，完 全数据与观察数据间存在一个一个对多个的映射| i l ，有y = ( z ) 。 q ( 一，p ) = e 【l o g ，( 口i y ，z ) i _ ) ，】，日( 口，) = t l 。g t ( z i y ，口) 1 ) ， 因而有工p ) = q ( p ，) 一h ( 口，) + e l 。g p ( z i y ) 1 ) ， 2 形式化定义 在所有的e m 算法中，完全数据模型，( 日i _ ) ，z ) 与观察数据模型g ( 日i y ) 有着相 同的参数集。p x e m 算法对参数集进行了扩充，( q i y ，z ) ，q = ，a ) ，其中。 只与e m 算法中的参数疗是一致的，口是一个辅助参数，当a = a 。时，有( q i ) ，z ) = ，( 口k z ) 。 同时满足下列两个条件： ( 1 ) 对所有的q ，存在一个多对一的归约函数r ( r e d u c t i o nf u n c t i o n ) ，有 q l y g ( p = r ( q ) i _ ) ，) 。 ( 2 ) 对任意的疗，当口= a 。时，有六( q = ，o 。) j y ，z ) = 厂p = 良j y ，z ) 。 p x e m 算法定义如下： 假定g = ( ，a 。) 是第j 次迭代值，口= a 。，那么第j + 1 次迭代如下： 1 0 p x e 步：计算q ( q ，q 1 ) = t 【l o g 丘( q i y ，z ) l y ，d 】口 p x m 步：找到q ”1 = a 唱m a x q ( q ，q i ，然后利用归约函数r ( q ) 获得 矿1 = r ( q “1 ) 。 p 卜e 步与p x m 步不断地重复直至收敛为止。 2 4 小结 期望最大化( e m ) 算法是一种求参数极大似然估计的迭代算法，在处理不完 全数据中有重要应用。e m 算法思想简单，实现也简单，数值计算稳定，并具有 良好的局部收敛性，所以，该算法自问世以来就一直受到统计界以其它应用学科 的广泛关注。本章主要介绍了e m 算法的基本概况，着重于对算法的描述，包括 算法的提出、基本原理及性质，明确指出算法还存在一些不尽如人意的地方，如 本身固有的局部收敛性，收敛速度慢等，并有针对性地介绍了目前流行的几种关、： 于e m 算法的改进和扩展方案。 第三章e m 算法在混合模型参数估计方面的应用 有限混合模型是分析复杂现象的一个灵活而有力的建模工具，他提供了用简 单结构模拟复杂密度的一个有效方法，给出了模拟同质性和异质性的一个自然框 架和半参数结构。因此它被广泛地应用于各个领域，如医学、遥感、经济学、环 境科学、模式识别、语音识别、图像处理、信号处理、神经网络，几乎涵盖了各 个学科。混合密度模型参数的估计问题是e m 算法在模式识别中应用最为广泛的 一个领域。 本章研究在混合分支数已知或者是事先给定的条件下，有限高斯混合模型期 望极大化( e m ) 估计的计算方法。 3 1 有限混合模型的定义 有限混合模型应用的分析可以追溯到一百多年前著名生物统计学家k a r l p e a r s o n ( 1 8 9 4 ) 的开创性论文，他用矩方法研究了2 一分量的单变量高斯混合模 型。然而，关于有限混合模型的蓬勃发展是在近二十年取得的，特别是用极大似 然的方法，这是因为d e m p s t e r 关于e m 算法的论文的发表极大地激起了研究者用 有限混合模型建模的兴趣。e m 算法把数据看成是不完全的( i n c o m p l e t e ) ，从而 使得用m l 方法拟合有限混合模型这个复杂的问题极大地简化为两步( 即期望e 步和最大化m 步) 迭代问题，而且在很弱的条件下是收敛的。事实上，1 9 7 8 年 之后有关混合模型的应用几乎都牵扯到e m 算法。 在数学上，有限混合模型的原型可以描述如下： 设x = x ，x ：，x ，) 为随机观察数据集，置是d 维随机变量，墨间相互独 立，暑 i q ) ( f = 1 ，2 ，m ) 是对应的概率密度函数，其中，x 是墨的取值， 只0 ，c 舻是参数。若将x 的样本按一定比例混合后，再从中任取一个进行观 察，其结果记为x ，则随即变量x 服从混合分布，它的概率密度为 p ( z 2 酗只o l q ) x 月。 3 _ d 其中q 是混合比例( m i x i n gp r o p o r t i o n ) 或权重( w e i g h t ) ，满足 q o ，荟a ；。1 ；口= ( 口，口z ，。，磅，) 7 ，口。， 。 ( 口：，矸，谚，- ，n 薹q “以。，谚 ，f = 1 z ，历) 。这样建立的 模型( 3 一1 ) 称为概率混合模型，也称为混合模型。日是模型的参数空问，胁表 示混合模型的分支数目，若当分量密度函数只o i 谚) 的分布形式确定了模型就成 为该分支的混合模型，而( 3 一1 ) 称为一个m 一分支的混合密度函数。 在有限混合模型公式( 3 1 ) 中，分支数m 一般考虑是固定的，但在大多数 应用中，小的值却是未知的，它往往需要同混合比和其它确定各分支密度的参数 一道从样本中去推断，这涉及到下文介绍的混合密度估计问题，这也是本文研究 的重点。 3 2 有限混合模型密度估计的极大似然方法 设x 是属于给定的混合密度参数族p 的一个随机变量，现有关于x 的一组简 单随机样本的观察值。混合密度估计问题就是要根据这些样本观察值建立形如( 3 1 ) 式的混合密度模型，包括确定分支数m 和模型参数口的取值。在大多情况 下，极大似然估计具有诸如强相合性、相合一致渐近正态性以及最优渐近正态性 等优良的大样本特征，因此，无论在理论上还是实际应用中，人们都首先考虑用 极大似然方法估计概率分布中的各参数。对于混合密度参数估计也是如此。 现有关于x 的一组简单随机样本的观察值，记为，屯，其中，t ， f = 1 ，2 ，n 。假设不同的样本之间具有统计的独立性，则 p ( x m p “，戎m p 瓴j 口) ( 3 2 ) 这是一个疗的函数，也称为口关于x 的似然函数。因为对数函数的单调性， 定义对数似然函数为 工( 日) 。1 0 9 玎p ( 畛荟1 。g ( p ( 峨坳 3 用最大似然法( m l ，m a x i 舢ml i k e li h o o d ) 估计口，计算似然函数的最大值， 即求p 0 ，s j l o g ( 口) = m a x l o g l ( 口) ( 3 4 ) 传统上，确定极大似然估计量的方法是首先建立极大似然估计量满足的似然 方程，并通过求解似然方程来获得极大似然估计量。基本上，似然方程的建立是 考虑对数似然函数求关于口的各分量的偏导数。如果 占一( & 。，d ：，d 。，帮，劈，群) 7 是日的极大似然估计，则在q 没有任何约束条件的 条件下，似然方程为 v b l o g l ( 口) 一0 ，f = 1 2 ，m ( 3 5 ) 对于混合比的计算，由于有非负及和为1 的约束，情况就比较复杂。记 a ；( 口1 ，口2 ，) 7 ，由于在固定q 的情况下，l o g p ) 关于口的h e s s i a n 矩阵 也耋7 麦两以以7 ( 其中以。慨“l q ) ，p ：( 屯成) ，以l 以矿) 在约束范 围内是负定的。所以在固定包( f = 1 2 ，m ) 的情况下，西= ( d 。，d ：，d 。) 7 是口 的极大似然估计量的充分且必要条件为所有满足约束条件 卟o ，咿1 ，f = 1 ，2 ，”棚 ( 3 6 ) 的口，有 v 。l ( 占) 7 ( a 一& ) s 0 ( 3 7 ) 其中梯度向钒砸) 。砉志站小( 鹏跏z ：胁，p m 瓴眇口显 然，m 维单位坐标向量己满足关于a 的约束条件，所以有 v 。工( 舀) 7 ( q 一舀) s o ，f = 1 ，2 ，m ( 3 8 ) 即 昙砉 1 f = 1 ，2 ，m ( 3 9 ) 易验证，v 。l ( 占) 7 d = n ，从而由( 3 9 ) 式有 一瓴一瓴只一p d j v 。l ( 占) 7 q5 n d ， i = 1 ，2 ，m ( 3 1 0 ) 若( 3 一1 0 ) 中存在某个严格不等号，则对( 3 一l o ) 关于i 求和有 n = v 。l ( 每) 7 舀= 薹喀v 。l ( 占) 7 q cn 砉喀= n ，f = 1 ，2 ，m 矛盾a 所以( 3 1 0 ) 式可修改为 d f v 。( 占) 7 q 口n d f f 口1 ，2 ，肌 ( 3 一1 1 ) 这等价于在( 3 9 ) 中，对于所有使口j o 的i 等号成立。又由( 3 1 1 ) 得 嘻。三守 ，l 舟 f 一1 ，2 ，棚( 3 1 2 ) 最大似然估计的确有一些可取之处。但是由于未知参数以非线性形式出现在 极大化中，导致计算困难。困难的原因是缺乏已知训练样本的类标签，即混合体 重的每一个样本所属的类。如