混合模型与期望最大化算法 (三)

写在前面：

大家好，我是强哥，一个热爱分享的技术狂。目前已有 12 年大数据与 AI 相关项目经验， 10 年推荐系统研究及实践经验。平时喜欢读书、暴走和写作。

业余时间专注于输出大数据、AI 等相关文章，目前已经输出了 40 万字的推荐系统系列精品文章，今年 6 月底会出版「构建企业级推荐系统：算法、工程实现与案例分析」一书。如果这些文章能够帮助你快速入门，实现职场升职加薪，我将不胜欢喜。

想要获得更多免费学习资料或内推信息，一定要看到文章最后喔。

内推信息

如果你正在看相关的招聘信息，请加我微信：liuq4360，我这里有很多内推资源等着你，欢迎投递简历。

免费学习资料

如果你想获得更多免费的学习资料，请关注同名公众号【数据与智能】，输入“资料”即可！

学习交流群

如果你想找到组织，和大家一起学习成长，交流经验，也可以加入我们的学习成长群。群里有老司机带你飞，另有小哥哥、小姐姐等你来勾搭！加小姐姐微信：epsila，她会带你入群。

第三章 混合模型与期望最大化

未标记的数据能够告诉我们：所有类中的实例是如何混合在一起的，他们是如何分布的。如果我们知道每个类中的样本是如何分布的，我们就可以将这些混合的数据分解为单独的类。这就是混合模型（mixture models）背后的思想。本章，我们详细讲解半监督学习中的混合模型的原理。首先我们回顾一些概率建模的概念。熟悉机器学习的读者可以跳到第 3.2 节。

3.1 监督分类的混合模型

例 3.1 包含 2 个组成成分高斯混合模型。假设训练数据来自两个一维高斯分布。图 3.1 展示了背后的分布 

 和一个小训练样本（只有两个标记的实例和几个未标记的实例）。

图 3.1 由 1 维高斯分布组成的包含两个类别的混合模型。虚线分别为 

 和 

。标记的和未标记的实例都绘制在了 x 轴上。

假设我们知道数据来自两个高斯分布，但我们不知道它们的参数(均值、方差和先验概率，我们后面会定义先验概率)。我们可以使用数据(标记的和未标记的)来估计这两个分布的参数。注意，在这个例子中，标记的数据实际上是具有误导性的，因为：标记的实例都在真实分布平均值的右边。我们可以通过未标记的数据来识别两个高斯分布的均值。基于给定的模型，通过计算，我们选择那个可以最大限度地提高生成训练数据概率的参数。值得一提的是，如果高斯分布的均值集中在未标记数据上，而不是在标记数据的右边，训练样本更容易生成。

设

是一个实例，我们将预测它的分类标签

我们将采用概率方法，寻求使条件概率

最大化的标签。这个条件概率指：给定实例下每个分类标签的可能性。根据定义，对所有

来说

并且

如果我们要将分类误差最小化，那么最好的策略是将

分到最可能的类

：

如果不同类型的错误分类(例如，将良性肿瘤错误地分类为恶性肿瘤 vs.恶性分类为良性)造成了不同的损失，那么上述策略在最小化预期损失方面可能不是最优的。我们将损失最小化的讨论推迟到后面的章节，但请注意，在概率模型中处理损失是更直接的方式。

我们如何计算

？一种方法是使用生成模型，该模型采用贝叶斯规则:

分母的和是所有类别

 的总和。

 称为类条件概率，

 称为先验概率。我们可以用一个外星人的例子来说明这些概率符号:

 对于一个特定的外星人，

是(体重，身高)特征向量，

是两个类别的概率分布:男性（male）或女性（female）。即

。有无穷多个

分布，每个特征向量

都有一个分布。

 这里只有两个类条件分布:

和

。其中每一个都是特征向量上的连续(如高斯)分布。换句话说，对于每种性别，某种体重、身高的组合比其他组合更可能出现，同时

度量了这些差异。

 先验概率

和

表示外星人口中男性和女性的比例。

此外，我们可以假设通过重复以下两个步骤，就可以从概率分布中“生成”独立同分布（i.i.d.）的实例-标签对

，这就是所谓的生成模型：

1. 抽样

。在外星人例子中，我们可以把

看成是（不均匀）硬币正面朝上的概率。这个抽样过程可以看成通过抛硬币选择性别。

2. 抽样

。在外星人的例子中，这表示抽样了一个二维特征向量，用来描述步骤 1 中选定了性别的外星人。

