基于支持向量机的渐进直推式分类学习

基于支持向量机的渐进直推式分类学习陈毅松，汪国平，董士海北京大学计算机系人机交互与多媒体实验室，100871摘要：支持向量机（SupportVectorMachine）是近年来在统计学习理论的基础上发展起来的一种新的模式识别方法，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势。直推式学习（transductiveinference）试图根据已知样本对特定的未知样本建立一套进行识别的方法和准则。较传统的归纳式学习方法而言，直推式学习往往更具普遍性和实际意义。本文提出了一种基于支持向量机的渐进直推式分类学习算法，在少量有标签样本和大量无标签样本所构成的混合样本训练集上取得了良好的学习效果。关键词：支持向量机，直推式学习。1引言基于结构化风险最小化方法的统计学习理论是一种专门的小样本统计理论，它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架，同时也发展了一种新的模式识别方法－支持向量机（SupportVectorMachine，简称SVM）[1][2][3]。统计学习理论和支持向量机方法能够对有限样本情况下模式识别中的一些根本性问题进行了系统的理论研究，并且在此基础上建立了一种较好的通用算法。以往困扰很多机器学习方法的问题，比如模型选择与过学习问题、非线性和维数灾难问题、局部极小问题等，在这里都得到了很多程度上的解决。因此，统计学习理论和支持向量机是机器学习领域的一个重要分支，已经得到了日益广泛的重视。虽然统计学习理论有比较坚实的理论基础和严格的理论分析，但是其中从理论到应用都还有很多尚未得到充分研究和解决的问题。例如，目前该领域的相关研究大多是试图设计某种分类器，使其对未来所有可能样本的预期性能最优，而在很多实际问题中，没有可能也没有必要用这样一个分类器对所有可能的样本进行识别，而往往只需要对一些特定的样本进行识别，于是可以考虑设计这样一种更为经济的分类器，用它来建立一种直接从已知样本出发对特定的未知样本进行识别和分类的方法和原则。相对于传统的归纳和演绎推理，这种推理方式在文献[4]中被称为直推（Transductiveinference）。统计学习领域的直推式学习是一个较新的研究领域，目前已经有了一些初步的研究成果[5][6]。本文是对直推式学习的进一步研究，试图寻找一个较已有的方法更为普遍和通用的直推式学习算法。本文在详细论述直推式学习思想的基础上，基于支持向量机分类的固有特点，设计了一个支持渐进直推式学习算法的支持向量机分类器，该分类器所使用的渐进判别法充分利用了支持向量机的最优超平面分割特性，能够在训练过程中有效地对无标签样本循序渐进地作出判别分类，并具有一定的差错修复能力。同时，通过直推式学习，有效地优化了原始分类器的分类性能，得到了较直接进行归纳式学习好得多的测试结果。本文以下部分的结构组织是这样安排的。第2节简单介绍了支持向量机分类算法的原理和实现；第3节介绍了直推式学习的概念、用途和研究现状，并重点描述了T.Joachims的直推式支持向量机分类算法；第4节结合支持向量机分类器的特点提出了渐进直推式支持向量机学习算法PTSVM，给出了具体实现步骤和算法有效性的证明；第5节给出了算法的实验结果并作了详细的分析；第6节总结全文，并指出了进一步研究的方向和思路。2支持向量机理论简述V.Vapnik提出的支持向量机理论[1]因其坚实的理论基础和诸多良好特性在近年获得了广泛的关注。已经有许多事实证明，作为支持向量机最基本思想之一的结构化风险最小化原则（StructuralRiskMinimization,SRM）要优于传统的经验风险最小化原则（EmpiricalRiskMinimization,ERM）。不同于ERM试图最小化训练集上的误差的做法，SRM试图最小化VC维的上界，从而使其学习机获得了更好的推广性能，这恰恰是统计学习理论最重要的目标之一。支持向量机的主要应用领域有模式识别、函数逼近和概率密度估计等等，本文的讨论重点是使用支持向量机进行二值分类的问题。图1特征空间中的最优分割平面如图1，考虑一个用某特征空间的超平面对给定训练数据集做二值分类的问题。对于给定样本点：}1,1{,),,(,),,(11inillyRxyxyx（1）其中向量ix可能是从对象样本集抽取某些特征直接构造的向量，也可能是原始向量通过某个核函数映射到核空间中的映射向量。在特征空间中构造分割平面:0)(bxw（2）使得：1])[(11)(11)(bxwyyibxwybxwiiiii),,2,1(li（3）可以计算出，训练数据集到一给定的分割平面的最小距离为：||2||max||min),(}1|{}1|{wwbxwwbxwbwpiyxiyxiiii（4）根据SVM对优化分割平面的定义，可以看出对该平面的求解问题可以简化为：在满足条件式（3）的情况下，计算能最大化),(bwp的分割平面的法向量w和偏移量b。Vapnik等人证明：分割超平面的法向量0w是所有训练集向量的线性组合。即0w可以描述为：liaxyawiiilii,,1),0()(0100（5）定义判别函数00)(bxwxf（6）则测试集的分类函数可以描述为：)())(sgn()(00bxwsignxfxlabel（7）由（3）式可知，在线性可分的情形下，对所有的训练样本都应该满足1)(xf，在下文中，我们把满足1)(xf的区域称为分割超平面所对应的边界区域。在多数情况下（5）式0w的展开式中，系数0ia为零值，而非零值的0ia对应的ix就称为支持向量SV。这些向量充分描述了整个训练数据集数据的特征，使得对SV集的线性划分等价于对整个数据集的分割。由（4）式可见，最优分割平面的求解等价于在（3）式约束下最大化下面的（8）式221)(ww（8）引入拉格朗日乘子lii,...,2,1,，并定义liiiixyw1)(（9）使用Wolfe对偶定理把上述问题转化为其对偶问题：ya,αsubjecttow(αw(ααMaxW(iiiiii00))21)（10）对于线性不可分的训练集，可以引入松弛变量i，把（8）式改写为下面的求解问题[3]。0,1)()21(2iiiiiibxwySubjecttoξCwMin(11)类似的可以得到相应的对偶问题：yaC,αsubjecttow(αw(ααMaxW(iiiiii00))21)（12）形如式（10）、（12）的求解是一个典型的有约束的二次型优化问题，已经有了很多成熟的求解算法，近年来，V.Vapnik,C.Burges,E.Osuna,T.Joachims,J.Platt等人的一系列工作使得对大规模训练集的支持向量机算法实现成为可能[7-11]。3直推式学习直推式学习概念的提出主要源于以下两个事实[12][13]：首先，在大量机器学习的实际应用中，获得加标签的训练样本常常需要较大的人力物力的代价，因此，学习机所能得到的有标签的训练样本往往是有限的。相反，常常能够很容易地获得大量无标签的样本。Web页面的分类工作是一个典型的例子，在这样一个应用中，对已有的Web页面作手工的或半自动的标注往往是烦琐而乏味的，但是却可以很容易地获得数以千计的未标注的Web页面。由于能够获得的有标签的训练样本较少，所以常常不能很好地刻画出数据的总体分布特性，因而直接采用有标签样本进行学习得到分类器性能往往欠佳。能否利用可以轻易获得的无标签样本来对其性能加以改进呢？这就很自然地产生了一个如何用少量的有标签样本和大量的无标签样本训练出一个较好的学习机的问题。其次，在传统的归纳式学习中，学习机试图根据已有的有标签训练样本归纳出一个判别函数，使得它对可能的整个样本空间分布有一个尽可能小的期望判别误差。然而在许多实际问题中，我们的目的仅仅是对一些特定的样本进行识别和分类，希望能够对这一特定测试集获得误差尽可能小的分类。如果把这一特定测试集有机地加入到分类器的设计和训练过程中，则不但可以对这一特定测试集获得获得良好的分类效果，而且可以在很大程度上提高原有归纳式学习算法的推广性能，弥补了归纳式学习算法因训练数据过少而带来的不足。这就是直推式学习的基本思想。在直推式学习中，学习机在训练过程中使用较少的有标签样本和较多的无标签样本进行学习。直推式学习的一个重要特色就在于在这样一种混合样本的学习过程中，测试集的样本分布信息从无标签样本转移到了最终的分类器中。由于无标签样本的数量较多，所以能够较有标签样本更好地刻画整个样本空间上的数据特性，从而使训练出的分类器具有更好的推广性能。直推式学习在模式识别的各个领域都已经有了不同程度的研究和应用[14][15]。有关基于支持向量机的直推式学习算法的研究尚处在起步阶段，目前最主要的研究成果是T.Joachims的直推式支持向量机（TSVM）。下面将简单地介绍一下TSVM的算法原理和实现。具体的描述和证明参见文献[6]。给定一组独立同分布的有标签训练样本点}1,1{,),,(,),,(11iminnyRxyxyx（13）和另一组来自同一分布的无标签样本点**3*2*1,...,,,kxxxx（14）在一般的线性不可分条件下，T.Joachims的直推式向量机的训练过程可以描述为以下的优化问题：0:0:1:1:21),...,,,...,,,,,...,(*11**111**12**11**1jkjinijjjkjiiinikjjniiknkbxwybxwy:tosubjectCCwbwyyoverMinimize(15)其中参数C和*C为户指定和调节的参数。与式（11）中的参数C作用类似。我们把参数*C称作是无标签样本在训练过程中的影响因子，**jC称为无标签样本j在目标函数中的影响项。TSVM的训练过程也就是求解上述优化问题的过程。训练算法大致可以分为以下几个步骤：步骤1，指定参数C和*C，使用归纳式学习对有标签样本进行一次初始学习，得到一个初始分类器。并按照某个规则指定一个无标签样本中的正标签样本数N步骤2，用初始分类器对无标签样本进行分类，根据对每一个无标签样本的判别函数输出，对输出值最大的N个无标签样本暂时赋正标签值，其余的赋负标签值。并指定一个临时影响因子tmpC*步骤3，对所有样本重新训练，对新得到的分类器，按一定的规则交换一对标签值不同的测试样本的标签符号，使得优化问题（14）中的目标函数值获得最大下降。这一步骤反复执行，直到找不出符合交换条件的样本对为止。步骤4，均匀地增加临时影响因子tmpC*的值并返回到步骤3，当**CCtmp时，算法结束，并输出结果。步骤3中的标签符号交换保证了交换后的解优于交换前的解，而步骤4中的临时影响因子由小到大逐步递增则试图通过逐渐增加无标签样本对算法的影响的办法来追求尽可能小的对无标签样本的分类误差。由于步骤1中指定的*C是有限的，由步骤4中的结束准则可知，算法能够在有限次执行后终止并输出结果。4一种新的渐进直推式支持向量机学习算法由于成功地把无标签样本中所隐含的分布信息引入了支持向量机的学习过程中，TSVM算法比单纯使用有标签样本训练得到的分类器在性能上有了显著提高。但是TSVM算法本身仍然存在着一些不足和值得进一步改进的方面。TSVM算法的一个主要缺陷在于，在算法执行之前必须人为指定待训练的无标签样本中的正标签样本数N，而在一般情况下N值是很难做出比较准确的估计的，在TSVM算法中采用了一种简单的方法，即根据有标签样本中的正标签样本所占比例来相应估计无标签样本中的正标签样本比例，进而估计出N值。不难看出，这一方法在有标签样本数较少的情况下很容易导致较大的估计误差，一旦事先设定的N值和实际上的正标签样本数相差较大，就会导致学习机性能的迅速下降。例如，一种常见的情况是，在有标签样本中正负标