第1章 半监督学习导论
1.1 有监督、无监督和半监督学习
为了理解半监督学习(semi-supervised learning，SSL)的本质，了解有监督和无监督学习很有必要。
1.1.1 有监督和无监督学习
传统上，机器学习中有两种本质上不同的任务。
第一种是无监督学习。设是一个包含个实例(或点)的集合，对于所有的，。典型地，假设点是从的一个常用分布中独立同分布地抽取出来。常用的便捷方法是：定义一个维矩阵，该矩阵将数据点作为行。无监督学习的目标是寻找数据中潜在有用的结构。人们对其本质有过争论，即从本质上估计，无监督学习可能生成的密度，然而无监督学习也有其较弱形式，如分位数估计、聚类、异常点检测和降维。
第二种是有监督学习。目标是给定一个由对构成的训练集合，学习一个从到的映射。这里，被称为实例的标记或目标。如果标记是数字，那么表示标记的列向量。同样，标准要求是对从某个分布中独立同分布地采样得到。由于一个映射可以通过其在测试实例上的预测性能来评价，因此任务可以被很好地定义。当或时(或更一般地，当标记连续时)，任务就被称作回归。本书的大部分内容将集中在分类上(第23章中有一些关于回归的研究)，即在一个有限集中取值(离散的标记)。有监督学习通常采用两种算法：生成式算法和判别式算法。生成式算法试图通过某些无监督学习过程来为类-条件密度建模1，因而预测的密度可以应用贝叶斯定理来推导：
(1.1)
事实上，是数据的联合密度，能够生成。
判别式算法并不试图估计如何生成，转而集中于估计。某些判别式方法甚至将自己局限于为是否大于或小于0.5这个问题而建模，支持向量机(support vector machine，SVM)就是其中一个例子。
现已证明，判别式模型和有监督学习的目标更一致，因此在实践中通常更有效率。2.2.1节和2.2.2节将详细讨论这两种框架。
1.1.2 半监督学习
半监督学习是有监督学习和无监督学习的折中。除了无标记数据，半监督学习又为算法提供了一些指导信息——但并非所有实例所必需。通常这种信息是和某些实例的目标值相关联的。在这种情况下，数据集合被分为两部分：①点，为此提供了标记；②点，其标记未知。这是本书研究的标准半监督学习，后面大部分章节都会提到这种设置。
本书也给出了部分有监督学习的其他形式。例如，可能给出“这些点有(或没有)相同的目标”这样的约束(Abu-Mostafa，1995)，第5章便考虑了这种更一般的设置。不同的设置对应半监督学习的不同视角。在第5章中，半监督学习被视为约束引导的无监督学习。与之对应，大部分其他方法将半监督学习视为带有额外实例分布信息的有监督学习。这些方法的解释似乎与大多数应用更加一致，它们的目标与有监督学习相同：为给定的预测一个目标值。然而，如果类别数量和性质预先未知但必须通过数据推断得出，那么这种策略不容易实施。相反，作为带约束的无监督学习的半监督学习在这样的情况下可能可用。
Vapnik介绍过一个与半监督学习相关的难题，称为直推式学习。在直推式学习中，给定一个(标记好的)训练集合和一个(未标记的)测试集合，其直推的思想就是只对测试集合实施预测。与归纳学习相反，直推式学习的目标是输出一个定义在整个空间上的预测函数。本书描述的许多方法都是直推式的。特别地，这对于基于数据图表示的推理很自然。关于这一点将在1.2.4节中再次讨论。
1.1.3 半监督学习的简要历史
在分类中使用未标注数据的*早想法可能是自学习，也称为自训练、自标注或者决策引导的学习。这是一种重复使用有监督学习方法的封装算法。它开始只在标注数据上训练。按照当前决策函数，在每一步标注一部分未标注数据；然后将自己的预测作为附加的标注数据重新训练有监督学习方法。这一思想之前在该领域就已出现(Scudder，1965；Fralick，1967；Agrawala，1970)。
自学习的一个优势是封装的效果依赖于其所用的有监督方法。如果自训练使用经验风险*小化和0-1损失，那么未标注数据将对结果没有任何效果。相反，如果使用边界*大化方法，那么结果就使决策边界远离未标注数据(见第6章)。在其他情况下，尚不清楚自学习真正做了什么，以及它对应哪一个假定。
与半监督学习相关的是直推法(或直推)，其*初由Vapnik提出(Vapnik et al.，1974; Vapnik et al.，1977)。与归纳推理相反，直推法并不推导一般性决策规则，只是预测未标注点(或者测试点)。Hartley和Rao(1968)给出了直推法的一个早期例子(虽然没有明确地将其认为是一个概念)。他们提出一种在测试点标记上的组合优化，以*大化其模型的似然度。
半监督学习的真正崛起是在20世纪70年代，当时人们考虑了在未标注数据上的费舍尔线性判别规则的估计问题(Hosmer，1973; McLachlan，1977; O’Neill，1978; McLachlan et al.，1982)。更简明地，这种情况下的设置是每个类条件密度为协方差矩阵相等的高斯分布。由此，在一个诸如期望*大化(expectation-maximization，EM)算法(Dempster et al.，1977)之类的迭代算法帮助下，使用标注和非标注数据进行模型似然性的*大化。除了高斯混合分布，人们也研究了以标注和非标注数据估计多项式分布的混合使用(Cooper et al.，1970)。
随后，这种每类一个模块的设置被扩展到每类多个模块(Shahshahani et al.，1994)并被Miller等(1997)进一步泛化。
Ratsaby和Venkatesh(1995)推导出两个混合高斯分布的半监督学习在可能近似正确(probably approximately correct，PAC)框架(Valiant，1984)下的学习速率。在可分辨混合的情况下，Castelli等(1995)证明了对于无限数量的未标注点，错误的概率指数收敛到贝叶斯风险(相对于标记实例的数量)。可分辨意味着对于给定的，其在中的分解是**的。这似乎是一个相对较强的假设，但它是可满足的，如针对高斯混合分布。具体分析请参见Castelli等的相关文献(Castelli et al.，1996)，其中类条件密度已知，但是类先验知识未知。
20世纪90年代，人们研究半监督学习的兴趣有所增长，这大部分归因于自然语言问题和文本分类方面的应用(Yarowsky，1995；Nigam et al.，1998；Blum et al.，1998；Collins et al.，1999；Joachims，1999)。
注意，Merz等(1992)是第一位在使用标注和未标注数据进行分类的任务中使用“半监督”这一术语的。事实上，半监督学习这一术语以前也被使用过，但是是用在不同于本书的情况下，相关例子请参见Board等(1989)的工作。
1.2 何时半监督学习可以工作
半监督学习有何意义？明确地说，与只使用标注数据的有监督算法相比，可以通过把未标注点考虑在内而有更精确的预测吗？理论上回答是肯定的。然而，有一个重要前提，即未标注数据的实例分布与分类问题相关。
在数学公式中通过未标注数据获取的关于的知识必须承载对推理有用的信息，否则，半监督学习将不会超越有监督学习。这可能导致误导推理，而使得未标注数据的使用降低了预测精度。第4章将详细研究这一问题。
因此，为了使半监督学习能正常工作，需要给出一定的假设条件。第22章讨论了一种在PAC框架内，对假设进行形式化描述的方法。*经典的一种假设方式是
有监督学习的平滑性假设1：若两个点、距离近，则对应的输出、也应该相近。
显然，没有这样的假设，就绝不可能从一个有限训练集合泛化到一个有多个未知样例的无限测试集合。
1.2.1 半监督平滑性假设
这里提出一个对半监督学习有用的平滑性假设的泛化，称为半监督平滑性假设。在有监督的情况下，按照先验知识，输出随着距离而平滑变化，现在把输入的密度考虑进来，假设标注函数在高密度区域比在低密度区域更平滑。
半监督平滑性假设是指若在高密度区域的两个点、距离近，则对应的输出、也应该相近。
由传递性可知，这个假设隐含着：若两个点被高密度区域中一条路径连接(如它们属于同一个聚类)，则其对应的输出也倾向于相近。另外，若它们被一个低密度区域分开，则其输出不能相近。
注意，半监督平滑性假设同时应用于回归和分类。1.2.2节将展示在分类情况下，如何将该假设归约成半监督学习中常用的假设。作为一种可选的方法，第23章提出一种可同时应用于回归和分类的使用未标注数据进行模型选择的方式。
1.2.2 聚类假设
假设每个类别的点倾向于各自形成一个聚类，那么未标注数据可以协助更精确地发现每个聚类的边界：运行聚类算法，使用已标记点为每个聚类设置一个类别。事实上，这是SSL*早期的形式之一(见第2章)。目前使用的、基础的经典假设是聚类假设(cluster assumption，CA)。
聚类假设是指若点在相同的聚类中，则它们更可能属于同一类别。
在类别绝对存在的基础上，这一假设可认为是合理的：若存在一个对象密集聚集的连续区，则它们被分成不同类别是不太可能的。
聚类假设并不隐含每个类别形成单一的紧密聚类，通常只意味着不考察在相同聚类中2个不同类别的对象。
聚类假设可视为半监督平滑性假设的一个特例，即聚类定义为只在高密度区域穿越的短弧线连接的点的集合。
聚类假设可以被形式化为一个等价形式——低密度分割。即决策边界应该处于一个低密度区域。一个在高密度区域的决策边界将把一个聚类切割成两个不同的类别；在相同聚类中不同类别的很多对象将要求决策边界切割聚类，即穿过一个高密度区域。
这两种形式在概念上是等价的，但可以产生不同的算法，1.3节将进一步讨论。低密度分割给人一个直觉，在许多现实问题中假设是合乎情理的。例如考虑数字识别，假设要学习如何区分手写数字“0”对“1”。从决策边界准确地选取一个样本点，那么该样本点将在“0”和“1”之间，*可能是一个看起来像垂直拉长的零，但是某个人写出这样怪诞数字的概率是非常小的。
1.2.3 流形假设
流形假设作为若干半监督学习方法的基础，与前面讨论的假设既有区别又有联系。流形假设是指(高维)数据(大致)依赖于低密度的流形。
许多统计方法和学习算法都存在维度灾难问题(见?11.6.2?节)。它与下述事实相关：实例所在空间的大小以维度数呈指数级增长，对于诸如密度的可靠估计一类的统计任务，实例数的指数级增长是必需的。这是一个直接影响生成式方法的问题，这些方法都基于输入空间的密度估计。对判别式方法影响更为严重的一个高维度问题是不同实例的两两距离更为相近，从而使方法的表达力减弱。
如果数据恰好依赖于低维流形，那么学习算法就能在对应维度的空间内进行基本操作，这样就避免了维度灾难。
根据上述内容，以流形方式工作的算法可被看做半监督平滑性假设的一个近似实现：这样的算法使用了用于计算*短路径距离的流形度量。如果将流形视为高密度区域的一个近似，那么在这种情况下，应用在流形上的半监督平滑性假设归约为有监督学习的标准平滑性假设。
如果流形以曲面方式(不仅仅是一个子空间)嵌入高维输入空间中，那么*短路径距离就不同于输入空间的距离。通过保证更精确的密度估计和更恰当的距离，使得流形假设对分类和回归都有用。
1.2.4 直推法
如前所述，某些算法很自然地以直推设置进行操作。按照Vapnik提出的理念，高维估计问题试图遵从
展开
