Andrew Ng机器学习公开课笔记 -- Mixtures of Gaussians and the EM algorithm

网易公开课，第12，13课 

notes，7a, 7b，8

从这章开始，介绍无监督的算法 

对于无监督，当然首先想到k means, 最典型也最简单，有需要直接看7a的讲义

mixtures of gaussians

如果要理解mixtures of gaussians，那先回去复习一下gaussians discriminant analysis，高斯判别分析

首先高斯判别分析是生成算法，

所以不会直接拟合p(y|x), 而是拟合p(x|y)p(y), 即p(x,y)

p(y)符合伯努力分布，如果是多元分类，即多项式分布 

p(x|y)符合多项高斯分布

这个问题就解了

那么对于混合高斯，区别只是，对于一系列数据点，y是未知的，即非监督 

下面看看形式化的定义，

既然y是未知，所以换个名字，z，隐随机变量（latent random variables, meaning that they’re hidden/unobserved.）

z符合多项式分布，参数φj表示z=j的概率，所以φ一定>=0, 并且所有φ的和为1

x|z，符合多项高斯分布

和高斯判别分析其实，只是把y替换成z，表示z是未知，不可见的 

那么它的最大似然估计为，

最大似然时，之所以只考虑x，没有像高斯判别那样考虑p(x, y)，是因为y不可见 

但是怎么理解？ 

可以想象一维数据，有很多数据点，分别代表多个高斯分布混合着一起 

而高斯分布一定是中间的点比较密集，这里的p(x)会比较高 

假设我们的数据点是有代表性的，所以拟合出p(x)高的高斯分布，会更合理一些

对于这个如何求解？ 

直接用梯度下降很难求解，因为在log里面求和。。。求导试试看

当然这里如果z已知，那么就很简单，直接变成高斯判别分析问题，但是问题现在z未知。

解决这个问题的方法，就是em算法，expectation maximization algorithm

这个算法其实思路很简单，但是如何推导和证明他的收敛和有效，比较复杂

所以先看看思路和实现，再来看推导

思路很简单，既然不知道z，并且如果知道就可以解这个问题，那么我们就先随便猜z，然后再迭代

具体如下，

具体算的公式如下，

m步骤，

用上面猜的z来重新计算参数，这里看到为何只要算出w就ok，因为就已经足够算出新的参数

至于为何是这个公式，因为从上面高斯判别分析，可以得到，

只是简单的把部分替换成w

通过不停的e，m步骤的迭代，最终一定可以收敛到局部最优，和k-means一样，可以多试些初始值，来找到全局最优

但是为何这么简单的方法会有效，如何理解em？继续

the em algorithm

上面看到使用em来拟合混合高斯问题，但这只是em的一个特例

这章会推导出em的一般形式，他可以解决各种含有隐变量的预估问题(estimation problems with latent variables.)

jensen's inequality

先介绍一下jensen不等式

首先通过下面的图理解一下，当f是凸函数的时候 

e[f(x)] >= f(e[x])

对于凸函数，如果x是随机变量，分布均匀，那么x的均值一定比较接近谷底，所以这个不等式一定成立的

如果要e[f(x)] = f(e[x])，当且仅当 x = e[x], 即x是个常量

需要注意，这个不等式对于concave，凹函数也是满足的，但不等式的方向相反

em algorithm

下面来看看em算法，

对于m个独立的训练数据点，似然函数如下， 

这个直接解是很困难的，所以用em算法解

解的思路，

先随便初始化参数，构建这个分布的下界，即最差的case 

然后通过下界的分布，得到z

m-step, optimize that lower-bound 

用e-step得到的z来最优化参数

如下图，在迭代过程中，下界的分布会不断的逼近真实分布

然后为了使用jensen不等式，对(1)分子分母同时乘上q(zi)，这样就产生了期望e

先看下期望的定义，

那么对应于上面的公式，其中

所以，

再来看jensen不等式，e[f(x)] >= f(e[x])，其中f就是log，所以得到上面(3)

我们需要在m-step中去最优化这个下界，但问题是现在q分布还没有确定，如何确定哪种q分布会最好

这时候再看jensen不等式中，对于=取值的条件，即，

所以得到q的分布，就是z的后验概率

所以，最终得到的general em算法为，

可以对比一下，之前混合高斯的em，体会一下特例和通用的差别

过程如下，

(6)因为在取下界的时候，选择q使得

所以得证

em和k-means都是一定会收敛到局部最优的

从另外一个角度来看em，其实是一种坐标上升算法，

mixture of gaussians revisited

看完通用的em算法，再会过头来看看混合高斯算法，应该会更清晰一些

对于e-step很简单，

文本聚类- mixtures of naive bayes model

这个没有讲义，只能截图

对于naive bayes是文本分类，而因为这里的训练集是不知道y的，所以就是文本聚类问题 

得到m个文本，每个文本是n维向量，其中每维取{0,1}代表该word是否在文本中出现

而隐变量z，也是取值{0,1}，表示分两类，那么z就符合伯努力分布

p(x|z)，符合naive bayes分布

这里给出，e-step和m-step的公式

当然其中m-step是通过最大化p(x|z)，求解出来的

其实想想，em和k-mean的基本思路是差不多的 

首先对于数据集，选定特征后，是可分的，即如果把数据画出来，是可以看到明显聚集的

所以随意设定初值后，不断迭代，比如混合高斯，总是可以渐渐收敛到局部最优的，不同于k-mean的是 

em可以给出具体的密度函数p(z|x) 

对于隐变量z，其实k-mean，如果设k=2，即两类，相当于产生z取值{0,1}

本文章摘自博客园，原文发布日期：2014-08-07