半监督学习综述_co-forest

半监督学习简介

自从 1946 年第一台电子计算机 ENIAC 诞生至今，计算机技术得到了迅猛的发展，这使得人类采集、存储数据的能力空前的提高，利用计算机对收集到的数据进行分析提取有价值信息的技术（机器学习技术）也随之而生，并得到了很快的发展。

传统的机器学习技术一般只利用有标记样本集或者只利用无标记样本集进行学习，而在实际问题中大多是有标记样本与无标记样本并存。在很多实际问题中，只有少量的带有标记的数据，因为对数据进行标记的代价有时很高，比如在生物学中，对某种蛋白质的结构分析或者功能鉴定，可能会花上生物学家很多年的工作，而大量的未标记的数据却很容易得到。为了更好地利用这些数据，半监督学习技术应运而生，近年来，半监督学习技术更成为机器学习领域一个被广泛研究的热点方向。

传统的机器学习技术可以分为两类，一类是无监督学习， 另一类是监督学习。
半监督学习则是介于两者之间的学习技术，它同时利用有标记样本与无标记样本进行学习。它所利用的数据集可以分为两部分，一部分是有标记的数据集， 另一部分是无标记数据集，这部分数据集中样本点的类别标记未知。 与实际情况相符一般假设无标记数据远远多于有标记数据。

半监督学习的发展

最早利用到半监督学习思想的算法应当是自训练(self-training)方法，出现于 20 世纪 60-70 年代的某些文献中。自训练方法的基本思想是首先利用监督学习技术对有标记的数据进行学习，然后利用学习到的结果对未标记数据进行标记，再将新标记的数据加入到有标记的数据中去再学习，如此迭代。 然而这种方法的性能依赖于其中的监督学习技术，而且当利用 0-1 代价函数经验风险最小化进行学习时，未标记样本将失效。
之后出现的则是与半监督学习技术十分相关的直推(transductive)学习技术， 直推学习技术由 Vapnik 在1974 年根据著名的 Vapnik 原理(不要通过解决更复杂的问题来解决问题)提出的学习技术，他认为很多学习任务只需要将当前数据集中的未标记样本进行标记，不需要对样本空间中的所有样本进行标记。直推学习技术与半监督学习技术的本质不同就在于，直推学习技术学习到的结果只需对当前数据中的未标记样本进行标记，半监督学习的学习目标则需是对于整个样本空间中的所有样本都可预测其标记。
半监督学习技术开始发展是由于 20 世纪 70 年代对利用未标记数据学习 Fisher 线性判别规则的研究。这段时间利用 EM 算法结合高斯混合模型或者多项式分布模型的半监督学习技术被广泛提出来。 根据 D.J.Miller 和 H.S. Uyar的看法，由于很难利用未标记数据对训练诸如前馈神经网络等当时主流学习技术进行提高，所以半监督学习研究在那个时候没有能够迅速发展开来。
而到了 20 世纪 90 年代，由于自然语言处理的发展，对利用未标记数据帮助提高学习性能的需求越来越强烈，半监督学习才成为了机器学习领域中的研究热点方向。 根据 O. Chapelle 等人的看法，半监督学习这个术语最早是在 Merz 等人在 1992 年使用的。

半监督学习中的基本假设

目前的机器学习技术大多基于独立同分布假设，即数据样本独立地采样于同一分布。
除了独立同分布假设， 为了学习到泛化的结果， 监督学习技术大多基于平滑smoothness)假设，即相似或相邻的样本点的标记也应当相似。 而在半监督学习中这种平滑假设则体现为两个较为常见的假设：聚类(cluster)假设与流型(manifold)假设。
下面对半监督学习中两个常用的假设做简单的介绍。
聚类假设是指同一聚类中的样本点很可能具有同样的类别标记。 这个假设可以通过另一种等价的方式进行表达，那就是决策边界所穿过的区域应当是数据点较为稀疏的区域，因为如果决策边界穿过数据点较为密集的区域那就很有可能将一个聚类中的样本点分为不同的类别这与聚类假设矛盾。
流型假设是指高维中的数据存在着低维的特性。 Z.H. Zhou 在文献[29]中给了另一种类似的表述，“处于一个很小的局部邻域内的示例具有相似的性质”。 关于这两者的等价性没有严格的证明，但是高维数据中的数据的低维的特性是通过局部邻域相似性体现的，比如一个在三维空间卷曲的二维纸带，高维的数据全局的距离度量由于维度过高而显得没有区分度，但是如果只考虑局部范围的距离度量，那就会有一定意义。
这两种假设一般是一致的，属于监督学习中平滑假设的在半监督学习中的推广。 Z.H. Zhou[29]认为流型假设比聚类假设更为一般，因为根据他的描述流型假设是相似的样本点具有相似的性质而不是聚类假设所认为的相同的标记，对于聚类假设无法成立的回归问题上流型假设却可以成立。

