机器学习笔记11: K-Means算法和EM算法

这一节开始我们讨论非监督学习(Unsupervised Learning)的算法。在监督学习算法中，训练数据既包含特征也包含标签，通常表示为{(x⁽¹⁾, y⁽¹⁾), ..., (x^(m), y^(m))}；而在非监督学习中，训练数据只有特征没有标签，通常表示为{x⁽¹⁾, ..., x^(m)}。

K-Means算法

聚类(clustering)问题是最常见的非监督学习问题。对于一组无标签数组，可以用聚类算法将数据分成若干相似的“群组”，从而发掘数据中的隐藏结构。

K-Means算法是最常见的一种聚类算法，算法步骤描述如下：

1. 随机选择k个中心点(centroids): μ₁, μ₂, ..., μ_k

2. 重复如下过程直到收敛：{
   

   对于每个样本i，令：
   对于每个中心点j，令：

}

在上面的算法中，k表示我们想要聚类的个数，μ_j表示目前我们对中心点的猜测。算法的第一步是初始化中心点，这个可以通过随机选择k个样本数据获得。算法的第二步是不断循环如下两个过程：首先将样本x⁽ⁱ⁾“指派”给离它距离最近的中心点μ_j，然后将中心点μ_j更新为所有被“指派”给它的样本距离的平均值。下图展示了算法的执行过程：

图(a)表示原始的训练数据。图(b)表示随机选取了两个初始中心点，用记号x表示。图(c)表示将每个训练数据指派给离它最近的中心点，图中用不同颜色表示数据与中心点的关系。图(d)表示更新中心点的位置。图(e)和(f)表示又进行了一轮迭代。

K-Means算法一定可以保证收敛。特别的，我们定义失真函数(distortion function)：

因此，J函数表示每个样本点离它对应中心点的平方和。可以证明，K-Means算法其实就是对J函数应用坐标下降算法。具体来说，K-Means算法内层循环的第一步是固定μ使c关于J求最小化，第二步是固定c使μ关于J求最小化。因此J是单调递减的，J的值必然是收敛的。

由于J函数不是凸函数，所以坐标下降法未必能得到全局最优解，也就是说K-Means算法可能会得到局部最优解。为了防止K-Means算法得出的结果是局部最优解，通常可以用不同的初始值多运行几次算法，然后取使得J函数最小的那个参数值。

混合高斯模型

这一部分我们介绍使用混合高斯模型进行聚类的算法。回顾在高斯判别分析(GDA)模型中，我们假设x是连续的随机变量，p(y)服从伯努利分布，p(x|y)服从多元正态分布，通过极大似然法使得联合概率p(x, y)最大，从而求解出模型的参数。

而在非监督学习的设定下，我们没有y的数据，因此我们引入一个隐含(latent)随机变量z。我们建立联合分布p(x⁽ⁱ⁾, z⁽ⁱ⁾) = p(x⁽ⁱ⁾|z⁽ⁱ⁾)p(z⁽ⁱ⁾)，其中p(z⁽ⁱ⁾)服从参数为φ的多项式分布(p(z⁽ⁱ⁾ = j) = φ_j)，p(x⁽ⁱ⁾|z⁽ⁱ⁾)服从正态分布N(μ_j, Σ_j)。我们的模型首先让z⁽ⁱ⁾随机地从1到k中取值，然后x⁽ⁱ⁾是从k个高斯分布中选择第z⁽ⁱ⁾个分布，这样的模型就称之为混合高斯模型(Mixtures of Gaussians)。由于z⁽ⁱ⁾是不可观察的隐含变量，这使得我们的计算变得更为困难。

为了计算模型中φ, μ和Σ的值，我们写出似然函数：

如果我们通过用求导的方式来求解参数，我们会发现这是不可能做到的。

由于z⁽ⁱ⁾是用来表示x⁽ⁱ⁾是来自k个高斯分布中的哪一个的，如果我们知道z⁽ⁱ⁾的取值的话，那么问题就变得简单了，我们将问题简化为：

对此似然函数最大化，我们求得各参数为：

因此，如果z⁽ⁱ⁾是已知的，那么最大化似然函数的问题就很简单了，而且求解参数的结果和通过GDA求解得到的参数非常相似。

但是在我们实际问题中，z⁽ⁱ⁾是未知的，那我们应该怎么办呢？

