一起来读西瓜书：第十三章 半监督学习

1. 章节主要内容

在前边的学习过程中，我们知道了监督学习和无监督学习的区别。前者是在标注好了的训练集上训练学习器，并用训练好的学习器去对新的样本进行预测，朴素贝叶斯、决策树、神经网络等都属于这类机器学习算法。后者是在未标注的数据集上根据数据本身的分布情况来对数据进行分类，各种聚类算法就是这类的机器学习算法。

从上边的定义来看，一个机器学习算法“监督”与否取决于用来计算的数据有无被“标注”好！那以此来推理，我们这章学习的“半监督学习”算法就是即使用了标注好了的数据，又使用了未标注的数据来训练学习器！

可是，既然已经有了标注好的数据集了，我们为什么还要费心去使用未标注的数据来辅助学习呢？原来在实际场景下，标注好了的数据集往往只是未标注数据集的千万分之一。想想互联网上每天产生多少PB的数据，其中拥有标注的数据真是少之又少。没有足够的标注训练集，监督学习算法训练出来的学习器往往泛化能力不佳，而且那么多的未标注数据不去利用，其中包含的信息就被浪费了！

一个最简单的办法是找来一堆人一个个的为未标注数据进行标注。显然，这种方法比较“笨”，需耗费大量的时间和精力

一个稍微省力的办法是，先用标注好的数据来进行训练，然后利用训练好的学习器找出未标注数据中能对性能改善最大的数据来询问“专家”。这样只需要专家标注比较少的数据就能得到较强的学习器了。

上边的方法被称为“主动学习”（active learning），这种方法引入了额外的专家知识，还需要外部的介入来辅助学习。如果我们不想再增加额外的人力了，想让机器自己的对未标注数据进行分析来提高泛化性能，可行吗？

答案是可行，半监督学习就是这样的算法！

事实上，未标记样本虽未直接包含标记信息，但若他们与有标记样本是从同样的数据源独立同分布采样而来，则它们所包含的关于数据分布的信息对建立模型将大有裨益。

下图给出了一个直观的示例。若仅基于图中的一个正例和反例，则由于待判别样本恰位于两者正中间，大体上只能随机猜测；若能观察到图中的为标记样本，则将很有把握的判别为正例。

让学习器不依赖外界交互、自动地利用为标记样本来提升学习性能，就是半监督学习（semi-supervised learning）。

半监督学习还可细分为纯（pure）半监督学习和直推学习，前者假定训练数据中的为标记数据并非待预测数据，而后者则假定学习过程中所考虑的为标记样本恰是待预测数据。下图直观的显示出主动学习、纯监督学习和直推学习的区别。

半监督学习要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记想联系的假设，其本质是“相似的样本拥有相似的输出”

针对未标记样本的假设的不同会形成不同的半监督学习算法，下边我们将一一介绍半监督学习领域比较有名的算法模型

1）生成式方法（generative methods）

生成式方法是直接基于生成式模型的方法，此类方法假设所有数据（无论是否有标记）都是由同一个潜在的模型生产的。这个假设使得我们能通过潜在模型的参数将未标注数据与学习目的关联起来，而未标注数据的标记则可看作模型的确实参数。

通常可基于EM算法进行极大似然估计求解。EM（Expectation Maximization）算法也叫期望最大化算法，在西瓜书第七章有过介绍。该算法的核心思想是通过 E 步来对未知变量进行估算，然后通过估算出来的变量在 M 步使用极大似然估计法（在第七章也有介绍）对模型参数进行估算。在反复迭代 E, M 步骤的过程中使预估的参数收敛到局部最优解。

在半监督学习生成式方法中，EM算法的使用逻辑是这样的：

［1］假设标注数据与未标注数据来源于同一潜在的分布模型，模型参数为 t

［2］给定参数的初始值 t0，我们可以根据分布模型计算出未标注数据的标注值 y0

［3］根据 y0 和标注数据使用极大似然估计估算此时参数 t 能使得数据概率最大的最优解 t1

［4］使用 t1 计算估算此时未标注数据的标注值 y1

［5］步骤［3］和步骤［4］不断迭代，直到收敛

优点：简单，易于实现，在有标记数据极少的情形下往往比其他方法性能更好

缺点：此类方法的关键在于，模型假设必须准确，即假设的生成式模型必须与真实数据分布吻合，否则使用未标记数据反而会降低泛化性能。遗憾的是，在现实任务中往往很难事先做出准确的模型假设，除非拥有充分可靠的领域知识