半监督学习算法介绍

1 自训练

自训练是一种增量算法（incremental algorithm），最初使用少量标记数据构建单个分类器。然后，它迭代地预测未标记示例地标签，通过预测结果的可信程度对样本进行排序，并将最有效的样本添加到标记的训练集中。它使用增强的（augmented）训练集重新训练基础分类器，并且重复该过程直至给定迭代次数或者满足一些启发式的收敛标准。只有当初始和后续的类别正确的标记了绝大多数样本时，才能通过迭代改进分类的精度。然而，添加错误的标记噪音是不可避免地。在实际应用中，使用更准确地信任度量和预定义地置信度阈值来限制错误标记地示例的数量。

自训练是一种包裹式算法，可以应用于许多算法中。将自训练应用于线性分类器（如SVM）时存在一个缺点是，最可信的样本往往离决策边界最远（非信息性样本）。因此在很多情况下，这个过程不会创建代表性的训练集（因为它选择的都是非信息性示例）。另外一个缺点是自训练对异常值非常敏感。如果一个样本靠近分类超平面，那么它就能够为调整分类决策面提供有效信息，因为它能够影响决策面的位置。

具体算法过程如下：
给定两个样本集合:Labled={(xi,yi)};Unlabled= {xj}.
执行如下算法：

Repeat:
1. 用L生成分类策略F;
2. 用F分类U,计算误差
3. 选取U的子集u,即误差小的,加入标记.L=L+u; 
重复上述步骤,直到U为空集.
1
2
3
4
5

上面的算法中,L通过不断在U中,选择表现良好的样本加入,并且不断更新子集的算法F，最后得到一个最优的F。

Self-training的一个具体实例:最近邻算法

记d(x1,x2)为两个样本的欧式距离,执行如下算法:

Repeat:
1. 用L生成分类策略F;
2. 选择x = argmin d(x, x0). 其中x∈U,min x0∈L.也就是选择离标记样本最近的无标记样本.
3. 用F给x定一个类别F(x).
4. 把(x,F(x))加入L中
重复上述步骤,直到U为空集。
1
2
3
4
5
6

上面算法中,也就是定义了self-training的”误差最小”,也就是用欧式距离来定义”表现最好的无标记样本”,再用F给个标记,加入L中,并且也动态更新F.

2 生成式模型

这类算法基于聚类假设。
在半监督学习的生成式模型中，高斯混合模型（GMM）是被用得最多的混合模型。
这类算法一般采用 EM 算法利用未标记样本进行对模型中 $p(x|y_i)$组成成分的参数进行估计， 再利用少量的未标记样本确定各分量所代表的类别， 这类算法比较经典的是 Nigam 等人在 2000 年的工作，Nigam等人将EM和朴素贝叶斯结合，通过引入加权系数动态调整无类标签的样例的影响提高了分类准确度，建立每类中具有多个混合部分的模型，使贝叶斯偏差减小。
这类算法简单， 但是存在着较难解决的问题，如克服 EM 算法的局部最优解的问题， Nigam 在 2001年的工作[9]在这方面做出了尝试； 除了使用混合模型以外，很多算法还需要首先对未标记样本进行聚类，然后再利用已标记样本给这些聚类的结果赋予类别标记，尽管在模型与数据磨合很好的情况下，这类算法可以有很好的性能， 但这类算法很难分析[1]。

3 低密度分割算法

