网易公开课，第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，然后再迭代

具体如下，

E步骤，我们任意初始化参数 ，就可以算出每个xi对应的zi，其实只要算出上面的这个概念分布就可以

具体算的公式如下，

，其中分别符合多项式和多项高斯分布，代入公式很容易算出

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的均值一定比较接近谷底，所以这个不等式一定成立的

当f是严格凸函数的时候，即 时，普通凸函数，二阶导数可能为0，比如某一段为直线
如果要E[f(x)] = f(E[x])，当且仅当 x = E[x], 即x是个常量

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

 

EM algorithm

下面来看看EM算法，

对于m个独立的训练数据点，似然函数如下，
这里是通用形式，所以参数就是 ，这里没有假设z和x|z的分布，可以是任意分布

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

解的思路，

E-step, construct a lower-bound on
先随便初始化参数，构建这个分布的下界，即最差的case
然后通过下界的分布，得到z

M-step, optimize that lower-bound
用E-step得到的z来最优化参数

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

 

首先，假设Q为z的某种分布，Q(zi)为zi出现的概率，那么有 ，并且Q(zi)>=0

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

先看下期望的定义，

参考，（EM算法）The EM Algorithm

 

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

，为g(z)

而 ，为p

所以，

就是，

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

所以这样就产生了的下界，

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

我们虽然给出在参数时的下界，但是我们希望这个下界是可以尽量逼近的，所以希望(3)中最好可以取到等式，这样下界就等于

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

由于，所以让分子和分母对所有的z求和，应该还是等于c，比如2+4 /1+2，仍然为2，得到

，

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

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

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

那么这个算法是收敛的吗？即证明下面的式子，第t+1次迭代的>=第t次迭代

过程如下，

(4)给出 的下界

(5)因为在M-step，要在固定Q情况下，最优化，所以优化完，一定比原来的要大

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

所以得证

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

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

在E-Step，我们固定 来，求解最优的Q

在M-Step，我们固定Q来，求解最优的

 

Mixture of Gaussians revisited

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

对于E-step很简单，

通用的EM，表示为

而对于混合高斯算法，为 ，这个很自然，不需要解释

然后对于M-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}