半监督学习
原理
13.1 未标记样本
- 形式化地看，我们有训练样本集 Dl，这 l 个样本的类别标记已知，称为“有标记”(labeled)样本；此外，还有 Du，l << u，这 u 个样本的类别标记未知，称为“未标记”(unlabeled)样本。若直接使用传统监督学习技术，则仅有 Dl 能用于构建模型， Du 所包含的信息被浪费了；另一方面，若 Dl 较小，则由于训练样本不足，学得模型的泛化能力往往不佳。那么，能否在构建模型的过程中将 Du 利用起来呢？
- 我们可以用 Dl 先训练一个模型，拿这个模型去地里挑一个瓜，询问瓜农好不好，然后把这个新获得的有标记样本加入 Dl 中重新训练一个模型，再去挑瓜，……这样，若每次都跳出对改善模型性能帮助大的瓜，则只需询问瓜农比较少的瓜就能构建出比较强的模型，从而大幅度降低标记成本。这样的学习方式成为“主动学习”(active learning)，其目标是使用尽量少的“查询”(query)来获得尽量好的性能。
- 显然，主动学习引入了额外的专家知识，通过与外界的交互来将部分未标记样本转变为有标记样本。若不与专家交互，没有获得额外信息，还能利用未标记样本来提高泛化性能吗？
- 答案是可以，事实上，未标记样本虽然未直接包含标记信息，但若它们与有标记样本是从同样的数据源独立同分布采样而来，则它们所包含的关于数据分布的信息对建立模型将大有裨益。
- 让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习(semi-supervised learning)。半监督学习的现实需求非常强烈，因为在现实应用中往往能容易地收集到大量未标记样本，而获取“标记”却需耗费人力、物力。
- 要利用未标记样本，必然要做一些未标记样本所揭示的数据分布信息与类别标记相联系的假设。最常见的是“聚类假设”(cluster assumption)，即假设数据存在簇结构，同一个簇的样本属于同一个类别。半监督学习中另一种常见的假设是“流形假设”(manifold assumption)，即假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。“邻近”程度常用“相似”程度来刻画，因此，流形假设可看作聚类假设的推广，但流形假设对输出值没有限制，因此比聚类假设的适用范围更广，可用于更多类型的学习任务。事实上，无论聚类假设还是流形假设，其本质都是“相似的样本拥有相似的输出”这个基本假设。
- 半监督学习可进一步划分为纯(pure)半监督学习和直推学习(transductive learning)，前者假定训练数据中的未标记样本并非待预测的数据，而后者假定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能。换言之，纯半监督学习是基于“开放世界”假设，希望学得模型能使用于训练过程中未观察到的数据；而直推学习是基于“封闭世界”假设，仅试图对学习过程中观察到的未标记数据进行预测。
13.2 生成式方法
- 生成式方法(generative methods)是直接基于生成式模型的方法。此类方法假设所有数据(无论是否标记)都是由同一个潜在的模型“生成”的。这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来，而未标记数据的标记则可看作模型的缺失参数，通常可基于 EM 算法进行极大似然估计求解。此类方法的区别主要在于生成式模型的假设，不同的模型假设将产生不同的方法。
13.3 半监督SVM
- 半监督支持向量机(Semi-Supervised Support Vector Machine, S3VM) 是支持向量机在半监督学习上的推广。在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM试图找到能将两类有效标记样本分开，且穿过数据低密度区域的划分超平面。这里的基本假设是“低密度分隔”(low-density separation)，显然，这是聚类假设在考虑了线性超平面划分后的推广。
- 半监督支持向量机中最著名的是 TSVM(Transductive Support Vector Machine)，与标准 SVM一样，TSVM也是针对二分类问题的学习方法，TSVM试图考虑对未标记样本进行各种可能的标记指派(label assignment)，即尝试给每个未标记样本分别作为正例和反例，然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面，一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。
13.4 图半监督学习
- 给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高(或相关性很强)，则对应的结点之间存在一条边，边的“强度”(strength)正比于样本之间的相似度(或相关性)。我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色。于是，半监督学习就对应于“颜色”在图上扩散或传播的过程。由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。
- 图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也相当明显。首先是在存储开销上，若样本数为O(m)，则算法中所设计的矩阵规模为O(m^2)，这使得此类算法很难直接处理大规模数据；另一方面，由于构图过程仅能考虑训练样本集，难以判知心样本在图中的位置，因此，在接收新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是需引入额外的预测机制，例如将 Dl 和经标记传播后得到标记的 Du 合并作为训练集，另外训练一个学习器例如支持向量机来对新样本进行预测。
13.5 基于分歧的方法
- 与生成式方法、半监督SVM、图半监督学习等基于单学习器利用未标记数据不同，基于分歧的方法(disagreement-based methods)使用多学习器，而学习器之间的“分歧”(disagreement)对未标记数据的利用至关重要。
- “协同训练”(co-training)是此类方法的重要代表，它最初是针对“多视图”(multi-view)数据设计的，因此也被看作“多视图学习”(multi-view learning)的代表。
- 在不少现实应用中，一个数据对象往往同时拥有多个“属性集”(attribute set)，每个属性集就构成了一个“视图”(view)。例如对一部电影来说，它拥有多个属性集：图像画面信息所对应的属性集、声音信息所对应的属性集、字幕信息所对应的属性集、甚至网上的宣传讨论所对应的属性集等。
- 假设不同视图具有“相容性”(compatibility)，即其所包含的关于输出空间 Y 的信息是一致的。
13.6 半监督聚类
- 聚类是一种典型的无监督学习任务，然而在现实聚类任务中我们往往能获得一些额外的监督信息，于是可通过半监督聚类(semi-supervised clustering)来利用监督信息以获得更好的聚类效果。
- 聚类任务中获得的监督信息大致有两种类型。第一种是“必连”(must-link)与“勿连”(cannot-link)约束，前者是指样本必属于同一个簇，后者是指样本必不属于同一个簇；第二种类型的监督信息则是少量的标记样本。
