计算机硬件及网络支持向量机

支持向量机引导孙宗宝2006年12月20日哈尔滨理工大学网络信息中心学术交流7/10/20231支持向量机引导孙宗宝2006年12月20日哈尔滨理工大学网络信息中心学术交流7/10/20232内容提要概述线性可分情况理论线性不可分情况支持向量机模型核函数支持向量机网络7/10/20233SVM简介90年代中期在统计学习理论的根底上开展起来的一种机器学习方法(Boser,Guyon,Vapnik)适合有限样本(小样本)问题在很大程度上解决了传统方法〔如神经网络〕中存在的问题，如过学习、非线性、多维问题、局部极小点问题等统计学习理论和支持向量机被视为机器学习问题的一个根本框架，传统的方法都可以看作是SVM方法的一种实现有坚实的理论根底和严格的理论分析7/10/20234概述一、向量的内积与超平面

7/10/20235概述二、最优分类平面7/10/20236概述二维数据最优分类线的根本要求：1、要能将两类样本无错误的分开即使经验风险最小，理论上为零

2、要使两类之间的距离最大也就是使margin最大，从而使实际风险最小7/10/20237概述我们要做的是什么呢？找到一个超平面(最优分类面)，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。7/10/20238HH2H1最优分类平面为最优分类平面的方程7/10/20239SVM原理之线性可分设线性可分样本集为(xi,yi),i=1,2,…,n,x∈Rd,y∈{+1,-1}是类别标号。那么d维空间中线性判别函数的一般形式为:g(x)=w·x+b分类面方程为:w·x+b=0(1)7/10/202310SVM原理之线性可分将判别函数进行归一化,使两类所有样本都满足|g(x)|≥1,即,使离分类面最近的样本的|g(x)|=1,这样分类间隔就等于2/‖w‖,因此间隔最大等价于使‖w‖(或‖w‖2)最小;而要求分类线对所有样本正确分类,就是要求其满足:

yi[(w·xi)+b]-1≥0,(i=1,2,…,n)(2)7/10/202311SVM原理之线性可分我们解决这样问题的思路是什么呢？首要的就是设法找到解决问题的数学模型！我们的问题是：找到满足上述式〔2〕、且使‖w‖2的分类面。其实这个分类面就是最优分类面！7/10/202312SVM原理之线性可分支持向量〔SV〕在那呢？能使式〔2〕yi[(w·xi)+b]-1≥0,(i=1,2,…,n)中等号成立的，也就是位于margin上的样本就是支持向量。7/10/202313SVM原理之线性可分最优分类平面求解的数学模型我们的求解过程显然是一个有约束条件的优化问题：即在式(2)的约束下,求函数:φ(w)=1/2‖w‖2=1/2(w·w)(3)的最小值。

7/10/202314SVM原理之线性可分求解方法---Lagrange乘子法什么是Lagrange乘子法？看一个例子。问题：给你一块面积固定〔等于a的平方〕板子，问做成什么样的长方体〔盒子〕，它具有最大的体积。7/10/202315SVM原理之线性可分Lagrange乘子法设长方体的三个棱长为x，y，z，那么其体积f为三个边长的乘积：f(x,y,z)=xyz本问题要求外表积为a的平方，于是长方体的6面的面积可以写成：2xy+2xz+2yz=a2即2xy+2xz+2yz-a2=0这个问题转化为了有约束条件的优化问题。7/10/202316SVM原理之线性可分Lagrange乘子法解题方法为：1用拉格朗日方法制造一个新函数F

2在F中放进一个未知的常数C

得到：

F=xyz+C(2xy+2xz+2yz-a2)7/10/202317SVM原理之线性可分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)7/10/202318SVM原理之线性可分Lagrange乘子法由此得出只有各个自变量的值相等才可以维持上面的关系，再由约束条件得到它们的值是：x=y=z=(a/√6)7/10/202319SVM原理之线性可分构造拉格朗日函数:L(w,b,a)=(w·w)—∑ai{yi[(w·xi)+b]-1}其中:ai>0为Lagrange系数。求式(3)的极小值就是对w和b求拉氏函数的极小值。求L对w和b的偏微分，并令其等于0,可转化为对偶问题:在约束条件aiyi=0,ai≥0,i=1,2,…,n之下对ai〉0求式(5)的最大值:7/10/202320SVM原理之线性可分W(a)=ai-aiajyiyj(xi.xj)〔5〕假设ai*为最优解，那么w*=∑i=1..nai*yixi〔6〕即最优分类面的权系数向量式训练样本的线性组合。7/10/202321SVM原理之线性可分这是一个不等式约束的二次函数极值问题，存在唯一解，并且解必须满足(Kuhn-Tucker条件):ai[yi(w*xi+b)-1]=0,i=1..n〔7〕显然，只有支持向量的系数ai不为0,即只有支持向量影响最终的划分结果。

这是为什么？

7/10/202322SVM原理之线性可分于是式〔6〕

w*=∑i=1..nai*yixi可以写成：w=aiyixi

可以看出，只有支持向量影响最终的划分结果，最优分类面的权系数向量是训练样本向量的线性组合。

〔8〕7/10/202323SVM原理之线性可分假设ai*为最优解,求解上述问题后得到的最优分类函数是:f(x)=sgn{(w*·x)+b*}=sgn{ai*yi(xi·x)+b*}其中:sgn()为符号函数,b*是分类的阈值,可以由任意一个支持向量用式(2)求得,或通过两类中任意一对支持向量取中值求得。对于给定的未知样本x,只需计算sgn(w•x+b),即可判定x所属的分类。对于非支持向量ai都为0。7/10/202324SVM原理之线性不可分对于线性不可分的样本,希望使误分类的点数最小,为此在式(2)中引入松弛变量ξi≥0,即：yi[(w·xi)+b]-1+ξi≥0,(i=1,2,…,n)〔9〕

//yi[(w·xi)+b]-1≥0,(i=1,2,…,n)(2)7/10/202325SVM原理之线性不可分在式(9)中,对于给定的常数C,求出使φ(w,ξ)=(w·w)+C{ξi}〔10〕取极小值的w,b,这一优化问题同样需要变换为用拉格朗日乘子表示的对偶问题,变换的过程与前面线性可分样本的对偶问题类似,结果也几乎完全相同,只是约束条件略有变化:aiyi=0,(0≤ai≤C,i=1,2,…,n)(11)C反映了在复杂性和不可分样本所占比例之间的折中。

7/10/202326支持向量机如果用内积K(x,x′)代替最优分类面中的点积,就相当于把原特征空间变换到了某一新的特征空间,此时优化函数变为:

W(a)=ai-aiajyiyjK(xi·xj)

相应的判别函数也应变为:f(x)=sgn{ai*yik(xi·x)+b*}

7/10/202327支持向量机算法的其他条件均不变,这就是支持向量机。所以，原问题就转化成了找SV的问题，而求SV的过程就是解一个二次规划(有约束的)，二次规划无局部极值，只有一个最值，所以SV的求解不会有不收敛或者收敛到局部极小的问题。而VC维又保证了机器的容量，不可能过学习(因为机器的结构已经固定)具体的求解方法可以参考运筹学中约束二次规划的求解7/10/202328非线性分类面非线性可分的数据样本在高维空间有可能转化为线性可分。在训练问题中，涉及到训练样本的数据计算只有两个样本向量点乘的形式使用函数 ,将所有样本点映射到高为空间，那么新的样本集为设函数 内核函数(Kernelfunction)7/10/202329一个能实现非线性关系到线性关系变换的实例取：那么7/10/202330核函数7/10/202331核函数Mercer