这篇讨论使用期望最大化算法(Expectation-Maximization)来进行密度估计(density estimation)。

与k-means 一样,给定的训练样本是{x (1), … ,x (m)},我们将隐含类别标签用z(i)表示。与k-means 的硬指定不同,我们首先认为z(i)是满足一定的概率分布的,这里我们认为满足多项式分布,z(i)~Multinomial(∅),其中p(z(i)=j)=∅j  ,  ∅j≥0, ∑j=1j=1 ,  z(i)   有k个值{1,...,k}可以取而 且 我 们 认 为 在 给 定 z(i) 后 ,x(i) 满 足 多 值 高 斯 分 布 , 即 (x(i)|z(i) = j)~N(µj , Σj)。由此可以得到联合分布p(x(i),z(i)) = p(x(i)|z(i))p(z(i))。

整个模型简单描述为对于每个样例x(i),我们先从 k 个类别中按多项式分布抽取一个z(i),然后根据z(i)所对应的 k 个多值高斯分布中的一个生成样例x(i)。整个过程称作混合高斯模型。注意的是这里的z(i)仍然是隐含随机变量。模型中还有三个变量∅,μ和Σ。最大似然估 计为p(x, z)。对数化后如下:image1

这个式子的最大值是不能通过前面使用的求导数为 0 的方法解决的,因为求的结果不是 close form。但是假设我们知道了每个样例的z(i),那么上式可以简化为:image2

这时候我们再来对∅,μ和Σ进行求导得到:

image3

j 就是样本类别中z(i) = j的比率。μj 是类别为 j 的样本特征均值,Σ j是类别为 j 的样例的特征的协方差矩阵。

实际上,当知道z(i) 后,最大似然估计就近似于高斯判别分析模型(Gaussian discriminant analysis model)了。所不同的是 GDA 中类别 y 是伯努利分布,而这里的 z 是多项式分布,还有这里的每个样例都有不同的协方差矩阵,而 GDA 中认为只有一个。

之前我们是假设给定了z(i),实际上z(i)是不知道的。那么怎么办呢?考虑之前提到 的 EM 的思想,第一步是猜测隐含类别变量 z,第二步是更新其他参数,以获得最大的最大似然估计。用到这里就是:

循环下面步骤,直到收敛:{

          (E步)对于每一个i和j,计算

                            wj(i) :=p(z(i)=j | x(i) ; Φ , µ ,Σ)

          (M步),更新参数:

image5

}

在 E 步中,我们将其他参数Φ,µ , Σ看作常量,计算z(i)的后验概率,也就是估计隐含类别变量。估计好后,利用上面的公式重新计算其他参数,计算好后发现最大化最大似然估计时,wj(i)值又不对了,需要重新计算,周而复始,直至收敛。

wj(i)的具体计算公式如下:

image6

这个式子利用了贝叶斯公式。

这里我们使用wj(i)代替了前面的1{z(i) = j},由简单的 0/1 值变成了概率值。

对比 K-means 可以发现,这里使用了“软”指定,为每个样例分配的类别z(i)是有一定 的概率的,同时计算量也变大了,每个样例 i 都要计算属于每一个类别 j 的概率。与 K-means相同的是,结果仍然是局部最优解。对其他参数取不同的初始值进行多次计算不失为一种好方法。

 

6. K-means聚类算法

K-means也是聚类算法中最简单的一种了,但是里面包含的思想却是不一般。聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例...

阅读全文

5.规则化和模型选择(Regularization and model selection)

1 问题 模型选择问题:对于一个学习问题,可以有多种模型选择。比如要拟合一组样本点,可以使 用线性回归(y =θTx),也可以用多项式回归(y = θTx1~m )。那么使...

阅读全文

欢迎留言