支持向量机原理及应用概述

1、精品文档东北大学研究生考试试卷评分考试科目：信号处理的统计分析方法课程编号：09601513阅卷人:刘晓志考试日期：2012 年 11月 07日姓名：赵亚楠学号：1001236注意事项1.考前研究生将上述项目填写清楚.2. 字迹要清楚 , 保持卷面清洁 .3. 交卷时请将本试卷和题签一起上交.4.课程考试后二周内授课教师完成评卷工作, 公共课成绩单与试卷交研究生院培养办公室,专业课成绩单与试卷交各学院, 各学院把成绩单交研究生院培养办公室.东北大学研究生院培养办公室。1欢迎下载精品文档支持向量机（ SVM）原理及应用目录一、 SVM的产生与发展3二、支持向量机相关理论4（一）统计学习理论基础4

2、（二）SVM原理41最优分类面和广义最优分类面52SVM的非线性映射73核函数 .8三、支持向量机的应用研究现状9（一）人脸检测、验证和识别9（二）说话人语音识别10（三）文字手写体识别10（四）图像处理 .11（五）其他应用研究11四、结论和讨论12。2欢迎下载精品文档支持向量机（ SVM）原理及应用一、 SVM的产生与发展自 1995年Vapnik 在统计学习理论的基础上提出SVM作为模式识别的新方法之后，SVM一直倍受关注。同年， Vapnik 和 Cortes 提出软间隔 (soft margin)SVM，通过引进松弛变量i 度量数据 xi 的误分类 ( 分类出现错误时i 大于 0)

3、，同时在目标函数中增加一个分量用来惩罚非零松弛变量 ( 即代价函数 ) ，SVM的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年， Vapnik 等人又提出支持向量回归(SupportVector Regression ， SVR)的方法用于解决拟合问题。 SVR同 SVM的出发点都是寻找最优超平面，但SVR的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston等人根据 SVM原理提出了用于解决多类分类的 SVM方法 (Multi-Class Support Vector Machines，Multi-S

4、VM) ，通过将多类分类转化成二类分类，将 SVM应用于多分类问题的判断：此外，在 SVM算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens提出的最小二乘支持向量机(Least Square Support Vector Machine， LSSVM)算法，Joachims等人提出的 SVM-1ight ，张学工提出的中心支持向量机(CentralSupport VectorMachine，CSVM)，Scholkoph 和Smola基于二次规划提出的 v-SVM等。此后，台湾大学林智仁 (LinChih-Jen) 教授等对 SVM的典型应用进行总结，并设计开

5、发出较为完善的SVM工具包，也就是LIBSVM(A Library for Support Vector Machines)。上述改进模型中，v-SVM是一种软间隔分类器模型，其原理是通过引进参数v，来调整支持向量数占输入数据比例的下限，以及参数来度量超平面偏差， 代替通常依靠经验选取的软间隔分类惩罚参数，改善分类效果； LS-SVM则是用等式约束代替传统SVM中的不等式约束，将求解 QP问题变成解一组等式方程来提高算法效率； LIBSVM是一个通用的 SVM软件包，可以解决分类、回归以及分布估计等问题，它提供常用的几种核函数可由用户选择，并且具有不平衡样本加权和多类分类等功能，此外，交叉验证

6、 (cross validation)方法也是 LIBSVM对核函数参数选取问题所做的一个突出贡献；SVM-1ight 的特点则是通过引进缩水(shrinking)逐步简化 QP问题，以及缓存 (caching) 技术降低迭代运算的计算代价来解决大规模样本条件下SVM学习的复杂性问题。3欢迎下载精品文档二、支持向量机相关理论（一）统计学习理论基础与传统统计学理论相比，统计学习理论(Statistical learning theory或SLT)是一种专门研究小样本条件下机器学习规律的理论。该理论是针对小样本统计问题建立起的一套新型理论体系，在该体系下的统计推理规则不仅考虑了对渐近性能的要求，而

