EM算法的数学原理

摘要

        EM算法主要分为两个步骤：E-step和M-step，主要应用在概率模型中。机器学习中，概率模型在进行参数估计时，我们主要应用的是最大似然估计，所以在对EM算法进行讨论时，是离不开最大似然估计的。EM算法主要是用来解决那些样本中存在隐变量的情况。E-step固定模型参数通过数学模型求解隐变量，M-step根据E-step求得的隐变量在通过最大似然估计最大化似然函数从而求出模型的参数，这样相互的迭代，从而得到模型的局部最优解。EM算法主要应用在聚类算法中，因为一般情况下聚类问题都存在一个隐变量。

什么是隐变量

        样本中存在隐变量即我们在对数据进行采样中，可以认为隐变量是那些我们不能通过数据采样所能确定的属性。如果不存在隐变量，那对于一些聚类模型，我们的参数求解就简单很多，比如k-means，k-means只是利用了EM算法的思想。我们有一批数据，想利用k-means算法来进行聚类分析，对于k-means算法，我们要确定的是k和k个质心，假如我们在对这批数据采样时已经知道他们分为4类，而且采样前就已经把数据给分好类了，已经知道了，还用聚类算法干嘛，我们这是暂时的假设用他来举例说明什么是隐变量，那么我们在用k-means算法时就变得很简单了，直接求出这k个质心，而不用我们所熟知的k-means算法的计算步骤。之所以我们使用我们所熟知的k-means算法的步骤，那是因为我们不知道每个样本应该归属于哪个类以及他们存在多少个聚类中心比较合适。那么这个隐变量就是每一个样本应该归属于哪个类。在举一个例子，高斯混合模型，这个是典型用到了EM算法的思想，如果对这个模型不太清楚，可以网上查资料。同样，我们也有这样一批数据，在采样中，我们就已经知道k和每个样本应该属于哪个类，那么我们所要做的工作就是把每一类数据拿出来，直接通过均值和方差就可以求出每一个高斯函数的模型了，而不需要再进行EM算法通过最大似然估计来计算我们的高斯混合模型参数了。而现实的应用中是我们不知道这样的一批数据应该分为几个类以及每一个样本应该属于哪一个类，那么这就是隐变量。这样的问题和先有鸡还是先有蛋的问题差不多，当我们知道数学模型的参数后，我们就知道了样本应该属于哪个类，同时当我们知道隐变量后，我们也就知道样本属于哪个类，从而得到数学模型的参数，但是不幸的是在开始的时候我们只有样本，隐变量和模型参数都不知道。

凸函数和凹函数以及其性质

为什么要讲这个，因为EM算法得以实施的基础就是函数的凹凸性以及凹凸函数的一些性质。所以这里还是说一下吧。

在高等数学和数学分析(数学专业的书)对于凹凸函数的定义可能有些不一样。这个没有关系只是叫法不同，但是他们这些图形和图形的性质是一样的。

凸函数定义：函数的二阶导函数在一定的区间内大于等于零，性质如下

如下图：

凹函数的定义：函数的二阶导函数在一定的区间内小于等于零，性质如下：

如下图所示：

最大似然估计步骤

因为在概率模型中，进行参数估计一般都采用最大似然估计

1、确定概率模型求出似然函数

2、对似然函数取log，把连乘变为求和

3、对变换后的似然函数求导，并另导数等于0，然后整理得到似然方程组

4、求解似然方程组，得到模型参数

EM算法

假设我们有一批数据样本{x(1),…,x(n)},，样本容量为n，概率模型为p(x,z)来对我们的数据进行拟合。根据概率模型的参数估计算法，我们可以得到似然函数：

上式中（1）我们是通过最大似然估计的步骤获取的，从（1）到（2）引入了样本属于某一个类的概率函数，从而对某一个样本求得该样本属于某个类的全概率公式，即引入了隐变量z。

当我们采用传统的概率模型求解参数的方法即最大似然估计，对上述式子进行求导数，从而得到似然方程：

