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

《人工智能之支持向量机ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能之支持向量机ppt课件.ppt（51页珍藏版）》请在三一办公上搜索。

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

2、blication, John Wiley&Sons, Inc目前已经在许多智能信息获取与处理领域都取得了成功的应用。,支持向量机 SVM,SVMs are learning systems that use a hyperplane of linear functionsin a high dimensional feature space Kernel functiontrained with a learning algorithm from optimization theory LagrangeImplements a learning bias derived from stati

3、stical learning theory Generalisation SVM is a classifier derived from statistical learning theory by Vapnik and Chervonenkis,2,5,线性分类器,a,yest,2,6,线性分类器,f,x,a,yest,denotes +1denotes -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,2,7,线性分类器,f,x,a,yest,denotes +1denotes -1,f(x,w,b) = si

4、gn(w. x - b),How would you classify this data?,2,8,线性分类器,f,x,a,yest,denotes +1denotes -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,2,9,线性分类器,f,x,a,yest,denotes +1denotes -1,f(x,w,b) = sign(w. x - b),How would you classify this data?,哪一个分界面是最优的？,2,10,分类超平面,Training set: (xi, yi), i=

5、1,2,N; yi+1,-1Hyperplane: wx+b=0This is fully determined by (w,b),w1x+b1=0,w2x+b2=0,w3x+b3=0,2,11,最大间隔,一个超平面，如果它能将训练样本没有错误地分开，并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的，则把这个超平面称作最优分类超平面（optimal separating hyperplane），两类样本中离分类面最近的样本到分类面的距离称为分类间隔，最优超平面也可以称作最大间隔超平面。,2,12,最大间隔原则,Note1: decision functions (w,b) and

6、 (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: geometric margin: the margin given by the canonical decision function, which is when c=1/|w| Strategy: 1) we need to maximise the geometric margin! (cf result fr

7、om learning theory)2) subject to the constraint that training examples are classified correctly,w,wx+b=0,wx+b0,wx+b0,2,13,支持向量,The training points that are nearest to the separating function are called support vectors.What is the output of our decision function for these points?,2,14,分类问题的数学表示,已知：训练

8、集包含 个样本点：说明： 是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标； 是输出指标，或输出. 问题：对一个新的模式 ，推断它所对应的输出 是1还是-1.实质：找到一个把 上的点分成两部分的规则.,2维空间上的分类问题) n维空间上的分类问题.,2,15,根据给定的训练集其中， ，寻找 上的一个实值函数 ，用决策函数判断任一模式 对应的 值.sgn()为符号函数，取自变量的符号。 可见，分类学习机构造决策函数的方法(算法)， 两类分类问题 多类分类问题 线性分类学习机 非线性分类学习机,分类学习方法,2,16,SVM分类问题大致有三种：线性可分问题、近似线性可分问题、

9、线性不可分问题。,分类学习方法,Chap8 SVM Zhongzhi Shi,2,17,考虑 上的线性可分的分类问题.这里有许多直线 能将两类点正确分开.如何选取 和 ？简单问题：设法方向 已选定，如何选取 ？解答： 选定 平行直线 极端直线 和 取 和 的中间线为分划直线如何选取 ？对应一个 ，有极端直线 ，称 和 之间的距离为“间隔”.显然应选使“间隔”最大的 。,最大间隔法的直观导出,2,18,数学语言描述,调整 ，使得,令 ，则两式可以等价写为,与此相应的分划直线表达式:,给定适当的法方向 后，这两条极端直线 可表示为,Chap8 SVM Zhongzhi Shi,2,19,如何计算分

10、划间隔？考虑2维空间中极端直线之间的间隔情况,求出两条极端直线的距离：,Chap8 SVM Zhongzhi Shi,2,20,Margin =,H1平面：,H2平面：,.(2),.(1),Chap8 SVM Zhongzhi Shi,2,21,分划直线表达式为 “间隔” 为极大化“间隔”的思想导致求解下列对变量 和 的最优化问题说明：只要我们求得该问题的最优解 ，从而构造分划超平面 ，求出决策函数 。上述方法对一般 上的分类问题也适用.,原始问题,Chap8 SVM Zhongzhi Shi,2,22,求解原始问题,为求解原始问题，根据最优化理论，我们转化为对偶问题来求解,对偶问题,为原始问

11、题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解,2,23,线性可分问题,计算 ，选择 的一个正分量 , 并据此计算,事实上， 的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为支持向量(SV),构造分划超平面 ,决策函数,根据最优解,2,24,近似线性可分问题,不要求所有训练点都满足约束条件 ，为此对第 个训练点 引入松弛变量(Slack Variable) ,把约束条件放松到 。,体现了训练集被错分的情况，可采用 作为一种度量来描述错划程度。,

