SVM的SMO算法实现

SVM的SMO算法实现

自研0 谭李（006334） 吴翔（006333）

摘要

支持向量机（Support Vector Machine）是一种新近出现的解决模式识别问题的有效工具。它的数学模型可以归结为一个有约束的二次规划问题。如何快速准确地解这个二次规划，是SVM推广应用中的一个重要环节。我们尝试了数种可能的方法，用程序实现了其中最有效的一种——SMO算法（Sequential Minimal Optimization algorithm），并用块算法的思想（Chunking）对其作出了改进。本文将先给出待解决的数学模型，介绍我们所做的一些尝试，然后着重讨论SMO算法的原理、程序实现及其独特优势，最后阐述我们自己的一些新思想，主要是经过改进的Chunking SMO算法，并在附录中介绍SVM的基本原理。

SVM的数学模型

这里简要介绍支持向量机（SVM）数学模型的引出过程，关于SVM的详细介绍将在附录中给出。

支持向量机的原理是用分类超平面将空间中两类样本点正确分离，并取得最大边缘（正样本与负样本到超平面的最小距离）这样，原问题为一个有约束非线性规划问题：

Minimize12w2yi(xiwb)10(w,b)

i1,2,...,l范数最小的满足约束的w就是最优分类超平面的法向量。目标函数是严格上凹的二次型，约束函数是下凹的，这是一个严格凸规划。按照最优化理论中凸二次规划的解法，我们把它转化为Wolfe对偶问题来求解：

Maxmizes.t.1lW(α)iijyiyjxixj2i,ji1liyi0i1l

i0i1,...,l其中αi正是样本点xi的Lagrange乘子。Kuhn-Tunker条件定理指出，无效

约束所对应的Lagrange乘子一定为0，在这里的物理意义也就是说非支持向量xi（对应着原问题中的约束 yi(w’xi＋b)－1>0 ）的Lagrange乘子一定为0。这样分类规则就仅由恰好在超平面边缘上的少数支持向量（对应着约束yi(w’xi＋b)－1＝0）决定，而与其它样本无关。“支持向量机”这一名称由此而来。

对于非线形情况，只需将对偶问题中的点积用卷积核函数K(xi,xj)代替。

第 1 页 共 16 页

SVM的SMO算法实现

对于样本点不可分的情况，构造软边缘分类面，最终得到的Wolfe对偶问题与原来相似，只是α多了一个上限约束。这个上限C代表着对错分样本的惩罚力度，在边缘之内的样本对分类面的构造所起的作用是有限制的，这就是所谓“软边缘”的含义。

最后，由于求最大值可以转化为取负求最小值，这一数学模型最终表达为：

1MinimizeWolfe(α)TH[1,1,...1]l2s.t.yii1li0i1,...,l

0iC其中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条件）也可等价地表示为

i0yiui10iCyiui1 iCyiui1其中ui就是分类面（在非线性下不一定是超平面）函数作用在xi上的输出：

uiyK(x,x)b

jjjij1l这一KKT条件在我们的问题中有其具体的物理意义：第一种情况是说xi是非支持向量，在分类面边缘以外，其Lagrange乘子为0，对分类面的构造没有影响；第二种情况是说xi是正好在分类面上的支持向量，对应着非零的Lagrange乘子；第三种情况是说xi在分类面边缘以内甚至被错分，其Lagrange乘子受到上限的限制而为C。

关于二次规划算法的探索

Wolfe对偶问题比原始问题易于处理，它把问题转化成了在非负象限内对以样本的Lagrange乘子为变量的半正定的二次函数Wolfe进行优化，并服从一个的等式约束。但由于问题规模比较大，再加上目标函数的二次型已不是正定的，而且约束个数较多，又是等式约束和不等式约束的混合问题，在样本点不可分时还要加以上限的约束。这种复杂局面使得很多高效的算法对此束手无策，SVM方法至今未能得到广泛的应用，难以找到快速的算法不能不说是一个重要的原因。

二次规划是一种常见的优化问题，关于二次规划有一套比较成熟的理论。最初我们试图把这个问题作为一个纯数学问题来对待，从寻优理论中找到一种能解决我们的问题的数值方法，但是可以说是以失败告终。不过，我们还是了解到不少二次规划的一般方法，并从中总结了一些经验。

在二次规划中，条件极值问题的通常解法有罚函数法和单纯形法。

罚函数法在以往曾被作为一种标准的SVM算法。其基本思想是将解不满足

第 2 页 共 16 页

SVM的SMO算法实现

