1.2 半监督学习方法

在当前的技术条件下，可以很容易地收集到大量无标记的样本，而有标记的样本获取则仍然十分困难，这是因为对样本进行标记往往需要消耗大量的人力和物力^［4］。以遥感图像的分类问题为例，图像对应的地物类别必须通过实地考察才可以确定，而遥感图像常覆盖着广大的区域，造成实地考察难度大、耗时长的问题，因此可用的标记样本量常无法满足需求。基于数量有限的有标记样本训练得到的分类器往往泛化能力较低；而大量未标记样本无法得到有效的利用，则造成数据资源的巨大浪费。半监督学习就是一种可以合理利用大量未标记样本作为有限的有标记样本的补充，对分类器性能进行优化的机器学习方法。本节将首先介绍半监督学习的思想起源，然后给出无标记样本提高学习性能的基本假设，最后对几种主流的半监督学习方法进行简要介绍。

1.2.1 半监督学习概述

一般认为，Shahshahani和Landgrebe^［24］在1994年的研究工作是半监督学习的开始。但由于在当时的主流机器学习方法（如神经网络）中考虑未标记样本相对比较困难，因此未得到较大关注。近些年来，随着统计学习理论的不断发展、机器学习理论在实际问题中的广泛应用以及利用未标记样本这一需求的日渐强烈，半监督学习逐渐成为机器学习研究领域的一个热点，并获得了长足的发展。

半监督学习的思想起源于自训练（Self-training）方法，自训练算法又被称为自学习（Self-teaching）算法或Bootstrapping方法，是目前在半监督学习中普遍使用的一种方法。在自训练方法中，首先用少量的有标记数据训练出一个初始的分类器，然后用该分类器对无标记数据进行预测。之后将置信度较高的无标记样本连同预测出的类别标记一同加入到原来的训练集中。再用新的训练集重新训练这个分类器，如此循环下去，直到达到终止条件。由上述学习过程可以看出，该方法能够利用无标记样本对训练样本集进行扩充，需要注意的一点是，如果在自训练过程中出现分类错误，则这些错误不但很难被纠正，而且会向下一轮的训练传播，反而使错误不断增强，因此如何选择置信度高的无标记样本至关重要。有些算法通过事先设定阈值的方式避免错误增强问题，若预测置信度低于设定的阈值，则不对相应的未标记样本做进一步的学习。自训练方法通常难以进行理论分析，但仍有一些专家学者尝试对其收敛性进行分析。

在一定的前提条件下，采用无标记的样本可以提高分类器的性能。Miller和Uyar^［25］通过理论推导，证明如果目标和未标记样本分布之间能够建立相互联系，利用未标记样本训练分类器就能够达到提高分类性能的效果。通常，未标记样本和目标间的联系需以某些假设为基础。聚类假设（Cluster Assumption）和流形假设（Manifold Assumption）是目前在半监督学习中使用最广泛的两个基本假设。

1）聚类假设是指相同聚类（Cluster）中的样本具有相同标记的概率更高。因此，分类器的决策边界就应尽可能避开各聚类中的数据稠密区域以免将聚类分割到决策边界两侧。根据聚类假设，未标记样本用来作为分析样本空间中数据分布的依据，根据未标记样本数据的分布特点，来调整通过标记样本学习得到的决策边界，使决策边界尽可能通过样本空间中数据分布稀疏的区域^［4］。聚类假设简单且直观，因此得到了较广泛的应用^{［26，27］}。例如，Joachims等^［28］提出一种直推式支持向量机，在训练时，通过不断调整支持向量机的决策超平面并标记超平面两侧部分未标记样本，使得分类器在全体样本组成的训练集上取得最大分类间隔，得到的分类超平面能避开数据稠密区域并对有标记样本进行正确划分；Lawrence等^［29］通过对高斯过程（Gaussian Process）中的噪声模型进行修改来实现半监督学习，该方法在正、反两类之外引入“零类”，禁止任一未标记样本被归入零类，以保证训练得到的决策面远离数据稠密区域；Grandvalet等^［30］引入信息熵作为正则化项来实现半监督学习，由于熵的最小化仅和模型在未标记样本上的输出相关，因此，最小化熵就是降低模型的不确定性，从而迫使决策面从数据稀疏的区域通过。

