人工智能之支持向量机课件.ppt

1、支持向量机支持向量机 Support Vector Machines内容提要内容提要n统计学习方法概述统计学习方法概述n统计学习问题统计学习问题n学习过程的泛化能力学习过程的泛化能力n支持向量机支持向量机nSVMSVM寻优算法算法n应用应用支持向量机支持向量机nSVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速发展起来nVapnik V N.1995.The Nature of Statistical Learning Theory.Springer-Verlag,New York nVapnik V N.1998.Sta

2、tistical Learning Theory.Wiley-Interscience Publication,John Wiley&Sons,Incn目前已经在许多智能信息获取与处理领域都取得了成功的应用。支持向量机支持向量机 SVMnSVMs are learning systems that nuse a hyperplane of linear functionsnin a high dimensional feature space Kernel functionntrained with a learning algorithm from optimization theory L

3、agrangenImplements a learning bias derived from statistical learning theory Generalisation SVM is a classifier derived from statistical learning theory by Vapnik and Chervonenkis25 线性分类器线性分类器ayestf xf(x,w,b)=sign(w.x-b)denotes+1denotes-1How would you classify this data?26线性分类器线性分类器f xayestdenotes+1d

4、enotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?27线性分类器线性分类器f xayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?28线性分类器线性分类器f xayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)How would you classify this data?29线性分类器线性分类器f xayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b

5、)How would you classify this data?哪一个分界面是最优的？210分类超平面分类超平面nTraining set:(xi,yi),i=1,2,N;yi+1,-1nHyperplane:wx+b=0nThis is fully determined by(w,b)w1x+b1=0w2x+b2=0w3x+b3=0211最大间隔最大间隔一个超平面，如果它能将训练样本没有错误地分开，并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的，则把这个超平面称作最优分类 超 平 面（o p t i m a l separating hyperplane），两类样本中离分

6、类面最近的样本到分类面的距离称为分类间隔，最优超平面也可以称作最大间隔超平面。212最大间隔原则最大间隔原则Note1:decision functions(w,b)and(cw,cb)are the sameNote2:but margins as measured by the outputs of the function xwx+b are not the same if we take(cw,cb).Definition:the margin given by the,which is when c=1/|w|Strategy:1)we need to maximise the ge

7、ometric margin!(cf result from learning theory)2)subject to the constraint that training examples are classified correctly wwx+b=0wx+b0wx+b非线性分划代价：2维空间内积6维空间内积非线性分类非线性分类235为此，引进函数有211222222112211221122(,)(1)12 2 2 ijijijijijijijijijK x xxxxxxxxxxxxxxxxx 比较(2)和(3)，可以发现2(,)()1)ijijK x xxx(3)2()()(,)()

8、1)ijijijxxK x xx x这是一个重要的等式，提示6维空间中的内积可以通过计算 中2维空间中的内积 得到。()()ijxx(,)ijK x x()ijx x非线性分类非线性分类1122121222221122()()12 2 2 ijijijiijjijijxxxxxxxxxxxxxx236实现非线性分类的思想实现非线性分类的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数 ，一旦选定了函数，就可以求解最优化问题2(,)()1)ijijK x xxx(,)ijK x x()x111l1i1min ,2.0 0,1,l

9、llijijijjijjiiiy yK x xstyC ilaa aaaa*1(,)Tlaaa得 ，而决策函数237*1()sgn(,)liiiif xyK x xba决策函数其中*1(,)|0ljiiijjibyyK x xjjCaa(,)iK x x 核函数实现非线性分类的思想实现非线性分类的思想238n多项式内核n径向基函数内核RBFnSigmoind内核(,)()qiiK x xx xc22|(,)expiixxK x x(,)tanh()iiK x xx xc目前研究最多的核函数主要有三类：得到q 阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含一个隐层

10、的多层感知器，隐层节点数是由算法自动确定核函数的选择核函数的选择Chap8 SVM Zhongzhi ShiSVM算法实现软件nLIBSVM：台湾大学林智仁教授等开发，有各种版本，应用很广泛nLS-SVMLAB：Matlab界面，分类、回归都可nOSU_SVM：用于分类，可以实现多分类nSVM toolbox:Matlab界面，代码简单，适合初学者了解原理，但算法效率较低39有关SVM的网站nwww.kernel-machines.org nwww.support- nwww.csie.ntu.edu.tw/cjlin/libsvm nwww.esat.kuleuven.ac.be/sista