约束条件的程度作为惩罚项加在目标函数中，将条件极值问题转化为无条件极值问题来处理，求得其解后增大惩罚力度，将上一步的结果作为下次寻优的起始迭代点，再求解无条件极值问题，直到解满足约束为止。其中的无约束极值问题可以用共轭梯度法求解。典型的共轭梯度法针对的是对称正定的二次规划问题，进行n步迭代一定得到最优解。对于半正定的问题，共轭梯度法也会是可行的，但n步迭代不能结束，算法的停止条件应设为梯度范数在允许误差范围内（也就是说目标函数没有很大下降余地了算法就结束）。我实验室成员曾对此算法进行过研究，并向我介绍了他们当时的工作。此算法用C语言实现后效果并不理想，当样本点增加到30个时算法开始变慢，并经常出现不收敛的现象。这是因为梯度范数并不能准确地代表目标函数的下降余地，有时迭代一步调整太大，“过犹不及”，导致了一种“矫枉过正”的局面。解决的办法是调整惩罚因子大小以及修正迭代步长计算公式。因此程序的执行伴随着试探性的调试过程，这需要调试者充分了解这种算法的原理并具有丰富的调试经验。样本数目进一步增多，算法将完全不能收敛。我们参考了算法的C语言源程序，没有找到可作重大改进的地方。也许共轭梯度法本身并不适合我们的问题。

单纯形法是先随机找到一个可行点作为初值点，构造以可行点为顶点的单纯形，然后按某种搜索策略逐步缩小单纯形，直至各顶点间的距离在允许误差范围内为止。单纯形法解决的问题标准形式正与我们的问题相符，我实验室成员也对这种算法进行过研究，发现计算结果与初值关系较大，如果能凭先验经验选择一个离最优解较近的初值点，算法就能很快收敛，否则很容易陷入死循环。而这正违背了支持向量机法的初衷之一：仅凭科学的模式识别方法而不是先验知识来作出划分。这种方法看来也不可行。

其它各种文献中介绍的一些二次规划方法大多是针对某种特殊问题的，如要求目标函数的Hessian矩阵对称正定，或只能解决单纯的等式约束问题，或只能解决单纯的不等式约束问题，都很难符合我们的要求。

另外，Matlab的Optimization软件包里有一个适用于各种二次规划问题的现成程序Quadprog，我们用Matlab编了一个程序调用这个函数，有一定效果，但样本个数增加到200个时，不但计算较慢，而且结果很不理想，这可能与数值方法所特有的误差积累效应有关。Matlab的函数是针对很一般的二次规划问题的，不可能考虑到我们这个问题本身的特点，效率不高也在我们意料之中。

SMO算法

在大量地查阅二次规划的一般方法的同时，我们也在努力从SVM本身的角度寻求解答，也就是说，问题所提供的信息并不完全包含在这个二次规划的数学问题中，从问题本身的物理意义出发还是有可能做出突破的。最终我们果然在John C. Platt 1999年的一篇论文[2]中找到了这样的方法。 一．SMO算法的原理

这一被称为“顺次最小优化”的算法和以往的一些SVM改进算法一样，是把整个二次规划问题分解为很多易于处理的小问题（后面我们将探讨SMO与以往SVM改进算法之间的联系），所不同的是，只有SMO算法把问题分解到可能达到的最小规模：每次优化只处理两个样本的优化问题，并且用解析的方法进行处理。我们将会看到，这种与众不同的方法带来了一系列不可比拟的优势。

第 3 页 共 16 页

SVM的SMO算法实现

对SVM来说，一次至少要同时对两个样本进行优化（就是优化它们对应的Lagrange乘子），这是因为等式约束的存在使得我们不可能单独优化一个变量。

所谓“最小优化”的最大好处就是使得我们可以用解析的方法求解每一个最小规模的优化问题，从而完全避免了迭代算法。

当然，这样一次“最小优化”不可能保证其结果就是所优化的Lagrange乘子的最终结果，但会使目标函数向极小值迈进一步。我们再对其它Lagrange乘子做最小优化，直到所有乘子都符合KKT条件时，目标函数达到最小，算法结束。

这样，SMO算法要解决两个问题：一是怎样解决两个变量的优化问题，二是怎样决定先对哪些Lagrange乘子进行优化。

二．两个Lagrange乘子的优化问题（子程序takeStep）

我们在这里不妨设正在优化的两个Lagrange乘子对应的样本正是第一个和第二个，对两个Lagrange乘子α1和α2，在其他乘子不改变的情况下，它们的约束条件应表达为正方形内的一条线段。（如图1）

α2 = C α2 = C

α1 = 0 a1 = 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/2 K11α21+1/2 K22α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/2 K11(d-sα2)2+1/2 K22α22+sK12(d-sα2) α2

第 4 页 共 16 页

SVM的SMO算法实现

+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－2K12>0, 那么驻点必为极小值点，无条件的极值点就为

α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个训练样本的“误差”，这个式子又可以写为

0

α2＝α2＋y2(E1－E2)/η

除非核函数K不满足Mercer条件（也就是说不能作为核函数），η不会出现负值。但η=0是可以出现的情况。这时我们计算目标函数在线段两个端点上的取值，并将Lagrange乘子修正到目标函数较小的端点上：

f1=y1(E1+b)－α1K(x1,x1)－sα2K(x1,x1) f2=y2(E2+b)－sα1K(x1,x2)－α2K(x2,x2) L1=α1+s(α2－L) H1=α1+s(α2－H)