2）流形假设则认为数据空间中的邻近样本应具有相似性，即这些样本的标记应该是大体一致的。具体来说，在高维空间中一个很小的局部邻域内的数据点在低维投影空间中应该是相近的，其标记也应该相似。这种相似性可理解为决策函数的局部平滑特性。相对而言，聚类假设注重整体特性，流形假设则着眼于局部特性。在流形假设下，大量存在的未标记样本使得数据空间更加稠密，因此对局域特性的刻画更加精细，相应的决策函数对数据的拟合也有更好的效果^［31］。在实际中，可直接应用流形假设。例如，Zhu等^［32］基于高斯随机场（Gaussian Random Field）和谐波函数实现半监督学习，先是根据训练样本集建立一个图，图中各个节点都表示一个（有标记或未标记）样本，接着由流形假设构造能量函数并求其最优解，以确定未标记样本对应的最优类别标记；Zhou等^［33］基于流形假设根据样本间的相似性建立图模型，并使有标记样本节点上的信息（类标）向邻近节点不断传播，直到实现图的全局稳定。

可以证明聚类假设和流形假设在本质上是一致的^［4］。事实上，聚类通常是比较稠密的区域，因此根据流形假设得到的模型输出在同一聚类中也是相似的。两者的差别在于，由于流形假设要求相似样本具有相似输出而非完全相同的标记，因此流形假设较聚类假设更为一般化，在一些半监督回归问题中聚类假设难以满足，而流形假设则更易实现^［4］。

1.2.2 半监督学习方法简介

半监督学习涵盖的范围非常广泛，如果根据所选取的不同模型来分类，则半监督学习方法可大致分为生成式模型（Generative Models）、协同训练（Co-training）、最大化分离（Maximizing Separation）和基于图的方法（Graph-based Methods）4种。其中，生成式模型将未标记样本属于各类别的概率作为缺失参数，使用期望最大化（Expectation Maximization，EM）算法对标记参数和模型参数进行估计，利用大量未标记样本帮助建立高斯混合模型的各个成分。为避免一个分类器的分类错误传递到后续过程中，并累积而导致分类器的训练结果持续恶化，协同训练假设样本集具有两个完备且冗余的视图（特征子集），利用这两个视图分别训练出对应的分类器。在协同训练阶段，两个分类器各自在未标记样本中对一些置信度较高的样本进行标记，并将标记后的样本补充到对方的标记训练集中，然后重新训练，当没有更多合适的未标记样本加入时迭代停止。当所使用的基分类器在初始分类效果上存在差异时，即便使用单个视图协同训练也同样有效。最大化分离方法要求数据分布满足聚类假设并存在较低的概率密度分布区域，通过加入约束项使得分类的超平面避开数据稠密的样本区域。而基于图的方法以流形假设理论为依据，通常利用训练样本集中标记样本和无标记样本间的相似度来构建图，通过流形正则化方法求解相应的决策函数。下面将对这4种主要的半监督学习方法进行更为详细的介绍。

（1）生成式模型半监督学习方法^［34］

生成式模型是最早的半监督学习方法之一。该方法完全基于数据的概率分布进行建模，其基本思想是对于给定样本特征的完全数据概率建模，通常以生成式模型为分类器，将未标记样本属于各类别的概率看作缺失参数，然后利用最大似然算法对标记和模型参数进行估计。常用于半监督学习的生成式模型有高斯混合模型、多项式混合模型、Markov隐式模型等。此类方法也可以看成是以少量已知标记的样本为中心进行聚类，因而属于基于聚类假设的方法。

