1.1 监督、非监督、半监督机器学习

为了理解半监督学习的本质，了解下监督和非监督学习是很有帮助的。

1.1.1 监督与非监督学习

传统上，机器学习有两个完全不同类别的任务。

第一就是非监督学习。设 为 n 个样本的数据集，这儿  对所有 。典型地它假设所有数据点服从一个  上的独立同分布。通常非常方便，定义 （n x d）矩阵 其中行表示数据点。非监督学习的目标是找到数据集 有意义的结构。有人认为，非监督学习的问题基本上是估计一个可能产生的密度。然而，无监督学习也有较弱的形式，如分位数估计、聚类、离群值检测和维数约简。

第二个任务就是监督学习。其目标是，给定一个由对构成的训练集，学习一个从 x 到 y 的映射。这儿， 被叫做样本  的标签或目标。如果这些标签是数字，表示标签的列向量。同样，标准要求是从分布在上的一些分布中采样的。任务定义得很好，因为映射可以通过它对测试示例的预测性能来评估。当 或（或更通常地，当标签是连续地的时候），这些任务被称作回归。本书将主要关注分类，即，y 的取值有限（离散标签）的情况。监督学习有两族算法，生成算法试图通过一些无监督的学习过程对类条件密度进行建模。利用贝叶斯定理可以推导出预测密度：

        (1.1)

实际上， 是生成数据对 的数据的联合密度。判别式算法不尝试估计是如何生成的，而是集中于估计。有些判别式模型甚至限制自己仅拟合是否大于或小于0.5，其中的一个例子就是支持向量机（SVM）。有人认为，判别式模型更直接地符合监督学习的目标，因此在实践中往往更有效率。这两种架构将在 2.2.1 和2.2.2 章节深入探讨。

1.1.2 半监督学习

半监督学习（SSL)介于监督学习和半监督学习之间。对于没有标记的数据来说，该算法提供了一些监督信息，但不一定适用于所有示例。通常，这些信息会是与一些样本相关联的指标，这种情况下，数据集 可分为两部分：点集 ,对应标签 会被提供；和点集 对应标签不知道。这是本书中研究的“标准”半监督学习；大多数章节都会提到这种设置。

其它形式的部分监督也是可能的。例如，可能有些限制如“这些样本点有（或没有）一样的指标”（Abu-Mostafa, 1995）。这类更一般的设置将在第 5 章探讨。不同的设置对应着对半监督学习的不同观点：在第 5 章，SSL 被看着是由限制引导的非监督学习。相比之下，大多数其他方法将 SSL 视为有监督的学习，并提供有关示例x分布的附加信息。后者的解释似乎更符合大多数应用，其目标和监督学习的一样：预测一个给定的的目标值。然而，如果事先不知道类的数量和性质，但必须从数据中推断，则不容易应用此看法。对比之下，作为带有约束的无监督学习的 SSL 可能仍然适用于这种情况。

几十年前，Vapnik 已经提出了一个与 SSL 相关的问题：所谓的转导学习。在这种设定中，会提供一个（标记过的）训练集和一个（未标记的）测试集。转导的理念是只对测试点进行预测。这与归纳学习不同，归纳学习的目标是输出一个在整个空间上定义的预测函数。本书中描述的许多方法都是转导的；特别是，这对于基于数据图形表示的推理更加自然，这一问题将在第1.2.4节中再次讨论。

1.1.3 半监督学习简史

或许最早提出在分类中使用非标记数据的是自我学习，这也被称为自我训练、自我标记或决策导向学习。这是一种包装算法，它重复使用有监督的学习方法。开始只使用有标签数据进行训练，每一步都有一部分未标记数据点根据当前的决策函数进行标记；然后监督学习器使用自己的预测作为标记数据点重新训练。这种思想在资料里已经出现了一段时间了（如：Scudder(1965); Fralick (1967); Agrawala (1970))。

自我学习的一个不令人满意的方面是包装的效果取决于包装内部使用的监督方法。如果将自学习与经验风险最小化和1-0-损失相结合，则未标记的数据对解完全没有影响。如果使用的是边际最大化方法，那么决策边界将被推离未标记的点（参见第6章）。在其他情况下，似乎不清楚自我学习到底在做什么，以及它对应的假设是什么。

