EM算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

EM算法

简介: 这篇文章仅仅只是对这篇博客的总结整理,仅供自己学习之用。可能很多人会疑惑,自己转载就行了,为啥老是自己写。我觉得,不管什么东西,只有自己咀嚼过一遍,才算真的是领悟了。

这篇文章仅仅只是对这篇博客的总结整理,仅供自己学习之用。可能很多人会疑惑,自己转载就行了,为啥老是自己写。我觉得,不管什么东西,只有自己咀嚼过一遍,才算真的是领悟了。

1、最大似然

假设我们需要调查学校中男女生的身高分布,因为一个个的去调查费时费力,所以我们需要采用抽样的方法。假设随机抽取了100名男生和100名女生,规则是:男生在左边,女生在右边。然后先统计这100名男生的身高,假设他们的身高服从正态分布,但是这个分布的均值u和方差\sigma^2我们不知道,所以我们需要求这两个参数,记作\theta = [u, \sigma]
用数学的语言描述:在学校那么多男生的身高中,我们独立的按照概率密度(高斯分布N(u,\sigma)的形式)p(x | \theta)抽取了100个身高,组成样本集X,我们想通过样本集X估计未知参数\theta,而\theta = [u, \sigma]。抽到的样本集为X = {x_1, x_2, ..., x_n},其中x_i表示抽到的第i个人的身高,这里n = 100
由于所有男生的身高服从高斯分布p(x | \theta),那么我抽到A的概率为p(x_A | \theta),抽到B的概率为p(x_B | \theta),因为抽到每个人各自都是独立的,所以同时抽到A和B的概率为他们的乘积。所以在分布p(x | \theta)的总体样本抽到100个样本的概率为样本集X中所有样本的联合概率:
L(\theta) = L(x_1, x_2, ..., x_n;\theta) = \prod_{i=1}^n p(x_i;\theta), \theta \in \Theta.
这个函数说明了,在不同的参数\theta的取值下,得到这个样本集X的可能性,因此称参数\theta相对于样本集X的似然函数(likehood function)。记为L(\theta)
在学校中,我抽到100个男生,他们的概率是似然函数L(\theta),我们需要找到一个参数\theta使得似然函数最大。记为:
\hat{\theta} = argmaxL(\theta)
一般便于运算,我们将似然函数L(\theta)取对数,将连乘变成连加:
lnL(\theta) = ln\prod_{i=1}^n p(x_i;\theta) = \sum_{i=1}^n ln p(x_i;\theta)
求最大化,然后就成立一个求导使导数为0的过程,不在赘述。所以说,最大似然估计是已经知道了结果,然后寻求使该结果出现的可能性最大的条件,以此作为估计值。

2、EM算法

针对上面的例子,我们用似然函数求的男生的参数\theta = [u, \sigma],对于女生也同样求解。但是如果例子并没有那么简单,100名男生和100名女生同在一个黑屋里,你从200个人里面随便指一个,我并不知道到底是男生还是女生。也就是说,你不知道抽取的那200个人里面的每一个人到底是从男生分布还是女生分布中取的。这个时候,对于每一个样本,就有两个东西需要猜测了。一是这个人是男是女?二是男生和女生对应的身高的高斯分布的参数是多少?
在上面的例子中,如果没有第一个问题,那么似然函数轻松解决。但是现在有第一个问题,我们没法分析高斯分布的参数。二只有我们对这两个分布参数做了准确的估计,才知道哪些人属于第一个分布,那些人属于第二个分布。这就陷入了一个死循环。解决的方法是先对分布参数赋一个随机值,然后算出是男女的概率,然后通过男女的概率算分布参数,直到收敛。
EM的意思是“Expectation Maximization”,在我们上面这个问题里面,我们是先随便猜一下男生(身高)的正态分布的参数:如均值和方差是多少。例如男生的均值是1米7,方差是0.1米(当然了,刚开始肯定没那么准),然后计算出每个人更可能属于第一个还是第二个正态分布中的(例如,这个人的身高是1米8,那很明显,他最大可能属于男生的那个分布),这个是属于Expectation一步。有了每个人的归属,或者说我们已经大概地按上面的方法将这200个人分为男生和女生两部分,我们就可以根据之前说的最大似然那样,通过这些被大概分为男生的n个人来重新估计第一个分布的参数,女生的那个分布同样方法重新估计。这个是Maximization。然后,当我们更新了这两个分布的时候,每一个属于这两个分布的概率又变了,那么我们就再需要调整E步……如此往复,直到参数基本不再发生变化为止。
这里把每个人(样本)的完整描述看做是三元组y_i=\{xi,z_{i1},z_{i2} \},其中,x_i是第i个样本的观测值,也就是对应的这个人的身高,是可以观测到的值。z_{i1}z_{i2}表示男生和女生这两个高斯分布中哪个被用来产生值x_i,就是说这两个值标记这个人到底是男生还是女生(的身高分布产生的)。这两个值我们是不知道的,是隐含变量。确切的说,z_{ij}x_i由第j个高斯分布产生时值为1,否则为0 。例如一个样本的观测值为1.8,然后他来自男生的那个高斯分布,那么我们可以将这个样本表示为{1.8, 1, 0}。如果z_{i1}z_{i2}的值已知,也就是说每个人我已经标记为男生或者女生了,那么我们就可以利用上面说的最大似然算法来估计他们各自高斯分布的参数。但是它们未知,因此我们只能用EM算法。

