半监督支持向量机综述-LAMDA-南京大学

半监督支持向量机综述年素磊(南京大学计算机科学与技术系,南京210093)Semi-supervisedSupportVectorMachinesSurveySu-LeiNian*(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:SupportvectormachineasamachinelearningmethodaimedatsmallsamplesisdevelopedbyVapnikandothersinthebasisofstatisticallearningtheory.Ithasbeenwidelyresearchedandappliedforitsadvantageofstronggeneralizationabilityandconvenientforhighdimensiondataoperation.Thoughstandardsupportvectormachinebasedonsupervisedlearningcanresolvemanyactualproblemseffectively,ithavetolabelmassunlabeleddatainordertogetenoughtrainingsamples.Itmakesthesemethodscostlyandlowefficiency.Sosemi-supervisedsupportvectormachinesareproposedaccordingtotheactualrequirement.Overthepastdecade,manyimprovedversionsareproposedtosolveeverydifferentspecificproblemofsemi-supervisedsupportvectormachines,forexample:totheinefficiencyissue,meanS3VMisintroduced;toperformancedegenerateproblem,S4VMisproposed;andtocostsensitiveissue,CS4VMemerges.Keywords:semi-supervisedsupportvectormachine;statisticallearningtheory;inefficiency;performancedegenerate;costsensitive摘要:支持向量机是Vapnik等在统计学习理论基础上发展起来的针对小样本的机器学习方法。该方法由于具有较强的泛化能力、方便对高维数据操作而得到了日益广泛的研究和应用。标准的支持向量机是基于监督学习的，虽然能有效地解决各种实际问题，但需要手工对大量样本进行标记以获取足够的训练样本，代价高，效率低。因此根据实际需要研究人员又提出了半监督支持向量机。在过去的十年中，为了解决半监督支持向量机某一方面的特定问题，出现了很多改进版本，如针对半监督支持向量机效率低下的问题，提出了meanS3VM算法；针对利用无标记数据时会产生性能下降的问题，提出了S4VM算法；针对代价敏感的问题，提出了CS4VM算法。关键词:半监督支持向量机;统计学习理论;低效;性能下降;代价敏感中图法分类号:TP301文献标识码:A1引言随着计算机在日常生活的广泛应用，各行各业都积累了大量的数据。如何快速、准确、方便地从海量的信息库中获取感兴趣、满足需要的信息，已成为人们亟待解决的问题。在各种复杂应用背景条件下，人工方作者简介:年素磊南京大学计算机系2011研究生2式不可能处理如此庞大的信息，机器学习方法就显得尤为重要。机器学习方法是从观测样本出发，寻找这些数据中蕴含的规律，利用这些规律对未知数据或者无法观测的数据进行预测。但真实应用中收集到的观测样本大多是没有类别标记的，因为对样本进行类别标记往往需要耗费大量的人力物力。显然，如果只使用少量的有标记样本进行训练，一方面利用它们所训练出的学习系统往往很难具有强泛化能力；另一方面，如果只使用少量“昂贵的”有标记的样本，而不利用大量“廉价的”无标记样本，也是对数据资源的一种极大的浪费。因此，在有标记样本较少时，如何使用大量无标记样本来改善学习性能已成为人们关注的问题，半监督学习算法正是为了解决这一问题而提出的。支持向量机是20世纪90年代以后逐步发展起来的一种基于统计学习理论的机器学习方法，坚实的理论基础使其成功地解决了机器学习中普遍存在的“维数灾难”和“过学习”问题，并具有良好的推广能力，已经在许多实际工程领域中展示了良好的应用前景。但标准的支持向量机算法都为监督学习，如果能把半监督学习思想引入支持向量机中，将会弥补标准支持向量机的缺陷，获得更好的分类效果，拓展支持向量机的应用领域。本报告正是对半监督支持向量机的原理、算法和扩展进行了综述。2半监督支持向量机原理、算法与扩展2.1分类问题和分类机在许多真实的生活场景中，我们都需要依据一个物体的属性，把它划分到几个类别中的一个里。例如依据病人的一些医学测试的结果，我们希望判断其是否有某种疾病，或者是否应该接受某种治疗。在计算机科学中，这样的情况就被描述为分类问题。用数学的语言可以把分类问题描述如下：分类问题给定训练集11{(,),,(,)}(),nlllTxyxyRy其中,{1,1},1,.niixRyyilix是特征向量，其分量是从物体中提取的特征或属性；iy是相应的类别标记（1和-1分别表示正类和负类）。据此寻找nR空间上的一个实值函数()gx，以便使用决策函数()sgn(())fxgx推断任一输入x对应的输出y。由此可见，求解分类问题，实质上就是找到一个把nR空间分成两部分的规则，或称其分类机。这里我们说的分类问题其实是二类别的问题，多类别的问题原理相同，本报告只考虑二类别问题。2.2SVM在众多的分类方法中，支持向量机（SVM）是非常流行的一种，它被广泛地应用在诸如文本分类，面部表情识别，和基因分析等多种应用中[2]。下面我们详细介绍支持向量机（SVM）的原理。2.2.1线性可分的情况首先我们讨论数据是线性可分的情况，线性可分意思就是训练集能用一个超平面完全正确地分开。这个超平面可以描述成0bwx，这里w垂直于超平面bw是原点到超平面的垂直距离3图1[1]分划直线将线性可分的两类数据分开图1为一个二维空间上的分类问题，白色的点为类别1的点，黑色的点为类别2的点。首先假定分划直线0bwx的法方向w已经给定，如图1中的w。这时直线就是一条以w为法方向且能够正确分划两类点的直线，显然，这样的直线不唯一，我们还可以平行地向右上方或左下方推移直线，直到碰到某个训练点的输入。这样就得到了两条极端的直线（图1中的两虚线），这两条直线称为支持直线。在两条支持直线之间的平行直线都能正确分划两类点，它们都作为候选分划直线。显然，在这些候选分划直线中，恰好位于两虚线中间的那条直线为最好，即d1=d2[8]。但如何选取分划直线的法方向w呢？这里我们称两条支持直线之间的距离为与该法方向相应的“间隔”（d1+d2），支持向量机的思想就是选取的法方向应使“间隔”达到最大。那么我们就可以根据上述思想把寻求分划直线0bwx的问题转化为对w，b的最优化问题。适当地选取w和b，我们可以将两条支持直线表示为1bwx和1bwx与此相应的分划直线的表达式为0bwx直接计算可知，此时相应的两条支持直线的距离为2w，即相应的“间隔”为2w。最大化“间隔”的思想导致求解下列对变量w和b的最优化问题2,12..(())1,1,,minwbiiwstywxbil上式中约束条件为分划直线必须能将两个类别的样本正确分开。具体求解上述优化问题时，我们可以通过引入Lagrange函数，来求解它的对偶问题1111..1min()20,0,1,,lllijijijjijjliiiistyyxxyil4解得***1(,,)Tl后，再计算**1liiiiwyx，然后选取*的一个正分量*j，据此计算**1()ljiiijibyyxx由此求得决策函数()sgn(())fxgx其中****1()()()liiiigxwxbyxxb由上述()gx的表达式可以看到，决策函数只依赖于训练集T中对应于正的*i的那些训练点，而其他的训练点都不起作用。由于这些训练点位于支持直线上，我们称其为支持向量，这也是称此方法为支持向量机的原因[10]。2.2.2线性不可分的情况上面讨论的是数据线性可分的情况，但在一般情况下，数据可能是线性不可分的，所以我们要放松限制条件，以便允许错误的分类。这可以通过引入一个正的松弛变量,1,iil得到：11110,1,iiiiiiiwxbforywxbforyil这样我们在找最优的分划直线时，就既要最大化间隔，又要控制错分类的数量。相应的最优化问题表示为2,,112..(())10,1,,minliwbiiiiiwCstywxbil其中C是个惩罚因子，用来平衡错分类的数量和模型的复杂度。具体求解过程和线性可分的情况类似，这里不再赘述。2.3S3VM2.3.1半监督学习传统的机器学习技术分为两类，一类是无监督学习，一类是监督学习。无监督学习只利用未标记的样本集，而监督学习则只利用标记的样本集进行学习。但在很多实际问题中，只有少量的带有标记的数据，因为对数据进行标记的代价有时很高，比如在生物学中，对某种蛋白质的结构分析或者功能鉴定，可能会花上生物学家很多年的工作，而大量的未标记的数据却很容易得到。这就促使能同时利用标记样本和未标记样本的半监督学习技术迅速发展起来[9]。2.3.2半监督支持向量机在众多的半监督学习方法中，半监督支持向量机（S3VM）是非常流行的一个，它基于聚类假设，试图5通过探索未标记数据来规范、调整决策边界。为了利用未标记的数据，我们需要在原来的支持向量机（SVM）的基础上，添加两个对未标记的数据点的限制。一个限制是假设未标记的点是属于类别1的，然后计算它的错分率；另一个限制是假设此点是属于类别2的，同样计算它的错分率。目标函数则计算这两个可能的错分率中小的那个[3]。所以，半监督支持向量机(S3VM)可以定义如下,,,,11min(,)..(())10,1,10,1,,()10minllkijjwbzijliiiijjjjjjwCzstywxbilwxbjllkwxbzz同样C是一个错误率的惩罚因子。2.4TSVM直推式支持向量机（TSVM）与半监督支持向量机（S3VM）在同一年提出，且算法主要的思想和要求解的优化问题类似，所以人们提到这两个概念时通常是可以互换的。不同点在于TSVM是在文本分类的背景下提出的，更强调直推式的概念。通常的支持向量机(SVM)都是归纳式的，它们试图为一个分类任务归纳出一个一般的决策函数，以便对新来的样本能正确分类。而直推式支持向量机只考虑一个特定的测试数据集，试图最小化这个测试集上的错分率，而不考虑一般的情况[4]。半监督支持向量机（S3VM）刚提出时也是做为直推式的，主要用来对未标记的样本的类别进行直接估计，但它还在整个输入空间中划出了一个决策边界，所以也可以提供对新来的样本的分类。2.5meanS3VM经过十来年的发展，半监督的支持向量机已经有了很多个版本，比较流行的除了前面介绍的S3VM和TSVM以外，还有LaplacianSVM。LaplacianSVM主要是通过图的拉普拉斯矩阵来探索数据的流形结构。它将已标记的和未标记的数据编码在一张连接图中，图的每一个节点代表一个数据点，如果两个数据点之间有很大