EM算法

jopen 8年前

我们知道在机器学习中，很多时候问题都可以归结为一个最优化问题，而要解决这个最优化问题只需要求解出模型参数即可。大多数时候，只要给定数据可以直接用极大似然估计法估计模型参数。但是当模型里含有隐变量的时候，直接求解参数的极大似然估计就会失效。这时就需要用到EM算法来对参数进行迭代求解。EM算法说白了也是求参数的极大似然估计，只不过它解决的问题是含有隐变量的模型参数的极大似然估计。

EM算法是一个十分重要且广泛应用的算法，因为有相当一部分模型实际上是存在隐变量的，比如混合模型（高斯混合模型，伯努利混合模型），训练推理主题模型（topic model）时的pSLA等等。

我们首先通过一般性的推理来了解什么是EM算法，然后通过高斯混合模型作为例子来阐释EM算法。

我们知道，EM算法的目标是对于含有隐变量的模型求出模型参数的极大似然估计。我们假设可观测变量的集合为X，隐藏变量的集合为Z，模型参数用W表示。因此，相应的对数似然函数为：

（1）

上式中等式左右两端用到了联合概率分布和边缘概率分布之间的一个转换，即：

（2）

从（1）式中我们可以看出，式中的求和符号是很“讨厌的”，它使得对数符号无法作用于联合概率密度函数上，这就使得求解参数W的极大似然估计变得复杂了。究其原因还是隐变量Z的引入，从而使得（1）式右边必须对Z求和，如果去掉隐变量，那么就变成了一般情况下的参数极大似然估计，这就很容易求解了。

对于X和Z，如果X对应的Z都是已知的，那么我们称{X,Z}为完全数据，在这种情况下由于Z已知，那么求解参数W的极大似然估计是相对容易和直接的。

但实际上问题中的Z往往是未知的，我们所知道的隐变量Z的信息只有它的后验概率P(Z|X,W)。由前面的分析可知，如果知道X和Z，那么求解完全数据{X, Z}的对数似然函数logp(X,Z|W)的参数W是容易的，但是我们现在只知道Z的后验概率，因此，我们转而求解logp(X,Z|W)在隐变量Z的后验概率下的期望值，而这就对应了EM算法的E步，即期望（expectation）；在接下来的M步，要做的工作就是极大化（maximum）这个期望。由上可知，如果参数目前的估计值为W^old，那么经过一个E步和M步之后，算法就会得到一个新估计的参数值W^new。

在E步的时候，我们用W^old来得到隐变量Z的后验概率，即p(Z|X,W^old)，接着，算法用得到的后验概率来求出logp(X, Z|W)的期望。由于X已知，Z的后验概率也已知，我们可以理解为X和Z都已知了，因此在求出期望后，就可以像已知完全数据{X,Z}的情况下，直接求解W的极大似然估计，这也对应了M步。期望的公式如下：

（3）

以上公式是由E步得到的，在M步，算法通过极大化期望来得到新一轮的参数估计值W^new。公式如下：

（4）

由（3）式可知，此时对数符号log已经直接作用于X和Z的联合概率密度函数上了，因此在（4）式中计算W的值就容易多了。

接下来将EM算法的步骤做一个总结。

给定X和Z的联合概率分布，该分布带有参数W，即，p(X,Z|W)，目标是要最大化似然函数p(X|W)，也就是要求出W使得p(X|W)最大。

1. 选择参数W的初始值，W^old。

2. E步：利用初始值W^old计算隐变量Z的后验概率分布，p(Z|X,W^old)，进而找出logp(X,Z|W)在Z的后验概率下的期望Q(W,W^old)。

3. M步：极大化Q(W,W^old)，以求出W。

4. 检查收敛条件，如果满足收敛条件则停止；否则，令W^old= W^new，然后跳转到第2步，继续迭代执行。

注意：以上对于EM算法的讨论是假设隐变量Z为离散型随机变量，当Z为连续型随机变量时，上面的讨论依然成立。

接下来我们看看EM算法的一个具体应用：求解高斯混合模型。

高斯混合模型是密度估计里十分常用的模型，如果样本点的分布是单峰的，那么高斯分布能够很好地估计样本点的概率密度，但是如果样本点的分布是多峰的，那么高斯分布不管怎么调整，也无法对样本点做一个很好的估计，这时就需要用到高斯混合模型来估计样本点的概率密度。假设我们接下来要求解的高斯混合模型的隐变量是离散型随机变量。

设随机变量X服从高斯混合分布，其概率密度函数为：

（5）

由上式可知，该高斯混合分布由K个高斯分布的加权线性组合构成，a_k的含义是X为第k个高斯分模型生成的概率，因此X由哪个高斯分模型生成实际上是未知的，也就是“隐藏的”。

下面来推导式（5）。这里定义一个K维的随机变量Z（隐变量），Z的取值特点为：仅有一个元素取值为1，其它K-1个元素取值为0。因此，对于向量Z，可能的取值方式有K种。我们定义p(Z_k= 1) = a_k，满足0 <= a_k<= 1，并且所有a_k的和等于1。由于p(Z_k= 1) = a_k，因此我们可以写出Z的边缘概率密度函数：

（6）

由高斯混合分布的定义可知，给定一个Z的取值，那么X的分布就是一个高斯分布：

（7）

由（7）式可知：

（8）

由于p(X, Z) =p(Z)*p(X|Z)，

(9)

由（9）式：

（10）

至此，由（10）式可知，我们已经推出了（5）式，即高斯混合分布。

下面介绍如何用EM算法来求解高斯混合模型。

假设有N个观测值x⁽¹⁾, x⁽²⁾, … , x⁽ⁿ⁾，每个观测值可以看作是高斯混合分布中的一个分模型产生的，因此每个x⁽ⁱ⁾对应了一个隐变量z⁽ⁱ⁾。下面写出关于p(X)中参数W的似然函数：

（11）

其中W表示高斯混合分布里的所有参数。由于式（11）带有求积符号，因此不太容易求解，一般都是对上式作用log之后，再求解：

（12）

我们的目标是极大化上面这个对数似然函数，由前面对EM算法的一般性分析可知，这里log没有直接作用在高斯分布上，而是在log里还有求和式，这就导致了直接求解式（12）比较麻烦。根据之前的分析，假设我们现在不仅知道观测数据X，也知道隐变量Z，那么我们可以写出p(X,Z)，并写出关于p(X,Z)中参数的对数似然函数。根据式（9），我们得到似然函数如下：

（13）