半监督学习

0  引言

机器学习(machine learning)是人工智能的核心研究领域，是智能信息处理的重要途径。监督学习(supervised learning)是机器学习中研究最多、应用最广泛的一种学习途径。在传统的监督学习中，学习系统通过对大量的有标记训练样本 (labeled examples) 进行学习，建立模型用于预测未知样本的标记(label)。在此，标记对应于示例的输出，用于表征待学习的目标概念。

随着数据收集和存储技术的发展，收集大量缺少标记的数据已相当容易，而为这些数据提供标记则相对困难，因为数据标记过程往往需要消耗大量人力物力，甚至必须依赖于少数领域专家来完成。例如在计算机辅助诊断中，可以方便地从医院日常体检中获取训练数据，但是让医学权威专家为所有的体检结果提供诊断往往是不现实的。事实上，在实际应用中，大量未标记数据和少量有标记数据并存的情况比比皆是。然而，由于能用于监督学习的有标记样本较少，通常难以学得泛化能力强的模型。因此，如何利用大量未标记数据来帮助提升在少量有标记数据上学得模型的泛化能力，成为了当前机器学习领域倍受关注的重要问题之一。

目前，利用未标记数据学习有三大主流技术，分别是半监督学习(semi-supervised learning)、直推学习(transductive learning)以及主动学习(active learning)。与直推学习仅关注在未标记数据上的预测性能以及主动学习依赖于人工干预不同，半监督学习可以自动地对未标记数据加以利用，学习在整个数据分布上具有强泛化能力的模型。整个学习过程无需人工干预，完全基于学习系统自身实现对未标记数据的利用。半监督学习凭借其自身特点以及广大的应用需求，在过去10年中已发展成为机器学习中一大研究热点。鉴于此，本文对半监督学习的研究进展进行简要介绍。

1  未标记数据的作用

缺少概念标记的未标记数据为何能够帮助学习器学习目标概念？图1给出了一个简单的例子，其中“+”代表正类样本、“-”代表反类样本、“.”代表未标记样本。此时，需要来预测“*”这个样本的标记。若仅利用有标记样本进行学习(如图1(a)所示)，很自然地会将该样本判为正类样本；但若考虑大量未标记样本(如图1(b)所示)，则可以发现待预测样本和有标记的正类样本同属于一个簇，有理由相信一个簇中样本性质应该相似，因此将该样本预测为反类样本应更加合理。从此例可以看出，未标记数据提供的分布信息能够帮助学习。

图 1  未标记数据的作用

最早对未标记数据效用的理论解释出现于1997年?Miller et al[1]的工作中。他们假设训练数据符合某个由M个成分组成的混合分布，并根据最大后验概率规则导出了一个可分解为P(y|mj, x)和P(mj|x)乘积的最优分类函数，其中mj代表第j个混合成分。学习目标则是在训练数据上估计上述两项概率。由于第二项不依赖于样本的标记y，利用大量的未标记数据可帮助提升对P(mj|x)估计精度。此后，Zhang et al[2]对半监督学习的进一步分析指出，如果一个参数化模型能够分解成p(x,y|θ)=p(y|x,)p(x|θ)的形式，那么未标记数据的作用体现于它们能够帮助更好地估计模型参数，从而提高模型性能。

事实上，若要未标记数据在学习过程中发挥效用，就必须建立未标记数据分布和预测模型之间的联系。在生成式模型中，这种联系通过数据生成过程而体现，即模型决定未标记数据该如何分布。对于通用学习器，往往需要借助某些假设来建立预测模型和未标记数据之间的联系。在半监督学习中，聚类假设(cluster assumption)和流形假设(manifold assumption)是两种最常用来建立联系的假设。聚类假设要求预测模型对相同聚类中的数据应该给出相同的类别标记，通常适用于分类问题；流形假设要求预测模型对相似输入数据应该给出相似的输出，除分类问题外还适用于回归、排序等任务，在某些情况下可以看成聚类假设的一种自然推广。现有多数的半监督学习方法大都直接或间接地体现了上述假设。

2  半监督学习方法