我们可以采用EM算法。EM算法是一个迭代式的算法，它总共分为两步。在这个问题中，E步尝试猜测一个合理的z⁽ⁱ⁾值，M步按照上一步猜测的z⁽ⁱ⁾来更新模型的参数。在M步，由于我们假设E步猜测的z⁽ⁱ⁾是正确的，因此最大化似然函数的问题变得简单了。算法步骤描述如下：

重复如下过程直到收敛：{

E步：对于每个i, j，我们令：
M步：按如下公式更新参数：

}

在E步中，我们计算的是在给定x⁽ⁱ⁾和其他参数情况下z⁽ⁱ⁾的后验概率，根据贝叶斯公式，我们有：

上式中的p(x⁽ⁱ⁾|z⁽ⁱ⁾ = j; μ,Σ)是通过平均值为μ_j，协方差为Σ_j的高斯分布在x⁽ⁱ⁾上的概率密度计算得出；p(z⁽ⁱ⁾ = j;φ)的值由φ^(j)计算得出。我们在E步中计算的w_j⁽ⁱ⁾可以认为是对z⁽ⁱ⁾的软猜测(软猜测是指猜测的结果是[0,1]之间的概率值，硬猜测是指0或1的取值)。

EM算法和K-Means算法的迭代步骤其实比较类似，不同的是K-Means算法中每次对c⁽ⁱ⁾的更新是硬猜测，而EM中每次对w⁽ⁱ⁾的更新是软猜测。和K-Means算法相同的是，EM算法也可能得到局部最优解，所以用不同的初始参数迭代会得到更好的结果。

这一部分我们用EM算法的思想讲了混合高斯模型问题，后面我们会讲更通用的EM算法，以及EM算法是如何保证算法的收敛性的。在讲解通用EM算法之前，我们先要介绍一个定理作为预备知识。

Jensen不等式

令f是一个定义域为实数的函数。若f是凸函数(convex function)，则f''(x) >= 0。如果f的定义域是向量，那么凸函数的条件变为f的Hessian矩阵H是半正定矩阵(H >= 0)。如果对于所有的x都有f''(x) > 0，那么我们说f是严格凸函数。对于定义域是向量的情况，如果H是正定矩阵(H > 0)，那么我们说f是严格凸函数。

Jensen不等式(Jensen’s inequality)可表述如下：

令f是凸函数，X是随机变量，那么有：E[f(X)] >= f(EX)。如果f是严格凸函数，那么E[f(X)] = f(EX)当且仅当X = E[X]的概率为1(即X是常量)。

由于我们在书写期望的时候有时候会把括号省略掉，所以上式中的EX是E[X]的缩写。为了对这个公式有直观的理解，我们可以用下图来解释：

上图中的曲线表示函数f，X是一个随机变量，它有一半的概率取a，有一半的概率取b，所以E[X]介于a和b的中间。另一方面我们可以看到y轴上f(a)，f(b)和f(EX)的值，而E[f(X)]介于f(a)和f(b)的中间。由于凸函数的特性，很容易看出一定有E[f(X)] >= f(EX)。

事实上很多人会记不清这个不等式的方向，有了上面这个图的话可以帮助我们更好的记忆。

注意，如果f是凹函数(concave function)(即f''(x) <= 0或H <= 0)，Jensen不等式也是成立的，只不过不等式的方向变了，即E[f(X)] <= f(EX)。

EM算法

这一节我们介绍通用的EM算法。假设我们的训练集是m个互相独立的样本{x⁽¹⁾, ..., x^(m)}，我们希望对p(x, z)进行建模，其似然函数为：

直接通过最大化似然函数求解参数是比较困难的。这里z⁽ⁱ⁾是隐含的随机变量，如果z⁽ⁱ⁾的值是已知的，那么问题将变得简单。

在这种情况下，EM算法给出了一个高效地求解最大化似然函数的方法。直接最大化l(θ)可能比较困难，那么我们的策略是不断地构造l的下界(E步)，然后最大化该下界(M步)。

对于每一个i，令Q_i是z⁽ⁱ⁾的某个分布(Σ_zQ_i(z) = 1, Q_i(z) >= 0; 如果z⁽ⁱ⁾是连续的，那么Q_i是概率密度函数)，引入Q_i后，我们有：

