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

《基于支持向量机的渐进直推式分类学习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于支持向量机的渐进直推式分类学习陈毅松，汪国平，董士海北京大学计算机系人机交互与多媒体实验室，100871摘要：支持向量机（SupportVectorMachine）是近年来在统计学习理论的基础上发展起来的一种新的模式识别方法，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势。直推式学习（transductiveinference）试图根据已知样本对特定的未知样本建立一套进行识别的方法和准则。较传统的归纳式学习方法而言，直推式学习往往更具普遍性和实际意义。本文提出了一种基于支持向量机的渐进直推式分类学习算法

2、，在少量有标签样本和大量无标签样本所构成的混合样本训练集上取得了良好的学习效果。关键词：支持向量机，直推式学习。1引言基于结构化风险最小化方法的统计学习理论是一种专门的小样本统计理论，它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架，同时也发展了一种新的模式识别方法－支持向量机（SupportVectorMachine，简称SVM）[1][2][3]。统计学习理论和支持向量机方法能够对有限样本情况下模式识别中的一些根本性问题进行了系统的理论研究，并且在此基础上建立了一种较好的通用算法

3、。以往困扰很多机器学习方法的问题，比如模型选择与过学习问题、非线性和维数灾难问题、局部极小问题等，在这里都得到了很多程度上的解决。因此，统计学习理论和支持向量机是机器学习领域的一个重要分支，已经得到了日益广泛的重视。虽然统计学习理论有比较坚实的理论基础和严格的理论分析，但是其中从理论到应用都还有很多尚未得到充分研究和解决的问题。例如，目前该领域的相关研究大多是试图设计某种分类器，使其对未来所有可能样本的预期性能最优，而在很多实际问题中，没有可能也没有必要用这样一个分类器对所有可能的样本进行识别，而往往只需要对一些特定的样

4、本进行识别，于是可以考虑设计这样一种更为经济的分类器，用它来建立一种直接从已知样本出发对特定的未知样本进行识别和分类的方法和原则。相对于传统的归纳和演绎推理，这种推理方式在文献[4]中被称为直推（Transductiveinference）。统计学习领域的直推式学习是一个较新的研究领域，目前已经有了一些初步的研究成果[5][6]。本文是对直推式学习的进一步研究，试图寻找一个较已有的方法更为普遍和通用的直推式学习算法。本文在详细论述直推式学习思想的基础上，基于支持向量机分类的固有特点，设计了一个支持渐进直推式学习算法的支持

5、向量机分类器，该分类器所使用的渐进判别法充分利用了支持向量机的最优超平面分割特性，能够在训练过程中有效地对无标签样本循序渐进地作出判别分类，并具有一定的差错修复能力。同时，通过直推式学习，有效地优化了原始分类器的分类性能，得到了较直接进行归纳式学习好得多的测试结果。本文以下部分的结构组织是这样安排的。第2节简单介绍了支持向量机分类算法的原理和实现；第3节介绍了直推式学习的概念、用途和研究现状，并重点描述了T.Joachims的直推式支持向量机分类算法；第4节结合支持向量机分类器的特点提出了渐进直推式支持向量机学习算法PT

6、SVM，给出了具体实现步骤和算法有效性的证明；第5节给出了算法的实验结果并作了详细的分析；第6节总结全文，并指出了进一步研究的方向和思路。2支持向量机理论简述V.Vapnik提出的支持向量机理论[1]因其坚实的理论基础和诸多良好特性在近年获得了广泛的关注。已经有许多事实证明，作为支持向量机最基本思想之一的结构化风险最小化原则（StructuralRiskMinimization,SRM）要优于传统的经验风险最小化原则（EmpiricalRiskMinimization,ERM）。不同于ERM试图最小化训练集上的误差的做法

7、，SRM试图最小化VC维的上界，从而使其学习机获得了更好的推广性能，这恰恰是统计学习理论最重要的目标之一。支持向量机的主要应用领域有模式识别、函数逼近和概率密度估计等等，本文的讨论重点是使用支持向量机进行二值分类的问题。图1特征空间中的最优分割平面如图1，考虑一个用某特征空间的超平面对给定训练数据集做二值分类的问题。对于给定样本点：（1）其中向量可能是从对象样本集抽取某些特征直接构造的向量，也可能是原始向量通过某个核函数映射到核空间中的映射向量。在特征空间中构造分割平面:（2）使得：（3）可以计算出，训练数据集到一给定的

8、分割平面的最小距离为：（4）根据SVM对优化分割平面的定义，可以看出对该平面的求解问题可以简化为：在满足条件式（3）的情况下，计算能最大化的分割平面的法向量和偏移量。Vapnik等人证明：分割超平面的法向量是所有训练集向量的线性组合。即可以描述为：（5）定义判别函数（6）则测试集的分类函数可以描述为：（7）由（3）式