WolfeL=L1f1+Lf2+1/2 L21K(x1,x1)+1/2 L2K(x2,x2)+sLL1K(x1,x2) WolfeH=H1f1+Hf2+1/2 H21K(x1,x1)+1/2 H2K(x2,x2)+sHH1K(x1,x2) 当两个端点上取得相同的目标函数值时，目标函数在整条线段上的取值都会是一样的（因为它是上凹的），这时不必对α1，α2作出修正。

α2的无条件极值确定后，再考虑上下限的限制，最终的α2为

*2H2L如果2H如果L2H 如果2L最后，由等式约束确定α1：

α1*=α1+s(α2－α2*)

三．选择待优化Lagrange乘子的试探找点法

事实上即使我们不采用任何找点法，只是按顺序抽取αi，αj的所有组合进行优化，目标函数也会不断下降，直到任一对αi，αj都不能继续优化，目标函数就会收敛到极小值。我们采取某种找点方法只是为了使算法收敛得更快。

这种试探法先选择最有可能需要优化的α2，再针对这样的α2选择最有可能取得较大修正步长的α1。这样，我们在程序中使用两个层次的循环：

内层循环（子程序examineExample）针对违反KKT条件的样本选择另一个样本与它配对优化（指优化它们的Lagrange乘子），选择的依据是尽量使这样一对样本能取得最大优化步长。对其中一个Lagrange乘子α2来说优化步长为|(E1－E2)/η|,但由于核函数估算耗时较大，我们只用|E1－E2|来大致估计有可能取得的步长大小。也就是说，选出使得|E1－E2|最大的样本作为第二个样本。需要注意的是，这样的步长估计是比较粗略的，选择出来的一对样本有时非但不能“一劳永逸”地“一步到位”，反而不能作出进一步调整，（例如η=0的情况，最小

第 5 页 共 16 页

SVM的SMO算法实现

优化问题的二次型只是半正定的）。这时我们遍历所有非边界样本（非边界样本就是Lagrange乘子不在边界0或C上的样本），继续寻找能与α2配对优化的α1，如果这样的样本在非边界样本中找不到，再遍历所有样本。这两次遍历都是从随机位置开始的，以免算法总是在一开始遍历就向固定的方向偏差。在极端退化的情形，找不到与α2配对能作出进一步调整的α1，这时我们放弃第一个样本。

外层循环（主程序smo）遍历非边界样本或所有样本：优先选择遍历非边界样本，因为非边界样本更有可能需要调整，而边界样本常常不能得到进一步调整而留在边界上（可以想象大部分样本都很明显不可能是支持向量，它们的Lagrange乘子一旦取得零值就无需再调整）。循环遍历非边界样本并选出它们当中违反KKT条件的样本进行调整，直到非边界样本全部满足KKT条件为止。当某一次遍历发现没有非边界样本得到调整时，就遍历所有样本，以检验是否整个集合也都满足KKT条件。如果在整个集合的检验中又有样本被进一步优化，就有必要再遍历非边界样本。这样，外层循环不停地在“遍历所有样本”和“遍历非边界样本”之间切换，直到整个训练集都满足KKT条件为止。

以上用KKT条件对样本所作检验都是达到一定精度就可以了，例如正侧的非边界样本的输出ui可以在1的一定公差范围之内，通常这一公差（tolerance）取0.001，如果要求十分精确的输出算法就不能很快收敛。 四．每次最小优化后的重置工作

每做完一次最小优化，必须更新每个样本的误差（Error Cache），以便用修正过的分类面对其它样本再做KKT检验，以及选择第二个配对优化样本时估计步长之用。

更新Error Cache首先要重置阈值b 。我们可直接利用刚刚被优化的两个样本的信息在原阈值b0基础上作简单修正，而不需要调用所有支持向量重新计算b 。最小优化后的α1*如果不在边界上，b的计算公式为：

b1=E1+y1(α1*－α10)K(x1,x1)+y2(α2*－α20)K(x1,x2)+b0

最小优化后的α2*如果不在边界上，b的计算公式为：

b2=E2+y1(α1*－α10)K(x1,x2)+y2(α2*－α20)K(x2,x2)+b0 α1*，α2*都不在边界上时，b1和b2是相等的。两个Lagrange乘子都在边界上时，b1和b2以及它们之间的数都可作为符合KKT条件的阈值。这时SMO算法选择最安全的b1 ，b2之中点作为阈值。

非线性的情况，误差的计算要用到所有已找到的支持向量及它们的Lagrange乘子：

uj支持向量yiiK(xi,xj)b

Ejujyj线性的情况则是先重置分类超平面的法向量w，再根据uj=w’xj-b计算输出uj和误差Ej=uj－yj 。同阈值的重置一样，法向量的重置也不需要调用所有的支持向量，只需在原来的法向量基础上作改动：

w*=w+y1(α1*－α1)x1+y2(α2*－α2)x2