上式中最后一步的不等式是由于Jensen不等式推导而来。具体来说由于f(x) = log(x)是凹函数，并且我们把

这一项看成是[p(x⁽ⁱ⁾, z⁽ⁱ⁾; θ)/Q_i(z⁽ⁱ⁾)]关于z⁽ⁱ⁾的期望，所以根据Jensen不等式：

其中“z⁽ⁱ⁾ ~ Q_i”的下标表示这是关于z⁽ⁱ⁾的期望，而z⁽ⁱ⁾满足Q_i的分布。综上我们可以从等式(2)推导出等式(3)。

现在对于任意分布Q_i，等式(3)给出了l(θ)的下界。Q_i可以有很多选择，而我们应该选择Q_i使得l(θ)最接近下界，也就是说我们希望选择Q_i使得Jensen不等式的等号成立。

回顾下使得Jensen不等式等号成立的条件，对照上式可得如下的随机变量应该是常数：

其中c代表某个与z⁽ⁱ⁾无关的常数，我们把它写成如下的形式：

再加上我们已知Σ_zQ_i(z⁽ⁱ⁾) = 1，因此可推导出：

所以Q_i是在给定x⁽ⁱ⁾和θ两个参数下的z⁽ⁱ⁾的后验概率。

现在我们可以给出EM算法的基本步骤：

重复如下过程直到收敛：{

E步：对于每个i，令：
M步：按如下公式更新参数：

}

算法中的E步给出了l(θ)的下界函数，M步是在最大化该下界。当算法收敛时我们便得到了最优解。那么这个算法为什么能收敛呢？这里我们简单证明一下。

假设θ^(t)和θ^(t+1)是EM算法连续两次迭代中的参数，而θ^(t)是满足Jensen不等式成立的参数，所以：

而θ^(t+1)是使得l(θ^(t))最大化的参数，所以有：

因此我们证明了l(θ^(t+1)) >= l(θ^(t))，所以EM算法是单调递增的，由此可证算法是收敛的。

另外，如果我们定义：

那么EM算法可以视为将J函数作坐标上升的过程，其中在E步是固定θ使Q关于J求最大化，M步是固定Q使θ关于J求最大化。

混合高斯模型重述

在给出了通用的EM算法定义后，我们重新推导一下混合高斯模型中的EM算法。前面我们只描述了算法，但没有证明为什么参数需要按照给定的公式更新。

证明E步是很简单的，根据EM算法中的推导，可得：

而在M步中，我们需要最大化的目标函数是：

首先固定其他参数，关于μ作目标函数最大化，我们先求出目标函数关于μ的导数：

将导数设为0，可得：

这和我们之前给出的结论一致。

接下来我们再来求参数φ。将和φ有关的项进行合并，我们需要最大化的目标函数是：

除此之外，我们还有一个约束：所有的φ_j之和为1。为了最优化该问题，我们构建拉格朗日算子：

其中β是拉格朗日乘数，对L求导可得：

将导数设为0，可得：

另外我们求解β，可得：

将β代入回φ_j式中：

因此，我们推导出了参数φ。参数Σ的推导类似，这里就不做证明了。

总结

• 聚类算法是最常见的无监督学习算法，而K-Means算法是最常见的聚类算法
• Jensen不等式：令f是凸函数，X是随机变量，那么有：E[f(X)] >= f(EX)。如果f是严格凸函数，那么E[f(X)] = f(EX)当且仅当X = E[X]的概率为1(即X是常量)；如果f是凹函数，那么Jensen不等式也成立，但不等式的方向相反
• EM算法是一个迭代式的算法，分为两个步骤：E步和M步；EM算法也可以视为将目标函数作坐标上升的过程，每个步骤都是固定一个参数并估计另一个参数
• EM算法和K-Means算法的迭代过程比较类似，不同的是K-Means算法中每次对参数的更新是硬猜测，而EM中每次对参数的更新是软猜测；相同的是，两个算法都可能得到局部最优解，采用不同的初始参数迭代会有利于得到全局最优解
• 混合高斯模型是对单一高斯模型的扩展，可以通过EM算法进行参数求解

参考资料

• 斯坦福大学机器学习课CS229讲义 The K-Means Algorithm | Mixture of Gaussians | The EM Algorithm
• 网易公开课：机器学习课程 双语字幕视频