我们称

为实例和标签的联合分布（joint distribution）。

作为生成模型的一个例子，多元高斯分布是连续特征向量

的常用选择。该类条件分布具有概率密度函数：

其中

和

 分别是均值向量和协方差矩阵。其中一个例子是图像分类，

是表示图像像素强度的向量。每一类的图像都是按照高斯分布进行建模的。整体生成模型称为高斯混合模型(GMM)。

多项式分布是生成模型的另一个例子：

其中

是概率向量，是计数向量

建模的常见选择。例如，在文本分类中，x 是文档中的单词计数向量(所谓的词袋模型)。每个类别的文档都采用多项分布的方法建模，整体生成模型称为多项混合模型（Multinomial Mixture Model）。

隐马尔可夫模型(HMM)是生成模型的另一个例子，它通常被用于实例序列的建模。序列中的每个实例都生成于隐含状态，隐含状态的条件分布可以是高斯分布或多项式分布。此外，HMM 还确定了各个状态之间的转移概率，正是转移概率形成了实例序列。HMM 的学习包括估计条件分布的参数和估计转移概率。于是通过学习我们可以推断出用于在序列中生成实例的隐含状态。

一旦我们有了

，我们就知道如何进行分类了，但问题是如何从训练数据中学习这些分布。类条件

通常由一些模型参数决定，比如高斯分布中的均值 

 和协方差矩阵 

 。对于

，如果有

个类，我们需要预测

个参数：

。由于

被归一化了，所以概率

。我们用 

 表示

中所有参数的集合。一个更准确的表达是用

表示。训练目的就是找到一个好的 

 。但我们如何定义一个好的

 呢?

一个常见的标准是极大似然估计(MLE)。给定训练数据 

, MLE 为：

也就是说，MLE 是使数据似然

最大的参数。我们通常用对数似然

代替直接似然

。因为

是单调的，在产生相同的最大值的情况下，对数似然更容易处理。

在监督学习中，当

时，我们可以轻松的得到 MLE，我们可以将对数似然重新表示为：

这里我们使用了这样一个事实：一组 i.i.d.事件的概率是样本概率的乘积。寻找极大似然值是一个优化问题，以使对数似然值最大化。在监督学习中，优化问题通常是直接的，并产生直观的 MLE 解决方案，正如下面例子所示。

例 3.2 高斯混合模型的 MLE，全标记数据本例给出了当

 时，二类高斯混合模型的极大似然估计值的推导。我们首先建立一个约束优化问题：

在这里我们强制要求类的先验和必须为 1。接下来我们引入一个拉格朗日乘子

来形成拉格朗日量。

其中

 分别是类的先验估计，高斯均值和协方差矩阵。我们计算所有参数的偏导数。然后让每个偏导数等于零，求出直观的闭形式 MLE 解:

显然，拉格朗日乘子 

 的作用是对类先验进行强制规一化约束。

其中

 表示类

 中实例的数量。我们将式(3.9)代入(3.8)计算得到 

。最后，我们可以看到，类先验的 MLE 仅仅是每个类中实例的占比（即

）。接着我们来解类的均值。这里需要用到向量 

 的导数，一般设

 是一个向量，

 是一个大小合适的方阵，我们得到

 。接着能得出：

我们看到，每个类均值的 MLE 仅仅只是该类的样本均值。最后，协方差矩阵的 MLE 解为：

也就是该类中实例的样本协方差。

半监督分类的混合模型

在半监督学习中，训练数据

 由标记数据和未标记数据共同组成。似然值取决于有标记的数据，也取决于无标记的数据——这体现了无标记数据可能帮助混合模型进行半监督学习。解析上求解 MLE 已经不太可能了，然而，正如我们将在下一节中看到的，我们可以使用一种叫 EM 算法的迭代过程来找到参数估计的局部最大值。

由于训练数据由标记数据和未标记数据组成，如：

，对数似然函数现在定义为：

半监督对数似然(3.13)与先前的监督对数似然(3.6)之间的本质区别是第二项未标记的实例。我们将

 称作边际概率（marginal probability），定义为：

它表示从任何类中生成

 的概率。因此，边际概率说明了这样一个事实:我们知道有哪些未标记的实例，但不知道它们属于哪些类。混合模型的半监督学习相当于要找到式子(3.13)的极大似然估计。监督学习和半监督学习(对于混合模型来说)的唯一区别是目标函数不同。直观地说，半监督的 

 需要同时拟合标记的和未标记的实例。因此，它与监督 MLE 的不同是显而易见的。