与半监督学习密切相关的是由 Vapnik（vapnik chervonenkis，1974年；推理 Vapnik和Sterin，1977年）开创的推理或转导概念。与归纳推理相比，不推断一般的决策规则，只预测未标记（或测试）点的标签。Hartley 和 Rao（1968）已经提出了一个早期的转导实例（尽管没有明确地将其视为一个概念）。他们建议在测试点的标签上进行组合优化，以最大化其模型的可能性。

在20世纪70年代，当考虑到用未标记数据估计费希尔线性判别规则时，半监督学习似乎真的开始了（Hosmer, 1973; McLachlan, 1977; O’Neill, 1978; McLachlan and Ganesalingam, 1982)。更准确地说，设置是在每一类条件密度是高斯分布的情况下，协方差矩阵相等。然后，在期望最大化（EM）算法等迭代算法的帮助下，使用标记和未标记的数据最大化模型的可能性(Dempster et al., 1977)。在（Cooper和Freeman，1970年）中，人们研究了使用标记和未标记数据估计的多项式分布的混合分布，而不是估计高斯分布的混合分布。

后来，这种每类一个组件的设置已扩展到每类几个组件（Shahshahani和Landgrebe，1994年），并由Miller和Uyar（1997年）进一步推广。

Ratsaby和Venkatesh（1995年）为两个高斯混合分布的半监督学习推导了一个可能近似正确（PAC）框架中的学习率。在可识别混合分布的情况下，Castelli和Cover（1995）表明，对于无限多的未标记点，错误概率对Bayes风险具有指数收敛性（即标记示例的数量）。可识别意味着给定，在中分解是唯一的。这似乎是一个相对强的假设，但它是满足的，例如，高斯混合分布。相关的是（Castelli和Cover，1996）中的分析，其中类别条件密度已知，而类别先验密度则不知道。

最后，在20世纪90年代，人们对半监督学习的兴趣增加了，这主要是由于在自然语言问题和文本分类中的应用(Yarowsky,1995; Nigam et al., 1998; Blum and Mitchell, 1998; Collins and Singer, 1999;Joachims, 1999)。

注意，据我们所知，Merz等人（1992）是第一个使用“半监督”一词对有标签和无标签数据进行分类的。事实上，它以前曾被使用过，但与本书中开发的内容不同；例如，参见（Board和Pitt，1989）。

1.2 什么时候适用半监督学习？

一个自然的问题是：半监督学习有用吗？更准确地说，与仅使用有标记数据的监督算法相比，人类能指望加入非标签数据后获得更精确的预测吗？你可能从本书的尺寸猜到了，肯定的答案是 “是”。然而，有一个重要的先决条件：这些非标记样本的分布有助于阐释与之相关的分类问题。

在一个更为数学的公式中，我们可以说，通过未标记的数据获得的关于的知识必须携带在推断中有用的信息。如何不是这样的，半监督学习相对监督学习将不会获得提升。甚至有可能使用未标记的数据会误导推断，从而降低预测精度，第4章详细研究了这种效应。

因此，人们不应该太惊讶，对于半监督学习工作，不得不做出一些假设。在这种情况下，请注意，简单的监督平滑性学习也必须依赖于假设。事实上，第22章讨论了一种假设的方法，在一个PAC风格的框架内将下面给出的假设形式化，其中一个最流行的假设可以表述如下。监督学习的平稳假设：如果两个点相近，对应的输出 也应该相近。

显然，如果没有这样的假设，将永远不可能从一个有限的训练集归纳为一组可能无限多的未看到的测试用例。

1.2.1 半监督学习的平稳架设

我们现在提出一个光滑假设的推广，这对半监督学习是有用的；我们称它为 “半监督平滑假设”。在监督学习的情况下，根据我们先前的信念，输出随距离平稳变化，我们现在也考虑到输入的密度。这个假设就是标记函数在高密度区域比在低密度区域更平滑。

半监督学习平滑假设：如果两个输入点在高密度区域是相近的，则对应的输出  也应该是相近的。

注意，通过传递性，这一假设意味着，如果两个点通过高密度路径连接（例如，如果它们属于同一个簇），那么它们的输出可能很接近。另一方面，如果它们被一个低密度区域隔开，那么它们的输出就不需要很接近。

注意，半监督平稳性假设适用于回归和分类。在下一节中，我们将展示在分类的情况下，它简化为SSL中常用的假设。目前，对于回归问题，这个假设的用处还不太清楚。作为替代方案，第23章提出了一种使用未标记数据进行模型选择的方法，该方法适用于回归和分类。