目前公认的半监督学习研究工作起源于1994年Shahshahani et al[3]在卫星遥感图像分析中对未标记图像的利用。之后，半监督学习得到了广泛关注，很多半监督学习方法相继提出。这些方法大致可分为四大类，分别是基于生成式模型(generative-model-based)的半监督学习、基于低密度划分(low-density-separation-based)的半监督学习、基于图(graph-based)的半监督学习以及基于不一致性(disagreement-based)的半监督学习。

2.1  基于生成式模型的半监督学习方法

该类方法通常是把未标记样本属于每个类别的概率看成一组缺失参数，然后采用EM (expectation-maximization) 算法对生成式模型的参数进行极大似然估计。不同方法的区别在于选择了不同的生成式模型作为基分类器，例如混合高斯(mixture of Gaussians)[3]、混合专家 (mixture of experts)[1]、朴素贝叶斯(na　ve Bayes)[4]。虽然基于生成式模型的半监督学习方法简单、直观，并且在训练样本，特别是有标记样本极少时能够取得比判别式模型更好的性能，但是当模型假设与数据分布不一致时，使用大量的未标记数据来估计模型参数反而会降低学得模型的泛化能力[5]。由于寻找合适的生成式模型来为数据建模需要大量领域知识，这使得基于生成式模型的半监督学习在实际问题中的应用有限。

2.2  基于低密度划分的半监督学习方法

