支持向量机论文

渤海大学专业学位研究生课程考核论文院（系、部）：年级：专业：姓名：学号：密封线第1页共14页任课教师：一、命题部分二、评分标准三、教师评语请根据您确定的评分标准详细评分，给定成绩，填入“成绩”部分。阅卷教师评语成绩评阅教师签字：200年月日____________________________注1：本页由学生填写卷头和“任课教师”部分，其余由教师填写。其中蓝色字体部分请教师在命题时删除。提交试卷时含本页。学生从第二页开始写作，要求见蓝色字体部分。注2：“阅卷教师评语”部分请教师用红色或黑色碳素笔填写，不可用电子版。无“评语”视为不合规范。注3：试题、评分标准、评语尽量控制在本页。注4：不符合规范试卷需修改规范后提交。密封线第2页共14页支持向量机简述提要传统统计学研究的是样本数目趋于无穷大时的渐进理论，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际表现却可能不尽如人意。针对小样本，Vapnik等人提出了统计学习理论，并以此为基础提出了支持向量机这一有力工具。本文对支持向量机进行了简单介绍，并以分类器为基础介绍了支持向量机的一些核心概念。关键字支持向量机统计学习理论（一）支持向量机简介支持向量机（SupportVectorMachine）是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中有许多特有的优势，并能推广应用到函数拟合等其他机器学习问题中[1]。支持向量机方法是建立在统计学习理论的VC维和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力[2]。1.1VC维定义1.1(N(F,mZ))：设F是一个假设集，即由在nRX上取值为-1或1的若干函数组成的集合。记mZ=},...,,{21mxxx为X中的ｍ个点组成的集合。考虑当f取遍F中的所有可能的假设时产生的m维向量(f(1x),f(2x),…f(mx))。定义N(F,mZ))为上述m维向量中不同的向量个数。定义1.2（mZ被F打散）：设F是一个假设集，mZ=},...,,{21mxxx为X中的m个点组成的集合。称mZ被F打散，或F打散mZ。定义1.3（VC维）：设假设集F是一个由X上取值为-1或1的函数组成的集合。定义F密封线第3页共14页的VC维为max{m|N(F,mZ)=m2}.VC维反映了函数集的学习能力。一般而言，VC维越大，学习机器越复杂。但目前没有通用的关于任意VC维计算的理论，只对一些特殊函数集的VC维可以计算。如何利用理论和实验的方法计算VC维是当前统计学习理论中一个待研究的问题[3]。1.2结构风险最小化机器学习本质上是一种对问题真实模型的逼近，由于真实世界的模型往往无法精确给出，我们给出的模型与真实模型就存在一个误差，这个与真实模型之间的误差积累就叫做风险。统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即泛化误差界。统计学习理论指出：经验风险)(wRemp和实际风险)(wR之间至少以1-η的概率满足如下关系lhlhwRwRemp)4/ln()1)/2(ln()()(其中，l是样本数，h是函数集的VC维。这一结论表明，统计学习的实际风险由两部分组成：一个是经验风险，另一个是置信风险。置信风险反映了真实风险和经验风险差值的上确界，和VC维h记样本数l有关。可简单地表示为)/()()(lhwRwRemp在有限的训练样本下，学习机器的复杂性越高，VC维越大，置信风险就越大，就会导致真实风险和经验风险间的差别越大。如图所示密封线第4页共14页这就解释了为什么有些学习机器训练阶段的准确率可以达到100%而泛化能力却很差。结构风险最小化原则（StructuralRiskMinimization,SRM）就是为了取得经验风险与置信风险的最小和。统计机器学习理论就是为了努力最小化结构风险。即不仅要使经验风险最小化，还要使VC维最小。（二）线性分类器线性分类器是最简单也是很有效的分类器形式，SVM就是是从线性可分情况下的最优分类面发展而来的[4]。2.1线性可分当一个线性函数能将样本完全正确地分开时，此时这些样本就是线性可分的。否则就称为非线性可分的。线性函数指形如f(x)=wx+b的一次函数，此函数值为0时确定了一个n维空间的超平面(HyperPlane)。w、x为n维向量，b为常数。2.2最优分类面密封线第5页共14页方形和圆形为两类样本，H为分类线，21H,H分别为过各类分类线最近的样本，且与分类线平行，他们之间的距离margin称为分类间隔。当分类线H不但能将两类正确分开，而且使分类间隔最大时，此分类线称为最优分类线。对分类线方程wx+b=0进行归一化处理，使得对线性可分的样本集}1,1{,,,...,1),,(yRxniyxdii，满足.,....,1,01])[(nibxwyii此时分类间隔等于w/2，使间隔最大等价于使2w最小。满足上述条件的分类面就叫最优分类面，21H,H上的训练样本点就称作支持向量。使分类间隔最大实际上就是对推广能力的控制，这是SVM的核心思想之一。统计学习理论指出，在N维空间中，设样本分布在一个半径为R的超球范围内，则满足条件Aw的正则超平面构成的指示函数集})sgn{(),,(bxwbwxf（sgn()为符号函数）的VC维满足下面的界1)],min([22NARh因此，使2w最小就是使VC维的上界最小，从而实现SRM准则中对函数复杂性的选择。于是问题就转换成一个有约束的非线性规划问题：2,21minwbwlibxwytsii,....,2,1,1)(..称上二式组成的最优化问题为原始优化问题。由于此为凸二次寻优问题，根据最优化理论，密封线第6页共14页这个问题存在唯一全局最小解。其Lagrange函数为：liiiibxwywL12)](1[21其中，0i是约束1)(bxwyii的Lagrange乘子。根据KKT条件（Karush-Kuhn-Tucker）有：liiiiliiiixywxywwL11001liiiybL根据wolf对偶理论，经运算将原始优化问题转为liljijijijiixxyyw11,)(21)(max.,...,2,1,0,0..1liytsiliii解此最优化问题，可确定最优超平面。且通常只有一小部分i不为0，这些非零解对应的样本就是支持向量。此时得到的最优分类函数是niiiibxxybxwxf1*})(sgn{})sgn{()(不难看出，式中的求和实际上只对支持向量进行。*b可由任一支持向量回代求得。此时，我们就得到了一个样本线性可分时的线性分类器。（三）核函数线性可分的问题可以由上述的线性分类器求解，当待分类样本为非线性可分时，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空间求最优分类面。如图密封线第7页共14页当（a,b）范围内的样本为一类，其余部分为一类时，在二维空间无法找到一个线性函数将其正确分开，但我们可以找到一条曲线，如此时该函数表达式为2120)(cxcxcxg新建一个向量TTTTcccaaaaxxyyyy),,(),,(,)1,,(),,(2103212321将g(x)转化为yayf,)(，此时f(y)与g(x)等价，且为四维空间中的线性函数。这样，我们就将低维的非线性可分问题转化为了高维的线性可分问题。但遗憾的是，目前还没有一种系统地将低维向量映射到高维的方法[5]。密封线第8页共14页事实上，计算过程中我们只关心高维向量之间的内积，只要找出一种方法可以求出此值就得到了我们想要的结果。核函数（kernelfunction）正是为了求出低维空间的向量经过变换后在高维空间的内积而提出的。并且由于其输入为原空间中的低维向量，避开了高维变换计算问题，使得问题大大简化了。根据泛函的有关理论，只要一种核函数),(jixxK满足Mercer条件，它就对应某一变换空间中的内积[6]。Mercer条件：对任意的对称函数),(xxK,它是某个特征空间中的内积运算的充分必要条件是，对任意0)(x，且dxx)(2，有0)()(),(xdxdxxxxK用核函数替换内积函数后，此时的最优分类目标函数变为niiiibxxKyxf1*})(sgn{)(此时由于计算仍在原空间进行，分类器的计算复杂度没有增加[4]。目前，常用的核函数有以下几种：线性核函数：jijixxxxK),(多项式核函数：djijixxxxK]1)[(),(径向基函数（RBF）：)exp(),(2jijixxxxKSigmoid函数：))(tanh(),(cxxvxxKjiji这时SVM实现的是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部极小点问题。密封线第9页共14页（四）松弛变量及惩罚因子核函数解决了低维向高维空间映射的计算问题，但如果映射到高维空间之后有少量样本的存在使得问题仍然是非线性可分的，这种造成少量错分的问题称为近似线性可分。如图4.1松弛变量此时我们对错分样本点i引入一非负松弛变量i使其间隔可以大于规定的间隔。并使用一个惩罚因子C衡量其带来的损失。此时，我们的原始优化问题就变为：minliiCw1221subjectto0),...2,1(1])[(iiiilibwxy此时，近似线性可分问题就转为了线性可分问题。由此得到的分类器称为软间隔分类器，之前未加入松弛变量得到的分类器为硬间隔分类器。引入松弛变量可以获得更大的分类间隔，但同时也使分类器的精确分类能力降低了。4.2惩罚因子密封线第10页共14页惩罚因子C代表了对离群点的重视程度，C越大，表示不能舍弃该样本的程度越大，在极端的情况下，C趋于无穷时退化为硬间隔分类问题。惩罚因子可用来解决数据集偏斜的问题，即分别给正类、负类的样本点赋予不同的惩罚因子，由此区分对两类样本的重视程度。数据集偏斜是指参与分类的两类样本数量差距很大，此时对于数量少的样本应予以重视，不能轻易舍弃，应赋予较大的惩罚因子。此时我们目标函数中因松弛变量而损失的部分就变为011jqppjjpiiCC其中，i=1..p为正样本，j=p+1…p+q为负样本。C、C的比例选取应根据实际情况具体问题具体分析，如当两类样本分部情况类似时，正负类惩罚因子的比例可以由数量之比确定，当一类与另一类相比样本较集中时，可以用覆盖两类的超球半径之比来确定。（五）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方法，虽然仍然存在分类重叠现象，密封线第11页共14页但避免了不可分类现象，缺点在于分类器个数过多，分类过程会较慢。DAGSMV方法是指，训练时，按照1-a-1的方法求出分类器，在分类阶段，以有向无环图的形式选取分类器进行运算，