大部分重置工作都是以简单的非循环计算来完成的，这使得需要做很多次最小优化的SMO算法不必在每次优化后的重置中花费太多时间。但是我们也看到，非线性的情况误差的重置必须与所有支持向量逐个计算核函数，而且核函数的计算本身就比点积复杂，于是非线性的情况误差的重置将成为算法速度的瓶颈。

第 6 页 共 16 页

SVM的SMO算法实现

五．SMO算法的特点和优势

SMO算法和以往流行的SVM优化算法如块算法、固定工作样本集法相比，既有共同点，又有自己的独特之处。共同点在于它们都是把一个大的优化问题分解为很多小问题来处理。块算法在每一步中将新加入样本中违反KKT条件的样本与原有的支持向量一起组成小问题的样本集进行优化，优化完毕后只保留其中的支持向量，再加进来新的样本进入下一步。固定工作样本集法是每一步只收集新加入样本中“最坏”的样本，并将原来保留的支持向量集中“较好”的替换出去，以保持样本集大小不变。SMO则是把每一步的优化问题缩减到了最小，它可以看作是固定工作样本集法的一种特殊情况：把工作样本集的大小固定为2，并且每一步用两个新的Lagrange乘子替换原有的全部乘子。

SMO的最大特色在于它可以采用解析的方法而完全避免了二次规划数值解法的复杂迭代过程。这不但大大节省了计算时间，而且不会牵涉到迭代法造成的误差积累（其它一些算法中这种误差积累带来了很大的麻烦）。理论上SMO的每一步最小优化都不会造成任何误差积累，而如果用双精度数计算，舍入误差几乎可以忽略，于是所有的误差只在于最后一遍检验时以多大的公差要求所有Lagrange乘子满足KKT条件。可以说SMO算法在速度和精度两方面都得到了保证。

SMO在内存的节省上也颇具特色。我们看到，由于SMO不涉及二次规划数值解法，就不必将核函数矩阵整个存在内存里，而数值解法每步迭代都要拿这个矩阵作运算。（4000个样本的核函数矩阵需要128M内存！）于是SMO使用的内存是与样本集大小成线性增长的，而不象以往的算法那样成平方增长。在我们的程序中SMO算法最多占用十几兆内存。SMO使得存储空间问题不再是SVM应用中的另一个瓶颈。

SMO算法对线性支持向量机最为有效，对非线性则不能发挥出全部优势，这是因为线性情况下每次最小优化后的重置工作都是很简单的运算，而非线性时有一步加权求和，占用了主要的时间。其他算法对线性和非线性区别不大，因为凡是涉及二次规划数值解的算法都把大量时间花在求数值解的运算中了。

当大多数Lagrange乘子都在边界上时，SMO算法的效果会更好。 尽管SMO的计算时间仍比训练集大小增长快得多，但比起其它方法来还是增长得慢一个等级。因此SMO较适合大数量的样本。

我们通过自己的计算切实发现SMO算法的确是一个不可多得的好创意。它建立在前人的启发基础之上，又是一个具有划时代意义的新方法。

我们自己的新思想

一．新思想之一——SMO算法与Chunking结合

虽然SMO算法在速度方面已表现出了出众的性能，我们认为仍有可望对其进行改进。我们想到的一种方法是将Chunking的思路与SMO算法结合起来。具体地说，就是用类似于块算法的方法将样本集分成许多小块，每一步将原有的支持向量集合并到下一个块中，用SMO算法优化，然后只保留得到的支持向量，继续合并到下一个块中。这样，如果支持向量的个数不随样本个数线性增长（经常见到的情况是很大的样本集并不比小样本集有更多的支持向量），我们有可望得到一个计算量随样本个数成线性增长的支持向量机。

第 7 页 共 16 页

SVM的SMO算法实现

这种方法是有风险的，因为支持向量并不能完全代表一个样本集。冒然将样本子集中的非支持向量丢弃，可能丢弃的是整个样本集的真正支持向量。对于这种风险，我们是这么看待的：样本集的子集也是可以反映整个集合的特征的，基于子集作出的分类完全违背整个集合的总体概率分布只是小概率事件。为了减少支持向量的丢失，我们还可以做一些技术上的处理，例如遍历过所有子集以后再将剩下的支持向量合并到第一个子集再作优化，进行第二次遍历。由于经过第一次遍历得到的支持向量总是会包含整个集合的大部分特征，可以想见第二次遍历不会象第一次那样从盲目开始，因而一定会少丢失一些支持向量。如此遍历数次，得到的支持向量集就不会有太大偏差了。我们借鉴块算法的思路而又不完全采用其策略（把原有支持向量和下一个块合并优化而不只是和下一个块中违反KKT条件的点合并优化），也是为了减少支持向量的丢失。