1.2.2 聚类假设

假设我们知道一个类的点倾向于形成一个簇。然后这些非标记数据应该有助于更精确地找到每个类的边界：我们可以运行一个聚类算法然后使用标记数据为每个簇分配一个类别。这实际上最早的一种半监督学习形式。基本的，现在是经典的，假设可以表述如下：聚类假设，如果点在同一个簇，这些点很大可能属于同一个类别。

基于纯粹的类别存在，这种假设是合理的:如果有一个数量密集的物体连续体，它们似乎不太可能被区分为不同的类别。

注意，聚类假设并不意味着每个类形成一个单一的、紧凑的簇：它只意味着，通常，我们不观察同一簇中两个不同类的对象。

聚类假设可以用等价的方式表述：低密度分割：决策边界应该位于低密度区域。

等价性很容易看出：高密度区域中的决策边界将一个簇划分为两个不同的类；同一个簇中的许多不同类的对象将需要决策边界来分割该群聚，即通过一个高密度区域。

尽管这两个公式在概念上是等效的，但它们可以激发不同的算法，正如我们将在1.3节中讨论的那样。低密度版本还提供了额外的直觉，为什么这个假设在许多现实问题中是合理的。例如，考虑数字识别，假设您想学习如何区分手写数字“0”和数字“1”。从决策边界精确地获取的样本点将介于0和1之间，很可能是一个看起来像非常长的零的数字。但有人写下这个“奇怪”数字的概率很小。

1.2.3 流形学习假设

构成几种半监督流形学习方法基础的一个不同但相关的假设是流形假设：

流形学习假设：（高纬的）数据在低维流形上的映射。

这如何有用呢？许多统计方法和学习算法的一个众所周知的问题是所谓的维度性诅咒。这与容量随维数呈指数增长这一事实有关，而对于诸如密度的可靠估计等统计任务，则需要以指数增长的方式来采样。这是一个直接影响基于输入空间密度估计的生成方法的问题。一个高维度的相关问题，对判别式方法来说可能更为严重，这就是成对的距离趋向于变得更相似，因而表现力也更低。

然而，如果数据恰好位于低维流形上，那么学习算法基本上可以在相应维的空间中运行，从而避免了维数的诅咒。

如上所示，我们认为，处理流形的算法可以看作是近似地实现半监督平滑假设：这种算法使用流形的度量来计算测地距离。如果我们将流形视为高密度区域的近似值，那么很明显，在这种情况下，半监督平滑假设减少到应用于流形的监督学习的标准平滑假设。

请注意，如果流形以弯曲的方式嵌入高维输入空间（即，它不仅仅是子空间），测地距离与输入空间中的距离不同。通过确保更精确的密度估计和更合适的距离，流形假设可能对分类和回归有用。

1.2.4 转导

如前所述，一些算法自然地在一个转换的环境中运行。根据Vapnik提出的原理，高维估计问题应该尝试遵循以下原则：

Vapnik 原理：当试图解决某个问题时，不应把解决更困难的问题作为中间步骤。

以监督学习为例，其中需要根据对象预测对应的标签。生成式模型将的密度作为中间步骤进行估计，而判别式方法则直接对标签进行估计。

相似地，如果标签预测只需要一个给定的测试集，可以认为转导比归纳更直接：而归纳法在整个空间上推断函数 ，然后返回在测试点上，的评估包括直接估计测试标签的有限集合，即仅在测试集上定义的函数。请注意，转导（如本书中定义的）与 SSL 不同：有些半监督算法是转导的，而另一些则是归纳的。

现在假设我们得到了一个转导算法，它产生了一个优于对相同标记数据（但丢弃未标记数据）进行训练的归纳算法的解。那么，性能差异可能是由于以下两点之一（或两者的组合）造成的：

1. 转导比归纳更接近 Vapnik 原理，或者

2. 该转导算法以类似于半监督学习算法的方式利用未标记数据。

有充分的证据表明，由于上述第二点，正在进行改进。我们目前不知道有选择地支持第一点的经验结果。尤其是，与本书（第21章）相关的基准的评估似乎并不表明转导方法的系统优势。然而，转导的性质仍然是争论的话题，第25章试图提出不同的观点。

1.3 算法族和本书的结构

