SVM的SMO算法实现

SVM的SMO算法实现第1页共16页SVM的SMO算法实现自研0谭李（006334）吴翔（006333）摘要支持向量机（SupportVectorMachine）是一种新近出现的解决模式识别问题的有效工具。它的数学模型可以归结为一个有约束的二次规划问题。如何快速准确地解这个二次规划，是SVM推广应用中的一个重要环节。我们尝试了数种可能的方法，用程序实现了其中最有效的一种——SMO算法（SequentialMinimalOptimizationalgorithm），并用块算法的思想（Chunking）对其作出了改进。本文将先给出待解决的数学模型，介绍我们所做的一些尝试，然后着重讨论SMO算法的原理、程序实现及其独特优势，最后阐述我们自己的一些新思想，主要是经过改进的ChunkingSMO算法，并在附录中介绍SVM的基本原理。SVM的数学模型这里简要介绍支持向量机（SVM）数学模型的引出过程，关于SVM的详细介绍将在附录中给出。支持向量机的原理是用分类超平面将空间中两类样本点正确分离，并取得最大边缘（正样本与负样本到超平面的最小距离）这样，原问题为一个有约束非线性规划问题：l,...,2,1i01)b(y21)b,(Minimizei2wxwwi范数最小的满足约束的w就是最优分类超平面的法向量。目标函数是严格上凹的二次型，约束函数是下凹的，这是一个严格凸规划。按照最优化理论中凸二次规划的解法，我们把它转化为Wolfe对偶问题来求解：l,...,1i00y.t.syy21)(WMaxmizeil1iiilj,ijiil1iijjixxα其中αi正是样本点xi的Lagrange乘子。Kuhn-Tunker条件定理指出，无效约束所对应的Lagrange乘子一定为0，在这里的物理意义也就是说非支持向量xi（对应着原问题中的约束yi(w’xi＋b)－10）的Lagrange乘子一定为0。这样分类规则就仅由恰好在超平面边缘上的少数支持向量（对应着约束yi(w’xi＋b)－1＝0）决定，而与其它样本无关。“支持向量机”这一名称由此而来。对于非线形情况，只需将对偶问题中的点积用卷积核函数K(xi,xj)代替。SVM的SMO算法实现第2页共16页对于样本点不可分的情况，构造软边缘分类面，最终得到的Wolfe对偶问题与原来相似，只是α多了一个上限约束。这个上限C代表着对错分样本的惩罚力度，在边缘之内的样本对分类面的构造所起的作用是有限制的，这就是所谓“软边缘”的含义。最后，由于求最大值可以转化为取负求最小值，这一数学模型最终表达为：l,...,1iC00y.t.s]1,...1,1[H21)α(WolfeMinimizeil1iiilT其中H是一个半正定的对称阵[yiyjK(xi,xj)]li,j=1（线性的情况也就是(XY)T(XY),X=[x1,x2,…,xl],Y=diag(y1,y2,…,yl),）α=[α1,α2,…,αl]T这个对偶问题仍是一个有约束的二次规划，它的Kuhn-Tucker条件（在SVM的文献中多称为Kaush-Kuhn-Tucker条件）也可等价地表示为1uyC1uyC01uy0iiiiiiiii其中ui就是分类面（在非线性下不一定是超平面）函数作用在xi上的输出：l1jjjib)(Kyuijx,x这一KKT条件在我们的问题中有其具体的物理意义：第一种情况是说xi是非支持向量，在分类面边缘以外，其Lagrange乘子为0，对分类面的构造没有影响；第二种情况是说xi是正好在分类面上的支持向量，对应着非零的Lagrange乘子；第三种情况是说xi在分类面边缘以内甚至被错分，其Lagrange乘子受到上限的限制而为C。关于二次规划算法的探索Wolfe对偶问题比原始问题易于处理，它把问题转化成了在非负象限内对以样本的Lagrange乘子为变量的半正定的二次函数Wolfe进行优化，并服从一个的等式约束。但由于问题规模比较大，再加上目标函数的二次型已不是正定的，而且约束个数较多，又是等式约束和不等式约束的混合问题，在样本点不可分时还要加以上限的约束。这种复杂局面使得很多高效的算法对此束手无策，SVM方法至今未能得到广泛的应用，难以找到快速的算法不能不说是一个重要的原因。二次规划是一种常见的优化问题，关于二次规划有一套比较成熟的理论。最初我们试图把这个问题作为一个纯数学问题来对待，从寻优理论中找到一种能解决我们的问题的数值方法，但是可以说是以失败告终。不过，我们还是了解到不少二次规划的一般方法，并从中总结了一些经验。在二次规划中，条件极值问题的通常解法有罚函数法和单纯形法。罚函数法在以往曾被作为一种标准的SVM算法。其基本思想是将解不满足SVM的SMO算法实现第3页共16页约束条件的程度作为惩罚项加在目标函数中，将条件极值问题转化为无条件极值问题来处理，求得其解后增大惩罚力度，将上一步的结果作为下次寻优的起始迭代点，再求解无条件极值问题，直到解满足约束为止。其中的无约束极值问题可以用共轭梯度法求解。典型的共轭梯度法针对的是对称正定的二次规划问题，进行n步迭代一定得到最优解。对于半正定的问题，共轭梯度法也会是可行的，但n步迭代不能结束，算法的停止条件应设为梯度范数在允许误差范围内（也就是说目标函数没有很大下降余地了算法就结束）。我实验室成员曾对此算法进行过研究，并向我介绍了他们当时的工作。此算法用C语言实现后效果并不理想，当样本点增加到30个时算法开始变慢，并经常出现不收敛的现象。这是因为梯度范数并不能准确地代表目标函数的下降余地，有时迭代一步调整太大，“过犹不及”，导致了一种“矫枉过正”的局面。解决的办法是调整惩罚因子大小以及修正迭代步长计算公式。因此程序的执行伴随着试探性的调试过程，这需要调试者充分了解这种算法的原理并具有丰富的调试经验。样本数目进一步增多，算法将完全不能收敛。我们参考了算法的C语言源程序，没有找到可作重大改进的地方。也许共轭梯度法本身并不适合我们的问题。单纯形法是先随机找到一个可行点作为初值点，构造以可行点为顶点的单纯形，然后按某种搜索策略逐步缩小单纯形，直至各顶点间的距离在允许误差范围内为止。单纯形法解决的问题标准形式正与我们的问题相符，我实验室成员也对这种算法进行过研究，发现计算结果与初值关系较大，如果能凭先验经验选择一个离最优解较近的初值点，算法就能很快收敛，否则很容易陷入死循环。而这正违背了支持向量机法的初衷之一：仅凭科学的模式识别方法而不是先验知识来作出划分。这种方法看来也不可行。其它各种文献中介绍的一些二次规划方法大多是针对某种特殊问题的，如要求目标函数的Hessian矩阵对称正定，或只能解决单纯的等式约束问题，或只能解决单纯的不等式约束问题，都很难符合我们的要求。另外，Matlab的Optimization软件包里有一个适用于各种二次规划问题的现成程序Quadprog，我们用Matlab编了一个程序调用这个函数，有一定效果，但样本个数增加到200个时，不但计算较慢，而且结果很不理想，这可能与数值方法所特有的误差积累效应有关。Matlab的函数是针对很一般的二次规划问题的，不可能考虑到我们这个问题本身的特点，效率不高也在我们意料之中。SMO算法在大量地查阅二次规划的一般方法的同时，我们也在努力从SVM本身的角度寻求解答，也就是说，问题所提供的信息并不完全包含在这个二次规划的数学问题中，从问题本身的物理意义出发还是有可能做出突破的。最终我们果然在JohnC.Platt1999年的一篇论文[2]中找到了这样的方法。一．SMO算法的原理这一被称为“顺次最小优化”的算法和以往的一些SVM改进算法一样，是把整个二次规划问题分解为很多易于处理的小问题（后面我们将探讨SMO与以往SVM改进算法之间的联系），所不同的是，只有SMO算法把问题分解到可能达到的最小规模：每次优化只处理两个样本的优化问题，并且用解析的方法进行处理。我们将会看到，这种与众不同的方法带来了一系列不可比拟的优势。SVM的SMO算法实现第4页共16页对SVM来说，一次至少要同时对两个样本进行优化（就是优化它们对应的Lagrange乘子），这是因为等式约束的存在使得我们不可能单独优化一个变量。所谓“最小优化”的最大好处就是使得我们可以用解析的方法求解每一个最小规模的优化问题，从而完全避免了迭代算法。当然，这样一次“最小优化”不可能保证其结果就是所优化的Lagrange乘子的最终结果，但会使目标函数向极小值迈进一步。我们再对其它Lagrange乘子做最小优化，直到所有乘子都符合KKT条件时，目标函数达到最小，算法结束。这样，SMO算法要解决两个问题：一是怎样解决两个变量的优化问题，二是怎样决定先对哪些Lagrange乘子进行优化。二．两个Lagrange乘子的优化问题（子程序takeStep）我们在这里不妨设正在优化的两个Lagrange乘子对应的样本正是第一个和第二个，对两个Lagrange乘子α1和α2，在其他乘子不改变的情况下，它们的约束条件应表达为正方形内的一条线段。（如图1）α2=Cα2=Cα1=0a1=Cα1=0α1=Cα2=0α2=0在这条线段上求一个函数的极值，相当于一个一维的极值问题。我们可以把α1用α2表示，对α2求无条件极值，如果目标函数是严格上凹的，最小值就一定在这一极值点（极值点在区间内）或在区间端点（极值点在区间外）。α2确定后，α1也就确定下来了。因此我们先找到α2优化区间的上下限制，再在这个区间中对α2求最小值。由图1我们容易得到α2的上下限应为：L=max(0,α2－α1)，H=min(C,C+α2–α1),若y1与y2异号；L=max(0,α2+α1－C),H=min(C,α2+α1),若y1与y2同号；令s=y1y2标志这两个样本是否同类，则有L=max(0,α2+sα1－1/2(s+1)C),H=min(C,α2+sα1–1/2(s－1)C)而α1和α2在本次优化中所服从的等式约束为：α1＋sα2=α01+sα02=d下面我们推导求最小值点α2的公式：由于只有α1，α2两个变量需要考虑，目标函数可以写成Wolfe(α1,α2)=1/2K11α21+1/2K22α22+sK12α1α2+y1α1v1+y2α2v2－α1－α2+常数其中Kij=K(xi,xj),vi=y3α03Ki3+…+ylα0lKil=ui+b0－y1α01K1i–y2α01K2i上标为0的量表示是本次优化之前Lagrange乘子的原值。将α2用α1表示并代入目标函数：Wolfe（α2）=1/2K11(d-sα2)2+1/2K22α22+sK12(d-sα2)α2SVM的SMO算法实现第5页共16页+y1(d-sα2)v1–d+sα2+y2α2v2－α2+常数对α2求导：dWolfe(α2)/dα2=－sK11(d－sα2)+K22α2－K12α2+sK12(d－sα2)－y2v2+s+y2v2－1＝0如果Wolfe函数总是严格上凹的，即二阶导数K11+K22－2K120,那么驻点必为极小值点，无条件的极值点就为α2＝[s(K11－K12)d+y2(v1－v2)＋1－s]/(K11＋K22－2K12)将d,v与α0,u之间关系代入，就得到用上一步的α02，u1,u2表示的α2的无条件最优点：α2＝[α02(K11＋K22－2K12)+y2(u1－u2＋y2－y1)]/(K11＋K22－2K12)令η=K11＋K22－2K12为目标函数的二阶导数，Ei=ui－yi为第i个训练样本的“误差”，这个式子又可以写为α2＝α02＋y2(E1－E2)/η除非核函数K不满足Mercer条件（也就是说不能作为核函数），η不会出现负值。但η=0是可以出现的情况。这时我们计算目标函数在线段两个端点上的取值，并将Lagrange乘子修正到目标函数较小的端点上：f1=y1(E1+b)－α1K(x1,x1)－sα2K(x1,x1)f2=y2(E2+