未观测到的标记

 被称为隐藏变量。隐藏变量会使对数似然(3.13)变得非凹，并且难以优化。幸运的是，对于寻找局部最优θ这个问题，我们已经找到了几种很好的优化方法。我们将在下一节中提出一种特别重要的方法——期望最大化(Expectation Maximization，EM)算法。对于高斯混合模型(GMMs)、多项式混合模型、还有 HMM 等来说，当存在无标记数据时，EM 算法已经成为了一种求解极大似然值(MLE)事实上的标准优化技术。HMM 的 EM 算法甚至有自己的名字: Baum-Welch 算法。

EM 优化算法

观测数据为

，隐含数据为

。设模型参数为θ。EM 算法是一个迭代过程，它用用来寻找使 

 局部最大化的θ。

算法 3.3 一般的期望最大化(EM)算法。

输入：观测数据

，隐含数据

，初始参数

。

1. 初始化

2. 重复以下步骤，直到

收敛。

3. E-步骤：计算

4. M-步骤：求

，使

最大化。

5. 

输出：

这里我们对 EM 算法的几个重要方面进行说明：

为隐含标签分布，它可以被认为是根据当前模型

，为未标记的数据分配“软标签（soft labels）”。

 可以证明 EM 在每次迭代时都提升了对数似然 

 。然而，EM 只收敛于局部最优解（local optimum）。也就是说，它找到的

 只有在参数空间的邻域内保证是最好的；它可能不是一个全局最优解（global optimum）（我们所期望的 MLE）。该过程完整的证明超出了本书的范围，你可以在 EM 的标准教科书中找到。

l EM 收敛的局部最优值取决于初始参数

 。

的一个常见的选择是一组小的标记训练数据的极大似然估计值。

上述通用的 EM 算法需要更具体的设定才能用于某种特定的生成模型。

例 3.4．带有隐含变量的 2 类 GMM 的 EM 算法。我们在一个简单的 GMM 生成模型上说明 EM 算法。在这种特殊情况下，我们观察到的数据只是带标记的和未带标记的实例样本。隐含变量是未标记实例的标签。为了学习利用两个高斯分布拟合数据的模型参数，EM 算法如下。

算法 3.5. GMM 的 EM 算法

输入：观测数据

1. 初始化

，标注数据的 MLE 估计

2. 重复以下步骤，直到对数似然

收敛。

3. E-步骤：对于所有未标记的实例

，计算：

对于标记的实例，如果

，则定义

，否则定义为 0.

M-步骤：使用当前的

，求解

。对于

，有如下算式，

5. 

输出：

该算法从单独求解标注数据的 MLE 开始。然后 E-步骤计算

值，这可以被看作是对实例的类标签的软赋值。这个过程有时被称为“责任（responsibilities）”(即第一个类负责

，同时概率为

)。

M-步骤使用当前的

值作为未标记实例的权重来更新模型参数。如果我们认为 E-步骤是利用少量的（fractional）带标签的实例在不同类中分割，那么 M-步骤只是使用这些少量的实例和带有标签的数据来计算新的 MLE 参数。当对数似然(3.13)收敛时（从一次迭代到下一次迭代，似然函数值不变），算法停止。在两个高斯混合的情况下，数据的对数似然是：

对于未标记的数据，我们已经在这两个类别中进行了边缘分布计算。

EM 和自训练之间的相似性是值得我们注意的。EM 可以被看作是一种特殊形式的自训练, 分类器θ会用所有可能的标签来标记未标记的实例，但每个都使用（一定的概率）分数权重

 。 然后，我们用这些被增强的未标记数据（而不用那几个最值得信赖的数据）来更新分类器。

3.4 混合模型假设

混合模型为半监督学习提供了一个框架，其中未标记数据的作用是明确的。在实践中，如果生成模型是(近似)正确的，那么这种半监督学习形式是非常有效的。下面的假设值得我们注意:

注释 3.6. 混合模型假设 数据实际上来自混合模型，其中混合成分的数量、先验概率

和条件概率

 都是正确的。

这个假设不好的一点是，由于我们没有太多标记的数据，所以很难评估模型的正确性。很多时候，人们会选择基于领域知识的生成模型或者具有数学方便性的模型。然而，如果模型是错误的，那半监督学习实际上会损害模型的准确性。在这种情况下，我们最好只使用标记数据并进行监督学习。下面的一个例子展示错误的模型所造成的后果。