低密度分割就是要尽量让分类边界通过密度较低区域。

半监督支持向量机(S3VM, Semi-Supervised SVM)

将聚类假设运用到支持向量机中， 即是要分类边界绕过数据密集的区域。 将 SVM 改进应用到半监督学习中的也是 SVM的提出者Vapnik， S3VM 其本质上是直推式的， Vapnik 本人提出时也称之为 TSVM(Transductive SVM)，直推/转导支持向量机。就是对样本中的所有的数据包括标记的与未标记的建立一个分类界面， 在学习过程中，调整分类界面，使得“间隔”最大，而且尽量避过数据较为密集的区域（通过修改分类边界两侧的未标记样本的类别标记迫使分类界面调整至稀疏区域）。

在训练过程中，TSVM算法首先利用有标记的数据训练一个SVM并估计未标记数据的标记，然后基于最大化间隔准则，迭代式地交换分类边界两侧样本的标记，使得间隔最大化，并以此更新当前预测模型，从而实现在尽量正确分类有标记数据的同时，将决策边界“推”向数据分布相对稀疏的区域。

然而，TSVM的损失函数非凸，学习过程会因此陷入局部极小点，从而影响泛化能力。为此，多种TSVM的变体方法被提出，以缓解非凸损失函数对优化过程造成的影响，典型方法包括确定性退火、CCCP直接优化等。此外，低密度划分思想还被用于TSVM以外的半监督学习方法的设计，例如通过使用熵对半监督学习进行正则化，迫使学习到的分类边界避开数据稠密区域。

使用半定规划的半监督学习算法

解 TSVM 的优化目标是一个 NP-难的问题，因为除了分类界面未标记样本的标记也是未知，导致了损失函数非凸[10]。 很多研究人员尝试放松 TSVM 的优化目标以期使得问题可解。 其中较为经典的工作就是De Bie 和 Cristianini[11]提出的将 TSVM 的优化目标放松成为半定规划问题，而半定规划问题是凸优化问题，从而使得问题对于稍大数据集可解。
但是实验的结果并没有十分的好，因为解半定规划问题所需要的计算开销依然很大。
除此之外， N.D. Lawrence 和 M.I. Jordan[12]通过修改高斯过程的噪音模型来进行半监督学习，对类的标记除了正负类之外，他们还引入了标记 0，并且规定未标记的数据的类别标记不可以标记为 0，这样迫使分类边界避开数据密集区域，这与 TSVM 的想法类似；使用正则化项使学习结果具有某种所需要的特性是机器学习领域中的惯用手法， Grandvalet 和 Bengio[13]通过在优化目标中将未标记样本的熵作为正则化项加入到优化目标中去进行学习，从而使得熵最小化，进而使得分类界面尽量不要切分数据密集区域，因为切分了数据密集区域则使得其不确定性增加，从而使得熵变大。

4 基于图的半监督算法

这类算法基于流型假设。假设所有的样本点（包括已标记与未标记）以及之间的关系可以表示为一个无向图的形式g=<V,E> 。其中图的结点为数据样本点，而边则体现了两个样本点之间的相似度关系。 基于图的半监督算法的优化目标就是要保证在已标记点上的结果尽量符合而且要满足流型假设。
Zhou 等人在 2004 年提出了标记“扩散” (spreading)算法，Szummer 和 Jaakkola于 2002 年提出了基于马尔可夫随机游走(Markov Random Walk)策略的给图中未标记点进行标记的算法。

事实上，标记传播方法对学习性能的影响远比不上数据图构建方法对学习性能的影响大。如果数据图的性质与数据内在规律相背离，无论采用何种标记传播方法，都难以获得满意的学习结果。然而，要构建反映数据内在关系的数据图，往往需要依赖大量领域知识。所幸，在某些情况下，仍可根据数据性质进行处理，以获得鲁棒性更高的数据图，例如当数据图不满足度量性时，可以根据图谱将非度量图分解成多个度量图，分别进行标记传播，从而可克服非度量图对标记传播造成的负面影响[13]。基于图的半监督学习方法有良好的数学基础，但是，由于学习算法的时间复杂度大都为O(n3)　，故难以满足对大规模未标记数据进行半监督学习的应用需求。