在半监督问题中，常将未标记样本隶属于各个类别的概率看作一组缺失参数，在此基础上采用期望最大化算法^［35］对标记和模型参数进行估计，从而利用未标记样本实现提升分类器分类性能的目标。期望最大化算法对模型的参数估计通常是利用最大似然准则来实现。假设数据集X={x₁，x₂，…，x_N}中的全部分量都是基于特定分布p（x_i|θ）的独立同分布采样获得的，则数据集的似然函数可表示为

式中：θ为样本分布的参数向量；N为样本个数；L（·）为似然函数。

最大似然准则就是要寻找满足以下条件的模型参数：

为简化计算，常利用对数似然函数lg（L（θ|X））来实现求解和优化。

在数据缺失情况下，期望最大化算法是进行模型参数估计的一种有效手段^［35-37］。用Z=（X，Y）表示包含已观测数据集X以及未测数据集Y的数据全集，则集合Z与集合X分别被称为完全数据集和不完全数据集。

根据上述定义可以得到以下关系式，即

定义L（θ|Z）=L（θ|X，Y）=p（X，Y|θ）为完全数据似然函数，则式（1.1）中的L（θ|X）就表示不完全数据似然函数。不妨将完全数据似然函数L（θ|X，Y）视为数据集Y的函数^［38］，即

式中：f（Y|X，θ）为未测数据集Y在给定已观测数据集X和参数向量θ的条件下的边缘分布函数。

以上述定义为基础，可概括期望最大化算法处理未测数据的过程如下：

1）期望步，计算以下完全数据对数似然函数，即

式中：θ^t-1为t-1时刻参数的估计值；Ω为缺失变量y的取值范围。

2）最大化步，求使式（1.5）中的期望值Q（θ，θ^t-1）最大化的t时刻的参数估计值，即

通过对上述期望步和最大化步的迭代执行，就可搜寻到参数θ的局部最优解^［39］。

此外，通过聚类算法消除影响半监督学习效果的奇异点，并在期望最大化算法的初值设置中引入优化，可显著提高半监督学习对数据结构挖掘的精确度^［40］。将半监督学习的误差估计与未标记样本的学习同时进行，而将误差估计值也作为调整分类器参数的依据，得到一种扩展型期望最大化半监督学习方法^［41］。通过引入广义贝叶斯理论，采用期望最大化算法对混合模型的参数进行调整，提出另一种改进的半监督混合模型方法^［42］。Constantinopoulos等^［43］提出的概率径向基函数神经网络，在每次迭代过程中都基于期望最大化算法进行半监督学习，可达到比监督型神经网络更理想的学习效果。

（2）协同训练半监督学习方法

协同训练（Co-training）是另外一种流行的半监督学习方法。协同训练隐含地利用聚类假设或流形假设。通常使用两个或多个分类器，在学习过程中，这些分类器挑选若干个置信度高的未标记样本进行相互标记，从而使得模型得以更新。协同训练已运用到文本分类、英语基本名词及短语识别、情感分类、共指消解等研究上，而且取得了不错的效果，甚至超过了传统的有监督学习方法。协同训练方法最大的优点是不用人工干涉，即可从未标注的数据中自动学习到知识。

协同训练算法（或称标准协同训练算法）^［44］假设数据集具有两个充分且冗余（Sufficient and Redundant）的视图（View），即两个满足充分和冗余条件的属性集。首先，每个属性集都足以单独描述该问题，在训练量足够的前提下，每个属性集上都足以建立起一个强的分类器；其次，对于给定标记，两个属性集满足条件独立假设。在此基础上，协同训练算法的基本思想是：基于标记样本的两个不同视图（View）分别训练得到一个分类器，在之后的协同训练过程中，一个分类器从未标记样本中选出一些标记置信度较高的样本并进行标记，再把标记后的样本作为标记样本加入另一个分类器的训练集中，而获得新样本的分类器则利用这些新标记进行重新训练。协同训练过程不断重复进行，直到最后达到某个停止条件。

