文档介绍：混合高斯模型( Mixtures of Gaussians )和 EM 算法这篇讨论使用期望最大化算法( Expectation-Maximization ) 来进行密度估计( density estimation )。与 k-means 一样, 给定的训练样本是, 我们将隐含类别标签用表示。与 k-means 的硬指定不同,我们首先认为是满足一定的概率分布的,这里我们认为满足多项式分布,, 其中,有k 个值{1, …,k} 可以选取。而且我们认为在给定后, 满足多值高斯分布,即。由此可以得到联合分布。整个模型简单描述为对于每个样例,我们先从 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 中的词对齐中也用到了。在 Mitchel l 的书中也提到 EM 可以用于贝叶斯网络中。下面主要介绍 EM 的整个推导过程。 1. Jensen 不等式回顾优化理论中的一些概念。设 f 是定义域为实数的函数,如果对于所有的实数 x, ,那么 f 是凸函数。当 x 是向量时,如果其 hessian 矩阵 H 是半正定的( ), 那么 f 是凸函数。如果或者,那么称 f 是严格凸函数。 Jensen 不等式表述如下: 如果 f 是凸函数, X 是随机变量,那么特别地,如果 f 是严格凸函数,那么当且仅当,也就是说X 是常量。这里我们将简写为。如果用图表示会很清晰: 图中,实线 f 是凸函数, X 是随机变量,有 的概率是 a ,有 的概率是 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 是连续性的, 那么