例 3.7．一个不正确的生成模型  假设一个数据集包含四组数据，每个类两组。该数据集如图 3.2 所示。正确的决策边界是沿着 x 轴的水平线。显然，数据不是由两个高斯函数生成的。如果我们坚持每个类都用一个高斯函数来建模，那么结果可能会很差。图 3.3 通过比较拟合该数据的两种可能的 GMMs 来说明这一点。在图(a)中，学习到的模型对无标记数据拟合得相当好(具有很高的对数似然)，但是使用该模型的预测将导致大约 50%的错误。相比之下，图(b)中拟合的模型将带来非常好的精度。然而，(b)模型不会受到 EM 算法的青睐，因为它的对数似然较小。

图 3.2 四组聚集数据中的两个类(分别为二维高斯分布)

图 3.3 (a)在错误模型假设下的良好拟合。决策边界是垂直的，从而产生较大的误差。(b)在错误的模型假设下，拟合度更差。然而，决策边界是正确的。

如上所述，在这种情况下，我们最好只使用标记数据和监督学习。如果我们在左下方的聚类和右上方的聚类中标记数据，那么监督学习的决策边界将近似于直线

，这将导致大约 25%的误差。

有很多方法可以减轻使用错误模型的危险。一个常见的方法是细化模型，使其更好地拟合目标，这需要一些相关领域的知识。在上面的例子中，我们可以将每个类本身建模为带有两个组件的 GMM，而不是一个单一的高斯函数。

另一种方法是不再过分强调未标记的数据，以防模型的正确性不好保证。具体地说，我们将半监督对数似然(3.13)中未标记数据的贡献缩放为一个小的正权重

当

 时，未标记数据的影响消失，这就变成了监督学习了。

3.5 生成模型中的其他问题

在定义生成模型时，可识别性（identifiability）是一个理想的属性。如果

（混合组件的在下标置换下保持不变），那么我们就说一个模型是可识别的。也就是说，如果两个模型的区别只在于哪个组件被称为组件一，哪个组件被称为组件二，依此类推，那么它们就被认为是等价的。也就是说，有一个唯一的(在置换下唯一)模型θ来解释观察到的未标记数据。因此，随着未标记数据量的增长，人们希望准确地识别混合成分。例如，GMMs 是可识别的，而其他一些模型则不能。下面的例子展示了一个无法识别的模型，以及为什么它不适合半监督学习。

例 3.8．不可识别生成模型  假设组件模型

对于

是一致的。让我们试着用半监督学习来学习这个均匀分布的混合数据。我们得到了大量的未标记数据，因此我们知道

在

中是均匀的。我们知道两个有标记的数据点

。我们能从中确定 

 的标签吗？

答案是否定的。根据我们的假设，我们无法区分以下两个模型(以及无数其他模型):

两个模型都与未标记数据和标记数据吻合，但第一个模型预测在 x = 0.5 时，标记 y = 1，而第二个模型预测 y =-1。下图 3.4 说明了这一点。

图 3.4:一个无法识别的模型。即使我们知道

是两个均匀分布的混合，我们也不能唯一地识别这两个组件。例如，两组混合模型产生相同的

，但它们对 x =0.5 的分类不同。注意，每个分布的高度代表一个概率密度(可以大于 1)，而不是概率质量。每个分布下的面积为 1。

生成模型的另一个问题是局部最优（local optima）。即使模型是正确的、可识别的，但以模型参数θ为函数的对数似然(3.13)一般都是非凹的。也就是说，表面可能有多个“凸起”。最高的凸起对应全局最优（global optima），即期望的 MLE。其他的是凸起是局部最优。EM 算法容易陷入局部最优当中，这可能导致模型效果较差。针对局部最优的一个标准实的实践方案是随机重启（random restart），因此其中的 EM 算法要运行多次。每次 EM 从一个不同的随机初始参数

开始。最后，通过比较 EM 在每次运行中收敛得到的对数似然，去选择那个与最优对数似然（即最大对数似然）相对应的θ。值得注意的是，随机重启并不能彻底解决局部最优问题——它只是缓解了该问题。选择一个更好的 

，就更有可能得到全局最优(或者仅仅是一个更好的局部最优)，这是另一种启发式方法，尽管这可能需要一些相关领域的专长。

最后，我们注意到混合模型半监督学习的优化目标是最大化对数似然(3.13)。EM 算法只是几种寻找（局部）最优的优化方法中的一种。我们也可以采用直接的优化方法，例如拟牛顿法（如 L-BFGS）等方法。

