支持向量机综述

上海大学2013～2014学年冬季学期研究生课程考试小论文格式课程名称：模式识别方法课程编号：09SB59004论文题目:支持向量机原理及应用研究生姓名:章云元学号:13721278论文评语:成绩:任课教师:李昕评阅日期:支持向量机原理及应用学号：13721278姓名：章云元日期：2014.03.07摘要：支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效的解决多类分类问题，如何解决支持向量机二次规划过程中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。本文详细介绍系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等。关键词：机器学习；统计学习理论；SVM；VC维；TheprincipleandapplicationofSupportVectorMachineABSTRACT：SVM(SupportVectorMachine)isanovelmethodofmachinelearningevolvingfromStatistics.SVMpresentsmanyownadvantagesinsolvingmachinelearningproblemssuchassmallsamples,nonlinearityandhighdimension.However,SVMmethodsexistsomeproblemsneedtoberesolved,mainlyincludinghowtodealwithmulti-classificationeffectively,howtosolvethebottle-neckproblemappearinginquadraticprogrammingprocess,andhowtodecidekernelfunctionandoptimisticalkernelparameterstoguaranteeeffectivityofthealgorithm.Thispaperhasintroducedindetailthestructure,evolvementhistory,andkindsofclassificationofmachinelearning,anddemonstratedsystemSLT(StatisticalLearningTheory),SVMandresearchhotspotsofSVM,includingseekingSVMproblems,multi-classification,parametersoptimization,kernelfunctionselectionandsoon.Keywords:Machinelearning,SLT,SVM,VCdimension1.引言1.1支持向量机研究背景及意义随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问题，参数的选择和优化问题等。求解一个SVM问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问题的二次规划问题(QuadraticProgramming，QP)。传统的方法是利用标准二次型优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于SVM需要计算和存储核函数矩阵，当样本规模较大时必然导致内存需求增加；另一方面，SVM在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效率，如块算法、分解算法、SMO算法、增式算法等等。支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题，如船舰识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方法扩展到多类分类情况是支持向量机方法研究的重要内容之一。目前，用SVM解决多类分类问题方法主要是通过构造或组合多个两类分类器来实现多类问题的分类。子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两类分类问题。常用的算法有“one---against---one”方法、“one--against--rest”方法、“基于决策树的方法”等。支持向量机多类分类方法的引入拓展了支持向量机的应用范围，也加快了支持向量机方法的改进和创新，同时，支持向量机的核函数的选择以及核参数的选择也是一个重要的研究方向。2.支持向量机的原理支持向量机(SupportVectorMachine，SVM)是由Vapnik及其合作者共同创造与发展起来的一种新的机器学习方法，其核心内容在1992年至1995年间提出的。2.1统计学习理论统计学习理论建立在一套较为坚实的理论基础之上，为解决有限样本的学习问题提供了一个统一的框架。它能将许多现有的方法纳入其中，有望帮助解决许多原来难以解决的问题，比如神经网络的结构选择问题、局部最小点问题等。2.1.1机器学习问题机器学习问题[1]可以看作是通过某种训练方法，对某一系统的输入与输出之间的依赖关系进行估计，并且期望这一估计可以对任意给定输入尽量准确地进行输出预测。一般地，机器学习问题可以表示为：假设变量y与x之间存在一定的未知依赖关系，即遵循某一未知的联合概率,Fxy(x和y之间的确定性关系可以看作是其特例)，机器学习问题就是根据n个独立同分布观测样本1122,,,,...,,nnxyxyxy，在一组函数,fx中求一个最优的函数,afx对依赖关系进行估计，使得期望风险最小。,,,LRyfxdFxy2-(1)其中,fx称作预测函数集，为函数的广义参数，,fx可以表示任何函数集；,,Lyfx为由于用,fx对y进行预测而造成的损失，不同类型的学习问题有不同形式的损失函数。在上面问题的表述中，学习的目标在于使期望风险最小化，但是，由于可以利用的信息只有样本最初的观测样本1122,,,,...,,nnxyxyxy，因此，期望风险2-(1)是无法计算的。传统的学习方法是采用了所谓经验风险最小化(ERM)准则[11]，即用样本定义经验风险11,,nempiiiRLyfxn2-(2)来逼近3-(1)定义的期望风险，用对参数求经验风险empR的最小值代替求期望风险R的最小化，这就是所谓的经验风险最小化原则。2.1.3VC维理论模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开，则称函数集能够把h个样本打散；函数集的VC维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只确定了一些特殊的函数集的VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是1n，对于一些比较复杂的学习机器(如神经网络)，其VC维除了与函数集(神经网结构)有关外，还受学习算法等的影响，其确定更加困难。但是，在实际应用统计学习理论时，可以通过变通的办法巧妙地避开直接求VC维的问题。2.1.4推广性的界统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险empR和实际风险R之间以概率1满足如下关系：ln21ln4emphnhRRn2-(3)其中h是函数集的VC维，n是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)，另一部分称作置信范围，它和学习机器的VC维及训练样本数有关，可以简单地表示为：empRRhn2-(4)它表明，在有限训练样本下，学习机器的VC维越高(复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，这一理论可以由图2.1说明。图2.1置信范围、经验风险与实际风险之间的关系由图2.1可以看出，当样本数目n固定，算法的VC维增大时，它对给定训练样本集合有更强的分类或拟合能力，导致了更小的经验风险empR，甚至使它为零。但是，VC维增大时，hn也随之增大，即放大了置信范围，从而减小了算法具有小的实际风险R的可能性。反之，若VC维缩小，那么它对给定的训练样本集合的分类或拟合能力减弱，导致了大的经验风险，此时，虽然置信区间hn缩小了，但仍不能保证获得小的实际风险。可以看出n固定时empR与hn是一对矛盾体，它们不可能同时都减小，但确实存在某个h值使实际风险上界达到最小值。2.1.5结构风险最小化原则经验风险最小化原则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多的前提下，致使各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取得理想的结果。由2.1.4节中的推广性的界可以看出，影响期望风险上界的因子有两个方面：首先是训练集的规模n，其次是VC维h。可见，在保证分类精度(经验风险)的同时，降低学习机器的VC维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化(StructureRiskMinimization，简称SRM)的由来。由VC维的讨论可以看到，经验风险和期望风险依赖于学习机器函数族的选择。把函数集,,sfx分解为一个函数子集序列12......ksss2-(5)使各个子集能够按照置信范围的大小排序，即12...khhh2-(6)所谓结构风险最小化，便是构造一组嵌套的函数子集，使得其VC维由内向外依次递增，然后在其上寻找经验风险和置信范围之和最小的子集，从而使得实际风险的上界最小化，如图2.2所示图3.2结构风险最小化示意图基于结构风险最小化准则的统计学习理论是一种专门研究小样本的统计理论，它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架，同时也发展出了一种新的模式识别方法——支持向量机，从而能够较好地解决小样本的学习问题。2.2支持向量机理论SVM方法是由Vapnik及其合作者Boser、Guyon、Cortes及Scholkopf在AT&TBell实验室共同创造与发展起来的一种新的学习方法。近年来，许多关于SVM方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，其中在理论上主要以Vapnik及其研究小组做了大量开创性及奠基性的工作。目前SVM正处于不断发展阶段，现在已经成为机器学习领域的标准工具之一。支持向量机是个三层网络结构，是一个多输入、单输出的学习机器，其体系结构如图2.3所示图2.3支持向量机的体系结构其中，位于体系结构最底层的123,,,...,nxxxx是输入样本，,1,2,...,iKxxin是样本x与支持向量在特定空间的内积，1,2,...,iin是拉格朗日乘子，fx是决策函数的输出。图3.3清晰的表示出支持向量机的逻辑概念框架，首先确定训练样本作为支持向量机的输入，然后选择适当的核函数，将样本