您的位置: 首页  >  文章  >  机器学习算法——EM算法

机器学习算法——EM算法

分类: 文章 • 2022-10-28 08:51:16

一、EM算法简介

EM算法，指的是最大期望算法（Expectation Maximization Algorithm，又译期望最大化算法），是一种迭代算法，在统计学中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。

中文名

em算法

别名

最大期望算法；期望最大化算法

外文名

Expectation Maximization Algorithm

领域

统计学

可以有一些比较形象的比喻说法把这个算法讲清楚。比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。

EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。

EM算法是一种解决存在隐含变量优化问题的有效方法。EM算法是期望极大(Expectation Maximization)算法的简称，EM算法是一种迭代型的算法，在每一次的迭代过程中，主要分为两步：即求期望(Expectation)步骤和最大化(Maximization)步骤。

二、EM算法推导

1、凸函数
凸函数,是数学函数的一类特征。凸函数就是一个定义在某个向量空间的凸子集C（区间）上的实值函数。

凸函数是一个定义在某个向量空间的凸子集C（区间）上的实值函数f，而且对于凸子集C中任意两个向量, f((x1+x2)/2)>=(f(x1)+f(x2))/2,则f(x)是定义在凸子集c中的凸函数（该定义与凸规划中凸函数的定义是一致的，下凸）。

设f是定义在实数域上的函数，如果对于任意的实数x，都有机器学习算法——EM算法,那么f是凸函数。若x不是单个实数，而是由实数组成的向量，此时，如果函数f的Hesse矩阵H是半正定的，即
机器学习算法——EM算法

那么f是凸函数。特别地，如果机器学习算法——EM算法或者机器学习算法——EM算法，那么称f为严格凸函数。
机器学习算法——EM算法

2、Jensen不等式

如果函数是凸函数，是随机变量，那么

机器学习算法——EM算法

特别地，如果函数是严格凸函数，那么

机器学习算法——EM算法

当且仅当

机器学习算法——EM算法

即随机变量是常量。

机器学习算法——EM算法机器学习算法——EM算法

注：若函数是凹函数，上述的符号相反。

3、EM算法推导

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

    第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z求联合分布概率和。但是直接求机器学习算法——EM算法
一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。

EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化机器学习算法——EM算法，我们可以不断地建立机器学习算法——EM算法的下界（E步），然后优化下界（M步）。这句话比较抽象，看下面的。    
对于每一个样例i，让机器学习算法——EM算法表示该样例隐含变量z的某种分布，机器学习算法——EM算法满足的条件是机器学习算法——EM算法。（如果z是连续性的，那么机器学习算法——EM算法是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。
可以由前面阐述的内容得到下面的公式：机器学习算法——EM算法

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

就是机器学习算法——EM算法 的期望（回想期望公式中的Lazy Statistician规则）

设Y是随机变量X的函数机器学习算法——EM算法（g是连续函数），那么

（1） X是离散型随机变量，它的分布律为机器学习算法——EM算法，k=1,2,…。若机器学习算法——EM算法绝对收敛，则有机器学习算法——EM算法

（2） X是连续型随机变量，它的概率密度为机器学习算法——EM算法，若机器学习算法——EM算法

绝对收敛，则有
机器学习算法——EM算法

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

可以得到（3）。

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

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

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

循环重复直到收敛 {

  （E步）对于每一个i，计算

         机器学习算法——EM算法

  （M步）计算

                  机器学习算法——EM算法

那么究竟怎么确保EM收敛？假定机器学习算法——EM算法和机器学习算法——EM算法是EM第t次和t+1次迭代后的结果。如果我们证明了机器学习算法——EM算法，也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。下面来证明，选定机器学习算法——EM算法后，我们得到E步
机器学习算法——EM算法

 这一步保证了在给定机器学习算法——EM算法时，Jensen不等式中的等式成立，也就是机器学习算法——EM算法

然后进行M步，固定机器学习算法——EM算法，并将机器学习算法——EM算法视作变量，对上面的机器学习算法——EM算法求导后，得到机器学习算法——EM算法，这样经过一些推导会有以下式子成立：机器学习算法——EM算法

解释第（4）步，得到机器学习算法——EM算法时，只是最大化机器学习算法——EM算法，也就是机器学习算法——EM算法的下界，而没有使等式成立，等式成立只有是在机器学习算法——EM算法固定，并按E步得到机器学习算法——EM算法时才能成立。况且根据我们前面得到的下式，对于所有的机器学习算法——EM算法和机器学习算法——EM算法都成立机器学习算法——EM算法

第（5）步利用了M步的定义，M步就是将机器学习算法——EM算法调整到机器学习算法——EM算法，使得下界最大化。因此（5）成立，（6）是之前的等式结果。

这样就证明了机器学习算法——EM算法会单调增加。一种收敛方法是机器学习算法——EM算法不再变化，还有一种就是变化幅度很小。 再次解释一下（4）、（5）、（6）。首先（4）对所有的参数都满足，而其等式成立条件只是在固定机器学习算法——EM算法，并调整好Q时成立，而第（4）步只是固定Q，调整机器学习算法——EM算法，不能保证等式一定成立。（4）到（5）就是M步的定义，（5）到（6）是前面E步所保证等式成立条件。也就是说E步会将下界拉到与机器学习算法——EM算法一个特定值（这里机器学习算法——EM算法）一样的高度，而此时发现下界仍然可以上升，因此经过M步后，下界又被拉升，但达不到与机器学习算法——EM算法另外一个特定值一样的高度，之后E步又将下界拉到与这个特定值一样的高度，重复下去，直到最大值。

  如果我们定义：
机器学习算法——EM算法

从前面的推导中我们知道机器学习算法——EM算法，EM可以看作是J的坐标上升法，E步固定机器学习算法——EM算法，优化机器学习算法——EM算法，M步固定机器学习算法——EM算法优化机器学习算法——EM算法
。
4、总结

如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题，只不过聚类问题中参数分为隐含类别变量和其他参数，这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步估计隐含变量，M步估计其他参数，交替将极值推向最大。EM中还有“硬”指定和“软”指定的概念，“软”指定看似更为合理，但计算量要大，“硬”指定在某些场合如K-means中更为实用（要是保持一个样本点到其他所有中心的概率，就会很麻烦）。

另外，EM的收敛性证明方法确实很牛，能够利用log的凹函数性质，还能够想到利用创造下界，拉平函数下界，优化下界的方法来逐步逼近极大值。而且每一步迭代都能保证是单调的。最重要的是证明的数学公式非常精妙，硬是分子分母都乘以z的概率变成期望来套上Jensen不等式，前人都是怎么想到的。

在Mitchell的Machine Learning书中也举了一个EM应用的例子，明白地说就是将班上学生的身高都放在一起，要求聚成两个类。这些身高可以看作是男生身高的高斯分布和女生身高的高斯分布组成。因此变成了如何估计每个样例是男生还是女生，然后在确定男女生情况下，如何估计均值和方差，里面也给出了公式，有兴趣可以参考. 

相关推荐