收稿日期:2003-06-13作者简介:姬水旺(1977)),男,陕西府谷人,硕士,研究方向为机器学习、模式识别、数据挖掘。
支持向量机训练算法综述姬水旺,姬旺田(陕西移动通信有限责任公司,陕西西安710082)摘 要:训练SVM 的本质是解决二次规划问题,在实际应用中,如果用于训练的样本数很大,标准的二次型优化技术就很难应用。
针对这个问题,研究人员提出了各种解决方案,这些方案的核心思想是先将整个优化问题分解为多个同样性质的子问题,通过循环解决子问题来求得初始问题的解。
由于这些方法都需要不断地循环迭代来解决每个子问题,所以需要的训练时间很长,这也是阻碍SVM 广泛应用的一个重要原因。
文章系统回顾了SVM 训练的三种主流算法:块算法、分解算法和顺序最小优化算法,并且指出了未来发展方向。
关键词:统计学习理论;支持向量机;训练算法中图分类号:T P30116 文献标识码:A 文章编号:1005-3751(2004)01-0018-03A Tutorial Survey of Support Vector Machine Training AlgorithmsJI Shu-i wang,JI Wang -tian(Shaanx i M obile Communicatio n Co.,Ltd,Xi .an 710082,China)Abstract:Trai n i ng SVM can be formulated into a quadratic programm i ng problem.For large learning tasks w ith many training exam ples,off-the-shelf opti m i zation techniques quickly become i ntractable i n their m emory and time requirem ents.T hus,many efficient tech -niques have been developed.These techniques divide the origi nal problem into several s maller sub-problems.By solving these s ub-prob -lems iteratively,the ori ginal larger problem is solved.All proposed methods suffer from the bottlen eck of long training ti me.This severely limited the w idespread application of SVM.T his paper systematically surveyed three mains tream SVM training algorithms:chunking,de -composition ,and sequenti al minimal optimization algorithms.It concludes with an illustrati on of future directions.Key words:statistical learning theory;support vector machine;trai ning algorithms0 引 言支持向量机(Support Vector M achine)是贝尔实验室研究人员V.Vapnik [1~3]等人在对统计学习理论三十多年的研究基础之上发展起来的一种全新的机器学习算法,也使统计学习理论第一次对实际应用产生重大影响。
SVM 是基于统计学习理论的结构风险最小化原则的,它将最大分界面分类器思想和基于核的方法结合在一起,表现出了很好的泛化能力。
由于SVM 方法有统计学习理论作为其坚实的数学基础,并且可以很好地克服维数灾难和过拟合等传统算法所不可规避的问题,所以受到了越来越多的研究人员的关注。
近年来,关于SVM 方法的研究,包括算法本身的改进和算法的实际应用,都陆续提了出来。
尽管SVM 算法的性能在许多实际问题的应用中得到了验证,但是该算法在计算上存在着一些问题,包括训练算法速度慢、算法复杂而难以实现以及检测阶段运算量大等等。
训练SVM 的本质是解决一个二次规划问题[4]:在约束条件0F A i F C,i =1,,,l (1)E li =1Ai y i =0(2)下,求W(A )=E li =1A i -12E i,JAi A j y i y j {7(x i )#7(x j )}=E li =1Ai -12E i,JA i A j y i y j K (x i ,x j )(3)的最大值,其中K (x i ,x j )=7(x i )#7(x j )是满足Merce r 定理[4]条件的核函数。
如果令+=(A 1,A 2,,,A l )T,D ij =y i y j K (x i ,x j )以上问题就可以写为:在约束条件+T y =0(4)0F +F C (5)下,求W(+)=+Tl -12+TD +(6)的最大值。
由于矩阵D 是非负定的,这个二次规划问题是一个凸函数的优化问题,因此Kohn -Tucker 条件[5]是最优点第14卷 第1期2004年1月 微 机 发 展M icr ocomputer Dev elopment V ol.14 N o.1Jan.2004应满足的充要条件。
Kohn-Tuc ker条件可化简为一个简单的形式[6],即所有训练样本应满足:Ai=0Z y i f(x i)E1(7) 0<A i<C Z y i f(x i)=1(8)A i=C Z y i f(x i)F1(9)其中f(x i)为SVM决策函数关于第i个样本的输出。
传统的标准二次型优化技术大都是针对矩阵D的维数较低的情况进行讨论的[5],即假设同时可以方便地对矩阵的所有行和列进行操作,对于SVM的训练问题矩阵D 的维数就是训练样本的个数,因此在大样本情况下SVM 的训练速度就必然很慢,这是阻碍SVM广泛应用的一个很大的障碍。
其主要原因是,首先,SVM方法需要计算和存储核函数矩阵,当样本点数目较大时,需要很大的内存,例如,当样本点数目超过4000时,存储核函数矩阵需要多达128MB内存[6],这使得在大样本情况下不可能将整个矩阵同时保存在内存中,增加了虚拟内存页替换的频率;其次,SVM在二次型寻优过程中要进行大量的矩阵运算,多数情况下,矩阵运算占用了算法时间的主要部分。
SVM方法的训练速度是限制它的广泛应用的主要原因,近年来人们针对方法本身的特点提出了许多算法来解决对偶寻优问题,这些算法的一个共同的思想就是采用分而治之的原则将原问题分解为规模较小的子问题,通过循环解决一系列子问题来求得原问题的解。
根据分解策略、分解后子问题的大小以及子问题的求解策略可以将现有的训练算法分为三种:块算法、分解算法和顺序最小优化算法。
2块算法(Chunking Algorithm)块算法最早是由Bose r等人[1]提出来的,它的出发点是:删除矩阵中对应于La grange乘数为零的行和列不会对最终结果产生影响。
对于给定的训练样本集,如果其中的支持向量是已知的,寻优算法就可以排除非支持向量,只需对支持向量计算权值(即Lagrange乘数)即可。
但是,在训练过程结束以前支持向量是未知的,因此,块算法的目标就是通过某种迭代方式逐步排除非支持向量。
具体的做法是,在算法的每一步中块算法解决一个包含下列样本的二次规划子问题:即上一步中剩下的具有非零La-grange乘数的样本,以及M个(事先确定的)不满足Kohn -Tucker条件(公式7~8)的最差的样本;如果在某一步中,不满足Kohn-Tucker条件的样本数不足M个,则这些样本全部加入到新的二次规划问题中。
每个二次规划子问题都采用上一个二次规划子问题的结果作为初始值。
在最后一步时,所有非零Lagrange乘数都被找到,因此最后一步解决了初始的大型二次规划问题。
块算法将矩阵的规模从训练样本数的平方减少到具有非零Lagrange乘数的样本数的平方,大大减少了训练过程对存储的要求,对于一般的问题这种算法可以满足对训练速度的要求。
对于训练样本数很大或支持向量数很大的问题,块算法仍然无法将矩阵放入内存中。
3分解算法(Decomposition Algorithm)当支持向量的数目远远小于训练样本数目时,块算法显然能够大大提高运算速度;然而,如果支持向量的数目本身就比较多,随着算法迭代次数的增多,工作样本集也会越来越大,算法依旧会变得十分复杂。
因此,如果把问题分解成为固定样本数的子问题:工作样本集的大小固定在算法速度可以容忍的限度内,迭代过程中只是将剩余样本中部分/情况最糟的样本0与工作样本集中的样本进行等量交换,即使支持向量的个数超过工作样本集的大小也不改变工作样本集的规模,而只对支持向量中的一部分进行优化,这就是分解算法的基本思想。
分解算法最早是由Osuna等人[7]提出的。
后来C. W.Hsu和T.Joachims[8,9]等人又对其进行了改进。
在文献[7,10]中,麻省理工学院生物与计算学习中心的Edgar Osunal等人介绍了一种具体的算法,并对人脸识别问题进行了实验。
他们将样本集分为两个集合B和N,集合B中包含b个样本,他们作为子问题工作样本集进行SVM训练,集合N中n有个样本,且b+n=l,在每一个子问题的训练过程中,所有N中的样本所对应的Lagrange乘数固定不变。
子问题训练结束后,用所得到的决策函数对N 中的样本进行测试,用违反Kohn-T ucker条件(公式7~ 8)最严重的样本替换初始工作集中Lagrange乘子为零的样本,于是可以按照以下步骤迭代求解:(1)随机选择b个样本组成集合B,构造子问题;(2)求子问题最优解A i,i I B及b,并置A j=0,j I N;(3)计算F j,j I N,找出其中不满足条件(公式7~ 8)的样本j,与B中满足A i=0的样本i交换,构成新的子问题,返回第二步,直到N中所有样本满足条件(公式7~ 8)。
Osuna等证明了一个定理,该定理指出:如果存在不满足Kohn-Tucker条件的样本,那么在把它加入到上一个子问题的集合中后,重新优化这个子问题,则可行点(Feasible Point)依然满足约束条件,且性能严格地改进。
因此,如果每一步至少加入一个不满足Kohn-T uc ke r条件的样本,一系列的二次规划子问题可保证最后单调收敛。