在每一步加入多少新样本的问题上，也有一番斟酌。我们考虑一次加入n个样本和分k次每次加入n/k个样本（也就是以不同方法取得同样的进展）哪一种计算量小：我们令原有支持向量个数为n0,并假设在这n个样本处理完后支持向量并没有显著增加（我们针对的就是样本很多，支持向量很少的一类问题），再设SMO算法平均计算量是样本个数的函数t(nx)，那么我们要比较的两个计算量分别是kt(n0+n/k)和t(n0+n)。可以想象，当n0>>n时，t(n0+n)并不比 t(n0+n/k)大多少，于是kt(n0+n/k)约为t(n0+n)的k倍；而当n较大,t增长又很快，使t(n0+n)>> t(n0+n/k)时，前一种办法有可能取得更高的效率。这说明n太大和太小都不一定好，一定存在一个最优的“步长”，可以取得最快的进展速度。我们将所追求的这种“最高效率”表达为求η= t(n0+n)/n的极大值。不妨将n作为连续的量，做一个定性的估计：令η对n导数等于0,得nt’=t。如果t是指数函数t(n)=e-1, n就应该是一个常数1/a；如果t是幂函数t(n)=n, n就应该是n0的固定倍数n0/(a-1).

如果有一个对SMO算法复杂度的精确估计，我们无疑能找到一种最优的添加新样本子集的方法在Chunking中使用。遗憾的是这种估计是非常困难的。我们在实验中只发现SMO算法平均复杂度随样本个数的增长速度一定远远超过线性函数，但每次个别的计算都有很多其他因素对实际计算时间起着更大的影响。John在[3]中提到SMO的算法平均复杂度应与n~n2.2成正比，这样每次新加入的样本个数应与现有支持向量个数相当或更多。如果t确实是随n成幂函数增长，我们可以设置每步“步长”固定为现有支持向量数的p倍，在试验中根据经验调整p以取得最短计算时间。

不管怎么样，这种“Chunking SMO”的新算法一定可以使计算量随样本个数成线性增长（前提是所针对的问题不会有太多的支持向量）。我们用程序实现了这一算法，对于某些种类的样本集可以说是效果惊人。这使得我们已经可以对上百万个训练样本进行操作。

二．新思想之二——SMO反用于解决二次规划问题

SVM的数学模型已经告诉我们，支持向量机的分类问题就等价于一个有约束二次规划问题。二者之中任何一个有了突破，另一个就也可以得到解决。我们的本意是找一种二次规划的数值方法应用到SVM的实现算法中，结果发现数学上已有的方法基本上都不能解决问题，反而是从SVM的方向找到了高效的算法，这使得我们有理由猜测，这种算法如能反用在数学中，有可能解决一类尚无有效

第 8 页 共 16 页

a

an

SVM的SMO算法实现

方法的大型二次规划问题，（据我们了解，二次规划虽然有很多成熟的方法，上万阶二次规划的快速算法却并不多见）并应用到其它学科同一数学模型的问题中去。

我们认为SMO算法可以用于如下形式的二次规划问题：

Minimizes.t.1THcT2 dT00iCi,i1,2,...,lf()其中c,d为任意列向量，H为半正定阵。β=[β1,β2,…,βl]T

这一问题与我们的SVM模型几乎是一样的，唯一的实质性区别在于SVM中我们知道H＝(XY)T(XY), （X=[x1,x2,…,xl], Y=diag(y1,y2,…,yl) ）所以对于一个一般的数学问题，还需有一种分解方法把一个半正定阵H分解为ZTZ（是否存在简便可行的分解方法我们尚不了解）。如果我们知道H＝ZTZ，就可以将其完全转化为一个SVM问题：

将β做归一化成为α（即α的每个分量αi为βi的固定倍数），使得等式约束dTβ=0成为[y1,y2,…,yl]α＝0，y1,y2,…,yl皆为+1或－1，再令Y=diag(y1,y2,…,yl),

-1**

X=[x1,x2,…,xl]=ZY, c和Ci变为新的c和Ci，问题就变为：

Minimizes.t.T1THc*2[y1,y2,...,yl]0f()

0iC*i,i1,2,...,l我们对它应用稍加改动的SMO算法，每个Lagrange乘子αi的上限设为不同（这在两个乘子的联合优化中只不过把正方形变成矩形，解析解法的思路不变），就可以得到问题的一种准确而快速的优化方法。这种推广是否真正可行，有待于我们在后续的工作中做进一步研究。

SMO的程序实现和实验效果

一．实现算法的核心模块

我们自己用Matlab编写了SMO的程序，并生成训练样本和测试样本检验算法的有效性。程序共有三个函数：主函数smo完成试探找点算法的外层循环：遍历非边界样本或遍历所有样本，对遍历到的每个样本调用子函数examineExample。子函数examineExample完成试探找点法的内层循环：针对给定的样本找一个合适的样本与它配对优化，调用子函数takeStep。子函数takeStep完成两个样本的优化。程序的原理和流程在前面都有详述，这里不再赘述。

虽然SMO算法的大致原理和流程都已经给出，但程序实现中一些技术性的

