内容发布更新时间 : 2024/12/24 0:35:28星期一 下面是文章的全部内容请认真阅读。
混合高斯模型(Mixtures of Gaussians)和EM算法
这篇讨论使用期望最大化算法(Expectation-Maximization)来进行密度估计(density estimation)。
与k-means一样,给定的训练样本是k-means的硬指定不同,我们首先认为式分布,
,其中
后,
满足多值高斯分布,即
。
,我们先从k个类别中按多项式分布抽取一个
,
,我们将隐含类别标签用
表示。与
是满足一定的概率分布的,这里我们认为满足多项
,
有k个值{1,…,k}
。由
可以选取。而且我们认为在给定此可以得到联合分布
整个模型简单描述为对于每个样例然后根据
所对应的k个多值高斯分布中的一个生成样例,。整个过程称作混合高斯模型。
和。最大似然估计为
注意的是这里的仍然是隐含随机变量。模型中还有三个变量
。对数化后如下:
这个式子的最大值是不能通过前面使用的求导数为0的方法解决的,因为求的结果不是close form。但是假设我们知道了每个样例的
,那么上式可以简化为:
这时候我们再来对
和进行求导得到:
就是样本类别中
的比率。是类别为j的样本特征均值,是类别为j的样例的
特征的协方差矩阵。 实际上,当知道
后,最大似然估计就近似于高斯判别分析模型(Gaussian discriminant
analysis model)了。所不同的是GDA中类别y是伯努利分布,而这里的z是多项式分布,还有这里的每个样例都有不同的协方差矩阵,而GDA中认为只有一个。 之前我们是假设给定了
,实际上
是不知道的。那么怎么办呢?考虑之前提到的EM
的思想,第一步是猜测隐含类别变量z,第二步是更新其他参数,以获得最大的最大似然估计。用到这里就是:
循环下面步骤,直到收敛: { (E步)对于每一个i和j,计算 (M步),更新参数: } 在E步中,我们将其他参数看作常量,计算的后验概率,也就是估计隐含类别变
量。估计好后,利用上面的公式重新计算其他参数,计算好后发现最大化最大似然估计时,值又不对了,需要重新计算,周而复始,直至收敛。
的具体计算公式如下:
这个式子利用了贝叶斯公式。
这里我们使用代替了前面的,由简单的0/1值变成了概率值。
是有一定的概
对比K-means可以发现,这里使用了“软”指定,为每个样例分配的类别
率的,同时计算量也变大了,每个样例i都要计算属于每一个类别j的概率。与K-means相同的是,结果仍然是局部最优解。对其他参数取不同的初始值进行多次计算不失为一种好方法。 虽然之前再K-means中定性描述了EM的收敛性,仍然没有定量地给出,还有一般化EM的推导过程仍然没有给出。下一篇着重介绍这些内容。
(EM算法)The EM Algorithm
EM是我一直想深入学习的算法之一,第一次听说是在NLP课中的HMM那一节,为了解决HMM的参数估计问题,使用了EM算法。在之后的MT中的词对齐中也用到了。在Mitchell的书中也提到EM可以用于贝叶斯网络中。 下面主要介绍EM的整个推导过程。
1. Jensen不等式
回顾优化理论中的一些概念。设f是定义域为实数的函数,如果对于所有的实数x,
,那么f是凸函数。当x是向量时,如果其hessian矩阵H是半正定的(
那么f是凸函数。如果
Jensen不等式表述如下:
如果f是凸函数,X是随机变量,那么
当且仅当
,也就是
或者
,那么称f是严格凸函数。
),
特别地,如果f是严格凸函数,那么说X是常量。
这里我们将简写为。
如果用图表示会很清晰:
图中,实线f是凸函数,X是随机变量,有0.5的概率是a,有0.5的概率是b。(就像掷硬币一样)。X的期望值就是a和b的中值了,图中可以看到 当f是(严格)凹函数当且仅当-f是(严格)凸函数。 Jensen不等式应用于凹函数时,不等号方向反向,也就是
。 成立。
2. EM算法
给定的训练样本是
,样例间独立,我们想找到每个样例隐含的类别z,能使
得p(x,z)最大。p(x,z)的最大似然估计如下:
第一步是对极大似然取对数,第二步是对每个样例的每个可能类别z求联合分布概率和。但是直接求一般比较困难,因为有隐藏变量z存在,但是一般确定了z后,求解就容易了。 EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化
,我们可以不
断地建立的下界(E步),然后优化下界(M步)。这句话比较抽象,看下面的。
对于每一个样例i,让表示该样例隐含变量z的某种分布,满足的条件是
。(如果z是连续性的,那么是概率密度函数,需要将求和符号换做
积分符号)。比如要将班上学生聚类,假设隐藏变量z是身高,那么就是连续的高斯分布。如果按照隐藏变量是男女,那么就是伯努利分布了。 可以由前面阐述的内容得到下面的公式:
(1)到(2)比较直接,就是分子分母同乘以一个相等的函数。(2)到(3)利用了Jensen不等式,考虑到
是凹函数(二阶导数小于0),而且
就是
设Y是随机变量X的函数
的期望(回想期望公式中的Lazy Statistician规则) (g是连续函数),那么 ,k=1,2,…。若 (1) X是离散型随机变量,它的分布律为绝对收敛,则有 (2) X是连续型随机变量,它的概率密度为,若绝对收敛,则有