该类方法要求决策边界尽量通过数据较为稀疏区域，以免把聚类中稠密的数据点分到决策边界两侧。基于该思想，Joachims[6]提出了TSVM算法(如图2所示，其中实线为TSVM的分类边界、虚线为不考虑未标记数据的SVM分类边界）。在训练过程中，TSVM算法首先利用有标记的数据训练一个SVM并估计未标记数据的标记，然后基于最大化间隔准则，迭代式地交换分类边界两侧样本的标记，使得间隔最大化，并以此更新当前预测模型，从而实现在尽量正确分类有标记数据的同时，将决策边界“推”向数据分布相对稀疏的区域。然而，TSVM的损失函数非凸，学习过程会因此陷入局部极小点，从而影响泛化能力。为此，多种TSVM的变体方法被提出，以缓解非凸损失函数对优化过程造成的影响，典型方法包括确定性退火[7]、CCCP直接优化[8]等。此外，低密度划分思想还被用于TSVM以外的半监督学习方法的设计，例如通过使用熵对半监督学习进行正则化，迫使学习到的分类边界避开数据稠密区域[9]。

图 2  TSVM算法示意图[6]

2.3  基于图的半监督学习方法

该类方法利用有标记和未标记数据构建数据图，并且基于图上的邻接关系将标记从有标记的数据点向未标记数据点传播（如图3所示，其中浅灰色和黑色结点分别为不同类别的有标记样本、空心结点为未标记样本）。根据标记传播方式可将基于图的半监督学习方法分为两大类，一类方法通过定义满足某种性质的标记传播方式来实现显式标记传播，例如基于高斯随机场与谐函数的标记传播[10]、基于全局和局部一致性的标记传播[11]等；另一类方法则是通过定义在图上的正则化项实现隐式标记传播，例如通过定义流形正则化项，强制预测函数对图中的近邻给出相似输出，从而将标记从有标记样本隐式地传播至未标记样本[12]。事实上，标记传播方法对学习性能的影响远比不上数据图构建方法对学习性能的影响大。如果数据图的性质与数据内在规律相背离，无论采用何种标记传播方法，都难以获得满意的学习结果。然而，要构建反映数据内在关系的数据图，往往需要依赖大量领域知识。所幸，在某些情况下，仍可根据数据性质进行处理，以获得鲁棒性更高的数据图，例如当数据图不满足度量性时，可以根据图谱将非度量图分解成多个度量图，分别进行标记传播，从而可克服非度量图对标记传播造成的负面影响[13]。基于图的半监督学习方法有良好的数学基础，但是，由于学习算法的时间复杂度大都为O(n3)?，故难以满足对大规模未标记数据进行半监督学习的应用需求。

图 3  标记传播示意图

2.4  基于不一致性的半监督学习方法

该类方法需要同时协同多个有差异性的学习器来实现对未标记数据的利用。在迭代式的学习过程中，当多个学习器在某个未标记数据上存在不一致的预测结果时，若部分学习器的置信度明显高于其他学习器，那么低置信度学习器将利用高置信度学习器给出的标记进行学习；若所有学习器的预测置信度都比较低，可通过与外界交互获取其标记信息。在此，未标记数据实际上为多个学习器提供了“信息交互平台”。基于不一致性的半监督学习起源于1998年Blum et al[14]提出的协同训练算法(如图4所示)。该算法假设数据具有两个充分冗余视图(sufficient and redundant views)，即从每个视图足以学得一个泛化能力强的学习器，且给定类别标记后视图之间相互独立，并通过不同视图上的学习器相互标记样本的方式进行半监督学习。他们证明当上述假设条件满足时，协同训练可利用未标记数据提升学习器性能。然而，在大多数实际应用中，数据均不具有充分冗余视图。为此，研究者在半监督学习中利用单视图下多个有差异性的学习器代替多个视图下的学习器，典型方法包括基于特殊基学习器的协同训练方法[15]、协同三分类器的半监督学习方法tri-training[16]、协同多分类器集成的半监督学习方法Co-Forest[17]、基于一致性(consistency)置信度估计的半监督回归方法COREG[18]等。最近，Wang et al[19]从理论上揭示了协同训练奏效的关键是学习器之间需要存在足够的不一致性(disagreement)，从而为上述采用多个有差异性学习器代替充分冗余视图的方式提供了理论依据。文献[20]给出了基于不一致性半监督学习方法的综述。

图 4  协同训练示意图

   上述四大类半监督学习方法已成功用于解决自然语言处理、互联网搜索、软件工程、生物信息学、医学等多个领域，并取得了良好的效果。例如：Li et al[21]基于不一致性框架设计了半监督排序方法SSRank，有效利用未标记数据提升了互联网搜索的性能；Xu et al[22]将Co-Forest算法用于蛋白质亚细胞定位，在利用未标记数据学习后，预测性能比现有监督学习方法提高了10%。

3  结束语

半监督学习是利用未标记学习的重要技术，它可以在无需外界干预的情况下自动利用大量未标记数据提升学习器在整个数据分布上的泛化能力。本文简要介绍了半监督学习中未标记数据的作用、半监督学习方法的分类及代表算法。

虽然半监督学习技术已取得了长足的发展，然而仍有一些重要问题有待进一步研究。例如，至少需要多少标记样本才能实现有效的半监督学习？在特殊情况下，这一问题已得到初步回答[23]，但在一般情况下半监督学习对标记样本的最低需求量仍是一个开问题。另一个值得研究的问题是，半监督学习在何种情况下奏效？以往研究表明，使用半监督学习可能造成学习器泛化能力显著下降。因此，设计出“安全”的半监督学习方法，使得学习器性能不会因利用未标记数据而降低，将有助于半监督学习解决更多的真实问题。此外，将半监督学习用于解决更多实际问题仍将继续成为半监督学习研究重要组成部分。

参考文献：

[1]Miller D J, Uyar H S. A mixture of experts classifier with learning based on both labelled and unlabelled data[C]//Mozer M, Jordan M I, Petsche T, et al. Advances in Neural Information Processing Systems 9. Cambridge: MIT Press, 1997: 571-577.

[2]Zhang T, Oles F J. A probability analysis on the value of unlabeled data for classification problems[C]//Proceedings of 17th International Conference on Machine Learning. Stanford: [s. n. ], 2000: 1191-1198.

[3]Shahshahani B, Landgrebe D. The effect of unlabeled samples in reducing the small sample size problem and mitigating the hughes phenomenon[J]. IEEE Transactions on Geoscience and Remote Sensing, 1994, 32(5): 1087-1095.

[4]Nigam K, McCallum A K, Thrun S, et al. Text classification from labeled and unlabeled documents usingEM[J]. Machine Learning, 2000, 39(2-3): 103-134.

[5]Cozman F G, Cohen I. Unlabeled data can degrade classification performance of generative classifier[C]//Proceedings of the 15th International Conference of the Florida Artificial Intelligence Research Socioty. Pensacola: [s. n. ], 2002: 327-331.

[6]Joachims T. Transductive inference for text classification using support vector machines[C]//Proceedings of the 16th International Conference on Machine Learning. Bled, Slovenia: [s. n. ], 1999: 200-209.

[7]Sindhwani V, Keerthi S S, Chapelle O. Deterministic annealing for semi-supervised kernel machines[C]// Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh: [s. n. ], 2006: 123-130.

[8]Collobert R, Sinz F, Weston J, et al. Large scale transductive SVMs[J]. Journal of Machine Learning Research, 2006, 7(8): 1687-1712.

[9]Grandvalet Y, Bengio Y. Semi-supervised learning by entropy minimization[C]//Saul L K, Weiss Y, Bottou L, et al. Advances in Neural Information Processing Systems 17.  Cambridge: MIT Press, 2005: 529-536.

[10]Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using Gaussian fields and harmonic functions[C]//  Proceedings of the 20th International Conference on Machine Learning. Washington: [s. n. ], 2003: 912–919.

[11]Zhou D, Bousquet O, Lal T N, et al. Learning with local and global consistency[C]//Thrun S, Saul L, Sch?lkopf B, et al. Advances in Neural Information Processing Systems 16. Cambridge: MIT Press, 2004: 321-328.

[12]Belkin M, Niyogi P, Sindwani V. Manifold regularization: a geometric framework for learning from labeled and unlabeled examples[J]. Journal of Machine Learning Research, 2006, 7(11): 2399-2434.

[13]Zhang Yin, Zhou Zhihua. Non-metric label propagation[C]//Proceedings of the 21st International Joint Conference on Artificial Intelligence. Pasadena: [s. n. ], 2009: 1357-1362.

[14]Blum A, Mitchell T. Combining labeled and unlabeled data with co-training[C]//Proceedings of the 11th Annual Conference on Computational Learning Theory. Madison: [s. n. ], 1998: 92-100.

[15]Goldman S, Zhou Y. Enhancing supervised learning with unlabeled data[C]//Proceedings of the 17th International Conference on Machine Learning. San Francisco: [s. n. ], 2000: 327-334.

[16]Zhou Zhihua, Li Ming. Tri-training: exploiting unlabeled data using three classifiers[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11): 1529-1541.

[17]Li Ming, Zhou Zhihua. Improve computer-aided diagnosis with machine learning techniques using undiagnosed samples[J]. IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, 2007, 37(6): 1088-1098.

[18]Zhou Zhihua, Li Ming. Semi-supervised regression with co-training style algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(11): 1479-1493.

[19]Wang Wei, Zhou Zhihua. Analyzing co-raining style algorithms[C]// Proceedings of the 18th European Conference on Machine Learning. Warsaw: [s. n. ], 2007: 454-465.

[20]Zhou Zhihua, Li Ming. Semi-supervised learning by disagreement[J]. Knowledge and Information Systems, 2010, 24(3): 415-439.

[21]Li Ming, Li Hang, Zhou Zhihua. Semi-supervised document retrieval[J]. Information Processing & Management, 2009, 45(3): 341-355.

[22]Xu Qian, Hu Derek Hao, Xue Hong, et al. Semi-supervised protein subcellular localization[J]. BMC Bioinformatics, 2009, 10(S1): S47.

[23]Zhou Zhihua, Zhan Dechuan, Yang Qiang. Semi-supervised learning with very few labeled training examples[C]//Proceedings of the 22nd AAAI Conference on Artificial Intelligence. Vancouver: [s. n. ], 2007: 675-680.

作者简介：黎铭，博士，南京大学计算机科学与技术系副教授，中国人工智能学会会员；主要研究方向为机器学习、数据挖掘、信息检索。E-mail：[e-mail]

基金项目：国家自然科学基金项目(60903103)