EM算法

Published: 30 Oct 2012 Category: 理论及算法

上一节中介绍了Em算法在混合高斯模型中的使用，这一节中介绍的是更概括的EM算法，上节中的算法是这里介绍的一个特例。

1 Jensen不等式

如果f是个凹函数，令X是一个随机变量，则E[f(x)]>=f(EX).

同理，对于凸函数，则E[f(x)]=< f(EX).

对于一个训练集X，有一个模型P(x,z|?)，只能观察到x，希望获得参数?使训练集的极大似然估计最大：

????

由于z是未知的，所以找到极大似然估计比较困难，但是如果z是已知的，就比较简单了。

EM算法的思想是直接使l(?)可能比较困难，那我们首先重复的构建l的下界（E-step），然后找到下界的最优值(M-step)。

对于每个样本xi，令Qi为z的分布。则：

????

第二步到第三部使用了jensen不等式。这样就得到了(3)式中的不等式。

对于(3)式，任何分布Qi都给出了l(?)的下界。如果已经给定了参数?，若使(3)式中的不等式为等号，则下界和函数l相切。即获得jensen不等式中的等号，则令

（常数）

因此，我们根据(3)式选择了一个较好的Qi，这是步骤E。

在步骤M中，我们给定Qi根据参数?最大化(3)式，获得了一个新的参数?。

重复步骤E和步骤M，就是EM算法：

EM算法可以下图表示：首先随机设定一个?0，然后找到函数l(?)的下界，这是步骤E。然后在下界中找到最大值获得参数?1。以此类推就可以获得l(?)的最大值。

可以这么理解，定义函数J(?,Q)为l(?)的下界：

为求出l(?)的最大值，在步骤E中，?不变，改变Q使J(?,Q)最大。在步骤M中，Q不变，改变?使J(?,Q)最大。

注：为什么使用EM算法而不是直接求出l(?)的最大值呢，因为EM算法中的所有表达式都是可以计算的，而无法计算l(?)的最大值。

在步骤E中，我们仅需要计算：

由贝叶斯规则可以进一步的得出：

根据我们的假设，x|z=j~N(u, ∑),z~Multinomial(φ)，就可以计算出上式结果。

在步骤M中，我们需要根据参数φ,u和 ∑使下式最大化

只要针对三个参数分别求出使上式取最大值的参数即可。如计算u时只要求上式导数并置为0即可。具体的求解步骤这里不详述。

在朴素贝叶斯中，我们的训练集是已经被分类好的，而我们用朴素贝叶斯分类器对一个新的对象进行分类。

而在聚类中，我们不知道训练集的分类，比如Google中的news模块，他是对所有最新抓到的news网页进行聚类，每一类中选一个news进行推荐。我们称为混合朴素贝叶斯。

训练集X={x(1), x(2).. x(m)}，x(i)={0,1}^n。x(i,j)表示第j个单词出现在文档i中。

Z(i)={0,1}，我们假设只有两个分类。

，,和。

初始化：随机设置参数。

以下公式是根据EM算法的公式进行推导得到的，和朴素贝叶斯的推导过程应该是一样的。

E-step:

M-step:

E-step: