支持向量机引导.ppt

2019/9/17,哈尔滨理工大学网络信息中心,1,支持向量机引导,孙宗宝 2006年12月20日,哈尔滨理工大学网络信息中心学术交流,2019/9/17,哈尔滨理工大学网络信息中心,2,支持向量机引导,孙宗宝 2006年12月20日,哈尔滨理工大学网络信息中心学术交流,2019/9/17,哈尔滨理工大学网络信息中心,3,内容提要,概述 线性可分情况理论 线性不可分情况 支持向量机模型 核函数 支持向量机网络,2019/9/17,哈尔滨理工大学网络信息中心,4,SVM简介,90年代中期在统计学习理论的基础上发展起来的一种机器学习方法 (Boser,Guyon,Vapnik) 适合有限样本(小样本)问题 在很大程度上解决了传统方法（如神经网络）中存在的问题，如过学习、非线性、多维问题、局部极小点问题等 统计学习理论和支持向量机被视为机器学习问题的一个基本框架，传统的方法都可以看作是SVM方法的一种实现 有坚实的理论基础和严格的理论分析,2019/9/17,哈尔滨理工大学网络信息中心,5,概述,一、向量的内积与超平面,2019/9/17,哈尔滨理工大学网络信息中心,6,概述,二、 最优分类平面,2019/9/17,哈尔滨理工大学网络信息中心,7,概述,二维数据最优分类线的基本要求： 1、要能将两类样本无错误的分开 即使经验风险最小，理论上为零 2、要使两类之间的距离最大,也就是使margin最大，从而使实际风险最小,2019/9/17,哈尔滨理工大学网络信息中心,8,概述,我们要做的是什么呢？ 找到一个超平面(最优分类面)，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。,2019/9/17,哈尔滨理工大学网络信息中心,9,H,H2,H1,最优分类平面,为最优分类平面的方程,2019/9/17,哈尔滨理工大学网络信息中心,10,SVM原理之线性可分,设线性可分样本集为(xi, yi), i=1,2,n,xRd, y+1,-1是类别标号。 则d维空间中线性判别函数的一般形式为: g(x)=wx+b 分类面方程为: wx+b=0 (1),2019/9/17,哈尔滨理工大学网络信息中心,11,SVM原理之线性可分,将判别函数进行归一化,使两类所有样本都满足 |g(x)|1,即,使离分类面最近的样本的|g(x)|=1,这样分类间隔就等于2/w,因此间隔最大等价于使w(或w2)最小;而要求分类线对所有样本正确分类,就是要求其满足: yi(wxi)+b-10,(i=1,2,n) (2),2019/9/17,哈尔滨理工大学网络信息中心,12,SVM原理之线性可分,我们解决这样问题的思路是什么呢？ 首要的就是设法找到解决问题的数学模型！ 我们的问题是： 找到满足上述式（2）、且使w2的分类面。 其实这个分类面就是最优分类面！,2019/9/17,哈尔滨理工大学网络信息中心,13,SVM原理之线性可分,支持向量（SV）在那呢？ 能使式（2） yi(wxi)+b-10,(i=1,2,n) 中等号成立的，也就是位于margin 上的样本就是支持向量。,2019/9/17,哈尔滨理工大学网络信息中心,14,SVM原理之线性可分,最优分类平面求解的数学模型 我们的求解过程显然是一个有 约束条件的优化问题： 即在式(2)的约束下,求函数: (w)= 1/2w2= 1/2(ww) (3) 的最小值。,2019/9/17,哈尔滨理工大学网络信息中心,15,SVM原理之线性可分,求解方法-Lagrange 乘子法 什么是Lagrange 乘子法？ 看一个例子。 问题：给你一块面积固定（等于a 的平方） 板子，问做成什么样的长方体（盒子），它具有最大的体积。,2019/9/17,哈尔滨理工大学网络信息中心,16,SVM原理之线性可分,Lagrange 乘子法 设长方体的三个棱长为x，y，z，则其体积f 为三个边长的乘积： f(x,y,z)=xyz 本问题要求表面积为a 的平方，于是长方体的6面的面积可以写成 ： 2xy+2xz+2yz=a2 即 2xy+2xz+2yz-a2=0 这个问题转化为了有约束条件的优化问题。,2019/9/17,哈尔滨理工大学网络信息中心,17,SVM原理之线性可分,Lagrange 乘子法 解题方法为： 1 用拉格朗日方法制造一个新函数F 2 在F中放进一个未知的常数C 得到： F=xyz+C(2xy+2xz+2yz-a2),2019/9/17,哈尔滨理工大学网络信息中心,18,SVM原理之线性可分,Lagrange 乘子法 F对x，y，z 的三个自变量的偏微分分别为零 ，得到三个新方程式 ： yz+2C(y+z)=0 xz+2C(x+z)=0 xy+2C(x+y)=0 因为自变量仅可能是正数，把上面的式子相除得 (x/y)=(x+z)/(y+z) (y/z)=(x+y)/(x+z),2019/9/17,哈尔滨理工大学网络信息中心,19,SVM原理之线性可分,Lagrange 乘子法 由此得出只有各个自变量的值相等才可以维持上面的关系，再由约束条件得到它们的值是： x=y=z=(a/6),2019/9/17,哈尔滨理工大学网络信息中心,20,SVM原理之线性可分,构造拉格朗日函数: L(w,b,a)= (ww)aiyi(wxi)+b-1 其中:ai0为Lagrange系数。求式(3)的极小值就是对w和b求拉氏函数的极小值。求L对w和b的偏微分，并令其等于0,可转化为对偶问题: 在约束条件 aiyi=0,ai0,i=1,2,n之下对 ai0求式(5)的最大值:,2019/9/17,哈尔滨理工大学网络信息中心,21,SVM原理之线性可分,W(a)= ai - aiajyiyj(xi.xj) （5）,若ai*为最优解，则,w* = i=1n ai*yixi （6）,即最优分类面的权系数向量式训练样本的线性组合。,2019/9/17,哈尔滨理工大学网络信息中心,22,SVM原理之线性可分,这是一个不等式约束的二次函数极值问题，存在唯一解，并且解必须满足(Kuhn-Tucker条件):,aiyi(w*xi + b) - 1 = 0, i=1n （7）,显然，只有支持向量的系数ai不为0, 即只有支持向量影响最终的划分结果。 这是为什么？,2019/9/17,哈尔滨理工大学网络信息中心,23,SVM原理之线性可分,于是式（6） w* = i=1n ai*yixi,可以写成：,w=,aiyixi,可以看出，只有支持向量影响最终的划分结果 ，最优分类面的权系数向量是训练样本向量的线性组合。,（8）,2019/9/17,哈尔滨理工大学网络信息中心,24,SVM原理之线性可分,若ai*为最优解,求解上述问题后得到的最优分类函数是: f(x)=sgn(w*x)+b*=sgnai*yi(xix)+b* 其中:sgn()为符号函数,b*是分类的阈值,可以由任意一个支持向量用式(2)求得,或通过两类中任意一对支持向量取中值求得。对于给定的未知样本x,只需计算sgn(wx+b),即可判定x所属的分类。对于非支持向量ai 都为0。,2019/9/17,哈尔滨理工大学网络信息中心,25,SVM原理之线性不可分,对于线性不可分的样本,希望使误分类的点数最小,为此在式(2)中引入松弛变量i0,即： yi(wxi)+b-1+i0,(i=1,2,n) （9） /yi(wxi)+b-10,(i=1,2,n) (2),2019/9/17,哈尔滨理工大学网络信息中心,26,SVM原理之线性不可分,在式(9)中,对于给定的常数C,求出使 (w,)= (ww)+C i （10）,取极小值的w,b,这一优化问题同样需要变换为用拉格朗日乘子表示的对偶问题,变换的过程与前面线性可分样本的对偶问题类似,结果也几乎完全相同,只是约束条件略有变化:,aiyi=0,(0aiC,i=1,2,n) (11),C反映了在复杂性和不可分样本所占比例之间的折中。,2019/9/17,哈尔滨理工大学网络信息中心,27,支持向量机,如果用内积K(x,x)代替最优分类面中的点积,就相当于把原特征空间变换到了某一新的特征空间,此时优化函数变为: W(a)= ai - aiajyiyjK(xixj) 相应的判别函数也应变为:,f(x)=sgn,ai*yik(xix)+b*,2019/9/17,哈尔滨理工大学网络信息中心,28,支持向量机,算法的其他条件均不变,这就是支持向量机。 所以，原问题就转化成了找SV的问题，而求SV的过程就是解一个二次规划(有约束的)，二次规划无局部极值，只有一个最值，所以SV的求解不会有 不收敛 或者 收敛到局部极小 的问题。而VC维又保证了机器的容量，不可能过学习(因为机器的结构已经固定) 具体的求解方法可以参考运筹学中约束二次规划的求解,2019/9/17,哈尔滨理工大学网络信息中心,29,非线性分类面,非线性可分的数据样本在高维空间有可能转化为线性可分。 在训练问题中，涉及到训练样本的数据计算只有两个样本向量点乘的形式 使用函数 ,将所有样本点映射到高为空间，则新的样本集为 设函数 内核函数 (Kernel function),2019/9/17,哈尔滨理工大学网络信息中心,30,一个能实现非线性关系到线性关系变换的实例,取：,那么,2019/9/17,哈尔滨理工大学网络信息中心,31,核函数,2019/9/17,哈尔滨理工大学网络