在协同训练中，当视图的充分冗余性条件成立时，分类器的性能可以通过标准协同训练算法得到显著提升^［45］。然而在很多实际应用中，充分冗余视图的条件可能很难达到。为解决该问题，需要设计不需要充分冗余视图条件支持的协同训练方法。其中一种不需要充分冗余视图的协同算法^［46］是：利用不同的决策树算法，基于同一个属性集训练得到两个不同的分类器，这两个分类器都能将样本空间划分为若干个等价类。在之后的协同训练过程中，这两个分类器通过统计方法来估计标记的置信度，并且选取置信度最高的样本标记提供给另一个分类器作为有标记训练例，更新对应分类器。这一过程反复进行，直到最后达到停止条件。在测试阶段，该算法首先对两分类器为未标记样本所做标记的置信度进行估计，然后选取置信度较高的分类器进行预测。该算法的性能已通过试验进行验证，且经过扩展后可使用多个不同种类的分类器。但该算法的计算时间消耗较大，且鲁棒性不高。

另一方面，有理论证明^［47］：只要两个分类器具有明显的差异，就能通过协同训练来有效利用未标记样本以提高学习性能。这说明当两个视图的条件独立性不成立时，采用具有明显差异的两个分类器的协同训练算法仍能取得较好的效果。

三重训练方法也是一种不需要充分冗余视图条件支持的协同训练方法^{［48，49］}，该方法既不需满足充分冗余性条件，也不需使用具有差异性的分类器，因此进一步放松了协同训练的约束条件。三重训练方法使用3个分类器，使标记置信度更易估计，未标记样本的类别也更容易预测，而集成学习（Ensemble Learning）^［50］的引入则能进一步提高算法的泛化性。三重训练方法首先对有标记样本集进行可重复采样（Bootstrap Sampling）从而得到3个有标记的训练集，然后基于每个训练集分别生成一个分类器。在之后的协同训练过程中，各分类器所用到的新标记样本都是通过其余两个分类器协作提供。具体做法是，当两个分类器对同一个未标记样本的预测相同时，认为该样本的标记具有较高的置信度，将该样本加入第三个分类器的训练集。预测过程中，采用投票的方式综合3个分类器的预测结果，来判断未标记样本的类别。集成学习的优势通过不同分类器的整合得以发挥。三重训练方法区别于以往协同训练算法的一个关键是，它根据3个分类器预测结果的一致性来隐式地比较不同未标记样本的标记置信度，从而避免统计测试技术的频繁使用，较大程度降低了运算量。然而与直接估计标记置信度的方法相比，这种隐式比较常常表现得不够准确，特别是对于分类器初始准确性较低的情况，如果未标记样本被错误标记，就可能给第三个分类器的训练引入噪声。针对这一问题，根据噪声学习理论^［51］可推导出以较高概率保证隐式处理方法效果的条件，即如果大部分未标记样本的标记是准确的，少量噪声所造成的干扰就会被大量未标记样本所包含的有效信息所抵消^［48］。如果要进一步减轻噪声的影响，就需要采用一些更可靠的误差估计技术，然而这是以增加算法运算量和存储空间占用率为代价的。在三重训练算法的基础上，进一步扩展得到的Co-forest算法^［52］，更好地发挥了集成学习的作用。

（3）最大化分离半监督学习方法