5 基于分歧的半监督算法

协同训练

标准协同训练算法是 Blum 和 Mitchell[18]在 1998 年提出的。他们提出了标准协同训练算法的三个基本假设： (1)属性集可以被划分为两个集合； (2)每一个属性集的子集合都足以训练一个分类器； (3)在给定类标签的情况下，这两个属性集是相互独立的。 其中每个属性集构成一个“视图” (view)，满足上述假设的“视图” 被称为“”充分冗余“视图”。 然后分别对已标记的样本在这两个属性集上训练分类器，这样得到两个分类器， 将这两个分类器应用到未标记样本上，然后选择每个分类器对分类结果置信度高的未标记样本以及该样本的预测标记加入到另一个分类器已标记样本集中进行下一轮的训练，如此迭代（如算法二所示）。
协同训练算法其实是通过引入未标记数据缩减假设空间来提高学习算法的性能的[1]。

Blum 和 Mitchell 的那三个假设很强，正如 Z.H. Zhou 在文献[29]中所说，在真实的问题中，满足充分冗余的要求往往很难达到。 Z.H. Zhou 举 Blum 和 Mitchell 当年所举的网页分类的例子来说明，“因为网页本身的信息这一视图与超链接上的信息这一视图很难满足条件独立性”，而且“大多数问题不具有充分大的属性集”。很多研究人员就尝试放松这三个假设。 Goldman 和 Zhou[19]在 2000 年提出了使用不同的分类器在整个属性集上训练的方法，训练时，首先利用已标记样本对两个不同的分类器在整个属性集上进行训练，再
用这两个分类器互相将自己在未标记样本上置信度较高的标记加入到对方的训练集中去再训练。在这个工作之后他们二人在 2004 年[20]又将集成学习的思想加入到他们的方法中去提高算法性能，基于整个属性集训练一组分类器，利用投票机制对未标记样本进行标记，加入到已标记样本集中再训练，最后的分类结果由加权投票机制的一个变种决定。

但是由于 Goldman 和 Zhou 的算法“在挑选未标记示例进行标记的过程中以及选择分类器对未见示例进行预测的过程中频繁地使用 10 倍交叉验证”，使得其计算开销很大， Z.H. Zhou 和 M. Li[21]在 2005 年提出了 tri-training 的算法，使用三个分类器，如果两个分类器分类结果一致，那么就将该未标记样本加入到已标记样本中去，这样的做法避免了频繁地计算 10 倍交叉验证，节省了计算开销，同时他们的算法不需要基于不同的视图，甚至不需要基于不同的分类器。 并且他们基于噪音学习理论给出了“以较高概率确保这一做法有效的条件”，在引入大量未标记样本的情况下，噪声所带来的负面影响可以被抵消。此后，他们还将tri-training 算法扩展为 Co-Forest 算法，并将这个方法用于乳腺癌诊断中的微钙化检测，通过实验证明这个方法能够有效提高预测精度．

半监督学习应用

比如在语音识别领域，现在的音频很多，而对这些音频加上标记，需要人去听并辨别这些音频再加上标记，相比于未标记的音频有标记的音频少之又少。
比较典型的应用就是在自然语言处理领域的应用。更由于互联网的日益发达，指数级增长的网络资源，能进行人工标记的网页等的资源是微乎其微，半监督学习技术在这方面得到了很广泛的应用。
半监督学习还有一个典型的应用，就是生物学领域对蛋白质序列的分类问题（蛋白质结构预测）。 对一种蛋白质的结构进行预测或者功能鉴定需要耗费生物学家很长时间的工作，知道了一个蛋白质表示序列，如何利用少有的有标记样本以及大量的蛋白质序列来预测蛋白质的结构， 而半监督学习技术则是为了解决这类问题而设计的， 这使得半监督学习在这个问题上被广泛研究。 比如 Weston 等人[28]利用聚类核方法对蛋白质的序列进行半监督分类； Shin 和 Tsuda[1]利用基于图的半监督学习算法对蛋白质的功能进行预测。

参考网址：
半监督学习
半监督学习综述
半监督学习综述
周志华《机器学习》（很全面）