您好、欢迎来到现金彩票网!
当前位置:PC蛋蛋 > 最优凸分解 >

支持向量机算法设计与分析-章doc

发布时间:2019-07-31 10:12 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第四章 分解算法在第二章和第三章中,我们把基于支持向量机的分类问题和回归问题归结为一个带有线性约束的凸二次规划问题。在这一章中,我们将研究这些优化问题的求解。4.1无约束问题的提法求解约束问题的途径之一,是把它转化为一个或一系列无约束问题。对于解分类问题的支持向量机凸二次规划问题,我们用Lee和Mangasarian所提出的方法给予说明[1]。至于回归问题,读者可以参考文献[2]。4.1.1非光滑无约束问题考虑线性支持向量机的原始优化问题, (4-1)s.t., (4-2) (4-3)这个最优化问题不是严格的凸二次规划问题。为了求解方便,Lee和Mangasarian把它修改为严格的凸二次规划问题[1] (4-4)s.t., (4-5) (4-6)由约束条件(4-5)-(4-6)可知:问题关于的解应满足, (4-7)其中函数是单变量函数 (4-8)把(4-7)代入(4-4)可得到无约束最优化问题, (4-9)上述问题是严格凸的无约束最优化问题,它有唯一的最优解。但函数是不可微的,所以要用非光滑的无约束最优化方法求解。光滑无约束问题由于无约束最优化问题是非光滑的,所以不能使用通常的最优化问题解法求解,因为那里总要求目标函数的梯度和Hessen矩阵等存在。为此,Lee和Mangasarian引入非光滑函数的近似函数[1] (4-10)其中是参数。显然函数是光滑的,可以证明:当时,函数收敛于。这样无约束最优化问题就近似于最优化问题, (4-11)可以期望,当充分大时,光滑无约束问题的解会近似于非光滑无约束问题的解。因而也会近似于原始问题的解。带有核的光滑无约束问题在广义支持向量机中,Mangasarian[3]考虑下述的非线)其中是一个对称正定矩阵, (4-15)和线性情况一样,Lee和Mangasarian[1]把问题(4-12)-(2-14)转化为下述的严格凸二次规划, (4-16)s.t. (4-17) (4-18)相应于该问题的光滑无约束最优化问题为 (4-19)对于光滑的无约束问题,一些经典的算法,如:Newton-Armijo算法、BFGS算法(变度量法)、PRP共轭梯度法和Newton-PCG算法(牛顿-条件预优共轭梯度算法)都可以使用[4-5]。4.2分解算法的提出在处理具体问题时,由于存储和计算量两方面的要求,传统的处理光滑无约束问题的方法常常失效。原因是这些算法都要存储与训练集相应的核矩阵,而存储核矩阵所需的内存是随着训练集中样本点个数的平方增长的。当样本点以万计时,所需的内存已相当大。例如,当样本点数目超过10000时,存储核矩阵所需内存超过800MB。另外,这些算法往往包含大量的矩阵运算,所需的运算时间往往比较长。为了解决大规模样本集的训练问题,研究者们提出了分解算法。其基本思想是:在每一步迭代中都把训练样本集分解为两个子集合和,只对工作集中的样本进行迭代,而另一个集合中的样本所对应的拉格朗日乘子保持不变。然后,将集合中的一部分“情况最糟糕的样本点”与工作集中的一部分样本点进行交换。目前,主要的分解算法有以下几种:(1)选块算法(Chunking):它是由Boser等人首先提出的一种解决支持向量机训练存储空间问题的方法[6]。具体步骤为:首先取训练样本集合中的任意一个子集作为工作集;然后对求解最优化问题,得到支持向量并构成一个分类判别函数,并用该判别函数测试集合中的样本,将其中不满足最优化条件者按其偏离最优的程度顺序排列为侯补工作集,若中的所有样本均满足最优化条件或为空集,则程序结束,否则继续;接下来剔除中的非支持向量样本,添加中排列在前面的个样本构成新的工作集。循环往复,直到程序结束。选块算法使得核矩阵大小由降低为(是支持向量得的个数),从而大大降低了对内存的需求,在支持向量很少的情况时能获得很好的结果,当很大时,对内存的需求仍很大,难以求解。(2)Osuna的分解算法:该算法是由Osuna等人提出的[7],与Chunking算法最大的不同,也是它最大的改进之处:它将求解支持向量机的QP问题分解为一系列较小的QP问题,并且工作集的大小保持不变,对内存的需求从与呈平方关系变为线性关系,因而可以克服Chunking算法中存在的问题。由于工作集是固定大小的,所以Osuna算法的速度与的选择和的大小有着密切的关系:如果较小,则每次优化的样本少,导致算法收敛很慢;反之,子QP问题的解决仍需要花费较多的内存和较长的时间,没有体现到分解算法的优越性。在Osuna分解思想的基础上,Joachims[8]和Lin[9]分别在各自的软件包SVMLight与LIBSVM中提出了不同的工作集选择方法。在实现的细节上,Joachims对常用的参数进行缓存,并对QP问题进行了Shrinking技术,从而使算法能较好地处理大规模的训练问题。(3)SMO算法:它首先是由Platt提出来的[10],可以说是Osuan分解算法的一个特例:工作集中只有两个样本。SMO将工作集的规模减到最小,一个直接的后果就是迭代次数的增加。然而,其优点在于:两个变量的最优化问题可以解析求解,因而在算法中不需要迭代地求解二次规划问题。考虑到Platt所提出的选训练点的启发式策略得到的点有可能不是最大矛盾对点,Keerthi对SMO算法做了重要的改进[11]。4.3选块算法我们知道,对偶问题 (4-20)s.t. (4-21) (4-22)的解仅依赖于支持向量对应的样本点。如果我们事先知道哪些是支持向量,就可以仅保留与它们相应的样本点,而从训练集中删去其他样本点。对缩小的训练集,建立并求解对偶问题(4-20)-(4-22)可以得到同样的决策函数。这一事实对于大规模的实际问题非常重要,因为它往往是稀疏的,只有不太多的支持向量,有可能只需求解规模不大的优化问题。然而,究竟哪些是支持向量,我们事先是不知道的,一般来说需要采用启发式算法寻找。最简单的启发式方法是选块算法。其基本思想是:去掉对应于非支持向量的拉格朗日乘子的那些训练点,而只对支持向量计算相应的拉格朗日乘子。其详细的算法描述如下(算法4.1):(1)给定参数和。选择初始工作集,记其对应的样本点的下标集为,令。(2)针对工作集用标准优化算法求解最优化问题 (4-23)s.t. (4-24) (4-25)得最优解。(3)根据按下述方式构造:当时,取为的相应分量;当时,。检验是否在精度内满足某个停机准则,比如KKT条件。若已满足,则用构造决策函数,停止计算;否则转步骤4。(4)根据确定支持向量对应的样本点组成的集合,在集合中找到个最严重地破坏条件 (4-26)的样本点,用这个样本点和中样本点一起组成新的工作集,记相应的下标集为。(5)令,转(2)。4.4 SVMLight算法我们把的分量分成两部分:一部分属于工作集,另一部分属于固定集。若记它们对应的下标集分别为和,则优化问题(4-20)-(4-22)可表示为 (4-27)s.t. (4-28) (4-29)其中 (4-30)因为N集合中的变量在一次迭代中是固定的,于是上式中的项可以省去,于是得到只是优化B集合需要求解的子问题 (4-31)s.t. (4-32) (4-33)在选定之后,如何选取下标集呢?一个简单的办法是找一个恰有个非零分量,且使目标函数下降速度最快的方向,然后用的这些非零分量的下标组成工作集。Joachims的选择策略求解下面的线) (4-39)目标函数(4-34)可以表示为 (4-40)其中。假设是当前搜索到的解,为下一步要寻找的解,根据最速下降法,我们有 (4-41)其中,为搜索步长。由于 (4-42)从而 (4-43)如果我们能够找到使得最大的个元素,则相应的目标函数将有最大的下降量。这样有如下的寻求工作集算法。算法4.2(寻找工作集)(1)给定工作集中的元素个数,其中为偶数。(2)计算,按的降序重新排列,得到序列 (4-44)与此对应有 (4-45)(3)从序列(4-45)中的最前边依次往后取个元素,要求这些元素满足:或者,或者当时有,或者时有;再从序列的最后边依次往前取个元素,要求这些元素满足:或者,或者当时有,或者当时有。这些元素对应的下标构成工作集。注:对于步骤3中的第一种情况,,当大时,就小;对于第二种情况,,当小时,也小。这样,这两种策略保证了目标函数(4-34)取最小值。有了寻找工作集的算法后,就可以给出详细的SVMLight算法算法4.3(SVMLight算法)(1)给定工作集中元素的个数及精度要求。取初始点,令。(2)用算法4.2求工作集。(3)用标准优化算法求解问题(4-31)-(4-33),得到解,令。(4)若在精度范围内满足停机准则,则转步骤5;否则,令,转步骤2。(5)由近似最优解构造决策函数。4.5 Platt的SMO算法SMO算法是在分解算法中选取的特殊情况,即每次迭代过程中只调整相应于两个样本点和的和。这时工作集的规模已经减少到最小,原因是问题(4-27)-(4-29)有等式约束,只要变动一个乘子,就至少必须同时调整另一个乘子来保证不违反该约束。Platt所提出的SMO算法主要解决两个问题:(1)两个变量的最优化问题的解析求解;(2)如何选取工作集中的两个训练样本。为了及时更新超平面参数,Platt也提出了更新的公式。下面,我们从这三个方面详细地介绍Platt的SMO算法。(一)两个变量的解析解求解方法不失一般性,假定我们在一组解中选取。上标为old的量表示是本次优化之前Lagrange乘子的原值(初始化时可取所有)。由得 (4-46)其中和为常数,,即,从而就有,原先的目标函数可以写成 (4-47)令,,,对于 (4-48)把代入,并注意到,我们可以得到 (4-49)令,把以及代入(4-49)式的右边第二项得(注意): (4-50)其中是估计值与线)的一阶和二阶导数 (4-52) (4-53)我们知道。在的情况下,有极小值。令,可得到收敛的迭代公式, (4-54)由于必须满足且的约束条件,以下我们分别讨论和时的修正公式。1o.当 图3-1a 图3-1b 当时,;当时,,即2o.当 图3-2a 图3-2b 当时,当时,即综上所述,的取值范围为, (4-55) (4-56)其中。的无条件极值确定后,再考虑上下限的限制,最终的的递推迭代公式为: (4-57)其中当时, 不能由(4-54)式求得,这时我们可以分别计算目标函数在线段两个端点上的取值,然后将Lagrange乘子修正到目标函数较小的端点上。当两个端点上取得相同的目标函数值时,目标函数在整条线段上的取值都会是一样的,这时不必对作出修正。综上所述,计算的步骤为:(1);(2)若,则其中,然后计算;(3)若,则此时,分别对应或情况的两个端点计算,取使最小的那个端点作,再由求得。(二)选择两个训练点进入工作集BPlatt提出的原始SMO算法的选择由两重循环完成:外层循环遍历非边界样本或所有样本:优先选择遍历非边界样本,因为非边界样本更有可能需要调整,而边界样本常常不能得到进一步调整而留在边界上。循环遍历非边界样本并选出它们当中违反KKT条件的样本进行调整,直到非边界样本全部满足KKT条件为止。当某一次遍历发现没有非边界样本得到调整时,就遍历所有样本,以检验是否整个集合也都满足KKT条件。如果在整个集合的检验中又有样本被进一步优化,就有必要再遍历非边界样本。这样,外层循环不停地在“遍历所有样本”和“遍历非边界样本”之间切换,直到整个训练集都满足KKT条件为止。内层循环针对违反KKT条件的样本选择另一个样本与它配对优化工作(指优化它们的Lagrange乘子),选择的依据是尽量使这样一对样本能取得最大优化步长。对其中一个Lagrange乘子来说优化步长为,但由于核函数估算耗时较大,只用来大致估计有可能取得的步长太小。也就是说,选出使得最大的样本作为第二个样本。需要注意的是,这样的步长估计是比较粗略的,选择出来的一对样本有时可能使目标函数不能作出进一步调整。这时就要遍历所有非边界样本(非边界样本就是Lagrange乘子不在边界0或C上的样本),继续寻找能与配对优化的,如果这样的样本在非边界样本中找不到,再遍历所有样本。这两次遍历都是从随机位置开始的,以免算法总是在一开始遍历就向固定的方向偏差。在极端退化的情形,找不到与配对能作出进一步调整的,这时就放弃第一个样本。以上用KKT条件对样本所作检验都是达到一定精度就可以了,例如不等式的约束可以在1的一定允许误差范围之内,通常这一允许误差(tolerance)取0.001,如果要求十分精确的输出算法就不能很快收敛。(三)样本误差和超平面参数的更新每做完一次最小优化,必须更新每个样本的误差(Error Cache),以便用修正过的分类面对其它样本再做KKT检验,以及选择第二个配对优化样本时估计步长之用。更新Error Cache首先要重置阈值。Platt直接利用刚刚被优化的两个样本的信息在原阈值基础上作简单修正,而不是调用所有支持向量重新计算。由和可知:优化后的如果不在边界上(由KKT条件可知),则的计算公式为: (4-58)优化后的如果不在边界上(由KKT条件可知),则的计算公式为: (4-59)当都不在边界上时,两者计算所得的值相同。如果都取值为0或C,即两个Lagrange乘子都在边界上时,和以及它们之间的数都可作为符合KKT条件的阈值。这时SMO算法选择最安全的和的中点作为阈值。 (4-60)至于样本的误差,其修正公式为: (4-61)4.6 Keerthi的SMO改进算法Platt的SMO算法,每次修改都涉及值。为了进一步提高SMO的性能,Keerthi等人提出了一种不考虑值的KKT条件判别方法,并给出了一种选择最大冲突对的计算公式[11]。 设 (4-62)则: (4-63)则KKT条件可写为 (4-64) (4-65) (4-66)引入记号: ,即此时 ,即此时 ,即此时 ,即此时 ,即此时(4-64)-(4-66)就可以写成 (4-67) (4-68)注意到:,,我们有(当KKT条件满足时)。设 (4-69) (4-70)当KKT条件满足时,就有 (4-71)这样我们就可以通过直接计算,而不是每次先更新b值再来判断所得解是否满足KKT条件了。在Keerthi的改进算法中,选进工作集中的样本下标如下: (4-72) (4-73)按照上述公式所选的样本和是与KKT条件发生最大冲突的两个样本。 其算法终止条件为: (4-74)其中是一个预先设定的大于0的小数,其目的是控制算法的精度。算法终止后,超平面参数为: (4-75)4.7 改进的SMO算法的收敛性对于改进的SMO算法的收敛性证明,Lin[12]和Keerthi[13]做了很好的工作。在这一节中,我们将详细介绍Lin的工作。假设是当前解,违背(4-71)约束的工作集是,那么子问题的最小值在取值范围内的线段上取得。由,我们可定义, , (4-76)则子问题的目标函数为: (4-77)s. t. . (4-78)设是这个问题的解,且。从(4-76)可以得到 (4-79)因为是的二次函数,由Taylor公式可得: (4-80)因为 (4-81) (4-82) 则有 (4-83) (4-84)定理4.1:如果SMO的工作集是根据(4-72)和(4-73)选择的,那么对于任意的正整数k,必然存在,使得下式成立: (4-85)证明:我们考虑下面两种情况:1)设是无约束情况下取最小值所对应的变量值,由方程(4-80)可得。很显然,(由二次函数的对称性可以得到),其中。由方程(4-79)和(4-80),可得 (4-86) 2)由(4-84)可知。对于分解算法,当在工作集中时,,由可知。从而,。因为意味着是线性函数,利用,,我们有 (4-87)注意到,。如果取 (4-88)则不等式(4-85)成立。4.8解回归问题的SMO算法4.8.1. ShevadeKeerthi继提出解分类问题的SMO算法之后,又把其思想推广到解回归问题[14]。在第三章的讨论中,我们得到了非线性回归问题的对偶问题 (4-89)s.t. (4-90) (4-91) (4-92)其拉格朗日函数为 (4-93)设 (4-94)则对偶问题的KKT条件为 (4-95) (4-96) (4-97) (4-98) (4-99) (4-100) 在第三章的第五节中,我们已经证明:。则由KKT条件(4-95)-(4-100)可知 (1) 当时 (4-101) (2) 当时 (4-102) (3) 当时 (4-103) (4) 当时 (4-104)(5) 当时 (4-105)假设的定义为 (4-106) (4-107) (4-108) (4-109)同时定义和如下: (4-110) (4-111)则下述关系式成立 (4-112) (4-113)设 (4-114) (4-115)则KKT条件可以表示为: (4-116)和处理分类问题的思想一样,Keerthi等人选择进入工作集,其中 (4-117) (4-118)最终的超平面参数用下列公式计算 (4-119)4.8.2基于Platt的SMO算法,Flake和Lawrence提出了解回归问题的分解算法[15]。下面,我们从两个变量的解析求解和超平面参数的更新两个方面介绍他们的工作。(一)两个变量的解析求解我们知道回归问题的输出形式为 (4-120)假设为对偶问题的目标函数,令,则由 (4-121)知 (4-122)从而有 (4-123) (4-124) (4-125)设工作集中的两个样本下标为和,则可表示为(4-126)其中是与和无关的常数。 (4-127) (4-128)设,则 (4-129)由可得(4-130)令,则有 (4-131)由(4-131)得 (4-132)其中 (4-133)方程(4-132)是一个关于变量的隐式方程,可采用下列步骤求和:(1)令,,这里是迭代次数。(2)计算。(3)如果,那么。(4)如果,转步骤5;否则,,转步骤2。(5)计算,。(6),。(二)超平面参数的更新由于回归问题的KKT条件为当时 (4-134)当时 (4-135)当时 (4-136)当时,我们有 (4-137)当时,我们有 (4-138)如果和都取值为0或则 (4-139)由方程(4-123),我们可以得到决策函数值和的更新公式如下: (4-140) (4-141)4.9 扩展的拉格朗日支持向量机4.9.1 拉格朗日支持向量机为了更清楚的描述问题,我们引进一些新的记号。表示空间中的向量,它的负数分量被置为零。代表一个的实数矩阵,和分别表示矩阵的第i行和第j列。定义阶对角矩阵,根据每个样本点的类别,规定矩阵对角线的向量。为单位矩阵。由于原始支持向量机不是严格凸二次规划,Mangasarian通过在目标函数中增加,把它转化成一个严格凸二次规划[16]。 (4-142)s.t. (4-143)上述优化问题的Lagrange函数为 (4-144)分别对求偏导,并分别令其为零,得到 (4-145)将(4-145)带入式(4-144),可得下述对偶问题 (4-146)设 则对偶问题(4-146)就变成: (4-147)设 ,则优化问题(4-147)的KKT条件为: (4-148)从而 (4-149)上述问题可以用下述迭代公式求解。 , (4-150)对于该迭代公式,可以证明,只要满足条件 (4-151)从任意初始点开始逐步迭代,都可以线)的全局最优解。通常我们可以取。应用SMW等式,Mangasarian用下式求 (4-152)这样就把一个求矩阵的逆的问题转化成了求矩阵逆的问题。我们知道,对应的是样本数,它往往是成千上万的,而则是样本的属性数,它往往只有几十个。可见利用SMW等式,求逆的难度大大下降了。它不仅使得的求解变得可行,而且快速地对其求解,从而使得LSVM算法在处理线性分类问题时达到一个非常快的速度。对于非线)不能用,只能直接求解,这就导致在这种情况下,它只能处理中小型样本,而不能处理大样本数据的训练问题。4.9.2 为了让LSVM机能够解大规模的非线性分类问题,我们提出了扩展的拉格朗日支持向量机算法(Extended Lagrangian Support Vector Machine, ELSVM)[17]。其基本想法是:当处理大规模的非线性分类问题时,我们首先对问题进行分解,用SVMLight算法寻找进入工作集的样本,然后用LSVM求解规模较小的子二次规划问题。这样以来,我们一方面可以扩大工作集的规模,另一方面可以充分利用LSVM机快速求解中小规模问题的优势。下面,我们先给出ELSVM的优化公式,然后给出详细的算法。 对于线性分类问题,ELSVM所要优化的问题为: (4-154)根据分解算法,将变量分解成两部分B和N,于是上式可变为 (4-155)因为集合N是固定集合,在一次迭代中,N中的变量值不发生变化,因此,项的值可以视为常数,于是式(4-155)可简化为 (4-156)令 (4-157)子问题可改写成 (4-158)其中 (4-159)对于非线)求的迭代公式为, (4-162)算法4-4(ELSVM算法)(1)给定工作集中元素的个数及精度要求。取初始点,令。(2)用算法4.2求工作集。(3)用公式(4-162)求解问题(4-158),得到解,令。(4)若在精度范围内满足停机准则,则转(5);否则,令,转(2)。(5)由近似最优解构造决策函数。我们对UCI中的五个数据库分别应用SVMLight,LSVM,ELSVM进行了学习,实验结果表明:对于非线性分类问题,LSVM在小样本集上具有最快的学习速度,但在大样本集上,由于存在求逆的困难,它的学习时间非常长。对于ELSVM来说,它不仅可以高效地求解大规模学习问题,而且它的速度比SVMLight快将近一半以上。参考文献[1] Lee, Y. J., Mangasarian, O. L., SSVM: smooth support vector machine for classification, Computational Optimization and Application, 2001, 20(1): 5-22.[2] Lee, Y. J., Hsieh, W. F., and Huang, C. M., Epsilon-SSVR: a smooth support vector machine for epsilon-insensitive regression, IEEE Transactions on Knowledge and Data Engineering, 2005, 17(5): 678-685.[3] Mangasarian, O. L., Generalized support vector machines, In Smola, A., Bartlett, P., Sch?lkopf, B., and Schuurmans, D., editors, Advances in Large Margin Classifiers, pages 135-146, Cambridge, MA, 2000. MIT Press. /math-prog/tech-reports/98-14.ps.[4] 邓乃扬,田英杰,数据挖掘中的新方法-支持向量机,北京:科学出版社,2004。[5] 袁亚湘,孙文瑜,最优化理论与方法,北京:科学出版社,1997。[6] Boser, E. B., Guyon. M., Vapnik. V., A training for optimal margin classifiers, Proceedings of the 5th Annual Workshop on Computational Learning Theory (COLT’~cjlin/libsvm.[10] Platt, J. C., Fast training of support vector machines using sequential minimal optimization, In Sch?lkopf, B., Burges, C. J. C., & Smola, A. J. (Eds.), Advances in Kernel Methods-Support Vector Learning, Cambridge, Massachusetts: The MIT Press, 1999, 185-208[11] Keerthi, S. S., Shevade, S. K., Bhattacharyya, C., Murthy, K. R. K., Improvements to Platt’s SMO algorithm for SVM classifier design. Neural Computation, 2001, 13(3): 637-649[12] Lin, C. J., Asymptotic convergence of an SMO algorithm without any assumptions, IEEE Transactions on Neural Networks, 2002, 13(1): 248-250.[13] Keerthi, S. S., Gilbert, E. G., Convergence of a generalized SMO algorithm for SVM classifier design, Machine Learning, 2002, 46: 351.[14] Shevade, S. K., Keerthi, S. S., Bhattacharyya, C., Murthy, K. R. K., Improvements to the SMO algorithm for SVM regression, IEEE Transactions on Neural Networks, 2000, 11(5): 1188 – 1193.[15] Flake, G. W., Lawrence, S., Efficient SVM regression training with SMO, Machine Learning, 2002, 46(1-3): 271-290.[16] Mangasarian, O., Musicant, D., Lagrangian support vector machines, Journal of Machine Learning Research, 2001, 1: 161-177.[17] Yang X. W., Shu, L., Hao Z. F., Liang Y. C., Liu G. R. and Han X., An extended Lagrange support vector machine for classification, Progress in Natural Science, 2004, 14(6), 519-523.第五章 最小二乘支持向量机无论对于二分类问题还是回归问题,Vapnik等人所提出的原始支持向量机都需要解一个带不等式约束的二次规划问题[1-3]。1998年,基于等式约束,Saunders, Gammerman 和Vovk提出了岭回归在高维特征空间中的具体形式,并利用核技巧给出了它的对偶形式[4]。1999年,基于等式约束和最小二乘损失函数,Suykens和Vandewalle提出了解二分类问题的最小二乘支持向量机[5],至于解回归问题的最小二乘支持向量机,它实际上是一种岭回归。2002年,针对带噪声的回归问题,Suykens等人提出了加权最小二乘支持向量机[6]。2004年,Zhang,Zhou和Jiao提出了隐空间支持向量机[7],2005年,王玲等人给出了它的最小二乘版本[8],2007年,针对分类问题,Wang和Chen提出了一种基于矩阵模式的最小二乘支持向量机[9]。目前,最小二乘支持向量机在分类和回归中得到了广泛的应用,取得了很好的效果[10-13]。在本章中,我们将详细地介绍最小二乘支持向量机的原理、解法和稀疏化问题。5.1最小二乘支持向量机在这一节中,我们将首先给出分类问题和回归问题的支持向量机公式,然后指出,在最小二乘支持向量机的框架下,分类问题的公式可以转化为回归问题的公式。5.1.1分类问题对于二分类问题,假设训练集由个样本点组成, (5-1)其中,是输入向量,是所属的类别。基于等式约束和最小二乘损失函数,1999年,Suykens和Vandewalle给出了下面的优化问题[5] (5-2)s. t. (5-3)式中是权向量,是正则化参数,是误差变量,从输入空间到高维特征空间的非线性映射,是一个偏量。对应于优化问题(5-2)-(5-3)的拉格朗日函数为 (5-4)其中是拉格朗日乘子,我们称对应于的样本点为支持向量。 相应的KKT条件为 (5-5) (5-6) (5-7) (5-8)可以表示为下列方程组的形式 (5-9)式中 令,则方程(5-9)可以表示为 (5-10) 解方程(5-10)得到和后,对于新的输入向量, 其类别可以根据下式进行判别 (5-11)5.1.2回归问题对于回归问题,假设训练集由个样本点组成, (5-12)其中,是输入向量,是相应于的输出。在Saunders, Gammerman 和Vovk所提出的岭回归公式中[4],令, 则最小二乘支持向量机的优化问题为 (5-13)s. t. (5-14)式中是权向量,是正则化参数,是误差变量,从输入空间到高维特征空间的非线性映射,是一个偏量。对应于优化问题(5-13)-(5-14)的拉格朗日函数为 (5-15)其中是拉格朗日乘子,我们称对应于的样本点为支持向量。 相应的KKT条件为 (5-16) (5-17) (5-18) (5-19)可以表示为下列方程组的形式 (5-20)式中 ,。解方程(5-20)得到和后,对于新的输入向量, 其输出值可以根据下式进行计算 (5-21)5.1.3分类问题和回归问题的统一在方程(5-3)的两边同时乘以得 (5-22)令 (5-23)则优化问题(5-2)-(5-3)可以表示为 (5-24)s. t. (5-25)这个优化问题与(5-13)-(5-14)是一样的。这说明,在最小二乘支持向量机的框架下,分类问题和回归问题的求解方程是一样的。因此,在本章中讨论相关算法时,如果不作特殊声明,我们以回归问题为例进行讨论。5.2最小二乘隐空间支持向量机设训练集由(5-12)给出,定义一个由实值函数集合构成的向量 (5-26)则向量将维输入空间上的点映射到一个维空间上。由于函数集合所起的作用类似于前向神经网络中的隐单元,因而将称为隐函数,相应的空间称为隐空间或特征空间。考虑一种特殊的隐函数:实对称核函数,即,令,则相应于输入空间的隐空间为 (5-27)在隐空间中构造最优分类超平面可以得到模式识别隐空间支持向量机[7] (5-28)s.t. (5-29) (5-30)由于,所以隐空间支持向量机在决策时将会用到所有的训练样本。对于大规模的问题来说,这是不现实的。基于最小二乘的思想,在隐空间中构造最优超平面,王玲等人给出了最小二乘隐空间支持向量机[8] (5-31)把(5-27)代入式(5-31)得 (5-32)上述表达式可写为 (5-33)去掉常数项,则(5-33)等价于下列标准二次规划问题 (5-34)其中 (5-35) (5-35) (5-36)由于对任意的,下式成立 (5-37)所以矩阵是对称正定的,从而 (5-34)是一个无约束凸二次规划,可以用共轭梯度法进行求解。5.3基于矩阵模式的最小二乘支持向量机考虑输入模式为矩阵的两分类问题。设训练集为 (5-38)其中,是输入模式,是模式所属的类别。对于集合中的所有模式,要求下式成立 (5-39)其中是决策函数,是待求的维向量,是待求的维向量。考虑到是矩阵,是维向量,对于固定的,集合可以转化为集合 (5-40)在集合上,Wang 和Chen给出了最小二乘支持向量机公式[9] (5-41)s. t. (5-42)优化问题(5-41)-(5-42)的拉格朗日函数为, (5-43)相应的KKT条件为, (5-44) (5-45) (5-46) (5-47)方程(5-44)-(5-47)可以表示为下列方程组的形式 (5-48)式中 , 。 由于方程组(5-48)的系数矩阵中有未知向量,所以需要用迭代法进行求解。的修正可以采用最速下降法。由, (5-49)可得, (5-50)式中是学习率,是迭代次数。该算法的详细步骤如下(算法5.1):(1)初始化参数,,和,设置。(2)从矩阵模式空间出发,计算向量模式空间。(3)解方程组(5-48)得到和,然后用方程(5-44)计算。(4)用方程(5-50)修正向量。 (5)如果,则算法终止;否则,,转 (2)。目前,该算法只能处理线性情况。与原始的最小二乘支持向量机相比,它的主要优势在于:它可以大大减少权向量的维数(原始支持向量机需要存储的权向量维数为,基于矩阵模式支持向量机需要存储的权向量维数为)。5.4最小二乘支持向量机的求解算法5.4.1超松弛算法我们知道方程组(5-20)的系数矩阵不是正定的,此时许多解线性代数方程组的高效算法不能直接使用。为了克服这个困难,我们首先对(5-20)进行变形。显然,从(5-20)中,我们可以得到下面的方程组[14-15] (5-51)式中 (5-52) (5-53)方程组(5-51)中的未知变量和可以通过下述步骤得到:(1)解方程组 (5-54) (5-55)得到和(2)计算 (5-56)(3)计算未知变量和 (5-57) (5-58) 从上面的分析中,我们可以看到,只要解出方程(5-54)-(5-55)中的和,我们就可以得到变量和。方程(5-54)和(5-55)可以写成统一的形式 (5-59)由于是对称正定的,所以我们可以用LU分解法或超松弛迭代法求解方程组(5-59)。5.4.2共轭梯度算法共轭梯度法是最著名的共轭方向法,它首先由Hestenes 和Stiefel提出来作为解线]。由于解线性代数方程组等价于极小化一个正定二次函数,1964年,Fletcher 和Reeves提出了无约束极小化的共轭梯度算法[17],它是直接从Hestenes 和Stiefel解线性代数方程组的共轭梯度法发展来的。共轭方向法的基本定理告诉我们,共轭性和精确线性搜索产生二次终止性,共轭梯度法就是使得最速下降方向具有共轭性,从而提高算法的有效性和可靠性。对于方程组(5-34),我们可以用共轭梯度算法求解,其详细的步骤如下[18](算法5.2):(1)给定初值,,令,。(2)当时,计算 (5-60) (5-61) (5-62) (5-63) (5-64)转(3);否则转(4)。(3) ,转(2)(4)输出,程序终止。Suykens等人利用共轭梯度算法解线),其详细的步骤如下[13,15,19]:(1)利用共轭梯度算法解线)计算。(3)根据方程(5-57)和(5-58),计算未知变量和,得到线改进的共轭梯度算法基于降阶策略,2005年,Chu等人对求解线)的共轭梯度算法进行了改进[20]。为了说明Chu的方法,我们首先给出两个定理。定理5.1假设对称正定矩阵 (5-65)其中,,。那么矩阵 (5-66)是正定矩阵。证明:设 (5-67)则有 (5-68)因为是正定矩阵,所以也是正定矩阵,从而也是正定矩阵。 定理5.2设是线)是(5-20)的解。 证明:因为是正定的,所以是唯一的。由(5-66)和(5-69)得 (5-72)把(5-71)和(5-72)写成矩阵形式,我们可以得到 (5-73)其中。由于,所以和是(5-20)的。从(5-69)可知,改进的共轭梯度算法只需求解一个阶数为的线性代数方程组即可,与Suykens等人所采用的共轭梯度算法(需要解两个阶数为的线性代数方程组)相比,至少会节省大约50%的计算时间。5.4.4 Chua算法 从方程组(5-20),我们可以得到和,从而 (5-74) (5-75)只要我们能够求出,则变量和就可以直接计算出来。受Mangasarian和Musicant的启发[21],Chua利用Sherman-Morrison- Woodbury (SMW)矩阵等式[22] (5-76)把一个矩阵的求逆降成了一个矩阵的求逆。这种方法仅适用于线性核的情况。对于非线性情况,由于一般是不知道的,所以无法用(5-76)计算。5.4.5 Keerthi的SMO算法2003年,Keerthi等人提出了用SMO算法解最小二乘支持向量机的方法[23]。设 (5-77) (5-78) (5-79) (5-80)则优化问题(5-13)-(5-14)可以表示为 (5-81)s. t. (5-82)上述问题的拉格朗日函数为 (5-83)相应的KKT条件为 (5-84) (5-85)从而,其对偶问题为 (5-86)s. t.. (5-87)对偶问题(5-86)-(5-87)的拉格朗日函数 (5-88)定义 (5-89)其中 (5-90)则相应于对偶问题(5-86)-(5-87)的KKT条件为 (5-91)定义 (5-92) (5-93) (5-94) (5-95)Keerthi等人选冲突对进入工作集B进行优化,当达到最优时。从数值计算的考虑,该算法的终止条件为 (5-96)其中 (5-97) (5-98) (5-99)公式(5-97)-(5-98)中的的更新公式为 (5-100)令 (5-101)由(4-80),(4-83)和(4-84)可得: (5-102)由于 (5-103)所以公式(5-96)中的的更新公式为 (5-104)5.5最小二乘支持向量机的稀疏化算法从方程(5-7)和(5-18)可以看出,无论对于分类问题还是回归问题,拉格朗日乘子都与误差成正比。一般来说,误差大部分不等于0,因此最小二乘支持向量机的解常常是非稀疏的,这是它最主要的缺点。在5.2中,我们介绍了一些求解最小二乘支持向量机的主要算法,如超松弛算法[14]、共轭梯度法[13,15,19]、降阶法[22] 和SMO算法[23]。从计算的角度看,这些算法是非常吸引人的。但是,用这些算法得到的解是非稀疏的,这极大地限制了最小二乘支持向量机的应用。因为在解非稀疏的情况下,几乎所有的训练数据都对最终的决策函数起作用,在学习样本大的情况下,预测就非常慢。为了得到稀疏解,人们在剪枝算法方面开展了一些重要的研究。Suykens等人提出了基于最小拉格朗日乘子绝对值的剪枝方法[15],Kruif和Vries提出了基于最小目标误差的剪枝方法[24],Hoegaerts等人对各种剪枝方法进行了比较[25]。考虑到重新训练的代价,Zeng和Chen提出了基于SMO的剪枝方法[26],杨晓伟等人提出了基于增量学习和逆学习的自适应剪枝算法[27]。在这节中,我们将详细地介绍相关的工作。5.5.1基于最小拉格朗日乘子绝对值的剪枝算法考虑到,Suykens等人认为,相应于比较小的样本对最终的决策影响较小,从而提出了基于最小拉格朗日乘子绝对值的剪枝算法[15]。其算法的详细步骤如下(算法5.3):(1)设原始训练集为,,解相应于集合的线性代数方程组得到拉格朗日乘子;(2)对进行升序排列,从集合中删除对应前5%的样本点,得到剩余样本点组成的集合;(3) 解相应于集合的线性代数方程组得到新的拉格朗日乘子;(4)如果学习机的性能下降,则输出与集合对应的和b,剪枝过程结束;否则,,转(2)。5.5.2基于最小剪枝误差的剪枝算法考虑到Suykens等人的剪枝策略不一定能保证剪枝误差最小,2003年,Kruif和Veries提出了一种基于最小剪枝误差的剪枝算法[24]。设 (5-105) (5-106) (5-107) (5-108)则方程组(5-20)可表示为 (5-109)当时,线)是一样的;令,则方程组(5-110)中得。令 (5-111) (5-112) (5-113)则方程组(5-109)可表示为 (5-114)当时,由得 (5-115)当时。设 (5-116)由 (5-117)可得 (5-118)从而线)得 (5-120)式中是第个元素为1,其余元素均为0的列向量。当时 (5-121)设样本在第次迭代时的输出为 (5-122)如果在第次迭代时样本被从训练集中删除,那么此时的输出为 (5-123)从而,由方程(5-121)可知,由于移去而在上所产生的输出差为 (5-124)其中 (5-125)在Kruif和Veries的策略中,他们将相应于最小的样本移去,从而达到稀疏化的目的。5.5.3基于SMO的剪枝算法2005年,Zeng 和Chen认为,在Kruif和Veries的剪枝策略中,由于需要计算,剪枝所花费的计算时间可能比较长,从而提出了一种基于SMO的剪枝策略[26]。优化问题(5-81)-(5-82)的对偶目标函数为 (5-126)令 (5-127)则(5-126)可表示为 (5-128)当把样本点(相应的拉格朗日乘子为)从训练集中移去时,新的对偶目标函数为 (5-129)其中 (5-130) (5-131)从而,由样本点所引起的目标函数差为 (5-132)在Zeng 和Chen的算法中,相应于最小的样本被移去。其详细的剪枝步骤如下(算法5.4):(1)设原始训练集为,,用SMO解相应于集合的线)把相应于最小的样本点从集合中移去,得到剩余样本点组成的集合。对于的样本点,用修正。为了快速,移去样本点的过程可以连续进行次;(3) 用SMO解相应于集合的线)如果学习机的性能下降,则输出与集合对应的和b,剪枝过程结束;否则,,转(2)。5.5.4基于增量学习和逆学习的自适应剪枝算法剪枝算法的计算费用包括剪枝点的确定和最小二乘支持向量机的重训。在前边所介绍的剪枝算法中,人们采用的是从上到下的策略,为了得到最小二乘支持向量机的稀疏解,必须先解原始的非稀疏最小二乘支持向量机。对于大的分类问题,这可能是不实际的,因为这将花费大量的时间。为了不直接解初始的线性代数方程组,受Cauwenberghs和Poggio的影响[27],我们采用块增量学习从下而上解决这个问题。为了防止工作集的规模太大,我们交替使用逆学习策略进行剪枝。这样我们的算法可以自适应地得到稀疏解。详细的算法步骤如下[28](算法5.5).(1)初始化工作集, 其中必须存在;(2)解线)式构建当前分类器;(3)用检测工作集以外的样本,若有样本被错分,则把该样本加入工作集;当工作集中的元素达到 时,做块增量学习,得到分类器,相应的工作集记为;(4)对与分类器相应的工作集运用逆学习算法,得到分类器,相应的工作集记为;(5)用检测后继样本,如果错分,则更新当前分类器为,,否则更新当前分类器为,;(6)判断程序停止条件是否满足。如果不满足,则转(3)。(1)块增量学习不失一般性,假设工作集规模为的最小二乘支持向量机已经建立。设 (5-133)方程(5-10)可以写为 (5-134)当个新的数据点, , , 被选入当前工作集时,可以得到, (5-135)其中, (5-136), (5-137), (5-138), (5-139). (5-140)矩阵可以利用得到: , (5-141)其中可以由下式得到. (5-142)这样,可以采用增量的方式计算,同时避免了大矩阵逆计算。(2)逆学习考虑工作集中包含个数据点的LS-SVM已经建立,则逆学习的过程如下(算法5.6):(1)根据一定的剪枝策略,从工作集中删除一个数据点;(2)对新的工作集重新进行学习,构造新的分类器。当从工作集中删除一个数据点之后,方程(5-122)可以表示为. (5-143)设, ,工作集中的第个数据被删除。则可以表示为[18]: (5-144)(3)剪枝策略在自适应剪枝算法中,我们采用了两种剪枝策略。第一个策略是把相应于最小的数据点从集合中删除,称为第一剪枝策略;第二个是把相应于最小的数据点从集合中删除[14],称为第二剪枝策略。其中。 (4)停机条件在新的算法中,我们采用的程序停止条件是:,是目标函数的上次循环值,是本次循环值,的值仅由中的数据决定。(5)数值模拟为了说明算法的效果,我们用VC++ 6.0编写了相关算法,并在内存为256MB、CPU为800 MHz的PC机上测试了UCI的5个数据集。数据集的详细描述如下: The Tic-Tac-Toe dataset:该数据集有958个样本,9个属性,两类。我们用900个样本进行训练,剩余的58个样本进行测试。The Image Segmentation dataset:该数据集有2310个样本,19个属性,7类。我们分别把1-4类和5-7类归为+1类和-1类,用2200个样本进行训练,110个样本进行测试。The King+Rook versus King+Pawn on a7 (KRKPA7) dataset:该数据集有3196个样本,36个属性,2类。我们用3000个样本进行训练,196个样本进行测试。The Sat Image dataset: 该数据集有6435个样本,36个属性,6类。我们把1,2,5类归为+1类3,4,7类归为-1类,用2435个样本进行训练,4000个样本进行测试。The White King and Rook against Black King (KRK) dataset: 该数据集有28056个样本,6个属性,18类。我们分别把zero~twelve类归为+1类,其余的归为-1类。从数据集中随机地选择15000个样本,3000个进行训练,12000个进行测试。在我们的实验中,我们采用了网格法寻找最优超参数,核函数为RBF核函数,10折交叉验证策略被采用测试算法的精度和速度。一些初始参数设置如下:。和SMO算法[11]的比较结果以及相关最优参数列在表1-表5中,块的大小和支持向量机数目、训练速度、测试精度之间的关系被显示在图1-图3中。表1文[28]的方法和SMO算法在Tic-Tac-Toe数据集上所得到的结果比较AlgorithmsPruningStrategiesTraining Time (seconds)# of SVsTrainingAccuracyTestingAccuracySMO256.008.00302.53108991.0000001.000000TheProposedAlgorithmStrategy One264.008.000.7360570.9990000.998276316.008.001.78351310.9935560.9965525256.008.000.98951030.9944440.9913797256.008.001.20581300.9698890..008.000.92031250.9591110.958621StrategyTwo2512.008.000.7352580.9977780.9982763128.008.001.2468930.9941110.9965525512.008.001.0736990.9887780.9827597128.008.002.74901620.9767780..008.001.80181480.9698890.958621表2文[28]的方法和SMO算法在Image Segmentation数据集上所得到的结果比较AlgorithmsPruningStrategiesTraining Time (seconds)# of SVsTrainingAccuracyTestingAccuracySMO8.0016.00572.793521921.0000000.980734TheProposedAlgorithmStrategy One28.0016.0018.51762130.9963640.97798234.0016.0018.75692290.9954090.97614751.0016.0022.49942570.9916820.97798278.0016.0025.04303110.9920450.977064108.0016.0024.82783350.9876360.974312StrategyTwo24.0016.0062.23962580.9947730.981651364.0016.0091.04173050.9965910.97798251.0016.0044.75142880.9893180.98073472.0016.0049.77273160.9904550.977982102.0016.0076.11063580.9880000.974312表3 文[28]的方法和SMO算法在KRKPA7数据集上所得到的结果比较AlgorithmsPruningStrategiesTraining Time (seconds)# of SVsTrainingAccuracyTestingAccuracySMO32.002.003476.345829971.0000000.996429TheProposedAlgorithmStrategy One2128.004.0019.80641360.9996000.99081632.004.0040.52852820.9867670.98316352.004.0026.49422940.9765000.97551071.004.0045.24513720.9709330.972959101.004.0036.11373940.9657670.969388StrategyTwo2256.004.0060.42482480.9920000.987245364.004.0053.49282660.9906330.98622451.004.0099.65963620.9766330.98265372.004.0055.29353360.9730670.971429101.004.0080.62014090.9669330.967857表4文[28]的方法和SMO算法在Sat Image数据集上所得到的结果比较AlgorithmsPruningStrategiesTraining Time (seconds)# of SVsTrainingAccuracyTestingAccuracySMO8.0032.001237.0424291.0000000.979325TheProposedAlgorithmStrategy One21.0032.0026.76251290.9988090.97360031.0032.0028.30771470.9945380.96672551.0032.0026.49311730.9946200.97015071.0032.0027.55871970.9937990.970575101.0032.0022.43211750.9946610.971425StrategyTwo21.0032.0038.79391530.9976590.97397531.0032.0037.25481550.9983570.97347551.0032.0029.14991570.9971250.97307571.0032.0025.54261580.9956060.972800101.0032.0025.76921790.9937990.973000表5文[28]的方法和SMO算法在KRK数据集上所得到的结果比较AlgorithmsPruningStrategiesTraining Time (seconds)# of SVsTrainingAccuracyTestingAccuracySMO512.004.0031486.169829971.0000000.972100TheProposedAlgorithmStrategy One2128.004.0016.51762410.9976000.9849673128.004.0018.79323240.9875330.972650564.004.0035.36005670.9647000.9508427256.004.0036.03786280.9477330..004.0047.26227150.9265330.914625StrategyTwo2128.004.00147.11453280.9893000.975692332.004.00236.76853870.9837330.9717505128.004.00618.19285860.9645000.9483837256.004.00431.83586060.9483670..004.00402.69616520.9367000.921100从表1-表5可以看出,无论使用第一剪枝策略还是第二剪枝策略,在测试的所有数据集上,我们都得到了最小二乘支持向量机的稀疏解。与Keerthi 的SMO算法相比,我们的算法不仅学习速度快,而且在的情况下测试精度也没有大的损失。 (1-a)Tic-Tac-Toe 数据集 (1-b) Image Segmentation数据集 (1-c) KRKPA7数据集 (1-d) Sat Image数据集 (1-e) KRK数据集图1 两种剪枝策略在不同的数据集上所得到的支持向量数和块的大小之间的关系 (2-a) Tic-Tac-Toe数据集 (2-b) Image Segmentation数据集 (2-c) KRKPA7数据集 (2-d) Sat Image数据集 (2-e) KRK数据集图2 两种剪枝策略在不同的数据集上所得到的测试精度和块的大小之间的关系从图1和图2可以看出,支持向量数和测试精度均与块的大小之间存在非线性关系。大多数情况下,支持向量

  ·2014年高考英语(大纲版)总复习“语法专题”训练:专题二 情态动词和虚拟语气(课前体验领悟+课堂考前讲练+课后演练提升) Word版含答案( 2013高考).doc

  ·工艺工法QC山西体育馆异形梁柱节点施工工法(复合玻璃钢模板).doc

  ·【精选资料】叉形叶根刀r刀片加工效率提升问题研究_本科毕业论文.docx

  ·九年级物理全册 第二十一章 第一节 现代顺风耳——电话名师示范教案 (新版)新人教版.doc

  ·XX公司年产kt五层共挤宽幅高阻隔BOPP包装基材(新型膜材料)生产机组项目可行性研究报告.doc

http://cairowatch.com/zuiyoutufenjie/165.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有