12、两个目标：1. 间隔 尽可能大 2. 错划程度 尽可能小,显然，当 充分大时，样本点 总可以满足以上约束条件。然而事实上应避免 太大，所以需在目标函数对 进行惩罚,（即“软化” 约束条件）,Chap8 SVM Zhongzhi Shi,2,25,因此，引入一个惩罚参数 ，新的目标函数变为:,体现了经验风险，而 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。,近似线性可分问题,Chap8 SVM Zhongzhi Shi,2,26,(广义)线性支持向量分类机算法,设已知训练集 ，其中,2. 选择适当的

13、惩罚参数 ，构造并求解最优化问题,3. 计算 ，选择 的一个分量 ，并据此 计算出,4. 构造分划超平面 ,决策函数,求得,2,27,非线性分类,例子:,2,28,Non-linear Classification,What can we do if the boundary is nonlinear ?,Idea:,transform the data vectors to a space where the separator is linear,Chap8 SVM Zhongzhi Shi,2,29,Non-linear Classification,The transformation

14、 many times is made to an infinite dimensional space, usually a function space.Example: x cos(uTx),Chap8 SVM Zhongzhi Shi,2,30,Non-linear SVMs,Transform x (x)The linear algorithm depends only on xxi, hence transformed algorithm depends only on (x)(xi)Use kernel function K(xi,xj) such that K(xi,xj)=

15、(x)(xi),2,31,设训练集 ，其中假定可以用 平面上的二次曲线来分划：,现考虑把2维空间 映射到6维空间的变换,上式可将2维空间上二次曲线映射为6维空间上的一个超平面：,非线性分类,2,32,可见，只要利用变换，把 所在的2维空间的两类输入点映射到 所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：,最后得出原空间中的二次曲线：,怎样求6维空间中的分划超平面？(线性支持向量分类机),非线性分类,2,33,需要求解的最优化问题,其中,非线性分类,2,34,在求得最优化问题的解 后，得到分划超平面,其中,最后得到决策函数,或,线性分划非线性分划代价：2维空间内积6维空间内

16、积,非线性分类,2,35,为此，引进函数,有,比较(2)和(3)，可以发现,这是一个重要的等式，提示6维空间中的内积可以通过计算 中2维空间中的内积 得到。,非线性分类,2,36,实现非线性分类的思想,给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数 ，一旦选定了函数，就可以求解最优化问题,得 ，而决策函数,2,37,决策函数,其中,实现非线性分类的思想,2,38,多项式内核径向基函数内核RBFSigmoind内核,目前研究最多的核函数主要有三类：,得到q 阶多项式分类器,每个基函数中心对应一个支持向量，它们及输出权值由算法自动确

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

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

19、起来绘出类似下图。,43,用SVM实现煤炭需求量的预测,任务：用1980-2002年的我国煤炭需求量来预测2003-2006年的煤炭需求量将历年的煤炭消费量X(t)看作时间序列，则其预测模型可以描述为其中为非线形函数，p为嵌入维数， 根据上式,可以得到输入样本和输出样本,这里用1999-2002年的数据作为检验样本, 分别用SVM和神经网络预测，结果为:,用SVM实现煤炭需求量的预测,用训练好的SVM模型来预测将来2003-2006年的煤炭需求量，其需求趋势如下图：,2003-2006年的预测值,有待解决的问题,1.如何合选择SVM的参数：怎样合理选择支持向量的核参数，目前尚无定论。格子搜索法

20、比较常见，有的 学者已提出用遗传算法、粒子群算法等优化参数2.如何实现时间序列的动态预测：动态预测要求SVM的参数能适应序列的动态变化，即建立基于SVM自适应预测控制系统,2,46,SVM applications,Pattern recognitionFeatures: words countsDNA array expression data analysisFeatures: expr. levels in diff. conditionsProtein classificationFeatures: AA composition,2,47,Handwritten Digits Reco

21、gnition,2,48,Applying SVMs to Face Detection,The SVM face-detection system,1. Rescale the input image several times,2. Cut 19x19 window patterns out of the scaled image,3. Preprocess the window using masking, light correction and histogram equalization,4. Classify the pattern using the SVM,5. If the

22、 class corresponds to a face, draw a rectangle around the face in the output image.,2,49,Applying SVMs to Face Detection,Experimental results on static imagesSet A: 313 high-quality, same number of facesSet B: 23 mixed quality, total of 155 faces,2,50,Applying SVMs to Face Detection,Extension to a r

23、eal-time system,An example of the skin detection module implemented using SVMs,Face Detection on the PC-based Color Real Time System,2,51,References,Vladimir Vapnik. The Nature of Statistical Learning Theory, Springer, 1995 Andrew W. Moore. cmsc726: SVMs. http:/www.cs.cmu.edu/awm/tutorialsC. Burges.

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