尽管许多方法并不是从上述假设中直接推导出来的，但大多数算法可以被视为对应或实现其中的一个或多个。我们试图将本书中介绍的半监督学习方法组织成四个大致符合基本假设的类。虽然分类并不总是唯一的，但是我们希望这个组织通过提供一个指导方案，使读者能够更容易地了解这本书及其内容。

出于同样的原因，这本书被组织成“部分”，每类SSL算法都有一个部分，另外一个部分关注生成方法。接下来的两个部分将介绍SSL的应用程序和前景。在下面，我们简要介绍每本书的每一部分所涵盖的思想。

1.3.1 生成式模型

第一部分用生成式模型介绍了SSL的历史和发展现状。第2章从对该领域的全面回顾开始。

使用生成式模型的推理涉及条件密度的估计。在这个设置中，关于的任何附加信息都是有用的。作为一个简单的例子，假设是高斯分布的。然后利用EM算法求出各类对应的高斯参数。与用于聚类的标准EM算法的唯一区别是，与任何带标签的示例关联的“隐藏变量”实际上不是隐藏的，它是已知的，并且等于它的类标签。它聚类集群假设（参见第2.2.1节），因为给定簇只属于一个类。

这个小例子已经强调了使用生成式模型的半监督学习的不同解释：

它可以被看作是一种分类，并提供有关边缘密度的附加信息。

它可以看作是带有附加信息的聚类。在标准设置中，这些信息将是点的子集的标签，但也可以是更通用的约束形式。这是第5章的主题。

生成式方法的一个优点是，通过对问题的结构或数据进行建模，可以自然地将其结合起来。在第三章中，对EM算法在文本数据中的应用进行了说明。结果表明，当建模假设不正确时，未标记的数据会降低预测精度。第四章对这种效应进行了深入的研究。

在统计学习中，在进行推理之前，选择一类函数或先验函数。我们必须根据预先知道的问题来选择它。在半监督学习环境下，如果对数据结构对目标函数的描述有一定的了解，那么在看到未标记的数据后，可以更精确地选择该先验函数：通常可以对满足集群假设的函数设置更高的先验概率。从理论上讲，这是一种自然的方法来获得半监督学习的界限，如第22章所述。

1.3.2 低密度分割

本书的第二部分旨在描述通过将决策边界推离未标记点来直接实现低密度分离假设的算法。

实现这一目标的最常见的算法是使用一个最大边缘算法如支持向量机。最大化未标记点和标记点的边缘的方法称为转导SVM（TSVM）。然而，相应的问题是非凸的，因此难以优化。

第6章给出了一种TSVM的优化算法。从只对标记数据进行训练的支持向量机解决方案开始，通过支持向量机预测对未标记的点进行标记，并对所有点进行支持向量机再训练。当未标记点的权重缓慢增加时，将重复此过程。另一种可能是第7章中建议的半定规划SDP松弛。

然后，提出了两种不同于TSVM的方案，分别在概率论和信息论框架中进行阐述。在第8章中，二元高斯过程分类通过引入一个占据两个正则类之间空间的空类来进行扩充。与TSVM相比，这是一个优势，允许概率输出。

这一优势由第9章提出的熵最小化所共享。它鼓励类条件概率在标记和未标记的点上接近1或0。作为平滑假设的结果，在任何高密度区域，概率都趋向于接近0或1，而类边界对应于中间概率。

使用熵或信息的另一种方法是第10章中开发的与数据相关的正则化。与TSVM相比，这似乎更直接地实现了低密度分离：标准平方范数正则化器乘以一个反映接近决策边界的密度的项。

1.3.3 基于图的方法

在过去的几年中，半监督学习最活跃的研究领域是基于图的方法，这是本书第三部分的主题。这些方法的共同点是，数据由图的节点表示，图的边缘用事件节点的成对距离标记（缺失的边缘对应无限距离）。如果两个点的距离是通过最小化连接两个点的所有路径上的总路径距离来计算的，则可以将其视为两个点相对于数据点流形的测地线距离的近似值。因此，图方法可以论证为建立在流形假设的基础上。

大多数的图形方法都是利用拉普拉斯图来表示图形。设  是一个由给出实际边权的图：。这儿，边的权重 指示事件节点的相似性（丢失的边缘与零相似性相关）。现在图的加权邻接矩阵（简称权重矩阵）定义为 

               (1.2)

由 定义的对角矩阵被称为的度矩阵。现在定义拉普拉斯图的方法有很多种，其中最突出的两种是归一化拉普拉斯图和非归一化拉普拉斯图，：

                                    (1.3)

