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

《支持向量机算法设计与分析-章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章分解算法在第二章和第三章中，我们把基于支持向量机的分类问题和回归问题归结为一个带有线性约束的凸二次规划问题。在这一章中，我们将研究这些优化问题的求解。4.1无约束问题的提法求解约束问题的途径之一，是把它转化为一个或一系列无约束问题。对于解分类问题的支持向量机凸二次规划问题，我们用Lee和Mangasarian所提出的方法给予说明[1]。至于回归问题，读者可以参考文献[2]。4.1.1非光滑无约束问题考虑线性支持向量机的原始优化问题，(4-1)s.t.，(4-2)(4-3)这个最优化问题不是严格的凸二次规划问题。为了求解方便，Lee和Mangasarian把它修改

2、为严格的凸二次规划问题[1](4-4)s.t.，(4-5)(4-6)由约束条件(4-5)-(4-6)可知：问题关于的解应满足，(4-7)其中函数是单变量函数(4-8)把(4-7)代入(4-4)可得到无约束最优化问题，(4-9)上述问题是严格凸的无约束最优化问题，它有唯一的最优解。但函数是不可微的，所以要用非光滑的无约束最优化方法求解。4.1.2光滑无约束问题由于无约束最优化问题是非光滑的，所以不能使用通常的最优化问题解法求解，因为那里总要求目标函数的梯度和Hessen矩阵等存在。为此，Lee和Mangasarian引入非光滑函数的近似函数[1](4-10)其中是参数。

3、显然函数是光滑的，可以证明：当时，函数收敛于。这样无约束最优化问题就近似于最优化问题，(4-11)可以期望，当充分大时，光滑无约束问题的解会近似于非光滑无约束问题的解。因而也会近似于原始问题的解。4.1.3带有核的光滑无约束问题在广义支持向量机中，Mangasarian[3]考虑下述的非线性优化问题，(4-12)s.t.，(4-13)(4-14)其中是一个对称正定矩阵，(4-15)和线性情况一样，Lee和Mangasarian[1]把问题(4-12)-(2-14)转化为下述的严格凸二次规划，(4-16)s.t.(4-17)(4-18)相应于该问题的光滑无约束最优化问题

4、为(4-19)对于光滑的无约束问题，一些经典的算法，如：Newton-Armijo算法、BFGS算法（变度量法）、PRP共轭梯度法和Newton-PCG算法（牛顿－条件预优共轭梯度算法）都可以使用[4-5]。4.2分解算法的提出在处理具体问题时，由于存储和计算量两方面的要求，传统的处理光滑无约束问题的方法常常失效。原因是这些算法都要存储与训练集相应的核矩阵，而存储核矩阵所需的内存是随着训练集中样本点个数的平方增长的。当样本点以万计时，所需的内存已相当大。例如，当样本点数目超过10000时，存储核矩阵所需内存超过800MB。另外，这些算法往往包含大量的矩阵运算，所需的运

5、算时间往往比较长。为了解决大规模样本集的训练问题，研究者们提出了分解算法。其基本思想是：在每一步迭代中都把训练样本集分解为两个子集合和，只对工作集中的样本进行迭代，而另一个集合中的样本所对应的拉格朗日乘子保持不变。然后，将集合中的一部分“情况最糟糕的样本点”与工作集中的一部分样本点进行交换。目前，主要的分解算法有以下几种：(1)选块算法（Chunking）：它是由Boser等人首先提出的一种解决支持向量机训练存储空间问题的方法[6]。具体步骤为：首先取训练样本集合中的任意一个子集作为工作集；然后对求解最优化问题，得到支持向量并构成一个分类判别函数，并用该判别函数测试集

6、合中的样本，将其中不满足最优化条件者按其偏离最优的程度顺序排列为侯补工作集，若中的所有样本均满足最优化条件或为空集，则程序结束，否则继续；接下来剔除中的非支持向量样本，添加中排列在前面的个样本构成新的工作集。循环往复，直到程序结束。选块算法使得核矩阵大小由降低为（是支持向量得的个数），从而大大降低了对内存的需求，在支持向量很少的情况时能获得很好的结果，当很大时，对内存的需求仍很大，难以求解。(2)Osuna的分解算法：该算法是由Osuna等人提出的[7]，与Chunking算法最大的不同，也是它最大的改进之处：它将求解支持向量机的QP问题分解为一系列较小的QP问题，并

7、且工作集的大小保持不变，对内存的需求从与呈平方关系变为线性关系，因而可以克服Chunking算法中存在的问题。由于工作集是固定大小的，所以Osuna算法的速度与的选择和的大小有着密切的关系：如果较小，则每次优化的样本少，导致算法收敛很慢；反之，子QP问题的解决仍需要花费较多的内存和较长的时间，没有体现到分解算法的优越性。在Osuna分解思想的基础上，Joachims[8]和Lin[9]分别在各自的软件包SVMLight与LIBSVM中提出了不同的工作集选择方法。在实现的细节上，Joachims对常用的参数进行缓存，并对QP问题进行了Shrinking