2）半监督SVM（Semi-supervised Support Vector Machine，简称S3VM）

半监督支持向量机是支持向量机在半监督学习上的推广。相对于支持向量机要找出最大间隔划分超平面，S3VM考虑了未标注样本的信息，试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。如下图所示，这里的基本假设是“低密度分隔”（low-density separation）

半监督支持向量机中最著名的是TSVM（Transductive Support Vector Machine）。TSVM试图考虑对未标记样本进行各种可能的标记指派，然后从中找出在所有标记和未标记样本上间隔最大化的划分超平面。

TSVM的基本逻辑如下：

［1］先用标记好的样本训练一个SVM分类器

［2］用SVM对未标记数据的分类结果进行预测

［3］在预测的未标记数据分类中，找出指派的标记相反的且很可能错误的未标记样本对，将它们的标记对换，然后用现有的标记和未标记样本重新训练SVM

［4］重复［2］、［3］直到到达停止条件

［5］至此在未标记数据的基础上获得了一个SVM分类器，即对已有的未标注样本进行了标记，还能用来对未见的样本进行预测

解释：算法中提到的很可能错误的判断标准是具体样本的松弛向量；在使用样本时，标注样本和未标注样本的权重是不同的，一开始我们将未标注样本的权重设定为很小，每次迭代一次后将其权重调高，当未标注样本的权重高于标注样本权重时，到达停止条件

特点：搜寻标记指派可能出错的每一对未标记样本进行调整，是一个涉及巨大计算开销的大规模优化问题。因此，半监督SVM研究的一个重点是如何设计出高效的优化求解策略

3）图半监督学习

将数据集映射成图，数据集中的每个样本对应于图中的一个结点，若两个样本之间的相似度或相关性很强，则对应的结点之间存在一条边，边的强度正比于样本之间的相似度。

我们将有标记的数据看作是被染色的节点，未标注的数据是未染色的节点。图半监督学习就对应于“颜色”在图上扩散和传播的过程。由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。

基本的学习逻辑如下：

［1］基于数据集构建一个图 G = (V, E)，V代表结点集合，E代表边集合

［2］根据数据集中结点的相似度计算出图的边集 E 的亲和矩阵 W；其中 wij 代表第 i 个结点和第 j 个结点之间的相似度，一般可基于高斯函数定义

［3］假定从图 G 上可学得一个实值预测函数 f：V -> R，于是可定义关于 f 的“能量函数”，能量函数可理解为任意两个结点的预测结果的差值乘以它们之间的权重 wij 的和。很明显，能量函数最小化时即得到最优结果

［4］对能量函数求导，可得到未标注数据的预测结果

优点：概念清晰，且易于通过对矩阵运算的分析来探索算法性质

缺点：存储开销大，很难直接处理大规模数据；接收新样本时可能需要从新计算

4）基于分歧的方法（disagreement-based methods）

与前边介绍的只基于单学习器的方法不同，基于分歧的方法使用多个学习器来训练数据，并利用学习器之间的“分歧”对未标记样本进行利用

“协同训练”（co-training）是此类方法的重要代表，它最初是针对“多视图”（multi-view）数据设计的，因此也被看作“多视图学习”的代表。

多视图：在不少现实应用中，一个数据对象往往同时拥有多个“属性集”（attribute set），每个属性集就构成了一个“视图”。比如一部电影，它的画面信息所对应的属性集可看作是一个视图、声音信息所对应的属性集也可看作是一个视图、甚至字幕信息或网络评论所对应的属性集也可以是一个视图。这种拥有多个视图的数据对象我们称之为多视图数据

多视图的特性：假设不同视图具有“相容性”（compatibility），即不同视图所包含的关于输出空间的信息是一致的：用电影的画面视图和声音视图来进行预测的输出都应该是判断电影类型，而不是一个是判断电影类型，一个是判断电影好评度。在此假设下，不同视图信息的“互补性”会给学习器的构建带来很多的便利

协同训练：协同训练正是很好地利用了多视图的“相融互补性”。假设数据拥有两个充分（充分指每个视图都包含足浴产生最优学习器的信息）且条件独立视图，则协同训练学习的基本逻辑如下：

［1］在每个视图上基于有标记样本分别训练出一个分类器

［2］让每个分类器分别挑选自己“最有把握的”未标记样本赋予伪标记

［3］将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新

［4］重复［2］、［3］直到两个学习器不再变化或达到预设的迭代次数时停止