最大化分离半监督学习方法（也称最大间隔分割半监督学习方法）是一种利用聚类假设中的低密度分割思想的半监督学习算法。在该算法中，未标记数据起到探索数据分布的稠密和稀疏区域的作用，并使决策边界出现于低密度数据区，保证不同类别的数据用最大的间隔（Maximum Margin）分割开来。基于支持向量机（Support Vector Machine，SVM）、高斯过程（Gaussian Process，GP）^［53］、信息正则化^［54］及最小化熵^［55］的半监督学习均属于最大化分离半监督学习方法。直推式支持向量机（Transductive Support Vector Machine，TSVM）^［27］是最早提出的也是最具代表性的一种最大化分离半监督学习方法，以下以直推式支持向量机为例对最大化分离半监督学习方法进行详细介绍。

在监督学习方法中，支持向量机只利用已标记样本在数据空间中构造一个最优超平面，使得两类样本具有最大分类间隔，而在半监督学习中，样本集中既有已标记样本又有未标记样本，因而数据间隔难以得到确切的描述，这就需要对问题进行适当的松弛，一般是通过施加一个弱约束条件来实现。直推式支持向量机在构造最优分类超平面时将未标记样本也考虑进来，使得原始的标记样本和未标记样本均以最大的间隔被分离，同时最优分类边界在对原始未标记样本分类时应具有最小泛化误差。

由于有效利用了隐含在未标记样本中的分布特性信息，直推式支持向量机的分类效果比单纯基于标记样本的传统支持向量机分类效果有了显著提高，然而直推式支持向量机本身仍然有需改进的地方。对于二分类问题，样本类别标记有正标记和负标记两种，直推式支持向量机在执行前要求人工设定未标记样本中的具有正标记的样本个数K，而在实际过程中很难准确给出K值的估计。在直推式支持向量机中K值的估算通常采用一种简单的方法实现，即由正标记样本在标记样本中所占比例来对K值进行估计。这种做法在标记样本集规模较小的条件下很可能导致较大的估计误差，而当K的估计值与真实的正标记样本个数相差较大时，分类器性能将迅速下降。从另一个角度来说，由于有标记样本通常是经人工处理和选取的，而不是随机采样获得的，因此根据其标记分布来估计整个样本集中正负标记的大致比例是不合理的。即使随机选取得到有标记样本，由于直推式向量机能用到的有标记样本集规模往往较小，据其对样本全集分布的估计也常常是不准确的。对K值的错误估计，将导致直推式支持向量机产生一个无法正确反映样本分布特性的分类器。直推式支持向量机的实用价值在很大程度上被这一缺陷所限制。在基本直推式支持向量机基础上，渐进直推式支持向量机（Progressive Transduetive SVM，PTSVM）^［56］有效解决了K值难以估计的问题。渐进直推式支持向量机在进行训练之前，并不估计未标记样本的分布特性，而是在训练过程中，每次选择1～2个可能对后续训练过程造成较大影响的未标记样本，标以当前条件下最可能的类标，并将其归入到有标记样本集，再重新进行下一轮的训练。一般情况下，新样本的加入会影响到新一轮的训练过程，并使当前分割平面发生些许偏移。在每一次训练中，可能会发现先前的部分标记是不合适的，这时则需要取消这些不合适的标记，将其恢复为未标记的状态。

直推式支持向量机作为一种最大化分离半监督学习方法，受到国内外研究学者越来越多的关注，成为半监督学习的一个代表性方法。Bruzzone等^［57］将二值分类的直推式支持向量机推广到多值分类问题，并将直推式支持向量机成功应用于复杂遥感图像的地物分类问题。Zhang等^［58］提出一种最小二乘直推式支持向量机，即对传统直推式支持向量机的目标函数由非凸函数向凸函数转换，以简化直推式支持向量机的求解过程，同时带来性能上的提升。Li等^［59］以直推式支持向量机为基础提出一种迭代式半监督支持向量机，通过特征重提取，成功解决了对未标记样本的学习过程中的误差累积问题。Adankon等^［60］结合遗传算法来求解直推式支持向量机使用的非凸目标函数的优化问题，进一步提升了直推式支持向量机的分类精度。此外，一些学者尝试在直推式支持向量机中引入包括半正定规划（Semi-definite Programming）、局部组合搜索（Local Combinatorial Search）、梯度下降（Gradient Descent）、延拓技术（Continuation Techniques）、凸凹过程（Convex-concave Procedures）、确定性退火技术（Deterministic Annealing）以及不可微分方法（Non-differentiable Methods）在内的多种优化技术来提升半监督学习的性能^［61-63］。