许多惩罚加权图边缘非光滑性的图方法，回顾起来可以看作是一个相当普通的算法家族的不同实例，如第11章所述。第13章从更为理论的角度出发，将光滑性的概念从连续情况转移到图上，作为离散情况。在此基础上，提出了基于数据图形表示的不同正则化器。

通常，预测由未标记节点的标签组成。因此，这种算法本质上是转导的，即只返回未标记点上的决策函数值，而不返回决策函数本身。然而，正如第12章所讨论的，为了扩展基于图的方法来产生归纳解，最近已经有了一些工作。

图上的信息传播还可以改进给定的（可能是严格监督的）分类，同时考虑到未标记的数据。第14章介绍了一种以这种方式使用有向图的概率方法。

图通常是通过计算其他表示形式中对象的相似性来构建的，例如，在欧几里得数据点上使用核函数。但有时原始数据已经有了图形的形式。例子包括网页的链接模式和蛋白质的相互作用（见第20章）。在这种情况下，边缘的方向性可能很重要。

1.3.4 表示的变化

第四部分的主题是算法，这些算法不是本质上半监督的，而是执行两步学习：

1. 对所有已标记和未标记的数据执行无监督步骤，但忽略可用的标签。例如，这可以是表示形式的更改，或者是新度量标准或新内核的构造。

2. 忽略未标记的数据，并使用新的距离、表示或内核执行纯监督学习。

这可以看作是半监督平滑假设的直接实现，因为表示方式的改变使得高密度区域中的小距离保持不变。

请注意，基于图的方法（第三部分）与本部分中提出的方法密切相关：从数据中构建图可以被视为表示的无监督变化。因此，第四部分的第一章，第15章，讨论了这些图的光谱变换，以便构建内核。谱方法也可用于非线性降维，如第16章所述。此外，在第17章中，研究了从图中得出的度量，例如从最短路径中得出的度量。

1.3.5 半监督学习的实践

当没有标记的数据远多于标记的数据时，半监督学习将是最有用的。如果获取数据很便宜，这很可能发生，但是获取标签需要花费大量的时间、精力或金钱。在机器学习的许多应用领域都是如此，例如：

在语音识别中，记录大量的语音几乎不需要花费任何费用，但是标记它需要一些人去听它并输入一份转录本。

数以十亿计的网页可直接用于自动化处理，但为了可靠地分类，人类必须阅读它们。

蛋白质序列现在是以工业速度获得的（通过基因组测序、计算基因发现和自动翻译），但要解决三维（3D）结构或确定单个蛋白质的功能可能需要多年的科学研究。

第三章从生成式模型的角度介绍了网页分类。

由于未标记的数据比标记的数据携带的信息少，因此需要大量数据才能显著提高预测精度。这意味着需要快速有效的SSL算法。第18章和第19章介绍了处理大量要点的两种方法。在第18章中，提出了加快第11章中介绍的标签传播方法。在第19章中，聚类内核被证明是一种有效的SSL方法。

第19章还介绍了半监督学习中两种重要的生物信息学应用方法：蛋白质序列分类。虽然这里的预测是基于蛋白质序列本身，但第20章将继续讨论一个更复杂的环境：这里的信息假定以描述蛋白质相互作用的图形的形式出现。存在一些这样的图，必须以适当的方式组合。

本书的最后一部分是一个非常实用的章节：介绍和评估与本书相关的基准（第21章）。它旨在向实践者提示如何根据问题的性质选择合适的方法。

1.3.6 总结

这本书的最后一部分，第六部分，专门介绍了正在进行的SSL研究中最有趣的一些方向。

到目前为止，这本书基本上还没有分类。第23章介绍了另一种适用于分类和回归的SSL方法，并从中派生算法。有趣的是，它似乎不需要第1章中提出的假设。

此外，本书主要介绍了SSL的算法。虽然上面讨论的假设提供了有关何时和为何使用SSL的一些直觉，第4章研究了何时和为何会失败，但对SSL的总体理论理解显然更令人满意。第22章提供了一个PAC风格的框架，为SSL问题提供了错误界限。

在第24章中，我们从Vapnik-Chervonenkis（VC）界和其他理论和哲学概念的角度对归纳半监督学习和转导进行了比较。

本书结尾是三位机器学习研究者关于半监督学习和转导的关系（以及两者之间的差异）的假设性讨论（第25章）。