半监督学习概述 (二）

写在前面：

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

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

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

内推信息

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

免费学习资料

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

学习交流群

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

第二章

半监督学习概述

2.1 通过标记数据和未标记数据进行学习

顾名思义，半监督学习介于非监督学习和监督学习之间。事实上，大多数半监督学习策略都是源于监督学习和非监督学习的某种拓展，以求包含这两种范式所特有的附加信息。具体来说，半监督学习包括以下几种不同的场景:

半监督分类。也叫做对有标签数据和无标签数据(或部分标签数据)的分类，是一种对监督分类问题的拓展。训练数据由

个标记的实例

和

 个未标记的实例

组成。通常我们会假设无标签数据比有标签数据多得多，

 。

· 半监督分类的目标是得到一个分类器，这个分类器是通过对有标签数据和无标签数据训练而得到的，它比我们单独训练有标签数据得到的监督分类器更好。

约束聚类。这是无监督聚类的一种拓展。训练数据包括未标记的实例

以及一些关于类（cluster）的 “监督信息”。例如，这些信息可以是所谓的必须链接约束（must-link constraints），即两个实例 

必须在同一个类中; 也可以是非链接约束（cannot-link constraints），即两个实例

· 能在同一个类中。我们也可以约束并限制类的大小。约束聚类的目标是获得一个（比从无标记数据得到的聚类）更好的聚类。

还有很多其他半监督学习场景，包括：有标签数据和无标签数据的回归，有标签实例（实例的约化特征表示已给出）的降维等。在这本书里，我们将着重分析半监督分类。

半监督学习的研究由两个因素推动：1.  实用价值：构建更好的计算机算法；2.理论价值：理解机器学习和人类学习。

半监督学习具有巨大的实用价值。在许多任务中，有标记数据非常缺乏。因为标记数据需要人工的注解、以及特殊的设备或昂贵而缓慢的实验，所以标签  

可能很难获得。比如：

· 在语音识别中，实例

 是一句语音，标签

 是这句语音对应的副本记录。下边列举了一些单词发音时的详细语音记录：

基于人工的精准转录是非常耗费时间的：在交换机电话会话语音数据转录中，需要花费长达 400 小时的时间来（在语音层面）转录 1 小时的语音[71]。（这些录音包含随机分配的参与者们讨论的各种话题：比如社会、经济、政治和环境问题。）

· 在自然语言解析中，实例 

 是一个句子，标签

 是对应的解析树。“全国田径冠军赛结束”这句中文的解析树示例如下所示。

训练数据由“句子-解析树”对组成，这些训练数据被称为树库（treebank）。树库的构建是耗时的，这需要语言学家专业的知识:在创建宾夕法尼亚中文树库时，专家们耗时长达两年时间，仅为 4000 个句子手工创建了对应的解析树。

· 在垃圾邮件过滤中，实例 

 是电子邮件，标签

 是用户的判断(该邮件是否为垃圾邮件)。在这种情况下，瓶颈将会是普通用户对标记大量电子邮件的耐心。

· 在视频监控中，实例

 是视频帧，标签

 是视频中对象的身份。因此在大量监控视频画面中手工标注目标是一项繁琐且耗时的工作。

· 在蛋白质三维结构的预测中，实例

 是一个 DNA 序列，标签 

 是 3D 蛋白质折叠结构。因此鉴定单个蛋白质的三维结构可能需要专业的晶体学家们进行数月的昂贵实验工作。

虽然标记过的数据 

 在这些领域很难获得，但未标记的数据 

 易于收集且可以大量获得：无线电广播可录下讲话内容； 文本句子可以从万维网（World Wide Web）上抓取；电子邮件存储于邮件服务器；监控摄像头一天 24 小时运行；蛋白质的 DNA 序列可以从基因数据库中轻易获取。然而，遗憾的是，传统的监督学习方法无法使用未标记的数据来训练分类器。

半监督学习很有吸引力，因为通过潜在地利用标记数据和非标记数据，它可以实现比监督学习更好的性能。从另一个角度来看，半监督学习使用更少的标记实例达到与监督学习相同的性能。这种方法减少了标注工作，从而降低了成本。我们后续将在第 3、4、5、6 章中介绍几种计算模型。

半监督学习还提供了一种计算模型，它阐释了人类如何从标记数据和非标记数据中学习。以儿童的概念学习任务（这个任务类似于分类）为例：实例

是一个对象(比如：动物)，标签 

 是与之对应的概念(比如：狗)。孩子们会从老师那里得到有标签的数据(例如：爸爸指着一只棕色的动物，然后说“狗”!)。但更常见的情况是，孩子们通常自己观察各种动物，而不接受明确的标签。显然，孩子们能够结合“有标签数据”和“无标签数据”来促进概念学习。因此，半监督学习的研究是建立机器学习和人类学习之间桥梁的一个机会。我们将在第 7 章讨论一些最近的研究。

半监督学习可行吗？

乍一看，人们可以从未标记的数据中了解关于预测因子

 的所有信息，这似乎是自相矛盾的。毕竟 

 是从实例 

 到标记

 的映射，但是未标记的数据并没有提供任何这样的映射。问题答案的得出基于人们的假设：即关于“无标签数据的分布

与目标标签之间的联系” 的假设。

图 2.1 展示了半监督学习的一个简单例子。每个实例都用一维特征 

 表示。包含两类：正标签数据、负标签数据。现在我们来考虑以下两种情况：

1. 在监督学习中，我们只得到两个标记的训练实例：

 和

，他们分别由图中红色和蓝色的符号所表示。决策边界的最佳估计值显然是

 ：那么所有

 的实例都应该被分类为

，而那些  

 的实例则归为

 。

此外，我们还拥有大量未标记的实例，如图中的绿色圆点所示。这些未标记实例的正确类标签是未知的。然而，我们观察到他们自动的组成了两组。假设每个类的实例都能组成一个连贯的小组（比如，

 为高斯分布，即每个类的实例都围绕着一个中心平均值分布），那么这些未标记的数据就能给我们提供更多的信息。准确的说，上述的“两个标记的实例”的例子似乎并不是类的最典型示例。我们对决策边界的半监督估计值应该在这两个组之间，即 

。

图 2.1. 一个简单的例子

如果我们的假设是真的，那么使用标记数据和未标记数据就可以给我们一个更可靠的决策边界估计值。直观地说，未标记数据的分布有助于识别具有相同标签数据所在的区域，少数标记数据则提供真实的标签。在本书中，我们将介绍一些其他常用的半监督学习假设。

归纳式学习 vs. 传递式半监督学习

实际上有两种半监督学习场景，他们略有不同，即归纳式半监督学习和传递式半监督学习。回想一下，在监督分类中，训练样本是完全标记的，所以我们总是对预测器在未来测试数据集的上表现感兴趣。在半监督分类中，训练样本包含一些未标记的数据。因此，就产生了两个截然不同的目标：一是预测未来测试数据的标签；二是预测训练样本中未标记实例的标签。我们称前者为归纳式半监督学习（inductive semi-supervised learning），后者为传递式学习（transductive learning）。

定义 2.1. 归纳式半监督学习。给定一个训练样本

，归纳半监督学习训练了一个函数

 ，期望

 在推理未来数据（超出

的部分）时是一个很好的预测器。

就像在监督学习中一样，我们可以通过使用单独的测试样本

 来估计未来数据的表现，这些单独的测试样本是没法用于模型训练的。

定义 2.2. 传递式半监督学习。给定一个训练样本

，传递式学习训练了一个函数

，期望

 对于未标记的数据

是一个很好的预测器。注: 

 仅在给定的训练样本上定义，不需要在训练样本之外进行预测。因此，它是一个更简单的函数。

来看一个有趣的比喻：归纳式半监督学习就像一场随堂考试，学生事先并不知道考试的题目，他们需要准备所有可能出现的问题；相反的，传递式学习就像开卷考试，学生知道所有的考题，他们不需要复习准备这些考题以外的内容。

注意事项

半监督学习可以使用额外的未标记数据来学习更好的预测器

，这似乎是合理的。虽然在映射过程

 中，未标记数据不起任何作用。如上文所述，问题的关键在于建立边际分布

 和条件分布

 之间联系（link）的半监督模型假设。有几种不同的半监督学习方法，每种方法对此联系（link）的假设都略有不同。这些方法包括自训练（self-training），概率生成模型（probabilistic generative models），协同训练（co-training），基于图的模型（graph-based models），半监督支持向量机（semi-supervised support vector machines）等。在接下来的几个章节中，我们将仔细研究这些模型并讨论它们的假设。在 8.2 节中，我们也将给出一些理论论证。根据以往的经验，这些半监督学习模型在某些数据集上确实训练出了比监督学习更好的分类器。

值得指出的是，盲目地为特定任务选择半监督学习方法并不一定比监督学习方法效果好。事实上，未标记的数据在错误的链接假设下会导致更糟糕的表现。下面的例子展示了一个简单的分类问题，我们通过比较监督学习和半监督学习的方法的性能和表现，说明了模型假设的敏感性。如果这些方法看起来很神秘，不要担心；我们将在本书的其余部分详细解释它们的工作原理。目前，很重要的一点是，半监督学习的效果取决于对该问题的模型所作的假设的正确性。

例 2.3. 考虑一个分类任务，包含两个高斯分布的类。这两个高斯分布严重重叠(如图 2.2 的顶部)。真正的决策边界位于两个分布的正中间，由虚线表示。由于我们知道真实的分布，所以我们可以根据每个高斯分布在决策边界错误一侧的概率质量来计算测试样本的错误率。由于类的分布是重叠的，所以最小错误率（即贝叶斯 Bayes 误差）为 21.2%。

通过监督学习所得到的决策边界位于两个标记的实例中间，未标记的实例则被忽略，参见图 2.2 的第二个图表中的粗实线。我们注意到它偏离了真正的决策边界，因为这两个标记的实例是随机抽样的。如果我们画出另外两个标记的实例，那么通过他们学习到的决策边界将会改变，但很可能仍然偏离真实边界（如图 2.2 其他图表所示）。大体来说，我们预期学习到的决策边界将与真正的边界重合，但对于任何实际给定的标记数据，它将会有相当大的偏差。于是，我们说学习到的决策边界有很大的方差。为了评估监督学习和即将介绍的半监督学习方法，我们绘制了 1000 个训练样本，每个样本有 1 个标记的实例和 99 个未标记的实例。与最优决策边界相比，使用监督学习得到的决策边界平均测试样本错误率为 31.6%，平均决策边界位于 0.02(与最优边界为 0 相比)，标准差为 0.72。

图 2.2. 五种随机样本的有标记训练样本和无标记训练样本的几种算法学习的决策边界

下面我们省略具体细节，给出三种半监督学习模型在训练数据上得到的学习决策边界。这些模型将在后面的章节详细介绍。首先是一个概率生成模型，该模型基于正确的模型假设而构建，它用 EM (第 3 章)学习了两个高斯分布，通过该模型得到的决策边界如图 2.2 虚线所示。通过该模型得到的边界非常接近真实决策边界，并且彼此很相似，即该算法的方差较小。经过 1000 次平均测试，该算法的样本错误率为 30.2%，平均决策边界为-0.003，标准差为 0.55，这表明该算法比监督模型更准确、更稳定。

第二个模型是半监督支持向量机（第 6 章），它假定决策边界不应该通过未标记数据密集的区域。然而，由于这两个类的分布严重重叠，所以真正的决策边界实际上通过了最密集的区域。因此，这个模型假设并不完全匹配此任务。它学习到的决策边界以点划线的形式如图 2.2 所示。这个结果比有监督分类的效果更好，而且效果和做出正确模型假设的概率生成模型差不多。这个方法得到的测试样本平均错误率为 29.6%，平均决策边界为 0.01(标准差为 0.48)。尽管该模型的假设是错误的，但这种方法使用了两个包含（大致）相同数量的实例的类，因此决策边界靠近中心。这也许可以解释为什么与正确的模型相比，它的表现更让人惊喜。

第三种方法是：基于图的模型(第 5 章)，它用一种典型方法生成图形: 标记数据和未标记数据中的任何两个实例都由一条边连接。如果两个实例距离较近，则边的权值较大;如果它们距离较远，则边的权值较小。基于该模型所做的假设是，所有与大权重边连接的实例往往具有相同的标签。然而，在这个例子中，两个类的分布重叠，所以来自不同类的实例可能会非常靠近，并且这些实例会通过大权重边相连接。因此，该模型的假设与我们的任务不匹配。该模型的结果如图 2.2 细实线所示。基于图的模型平均测试样本错误率为 36.4%，平均决策边界为 0.03(标准差为 1.23)。因此基于图的模型不适合这个任务，它甚至比监督学习的表现更糟糕。

如上述的例子所示，模型假设在半监督学习中起着重要的作用。它弥补了标记数据的不足，可以确定预测器的质量和效果。然而，在半监督学习中，做出正确的假设(或发现错误的假设)仍然是一个开放性的问题。这意味着对于“我应该使用哪个半监督模型?”这个问题，没有一个简单的答案。因此，本书将主要介绍方法论。大多数章节将介绍一系列不同的半监督学习模型。接下来我们从一个简单的半监督分类模型开始:自训练模型。

2.2 自训练模型

自我训练模型的学习过程是很有特点的，它使用自己的预测结果来自学。因此，它也被称为自教模型（self-teaching）或自助模型（bootstrapping）（不要与同名的统计过程混淆）。自我训练可以是归纳式的，也可以是传递式的，这取决于预测器

的性质。

算法 2.4.自训练。

输入：标记数据

，和未标记数据

。

1. 初始化，

。

2. 重复：

3.       使用监督学习从

 中训练出

。

4.       将 

 应用于 

 中未标记的实例。

5.       从 

 中去掉子集 

，把

添加到

 中。

该方法的主要思想是首先在标记数据上训练

，其次使用

 来预测未标记数据的标签。然后选择未标记数据的子集

 及其预测的标签，以增加标记数据。通常，

 由少数未标记的实例组成，并且这些实例的

 预测值是高度可信的（即，我们比较确信预测是对的）。 接下来

在更新后的更大的标记数据集上重新进行训练，然后不停重复这个过程。 

 也有可能是整个未标记的数据集。在这种情况下， 

 和 

 仍然是整个训练样本，但是在没有标记的实例上，预测的标签值可能随着迭代不同而不断变化。

注释 2.5. 自训练假设。自训练的假设是预测器

 的预测值（至少对于高度可信的预测）往往是正确的。当类（classes）形成分离良好的簇/类（clusters）时，可能会出现这种情况。

自训练的主要优点是简单，而且它是一种包装（wrapper method）方法。这意味着对于步骤 3 中

 的选择是完全开放的，没有任何限制。例如，

 可以是一个简单的 kNN 算法，也可以是一个非常复杂的分类器。自训练过程“包装”了

 ，而不改变其内部工作方式。这对于许多现实任务来说很重要，比如在自然语言处的任务中，

 可能是难于调优的复杂的黑盒模型。

从另一方面来讲，我们可以想象，如果存在一个由

 (由于初始

 很小，一开始就不够理想)所造成的早期错误，那么自训练可能会通过生成错误的标记数据不断放大错误。于是在下一次迭代中，使用这些错误的数据进行再训练将导致更糟糕的

 。不过人们已经提出了各种启发式的方法来缓解这个问题。

例 2.6. 作为自我训练的一个具体例子，我们现在介绍一种称为传递 1-NN 最近邻（propagating 1-nearest-neighbor）的算法，并用外星小绿人数据进行说明。

算法 2.7.传递最近邻（Propagating 1-Nearest-Neighbor）

输入：标记数据

，未标记数据

，和距离函数 d（）

1. 初始化，

 .

2. 重复，直到

 是空集。

3.     选择

4.     设置

 为

 中离

 最近的实例的标签。

5.     从

 中去掉 

 ；把 

 加到 

 中。

这个算法包装了一个 1-NN 最近邻分类器。在每次迭代中，它选择最接近任何标记实例的未标记实例(即，当前 

 中的任何实例，该实例可能是之前的迭代生成的，即原来在 U 中，后面通过该算法生成了标签)。该算法将与当前标记数据的距离来作为置信度的判定标准（即假设距离近的样本标签是一样的）。然后，为所选实例指定其最近邻居的标签，并将其插入到 

 中，就好像它是真正的有标签数据一样。该过程将持续重复，直到所有的实例都添加到了 

 中。

现在我们回到 100 个外星小绿人的数据中。假设你只与一名男性和一名女性外星人面对面(即有标签的数据)，但其他 98 人的体重和身高对你来说都是未知的（即无标签数据）。你想把所有的外星人按性别分类，所以你使用了“传播 1-NN 最近邻”方法。图 2.3 演示了三次特定迭代后的结果，以及所有实例的最终标记。原始标记的实例显示为大符号（即下图 a 中的红色叉和蓝色圈），而算法标记的实例显示为小符号（即下图 b、c、d 中的小的红色叉和蓝色圈），未标记的实例则显示为绿点。下图展示了标签向邻居传播的方式，扩展正负实例的集合，直到所有实例都被标记。这种方法非常有效，可以完全恢复图 1.3(a)中显示的真实标签。这是因为对于这个数据集来说，模型假设“类（classes）形成了分离良好的簇/类（clusters）”是正确的。

图 2.3: 传递 1-NN 最近邻方法应用于外星小绿人数据

现在通过引入一个离群值来修改这个数据，离群值位于两个类之间，它是一个不合理的实例，出现在离其他数据很远的地方。在本例中，实例远离任何类的中心。如图 2.4 所示，该离群值打破了一个良好的分离聚类假设，导致算法出现偏差。显然，自训练方法(如传递 1-NN 最近邻)对可能导致传递不正确信息的离群值非常敏感。在当前这个例子中，避免这个问题的一种方法是：在选择下一个要标记的点，在给该点分配标签时，不只考虑单个最近的邻居（可以考虑多个邻居）。

图 2.4 传播最近邻，离群值图解。(a)经过几次迭代后，(b,c)突出离群值的效果，

(d)标记所有实例，结果将整个最右边的类标记错误。

这一节我们总结了对半监督学习背后原理的基本介绍，以及必须关注的各种问题。我们还展示了一个简单的半监督学习的例子，以展示在半监督学习中可能导致算法正确或者失败的情形。在下一章中，我们将深入讨论一种使用生成概率模型的更复杂的半监督学习算法。