3.6 聚类-标记（CLUSTER-THEN-LABEL）方法

我们使用 EM 算法从未标记的数据中识别数据混合成分。提醒一下，无监督聚类算法也可以从未标记的数据中识别聚类。于是，提出了一种自然的聚类-标记算法来进行半监督分类。

算法 3.9. 聚类 0 标记算法 

输入: 标记数据

，未标记的数据

，聚类算法

，监督学习算法

。

1. 用

 聚类

。

2. 对于每个产生的聚类，设 S 为该聚类中已标记的实例：

3. 如果 S 非空，从

 中学习一个有监督的预测器。

将

 应用于此聚类中所有未标记的实例。

4. 如果 S 是空的，使用从所有标记数据输出训练的预测器 

输出:未标记数据上的标记

。

在第 1 步中，聚类算法 

 是无监督的。在第 2 步中，我们学习了一个有监督的预测器，它使用每个聚类中已标记的实例，并使用预测器标记该聚类中未标记的实例。可以使用任何聚类算法 

 和监督学习算法

 。值得注意的是，聚类-标记算法并不一定涉及概率混合模型。

下面的例子展示了一个聚类-标记算法，对于

 ，使用分层凝聚聚类方法（Hierarchical Agglomerative Clustering），对于 

，在每个聚类中使用简单的多数投票方法。

Example 3.10. 利用分层凝聚聚类的聚类-标记算法在本例中，我们对第一章中的外星人数据采用聚类-标注算法建模。对于第一步，我们使用分层凝聚聚类(算法 1.1)，以欧氏距离作为距离函数，用单链接方法（single linkage method）确定聚类之间的距离。因为标记数据只包含两个类，所以我们启发式地在剩两个类时停止算法迭代。聚类-标记算法中的步骤 2-4 用于：在每个聚类中找到投票最多的（大多数数据具备的）标签，并将这个标签分配给聚类中剩下的所有未标记实例。

图 3.5 展示了原始的部分标记数据，两个聚类，以及所有数据的最终预测标签。在本例中，因为聚类与数据的真正标记一致，所以我们正确地对所有未标记的实例进行了分类。中间的图片里实例之间的线表示负责合并聚类直到剩下连个类的连接。

 3.5 聚类-标记：利用分层凝聚聚类算法（

）和多数投票算法（

）

事实证明，在这里使用单链接（single linkage）是非常重要的，因为自然形成的聚类是又长又瘦的。不同的选择，比如完全链接聚类（complete linkage clustering），会形成一些分布更圆的聚类。当应用于此数据时，全链接将产生如图 3.6 所示的结果。通过全链接发现的聚类与数据的真实标注不匹配。事实上，具备两个标记的实例最终都出现在同一个聚类中。因为在两个类中都没有“多数”标签，多数投票算法最终会随机地打破他们之间的联系并终止，从而为所有未标记的实例分配随机标签。

事实证明，在这里使用单链接（single linkage）是非常重要的，因为自然形成的聚类是又长又瘦的。不同的选择，比如完全链接聚类（complete linkage clustering），会形成一些分布更圆的聚类。当应用于此数据时，全链接将产生如图 3.6 所示的结果。通过全链接发现的聚类与数据的真实标注不匹配。事实上，具备两个标记的实例最终都出现在同一个聚类中。因为在两个类中都没有“多数”标签，多数投票算法最终会随机地打破他们之间的联系并终止，从而为所有未标记的实例分配随机标签。

图 3.6 使用完全链接分层凝聚聚类做聚类-标记学习，最终导致学习到的标签跟数据的真实标签不一致

这个例子的重点并不是要说全链接不好，而单一链接更好。事实上，对于其他数据集来说，情况可能正好相反! 这个例子是为了突出半监督学习对其潜在假设的敏感性——在本例中，聚类与决策边界相一致。如果这个假设不正确，结果可能会很差。

本章介绍了混合模型和半监督学习的期望最大化(EM)算法。我们还回顾了使用生成模型时所面临的一些常见问题。最后，我们提出了一种非概率的、聚类-标签的方法，这种方法使用了与混合模型相同的直觉:未标记的数据帮助识别输入空间中对应于每个聚类的类。在下一章中，我们将转向一种不同的半监督学习方法，即协同训练（co-training），它使用一种非常不同的直觉——涉及多个实例的特征表示。