SVM 支持向量机基本原理及应用.ppt

《SVM 支持向量机基本原理及应用.ppt》由会员分享，可在线阅读，更多相关《SVM 支持向量机基本原理及应用.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、支持向量机支持向量机支持向量机支持向量机（support vector machinesupport vector machine，SVMSVM）Wang Wang JiminJiminNov 18,2005 Nov 18,2005 信息科学技术学院信息科学技术学院 网络研究所网络研究所OutlineOutlineooSVM的理论基础oo线性判别函数和判别面oo最优分类面oo支持向量机ooSVM的研究与应用信息科学技术学院信息科学技术学院 网络研究所网络研究所SVM的理论基础的理论基础oo传统的统计模式识别方法只有在样本趋向无穷大传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保

2、证。统计学习理论时，其性能才有理论的保证。统计学习理论（STLSTL）研究有限样本情况下的机器学习问题。研究有限样本情况下的机器学习问题。SVMSVM的理论基础就是统计学习理论。的理论基础就是统计学习理论。oo传统的统计模式识别方法在进行机器学习时，强传统的统计模式识别方法在进行机器学习时，强调调经验风险最小化。经验风险最小化。而而单纯的经验风险最小化会单纯的经验风险最小化会产生产生“过学习问题过学习问题”，其推广能力较差。，其推广能力较差。oo推广能力推广能力推广能力推广能力是指是指:将学习机器将学习机器(即预测函数即预测函数,或称学或称学习函数、学习模型习函数、学习模型)对未来输出进行正确

3、预测的能对未来输出进行正确预测的能力。力。信息科学技术学院信息科学技术学院 网络研究所网络研究所过学习问题oo“过学习问题过学习问题”：某些情况下，当训练误差过小反而会导致推广能力的下降。oo例如：对一组训练样本(x,y),x分布在实数范围内，y取值在0，1之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0.信息科学技术学院信息科学技术学院 网络研究所网络研究所SVMoo根据统计学习理论，学习机器的实际风险由经验风根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最险值和置信范围值两部分组成。而基于经验风险最小化准

4、则的学习方法只强调了训练样本的经验风险小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此其推广能最小误差，没有最小化置信范围值，因此其推广能力较差。力较差。ooVapnikVapnik提出的支持向量机提出的支持向量机（SupportVectorMachine,SupportVectorMachine,SVMSVM）以训练误差作为优化问题的约束条件，以置以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即信范围值最小化作为优化目标，即SVMSVM是一种基于是一种基于结构风险最小化准则的学习方法，其推广能力明显结构风险最小化准则的学习方法，其推广能力明

5、显优于一些传统的学习方法。优于一些传统的学习方法。oo形成形成时时期在期在1992199219951995年。年。信息科学技术学院信息科学技术学院 网络研究所网络研究所SVMoo由于由于SVMSVM的求解最后转化成二次规划问题的求解，的求解最后转化成二次规划问题的求解，因此因此SVMSVM的解是全局唯一的最优解的解是全局唯一的最优解ooSVMSVM在解决小样本、非线性及高维模式识别问题在解决小样本、非线性及高维模式识别问题在解决小样本、非线性及高维模式识别问题在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函中表现出许多特有的优势，并能够推广应用到函中表现出许多特

6、有的优势，并能够推广应用到函中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中数拟合等其他机器学习问题中数拟合等其他机器学习问题中数拟合等其他机器学习问题中ooJoachims Joachims 最近采用最近采用SVMSVM在在Reuters-21578Reuters-21578来进行来进行文本分类，并声称它比当前发表的其他方法都好文本分类，并声称它比当前发表的其他方法都好 信息科学技术学院信息科学技术学院 网络研究所网络研究所OutlineOutlineooSVM的理论基础oo线性判别函数和判别面oo最优分类面oo支持向量机ooSVM的研究与应用信息科学技术学院信息科学技术

7、学院 网络研究所网络研究所线性判别函数和判别面线性判别函数和判别面oo一个线性判别函数(discriminantfunction)是指由x的各个分量的线性组合而成的函数oo两类情况:对于两类问题的决策规则为对于两类问题的决策规则为oo如果如果g(x)0g(x)0，则判定则判定x x属于属于C C1 1，oo如果如果g(x)0g(x)0；当当x点在超平面的负侧时，点在超平面的负侧时，g(x)0g(x)0，则判定则判定x x属于属于C C1 1，如果如果g(x)0g(x)0，则判定则判定x x属于属于C C2 2，如果如果g(x)=0g(x)=0，则可以将则可以将x x任任意分到某一类或者拒绝判定

