《机器学习》笔记-半监督学习（13）

刘才权

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

• 未标记样本
• 生成式方法
• 半监督SVM
• 图半监督学习
• 基于分歧的方法
• 半监督聚类

（一）未标记样本

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

（二）生成式方法

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

（三）半监督SVM

半监督支持向量机（Semi-Supervised Support Vector Machine，简称 S3VM）是支持向量机在半监督学习上的推广。在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。如下图所示，

这里的基本假设是“低密度分隔”（low-density separation），显然，这是聚类假设在考虑了线性超平面划分后的推广。

（四）图半监督学习

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高（或相关性很强），则对应结点之间存在一条边，边的“强度”（strength）正比于样本之间的相似度（或相关性）。我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色。于是，半监督学就对应于“颜色”在图上扩散或传播的过程。由于一个图对应了一个矩阵，这使得我们能基于矩阵运算来进行半监督学习算法的推到和分析。
图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也相当明显。首先是在存储开销上，若样本数为O(m)，则算法中所涉及的矩阵规模未O(m2)，这使得此类算法很难直接处理大规模数据；另一方面，由于构图过程仅能考虑训练样本集，难以判断新样本在图中的位置，因此，在接收到新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是需引入额外的预测机制。

（五）基于分歧的方法

与生成式方法、半监督SVM、图半监督学习等基于单学习器利用未标记数据不同，基于分歧的方法（disagreement-base methods）使用多学习器，而学习器之间的“分歧”（disagreement）对未标记数据的利用至关重要。
基于分歧的方法只需采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模的影响，学习方法简单有效、理论基础相对坚实、适用范围较为广泛。为了使用此类方法，需能生成具有显著分歧、性能尚可的多个学习器，但当有标记样本很少，尤其是数据不具有多视图时，要做到这一点并不容易，需有技巧的设计。

（六）半监督聚类

聚类是一种典型的无监督学习任务，然而在现实聚类任务中我们往往能获得一些额外的监督信息，于是可通过半监督聚类（semi-supervised clustering）来利用监督信息以获得更好的聚类效果。
聚类任务中获得的监督信息大致有两种类型。第一种类型是“必连”（must-link）与“勿连”（cannot-link）约束，前者是指样本必属于同一个簇，后者是指样本必不属于同一个簇；第二种类型的监督信息则是少量的有标记样本。