哈工大模式识别SVM讲义，哈工大模式识别研究生课程资源数针对a的最大化,同吋考虑(7)式的约束,得到

文件名称: 哈工大模式识别SVM讲义

所属分类: 讲义

开发工具:

文件大小: 234kb

下载次数: 0

上传时间: 2019-03-03

提供者: qq_27******

下载 (234kb)

不能下载？报告错误

详细说明：哈工大模式识别SVM讲义，哈工大模式识别研究生课程资源数针对a的最大化,同吋考虑(7)式的约束,得到原始问题的对儁优化问题: 对偶优化问题 max(a)=2a1-2∑2xx (8) 约束 ≥0,i=1 22 原始优化问题和对偶优化问题都是典型的线性不等式约朿条件下的二次优化问题,求解两者中的任何一个都是等价的。但SVM算法一般求解的是对偶问题,因为它有如下两个特 l、对偶问题不直接优化权值矢量w,因此与样本的特征维数d无关,只与样本的数量 n有关。当样本的特征维数很高时,对偶问题更谷易求解 2、对偶优化问题中,训练样本只以任意两个矢量内积的形式出现,因此只要能够计算矢量之间的内积,而不需要知道样本的每一维特征就可以进行优化求解。以上两个特点使得我们可以很容易地将“核函数”引入到算法中,实现非线性的SⅥM分类。 Ⅱ.线性不可分的情况下面来看一下样本集D是线性不可分的情况。重新考察(3)式的优化问题,当样本集线性不可分时,不存在任何一个权值矢量w和偏置w能够使得作为约束的n个不等式都得到满足。通过在每个不等式上引入一个非负的“松弛变量”ξ,使得不等式变为: z(wx+w)21-5,5>0 只要选择一系列适合的松弛变量ξ,不等式约束条件总是可以得到满足的。然而,即使训练样本集是线性不可分的,我们也希望学小得到的分炎器能够正确识别尽量多的训练样本,换句话说就是希望尽量多的松弛变量ξ=0。因此冂标函数就需要同吋考虑两方面因素的优化:与分类界面和样本集之间的几何闸隔相关的|wP,以及不为0的松弛变量的数量。育接优化松弛变量的数量存在一定的难度,一般是转而优化一个相关的目标:∑5 在一个优化问题中无法同时优化两个目标,需要引入一个大于0的常数C来协调对两个优化目标的关注程度。C值越大表示我们希望更少的训练样本被错误识别,C值越小表示我们希望分类界面与训练样本集的间隔更大。这样,我们就得到了在样本集线性不可分情况下的原始优化问题: 原始优化问题 min s(w, wo w‖+ ∑5 (8) 约束: z(wx+1)21-5,1=1…n ≥0,i=1,…,n 类似于线性可分情况,针对两组不等式约束分别引入 Lagrange系数a和阝,建立 Lagrange函数: l(w20-+C5-以[:(Wx+m)-1+5]-∑5 同样道理,原始问题的优化等价于 Lagrange函数首先对w,w和ξ进行最小值优化,然后对a,β在非负的约束下进行最大值优化 Ul a zx,=O 012 aL(W, Wo, s ,a, B) az=0→ C.z.=0 9b) B 将上述3式重新代入 Lagrange函数: 4点时=f+C5-(w)1+]∑5 3:叫 xx+m0-a1+a5}∑月 ∑∑a,22xx;∑∑以2x;-"∑x2+2a1+∑(C-a1-B)5 a-∑∑aaxz X.X 可以看出,重写的 Lagrange函数与线性可分情况是完全相同的,与w,1,松孢矢量ξ 尢关,也与引入的第2组 Lagrange系数β无关。对偶优化问题与线性可分情况的唯一不同点是(9c)式引入的:a1=C-B,考虑到月≥0,因此需要增加约束a1≤C。对偶优化问题 maxL(a)=∑a1-∑∑ aa,,,, 2,Z,XX (10) 约束 C≥c,≥0,t=1, C.2 0 在线性不可分的情况下,对偶问题相比于原始优化问题要简单。线性SVM分类器的学习,就是采用二次规划算法对(10)优化问题的求解。最优化方法的研究已经证明此类问题属于凸规划问题,存在唯一的最优解,并且可以由相关算法计算求解。常用的二次规划算法包括:内点法、有效集法、椭球算法等等,而且经过研究已经找到了专门针对SVM学习的有效算法-序列最小化算法(SMO, Sequential minimal Optimization) 通过对偶问题的优化,可以得到与每个训练样本相关的组最优 Lagrange系数α。构造线性判别函数需要的是权值矢量w和偏置w,因此下面需要考虑如何由系数a计算w和 vn在此之前我们首先来看一下a中元泰的含义从前面针对a优化的分析中可以看到,c,是与(3)优化问题的第i个约束 z(wx,+w)21相关的 Lagrange系数。当约束不等式以大于1的方式得到满足时,相应的 Lagrange系数ar=0;而当约束以等于1的方式得到满足吋,系数a可以大于0。同样道理, 线性不可分情况下优化问题(8)中,由于有(9c)式中a1=C-B关系存在,因此当>0 时, Lagrange系数=0,而a1=C;当=0时,月可以大于0,相应的a可以小于C 更严格地说,依据最优化方法中的Kuhn- Tucker定理可以证明有如下关系存在: Wx.+ ((( z: WX, +w 1.C w'x,+wa>0对应的训练样本处于支持面之上;a=C对应的训练样本则处于各自类别支持面与分类超平面之间,甚至是分类界面的反方向区域(图1中黑色方框中的样木)。所有对应ax>0的训练样本称为支持向量图支持向量与 Lagrange系数借助于(9a),可以将判别函数的权值w衣示为训练样本由相应 Lagrange系数加权求和的形式: (12) 因此,由对偶优化问题的解可以直接得到判别函数的权值矢量。这里需要注意的是实际上只有支持向量参与了求和式的计算,非支持向量的系数a1为0,对w的计算没有贡献任意个处于支持面上的支持向量与分类界面之间的函数间隔为1,因此偏置w可以利用任意个对应于C>a,>0的支持向量x.由下述方程求得: z(wx+1)-1%=2-wx (13) 这样,我们就可以通过求解对偶优化问题得到一纠 Lagrange系数a,进而根据(12)和 (13)式计算线性判別函数的权值矢量w和偏置w,得到最优的线性判別函数 II非线性支持向量机将核函数引入支持向量机,将其转化为非线性分类器。支持向量机的学习过程主要是求解优化问题(10),注意创其中只涉到任意两个训练样本的内积计算,因此可以引入核函数K将其转化为(14)式进行优化,达到首先将每个训练样本由某个非线性射Φ射到特征空间,然后在特征空间中求解最大间隔超平面,对应于输入空间中的非线性分类界面非线性SⅴM的优化问题 max()=2a-∑∑ak(x,x) 约束 ∑ C,z.=0 C≥c,≥0,i=1,…,n 通过(14)优化问题的求解,可以得到每个训练样本对应的 Lagrange系数a,而要构造判别函数需要计算权值矢量w和偏置。注意到权值矢量w是一个经过Φ映射之后特征空间中的矢量,可以由(12)计算,只不过每个训练样本需要山映射之后的矢量Φ(x)米代替: w=∑az(x) (15) 但是在核方法中我们并没有直接定义映射Φ,而是通过引入核函数K来间接的达到非线性映射的的,因此无法计算每个Φ(x)。但是如果将(15)式代入特征空间中的线性判别函数: o(x)+1=∑z0(x)(x)+1=∑azK(x,x)+ 可以看出,输入空间屮的非线性SVM判别涿数只需要利用核函数计算测试样本x和训练样本x在特征空间中的内积K(xx): (x)=∑a2k(x,x,)+ (16) 偏置w,同样可以由某个满足C>c,>0的支持向量x,计算: a, 2, K(x,x (17) 这样我们看到,通过引入核函数可以实现非线性的支持向量机分类。所付出的代价是无法像线性sⅥM一样直接计算出权值矢量w,而是需要在识别的时候,采用(16)式利用核函数计算测试样本与训练样本在特征空间中的内积,从而得到判别函数的输出。由于非支持向量的 Lagrange系数a为0,因此算法只需要保存和计算所有的支持向量即可。 .多类别支持向量机支持向量机可以采用“·对多方式”和“·对·方式”,将多类别问题转化为多个两类别问题来解决,但是这两种方式都存在着尢法辨别的Ⅸ域。在支持向量机屮还可以采用一种特殊的方式进行多类别范磊。这种特殊的多类别分类方式是在原来“一对一方式”的基础之上,增加了一个“投票”的机制。首先,在学习过程屮利用任意两个类别的样本学丬出c(c-1)/2个区分两个类别的支持向量机分类器。在识別过程中,计算每一个支持向量机判别函数的输出,根据输出的正负向相关类別的“投票箱”中投入一票。例如,如果判别函数g(x)>0,则在第i的投票箱中投入一票,反之则在第j类的票箱中投入一票。最后,统计c个类別的得票数,判别x属于得票最多的类別。这个过程可以形式化的表示为: (x)=∑(g(x 如果:k= argmax v(x),则判别:x∈ak 其中Ⅰ为示性函数 I is true lo, a is false V.支持向量机的最优性结构风险最小化原则(SRM, Structural risk minimization):把函数集 S={/(xw),w∈92}分解为个函数了集序列 S,cS,c…S 各个了集按照ⅤC维的大小排序 h 在了集序列中寻找经验风险与置信范围之和最小的了集,这个了集中使经验风险最小的函数就是所求的最优函数。定理:在d维空间中,假设所有n个样本都在一个超球范围之内,超球的半径为R,那么γ-间隔分类超平面集合的VC维h满足如下不等式 h≤min R 十而间隔y=1/w,因此根据SRM的原则,只需在保证纤验风险为0的条件下(超“面能够正确分类全部训练样本),最小化权值矢量的长度w

(系统自动生成,下载前可以参看下载内容)