细节还是很费一番斟酌的。例如在子函数takeStep中，如果调整过小， |α2*－α2|小到一定程度，显然就不必调整了。如何定义衡量这一“调整步长”的阈值范围，我们开始只是简单地令|α2*－α2|<ε时放弃调整。后来我们发现对于不同的样本集最优的Lagrange乘子大小差别很大，认为相对调整步长大小意义更大，将这一标准改为|α2*－α2|<ε(α2*+α2)。进而我们又引入绝对阈值

第 9 页 共 16 页

SVM的SMO算法实现

（absolute ε）和相对阈值（relative ε）的概念，认为εr(α2*+α2+εa)才可以实现对这一阈值的完整表达，它要求调整大小既大于某一绝对数值，又使Lagrange乘子相对于自身有明显的比例变化。相对阈值可固定地取1%，绝对阈值则难以找到一个放之四海而皆准的普适常数。因为不同训练集的Lagrange乘子确实在数量级上差别极大，具体的说就是正负样本之间间距越大的样本集（从而分类面的边缘越大）Lagrange乘子越小。一种办法是手工调整：先用较大的εa计算，算完如果没有任何一个乘子被调整，再逐步缩小εa。最后经过反复地考虑，我们发现εa太大或太小的真正弊病在于：首先任何时候εa都不能太大，远超过Lagrange乘子的规模，否则很多重要的调整都会被忽略；其次后期εa不能太小，否则很可能较大的Lagrange乘子都已调整到位，小得多的乘子还在不停调整，颇有舍本逐末之嫌，因为这些小的乘子相对自身变化再大也不会影响分类规则，这并不是一个时间换精度的问题，而是白白浪费计算时间。认清了这一问题的本质，我们令εa总是等于现有的最大的αi，既不会忽略对分类规则有影响的重要调整，又可以及时停止微枝末节的精打细算，能自动适应各种不同的问题。果然，我们做了这一调整以后，算法速度增加了数倍。最初的程序运算效率对两类样本分开的程度比较敏感，对间隔很小的两类样本（从而最优超平面不能取得很大的边缘）计算相对慢得多。修改过的程序则对紧密贴在一起的两类样本和间隔很大的两类样本具有同样的高效。可见一个好的创意还必须要有编程人员耐心地考虑每一个细节才能发挥出它应有的效率。

程序中的一些输入参数和控制参数需要说明：输入参数共有5个：input_linear 告知程序是否用线性分类面，1表示线性，0表示非线性。input_dimension告知样本的维数。input_trainingsize告知样本个数。NeedVerify为1或0表示要或不要读入测试样本检验错分率。filename为训练集文件、测试集文件、训练结果文件、测试结果文件的文件名（不需输扩展名）。

控制参数共有6个：relativeEps 是上面提到的相对阈值。boundmargin是Lagrange乘子“边界”的边缘大小：α在0或C的boundmargin范围内我们认为它等于0或C。鉴于这个量的大小也应与Lagrange乘子的规模成比例，我们不规定它的大小，而控制比例关系boundmargin_scale,令boundmargin等于最大乘子的boundmargin_scale倍。C是对错分样本的惩罚力度，Lagrange乘子的上限。tolerance是要求样本满足KKT条件的公差范围。d是非线性支持向量机的核函数参数（本程序采用多项式学习机器，d为多项式阶次。） 二．外围模块

外围模块包括从文件中读入训练数据、将结果存入结果文件、画图显示以及读入测试样本检测错分率，都在主函数smo中完成。另外我们还用VC编制了样本生成器，可以生成线性和非线性、可分和不可分、二维和高维的多种有代表性的样本。

结果文件记录了详细的实验结果，包括训练样本个数、支持向量个数、所有的支持向量及其Lagrange乘子、计算时间、程序中使用的所有控制参数，线性的情况还记录分类面的法向量和阈值。

对于二维的样本，我们画图显示。图中正样本为蓝点，负样本为红叉，支持向量用同种颜色的方框标出，绿色的是分类面。 三．实验效果

实验结果是非常令我们满意的，对线性可分的情况，SMO可以处理6000个样本，计算时间近1小时（3337秒），并取得了很高的精度。线性不可分的情

第 10 页 共 16 页

SVM的SMO算法实现

况计算速度较慢，计算速度和不可分的程度关系很大，但结果仍是十分逼近样本的生成规则。非线性的情况SMO算法可以处理300个样本，并未显示出很大优势。前面已经介绍过SMO算法在非线性效率较低的原因。

考虑到我们的SMO程序是用Matlab实现的，Matlab是一种解释型的语言，执行效率比较低，如果改用C语言编程，处理的样本还可再多。

Chunking SMO的程序实现和实验效果

一．Chunking思想的程序实现

为了把SMO程序改造为Chunking SMO程序，我们定义数组actual，actual(i)的值是正在处理的块（Chunk）中第i个样本在整个样本集中的真正下标。这样我们在加入新样本时就不必把样本数据传输给块中的样本，而只需记下它们的下标。我们在块中处理第i个样本的Lagrange乘子，只需对alph(actual(i))进行操作。

