支持向量机论文

任课教师：一、命题局部二、评分标准三、教师评语请根据您确定的评分标准详细评分，给定成绩，填入“成绩”局部。阅卷教师评语成绩评阅教师签字：200年月日____________________________注1：本页由学生填写卷头和“任课教师”局部，其余由教师填写。其中蓝色字体局部请教师在命题时删除。提交试卷时含本页。学生从第二页开始写作，要求见蓝色字体局部。注2：“阅卷教师评语”局部请教师用红色或黑色碳素笔填写，不可用电子版。无“评语”视为不合标准。注3：试题、评分标准、评语尽量控制在本页。注4：不符合标准试卷需修改标准后提交。支持向量机简述提要传统统计学研究的是样本数目趋于无穷大时的渐进理论，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际表现却可能不尽如人意。针对小样本，Vapnik等人提出了统计学习理论，并以此为根底提出了支持向量机这一有力工具。本文对支持向量机进行了简单介绍，并以分类器为根底介绍了支持向量机的一些核心概念。关键字支持向量机统计学习理论支持向量机简介支持向量机〔SupportVectorMachine〕是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中有许多特有的优势，并能推广应用到函数拟合等其他机器学习问题中[1]。支持向量机方法是建立在统计学习理论的VC维和结构风险最小原理根底上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最正确折衷，以期获得最好的推广能力[2]。VC维定义1.1(N(F,))：设F是一个假设集，即由在上取值为-1或1的假设干函数组成的集合。记=为X中的ｍ个点组成的集合。考虑当取遍F中的所有可能的假设时产生的m维向量((),(),…())。定义N(F,))为上述m维向量中不同的向量个数。定义1.2〔被F打散〕：设F是一个假设集，=为X中的m个点组成的集合。称被F打散，或F打散。定义1.3〔VC维〕：设假设集F是一个由X上取值为-1或1的函数组成的集合。定义F的VC维为max{m|N(F,)=}.VC维反映了函数集的学习能力。一般而言，VC维越大，学习机器越复杂。但目前没有通用的关于任意VC维计算的理论，只对一些特殊函数集的VC维可以计算。如何利用理论和实验的方法计算VC维是当前统计学习理论中一个待研究的问题[3]。结构风险最小化机器学习本质上是一种对问题真实模型的逼近，由于真实世界的模型往往无法精确给出，我们给出的模型与真实模型就存在一个误差，这个与真实模型之间的误差积累就叫做风险。统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即泛化误差界。统计学习理论指出：经验风险和实际风险之间至少以1-η的概率满足如下关系其中，l是样本数，h是函数集的VC维。 这一结论说明，统计学习的实际风险由两局部组成：一个是经验风险，另一个是置信风险。置信风险反映了真实风险和经验风险差值的上确界，和VC维h记样本数l有关。可简单地表示为在有限的训练样本下，学习机器的复杂性越高，VC维越大，置信风险就越大，就会导致真实风险和经验风险间的差异越大。如下图这就解释了为什么有些学习机器训练阶段的准确率可以到达100%而泛化能力却很差。结构风险最小化原那么〔StructuralRiskMinimization,SRM〕就是为了取得经验风险与置信风险的最小和。统计机器学习理论就是为了努力最小化结构风险。即不仅要使经验风险最小化，还要使VC维最小。线性分类器线性分类器是最简单也是很有效的分类器形式，SVM就是是从线性可分情况下的最优分类面开展而来的[4]。2.1线性可分 当一个线性函数能将样本完全正确地分开时，此时这些样本就是线性可分的。否那么就称为非线性可分的。线性函数指形如f(x)=wx+b的一次函数，此函数值为0时确定了一个n维空间的超平面(HyperPlane)。w、x为n维向量，b为常数。2.2最优分类面 方形和圆形为两类样本，H为分类线，分别为过各类分类线最近的样本，且与分类线平行，他们之间的距离margin称为分类间隔。当分类线H不但能将两类正确分开，而且使分类间隔最大时，此分类线称为最优分类线。对分类线方程wx+b=0进行归一化处理，使得对线性可分的样本集，满足此时分类间隔等于，使间隔最大等价于使最小。满足上述条件的分类面就叫最优分类面，上的训练样本点就称作支持向量。 使分类间隔最大实际上就是对推广能力的控制，这是SVM的核心思想之一。统计学习理论指出，在N维空间中，设样本分布在一个半径为R的超球范围内，那么满足条件的正那么超平面构成的指示函数集〔sgn()为符号函数〕的VC维满足下面的界因此，使最小就是使VC维的上界最小，从而实现SRM准那么中对函数复杂性的选择。 于是问题就转换成一个有约束的非线性规划问题：称上二式组成的最优化问题为原始优化问题。由于此为凸二次寻优问题，根据最优化理论，这个问题存在唯一全局最小解。其Lagrange函数为：其中，是约束的Lagrange乘子。 根据KKT条件〔Karush-Kuhn-Tucker〕有：根据wolf对偶理论，经运算将原始优化问题转为解此最优化问题，可确定最优超平面。且通常只有一小局部不为0，这些非零解对应的样本就是支持向量。此时得到的最优分类函数是不难看出，式中的求和实际上只对支持向量进行。可由任一支持向量回代求得。此时，我们就得到了一个样本线性可分时的线性分类器。核函数线性可分的问题可以由上述的线性分类器求解，当待分类样本为非线性可分时，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空间求最优分类面。如图当〔a,b〕范围内的样本为一类，其余局部为一类时，在二维空间无法找到一个线性函数将其正确分开，但我们可以找到一条曲线，如此时该函数表达式为新建一个向量将g(x)转化为，此时f(y)与g(x)等价，且为四维空间中的线性函数。这样，我们就将低维的非线性可分问题转化为了高维的线性可分问题。 但遗憾的是，目前还没有一种系统地将低维向量映射到高维的方法[5]。 事实上，计算过程中我们只关心高维向量之间的内积，只要找出一种方法可以求出此值就得到了我们想要的结果。 核函数〔kernelfunction〕正是为了求出低维空间的向量经过变换后在高维空间的内积而提出的。并且由于其输入为原空间中的低维向量，避开了高维变换计算问题，使得问题大大简化了。根据泛函的有关理论，只要一种核函数满足Mercer条件，它就对应某一变换空间中的内积[6]。Mercer条件：对任意的对称函数,它是某个特征空间中的内积运算的充分必要条件是，对任意，且，有用核函数替换内积函数后，此时的最优分类目标函数变为此时由于计算仍在原空间进行，分类器的计算复杂度没有增加[4]。目前，常用的核函数有以下几种：线性核函数：多项式核函数：径向基函数〔RBF〕：Sigmoid函数：这时SVM实现的是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部极小点问题。松弛变量及惩罚因子核函数解决了低维向高维空间映射的计算问题，但如果映射到高维空间之后有少量样本的存在使得问题仍然是非线性可分的，这种造成少量错分的问题称为近似线性可分。如图4.1松弛变量此时我们对错分样本点i引入一非负松弛变量使其间隔可以大于规定的间隔。并使用一个惩罚因子C衡量其带来的损失。此时，我们的原始优化问题就变为：min subjectto此时，近似线性可分问题就转为了线性可分问题。由此得到的分类器称为软间隔分类器，之前未参加松弛变量得到的分类器为硬间隔分类器。引入松弛变量可以获得更大的分类间隔，但同时也使分类器的精确分类能力降低了。4.2惩罚因子 惩罚因子C代表了对离群点的重视程度，C越大，表示不能舍弃该样本的程度越大，在极端的情况下，C趋于无穷时退化为硬间隔分类问题。惩罚因子可用来解决数据集偏斜的问题，即分别给正类、负类的样本点赋予不同的惩罚因子，由此区分对两类样本的重视程度。 数据集偏斜是指参与分类的两类样本数量差距很大，此时对于数量少的样本应予以重视，不能轻易舍弃，应赋予较大的惩罚因子。 此时我们目标函数中因松弛变量而损失的局部就变为其中，i=1..p为正样本，j=p+1…p+q为负样本。 、的比例选取应根据实际情况具体问题具体分析，如当两类样本分部情况类似时，正负类惩罚因子的比例可以由数量之比确定，当一类与另一类相比样本较集中时，可以用覆盖两类的超球半径之比来确定。SVM用于多类分类由于SVM属于二类分类器，一个分类器只能完成二类分类，在处理多类分类问题时，需要用到多个分类器共同完成分类工作。常用的多类分类方法有：一类对余类〔1-a-r〕、一对一类(1-a-1)和有向无环图支持向量机(DAGSMV)1-a-r方法是指，训练时，每次选取一个类的样本作为正类样本，其余为负类样本，此时生成的分类器个数为n。分类时，将待分类样本代入每个分类器进行运算。1-a-r方法由于分类器较少，所以分类速度较快，但会出现分类重叠或不可分类现象，并且由于训练阶段正负类数量差距较大，这就人为造成了数据集偏斜。1-a-1方法是指，训练时，选取一个样本作为正类样本，分别取其余样本中的一类为负类样本进行训练，此时生成的分类器个数为n(n-1)个。分类时，将待分类样本代入每个分类器进行运算，采用每个分类器投票的方式决定样本类别。1-a-r方法的优点在于，由于训练阶段正负类样本数量较少，整体上来说，速度要优于1-a-r方法，虽然仍然存在分类重叠现象，但防止了不可分类现象，缺点在于分类器个数过多，分类过程会较慢。DAGSMV方法是指，训练时，按照1-a-1的方法求出分类器，在分类阶段，以有向无环图的形式选取分类器进行运算，最终得到分类结果，如图 DAGSVM的优点在于分类时不必遍历所有的分类器，具有较高的分类效率。但一旦根节点分类错误，那么后面将无法修正错误并导致错误的分类。故一般根节点都会使用差异较大的两类分类器。SVM算法的改良目前针对SVM应用中出现的问题，主要针对SVM的一些缺乏之处进行如下改良和完善。6.1对学习训练速度的改良SVM训练速度与支持向量的数量有关，支持向量个数越大，训练的计算量就越大，识别的计算量也同样很大。于是，就需要提高SVM的计算速度，以便处理大规模问题。因此，降低支持向量数目、简化支持向量成为一项非常有意义的工作[7][8]。6.2对SVM多分类算法的研究 经典SVM算法在二类分类问题上得到了很好的研究和应用，但现实中的问题往往需要多类分类问题。如何将SVM良好的二分类处理能力有效地延伸到多累分类问题上，是扩大SVM应用领域的实际要求，是目前研究的一个重要方面[9][10]。6.3对过学习问题的优化 当训练样本两类样本混杂较严重时，SVM也可能出现过学习现象，使得决策面过于复杂而降低了泛化能力。因此，对过学习问题的研究和寻找防止方法也是研究之一[11]。6.4对SVM样本孤立点和噪点处理的改良 改良对训练样本中噪点的处理提高其泛化能力，因为SVM在构造最优分类面时所有样本具有相同的作用，因此，存在对噪声或野值敏感的问题。于是，如何消除噪点影响也是改良SVM的研究方向之一[12]。6.5核函数的构造和参数的选择理论研究 基于各个不同的应用领域，可以构造不同的核函数，能或多或少的引入领域知识。现在核函数广泛应用的类型有：多项式逼近、贝叶斯分类器、径向基函数、多层感知器等。参数的选择现在多利用交叉验证的方法来确认。6.6主动学习的SVM 主动学习在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，它能有效地减少评价样本的数量，也就是通过某种标准对样本分类的有效性进行排序，然后选择有效样本进行训练。SVM的应用由于SVM坚实的理论根底以及分类器较低的系统资源占用，使得SVM成为一种较有力的工具。7.1在函数拟合上的应用 SVM方法可以很好地应用于函数拟合问题中，其思路与在模式识别中十分相似，一般支持向量都是在函数变化比拟剧烈的位置上的样本[4]。但凡涉及内积运算的只要用核函数来计算就可以实现非线性函数拟合。7.2在高维模式识别上的应用 由于SVM的分类器十分简洁，使得SVM在高维模式识别方面有特有的优势。如文本分类领域，即使计算高维样本也不会对计算机造成太大的负担。而其他方法，如KNN方法，在样本维数及样本数过高时效率会非常低下。7.3在一般模式识别上的应用 但凡能够量化为向量形式的问题都可以将SVM作为工具来使用，如人脸识别、三维物体识别、遥感图像分析、时间序列预测、波束成型等。 在现实应用中，SVM在手写识别[13]，波束成形[14]等应用领域取得了良好的效果。讨论由于统计学习理论和支持向量机建立了一套较好的在小样本下机器学习的理论框架和通用方法，既有严格的理论根底，又能较好地解决小样本、非线性、高维和局部极小点等实际问题，因此成为继神经网络之后的有一个研究方向。但从文中我们可以看出，支持向量机还有许多领域有待研究，如VC维确实定、核函数的选择、如何找到一个更好反映学习机器的参数和得到更紧的界等。在应用方面，支持向量机在性能上有各种出色的表现，目前，支持向量机更趋向于与其他机器学习方法的融合，如SVM与KNN算法、SVM与神经网络等等。参考文献[1]刘霞，卢苇.SVM在文本分类中的应用研究，计算机教育，2007.1[2]唐春生，张磊.文本分类研究进展[3]VapnikV,LevinE,LeCunY.MeasuringtheVC2dimensionofalearningmachine.NeuralComputation,1994,6:851～876.[4]张学工.关于统计学习理论与支持向量机，自动化学报，2000.1[5]Jasper'sJavaJacal.SVM入门〔七〕为何需要核函数，[6]VapnikVN.TheNatureofStatisticalLearningTheory,NY:Springer2Verlag,1995张学工译.统计学习理论的本质.北京:清华大学出版社,1999[7]CJCBurges.Simplifiedsupportvectordecisionrule[A].Proc13