11、/ 在实验中选取RBF函数作为核函数的首选，原因：n1.RBF函数可以将样本非线性地规划到更高维的空间中，从而实现非线形影射。Sigmoid核函数取某些特定参数时性能和RBF相同。n2.RBF函数的参数只有一个。相比之下多项式核函数参数比RBF核函数多，因此其模型选择更为复杂。n3.RBF函数的数值限制条件少。RBF函数使数值被限制在0和1之间，而多项式核函数的值可能会趋于不定值 或零值 且幂值更高；Sigmoid核函数在取某些参数值时则可能无效。41SVM预测模型的建立（续）nC和r和选取（以分类为例）选定一组C,r的范围 和 ,然后将它们的准确率用等高线连接起来绘出类似下图。15352,2

12、,2C312152,2,242用SVM实现煤炭需求量的预测n任务：用任务：用1980-2002年的我国煤炭需求量来预测年的我国煤炭需求量来预测2003-2006年的煤炭需求量年的煤炭需求量n将历年的煤炭消费量将历年的煤炭消费量X(t)看作时间序列，则其预测模型可看作时间序列，则其预测模型可以描述为以描述为其中为其中为非线形函数，非线形函数，p为嵌入维数，为嵌入维数，根据上式根据上式,可以得到可以得到输入样本和输出样本输入样本和输出样本,这里用这里用1999-2002年的数据作为检验年的数据作为检验样本样本,分别用分别用SVM和神经网络预测，结果为和神经网络预测，结果为:()(1),(2),()

13、X tX tX tX tp 性能比较SVMRBF神经网络预测最大误差2.992%3.259%平均相对误差1.872%1.976%43用SVM实现煤炭需求量的预测用训练好的用训练好的SVM模型来预测将来模型来预测将来2003-2006年的煤炭年的煤炭需求量，其需求趋势如下图需求量，其需求趋势如下图：2003-2006年的预测值44有待解决的问题n1.如何合选择SVM的参数：怎样合理选择支持向量的核参数，目前尚无定论。格子搜索法比较常见，有的 学者已提出用遗传算法、粒子群算法等优化参数n2.如何实现时间序列的动态预测：动态预测要求SVM的参数能适应序列的动态变化，即建立基于SVM自适应预测控制系统

14、45246SVM applicationsnPattern recognitionoFeatures:words countsnDNA array expression data analysisoFeatures:expr.levels in diff.conditionsnProtein classificationoFeatures:AA composition247Handwritten Digits Recognition248Applying SVMs to Face DetectionnThe SVM face-detection system1.Rescale the 1.Re

15、scale the input image seinput image several timesveral times2.Cut 19x19 wi2.Cut 19x19 window patterns ondow patterns out of the scaled ut of the scaled imageimage3.Preprocess the windo3.Preprocess the window using masking,light cw using masking,light correction and histogram orrection and histogram

16、equalizationequalization4.Classify the 4.Classify the pattern using tpattern using the SVMhe SVM5.If the class corresponds t5.If the class corresponds to a face,draw a rectangle ao a face,draw a rectangle around the face in the output round the face in the output image.image.249Applying SVMs to Face

17、 DetectionnExperimental results on static imagesnSet A:313 high-quality,same number of facesnSet B:23 mixed quality,total of 155 faces250Applying SVMs to Face DetectionnExtension to a real-time systemAn example An example of the skin dof the skin detection moetection module implemdule implemented us

18、ing ented using SVMsSVMsFace DetecFace Detection on the tion on the PC-based PC-based Color Real Color Real Time SysteTime Systemm251ReferencesnVladimir Vapnik.The Nature of Statistical Learning Theory,Springer,1995 nAndrew W.Moore.cmsc726:SVMs.http:/www.cs.cmu.edu/awm/tutorialsnC.Burges.A tutorial

19、on support vector machines for pattern recognition.Data Mining and Knowledge Discovery,2(2):955-974,1998.http:/ nVladimir Vapnik.Statistical Learning Theory.Wiley-Interscience;1998nThorsten Joachims (joachims_01a):A Statistical Learning Model of Text Classification for Support Vector MachinesnBen Rubinstein.Statistical Learning Theory.Dept.Computer Science&Software Engineering,University of Melbourne;and Division of Genetics&Bioinformatics,Walter&Eliza Hall Institute