EM

chwang@microsoft.com

注意：这是一个非正式的简介，所以没有列出相关的参考文献，以后我会陆续完善。写EM简介的文章很多，我这里希望能对初学者有所帮助。水平有限，如有错误，敬请指正。

Expectation-Maximization (EM) 算法是一个在含有隐含变量的模型中常用的算法，最常见的是用于高斯混合模型 (Mixtures of Gaussians), 但EM算法的应用决不仅仅限于此 。

假设我们要估计联合概率密度݌ሺ࢞,࢟|ࢶሻ，其中࢞为可以观测的变量，࢟为隐含变量，઴为参数。令计(Maximum Likelihood),也就是最大化下面式子: 写的更一般一些，可以为：

ሼࢄ,ࢅሽൌሼሺ࢞ଵ,࢟ଵሻ,…,ሺ࢞ே,࢟ேሻሽ。ሺ࢞௜,࢟௜ሻ,݅אሼ1,2,…,ܰሽ是相互独立的。给定ࢄ，考虑઴的最大似然估ࣦሺ઴|ࢄሻൌlog∏௜݌ሺ࢞௜|઴ሻൌ∑௜log݌ሺ࢞௜|઴ሻൌ∑௜݈݋݃∑࢟೔݌ሺ࢞௜,࢟௜|઴ሻ .

ࣦሺ઴|ࢄሻൌlog݌ሺࢄ|઴ሻൌlog∑ࢅ݌ሺࢄ,ࢅ|઴ሻ 。如果ࢅ是连续变量，ࣦሺ઴|ࢄሻൌlog׬݌ሺࢄ,ࢅ|઴ሻ݀ࢅ

基本的EM算法：

假设ࢅ可观测，那么ࣦሺࢶ|ࢄ,ࢅሻൌlog݌ሺࢄ,ࢅ|઴ሻ, 通常来说比较容易求解，特别是如果݌ሺࢄ,ࢅ|઴ሻ是指数族的情况下。

定义ܳ函数: ܳሺ઴,઴௢௟ௗሻൌܧ௣ሺࢅ|ࢄ,઴೚೗೏ሻሾࣦሺࢶ|ࢄ,ࢅሻሿ E-step：Compute ݌ሺࢅ|ࢄ,઴௢௟ௗሻ M-step: ઴୬ୣ୵ൌargmax઴ܳሺ઴,઴௢௟ௗሻ

上述的EM算法虽然描述简单，但不是很直观，下面从另外一个角度来导出EM算法。 从优化的角度导出的EM算法： 首先介绍Jensen不等式:

假设݂ሺ࢞ሻ为凸函数函数（对于凹函数，不等号方向相反），（对于二阶可导的情况，可以考虑证明

ᇱ

Hessian矩阵是非负定的，一维情况݂ᇱሺݔሻ൒0）, 对于随机变量ࢄ,有

可以证明每次EM都可以使得ࣦሺ઴|ࢄሻ增加，保证收敛到局部极大值。

恒成立，等号成立当且仅当ࢄൌܧࢄ, 以概率1成立（ࢄ是常数）。如图1所示。

ܧሾ݂ሺࢄሻሿ൒݂ሺܧࢄሻ

本页已使用福昕阅读器进行编辑。福昕软件（Ｃ）２００５－２００７，版权所有，仅供试用。

图1. 凸函数

很容易验证log ሺݔሻ是凹函数。由于直接优化ࣦሺ઴|ࢄሻൌlog݌ሺࢄ|઴ሻൌlog∑ࢅ݌ሺࢄ,ࢅ|઴ሻ很难，考虑ࣦሺ઴|ࢄሻ的下界，假设ݍሺࢅሻ为任意概率密度：

ࢅ

ࣦሺ઴|ࢄሻൌlog෍݌ሺࢄ,ࢅ|઴ሻൌlog෍ݍሺࢅሻ

ࢅ

݌ሺࢄ,ࢅ|઴ሻ݌ሺࢄ,ࢅ|઴ሻൌlogܧ௤ሺࢅሻ൤൨

ݍሺࢅሻݍሺࢅሻ由Jensen不等式:

等号成立当且仅当

௣ሺࢄ,ࢅ|઴ሻ௤ሺࢅሻ这就是在基本EM算法中的E-step。 而M-step则变为:

઴

୬ୣ୵

ൌܧ௤ሺࢅሻቂ

logܧ௤ሺࢅሻ൤

௣ሺࢄ,ࢅ|઴ሻ௤ሺࢅሻ݌ሺࢄ,ࢅ|઴ሻ݌ሺࢄ,ࢅ|઴ሻ൨൒ܧ௤ሺࢅሻ൤log൨

ݍሺࢅሻݍሺࢅሻቃൌ ݌ሺࢄ|઴ሻൌܿ݋݊ݏݐܽ݊ݐ, 所以有ݍሺࢅሻൌ ݌ሺࢅ|ࢄ,઴ሻ。可见，

总结，考虑最大化ࣦሺ઴|ࢄሻ下界ܧ௤ሺࢅሻቂlog并且 ݍ௡ሺࢅሻൌ ݌ሺࢅ|ࢄ,઴࢔ሻ有：

࢔ା૚

݌ሺࢄ,ࢅ|઴כሻ݌ሺࢄ,ࢅ|઴כሻൌargmax઴כlogܧ௤ሺࢅሻቈ቉ൌargmax઴כܧ௤ሺࢅሻ൤log൨

ݍሺࢅሻݍሺࢅሻ௣ሺࢄ,ࢅ|઴ሻ௤ሺࢅሻࣦሺ઴|ࢄሻ的问题。利用Jensen也很容易证明ࣦሺ઴|ࢄሻ是递增的。假设઴௡,઴௡ାଵ为迭代第݊,݊൅1的值,ࣦሺ઴

݌ሺࢄ,ࢅ|઴࢔ା૚ሻ|ࢄሻൌlogܧ௤೙ሺࢅሻቈ቉

ݍ௡ሺࢅሻቃൌ∑ࢅݍሺࢅሻlog

௣ሺࢄ,ࢅ|઴ሻ௤ሺࢅሻ的问题，从而解决了最大化

݌ሺࢄ,ࢅ|઴࢔ା૚ሻ൒ܧ௤೙ሺࢅሻቈlog቉

ݍ௡ሺࢅሻ݌ሺࢄ,ࢅ|઴࢔ሻ൒ܧ௤೙ሺࢅሻ൤log൨

ݍ௡ሺࢅሻൌࣦሺ઴࢔|ࢄሻ

上式中第一个不等式是由于Jensen不等式，第二个是由于M-step求最大的性质。

有些时候，ݍሺࢅሻൌ ݌ሺࢅ|ࢄ,઴ሻ也不是能够显示的计算出来的，这个时候最大化ࣦሺ઴|ࢄሻ就显得相当困难。这个时候，可以考虑不一定保证Jensen不等式一定取等号。如果给定ݍሺࢅሻ某种形式，就得到Variational EM算法。 To be continued …