我们令chunkingloop_total为事先设定的遍历整个样本集的次数，当遍历次数未达到时就继续加入新样本构造下一个块。加入新样本之前先把上一步留下的所有支持向量那入块中。我们还定义数组SV(i)，对应着每一个样本是否为支持向量。在将新样本纳入块中时，检查它的SV(i)，就不会使块中出现重复的样本。

每次纳入的样本个数（chunkstep）取为已有支持向量个数的chunkstep_scale倍。按我们在实验中取得的经验，chunkstep_scale取1.5 ~ 3效率较高。

Chunking SMO程序可以在计算中输出已进行的遍历数和本次遍历已进行的样本数作为进度指示。对于调试者来说这样的进度指示还是很有必要的。 二．Chunking SMO的实验效果

Chunking SMO对于线性可分的样本集具有惊人的计算速度，真正实现了计算量随样本数线性增长。实验结果表明Chunking SMO处理500,000个样本只需3小时（11265秒）。分类面的准确度有微小的下降。这种精度下降似乎不随着我们增加遍历次数chunkingloop_total而减小，但可以通过调整chunkstep_scale得到较满意的结果。可能我们对于Chunking中支持向量丢失的理解还不够准确。

对线性不可分的样本集Chunking SMO也加快了计算速度，但不如线性可分的样本那样显著（我们实验用的一种训练集，Chunking SMO计算1000点的时间约为原始SMO算法的60%）。这是因为不可分的样本集会有很多的支持向量，而Chunking方法的优势在于支持向量少的样本集。

对于非线性的样本集Chunking SMO实验效果很不好，经常只能找到少数的支持向量，作出类似线性的分类面。我们认为可能的原因是非线性样本集的支持向量更难代表整个样本集，因而只保留支持向量的Chunking方法难以适用。

以上所提到的程序和典型实验结果都已上载到实验室的ftp服务器，请匿名登录ftp://simba.au.tsinghua.edu.cn/pub/xzhang/SLT/smo 下载。实验的一些有代表性的结果的图示附在附页中。（由于Chunking SMO的实验结果除了速度可观以外效果没有什么不同，500,000个样本的图象在内存中也无法容纳，因此不再附Chunking SMO实验结果的图示。）

附录 SVM数学模型的建立过程

一．线性可分的支持向量机

第 11 页 共 16 页

SVM的SMO算法实现

SVM是统计学习理论的重要成果。它的原理可以直观地得到。首先看线性可分的情况：

假定训练数据(x1,yi),„,(xl,yl),x∈Rn,y∈{+1,-1} 可以被一个超平面

(wx)b0没有错误地分开，按照直观的推测，与两类样本点距离最大（称为

边缘最大）的分类超平面会获得最佳的推广能力（也就是最为稳妥地描述了两种样本的界限）。最优超平面将由离它最近的少数样本点（称为支持向量）决定，而与其它样本无关。我们用如下形式描述与样本间隔为Δ的分类超平面：

(wx)b0， w=1 y=1, 若(wx)b y=-1,若(wx)b

将这个分类超平面做以下归一化：令Δ＝1，而w和b可以按比例缩放。离超平面最近的样本点（支持向量）满足

(wxi)b1 ，若y=1 (wxi)b1，若y=-1

支持向量到超平面的距离为1/w。于是，这个最优化问题最初的数学提法将是：

Minimizes.t.1w2yi(xiwb)10(w,b)2

i1,2,...,l目标函数是严格上凹的二次型，约束函数是下凹的，这是一个严格凸规划。按照最优化理论中凸二次规划的解法，我们把它转化为Wolfe对偶问题来求解：

构造Lagrange函数：

1L(w,α,b)w22iyi(xiwb)i,i1i1lli0,i1,2,...,l

L(w,α,b)0，b（Kuhn-Tucker条件），即wiyixi和iyi0。将两式代回Lagrange函

（其中αi是Lagrange乘子。）它应满足条件wL(w,α,b)0,ii数中，消去w和b,经运算得到原最优化问题的Wolfe对偶问题：

Maxmizes.t.1lW(α)iijyiyjxixj2i,ji1liyi0i1l

i0i1,...,l第 12 页 共 16 页

SVM的SMO算法实现

其解是原最优化问题的整体最优解。解出α后利用wiyixi确定最优超平

i面，注意到只有支持向量所对应的Lagrange乘子αi才不是0。

利用Wolfe对偶问题，不但使问题更好处理，而且使样本在新问题中仅以向量点积的形式出现，正是这一重要特点，使支持向量机法能推广到非线性情况。由于Wolfe对偶问题带来了这样好的一个副产品，现在对SVM所作研究一般都从Wolfe对偶问题开始，而不将其最初的数学提法作为优化目标。 二．非线性支持向量机

前面的算法针对的是输入空间存在线性判别面的情况，对分类面是非线性函数的情况，理论上应将输入空间通过某种非线性映射映射到一个高维特征空间，在这个空间中存在线性的分类规则，可以构造线性的最优分类超平面。但是这种方法带来了两个问题：一是概念上的问题：怎样在如此高维的空间中找到一个推广性好的分类超平面？二是技术上的问题：如何处理高维空间中的计算问题？