7、且追求在有限信息条件下得到最优结果。 Vapnik 等人从上世纪六、七十年代开始致力于该领域研究，直到九十年代中期，有限样本条件下的机器学习理论才逐渐成熟起来，形成了比较完善的理论体系统计学习理论。统计学习理论的主要核心内容包括：(1) 经验风险最小化准则下统计学习一致性条件；(2)这些条件下关于统计学习方法推广性的界的结论；(3) 这些界的基础上建立的小样本归纳推理准则； (4) 发现新的准则的实际方法( 算法 ) 。（二） SVM原理SVM方法是 20世纪 90年代初 Vapnik 等人根据统计学习理论提出的一种新的机器学习方法，它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该

8、子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。支持向量机的基本思想是：首先，在线性可分情况下，在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输入空间的样本映射到高维属性空间使其变为线性情况，从而使得在高维属性空间采用线性算法对样本的非线性进行分析成为可能，并在该特征空间中寻找最优分类超平面。其次，它通过使用结构风险最小化原理在属性空间构建最优分类超平面，使得分类器得到全局最优，并在整个样本空间的期望风险以某个概率满足一定上界。其突出的优点表现在： (1) 基

9、于统计学习理论中结构风险最小化原则和 VC维理论，具有良好的泛化能力，即由有限的训练样本得到的小的误差能够保证使独立的测试集仍保持小的误差。(2) 支持向量机的求解问题对应的是一个凸优化问题，因此局部最优解一定是全局最优解。(3) 核函数的成功应用，将非线性问题转化为线性问题求解。 (4) 分类间隔的最大化，使得支持向量机算法具有较好的鲁棒性。 由于 SVM自身的突出优势， 因此被越来越多的研究人员作为强有力的学习工具，以解决模式识别、回归估计等领域的难题。4欢迎下载精品文档1最优分类面和广义最优分类面SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用图1来说明。对于一维空间中的点，

10、二维空间中的直线，三维空间中的平面，以及高维空间中的超平面，图中实心点和空心点代表两类样本，H为它们之间的分类超平面，H1，H2分别为过各类中离分类面最近的样本且平行于分类面的超平面，它们之间的距离叫做分类间隔(margin) 。图 1 最优分类面示意图所谓最优分类面要求分类面不但能将两类正确分开，而且使分类间隔最大。将两类正确分开是为了保证训练错误率为 0，也就是经验风险最小 ( 为 O)。使分类空隙最大实际上就是使推广性的界中的置信范围最小，从而使真实风险最小。推广到高维空间，最优分类线就成为最优分类面。设线性可分样本集为 (x ,yi _),i1,., ,Rd ,y1, 1 是类别符号。

11、 d维空间中线性判in x别函数的一般形式为是类别符号。d维空间中线性判别函数的一般形式为g ( x) w x b ，分类线方程为 w x b 0 。将判别函数进行归一化，使两类所有样本都满足| g( x) | 1，也就是使离分类面最近的样本的 | g(x) |1，此时分类间隔等于2 / | w | ，因此使间隔最大等价于使| w | ( 或 | w |2 ) 最小。要求分类线对所有样本正确分类，就是要求它满足yi ( w x) b10,i 1,2,., n（1-1 ）满足上述条件 (1-1) ，并且使 | w |2 最小的分类面就叫做最优分类面，过两类样本中离分类面最近的点且平行于最优分类面

12、的超平面12(supportH，H 上的训练样本点就称作支持向量vector) ，因为它们“支持”了最优分类面。5欢迎下载精品文档利用 Lagrange 优化方法可以把上述最优分类面问题转化为如下这种较简单的对偶问题，即：在约束条件，nyi i 0（1-2a ）i 1i0,i1,2,., n(1-2b)下面对i 求解下列函数的最大值：n1Q（ ）ii 12nij yi y j ( xi x j )（1-3 ）i , j1n若* 为最优解，则 w* yi（1-4 ）i 1即最优分类面的权系数向量是训练样本向量的线性组合。这是一个不等式约束下的二次函数极值问题，存在唯一解。根据khn-Tucker