我们会发现上述似然方程中存在对数，并且对数里面是个求和公式，这种求解是很难得到参数的解析解的。遇到胡同了，我们就要想一下拐一下弯，既然这个公式无法求解的难点在于对数里面有求和公式，那么我们能不能采用什么办法把对数后面的求和号给拿到外面。再看看对数函数的性质是什么样子的？对数函数是一个凹函数那么他肯定满足凹函数的基本性质：

把上式进行变换：

我们的目标函数和凹函数的性质还差那么一点点的差距，那么我们就认为对于每一个实例i，用Qi表示对应于隐含变量即其属于哪个类的概率分布，我们这是对于一个样本而言的，那么样本有n个，就会存在n个这样的Qi的函数分布，一定要把这一点弄明白。这个Qi表示的样本i对应于k个类，其属于这k个类的概率分布。那么Qi应该满足的条件是：

那么我们就可以把我们的似然函数进行改写了：

这样一看就和我们的凹函数性质一致了吧。于是我们可以把上述函数通过凹函数的性质进行变换：

既然原函数无法得到最优解，我们可以通过调整原函数的下界函数，对原函数的下界函数求最大值，从而使原函数逐步逼近最优解或者得到一个局部最优解。即我们不停的求解上式中（4）的最大值，从而是我们原函数逼近最优解。

看到这可能会有一个问题，通过最大似然估计得到的原似然方程无法得到解析解，为什么变成（4）就可以得到了呢？我们在已知隐变量的前提下对模型参数进行求偏导得到的似然方程中，发现log已经不复存，已经变成了我们熟悉的线性方程组或者非线性方程组(这个跟数学模型有关)，一般情况下这个就可以利用线性代数的理论进行求解了啊。

因此EM算法的基本思想就是通过引入隐变量，先得到样本属于某一个类的概率，然后再使用最大似然估计最大化似然函数来求解参数，得到参数以后，数学模型就已经确定，那么我就可以得到样本属于哪个类了，从而得到隐变量的值，因此就用迭代的进行求解最终得到问题的解。当我们引入隐变量后，整个似然函数就会存在两类参数类型：隐变量和数学模型的参数。那么EM算法采用的步骤如下：

E-step: 通过固定数学模型的参数，利用现有样本对隐变量进行参数估计，即求出隐变量的期望也就是我们期望样本属于哪一个类

M-step: 通过E-step求得的隐变量，对数学模型参数求导，最大化似然函数。

隐变量的求解

对于EM算法，我们是不断的逼近最优值，那么E-step计算的是什么呢？因为在凹函数的性质中上述不等式取等号的前提条件是xi为常数

则：

对上式进行求和：

通过上述两个式子我们进行变换得到：

在上式中从（1）到（2）为什么会是这样，我们按照举个例子，用二元一次函数的积分问题来看待这个问题的推导，因为积分的实质也是一种求和对函数下部的面积进行无线的拆分然后再求和。如下式的二元函数：

然后我们对上面的二元一次函数对y进行求积分：

从而消除了变量y，同样的道理，从（1）到（2）的过程中，我们分母对样本i的所有的可能隐变量取值求和，从而把隐变量z给消除，从而得到公式（2）从（2）到（3）是通过条件概率的公式得到的。因此我们可以发现隐变量其实就是在固定数学模型参数和已知数据样本的情况下的后验概率。

以上只是理论部分，下面我们简单说一下EM算法的实际应用。

在实际应用中我们不会按照上面公式来推导我们的算法。我们只知道两个点就可以了：隐变量的求解和已知隐变量的前提下最大化似然函数从而来求解数学模型的参数。

隐变量的求解：我们已经知道其是样本和数学模型参数的后验概率，那么我就可以根据实际的情况来推导计算这个后验概率从而得到我们的隐变量和参数的关系表达式从而用于迭代求解即为E-step

最大化似然函数：这个是我们最大似然估计算法的步骤了即M-step。

---能力有限，存在不对的地方，望请指教。