8、。意分到某一类或者拒绝判定。信息科学技术学院信息科学技术学院 网络研究所网络研究所广义线性判别函数广义线性判别函数信息科学技术学院信息科学技术学院 网络研究所网络研究所广义线性判别函数广义线性判别函数信息科学技术学院信息科学技术学院 网络研究所网络研究所设计线性分类器设计线性分类器 信息科学技术学院信息科学技术学院 网络研究所网络研究所Fisher线性判别方法线性判别方法oo如如：FisherFisher线线性性判判别别方方法法，主主要要解解决决把把d d维维空空间间的的样样本本投投影影到到一一条条直直线线上上，形形成成一一维维空空间间，即把维数压缩到一维。即把维数压缩到一维。oo然然而而在在

9、d d维维空空间间分分得得很很好好的的样样本本投投影影到到一一维维空空间间后后，可可能能混混到到一起而无法分割。一起而无法分割。oo但但一一般般情情况况下下总总可可以以找找到到某某个个方方向向，使使得得在在该该方方向向的的直直线线上上，样本的投影能分开的最好。样本的投影能分开的最好。oo目的是降维目的是降维,在低维空间中分割在低维空间中分割信息科学技术学院信息科学技术学院 网络研究所网络研究所OutlineOutlineooSVM的理论基础oo线性判别函数和判别面oo最优分类面oo支持向量机ooSVM的研究与应用信息科学技术学院信息科学技术学院 网络研究所网络研究所最优分类面 ooSVM SV

10、M 是从线性可分情况下的最优分类面发展而来是从线性可分情况下的最优分类面发展而来的的,基本思想可用图基本思想可用图2 2的两维情况说明的两维情况说明.图中,方形点和圆形点代表两类样本,H 为分类线,H1,H2分别为过各类中离分类线最近的样本且平行于分类线的直线,它们之间的距离叫做分类间隔(margin)。所谓最优分类线就是要求分类线不但能将两类正确分开(训练错误率为0),而且使分类间隔最大.推广到高维空间，最优分类线就变为最优分类面。信息科学技术学院信息科学技术学院 网络研究所网络研究所最优分类面信息科学技术学院信息科学技术学院 网络研究所网络研究所如何求最优分类面如何求最优分类面 信息科学技

11、术学院信息科学技术学院 网络研究所网络研究所最优分类面信息科学技术学院信息科学技术学院 网络研究所网络研究所OutlineOutlineooSVM的理论基础oo线性判别函数和判别面oo最优分类面oo支持向量机ooSVM的研究与应用信息科学技术学院信息科学技术学院 网络研究所网络研究所支持向量机支持向量机 上节所得到的最优分类函数为：上节所得到的最优分类函数为：oo该式只包含待分类样本与训练样本中的支持向量的内该式只包含待分类样本与训练样本中的支持向量的内积积 运算，可见运算，可见,要解决一个特征空间中的最优线性分要解决一个特征空间中的最优线性分类问题类问题,我们只需要知道这个空间中的内积运算即

12、可。我们只需要知道这个空间中的内积运算即可。oo对非线性问题对非线性问题,可以通过非线性变换转化为某个高可以通过非线性变换转化为某个高维空间中的线性问题维空间中的线性问题,在变换空间求最优分类面在变换空间求最优分类面.这这种变换可能比较复杂种变换可能比较复杂,因此这种思路在一般情况下不因此这种思路在一般情况下不易实现易实现.信息科学技术学院信息科学技术学院 网络研究所网络研究所支持向量支持向量机机信息科学技术学院信息科学技术学院 网络研究所网络研究所核函数的选择核函数的选择信息科学技术学院信息科学技术学院 网络研究所网络研究所SVMSVM方法的特点方法的特点oo 非线性映射是非线性映射是SVM

13、SVM方法的理论基础方法的理论基础,SVMSVM利用内积利用内积核函数代替向高维空间的非线性映射核函数代替向高维空间的非线性映射;oo 对特征空间划分的最优超平面是对特征空间划分的最优超平面是SVMSVM的目标的目标,最最大化分类边际的思想是大化分类边际的思想是SVMSVM方法的核心方法的核心;oo 支持向量是支持向量是SVMSVM的训练结果的训练结果,在在SVMSVM分类决策中起分类决策中起决定作用的是支持向量。决定作用的是支持向量。ooSVM SVM 是一种有坚实理论基础的新颖的小样本学习方法。它是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等基本上不涉及概率

14、测度及大数定律等,因此不同于现有的统因此不同于现有的统计方法。从本质上看计方法。从本质上看,它避开了从归纳到演绎的传统过程它避开了从归纳到演绎的传统过程,实实现了高效的从训练样本到预报样本的现了高效的从训练样本到预报样本的“转导推理转导推理”(”(transductivetransductive inference),inference),大大简化了通常的分类和回大大简化了通常的分类和回归等问题。归等问题。信息科学技术学院信息科学技术学院 网络研究所网络研究所SVMSVM方法的特点方法的特点ooSVM SVM 的最终决策函数只由少数的支持向量所确定的最终决策函数只由少数的支持向量所确定,计计算