13、 条件，解中将只有一部分 ( 通常是很少一部分 )i 不为零，这些不为 0解所对应的样本就是支持向量。求解上述问题后得到的最优分类函数是：nf (x) sgn( w* x)b* sgni* yi (xi x) b* (1-5)i1根据前面的分析，非支持向量对应的i 均为 0，因此上式中的求和实际上只对支持向量进行。 b* 是分类阈值，可以由任意一个支持向量通过式(1-1) 求得 ( 只有支持向量才满足其中的等号条件 ) ，或通过两类中任意一对支持向量取中值求得。从前面的分析可以看出，最优分类面是在线性可分的前提下讨论的，在线性不可分的情况下，就是某些训练样本不能满足式 (1-1) 的条件，因此

14、可以在条件中增加一个松弛项参数i 0 ，变成：yi ( w xi ) b 1 i 0, i 1,2,., n(1-6)对于足够小的 s0，只要使nF ( )i(1-7)i1最小就可以使错分样本数最小。对应线性可分情况下的使分类间隔最大，在线性不可分情况下可引入约束：。6欢迎下载精品文档| w |2ck（ 1-8 ）在约束条件 (1-6) 幂1(1-8) 下对式 (1-7) 求极小，就得到了线性不可分情况下的最优分类面，称作广义最优分类面。为方便计算，取 s=1。为使计算进一步简化， 广义最优分类面问题可以迸一步演化成在条件 (1-6) 的约束条件下求下列函数的极小值：） 1 ( w, w) C

15、 (n（ w,i )(1-9)2i 1其中 C为某个指定的常数， 它实际上起控制对锩分样本惩罚的程度的作用， 实现在错分样本的比例与算法复杂度之间的折衷。求解这一优化问题的方法与求解最优分类面时的方法相同，都是转化为一个二次函数极值问题，其结果与可分情况下得到的(1-2) 到 (1-5)几乎完全相同，但是条件(1-2b) 变为：0iC , i 1,., n(1-10)2 SVM的非线性映射对于非线性问题，可以通过非线性交换转化为某个高维空间中的线性问题，在变换空间求最优分类超平面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是我们可以看到，在上面对偶问题中，不论是寻优目标函数（1

16、-3 ）还是分类函数 (1-5) 都只涉及训练样本之间的内积运算 （ x xi）。设有非线性映射: R dH 将输入空间的样本映射到高维( 可能是无穷维 ) 的特征空间 H中，当在特征空间 H中构造最优超平面时，训练算法仅使用空间中的点积，即( xi )(x j ) ，而没有单独的( xi ) 出现。因此，如果能够找到一个函数K使得K ( xix j )( xi )( x j )(1-11)这样在高维空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实现的，我们甚至没有必要知道变换中的形式。根据泛函的有关理论， 只要一种核函数 K ( xix j )满足 Mercer 条件，它就

17、对应某一变换空间中的内积。因此，在最优超平面中采用适当的内积函数 K (xix j ) 就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加。此时目标函数 (1-3) 变为：Q( )n1n(1-12)i2 i , ji j yi y j K (xi x j )i111。7欢迎下载精品文档而相应的分类函数也变为nf (x) sgni* yi K (xi x j ) b* (1-13)i1算法的其他条件不变，这就是SVM。概括地说 SVM就是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间，在这个特征空间中构造最优分类超平面。在形式上 SVM分类函数类似于一个神经网络，输出是中

18、间节点的线性组合，每个中间节点对应于一个支持向量，如图2所示图2 SVM示意图n其中，输出 ( 决策规则 ) ： y sgni yi K ( x xi ) b ，权值 wii y i ， K ( x xi ) 为基于 si 1个支持向量 x1, x2 ,., xs 的非线性变换 ( 内积 ) ， x( x1 , x 2 ,., x d ) 为输入向量。3核函数选择满足 Mercer 条件的不同内积核丞数， 就构造了不同的 SVM，这样也就形成了不同的算法。目前研究最多的核函数主要有三类：(1) 多顼式核函数K ( x, xi ) ( x xi ) 1 q（ 1-14)。8欢迎下载精品文档其中

19、q是多项式的阶次，所得到的是q阶多项式分类器。(2) 径向基函数 (RBF)| xxi|2(1-15)K (x, xi ) exp2所得的 SVM是一种径向基分类器， 它与传统径向基函数方法的基本区别是，这里每一个基函数的中心对应于一个支持向量，它们以及输出权值都是由算法自动确定的。径向基形式的内积函数类似人的视觉特性，在实际应用中经常用到，但是需要注意的是，选择不同的S参数值，相应的分类面会有很大差别。(3)S 形核函数K (x, xi ) tanh v(x xi ) c（1-16)这时的 SVM算法中包含了一个隐层的多层感知器网络，不但网络的权值、 而且网络的隐层结点数也是由算法自动确定的