（4）基于图的半监督学习方法

基于图的半监督学习方法直接或间接地利用流形假设，在学习过程中首先基于训练样本的特定相似度度量建立图，图中各节点对应（有标记或是未标记）样本，节点间的连接表示样本间的相似度，之后定义模型的优化目标函数，并根据图的平滑性，添加相应的正则化项得到决策函数，通过最小化决策函数计算模型参数的最优值。

基于图模型的半监督学习方法中较有代表性的方法有Mincut方法^［64］、Tikhonov正则化方法^［65］、马尔可夫随机漫步法（Markov Random Walk）^［66］、图-核方法（Graph Kernels）^{［67，68］}和流形方法（Manifold Method）^［69］等。其中流形方法在近年来受到较为广泛的关注。流形方法认为，分类边界在子流形上可以比在原空间中更为容易识别，基于此设想，流形方法把处于高维空间的样本映射到低维流形上以达到简化分类的目的。流形学习方法是一种非参数方法，即对流形的参数不需要进行先验假设。目前基于流形的半监督学习方法主要包括谱映射（Spectral Projection）方法^［70］、基于局部和全局一致性（Local and Global Consistency）的方法^［71］、基于高斯域和调和函数（Gaussian Fields and Harmonic Functions）的方法^［72］以及黎曼流形最小误差映射（Riemannian Manifolds and Mapping for Minimum Error Sum）方法^［73］等。这些基于流形的半监督学习方法在低维映射过程中，都会事先设定一个能量函数来确认低维空间比原空间具有更加突出的类别分界线。基于流形的半监督学习方法所采用的能量函数，可以统一表示为

式中：t为样本在低维流形上的坐标值（或者是样本的类别标记）；E（t）为t坐标值上的能量函数；w_ij为图模型中各个样本点间连接的权值；i和j为第i个和第j个样本；N为样本个数。

以极小化E（t）为优化目标，该映射过程的含义是，在原样本空间内距离较近的样本点投影到低维流形上也应该相互接近，即应趋于相同的类标。近年来，基于图模型的半监督学习方法得到了越来越多相关学者的关注。Camps-Valls等^［67］通过流形半监督学习从高光谱遥感图像中发掘出了未标记样本的类别特征信息，并且成功地克服了高光谱遥感图像分类中存在的不适定问题。Kulis等^［74］结合核聚类算法与图模型，利用基于图的半监督分类方法实现了对向量数据和图形数据的同时处理。构建合理的图模型权值矩阵是基于图的半监督学习方法的关键，针对这一关键问题Yang等^［75］提出一种子空间半监督学习框架，该框架使得图模型的权值矩阵的求解更容易，这种框架方法已成功应用于降维问题中。Zhong等^［76］提出的基于图模型的半监督学习方法，将若干图模型整合为统一框架，很好地解决了半监督特征选择中存在的未标记样本利用效率低的问题。Rohban等^［77］提出一种新的方法来对半监督图模型中边权值进行更新，该方法能有效降低个别强势节点对相邻节点的不良影响，并实现半监督图模型的整体性能的优化。Wang等^［78］指出大部分基于图的半监督学习方法仅以距离作为样本点之间相似性的唯一判断标准的做法会导致严重的分类误差，在基于图的半监督分类方法中引入近邻相似性测量（Neighborhood Similarity Measure）技术，该技术使得半监督学习方法在充分考虑到样本间距离相似性的同时，考虑局部分布的差异性，从而能有效提高基于图模型的半监督学习方法的分类精度。