支持向量机网络

1、第五讲第五讲 支持向量机网络支持向量机网络目录(1/1)1 引言引言(1/13)1 引言引言(2/13)1 引言引言(3/13)1 引言引言(4/13)1 引言引言(5/13)1 引言引言(6/13)1 引言引言(7/13)1 引言引言(8/13)1 引言引言(9/13)1 引言引言(10/13)1 引言引言(11/13)1 引言引言(12/13)1 引言引言(13/13)2 SLT的基本理论(1/4)2 SLT的基本理论(2/4)2 SLT的基本理论(3/4)2 SLT的基本理论(4/4)2.1 经验风险经验风险(1/3)2.1 经验风险经验风险(2/3)( )( ,( ,)( , )R w

2、L y f x w dF x y ),(1),(0),(,wxfyifwxfyifwxfyL2.1 经验风险经验风险(3/3)liiiempwxfyLlwR1),(,1)( 机器学习的目的就是要设计学习算法,使上述风险最小,作为对R(w)的评估.2.2 经验风险最小一致性原理经验风险最小一致性原理(1/2)(inf)(wRwRwpll)(inf)(wRwRwpllemp2.2 经验风险最小一致性原理经验风险最小一致性原理(2/2) inf R(w) R(w) Remp(w) 2.3 经验风险最小归纳原理经验风险最小归纳原理(1/3)nhnhwRwRemp)4/ln() 1)/2(ln()()(

3、其中n是样本数,h是函数集的VC维.2.3 经验风险最小归纳原理经验风险最小归纳原理(2/3),()()(lhwRwRemp这里(h,l)随着h增大而增加.2.3 经验风险最小归纳原理经验风险最小归纳原理(3/3)2.4 VC维的概念维的概念(1/7)2.4 VC维的概念维的概念(2/7)2.4 VC维的概念维的概念(3/7)2.4 VC维的概念维的概念(4/7) 因此,该线性分类函数的VC维即为3.2.4 VC维的概念维的概念(5/7)2.4 VC维的概念维的概念(6/7) 因此,该矩形分类函数的VC维即为4.2.4 VC维的概念维的概念(7/7)2.5 模型复杂度和泛化能力模型复杂度和泛化

4、能力(1/4)2.5 模型复杂度和泛化能力模型复杂度和泛化能力(2/4)2.5 模型复杂度和泛化能力模型复杂度和泛化能力(3/4)2.5 模型复杂度和泛化能力模型复杂度和泛化能力(4/4)3 SVM(1/3)3 SVM(2/3)3 SVM(3/3)3.1 线性可分的线性可分的SVM(1/4)类分类为类分类为II, 0)(1I, 0)(1)(iiiixfxfxgy3.1 线性可分的线性可分的SVM(2/4)3.1 线性可分的线性可分的SVM(3/4)BPRBF3.1 线性可分的线性可分的SVM(4/4)3.1 线性可分的线性可分的SVM-最优分类面最优分类面SVM(1/5)3.1 线性可分的线性

5、可分的SVM -最优分类面最优分类面SVM(2/5) Class 1 Class 2 Class 1 Class 2 Class 1 Class 2 (a)(b)(c)3.1 线性可分的线性可分的SVM -最优分类面最优分类面SVM(3/5) Class 1 Class 2 m wTx+b=1 wTx+b=-1 wTx+b=0 r=(wTx+b)/|w| 任一样本与分界面的距离为r=(wTx+b)/|w| 因此,当选择分类的开关函数为1)(11)(1)sgn()(iiiixfxfxxg则分界面与最近邻的样本的距离为r=1/|w|3.1 线性可分的线性可分的SVM -最优分类面最优分类面SVM(

6、4/5)相应的约束条件为2,|21min|2maxwwbwbw等效nibxwyxgyiTiii,.,2 , 11)()( SVM的最优分界面的优化函数为二次型,约束条件是线性的,因此是典型的二次规划问题,可由拉格朗日乘子法求解.3.1 线性可分的线性可分的SVM -最优分类面最优分类面SVM(5/5)BPRBF3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(1/16)nibxwyxgyiTiii,.,2 , 11)()(过于严格. 对存在数据污染、近似线性分类的情况,可能并不存在一个最优的线性分类面. 如对于下图所示的分类问题,不存在严格的线性分类面3.1 线性可分的线

7、性可分的SVM 广义最优分类面广义最优分类面SVM(2/16)Class 1Class 2分类面3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(3/16) 此外,对于海量数据,求解最优分类面的时间代价大. 因此,需要发展允许有一定范围内的“错分”,又有较大分界区域的最优分类面. 实际上,广义最优分类面是在分类准确性与泛化特性上寻求一个平衡点. 上图所示的分类问题可以找到如下图所示的广义最优分类面。3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(4/16)Class 1Class 2分类面3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分

8、类面SVM(5/16)nibxwyxgyiiTiii,.,2 , 11)()(因此,SVM的广义最优分类问题可表示为如下优化问题:miibwi1 ,min相应的约束条件为3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(6/16)0|21min12 ,CCwmiibwininibxwyxgyiiiTiii,.,2 , 10,.,2 , 11)()(其中Parameter C is tradeoff parameter between error and margin and can be viewed as a way to control overfitting. C越

9、大,表示分类越严格,允许错分的样本受到的限制越大,错分的样本数少,越过拟合。 按照上述目标函数进行分类所得到的分类面也称为The Soft Margin Hyperplane incorporating slack variables。3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(6/16)3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(7/16)其中i与i为拉格朗日乘子,满足i, i0 根据拉格朗日松弛法的Kuhn-Tucker条件,有miiimiiTiiimiibxwyCwL1112)(1 |213.1 线性可分的线性可分的SVM 广义最优

10、分类面广义最优分类面SVM(8/16)000)(1 00/0/0iiiiiiiiiiiiiiiiiiwbwxyCLybLxyw3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(9/16) 只要确定i ,便可解出w,b,i, i0000)(1 00iiiiiiiiiiiiiiiiiCbwxyCyxyw3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(10/16)其中w,b,i, i可根据i计算出,即优化变量只有i. 因此,SVM广义最优分类面的优化目标函数可变换为iiiiiiiiTiiiiiCybwxywL)(|212jijTijijiiixxyyL,

11、21Cyiiii00相应的约束条件为3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(11/16)3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(12/16)6=1.4Class 1Class 21=0.82=03=04=05=07=08=0.69=010=03.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(13/16)式中的求和实际上只对支持向量进行. b*是分类阈值,可以用任一个支持向量(满足(1)中的等号)求得,或通过两类中任意一对支持向量取中值求得. Notice that 分类函数 relies on an inne

12、r product between the test point x and the support vectors （learning sample）xi 。niTiiiTbybg1*)(sgnsgn)(xxxwx3.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(14/16)jjjttsjtXyw13.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(15/16)bzXybzwzfTttsjtTjjj)()(13.1 线性可分的线性可分的SVM 广义最优分类面广义最优分类面SVM(16/16)3.2 非线性可分的非线性可分的SVM(1/12) 0 x2

13、 x 0 x 下在高维空间有可能转化为线性可分. 如下图所示的2个例子.3.2 非线性可分的非线性可分的SVM(2/12) 3.2 非线性可分的非线性可分的SVM(3/12)3.2 非线性可分的非线性可分的SVM(4/12)3.2 非线性可分的非线性可分的SVM(5/12)niiTiibyg1)()(sgn)(xxx相应的函数优化的约束条件仍然为jijiTjijiiiyyL,)()(21xxCyiiii003.2 非线性可分的非线性可分的SVM(6/12)3.2 非线性可分的非线性可分的SVM(7/12)3.2 非线性可分的非线性可分的SVM(8/12)3.2 非线性可分的非线性可分的SVM(

14、9/12)niiiibKyg1),(sgn)(xxxjijijijiiiKyyL,),(21xx 因此,非线性分类的SVM方法最后集中到核函数的选取. In practical use of SVM, only the kernel function (and not f(.) is specified. 选取适宜核函数是成功进行非线性分类的关键.3.2 非线性可分的非线性可分的SVM(10/12)则对偶问题的Lagrange函数可以写成：iiiiyw)()(xijjijjiiiyKyywF),()()(xxxiiiiiiiiiiiybCwL)()(212 因此KKT条件为 iiiiiiiiT

15、iiiiiCybwxywL)(|2123.2 非线性可分的非线性可分的SVM(11/12)0)(iiiiiybFL00iii且3.2 非线性可分的非线性可分的SVM(12/12)4 核函数(1/8)must be positive semi-definite,q 根据上述条件,构造核函数的方法有:4 核函数(2/8)(0)()(),(2XLfdxdxxfxfxxKjijiji0),(BxxxxKjTijiBK(xi,xj)=exp-|xi-xj|2/2K(xi,xj)=fT(xi)f(xj) K(xi,xj)=K1(xi,xj)+K2(xi,xj)K(xi,xj)=K1(xi,xj) 04 核

16、函数(3/8)bxxyxxfnidiTiii1) 1(sign),(4 核函数(4/8)bxxyxxfniiiii12/expsign),(其中kr(|x-xi|) 取决于两个向量之间的距离|x-xi|. 多层感知机多层感知机,核函数采用sigmoid函数K(x,xi)=tanh(b1xTxi+b2)所得到得的非线性分类器为bbxxbyxxfniiTiii121tanhsign),(4 核函数(5/8)222121212221)(xxxxxxx 4 核函数(6/8)其中k(x)为一组正交基函数,充分必要条件为对所有非恒为0的L2函数f(x),下式成立)(0)()(),(2XLfdxdzzfxf

17、zxK)()(),(1zxzxKkkk4 核函数(7/8)4 核函数(8/8)5 SVM优化方法优化方法(1/3)5 SVM优化方法优化方法(2/3)5 SVM优化方法优化方法(3/3)5 SVM优化方法优化方法-块算法块算法(1/2)5 SVM优化方法优化方法-块算法块算法(2/2)5 SVM优化方法优化方法-固定工作样本集的方法固定工作样本集的方法(1/5)5 SVM优化方法优化方法-固定工作样本集的方法固定工作样本集的方法(2/5)5 SVM优化方法优化方法-固定工作样本集的方法固定工作样本集的方法(3/5)5 SVM优化方法优化方法-固定工作样本集的方法固定工作样本集的方法(4/5)5

18、 SVM优化方法优化方法-固定工作样本集的方法固定工作样本集的方法(5/5)5 SVM优化方法优化方法-序贯极小优化序贯极小优化(1/5)5 SVM优化方法优化方法-序贯极小优化序贯极小优化(2/5)5 SVM优化方法优化方法-序贯极小优化序贯极小优化(3/5)5 SVM优化方法优化方法-序贯极小优化序贯极小优化(4/5)5 SVM优化方法优化方法-序贯极小优化序贯极小优化(5/5)5 SVM优化方法优化方法-其它改进算法其它改进算法(1/9) 因此, 的基本思想是将SVM原问题的惩罚项由线性累加 改为二次累加 .iniC121iniC 连续超松弛方法 (Successive Over Rel

19、axation, SOR) 通过在原目标函数中加一项b2,从而使其对偶问题多出一项 ,而约束条件则少了一项等式约束.5 SVM优化方法优化方法-其它改进算法其它改进算法(2/9)/221iniv 修改后的对偶问题变为边界约束条件下的二次规划问题,适合迭代求解.v 同时应用矩阵分解技术,每次只更新Lagrange乘子的一个分量,从而不需将所有样本放入内存,大大提高了收敛速度.5 SVM优化方法优化方法-其它改进算法其它改进算法(3/9)约束条件为:iniTLSebwewwebwJ1,221),(minv 定义相应的Lagrange函数,并运用KT最优条件,可得到一组线性方程.v 通过解线性方程组

20、可得到问题的解.v 该方法显示出了较低的计算代价.niebxwyiiT,.,2 , 11)(5 SVM优化方法优化方法-其它改进算法其它改进算法(4/9)5 SVM优化方法优化方法-其它改进算法其它改进算法(5/9)5 SVM优化方法优化方法-其它改进算法其它改进算法(6/9)5 SVM优化方法优化方法-其它改进算法其它改进算法(7/9)5 SVM优化方法优化方法-其它改进算法其它改进算法(8/9)5 SVM优化方法优化方法-其它改进算法其它改进算法(9/9)6 SVM方法小结方法小结(1/6)6 SVM方法小结方法小结(2/6)6 SVM方法小结方法小结(3/6)6 SVM方法小结方法小结(

21、4/6)6 SVM方法小结方法小结(5/6)6 SVM方法小结方法小结(6/6)7 SVM的应用领域和研究进展的应用领域和研究进展(1/7)7 SVM的应用领域和研究进展的应用领域和研究进展(2/7)7 SVM的应用领域和研究进展的应用领域和研究进展(3/7)7 SVM的应用领域和研究进展的应用领域和研究进展(4/7)7 SVM的应用领域和研究进展的应用领域和研究进展(5/7)7 SVM的应用领域和研究进展的应用领域和研究进展(6/7)7 SVM的应用领域和研究进展的应用领域和研究进展(7/7)8 Support Vector Regression(1/15)8 Support Vector

22、Regression(2/15)8 Support Vector Regression(3/15)eeValue offtargetPenaltye-insensitive 1-norm loss functionValue offtargetPenaltySquare loss function8 Support Vector Regression(4/15)eeValue offtargetPenaltye-insensitive 2-norm loss function8 Support Vector Regression(5/15)bxwyiii1238 Support Vector Regression(6/15)ebxwyiiiy128 Support