第十三章 半监督学习

13.1 未标记样本

事实上，未标记样本虽未直接包含标记信息，但若它们与有标记样本是从同样的数据源独立同分布采样而来，则它们所包含的关于数据分布的信息对建立模型将大有裨益。下图给出一个直观的例示。若仅基于图中的一个正例和一个反例，则由于待判别样本恰位于两者正中间，大体上只能随机猜测；若能观察到图中的未标记样本，则将很有把握地判别为正例。

让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习。
要利用未标记样本，必然要做一些将未标记样本所揭示地数据分布信息与类别标记相联系的假设。最常用的是“聚类假设”，即假设数据存在簇结构，同一个簇的样本属于同一个类别。上图就是基于聚类假设来利用未标记样本，由于待预测样本与正例样本通过未标记样本的撮合聚在一起，与相对分离的反例样本相比，待判别样本更可能属于正类。
半监督学习中另一种常见的假设是流行假设，即假设数据分布在一个流行结构上，邻近的样本拥有相似的输出值。邻近程度常用相似程度来刻画，因此，流形假设可看作聚类假设的推广，但流行假设对输出值没有限制，因此比聚类假设的适用范围更广，可用于更多类型的学习任务。
无论聚类假设还是流行假设，其本质都是相似的样本拥有相似的输出这个假设。
半监督学习可进一步划分为纯半监督学习和直推学习,前者假定训练数据中的未标记样本并非待预测的数据，而后者则假定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能。换言之，纯半监督学习是基于“开放世界”假设，希望学得模型能适用于训练过程中未观察到的数据；而直推学习是基于 “封闭世界”假设，仅试图对学习过程中观察到的未标记数据进行预测。下图直观地显示出主动学习、纯半监督学习、直推学习的区别。需注意的
是，纯半监督学习和直推学习常合称为半监督学习。

13.2 生成式方法

生成式方法是直接基于生成式模型的方法。此类方法假设所有数据（无论是否有标记）都是由同一个潜在的模型生成的。这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来，而未标记数据的标记则可看作模型的缺失参数，通常可基于EM算法进行极大似然估计求解。此类方法的区别主要在于生成式模型的假设，不同的模型假设将产生不同的方法。

13.3 半监督SVM

半监督支持向量机（S3VM）是支持向量机在半监督学习上的推广。在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面，如下图所示。这里的基本假设时“低密度分隔”，显然，这是聚类假设在考虑了线性超平面划分后的推广。

半监督支持向量机中最著名的是TSVM，欲标准SVM一样，TSVM也是针对二分类问题的学习方法。TSVM试图考虑对未标记样本进行各种可能的标记指派，即尝试将每个未标记样本分别作为正例或反例，然后在所有这些结果中，寻求一个在所有样本上间隔最大化的划分超平面。一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。

13.4 图半监督学习

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高，则对应的结点之间存在一条边，边的强度正比于样本之间的相似度。我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色。于是半监督学习就对应于颜色在图上扩散或传播的过程。

图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也相当明显。首先是在存储开销上，若样本数为O(m)，则算法中所涉及的矩阵规模为O(m^2),这使得此类算法很难直接处理大规模数据；另一方面，由于构图过程仅能考虑训练样本集，难以盼知新样本在图中的位置，因此，在接收到新样本时，或是将其加入原数据对图进行重构并重新进行标记传播，或是需引入额外的预测机制。

13.5 基于分歧的方法

与生成式方法、半监督SVM、 图半监督学习等基于单学习器利用未标记数据不同，基于分歧的方法使用多学习器，而学习器之间的分歧对未标记数据的利用至关重要。
协同训练是此类方法的重要代表，它最初是针对多视图数据设计的，因此也被看做多视图学习的代表。
在不少现实应用中，一个数据对象往往同时拥有多个属性集，每个属性集就构成了一个视图。假设不同视图具有相容性，即其所包含的关于输出空间y的信息是一致的。显然，在相容性基础上，不同视图信息的互补性会给学习器的构建带来很多便利。
协同训练正是很好地利用了多视图地相容互补性。假设数据拥有两个充分且条件独立视图，充分是指每个视图都包含足以产生最优学习器地信息。条件独立则是指在给定类别标记条件下两个视图独立。 在此情形下，可用一个简单的办法来利用未标记数据：首先在每个视图上基于有标记样本分别训练出一个分类器，然后让每个分类器分别去挑选自己“最有把握的”未标记样本赋予伪标记，并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新……这个"互相学习、共同进步”的过程不断迭代进行，直到两个分类器都不再发生变化，或达到预先设定的迭代轮数为止。算法描述如图13.6所示。若在每轮学习中都考察分类器在所有未标记样本上的分类置信度，会有很大的计算开销，因此在算法中使用了未标记样本缓冲池[Blum and Mitchell, 1998].分类置信度的估计则因基学习算法£ 而异，例如若使用朴素贝叶斯分类器，则可将后验概率转化为分类置信度；若使用支持向量机,则可将间隔大小转化为分类置信度.

13.6 半监督聚类

聚类是一种典型地无监督学习任务，然而在现实聚类任务中我们往往能获得额外的监督信息，于是可通过半监督聚类来利用监督信息以获得更好的聚类效果。
聚类任务中获得的监督信息大致有两种类型。第一种类型是必连与勿连约束，前者是指样本必属于同一个簇，后者是指样本必不属于同一个簇；第二种类型的监督信息则是少量的有标记样本。
约束k均值算法是利用第一类监督信息的代表。