数据挖掘领域十大经典算法之—EM算法

http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html

http://blog.csdn.net/zouxy09/article/details/8537620

觉得他们写的非常好，可以参考，下面的内容也是自己看完了之后的一个整理的过程：

1 最大似然概率

   例子是说测量校园里面同学的身高分布，分为男生和女生，分别抽取100个人…具体的不细讲了，参考文档中讲得很详细。假设他们的身高是服从高斯分布的。但是这个分布的均值u和方差∂²我们不知道，这两个参数就是我们要估计的。记作θ=[u, ∂]^T。

      我们独立地按照概率密度p(x|θ)抽取100了个（身高），组成样本集X，我们想通过样本集X来估计出未知参数θ。这里概率密度p(x|θ)我们假设是是高斯分布N(u,∂)的形式，其中的未知参数是θ=[u, ∂]^T。抽到的样本集是X={x₁,x₂,…,x_N}，其中x_i表示抽到的第i个人的身高，这里N就是100，表示抽到的样本个数。那么

我同时抽到这100个男生的概率就是他们各自概率的乘积了。就是从分布是p(x|θ)的总体样本中抽取到这100个样本的概率，也就是样本集X中各个样本的联合概率，用下式表示：

X就是我们的样本是测量值，所以是已知的，那么这个式子就是表示在θ参数的情况下抽取得到这个样本集的概率，这里L(θ)就是参数θ相对于样本集的似然函数（likehood function）

似然函数这里我觉得可以理解为，X样本集代表一个目标函数或者是一个事实，现在的目标就是通过调整θ参数使这个样本出现的概率最大。这是一个反推的过程就是已经知道一个结果，那么就是找到出现这个结果的最大概率。

θ的最大似然估计量，记为：

有时，可以看到L(θ)是连乘的，所以为了便于分析，还可以定义对数似然函数，将其变成连加的：

下面剩下的问题就是对函数求极值， 怎么求一个函数的最值？当然是求导，然后让导数为 0 ，那么解这个方程得到的 θ 就是了（当然，前提是函数 L( θ )连续可微 ）。那如果 θ 是包含多个参数的向量那怎么处理啊？当然是求 L( θ )对所有参数的偏导数，也就是梯度了，那么 n 个未知的参数，就有 n 个方程，方程组的解就是似然函数的极值点了，当然就得到这 n 个参数了。

求最大似然函数估计值的一般步骤：

（1）写出似然函数；

（2）对似然函数取对数，并整理；

（3）求导数，令导数为0，得到似然方程；

（4）解似然方程，得到的参数即为所求；

这里需要注意的是，这里的参数只是对应了一个类别，也就是说男生，女生身高的问题，就是在已知这一群人都是男生的情况下，获得这个类别的参数，或者都是女生的情况下获得。如果两个类别混在一起，那么就是下面的EM估计了。

二 EM算法

 EM出现的原因就是抽取的样本不知道是哪个分布抽取的。例如刚开始的最大似然所说的，但现在两种高斯分布的人混在一块了，我们又不知道哪些人属于第一个高斯分布，哪些属于第二个，所以就没法估计这两个分布的参数。反过来，只有当我们对这两个分布的参数作出了准确的估计的时候，才能知道到底哪些人属于第一个分布，那些人属于第二个分布。所以这里就是说EM估计就是因为多了一个隐含变量（抽取得到的每个样本都不知道是从哪个分布抽取的）使得本来简单的可以求解的问题变复杂了。

这里简单的思路就是先初始化隐含变量，然后估计出每个类别对应的分布参数。然后再根据这个分布参数去调整每个样本的隐含参数，依次迭代。。。至于为什么最后能够迭代成功，就是因为在后面的似然函数的证明中可以证明似然函数最后就是一个单调函数

三 EM算法的推导：

给定的训练样本是，样例间独立，我们想找到每个样例隐含的类别z，能使得p(x,z)最大。p(x,z)的最大似然估计如下：

      第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z求联合分布概率和。

