《支持向量机原理及应用概述》由会员分享，可在线阅读，更多相关《支持向量机原理及应用概述（14页珍藏版）》请在金锄头文库上搜索。
1、东北大学研究生考试试卷评分考试科目：信号处理的统计分析方法课程编号：09601513阅卷人：刘晓志考试日期： 2012年11月07日姓名：赵亚楠学号：1001236注意事项1. 考前研究生将上述项目填写清楚.2. 字迹要清楚，保持卷面清洁.3. 交卷时请将本试卷和题签一起上交.4. 课程考试后二周内授课教师完成评卷工作，公共课成绩单与试卷交研究生院培养办公室, 专业课成绩单与试卷交各学院,各学院把成绩单交研究生院培养办公室.东北大学研究生院培养办公室支持向量机（SVM）原理及应用目录一、SVM的产生与发展3二、支持向量机相关理论4（一）统计学习理论基础4.（二）SVM原理4.1 .最优分类面和
2、广义最优分类面52. SVM的非线性映射7.3 .核函数8.三、支持向量机的应用研究现状9（一）人脸检测、验证和识别1.0（二）说话人/语音识别10（三）文字/手写体识别1.1（四）图像处理.1（五）其他应用研究.12四、结论和讨论12支持向量机(SVM)原理及应用一、SVM的产生与发展自1995年Vapnik在统计学习理论的基础上提出SVM作为模式识别的新方法之后，SVM一直 倍受关注。同年，Vapnik和Cortes提出软间隔(soft margin)SVM，通过引进松弛变量&.度量 数据七的误分类(分类出现错误时&i大于0)，同时在目标函数中增加一个分量用来惩罚非零松 弛变量(即代价函数
3、)，SVM的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程； 1996年，Vapnik等人又提出支持向量回归(Support Vector Regression， SVR)的方法用于解 决拟合问题。SVR同SVM的出发点都是寻找最优超平面，但SVR的目的不是找到两种数据的分割 平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年， Weston等人根据SVM原理提出了用于解决多类分类的SVM方法(Multi-Class Support Vector Machines，Multi-SVM)，通过将多类分类转化成二类分类，将SVM应用于多分类问题的判断： 此外
4、，在SVM算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如， Suykens提出的最小二乘支持向量机(Least Square Support Vector Machine， LSSVM)算 法，Joachims等人提出的SVMTight，张学工提出的中心支持向量机(Central Support Vector Machine，CSVM)，Scholkoph和Smola基于二次规划提出的v-SVM等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM的典型应用进行总结，并设计开发出较为完善的SVMT具包，也就是 LIBSVM(A Library for Supp
5、ort Vector Machines)。上述改进模型中，v-SVM是一种软间隔 分类器模型，其原理是通过引进参数v,来调整支持向量数占输入数据比例的下限，以及参数 P来度量超平面偏差，代替通常依靠经验选取的软间隔分类惩罚参数，改善分类效果；LS-SVM 则是用等式约束代替传统SVM中的不等式约束，将求解QP问题变成解一组等式方程来提高算法 效率；LIBSVM是一个通用的SVM软件包，可以解决分类、回归以及分布估计等问题，它提供常 用的几种核函数可由用户选择，并且具有不平衡样本加权和多类分类等功能，此外，交叉验 证(cross validation)方法也是LIBSVM对核函数参数选取问题所做
6、的一突出贡献； SVM-1ight的特点则是通过引进缩水(shrinking)逐步简化QP问题，以及缓存(caching)技术降 低迭代运算的计算代价来解决大规模样本条件下SVM学习的复杂性问题。二、支持向量机相关理论（）统计学习理论基础与传统统计学理论相比，统计学习理论（Statistical learning theory或SLT）是一种专 门研究小样本条件下机器学习规律的理论。该理论是针对小样本统计问题建立起的一套新型 理论体系，在该体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在有限信息 条件下得到最优结果。Vapnik等人从上世纪六、七十年代开始致力于该领域研究，直到九十
7、年代中期，有限样本条件下的机器学习理论才逐渐成熟起来，形成了比较完善的理论体系一 一统计学习理论。统计学习理论的主要核心内容包括：（1）经验风险最小化准则下统计学习一致性条件； 这些条件下关于统计学习方法推广性的界的结论；（3）这些界的基础上建立的小样本归纳推理 准则；（4）发现新的准则的实际方法（算法）。（二）SVM原理SVM方法是20世纪90年代初Vapnik等人根据统计学习理论提出的一种新的机器学习方法， 它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使 学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试 集的测试误差仍然较小
8、。支持向量机的基本思想是：首先，在线性可分情况下，在原空间寻找两类样本的最优分 类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维 输入空间的样本映射到高维属性空间使其变为线性情况，从而使得在高维属性空间采用线性 算法对样本的非线性进行分析成为可能，并在该特征空间中寻找最优分类超平面。其次，它 通过使用结构风险最小化原理在属性空间构建最优分类超平面，使得分类器得到全局最优， 并在整个样本空间的期望风险以某个概率满足一定上界。其突出的优点表现在：（1）基于统计学习理论中结构风险最小化原则和VC维理论，具有良 好的泛化能力，即由有限的训练样本得到的小的误差能够保证使独
9、立的测试集仍保持小的误 差。（2）支持向量机的求解问题对应的是一个凸优化问题，因此局部最优解一定是全局最优解。 （3）核函数的成功应用，将非线性问题转化为线性问题求解。（4）分类间隔的最大化，使得支 持向量机算法具有较好的鲁棒性。由于SVM自身的突出优势，因此被越来越多的研究人员作为强有力的学习工具，以解决模式识别、回归估计等领域的难题。1 .最优分类面和广义最优分类面SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用图1来说明。对于一维 空间中的点，二维空间中的直线，三维空间中的平面，以及高维空间中的超平面，图中实心 点和空心点代表两类样本，H为它们之间的分类超平面，H H2分别为
10、过各类中离分类面最近 的样本且平行于分类面的超平面，它们之间的距离叫做分类间隔(margin)。图1最优分类面示意图margin -所谓最优分类面要求分类面不但能将两类正确分开，而且使分类间隔最大。将两类正确 分开是为了保证训练错误率为0，也就是经验风险最小(为O)。使分类空隙最大实际上就是使 推广性的界中的置信范围最小，从而使真实风险最小。推广到高维空间，最优分类线就成为 最优分类面。设线性可分样本集为(x ,七),，=1,n, x e Rd, y e +1,-1是类别符号。d维空间中线性判 别函数的一般形式为是类别符号。d维空间中线性判别函数的一般形式为g(x) = w x + b，分 类
11、线方程为w x + b = 0。将判别函数进行归一化，使两类所有样本都满足I g(x) 1= 1，也就是 使离分类面最近的样本的I g(x) I= 1，此时分类间隔等于2/II wII，因此使间隔最大等价于使 II w II (或II w II2 )最小。要求分类线对所有样本正确分类，就是要求它满足y (w x) + b -1 0, i = 1,2,.,n(1-1)i满足上述条件(1-1)，并且使II w II2最小的分类面就叫做最优分类面，过两类样本中离分类面最近的点且平行于最优分类面的超平面H1, H2上的训练样本点就称作支持向量(support vector),因为它们“支持”了最优分类
12、面。利用Lagrange优化方法可以把上述最优分类面问题转化为如下这种较简单的对偶问题，即：在约束条件，(1-2a)(1-2b)(1-3)(1-4)工 y a =0i ii=1a 0,i = 1,2,.,n下面对a ,求解下列函数的最大值：Q (a) = 2L a - - IL a a yy (尤尤)i 2 i j i j i ji=1i,j=1若a *为最优解，则w* = 8a * yaii=1即最优分类面的权系数向量是训练样本向量的线性组合。这是一个不等式约束下的二次函数极值问题，存在唯一解。根撼Uhn-Tucker条件，解中 将只有一部分(通常是很少一部分)a i不为零，这些不为0解所对
13、应的样本就是支持向量。求 解上述问题后得到的最优分类函数是：f (x) = sgn(w* -x) + b* = sgn8a *y (x -x) + b*(1-5)i=1根据前面的分析，非支持向量对应的a i均为0,因此上式中的求和实际上只对支持向量 进行。b*是分类阈值，可以由任意一个支持向量通过式(1-1)求得(只有支持向量才满足其中 的等号条件)，或通过两类中任意一对支持向量取中值求得。从前面的分析可以看出，最优分类面是在线性可分的前提下讨论的，在线性不可分的情 况下，就是某些训练样本不能满足式(1-1)的条件，因此可以在条件中增加一个松弛项参数 e i 0，变成：y.(wx.) + b-
14、1 + e . 0,i = 1,2,.,n(1-6)对于足够小的s0,只要使七(e) = 8喝(1-7)i=1最小就可以使错分样本数最小。对应线性可分情况下的使分类间隔最大，在线性不可分 情况下可引入约束：II w 1|2 c(1-8)在约束条件(1-6)幂1(1-8)下对式(1-7)求极小，就得到了线性不可分情况下的最优分类 面，称作广义最优分类面。为方便计算，取s=1。为使计算进一步简化，广义最优分类面问题可以迸一步演化成在条件(1-6)的约束条件下 求下列函数的极小值：.1 (w,)= (w,w) + C( e )(1-9)i=1其中C为某个指定的常数，它实际上起控制对锩分样本惩罚的程度
15、的作用，实现在错分样 本的比例与算法复杂度之间的折衷。求解这一优化问题的方法与求解最优分类面时的方法相同，都是转化为一个二次函数极值问题，其结 果与可分情况下得到的(1-2)到(1-5)几乎完全相同，但是条件(1-2b)变为：0 a. C,i = 1,.,n(1-10)2.SVM的非线性映射对于非线性问题，可以通过非线性交换转化为某个高维空间中的线性问题，在变换空间 求最优分类超平面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是我 们可以看到，在上面对偶问题中，不论是寻优目标函数(1-3)还是分类函数(1-5)都只涉及 训练样本之间的内积运算危-七)。设有非线性映射:Rd r H将输入空间的样本映射到高维 (可能是无穷维)的特征空间H中，当在特征空间H中构造最优超平面时，训练算法仅使用空间 中的点积，即(七)。(七)，而没有单独的 (七)出现。因此，如果能够找到一个函数K使得K(x -x.) = (x ).(x.)(1-11)这样在高维空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实 现的，我们甚至没有必要知道变换中的形式。根据泛函的有关理论，只要一种核函数K(xi x.)
