线性口袋算法改进了线性感知器算法

《线性口袋算法改进了线性感知器算法》由会员分享，可在线阅读，更多相关《线性口袋算法改进了线性感知器算法（13页珍藏版）》请在装配图网上搜索。

1、线性口袋算法改进了线性感知器算法，能够直接处理线性不可分问题。1、支持向量机理论1、SVM从线性可分情况下的最优分类面发展而来。H为分类线,H1, H2分 别为过各类中离分类线最近的样本且平行于分类线的直线 , 它们之间的 距离叫做分类间隔(margin)。推广到高维空间，最优分类线就变为最优分 类面。2、最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0), 且使分类间隔最大。3、SVM 考虑寻找一个满足分类要求的超平面, 并且使训练集中的点距离分 类面尽可能的远，也就是寻找一个分类面使它两侧的空白区域(margin)最 大。4、过两类样本中离分类面最近的点且平行于最优分类面的超平

2、面上 H1,H2的训练样本就叫做支持向量。|仪|仙x) + 厂乔(两(xz)帀假定训练数据(X , y ),( x , y ), x g Rn, y g +1,-1可以被一个超平面分开(w.x) + b = 0, w g RN,b g R我们进行正归化y (w- x ) + b) 1,i二1,lii2此时分类间隔等于耗使最大间隔最大等价于使I |WI2最小我们可以对它进行归一化，使得所有样本都满足|g (x)| 1，即离分类面最近的样本满足Ig(x)二1，这样分类间隔就等于乙。因此要求分类间隔最大，就是 要求加|(或|2 )最小。而要求分类面对所有样本正确分类，就是要求满足y (w-x) +

3、b) 1,i二I,.,l。因此，满足上面公式且使|2最小的分类面就是最优 ii分类面。最优分类面问题可以表示成约束优化问题Minimize(w) = |w|2 = (w - w)Subject to yi(w - xi)+ b) 1,i = 1,1定义 Lagrange 函数L(w,b,a) = +|W|2 _a (y - (x - w) + b) -1)i=1求偏导：鲁L(w,b,a) = 0 学L(w,b,a) = 0 cbcw得工ay = 0 w = Xa yxi ii i ii=1i=1将上式代入拉格朗日函数，消去w和b得到原问题的Wolf对偶(Dual)问题: minW(a)=为a

4、一 + 为aa y y (x -x )i=1i 2i j i j i ji, j=1a 0, i = 1,., l, and Xa y = 0ii ii=1f (x) = sgn(工 y a - (x - x ) + b)i ii1 一 i2 一 204x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1Q(a) = (a +a +a +a ) -(a2 一4a a + 4a2 + 4a2)1 2 3 4 2 2 2 3 3 4可调用 Matlab 中的二次规划程序，求得 a1,a2,a3,a4 的值，进而求得 w 和 b 的值。a

5、= 01a = 1 1 g ,i = 1,., liii两个目标：1间时尽可能大2错划程度工g尽可能小ii=1当0 1时，样本点X被错分。因此，引入一个惩罚 iiii2i 吋+c gi参数C 0，新的目标函数变为：min，b；=1s.ty (w - x.) + b) 1 -g, i=i,.,iiiig 0,i =1,.,li为g体现了经验风险，而| |则体现了表达能力。所以惩罚参数c实质上是对经ii =1验风险和表达能力匹配一个裁决。当C时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。1、用间隔定量地定义了置信风险：间隔越大，置信风险越小，间隔越小，置 信风险越大2、用参数 C

6、 实现了经验风险与置信风险的折中3、最优分类超平面只由少数支持向量决定，问题具有稀疏性4、模型为凸二次规划模型，没有陷入局部最优解的问题，任何局部 最优解都是全局最优解5、通过使用核方法，具备了强大的非线性处理能力注：问题具有稀疏性是指决策时可以不管非支持向量的样本，而仅用到少数 支持向量样本。注意训练时还是用到了所有的样本。核函数SVM 中不同的内积核函数将形成不同的算法,主要的核函数有三类：多项式核函数K(x,x ) = (x-x ) + cL得到q阶多项式分类器。iif x x 2径向基函数K(x,x ) = exp ib 2S 形函数 K(x,x ) = tanh(u (x- x )

7、+ c)ii对非线性分类问题，若在原始空间中的简单最优分类面不能得到满意的分 类结果，则可以通过非线性变换转化为某个高维空间的线性问题，在变换 空间求最优分类面，SVM通过核函数变换，巧妙地解决了这个问题。0(x)0(。)0(。)O高维数据空间原始数据空间0( x)核函数如何针对不同的问题选择不同的核函数仍然是一个悬而未决的问题。 由于寻找最优分类面函数只涉及到训练样本之间的点积运算，所以将样本映 射到高维空间H时，算法仅使用H空间中的点积仙(x)QKx)，而没有单独出现 0 (x.)。能够找到一个函数K使得K(x ,x )=伸(x )(x )；，这种点积运算是可以ii j ij 在原空间中的