20、，而不像传统的感知器网络那样由人凭借经验确定。此外，该算法不存在困扰神经网络的局部极小点的问题。在上述几种常用的核函数中，最为常用的是多项式核函数和径向基核函数。除了上面提到的三种核函数外，还有指数径向基核函数、小波核函数等其它一些核函数，应用相对较少。事实上，需要进行训练的样本集有各式各样，核函数也各有优劣。B.Bacsens和S.Viaene 等人曾利用 LS-SVM分类器，采用 UCI数据库，对线性核函数、多项式核函数和径向基核函数进行了实验比较，从实验结果来看，对不同的数据库，不同的核函数各有优劣，而径向基核函数在多数数据库上得到略为优良的性能。三、支持向量机的应用研究现状SVM方法在

21、理论上具有突出的优势， 贝尔实验室率先对美国邮政手写数字库识别研究方面应用了 SVM方法，取得了较大的成功。在随后的近几年内，有关SVM的应用研究得到了很多领域的学者的重视，在人脸检测、验证和识别、说话人/ 语音识别、文字 / 手写体识别、图像处理、及其他应用研究等方面取得了大量的研究成果，从最初的简单模式输入的直接的SVM方法研究，进入到多种方法取长补短的联合应用研究，对SVM方法也有了很多改进。（一）人脸检测、验证和识别Osuna最早将 SVM应用于人脸检测并取得了较好的效果。其方法是汽接训练非线性SVM分类器完成人脸与非人脸的分类。由于SVM的训练需要大量的存储空间，并且非线性SVM分类

22、。9欢迎下载精品文档器需要较多的支持向量，速度很慢。为此，马勇等提出了一种层次型结构的SVM分类器，它由一个线性 SVM组合和一个非线性 SVM组成。检测时，由前者快速排除掉图像中绝大部分背景窗口，而后者只需对少量的候选区域做出确认；训练时，在线性SVM组台的限定下，与“自举(bootstrapping)”方法相结合可收集到训练非线性SVM的更有效的非人脸样本， 简化 SVM训练的难度，大量实验结果表明这种方法不仅具有较高的检测率和较低的误检率，而且具有较快的速度。人脸检测研究中更复杂的情况是姿态的变化。叶航军等提出了利用支持向量机方法进行人脸姿态的判定， 将人脸姿态划分成 6个类别，从一个多

23、姿态人脸库中手工标定训练样本集和测试样本集，训练基于支持向量机姿态分类器，分类错误率降低到 1.67 。明显优于在传统方法中效果最好的人工神经元网络方法。在人脸识别中，面部特征的提取和识别可看作是对 3D物体的 2D投影图像进行匹配的问题。由于许多不确定性因素的影响，特征的选取与识别就成为一个难点。凌旭峰等及张燕昆等分别提出基于 PCA与SVM相结合的人脸识别算法，充分利用了 PCA在特征提取方面的有效性以及SVM在处理小样本问题和泛化能力强等方面的优势，通过 SVM与最近邻距离分类器相结合，使得所提出的算法具有比传统最近邻分类器和 BP网络分类器更高的识别率。 王宏漫等在 PCA基础上进一步

24、做 ICA，提取更加有利于分类的面部特征的主要独立成分； 然后采用分阶段淘汰的支持向量机分类机制进行识别。 对两组人脸图像库的测试结果表明， 基于 SVM的方法在识别率和识别时间等方面都取得了较好的效果。（二）说话人语音识别说话人识别属于连续输入信号的分类问题，SVM是一个很好的分类器， 但不适合处理连续输入样本。为此，忻栋等引入隐式马尔可夫模型 HMM，建立了 SVM和 HMM的混合模型。 HMM适合处理连续信号，而 SVM适台于分类问题； HMM的结果反映了同类样本的相似度，而 SVM的输出结果则体现了异类样本间的差异。为了方便与 HMM组成混合模型，首先将 SVM的输出形式改为概率输出。

