Lecture 10:Expectation-Maximization (EM) 张伟平 Monday 16th November,2009
Lecture 10: Expectation-Maximization (EM) ê{ ‹ï² Monday 16th November, 2009
Contents 1 EM optimization method 1.1 EM algorithm........···.·..···.· 2 l.2 Convergence..:·。。··.·····。······ 15 l.3 Usage in exponential families·.:.......·.· 19 l.4 Usage in finite normal mixtures...·..····.···· 20 1.5 Variance estimation 23 1.5.1 Louis method..... 24 1.5.2 SEM algorithm . 28 1.5.3 Bootstrap method.. 36 1.5.4 Empirical Information 37 1.6 EM Variants . 444444 38 l.6.1 Improving the E step:...·。.。·。.··· 38 1.6.2 Improving the M step 4+。·4。·。4.4。·。。。· 39 1.7 Pros and Cons.····.············· 。4 40 Previous Next First Last Back Forward 1
Contents 1 EM optimization method 1 1.1 EM algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3 Usage in exponential families . . . . . . . . . . . . . . . . . 19 1.4 Usage in finite normal mixtures . . . . . . . . . . . . . . . . 20 1.5 Variance estimation . . . . . . . . . . . . . . . . . . . . . . 23 1.5.1 Louis method . . . . . . . . . . . . . . . . . . . . . . 24 1.5.2 SEM algorithm . . . . . . . . . . . . . . . . . . . . . 28 1.5.3 Bootstrap method . . . . . . . . . . . . . . . . . . . 36 1.5.4 Empirical Information . . . . . . . . . . . . . . . . . 37 1.6 EM Variants . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.6.1 Improving the E step . . . . . . . . . . . . . . . . . . 38 1.6.2 Improving the M step . . . . . . . . . . . . . . . . . 39 1.7 Pros and Cons . . . . . . . . . . . . . . . . . . . . . . . . . 40 Previous Next First Last Back Forward 1
Chapter 1 EM optimization method 期望-最大化(EM)算法是一种在观测到数据后，估计未知参数的迭代优化方 法.其能非常简单地执行并且能够通过稳定，上升的步骤非常可靠地找到全局 最优值.对EM方法详细介绍请参考非常好的教材McLachlan and Krishnan, 1997,EM algorithm and extensions,Wiley. 在频率概率框架下，我们可以认为：除了观测到的样本X外，还有一些与 之伴随的未知的缺失量(missing)或者没有观察到的量Z.那么，完整的样本 应该是Y=(X,Z).问题的目的是在得到观测的样本x后，最大化似然函 数L(x)=∫f(x,z旧)dz.此似然函数由于涉及到边际概率函数一般难以处 理，而采用f(x,旧)和f(zx,)则可能容易处理，EM算法就是通过采用这些较 容易的密度而避免直接考虑L(x): Previous Next First Last Back Forward
Chapter 1 EM optimization method œ"-Ååz(EM)é{¥ò´3*ˇÍ‚, OôÎÍSì`zê {. Ÿ Uö~{¸/â1øÖU œL½,˛,⁄½ö~åÇ/È ¤ Å`ä. ÈEMê{ç[0 ûÎö~–· McLachlan and Krishnan, 1997, EM algorithm and extensions, Wiley. 3™«V«µee, ·Çå±@è:ÿ *ˇ X , Ñkò Ü Éäëô "î˛(missing)½ˆvk* ˛Z. @o, AT¥Y = (X, Z). ØK8 ¥3*ˇ x, Ååzq,º ÍL(θ|x) = R f(x, z|θ)dz. dq,ºÍ du9>SV«ºÍòÑJ±? n, Ê^f(x, z|θ)⁄f(z|x, θ)KåUN¥?n, EMé{“¥œLÊ^˘ N¥ó› ;ù܃L(θ|x). Previous Next First Last Back Forward 1
另外，在Byes理论框架下，感兴趣的通常是对后验概率函数f(0x)最大化， 以后验众数（似然思想）来估计参数.此时，最优化问题有时可以通过考虑引入 一个未观测的参数而得到简化 有时候，缺失数据Z并非真正的缺失了，它们可能仅仅是为了简化我们的问 题而引入的变量.此时，Z常常被称为隐变量(latent variable) 1.1 EM algorithm 记可观测的量为X,缺失量为Z,完全数据为Y=(X,Z),待估参数为8.则 我们有的信息是观测数据的似然L(x),最大化此似然或者说是求的极大 似然估计是我们的目标.EM算法通过迭代方式来寻求最大化L(x)的解.假 设0（表示在第t次迭代后的最大值点，t=0,1,2,··.定义Q(8)为在观测 到X=x,以及在参数0=)的条件下完全数据的联合对数似然函数的期望： 此期望是对f21x(zx,8()计算.即 Q(0l0())=EflogL(0Y)I,0()} Previous Next First Last Back Forward 2
, , 3Bayesnÿµee, a,œ~¥ÈV«ºÍf(θ|x)Ååz, ±ØÍ(q,gé)5OÎÍ. dû, Å`zØKkû屜Lƒ⁄\ òáô*ˇÎÍψ {z. kûˇ, "îÍ‚Zøö˝"î , ßÇåU==¥è {z·ÇØ K ⁄\C˛. dû, Z~~°è ¤C˛(latent variable). 1.1 EM algorithm På*ˇ˛èX, "î˛èZ, Í‚èY = (X, Z), ñÎÍèθ. K ·Çk&E¥*ˇÍ‚ q,L(θ|x), Ååzdq,½ˆ`¥¶θ4å q,O¥·Ç8I. EMé{œLSìê™5œ¶ÅåzL(θ|x)). b θ (t)L´31tgSìÅåä:, t = 0, 1, 2, · · · . ½¬Q(θ|θ (t) )è3*ˇ X = x,±93ÎÍθ = θ (t)^áe Í‚È‹ÈÍq,ºÍœ", dœ"¥ÈfZ|X(z|x, θ(t) )Oé. = Q(θ|θ (t) ) = E{logL(θ|Y )|x, θ(t) } Previous Next First Last Back Forward 2
Eflogf(,Z10)r,0() logf(z,210)f(0())dz 最后一式强调一旦我们给定了X=x,Z就是Y唯一的随机部分 EM算法从8(O)开始，然后在两步之间交替：E表示期望，M表示最大化.该 算法概括如下： (1)E步：计算Q(ee)=EL(0Y)z.9)1 (2)M步：关于0最大化Q((t).并记9(+1)表示此时的最大值点 (3)返回到E步，直至收敛准则达到 例1椒花蛾(peppered moth)一个进化和工业污染的例子. 白桦尺蛾(peppered moth),麟翅目(Lepidoptera)尺镀科(Geometridae)昆 虫，学名Biston betularia.翅黑或白色，上有斑点，分布欧洲.其生命周 期有四个阶段：卵，毛毛虫.前.成虫.在由蛹变为成虫的时刻，它们会停留 在树干上完成此过程，此时就会被鸟类捕食.1848年，在英国曼彻斯特首 次注意到黑色型，到1898年黑色型反而以99：1的比例超过了淡色型.对这 种现象的解释是：工业区的树干被煤烟染黑，黑色的蛾栖于树上，目标不显 著，不易为鸟类捕食.这是通过工业黑化现象进行自然选择的一个例子. 一百度百科 Previous Next First Last Back Forward 3
= E{logf(x, Z|θ)|x, θ(t) } = Z logf(x, z|θ)f(z|x, θ(t) )dz Åò™rNò·Çâ½ X = x, Z“¥Y çòëÅ‹©. EMé{lθ (0)m©, ,3¸⁄ÉmO: EL´œ", ML´Ååz. T é{V)Xe: (1) E⁄: OéQ(θ|θ (t) ) = E[L(θ|Y )|x, θ(t) ]. (2) M⁄: 'uθÅåzQ(θ|θ (t) ), øPθ (t+1)L´dûÅåä:. (3) à£E⁄, Üñ¬ÒOKà. ~1 ˛sˇ(peppered moth) òá?z⁄Ûí¿/~f. x ºˇ(peppered moth),º8(Lepidoptera)ºˇâ(Geometridae)& £, ƶBiston betularia. ºÁ½x⁄, ˛kÄ:, ©ŸÓ³. Ÿ)·± œkoá „: Œ, ff£, W, §£. 3dWC解ûè, ßÇ ¨ 3 3‰Z˛§dLß, dû“¨ja”†. 1848c, 3=I˘îdA ƒ g5øÁ⁄., 1898cÁ⁄.á ±99:1'~áL ⁄.. È˘ ´yñ)º¥: Ûí´‰ZuÎ/Á, Á⁄ˇ—u‰˛, 8Iÿw Õ, ÿ¥èja”†. ˘¥œLÛíÁzyñ?1g,¿Jòá~f. —–z›zâ Previous Next First Last Back Forward 3