3、EM算法推导

假设我们有一个样本集\{x^{(1)}, ..., x^{(m)}\},包含m个独立样本。但是每个样本i对应的类别z^{(i)}是未知的,即隐含变量。我们需要估计概率模型p(x,z)的参数\theta,但是里面有隐含变量z,不能用极大似然,如果z知道了,那么很容易求解。
对于参数估计,本质上还是想获得一个使似然函数最大化的那个参数\theta,唯一不同的是似然函数式多了隐变量z。我们的目标是找到合适的\thetaz使得L(\theta)最大,公式如下:

img_1b28c9c4aa6041238ad7d39abe136ae7.png

首先,我们想到是求偏导,但是很复杂,别想了。所以可以通过第(2)步变形,最后得到一个不等式,将和的对数变成对数的和。此变换是通过Jensen不等式来的。

Jensen不等式:

f是定义域为实数的函数,如果对于所有的实数xf(x)的二次导数大于等于0,那么f是凸函数。当x是向量,如果七hessian矩阵H是半正定的,那么f是凸函数。如果只大于0,不等于0,那么称f是严格凸函数。
Jensen不等式表述如下:
如果f是凸函数,x是随机变量,那么:E(f(x)) >= f(E(x))。特别地,如果f是严格凸函数,当且仅当x是常量时,上式取等号。如图所示:

img_35230d74bd9749be381a316a0322cf56.png

在图中,实线f是凸函数,x是随机变量,有0.5概率是a,有0.5的概率是b(就像掷硬币一样)。x的期望是ab的中值了,图中可以看到E(f(x)) >= f(E(x))成立。
f是(严格)凹函数,当且进度-f是(严格)凸函数。
Jensen不等式应用于凹函数时,不等号方向反向。
回到公式(2),因为f(x)=log x为凹函数(其二次导数为-1/x^2 < 0)。
(2)式中,

img_cb06bab9d26e3289e397043ea9f6a8ab.png

的期望,(考虑到E(x) = \sum x * p(x)f(x)x的函数,则E(f(x)) = \sum f(x) * p(x)),又\sum_z Q_i(z^{(i)}) = 1,所以就可以得到公式(3)的不等式了:

img_cc8ecf3cb9a588e77670346fc6aef26d.png

到这里,式(3)就可以很容易的求导,但是式(2)和式(3)是不等式,式(3)的最大值不是式(2)的最大值,而我们需要式(2)的最大值。
解决方法是,上面式(2)和式(3)不等式可以写成:似然函数L(\theta) > J(z, Q),那么我们可以通过不断的最大化这个下界J,来使得L(\theta)不断提高,最终达到它的最大值。

img_b8de1c7c2d4a07361d87b6634298d699.png

上图中,我们固定\theta,调整Q(z)使下界J(z,Q)上升至与L(\theta)在此点\theta处相等(绿色曲线到蓝色曲线),然后固定Q(z),调整\theta使得下界J(z,Q)达到最大值(\theta^t\theta^{t+1}),然后在固定\theta,调整Q(z).....知道收敛到似然函数L(\theta)的最大值处的\theta^*。两个问题:什么时候下界J(z,Q)L(\theta)在此点\theta处相等?为什么一定会收敛?
首先第一个问题,在Jensen不等式中说到,当自变量x是常数的时候,等式成立。而在这里,即:
\frac{p(x^{(i)}, z^{(i)};\theta)}{Q_i(z^{(i)})} = c
再推导下,由于\sum_z Q_i(z^{(i)}) = 1(因为Q是随机变量z^{(i)}的概率密度函数),则可以得到:分子的和等于c(分子分母都对所有z^{(i)}求和:多个等式分子分母相加不变,这个认为每个样例的两个概率比值都是c),则:

img_59950d8cebc2fb0244b7552d12e7d821.png

我们推出了在固定参数\theta后,使下界拉升的Q(z)的计算公式就是后验概率,解决了Q(z)如何选择的问题。这一步就是E步,建立L(\theta)的下界。接下来的M步,就是在给定Q(z)后,调整\theta,去极大化L(\theta)的下界J(在固定Q(z)后,下界还可以调整的更大)。那么一般的EM算法的步骤如下:

img_ad4137f8ff638947932e9b3835475869.jpe

4、EM算法的应用

EM算法有很多的应用,最广泛的就是GMM混合高斯模型、聚类、HMM等等,自己去搜吧。。。
最后,感谢这些大牛将这么好的文章po到网上。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章