25、实验中使用 YOHO数据库，特征提取采用 12阶的线性预测系数分析及其微分，组成 24 维的特征向量。实验表明 HMM和SVM的结合达到了很好的效果。（三）文字手写体识别贝尔实验室对美国邮政手写数字库进行的实验，人工识别平均错误率是2.5 ，专门针对该特定问题设计的 5层神经网络错误率为 5.1 ( 其中利用了大量先验知识) ，而用 3种 SVM方法。10欢迎下载精品文档( 采用 3种核函数 ) 得到的错误率分别为 4.0 、4.1 和 4.2%，且是直接采用 1616的字符点阵作为输入，表明了 SVM的优越性能。手写体数字 O 9的特征可以分为结构特征、统计特征等。柳回春等在心理测试自动分析

26、系统中组合 SVM和其他方法成功地进行了手写数字的识别实验。另外，在手写汉字识别方面，高学等提出了一种基于 SVM的手写汉字的识别方法， 表明了 SVM对手写汉字识别的有效性。（四）图像处理(1) 图像过滤。一般的互联网色情网图像过滤软件主要采用网址库的形式来封锁色情网址或采用入工智能方法对接收到的中、英文信息进行分析甄别。段立娟等提出一种多层次特定类型图像过滤法，即以综合肤色模型检验，支持向量机分类和最近邻方法校验的多层次图像处理框架，达到 85以上的准确率。(2) 视频字幕提取。揽频字幕蕴含了丰富语义，可用于对相应视频流进行高级语义标注。庄越挺等提出并实践了基于 SVM的视频字幕自动定位和

27、提取的方法。 该方法首先将原始图像帧分割为 N*N的子块，提取每个子块的灰度特征；然后使用预先训练好的 SVM分类机进行字幕子块和非字幕子块的分类；最后结合金字塔模型和后期处理过程，实现视频图像字幕区域的自动定位提取。实验表明该方法取得了良好的效果。(3) 图像分类和检索。由于计算机自动抽取的图像特征和人所理解的语义间存在巨大的差距，图像检索结果难以令人满意。近年来出现了相关反馈方法，张磊等以 SVM为分类器，在每次反馈中对用户标记的正例和反例样本进行学习，并根据学习所得的模型进行检索，使用由幅图像组成的图像库进行实验，结果表明，在有限训练样本情况下具有良好的泛化能力。目前 3D虚拟物体图像应

28、用越来越广泛， 肖俊等提出了一种基于 SVM对相似 3D物体识别与检索的算法。该算法首先使用细节层次模型对 3D物体进行三角面片数量的约减，然后提取 3D物体的特征，由于所提取的特征维数很大，因此先用独立成分分析进行特征约减，然后使用SVM进行识别与检索。将该算法用于3D丘陵与山地的地形识别中，取得了良好效果。（五）其他应用研究(1) 由于 SVM的优越性，其应用研究目前开展已经相当广泛。陈光英等设计并实现了一种基于 SVM分类机的网络入侵检测系统。 它收集并计算除服务器端口之外 TCPIP 的流量特征使用SVM算法进行分类， 从而识别出该连接的服务类型， 通过与该连接服务器端口所表明服务类。

29、11欢迎下载精品文档型的比较，检测出异常的TCP连接。实验结果表明，系统能够有效地检测出异常TCP连接。(2) 口令认证简便易实现，但容易被盗用。刘学军等提出利用SVM进行键入特性的验真，并通过实验将其与 BP、 RBF、PNN和LVQ 4种神经网络模型进行对比。证实了采用SVM进行键入特性验真的有效性。(3) 李晓黎等提出了一种将 SVM与无监督聚类相结合的新分类算法，并应用于网页分类问题。该算法首先利用无监督聚类分别对训练集中正例和反例聚类然后挑选一些例子训练 SVM并获得 SVM分类器。任何网页可以通过比较其与聚类中心的距离决定采用无监督聚类方法或SVM分类器进行分类。该算法充分利用了SVM准确率高与无监督聚类速度快的优点。实验表明它不仅具有较高的训练效率，而且有很高