《《支持向量机》PPT课件》由会员分享，可在线阅读，更多相关《《支持向量机》PPT课件（63页珍藏版）》请在金锄头文库上搜索。
1、支持向量机支持向量机支持向量机 nVapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(Support Vector Machine，简称SVM)。支持向量机n支持向量机方法是在近年来提出的一种新方法。n支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。支持向量机线性可分条件下的支持向量机最优分
2、界面线性可分条件下的支持向量机最优分界面 nSVM的思想：由于两类别训练样本线性可分，因此在两个类别的样本集之间存在一个间隔。对一个二维空间的问题用下图表示。支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n其中H是将两类分开的分界面，而H1与H2与H平行，H是其平分面，H1上的样本是第一类样本到H最近距离的点，H2的点则是第二类样本距H的最近点。HH1H2支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n由于这两种样本点很特殊，处在间隔的边缘上，因此再附加一个圈表示。这些点称为支持向量，它们决定了这个间隔。 HH1H2支持向
3、量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n从图上可以看出能把两类分开的分界面并不止H这一个，如果略改变H的方向，则根据H1、H2与H平行这一条件，H1、 H2的方向也随之改变，这样一来，H1与H2之间的间隔(两条平行线的垂直距离)会发生改变。n显然使H1与H2之间间隔最大的分界面H是最合理的选择，因此最大间隔准则就是支持向量机的最佳准则。n从图上可以看出能把两类分开的分界面并不止H这一个，如果略改变H的方向，则根据H1、H2与H平行这一条件，H1、 H2的方向也随之改变，这样一来，H1与H2之间的间隔(两条平行线的垂直距离)会发生改变。n显然使H1与H2之间
4、间隔最大的分界面H是最合理的选择，因此最大间隔准则就是支持向量机的最佳准则。支持向量机Best Linear Separator?支持向量机Find Closest Points in Convexcd支持向量机Plane Bisect Closest Points dc支持向量机支持向量机 支持向量机Best Linear Separator:Supporting Plane Method Maximize distanceBetween two parallel supporting planesDistance = “Margin” = 支持向量机支持向量机 支持向量机线性可分条件下的支
5、持向量机最优分界面线性可分条件下的支持向量机最优分界面n为了将这个准则具体化，需要用数学式子表达。为了方便，将训练样本集表示成 xi,yi ，i=1，N，其中xi为d维向量也就是特征向量，而yi-1，+1，即用yi是+1或-1表示其类别。对于分界面H表示成(1)(2)支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n显然H1平面到坐标原点的距离为故H1到H2的间隔为n因此欲达到Vapnik提出的使间隔最大的准则，则应使|w|最小。n必须遵守约束条件（2）支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n因此欲达到Vapnik提
6、出的使间隔最大的准则，则应使|W|最小。 而H2则为故H1到H2的间隔为 n 而下式是它必须遵守的约束条件，可改写成大于零的不等式支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n因此欲达到Vapnik提出的使间隔最大的准则，则应使|w|最小。n 对于这样一个带约束条件为不等式的条件极值问题，需要引用扩展的拉格朗日乘子理论，按这个理论构造拉格朗日函数的原则为： Minimize Subject to支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n使目标函数为最小，减去用拉格朗日乘子(乘子值必须不小于0)与约束条件函数的乘积，
7、在讨论的问题中可写成n 目标函数是二次函数，而约束条件中为线性函数，按拉格朗日理论该问题存在唯一解，根据研究扩展的拉格朗日理论的Kuhn与Tucker等人的研究，表明以下是该唯一解的充分必要条件： (3)支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面对于这样一个带约束条件为不等式的条件极值问题，为了求出最优解，拉格朗日理论中引入一种对偶函数：支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面nMaximize(4)Subject to支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面nWhere
8、 D is an NN matrix such that Dij=yiyjxixj 拉格朗日理论证明：满足上述条件 时，找LD极大值的解就是LP式的条件极小值，因此由LD可求得各个最佳值。支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面nb can be determined from *, which is a solution of the dual problem, and from the Kuhn-Tucker conditions(5)支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面nNote that the o
9、nly i* that can be nonzero in (5) those for which the constraints (2) are satisfied with the equality sign.(5)(2)支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面nMost of the constraints in (2) are satisfied with inequality signs i.e., most * solved from the dual are null.(2)支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支
10、持向量机最优分界面nWhere for all i=1,N, eitherirrelevantor(on the margin)xi Support vectorn The solution is determined by the examples on the margin. Thus 支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n只有满足约束条件(2)中等于等于的点,其拉格朗日乘子才可能不为零；而对满足约束条件(2)大于大于的样本数据来说，其拉格朗日乘子必须为零，显然只有部分(经常是少量)的样本数据的i不为零，而线性分界面的权向量w则是这些i不为零的
11、样本数据的线性组合，i不为零的样本数据也因而被称为支持向量。 支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n至此，再回顾一下线性可分条件下的支持向量机方法。n首先支持向量机的方法是明确提出一个间隔概念，并把使间隔最宽作为确定线性分界面的最佳原则。既然是间隔又有线性可分作条件，只需找到处在间隔边缘上的点，以便确定最优的间隔就行，而其它数据点的作用，只是要求所确定的间隔能保证把它们置在间隔外确定的一方就行。支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n这样一来，数据点就分成两部分，一种对确定间隔参数(体现在权向量w的确定很
12、重要，而另一类(一般说占数据的大部分)对确定间隔的参数没有直接的影响，在这个意义上说它们对确定间隔参数无关紧要。它们相应的拉格朗日乘子i是否为0，就表示了数据的这种重要性，对确定间隔参数主要的点应有i0，并称为支持向量，而其余的数据点，它的i=0，支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n一旦使LD式达极大值的数据确定下来(只有少量的*i0，其余都为0)，则最佳的权向量w也就可以利用n定下来，它们是这些支持向量数据的线性求和。 支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n如果知道哪些数据是支持向量，哪些不是，则问
13、题就简单了。问题在于哪些数据是支持向量事先并不能确定，因此这只有通过求(3)式的极大值来求解。n对(4)式的来源不要求弄懂，只需知道，它的极大值解与(3)式的极小值解是一致的就行了。因为后面还要用(4)说明一些问题。 支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n例：XOR问题的SVMn异或问题是最简单的一个无法直接对特征采用线性判别函数解决的问题。n如图所示的四个样本点。利用SVM将他们映射到一个更高维的空间，使之线性可分。支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n如采用最简单且展开不超过二次的展开：n在6维空间
14、中的最佳超平面是(6维空间)n裕量为n其二维空间投影如图所示：支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n通过支持向量的超平面是：n它对应于原始特征空间中的双曲线支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n寻找使前面(4)最大化n即Subject ton根据问题的对称性支持向量机线性可分条件下的支持向量机最优分界面线性可分条件下的支持向量机最优分界面n利用解析方法解出n所有的样本都是支持向量。nSVM的重要优点是所获得的分类器复杂度可以采用支持向量的个数，而不是变换空间的维数来刻划。因此SVM往往不像一些别的方法一
15、样容易发生过拟合(overfitting)现象。支持向量机线性不可分条件下的广义最优线性分界面线性不可分条件下的广义最优线性分界面n以上讨论的是线性可分条件下的最优线性分界面的计算方法，对于线性不可分的情况下，如果仍要使用线性分界面，则必然有部分训练样本向量被错分。在线性分界面条件下，被错分的样本从本类别训练样本占主导的决策域，进入了对方的决策域。支持向量机线性不可分条件下的广义最优线性分界面线性不可分条件下的广义最优线性分界面n在这种条件下，严格意义上的间隔已不存在，前面公式也对一些数据不适用。但是仍然可以保留求最大间隔的框架，但允许有些数据能进入间隔区，甚至到对方的决策域中。但是对这部分数
16、据的数量要严加控制。为了实行控制，可以采用的一种方法是对下式作一些改动，增加一种起缓冲作用的量i，i0 (2)支持向量机线性不可分条件下的广义最优线性分界面线性不可分条件下的广义最优线性分界面nPurpose： to allow for a small number of misclassified points for better generalization or computational efficiency. such that支持向量机Generalized OSHnThe generalized OSH is then regarded as the solution to n
17、Problem 3Subject ton Minimize支持向量机Generalized OSHnRole of C: nAs a regularization parameter (cf. Radial Basis Function, fitting).n large CMinimize the number of misclassified points.n small Cmaximize the minimum distance支持向量机Dual ProblemnProblem 4n Maximizen subject to支持向量机Dual ProblemnAs before, n
18、and b* can be determined from *, solution of the dual Problem 4 and from the new Kuhn- Tucker conditionsn where * are the values of the at the saddle point. Similar to separable case, the points xi for which i*0 are termed support vectors. (19)(20)支持向量机Dual ProblemnTwo cases:ni*1, misclassified poin
19、ts0n) using function .n：RnRm支持向量机Nonlinear Support Vector MachinenExample: All degree 2 monomials支持向量机Nonlinear Support Vector MachinenThen the training algorithm would only depend on the dot products in H, i.e., on the functions of the form (xi) (xj). nIn other words,支持向量机Nonlinear Support Vector M
20、achinenBut the transformation operator, is computationally expensive.nIf there were a “kernel function” K such that K(xi,xj)= (xi) (xj), we would only need to use K in the training algorithm. nOne example, n All the previous derivations in linear SVM hold (substituting dot product with kernel functi
21、on), since we are still doing a linear separation, but in a different space. 支持向量机Mercers Condition for Kernel FunctionnThe idea of constructing support vector networks comes from considering general forms of the dot product in a Hilbert space.n Question: Which kernel does there exist a pair H,) suc
22、h that K(xi,xj)=(xi)(xj)n Answer: Mercers condition. It tells us whether or not a prospective kernel is actually a dot product in some space.(21)支持向量机Mercers Condition for Kernel FunctionnAccording to the Hilbert-Schmidt Theory, any symmetric function K(u,v), with K(u,v)L2, can be expanded in the fo
23、rmn where i R andare eigenvalue and eigenfunction n Of the integral operator defined by the kernel K(u,v).(22)支持向量机Mercers Condition for Kernel FunctionnA sufficient condition to ensure that (21) defines a dot product in a feature space is that all the eigenvalues in the expansion (22) are positive.
24、 To guarantee that these coefficients are positive, it is necessary and sufficient (Mercers theorem) that the conditionn is satisfied for all g such that支持向量机Some Kernel Function in SVMnThe first kernels investigated for the pattern recognition problem were the following: na polynomial of degree p i
25、n the datan two-layer neural networkn Gaussian radial basis function支持向量机Some Kernel Function in SVMnwhere the kernel was chosen to be a cubic polynomial.n linearly separable case (left panel), the solution is roughly linear, indicating that the capacity is being controlledn linearly non-separable c
26、ase (right panel) has become separable支持向量机Some Kernel Function in SVMnToy Example with Gaussian Kernel支持向量机The SVM Architecture支持向量机nExample showing the binary SVM classifier trained on the Riplys data.支持向量机nExample showing the multi-class SVM classifier build by one-against-all decomposition.支持向量机
27、nExample showing the multi-class SVM classifier build by one-against-one decomposition.支持向量机nExample shows the binary classifier trained based on the Kernel Fisher Discriminant.支持向量机nExample shows the decision boundaries of the SVM classifier trained by SMO and the approximated SVM classifier found
28、by the reduced set method. The original decision rule involves 94 support vectors while the reduced one only 10 support vectors.支持向量机nExample shows the decision boundaries of the SVM classifier trained by SMO and the approximated SVM classifier found by the reduced set method. The original decision
29、rule involves 94 support vectors while the reduced one only 10 support vectors.支持向量机nExample shows the decision boundaries of the SVM classifier trained by SMO and the approximated SVM classifier found by the reduced set method. The original decision rule involves 94 support vectors while the reduce
30、d one only 10 support vectors.支持向量机nExample shows the decision boundaries of the SVM classifier trained by SMO and the approximated SVM classifier found by the reduced set method. The original decision rule involves 94 support vectors while the reduced one only 10 support vectors.支持向量机ApplicationsnP
31、attern Recognition: nhandwriting digit recognitionn3D object recognitionnFace detectionnPedestrian detectionnGender classificationnExpression recognitionnSpeaker identificationnText classification支持向量机ApplicationsnRegression Estimation: nTime series predictionnSignal Processing:n seismic signal classificationnDensity estimationnDNA sequence classification