优点：过程简单，并且若两个视图充分且条件独立，可利用未标记样本将弱分类器的泛化性能提升到任意高

缺点：视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度不会那么大

5）半监督聚类（semi-supervised clustering）

半监督聚类通过利用现实聚类任务中的额外监督信息来获得更好的聚类效果。（有趣的是：前边的算法是在监督学习的基础上引入未标注数据来优化性能，半监督聚类则是在非监督学习的基础上引入监督信息来优化性能，这同样也是另一个角度的“半”监督学习）

聚类任务中获得的监督信息大致有两种类型。第一种是“必连”（must-link）与“勿连”（cannot-link）约束，前者是指样本必属于同一簇，后者是指样本必不属于同一簇；第二种类型的监督信息则是少量的有标注样本。根据不同的监督信息，我们分别介绍一个经典的半监督聚类算法。

约束 k 均值（Constrained k-means）算法：约束 k 均值算法是利用第一类监督信息的代表，其在 k 均值算法的基础上考虑了“必连”和“勿连”约束。

具体逻辑如下：

-> 首先，初始化 k 个簇，随机选择 k 个样本作为 k 个簇的初始均值向量

-> 然后，不断迭代以下几步步骤

>> 对每个样本 x ，计算其与每个簇均值向量的距离 d，

>> 找出距离样本 x 最近的簇 i ，判断将 x 放进 i 是否违反“约束”

>> 如果不违反，则将簇 i 作为 x 的簇标记，并将 x 放入该簇集合 Ci 中

>> 如果违反，则找次近的簇，以此类推直到找到满足约束的最近簇 i'，将x 放入该簇集合 Ci' 中

>> 对所有的簇集合，根据本次迭代得到的簇集合计算新的均值向量

>> 当均值向量均未更新时，退出迭代步骤

-> 最终，我们获得了聚类计算的结果簇划分

约束种子 k 均值（Constrained Seed k-means）算法：约束种子 k 均值算法使用少量标记数据来辅助聚类计算。与 k 均值算法一样，不同点在于用标记样本作为“种子”来初始化 k 均值算法的 k 个聚类中心，并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系

2. 基础知识

1）松弛向量

一般地，对于不同形式的线性规划模型，可以采用一些方法将其化为标准型。其中，当约束条件为“≤”（“≥”）类型的线性规划问题，可在不等式左边加上（或者减去）一个非负的新变量，即可化为等式。这个新增的非负变量称为松弛变量（或剩余变量），也可统称为松弛变量

给线性规划加入松弛变量也就是为硬性的阈值加入一定的容错性

可以用生活中的问题来帮助理解松弛变量。有多条长短不一的绳子，现在将所有绳子的一端固定在墙上，然后将所有绳子的另一端对齐后往外拉。当拉不动时，说明最短的一根绳子已经拉紧了，不能继续拉了。但是，这时其他绳子可能还是松的。如果放开已经拉紧的绳子，松弛的绳子还可以继续拉动，每根松弛的绳子可以继续拉动的距离就是各个指标的松弛变量值。

2）拉普拉斯矩阵（Laplacian matrix）

拉普拉斯矩阵(Laplacian matrix) 也叫做导纳矩阵、基尔霍夫矩阵或离散拉普拉斯算子，主要应用在图论中，作为一个图的矩阵表示。

3）高斯函数

在数学中，高斯函数，或者直接称为高斯，其形式为：

其中a,b,c∈R

以大数学家约翰·卡尔·弗里德里希·高斯的名字命名。高斯函数的图形在形状上像一个倒悬着的钟。参数a指高斯曲线的峰值，b为其对应的横坐标，c即标准差（有时也叫高斯RMS宽值），它控制着“钟”的宽度。

高斯函数被广泛运用于统计学以描述正态分布

3.总结

1）半监督学习是相对于监督学习和非监督学习来说的，前者是在标注好了的训练集上训练学习器，并用训练好的学习器去对新的样本进行预测；后者是在未标注的数据集上根据数据本身的分布情况来对数据进行分类

2）所以对于监督学习，让学习器不依赖外界交互、自动地利用为标记样本来提升学习性能，就是半监督学习

3）对于非监督学习，让学习器引入额外的监督信息来获得更好的性能，也是半监督学习

4）半监督学习要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记想联系的假设，其本质是“相似的样本拥有相似的输出”

5）基于这个假设，我们可以从不同的角度来使用非标记样本的这个特性，这就形成了不同的半监督学习算法