半监督学习

未标记样本

我们有训练样本集$D_l=\{(x_1,y_1),(x_2,y_2),…,(x_l,y_l)\}$这l个样本的类别标记(即是否好瓜)已知,称为”有标记”(labeled)样本;此外,还有$D_u=\{(x_{l+1},x_{l+2},…,x_{l+u})\}$,l<<u,这u个样本的类别标记未知(即不知是否好瓜),称为”未标记”(unlabeled)样本.若直接使用传统监督学习技术,则仅有$D_l$能用于构建模型,$D_u$所包含的信息被浪费了;另一方面,若$D_l$较小,则由于训练样本不足,学得模型的泛化能力往往不佳,那么,能否在构建模型的过程中将$D_u$利用起来呢？

我们可以用$D_l$先训练一个模型,再去取数据,询问专家这个数据的标签,然后把这个新获得的有标记样本加入$D_l$中重新训练一个模型,再去选取数据… 这样的学习方式称为”主动学习”,其目标是使用尽量少的”查询”来获得尽量好的性能.主动学习引入了额外的专家知识,通过与外界的交互来将部分未标记样本转换为有标记样本.

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

让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能,就是半监督学习。

要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设.最常见的是”聚类假设”,即假设数据存在簇结构,同一个簇的样本属于同一个类别。半监督学习中另一种常见的假设是”流形假设”,即假设数据分布再一个流形结构上,邻近的样本拥有相似的输出值.“邻近”程度常用”相似”程度来刻画,因此,流形假设可看作聚类假设的推广,但流形假设对输出值没有限制,因此比聚类假设的适用范围更广,可用于更多类型的学习任务.事实上,无论聚类假设还是流形假设,其本质就是”相似的样本拥有相似的输出”这个基本假设.

半监督学习可进一步划分为纯半监督学习和直推学习,前者假定训练数据中的未标记样本并非待预测的数据,而后者则假设学习过程中所考虑的未标记样本恰是待预测数据。学习的目的就是再这些未标记样本上获得最优泛化性能。换言之,纯半监督学习是基于”开放世界”假设,希望学得模型能适用于训练过程中未观察到的数据;而直推学习是基于”封闭世界”假设,仅试图对学习过程中观察到的未标记数据进行预测。

半监督学习中的一些常用算法模型

生成式方法

生成式方法是直接基于生成式模型的方法，此类方法假设所有数据（无论是否有标记）都是由同一个潜在的模型生产的。这个假设使得我们能通过潜在模型的参数将未标注数据与学习目的关联起来，而未标注数据的标记则可看作模型的确实参数。通常可基于EM算法进行极大似然估计求解。
在半监督学习生成式方法中，EM算法的使用逻辑是这样的：

1. 假设标注数据与未标注数据来源于同一潜在的分布模型，模型参数为 t
1. 给定参数的初始值 t0，我们可以根据分布模型计算出未标注数据的标注值 y0
1. 根据 y0 和标注数据使用极大似然估计估算此时参数 t 能使得数据概率最大的最优解 t1
1. 使用 t1 计算估算此时未标注数据的标注值 y1
1. 步骤3和步骤4不断迭代，直到收敛

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

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

半监督SVM

半监督支持向量机中最著名的是TSVM。TSVM试图考虑对未标记样本进行各种可能的标记指派,即尝试将每个未标记样本分别作为正例或负例,然后在所有这些结果中,寻求一个在所有样本(包括有标记样本和进行了标记指派的未标记样本)上间隔最大化的划分超平面.一旦划分超平面得以确定,未标记样本的最终标记指派就是其预测结果.

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

图半监督学习

将数据集映射成图，数据集中的每个样本对应于图中的一个结点，若两个样本之间的相似度或相关性很强，则对应的结点之间存在一条边，边的强度正比于样本之间的相似度。我们将有标记的数据看作是被染色的节点，未标注的数据是未染色的节点。图半监督学习就对应于“颜色”在图上扩散和传播的过程。由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。
基本的学习逻辑如下：

1. 基于数据集构建一个图 G = (V, E)，V代表结点集合，E代表边集合
1. 根据数据集中结点的相似度计算出图的边集 E 的亲和矩阵 W；其中 wij 代表第 i 个结点和第 j 个结点之间的相似度，一般可基于高斯函数定义
1. 假定从图 G 上可学得一个实值预测函数 f：V -> R，于是可定义关于 f 的“能量函数”，能量函数可理解为任意两个结点的预测结果的差值乘以它们之间的权重 $w_{ij}$ 的和。很明显，能量函数最小化时即得到最优结果
1. 对能量函数求导，可得到未标注数据的预测结果

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

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

基于分歧的方法

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

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

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

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

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

1.在每个视图上基于有标记样本分别训练出一个分类器
2.让每个分类器分别挑选自己“最有把握的”未标记样本赋予伪标记
3.将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新
4.重复步骤2、3直到两个学习器不再变化或达到预设的迭代次数时停止

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

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

详细见西瓜书P304-306

半监督聚类

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

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

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

首先，初始化 k 个簇，随机选择 k 个样本作为 k 个簇的初始均值向量
然后，不断迭代以下几步步骤>> 对每个样本 x ，计算其与每个簇均值向量的距离 d，
找出距离样本 x 最近的簇 i ，判断将 x 放进 i 是否违反“约束”
如果不违反，则将簇 i 作为 x 的簇标记，并将 x 放入该簇集合 C_i 中;如果违反，则找次近的簇，以此类推直到找到满足约束的最近簇 i’，将x 放入该簇集合 C_{i’} 中
对所有的簇集合，根据本次迭代得到的簇集合计算新的均值向量
当均值向量均未更新时，退出迭代步骤
最终，我们获得了聚类计算的结果簇划分

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