支持向量机综述

《支持向量机综述》由会员分享，可在线阅读，更多相关《支持向量机综述（15页珍藏版）》请在装配图网上搜索。

1、上海大学 2013 2014学年 冬 季学期研究生课程考试小论文格式课程名称： 模式识别方法 课程编号： 09SB59004 论文题目: 支持向量机原理及应用 研究生姓名: 章云元 学 号: 13721278 论文评语:成 绩: 任课教师: 李昕 评阅日期: 支持向量机原理及应用学号：13721278 姓名：章云元日期：2014.03.07摘要：支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效的解决多类分类问题，如何解决支持向量机二次规划过程

2、中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。本文详细介绍系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等。关键词：机器学习；统计学习理论；SVM；维；The principle and application of Support Vector MachineABSTRACT： SVM(Support Vector Machine) is a novel method of machine learning evolving from Statistics. SVM prese

3、nts many own advantages in solving machine learning problems such as small samples, nonlinearity and high dimension. However, SVM methods exist some problems need to be resolved, mainly including how to deal with multi-classification effectively, how to solve the bottle-neck problem appearing in qua

4、dratic programming process, and how to decide kernel function and optimistical kernel parameters to guarantee effectivity of the algorithm.This paper has introduced in detail the structure, evolvement history, and kinds of classification of machine learning, and demonstrated system SLT(Statistical L

5、earning Theory), SVM and research hotspots of SVM, including seeking SVM problems, multi-classification, parameters optimization, kernel function selection and so on. Keywords: Machine learning, SLT, SVM, VC dimension1.引言1.1支持向量机研究背景及意义随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问

6、题，参数的选择和优化问题等。求解一个SVM问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问题的二次规划问题(Quadratic Programming，QP)。传统的方法是利用标准二次型优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于SVM需要计算和存储核函数矩阵，当样本规模较大时必然导致内存需求增加；另一方面，SVM在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效率，如块算法、分解算法、SMO算法、增式算

7、法等等。支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题，如船舰识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方法扩展到多类分类情况是支持向量机方法研究的重要内容之一。目前，用SVM解决多类分类问题方法主要是通过构造或组合多个两类分类器来实现多类问题的分类。子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两类分类问题。常用的算法有“one-against-one”方法、“one-against-rest”方法、“基于决策树的方法”等。支持向量机多类分类方法的引入拓展了支持向量机的应用范围，也加快了支持向量机方法的改进和创新，同时，支持

8、向量机的核函数的选择以及核参数的选择也是一个重要的研究方向。2.支持向量机的原理支持向量机(Support Vector Machine，SVM)是由Vapnik及其合作者共同创造与发展起来的一种新的机器学习方法，其核心内容在1992年至1995年间提出的。2.1统计学习理论统计学习理论建立在一套较为坚实的理论基础之上，为解决有限样本的学习问题提供了一个统一的框架。它能将许多现有的方法纳入其中，有望帮助解决许多原来难以解决的问题，比如神经网络的结构选择问题、局部最小点问题等。2.1.1机器学习问题机器学习问题1可以看作是通过某种训练方法，对某一系统的输入与输出之间的依赖关系进行估计，并且期望这

9、一估计可以对任意给定输入尽量准确地进行输出预测。一般地，机器学习问题可以表示为：假设变量与之间存在一定的未知依赖关系，即遵循某一未知的联合概率(和之间的确定性关系可以看作是其特例)，机器学习问题就是根据n个独立同分布观测样本，在一组函数中求一个最优的函数对依赖关系进行估计，使得期望风险最小。 2-(1)其中称作预测函数集，为函数的广义参数，可以表示任何函数集；为由于用对进行预测而造成的损失，不同类型的学习问题有不同形式的损失函数。在上面问题的表述中，学习的目标在于使期望风险最小化，但是，由于可以利用的信息只有样本最初的观测样本，因此，期望风险2-(1)是无法计算的。传统的学习方法是采用了所谓经

10、验风险最小化(ERM)准则11，即用样本定义经验风险 2-(2)来逼近3-(1)定义的期望风险，用对参数求经验风险的最小值代替求期望风险的最小化，这就是所谓的经验风险最小化原则。2.1.3维理论模式识别方法中维的直观定义是：对一个指示函数集，如果存在个样本能够被函数集中的函数按所有可能的种形式分开，则称函数集能够把个样本打散；函数集的维就是它能打散的最大样本数目。若对任意数目的样本都有函数能将它们打散，则函数集的维是无穷大。维反映了函数集的学习能力，维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集维计算的理论，只确定了一些特殊的函数集的维。比如在维实数空间中线性分类

