EM算法简介.ppt

EM算法简介 尤全增ultimateyou 1 提纲 算法介绍EM算法GEM算法性质EM算法解释EM不足及改进 2 EM算法介绍 EM expectation maximization 算法是Dempster Laird和Rubin DLR 三个人在1977年正式提出的 主要是用于在不完全数据的情况下计算最大似然估计 在EM算法正式提出以来 人们对EM算法的性质有更加深入的研究 并且在此基础上 提出了很多改进的算法 在数理统计 数据挖掘 机器学习以及模式识别等领域有广泛的应用 3 问题提出 给定一些观察数据y 假设y符合如下的高斯分布需要求出混合高斯分布的三组参数 4 问题简化 该混合高斯分布一共有K个分布函数 对于每一个观察到的样本y 如果知道它是属于K中的哪个分布 那么求这些参数就会变得很简单 假如我们用来表示这些高斯分布 那么我们的样本集中不仅仅是 而是 5 隐藏变量 由于实际问题中我们往往不知道每个y属于哪个分布 我们观察不到z z是一个隐藏变量 引入变量Z 其中取值为0或1表示Z的第k个分量为1 其它分量为0 并且 于是Z 1 6 引入隐藏变量后的高斯分布 将Z引入后 2 最终得到Z 3 7 EM算法 首先引入如下变量定义两个样本空间X和Y 其中X是完整数据空间 Y是观察数据 即incompletedata 令Z表示添加数据那么X Y Z 参数集合 表示观察后验概率密度函数 表示添加数据Z后得到的后验密度函数 表示给定数据 和观察数据y下x的条件密度函数 8 EM算法 根据上面定义 4 定义似然函数 5 根据 4 式可知 6 定义函数 7 9 EM算法 定义函数 8 则有 4 5 7 式可得 9 10 EM算法 目的 计算后验分布的众数 EM算法如下进行记为第i 1次迭代开始时参数的估计值 则第i 1次迭代的两步为 E step计算M step最大化 即 重复上面两个步骤直至或充分小时 停止 11 EM例子 有公式 1 3 以及贝叶斯公式可得 其中N表示观察样本数 公式中是未知的 需要求出它的期望 12 的期望估计 13 用代替 将代入下面就应该使改式最大 也就是期望最大化 14 迭代描述 在迭代过程中我们需要不断的根据后验概率 Start 15 GEM算法 DLR提出GEM算法 GeneralEM EM的M step可能比较复杂M step定义映射满足 M步可以描述为令即 16 GEM算法性质 引理1 定理1 GEM算法满足其中 等号成立当且仅当几乎处处成立 推论1 假设存在一些并且 那么有几乎处处成立 17 GEM算法性质 推论2 对于一些 其中 那么对于GEM算法有定理2 假设是GEM算法的一个迭代序列 并且满足在闭包中收敛到 负定的 并且特征值都远离0 那么是负定的 并且 18 GEM算法收敛性质 定义 是参数 的局部最优点集 是参数 的稳定点集 定理3 设 是GEM的一个迭代序列 即并且满足M是在 的补集上是封闭的 那么 的极限是L的稳定点 并且存在一些稳定点 使得单调收敛到即对于EM算法来说满足条件a 的一个充分条件是在 和 上都是连续的 将定理中的 换为 相应定理也成立 19 GEM算法性质 定理4 假设Q函数是连续的 并且 是EM算法的一个迭代序列 那么有的极限是L的稳定点 存在稳定点使得L单调收敛到即 定理5 假设Q函数是连续的 并且对于成立 那么有若 是EM算法的一个迭代序列 那么收敛到L的局部极值点 存在局部极值点使得L单调收敛到即 注当收敛到并不意味着序列 收敛到 更多讨论参考Wu C F J 1983 OntheconvergencepropertiesoftheEMalgorithm 20 EM算法的解释 一 EM算法的直观解释是 1 如果缺失数据是已知的 就可以利用已知的完全数据处理技术对模型的未知参数进行估计 2 如果模型的参数已知 根据模型我们可以推导出缺失数据的值 21 EM算法的解释 二 下界极大化 LowerBoundMaximization E step构造后验分布的局部下界 M step优化这个下界 TomasP Minka 1998 Expectation Maximizationaslowerboundmaximization Neal R andHintonG 1998 AviewoftheEMalgorithmthatjustifiesincremental sparse andothervariants 22 EM算法缺点 EM主要缺点收敛速度慢 算法高度依赖初始值的选择 23 EM算法改进 一 EM算法收敛速度假设 设 那么由于满足 因此当 0时 有根据上式可知EM算法是线性收敛到 24 EM改进 一 艾特金 Aitken 假设 当k 那么有 10 因而 11 将 11 式带入 10 式可得 其中所有的特征值在0 1 12 25 EM改进 一 根据 12 式 13 Jamshidian和Jenrish 1993 指出Aitken方法等价于运用Newton Raphson方法来找的根 13 式可以改写为由于的梯度是 故上式表示运用Newton Raphson公式来求的根 26 EM算法改进 一 其它改进算法 1 PX EMCLiu DBRubinandWu 1997 ParameterExpansiontoAccelerateEM thePX Emalgorithm 2 XliMeng DBRubin 1993 MaximumlikelihoodestimationviatheECMalgorithm Ageneralframework 3 CLiu DBRubin 1994 TheECMEalgorithm AsimpleextensionofEMandECMwithfastermonotoneconvergence 27 EM算法改进 二 关于初始点的选择初始值的获取可以通过k means算法 层次聚类算法或者是对数据进行随机的分割 1 重复利用EM CEM和SEM进行初始点的选择 2 1 McLachlan G J andNg S K 2008 TheEMalgorithm 2 ChristopheBiernachi GillesCeleux GerardGovaert 2003 ChoosingstartingvaluesfortheEMalgorithmforgetting