但是直接求一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。也就是说我们的目标是找到适合的θ和z让L(θ)最大。

      EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化，我们可以不断地建立的下界（E步），然后优化下界（M步）。这句话比较抽象，看下面的。

      对于每一个样例i，让表示该样例隐含变量z的某种分布，满足的条件是。（如果z是连续性的，那么是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。

可以由前面阐述的内容得到下面的公式：

   是多了一个未知的变量而已啊，我也可以分别对未知的θ和z分别求偏导，再令其等于0，求解出来不也一样吗？但是可以看到里面有“和的对数”，求导后形式会非常复杂（自己可以想象下log(f₁(x)+ f₂(x)+ f₃(x)+…)复合函数的求导），所以很难求解得到未知参数z和θ。那OK，我们可否对（1）式做一些改变呢？我们看（2）式，（2）式只是分子分母同乘以一个相等的函数，还是有“和的对数”啊，还是求解不了，那为什么要这么做呢？咱们先不管，看（3）式，发现（3）式变成了“对数的和”，那这样求导就容易了。我们注意点，还发现等号变成了不等号，为什么能这么变呢？这就是Jensen不等式（就是对凹函数的公式: f(E[X]>=E[f(X)])）的大显神威的地方。

（1）到（2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（3）利用了Jensen不等式，考虑到是凹函数（二阶导数小于0），而且

      就是的期望（回想期望公式中的Lazy Statistician规则）

      对应于上述问题，Y是，X是，是，g是到的映射。这样解释了式子（2）中的期望，再根据凹函数时的Jensen不等式：

可以得到（3）。

    OK，到这里，现在式（3）就容易地求导了，但是式（2）和式（3）是不等号啊，式（2）的最大值不是式（3）的最大值啊，而我们想得到式（2）的最大值，那怎么办呢？

      现在我们就需要一点想象力了，上面的式（2）和式（3）不等式可以写成：似然函数L(θ)>=J(z,Q)，那么我们可以通过不断的最大化这个下界J，来使得L(θ)不断提高，最终达到它的最大值。

     见上图，我们固定θ，调整Q(z)使下界J(z,Q)上升至与L(θ)在此点θ处相等（绿色曲线到蓝色曲线），然后固定Q(z)，调整θ使下界J(z,Q)达到最大值（θ^t到θ^t+1），然后再固定θ，调整Q(z)……直到收敛到似然函数L(θ)的最大值处的θ*。这里有两个问题：什么时候下界J(z,Q)与L(θ)在此点θ处相等？为什么一定会收敛？

      这个过程可以看作是对求了下界。对于的选择，有多种可能，那种更好的？假设已经给定，那么的值就决定于和了。我们可以通过调整这两个概率使下界不断上升，以逼近的真实值，那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于了。按照这个思路，我们要找到等式成立的条件。根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值，这里得到：

      c为常数，不依赖于。对此式子做进一步推导，我们知道，那么也就有，（多个等式分子分母相加不变，这个认为每个样例的两个概率比值都是c），那么有下式：

      至此，我们推出了在固定其他参数后，的计算公式就是后验概率，解决了如何选择的问题。这一步就是E步，建立的下界。接下来的M步，就是在给定后，调整，去极大化的下界（在固定后，下界还可以调整的更大）。那么一般的EM算法的步骤如下：

      那么究竟怎么确保EM收敛？假定和是EM第t次和t+1次迭代后的结果。如果我们证明了，也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。证明过程就先省略了

感性的说，因为下界不断提高，所以极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。理性分析的话，就会得到下面的东西：

四、EM算法另一种理解

坐标上升法（Coordinate ascent）：

       图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。

       这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步：固定θ，优化Q；M步：固定Q，优化θ；交替将极值推向最大。

五、EM的应用

       EM算法有很多的应用，最广泛的就是GMM混合高斯模型、聚类、HMM等等。具体可以参考JerryLead的cnblog中的Machine Learning专栏。