15、的复杂性取决于支持向量的数目算的复杂性取决于支持向量的数目,而不是样本空间而不是样本空间的维数的维数,这在某种意义上避免了这在某种意义上避免了“维数灾难维数灾难”。oo少数支持向量决定了最终结果少数支持向量决定了最终结果,这不但可以帮助我这不但可以帮助我们抓住关键样本、们抓住关键样本、“剔除剔除”大量冗余样本大量冗余样本,而且注定而且注定了该方法不但算法简单了该方法不但算法简单,而且具有较好的而且具有较好的“鲁棒鲁棒”性。性。这种这种“鲁棒鲁棒”性主要体现在性主要体现在:n n增、删非支持向量样本对模型没有影响增、删非支持向量样本对模型没有影响;n n支持向量样本集具有一定的鲁棒性支持向量样本

16、集具有一定的鲁棒性;n n有些成功的应用中有些成功的应用中,SVM SVM 方法对核的选取不敏感。方法对核的选取不敏感。信息科学技术学院信息科学技术学院 网络研究所网络研究所OutlineOutlineooSVM的理论基础oo线性判别函数和判别面oo最优分类面oo支持向量机ooSVM的研究与应用信息科学技术学院信息科学技术学院 网络研究所网络研究所SVM SVM 应用应用oo近年来SVM 方法已经在图像识别、信号处理和基因图谱识别等方面得到了成功的应用,显示了它的优势。ooSVM 通过核函数实现到高维空间的非线性映射,所以适合于解决本质上非线性的分类、回归和密度函数估计等问题。oo支持向量方法

17、也为样本分析、因子筛选、信息压缩、知识挖掘和数据修复等提供了新工具。信息科学技术学院信息科学技术学院 网络研究所网络研究所支持向量机的研究支持向量机的研究oo对支持向量机的研究主要集中在对对支持向量机的研究主要集中在对SVMSVM本身性质的本身性质的研究以及加大支持向量机应用研究的深度和广度两研究以及加大支持向量机应用研究的深度和广度两方面。方面。ooSVMSVM训练算法训练算法训练算法训练算法n n传统传统的利用的利用标标准二次型准二次型优优化技化技术术解决解决对对偶偶问题问题的方法的方法,是是SVMSVM训练训练算算法慢及受到法慢及受到训练样训练样本集本集规规模制模制约约的主要原因。的主要

18、原因。n n目前已提出了目前已提出了许许多解决方法和改多解决方法和改进进算法算法,主要是从如何主要是从如何处处理大理大规规模模样样本集的本集的训练问题训练问题、提高、提高训练训练算法收算法收敛敛速度等方面改速度等方面改进进。n n主要有：分解方法、修改主要有：分解方法、修改优优化化问题问题法、增量学法、增量学习习法、几何方法等分法、几何方法等分别讨论别讨论。信息科学技术学院信息科学技术学院 网络研究所网络研究所SVMSVM分类算法ooSVMSVM分类算法分类算法分类算法分类算法oo训练好训练好SVMSVM分类器后分类器后,得到的支持向量被用来构得到的支持向量被用来构成决策分类面。对于大规模样本

19、集问题成决策分类面。对于大规模样本集问题,SVMSVM训训练得到的支持向量数目很大练得到的支持向量数目很大,则进行分类决策时则进行分类决策时的计算代价就是一个值得考虑的问题。的计算代价就是一个值得考虑的问题。oo解决方法如：缩减集解决方法如：缩减集(Reduced Set)SVMReduced Set)SVM方法，方法，采用缩减集代替支持向量集采用缩减集代替支持向量集,缩减集中的向量不缩减集中的向量不是支持向量是支持向量,数目比支持向量少数目比支持向量少,但它们在分类但它们在分类决策函数中的形式与支持向量相同。决策函数中的形式与支持向量相同。信息科学技术学院信息科学技术学院 网络研究所网络研究所多类多类SVMSVM算法算法ooSVMSVM本质上是两类分类器本质上是两类分类器.oo常用的常用的SVMSVM多值分类器构造方法有多值分类器构造方法有:信息科学技术学院信息科学技术学院 网络研究所网络研究所SVM package 信息科学技术学院信息科学技术学院 网络研究所网络研究所OutlineOutlineooSVM的理论基础oo线性判别函数和判别面oo最优分类面oo支持向量机ooSVM的研究与应用信息科学技术学院信息科学技术学院 网络研究所网络研究所Thank you!