前面我们把寻找最优超平面最终归结为其Wolfe对偶问题，一个很重要的副产品就是找到了一个克服“维数灾难”，解决技术上问题的绝好方法：如果数

nn

学上可以找到一个函数K：（R,R）→R使得K(xi,xj)就等于xi,xj在高维特征空间中的映射之点积，那面我们用K(xi,xj)代替Wolfe对偶问题中xi和xj的点积即可，计算量将会大大减少。事实上确实存在这样的函数，Vapnik称之为卷积核函数（Convolution of Inner Product,or Kernel Function）。于是我们只需在输入空间中计算卷积核函数，而不必知道非线性映射的形式，也不必在高维特征空间中进行计算。

我们自然会提出这样的问题：怎样选择核函数？核函数的性质会对学习机器的推广能力起决定作用吗？幸运的是，实验表明采用不同种类核函数的学习机器表现出了大致相同的性能，它们找到的支持向量大致相同。多项式分类器、径向基函数、两层神经网络等都是常用的SVM的核函数。

与线性情况有所不同的是：尽管在高维特征空间中线性判别面的法向量w仍可表示成这个空间中支持向量的线性组合，但由于将输入空间映为高维空间的是非线性映射，这种线性组合关系在输入空间中不再表现为线性组合，我们又不可能把工作样本映到高维空间再行判别，所以就需要重新考虑工作样本的决策问题。输入空间中的判别函数是：

f(x)signyiiK(xi,x)b

支持向量如果支持向量很多的话，决策阶段的计算量也将是较大的。 三．不可分情况的处理

为了使SVM算法能应用于不可分情况，Cortes和Vapnik在1995年引入了 软边缘最优超平面的概念，引入非负变量ξi,将约束条件放松为

yi(xiwb)11i,同时对目标函数引入惩罚项：

1(w,)w22i1,2,...,l

lCi i1第 13 页 共 16 页

SVM的SMO算法实现

求解这个二次规划问题，最终推导所得的Wolfe对偶问题与可分的情况类似：

Maxmizes.t.1lW(α)iijyiyjxixj2i,ji1liyi0i1l

Ci0i1,...,l唯一的区别在于对αi加了一个上限限制。这种软边缘分类面对于非线性支持向

量机同样适用，使支持向量机可以普遍适用于各种模式识别问题。

参考文献

[1] Vladimir N. Vapnik 著，张学工译。统计学习理论的本质。清华大学出版社。2000

[2]John C.Platt . Using Analytic QP and Sparseness to Speed Training of Support Vector Mections . MIT Press. 1999

[3] John C.Platt . Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Technical Report MSR-TR-98-14. 1998

[4] 赵瑞安，吴方。非线性最优化理论和方法。浙江科学技术出版社。1992 [5] 袁亚湘。非线性规划数值方法。上海科学技术出版社。1993 [6] 袁亚湘，孙文瑜。最优化理论与方法。科学出版社。1997

后记

本文作为“高等数值分析”和“统计学习理论”两门课程的Project，我们最初的想法是将数值分析的方法应用到SVM中去，自己编程实现SVM的一种行之有效的算法。具体的方法打算用共轭梯度法，目标是能处理1000个左右的样本，并实现线性、非线性、可分、不可分的几种SVM，既能加深我们对共轭梯度法的理解，又可将数学方法应用到自己专业的工程实际中去，解决自己领域内的问题。最后结果大大超出计划，但并不是用数值分析的方法实现的，可见数学方法必须与具体学科的实际情况相结合。

感谢老师给我们找到这样一个课题，大大开拓了我们的视野，锻炼了科研能力。特别感谢蔡大用老师和我们的导师张学工老师、王文渊老师对我们的悉心指导。我们能完成这一课题和实验室诸位师兄师姐的鼎力帮助也是分不开的。没有实验室其他成员以往在SVM研究中积累的经验，我们还要走很多弯路。数学系的徐金星老师也曾为我们答疑解惑，在这里一并致谢。

第 14 页 共 16 页

SVM的SMO算法实现

【附页】 几个实验结果附图

（一）线性可分情况，6000个点，用SMO算法，找到20个支持向量，计算时

间3337秒。样本的生成规则使正负样本以y = －x + 6000为分界面。 计算所得最优超平面为y = －0.966660x + 5664 。(linear6000.jpg , linear6000.txt)

（二）线性不可分情况，以两个点为中心正态分布的1000个点，用SMO算法，

找到268个支持向量，计算时间3982秒。(normal1000.jpg , normal1000.txt)

第 15 页 共 16 页

SVM的SMO算法实现

（三）非线性可分情况，150个点，在y=sinx上下分布，用SMO算法，找到50

个支持向量，计算时间1745秒。(sin150.jpg , sin150.txt)

（四）非线性可分情况，300个点，在圆x2+y2=100内外分布，用SMO算法，

找到35个支持向量，计算时间2127秒。(circle300.jpg , circle300.txt)

第 16 页 共 16 页