看来了一下EM算法的推导,感觉信号检测与估值的课需要复习了。。。
斯坦福大学机器学习——EM算法求解高斯混合模型(系列)
下面主要介绍EM的整个推导过程。
1. Jensen不等式
回顾优化理论中的一些概念。设f是定义域为实数的函数,如果对于所有的实数x,
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CNyUTM1UTM2EjNwQDMxEDMy8CX0ATMxAjMvwFZhVGb5Jnclp2Lc12bj91cn9Gbi52YvwVbvNmLzd2bsJmbj5ycldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
,那么称f是严格凸函数。
Jensen不等式表述如下:
如果f是凸函数,X是随机变量,那么
,也就是说X是常量。
这里我们将
。
如果用图表示会很清晰:
成立。
当f是(严格)凹函数当且仅当-f是(严格)凸函数。
Jensen不等式应用于凹函数时,不等号方向反向,也就是
2. EM算法
给定的训练样本是
一般比较困难,因为有隐藏变量z存在,但是一般确定了z后,求解就容易了。
EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化
的下界(E步),然后优化下界(M步)。这句话比较抽象,看下面的。
对于每一个样例i,让
是概率密度函数,需要将求和符号换做积分符号)。比如要将班上学生聚类,假设隐藏变量z是身高,那么就是连续的高斯分布。如果按照隐藏变量是男女,那么就是伯努利分布了。
可以由前面阐述的内容得到下面的公式:
设Y是随机变量X的函数 (g是连续函数),那么 (1) X是离散型随机变量,它的分布律为 |
对应于上述问题,Y是
,X是
,
是
,g是
到
的映射。这样解释了式子(2)中的期望,再根据凹函数时的Jensen不等式:
可以得到(3)。
这个过程可以看作是对
求了下界。对于
的选择,有多种可能,那种更好的?假设
已经给定,那么
的值就决定于
和
了。我们可以通过调整这两个概率使下界不断上升,以逼近
的真实值,那么什么时候算是调整好了呢?当不等式变成等式时,说明我们调整后的概率能够等价于
了。按照这个思路,我们要找到等式成立的条件。根据Jensen不等式,要想让等式成立,需要让随机变量变成常数值,这里得到:
c为常数,不依赖于
。对此式子做进一步推导,我们知道
,那么也就有
,(多个等式分子分母相加不变,这个认为每个样例的两个概率比值都是c),那么有下式:
至此,我们推出了在固定其他参数
后,
的计算公式就是后验概率,解决了
如何选择的问题。这一步就是E步,建立
的下界。接下来的M步,就是在给定
后,调整
,去极大化
的下界(在固定
后,下界还可以调整的更大)。那么一般的EM算法的步骤如下:
循环重复直到收敛 { (E步)对于每一个i,计算 |
那么究竟怎么确保EM收敛?假定
是EM第t次和t+1次迭代后的结果。如果我们证明了
,也就是说极大似然估计单调增加,那么最终我们会到达最大似然估计的最大值。下面来证明,选定
后,我们得到E步
这一步保证了在给定
时,Jensen不等式中的等式成立,也就是
然后进行M步,固定
,并将
视作变量,对上面的
求导后,得到
,这样经过一些推导会有以下式子成立:
解释第(4)步,得到
时,只是最大化
,也就是
的下界,而没有使等式成立,等式成立只有是在固定
,并按E步得到
时才能成立。
况且根据我们前面得到的下式,对于所有的
都成立
第(5)步利用了M步的定义,M步就是将
调整到
,使得下界最大化。因此(5)成立,(6)是之前的等式结果。
这样就证明了
会单调增加。一种收敛方法是
不再变化,还有一种就是变化幅度很小。
再次解释一下(4)、(5)、(6)。首先(4)对所有的参数都满足,而其等式成立条件只是在固定
,并调整好Q时成立,而第(4)步只是固定Q,调整
,不能保证等式一定成立。(4)到(5)就是M步的定义,(5)到(6)是前面E步所保证等式成立条件。也就是说E步会将下界拉到与
一个特定值(这里
)一样的高度,而此时发现下界仍然可以上升,因此经过M步后,下界又被拉升,但达不到与
另外一个特定值一样的高度,之后E步又将下界拉到与这个特定值一样的高度,重复下去,直到最大值。
如果我们定义
从前面的推导中我们知道
,EM可以看作是J的坐标上升法,E步固定
,优化
,M步固定
优化
从最大似然到EM算法浅解
EM算法有很多的应用,最广泛的就是GMM混合高斯模型、聚类、HMM等等。具体可以参考JerryLead的cnblog中的Machine Learning专栏:
(EM算法)The EM Algorithm
混合高斯模型(Mixtures of Gaussians)和EM算法
K-means聚类算法
C/C++基本语法学习
STL
C++ primer