11、器和线性实函数的维是，对于一些比较复杂的学习机器(如神经网络)，其维除了与函数集(神经网结构)有关外，还受学习算法等的影响，其确定更加困难。但是，在实际应用统计学习理论时，可以通过变通的办法巧妙地避开直接求维的问题。2.1.4推广性的界统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险和实际风险之间以概率满足如下关系： 2-(3)其中是函数集的维，是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)，另一部分称作置信范围，它和学

12、习机器的维及训练样本数有关，可以简单地表示为： 2-(4) 它表明，在有限训练样本下，学习机器的维越高(复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，这一理论可以由图2.1说明。图2.1 置信范围、经验风险与实际风险之间的关系由图2.1可以看出，当样本数目固定，算法的维增大时，它对给定训练样本集合有更强的分类或拟合能力，导致了更小的经验风险，甚至使它为零。但是，维增大时，也随之增大，即放大了置信范围，从而减小了算法具有小

13、的实际风险的可能性。反之，若维缩小，那么它对给定的训练样本集合的分类或拟合能力减弱，导致了大的经验风险，此时，虽然置信区间缩小了，但仍不能保证获得小的实际风险。可以看出固定时与是一对矛盾体，它们不可能同时都减小，但确实存在某个值使实际风险上界达到最小值。2.1.5结构风险最小化原则经验风险最小化原则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多的前提下，致使各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取得理想的结果。由2.1.4节中的推

14、广性的界可以看出，影响期望风险上界的因子有两个方面：首先是训练集的规模，其次是维。可见，在保证分类精度(经验风险)的同时，降低学习机器的维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化(Structure Risk Minimization，简称SRM)的由来。 由维的讨论可以看到，经验风险和期望风险依赖于学习机器函数族的选择。把函数集分解为一个函数子集序列 2-(5)使各个子集能够按照置信范围的大小排序，即 2-(6)所谓结构风险最小化，便是构造一组嵌套的函数子集，使得其维由内向外依次递增，然后在其上寻找经验风险和置信范围之和最小的子集，从而使得实际风险的上界最小化，

15、如图2.2所示图3.2 结构风险最小化示意图基于结构风险最小化准则的统计学习理论是一种专门研究小样本的统计理论，它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架，同时也发展出了一种新的模式识别方法支持向量机，从而能够较好地解决小样本的学习问题。2.2支持向量机理论SVM方法是由Vapnik及其合作者Boser、Guyon、Cortes及Scholkopf在AT&TBell实验室共同创造与发展起来的一种新的学习方法。近年来，许多关于SVM方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，其中在理论上主要以Vapnik及其研究小组做了大量开创性

16、及奠基性的工作。目前SVM正处于不断发展阶段，现在已经成为机器学习领域的标准工具之一。支持向量机是个三层网络结构，是一个多输入、单输出的学习机器，其体系结构如图2.3所示图2.3 支持向量机的体系结构其中，位于体系结构最底层的是输入样本，是样本与支持向量在特定空间的内积，是拉格朗日乘子，是决策函数的输出。图3.3清晰的表示出支持向量机的逻辑概念框架，首先确定训练样本作为支持向量机的输入，然后选择适当的核函数，将样本从输入空间映射到高维的特征空间，根据优化问题求解出来的支持向量最终得到相应的决策函数。它与传统的神经网络的最大区别在于：神经网络结构的确定大多是凭经验选取的，有一定的盲目性，无法确定

17、泛化的置信空间界限，所以无法保证网络的推广能力，容易出现过学习的现象。而支持向量机网络通过结构化风险最小化归纳原理控制学习单元的维的上界，限制了学习单元的能力，在一定程度上避免了过学习现象。支持向量机是建立在统计学习理论的维理论和结构风险最小化原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。支持向量机被看作是对传统分类器的一个好的发展，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势。概括的说，支持向量机是以寻找最优分类面为目标、以二次规划为手段、以非线性映射为理论基础的统计学习方法。下面将分别从这几个方面对支持向量机理论进行系

18、统的阐述。2.2.1最优分类面支持向量机是从线性可分情况下的最优分类面发展而来的，其基本思想可用图2.4表示，对应于一维空间中的点，二维空间中的直线，三维空间中的平面，以及高维空问中的超平面。图中圆形和三角形的标志分别代表两类样本，中间的实线为两类样本之间的分类超平面，两条虚线分别表示过各类中距离分类面最近的样本且平行于分类面的超平面，它们之间的距离叫做分类间隔(margin)。图2.4 最优分类面示意图最优分类面在把两类正确分开的同时保证分类间隔最大，根据结构风险最小化原则，前者是保证经验风险最小，而后者使分类问隔最大，导致维最小，实际上就是使推广性的界中的置信范围最小，从而达到使真实风险最

19、小。后者保证维最小，从而达到使真实风险最小。假定给出一个样本集满足 2-(7)其中是分类面方程，此时分类间隔为，最终目标是求一个分类面，使得能够将两类样本正确分类的同时保证分类间隔最大，这里是使最小。如图2.4所示，中间的实线为最优分类面，两侧虚线上的样本即为支持向量。因而，在线性可分的情况下，得到的SVM的目标函数是： 2-(8) 2-(9)为求得公式3-(8)的最小值，定义如下Lagrange函数： 2-(10)其中为各样本对应的Lagrange乘子。为了求解表达式3-(10)的最小值，可以令该泛函对、求偏导，并令其等于零，我们得到表达式3-(10)的相应的对偶函数： 2-(11) 2-(

20、12)在表达式2-(12)的约束下，求得表达式3-(11)的唯一解，其中，不为零Lagrange乘子所对应的样本就是支持向量。若为最优解，相应的求出最优分类面权系数向量和分类器的阈值 ： 2-(13) 2-(14)其中、分别表示两类中任意一个支持向量。由上面推导得出的参数、可以得到分类器的决策函数： 2-(15)上述方法可以确保在线性可分的情况下将全部样本正确分类，如果对于线性不可分或者事先不知道是否线性可分的情况，可以通过引入非负松弛变量来允许错分样本的存在。相应地，表达式2-(7)、2-(8)、2-(9)分别变为： 2-(16) 2-(17) 2-(18)其中，是一个自定义的惩罚因子，它表

21、示对错分样本惩罚的程度，用来控制样本偏差与机器推广能力之间的折衷。C越大，对错分样本的惩罚就越大，对错分样本的约束程度就越大。容许错分的分类面又称为软问隔分类面12，求解表达式2-(17)的优化问题和求解表达式2-(8)的优化问题类似，都是通过引入相应的拉格朗日函数及其对偶问题并对其求解，最终得到最优分类判别函数。2.2.2标准支持向量机支持向量机是从线性可分情况下的最优分类面发展而来的，前面介绍的是在线性分类情况下如何求解最优分类超平面。而在实际问题中，分类问题是常常是非线性问题，理想的最优分类面应该是非线性的。支持向量机解决非线性问题的思想是：首先选择适当的核函数13，将低维空间的训练样本

22、通过非线性映射映射到高维特征空间中，然后用前面介绍的方法在高维空间中求解最优分类超平面，高维空问中得到的线性分类面就对应着低维空间的非线性分类面。如图3.5所示，支持向量机处理非线性分类问题时，只是比线性分类问题多了个非线性映射过程，设定该非线性映射为： 2-(19)则表达式3-(11)的优化问题最转化为： 2-(20)图2.5 输入空间和特征空间所对应的分类面示意图非线性映射的引入很好的解决了非线性分类问题，同时也增加了优化求解的困难，使2-(20)的计算非常不容易实现，但是注意到，上面的对偶问题中只涉及到高维空间中的内积运算，即，而没有单独的映射。因此，可以考虑是否可以找到输入空间的一个函

23、数来替代特征空间的内积运算，即 2-(21)这样就省去了高维空间中复杂的内积计算，我们甚至不需要知道映射变换,的具体表示形式。根据泛函的有关理论，只要满足下列定理的Mercer条件，它就对应某一变换空间的内积。定理2.1(Mercer条件)对于任意的对称函数，它是某个特征空间中的内积运算的充分必要条件是，对于任意的且有 2-(22)这样，在高维空间中求解最优分类面时，可以通过采用适当的核函数将高维空将的内积运算转化为低维空间的函数运算，就可以在不影响计算复杂度的情况下实现非线性分类问题。表达式3-(20)也相应的转化为： 2-(23)相应的最优分类面的决策函数也转化为： 2-(24)我们称2-

24、(21)的为核函数，核函数的引入，很好的解决了高维问题，将高维空间的内积运算转化为低维空间的函数运算，常用的核函数有多项式核函数、径向基核函数和Sigmoid核函数等。(1)多项式核函数 2-(25)(2)径向基核函数 2-(26)(3)Sigmoid核函数 2-(27)3支持向量机的算法人脸识别仿真支持向量机是以结构风险最小化理论和维理论为理论基础，以求解二次规划问题为主要手段，以在高维空间中求解最优分类超平面为主要目标，以求解支持向量为结果的一种新的机器学习方法。目前，支持向量机在模式识别、图形分割等领域已经进入了实用阶段。一些学者认为，统计学习理论和支持向量机理论正在成为继神经网络研究之

25、后新的研究热点，并将推动机器学习理论和技术的进一步发展。人脸识别是生物特征识别的一个重要方面，在安全验证系统、医学、档案管理系统、人机交互系统、视频会议以及图像检索等领域具有很大的应用前景，比起指纹识别、视网膜识别、虹膜识别等技术来说，人脸识别相对更加直接，友好，使用者更容易接受24。事实上，不管是对人也好，还是对于计算机也好，要实现对人的检测识别，最优先考虑、最直接、也最有意义的特征就是人脸了，而且如果做更深入的分析，还可以从人脸获取更多的信息，如表情，姿态，年龄等。本章将支持向量机多类分类算法应用于人脸识别中，并通过仿真实验证明算法的有效性。3.1人脸识别的理论基础一个基本的人脸检测识别系

26、统应该包括以下几个方面：人脸检测，人脸表示和人脸鉴别，其中后两步也就是通常所说的人脸识别。人脸识别的主要步骤大致分为图像获取、特征提取和人脸识别几个部分，具体流程如图4.1所示：图像获取预处理人脸检测人脸识别分类器设计特征提取图3.1 人脸识别系统示意图图像获取是人脸识别的第一步，它是指从不同条件下获取的图像中，根据一定的规则和先验知识，利用选择的特征进行检测。先确定有无人脸，若检测到有人脸存在，则对人脸进行定位并获取其尺度姿态等信息，将图像分割成人脸区域和非人脸区域，这一步预处理的工作直接影响着后面的特征提取和识别工作，所以是极其重要的。特征提取是指采取某种表示方式表征检测出的人脸和数据库中

27、的人脸，也可以把它看作一个人脸表示的过程。这些特征可以是较直观的人脸器官的几何特征，如眼，耳，口，鼻的位置，形状，距离等，也可以是比较抽象的代数特征，如K-L变换所得的主成分特征，奇异值分解得到的奇异值特征等，还可以是模板特征，颜色特征，纹理特征等25。人脸识别这一步的主要工作是把待识别人脸数据和数据库中的已知人脸数据进行匹配，以得到相关信息，实际上可以把人脸识别看作是一个分类过程，关键在于选择适当的分类器和分类策略，对表示人脸的特征进行分类。根据对人脸的不同的特征表示，分类器选择也不同，可以是传统的最小距离法、最近邻法等，也可以是较新的神经网络、支持向量机等，而且利用多特征和多分类器组合来改

28、善识别效果也是近年来的一个研究方向。近些年来，人脸识别研究和应用已相对比较成熟，提出了不少新的算法，目前主要有基于几何特征的方法、基于代数特征的方法、基于弹性模型的方法、基于神经网络方法和基于支持向量机的方法等，通常的实验结果表明支持向量机有较好的识别效率。3.2基于PCA方法和SVM原理的人脸识别仿真基于PCA（Principal Components Analysis，主成分分析方法）和SVM方法的人脸识别算法首先将实验图像进行预处理26，然后用PCA方法进行特征提取，最后，将得到的图像特征作为支持向量机的输入训练并测试分类器。选用第四章中介绍的决策树方法来构造分类器，对输入的图像进行训练

29、和识别，具体实现步骤如下：(1)图像获取。选取数据库中的200幅图像(前一百幅为人脸图像，后一百幅为非人脸图像)作为实验样本；(2)预处理。由于本实验中选取的图像为小图像，故无需进行预处理；(3)特征提取，计算预处理之后每幅图像的PCA特征。首先计算每幅人脸图像的协方差矩阵，然后计算每个协方差矩阵的特征值和特征向量，将特征向量矩阵的列向量按特征值降序排列，选取最大特征值对应的特征向量作为投影轴，求图像在该轴上的投影，作为训练和测试的样本输入值；(4)训练分类器。将计算得到的图像特征作为支持向量机的输入，结合第四章提出的SVM两类分类算法训练初始支持向量机SVM；(5)测试训练得到的支持向量机，

30、通过这种传统的支持向量机两类分类算法，得到的实验结果表明，本算法具有一定的有效性。SVM线性分类器的仿真结果如图3.2所示：3.2 基于SVM分类结果4 支持向量机的总结由机器学习介绍起，从机器学习中的泛化性和考虑实际风险，引入VC维。当然这些都是基于统计学的基础，重点关注是小样本统计。其中SVM重点介绍SVM的基本概念和基本推导，中规中矩。让我最头疼的是拉格朗日对偶，后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题。对比这么复杂的推导过程，SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点（中间加了一层sigm

31、oid函数变换），而是就在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，我们还需要进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，其实是松弛变量没有出现在最后的目标函数中，我们这里没有对软间隔考虑，当然为了结构严谨性，我可以粗略说下，最后的优化求解问题，同样也是被拉格朗日对偶和利用SMO算法化解，使SV

32、M趋向于完美。另外，其他很多议题如SVM背后的学习理论、参数选择问题、二值分类到多值分类等等还没有涉及到。参考文献1 邓乃扬，田英杰数据挖掘中的新方法一一支持向量机M科学出版社，20042 张翔支持向量机及其在医学图象分割中的应用ED华中科技大学，20043 Vapnik VThe Nature of Statistical Learning Theory(2nd edition)JNew York，4 Springer，20005 昕炜支持向量机算法的研究及应用D浙江大学，20036 Pabitra Mitra，BUma Shankar，Sankar KPal Segmentation of

33、 multispectral remote sensing images using active support vector machinesJPattern Recognition Letters2004，25(9)：106710747 Xue-Cheng Xi，AunNeow Poo and Si都rKiang ChouSupport vector regression model predictive control on a HVAC plantJControl Engineering Practice，2007，8(15)：897-9088 Qi MiaoShiFu WangNo

34、nl inear Model Predictive Control Based on Support Vector RegressionJProceedings of International Conference on Machine Learning and Cybernetics，2002，(3)：165716619 B.J.de Krnif，T.J.A.deVriesOn Using a Support Vector Machine in Learning FeedForward Contr01.In Proceediings of Int. Conf.on Advanced Int

35、elligent MechatronicsJ，Como，Italy，July 2001：272-27710 J.A.K.SuykensNonlinear Modeling and Support Vector MachinesJProceedings of the 18th IEEE Instrumentation and Measurement Technology Conference, 2001,(1):28729411 王莉，林锦国支持向量机的发展与应用J石油化工自动化，2006，(3)：34-3812 V.N Vacpnik. Principles of risk minimizat

36、ion for learning theoryJ.Neural Information Processing Systems，V014，morgan Kanfmann，San MateolCA，1992，(4):83183813 C.Cortes,V.Vapnik. The Soft Margin C1assifierJ. Technical memorandu 11359-931 20918TM，AT&T Bell Labs，199314 V.Vapnik，S.Golowich，A.Smola.Support Vector Method for Function Approximation，

37、Regression Estimation，and Signal ProcessingJ. Advances inNeural Information ProcessingSystems 9，Cambridge，MIT Press，1997：28128715 郑勇涛,刘玉树.支持向量机解决多分类问题研究J. 计算机工程与应用，2005，41(23)：187-19016 Yiguang Liu，Zhisheng YoU，Liping CaoA novel and quick SYM-based multiclass classifierJPattern Recognition. 2006,39(

38、11)：2258226417 Pawan Lingras。Cory ButzRough set based 1-v-1 approaches to support vector machine multiclassificationJinformation sciences2007，177(8)：3782379818 唐发明，王仲东，陈绵云支持向量机多类分类算法研究J控制与决策，2005，20(7)：74674919 黄勇，郑春颖，宋忠虎多类支持向量机算法综述J计算机技术与自动化2005，24(4)：61-6420 Qing 1 i，Licheng jiao，Yingjuan HaoAdapt

39、ive simplification of soluting for support vector machineJPattern Recognition2007，40(3)：97298021 E1 isa Ricci，Luca Rugini，Renzo PerfettiSVM-based CDMA receiver with incremental active learningNeurocomputing，2006，69(1315)：1691169622 Mathias MAdankon，Mohamed CherietOptimizing resources in model selection for support vector machineJPattern Recognition，2007，40(3)：953963