8、函数实现的，甚至没有必要知道变换的形式。根据泛函的有关理论，只要一种核函数K(x ,x )满足Mercer条件，它就对应某一种变换空间中的点积。ij引入内积函数K(x ,x )之后，目标函数式变为：ijQ(a)二工a - + Maa y y K(x -x )i 2i j i j i ji =1i, j=1相应的分类函数式变为：f (x) = sgn(M a *y - K(x- x ) + b*)i iii=1Mercer 条件对于任意的对称函数K(x,x)，它是某个特征空间中的内积运算的充要条件x, x)*(x)*(x)dxdx 0。是，对于任意的*(x)丰0且2(x)dx 8,有JJK(在最

9、优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性 分类,而计算复杂度却没有增加。Q(a) = Ka -1 Kaa y y K(x -x )i 2i j i j i ji=1i , j =1/(x) = sgn(兰 yia 厂 K(x - xzJ + b*)其中a *，b*是模型的解。i =1i这就是支持向量机。K（X ,x ）一工 ； 持向量机就是首先通过用内积函数定义的非线性变换将输入空 间变换到一个高维空间，在这个空间中求最优分类面。支持向量机(support vector machines)是由贝尔实验室研究者Vapnik于 20世纪90年代最先提出的一种新的机器学习理论，是

10、建立在统计学习理论的 VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性 和学习能力之间寻求最佳折衷，以期获得最好的推广能力。统计方法是从事物外在的表现去推断该事物可能的规律性。统计学习理论是针对小样本情况下的机器学习理论，它依据算法的经验风 险以及算法本身的构造来推测它的实际风险，并获得较好的泛化能力。统计学习 理论将算法的训练过程看作算法向训练样本学习的过程。统计学习理论是一种专 门研究小样本情况下机器学习规律的理论，其核心概念是VC维。VC维反映了函 数集的学习能力,VC维越大则学习机器越复杂。一般地，对于N维线性空间Rn 中的VC维是N+1。但是在非线性情况下,VC

11、维通常是无法计算的。在应用统计 学习理论时，可以通过变通的办法避开直接求VC维的问题。统计学习理论从VC维的概念出发，推导出了关于经验风险和实际风险之间 关系,并得出结论是:学习机器的实际风险是由两部分组成的,一是经验风险(训练 误差),另一个是置信范围,它和学习机器的 VC 维及训练样本数有关,可以简单表 示为R(a) inf R （）， R （） p inf R （）。emp 11T8 gA11T8 gA收敛。这个充要条件在理论上有重要的意义，但是实践中一般无法直接应用。给定的对应着一个或一组超平面，其VC维与h满足下面的函数关系:h=f G），其中f（）是单调增函数，即h与分类间隔成反比

12、关系。因 此，当训练样本给定时，分类间隔越大，则所对应的VC维越小。置信范围申和学习机器的VC维及训练样本数有关，随-的变化趋势如 h图所示。n训练样本数，h： VC维，0 (h):置信范围结构化风险最小化 通常，在小样本的情况下，对于复杂的学习机器，其训练误差过小，但反而 造成了置信范围的增大，从而导致泛化性能下降。这往往是由于学习机器的结构 不合理造成的。因此， ERM 原则在样本有限时是不合理的。为此，统计学习理 论提出了一种新的策略，在保证ERM原则的基础上，降低学习机器的VC维， 能够使得期望风险在整个总体集上得到控制，即在训练误差和置信范围二者之间 寻求一个折衷。这种思想就是结构风

13、险最小化(Structural Risk Minimization，SRM) 原则。最小化算法的经验风险与置信范围之和 (而不仅仅是最小化经验风险 )被称 作结构风险最小化原则。实现SRM原则可以有两种思路：1、对函数集S的每个子集Si求最小经验风险，然后选择使最小经验风险和置 信范围之和最小的子集；2、设计函数集的某种结构使每个子集中都能取得最小的经验风险，如使训 练误差为 0，然后只需选择适当的子集使置信范围最小，则这个子集中使经 验风险最小的函数就是最优函数。所谓最优分类线，就是要求分类线不但能将两类正确分开，使训练错误率为 0， 而且还要使分类间隔最大。前者保证经验风险最小；后者保证推

14、广性界中的置信 范围最小，从而使真实的风险最小。推广到高维空间，最优分类线就成了最优分 类面。标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁 棒性是至关重要的。支持向量机的本质是解一个二次规划问题,虽然有一些经典(如对偶方法、 内点算法等),但当训练集规模很大时,这些算法面临着维数灾难问题。为此,人们 提出了许多针对大规模数据集的SVM训练算法。训练 SVM 的绝大多数算法都是针对分类问题,只有一小部分算法考虑了回归 函数的估计问题。SVM 存在两个主要问题： 二次规划的训练速度核函数的选择SVM 方法的特点(1) SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂

15、性取决于支持 向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。(2) 少数支持向量决定了最终结果 ,这不但可以帮助我们抓住关键样本、“剔 除”大量冗余样本,而且注定了该方法不但算法简单 ,而且具有较好的“鲁棒” 性。这种“鲁棒”性主要体现在: 增、删非支持向量样本对模型没有影响； 支持向量样本集具有一定的鲁棒性; 有些成功的应用中,SVM方法对核的选取不敏感。由于SVM的求解最后转化成二次规划问题的求解，因此SVM的解是全局 唯一的最优解。SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。超平面方程g(x)=O

16、定义了一个判定面，它把归类于C1的点与归类于C2的点分开来。当g(x)是线性函数时，这个平面被称为“超平面”(hyperplane)。o当 x1 和 x2 都在判定面上时，.V- + 11C = irJ + 15或怦 11,J-= 0这表明w和超平面上任意向量正交，并称w为超平面的法向量 注意到：x1-x2表示超平面上的一个向量(1) 线性判别函数利用一个超平面把特征空间分隔成两个区域。(2) 超平面的方向由法向量w确定，它的位置由阈值w0确定。(3) 判别函数g(x)正比于x点到超平面的代数距离(带正负号)。当x点在 超平面的正侧时，g(x)0；当x点在超平面的负侧时，g(x)0，则判定x属

17、于C1,如果g(x) 1 -g iiig 0,i 1A对偶模型1 ai i1min 工:,x ) 一2i j i j i ji 1 i1(4)ST. ya 0,0 a Ci iii1i 1当C=g,K(xi，x/)=(xi,劝时对应线性可分情形； 当0vCve,K(xi，x/)=(xi,劝时对应近似线性可分情形。原问题的解与对偶问题的解之间的关系：w* y a*(x )i i ii1b* y -ya*k(x ,x ) (0 a* C)ji i i jji1 分类决策函数： f (x) sgn(w*, x) + b*) sgn(ya*k(x,x)+ y -ya*k(x ,x ) i i iji

18、i i ji 1i 1这里K(xi, xj)=(xi),0 (x/)是样本xi,xj在特征空间中的内积，称为输入空间 X 上的核函数。1、KKT 条件0a 1iij j i jj=10a C o y (为y a k(x ,x ) + b) = 1iij j i jj=1a = C o y (工 y a k (x , x ) + b) 1iiig 0, i = 1,Ii（2）样本重要性不同时的对策min II w II2w,b勺 2i=1 S.T. y (w,e(x ) + b) 1-giiig 0,i =Ii1、v-SVC 模型l2p/II w II00010l : (w, x) + b = 一 pl : (w, x) + b = 00l : (w, x) + b = p+iw给定时,p越大，间隔就越大，但是间隔内的支持向量也越多，即经验风险Y g也越大，所以当w给定时，我们也可以设置一个参数代表经验风险与置i信风险的折中，或者更准确地说，这个参数可以控制间隔内的支持向量的个数。