支持向量机及其算法研究

支持向量机及其算法研究

Support Vector Machines and Application Research Overview

杜晓东3　李岐强DU Xiao 2dong LI Qi 2qiang

摘　要

　本文首先概要介绍了支持向量机的理论背景,然后结合目前一些主要的S VM 训练方法以及它们之间的联系,比较了各种算法的优缺点。重点阐述了其中最有代表性的序贯最小优化(S M O )算法及其多种改进方案。最后指出了S VM 及其算法进一步研究和亟待解决的一些问题。

关键词

　支持向量机　统计学习理论　S M O

Abstract The paper first reviews the principles of S VM ,then introduces s ome important and newest learning alg o 2

rithm.All the kinds of alg orithm ’advantages and disadvantages were analyzed.Sequential minimal optimization (S M O )and it ’s improved versions was discussed in detail.S ome important issues about S VM and S M O are proposed to be in 2vestigated and the directions of research have been pointed out als o.

K eyw ords Support vector machine S tatistical learning theory S M O

3山东大学(南校区)控制学院模式识别与系统工程研究所　250061

1　引言

支持向量机(Support Vector Machine ,S VM )[122]是近年来在模式识别与机器学习领域中出现的新工具,其核心内容从

1992年才开始提出,1995年Vapnik 的《The Nature of S tatistical Learning Theory 》一书的出版,标志着统计学习理论体系已走

向成熟。S VM 以统计学习理论为基础,有效地避免经典学习方法中过学习、维数灾难、局部极小等传统分类存在的问题,在小样本条件下仍然具有良好的范化能力,因此受到了广泛的关注,而且成功应用到了人脸识别[3,4]

,文本分类

[5]

,基因

分析

[6]

,手写体识别

[7]

,语音识别

[8]

等多种领域。

S VM 的训练问题实质上是一个二次规划(QP )问题。在

最优化理论中已有多种成熟算法来解决此问题,如内点法,共轭梯度法。但是传统算法在每一步迭代都涉及到核函数矩阵的运算,而核函数矩阵占用的内存随样本数呈平方增长,如计算4000个样本的核函数矩阵就需要128M 内存

[2]

。

而且由于迭代误差的积累,也会导致算法精度难以接受。因此设计适用于针对大量样本的算法就成为近年来S VM 研究的重要内容。支持向量机有效实现算法的出现也极大的推动了这一理论的应用。

该文在简要介绍支持向量机理论背景的基础上,对其算法进行综述,最后指出了进一步研究和亟待解决的问题。

2　支持向量机的理论背景

2.1　统计学习理论

统计学习理论(S tatistical Learning Theory )[1]是Vapnik 等人在20世纪70年代末提出并在20世纪90年代逐渐完善的一种针对小样本的机器学习理论。它的核心问题是寻找一种归纳原则以实现最小化风险泛函,从而实现最佳的推广能力。

Vapnik 提出了VC 维的概念来标志函数集的复杂程度,

并用这个概念给出了与分布无关的学习机器推广能力的界。这个界由两部分构成:经验风险和置信范围(以VC 维为参数)。学习机器能力过强(VC 维很大),虽然能取得小的经验风险,但置信范围会很大;VC 维太小又会导致大的经验风险。一个好的归纳原则必须在二者之间作出权衡。结构风险最小化原则(SRM )正是这样一种归纳原则。SRM 原则定义了在对给定数据的逼近精度和逼近函数的复杂性之间的一种折衷。

2.2　S VM 的基本原理

S VM 是统计学习理论的重要成果。

假定训练数据(x 1,y i ),...,(x l ,y l ),x ∈R n ,y ∈{+1,21}可以被一个超平面(w ?x )-b =0没有错误地分开,与两类样本点距离最大(称为边缘最大)的分类超平面会获得最佳的推广能力。最优超平面将由离它最近的少数样本点(称为支持向量)决定,而与其它样本无关。我们用如下形式描述与

样本间隔为Δ的分类超平面:

(w ?x )-b ,‖w ‖=1y =1,若(w ?x )-b ΕΔy =21,若(w ?x )-b Φ-Δ

Vapnik 给出了一个关于Δ-间隔分类超平面VC 维上界

的定理:如果向量x 属于一个半径为R 的球中,那么Δ-间隔分类超平面集合的VC 维h 有下面的界:

h Φmin

R

2

Δ2

,n +1

这样,S VM 首先保证了一个小的经验风险(在训练样本可分时就是零),并通过选择边缘最大的超平面的方式控制了函数集的VC 维,这正是SRM 原则所要求的。

3　支持向量机的数学模型

3.1　线性支持向量机

支持向量机的原理是用分类超平面将空间中两类样本点正确分离,并得到最大的分类间隔,我们将S VM 的最优化问题中的分类超平面归一化:令Δ=1,而w 和b 可以按比例缩放。离超平面最近的样本(支持向量)满足

(w ?x i )-b =1,若y =1(w ?x i )-b =-1,若y =21

支持向量到超平面的距离为1Π‖w ‖。原问题就转换成一个有约束非线性规划问题:

Minimize

Φ(w ,b )=12

‖w ‖2

s.t. y i (x i ?w +b )-1Ε0 i =1,2,…,1

目标函数是严格上凹的二次型,约束函数是下凹的,这是一个严格凸规划。按照最优化理论中凸二次规划的解法,我们把它转化为W olfe 对偶问题来求解:

构造Lagrange 函数:

L (w ,α,b )=

12

‖w ‖2

-∑1

i =1αi y i (x i ?w +b )+∑1

i =1αi ,αi Ε0,i =1,2,…,1(其中αi 是Lagrange 乘子。

)它应满足条件 w L (w ,α,b )=0,99b L (w ,

α,b )=0,(K uhn 2Tucker 条件),即w =∑i

αj y i x i 和∑i

αj y i =0。

将两式代回Lagrange 函数中,消去w 和b ,经运算得到原最优化问题的W olfe 对偶问题:

Maxmize w (α)=∑1

i =1αi

-12∑1i ,j αi αj y i y j x i ?x j

s.t ∑1

i =1

αi y i =0

αi Ε0

i =1,…,1其解是原最优化问题的整体最优解。解出αi 后利用∑i

αi y i x i 确定最优超平面,注意到只有支持向量所对应的Lagrange 乘

子αi 才不是0。

利用W olfe 对偶问题,不但使问题更好处理,而且使样本在新问题中仅以向量点积的形式出现,正是这一重要特点,使支持向量机法能推广到非线性情况。

3.2　非线性支持向量机

把寻找最优超平面最终归结为其W olfe 对偶问题克服了

“维数灾难”:利用核函数K:(R n ,R n

)→R 使得K (x i ,x j )就等

于x i ,x j 在高维特征空间中的映射之点积,用K (x i ,x j )代替

W olfe 对偶问题中x i 和x j 的点积即可,计算量将会大大减少。

这样只需在输入空间中计算卷积核函数,而不必知道非线性映射的形式,也不必在高维特征空间中进行计算。

此时输入空间中的判别函数是:

f (x )=sign

∑支持向量

y i αi

3

K (x i ,x j )-b )其中:选择一个小于C 的正分量αj

3,并据此计算b 3

=y i 2∑支持向量

y i αi

3

K (x i ,x j )如果支持向量很多的话,决策阶段的

计算量也将是较大的。

3.3　线性不可分情况的处理

为了使S VM 算法能应用于不可分情况,C ortes 和Vapnik 在1995年引入了软边缘最优超平面的概念,引入非负变量

ξi

,将约束条件放松为:

y i (x i ?w +b )-1Ε1-ξi ,

i =1,2,…,1同时对目标函数引入惩罚项:

Φ(w ,ξ)=12

‖w ‖2

+C ∑1

i =1ξi 求解这个二次规划问题,推导所得的W olfe 对偶问题为:

Maxmize w (α)=∑1

i =1αi -12∑1

i ,j αi αj y i y j x i ?x j

s.t ∑1

i =1

αi y i =0

C Εαi Ε0

i =1,…,1唯一的区别在于对αi 加了一个上限限制。

S VM 是一种基于SRM 原则的以样本间的某种距离作为

划分依据的模式识别方法,它可以在高维空间中构造较低

VC 维的函数集,从而获得好的推广能力,它的数学模型中样

本仅以点积形式出现,使得这种方法很容易推广到非线性。

4　S VM 的训练算法

注意到支持向量机中凸二次规划这一特殊的最优化问题具有一些良好的特性,如解的稀疏性和最优化问题的凸性,这使得可能构造使用较少存储的快速专用算法。即将大

规模的原问题分解成若干小规模的子问题,按照某种迭代策略,反复求解子问题,得到原问题的近似解,并能逐渐收敛到

原问题的最优解。根据子问题的选取和迭代策略的不同,算法大体分为选块算法,分解算法和序列最小优化方法。

4.1　选块算法

由于问题的解只是依赖与支持向量对应的样本点,因此可以事先选择那些支持向量,保留其对应的样本点,并删除其他的样本点,可以建立相同的决策函数。块算法最早是由Boser等人提出来的,其目标就是通过某种迭代方式逐步排除非支持向量。其具体做法是首先从训练样本集中选择任意一个子集,利用标准的优化算法求解对偶问题,保留其中的支持向量对应的样本,舍去其它的样本点,然后利用新得到的决策函数检验剩余的训练样本,将其中M(事先确定)个违背KK T条件最严重的样本点加到新块中去求解,直到满足某一个停机的准则。每个二次规划子问题都采用上一个二次规划子问题的结果作为初始值。

显然,这种方法可以减少问题的规模,尤其对于支持向量数目远远小于训练样本数目的情况,但是如果支持向量的数目比较多,算法又需要处理较大的黑塞矩阵,使得算法变得缓慢而失效。

4.2　分解算法

如上所述当支持向量较多时,块算法可能会失效,这时可以利用另一种方法———分解。Osuna等人最早提出分解算法,其思想是每次只是更新若干个Lagrange乘子,而其它的乘子不变,迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换,即使支持向量的个数超过工作样本集的大小也不改变工作样本集的规模,而只对支持向量中的一部分进行优化。对于分解算法,关键是对样本点换入换出策略的选择上,Joachims提出了一些启发式的迭代策略有助于提高算法的收敛速度,并在软件包S VM light中具体实现,其基本改进思想是在工作样本集的选择上,S VM light中是沿着最速下降可行方向d,d仅含q个非零元素,由非零元素对应的q个优化变量构成工作样本集。已经证明了只要最速下降可行方向d存在,则用相应子集构成的子问题可以进一步优化,而子问题的可行解也是原问题的可行解。而且该算法采用连续收缩和对常用的参数进行缓存的方法,提高训练速度,适合求解大型支持向量机中优化问题。张学工提出了CS VM算法,其原理是把每类训练样本集进行聚类分成若干子集,用子集中心组成新训练样本集训练S VM,该算法在提高算法速度的同时,减少了野点对结果的影响。但是牺牲了解的稀疏性。

对于分解算法,Osuna等证明了一个关键定理:如果存在不满足K ohn2Tucker条件的样本,那么在把它加入到上一个子问题的集合中后,重新优化这个子问题,则可行点依然满足约束条件,且性能严格地改进。因此,如果每一步至少加入一个不满足K ohn2Tucker条件的样本,一系列的二次规划子问题可保证最后单调收敛。这对于下面的序列最小优化算法提供了理论依据。Lin证明在一定条件下采用可行方向策略的分解算法,其{ακ}的任意聚点是对偶优化问题的全局最优解。当q=2时,Lin证明无须该条件,还证明在一定条件下,采用可行方向策略的分解算法具有线性收敛速度。4.3　序列最小优化算法(Sequential Minimal Optimization2 S M O)

S M O方法可以看作是分解算法的一个特例,它将子问题的规模减少到了最小。它由微软研究院的John C.Platt等人提出并做了多次改进。根据分解算法的原理,在优化过程中换入换出样本点但保持非工作集的Lagrange乘子不变,S M O 方法将工作样本集的规模减到了最小———两个样本,这样就满足分解算法的原理,即满足等式线性约束的存在使得同时至少有两个Lagrange乘数发生变化。由于子问题的优化只涉及两个变量,而且应用等式约束可以将其中一个变量用另一个变量线性表示出来,所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来,而不用在算法的迭代中求解二次规划问题。它在每一步迭代只是选择两个变量进行调整,同时固定其他变量,通过求解最优化问题,得到这两个变量的最优值,来更新相应的Lagrange乘子。

虽然我们可以按顺序遍历抽取两个Lagrange乘数的所有组合,也可以使Lagrange乘数优化,但是为了提高算法,还需要一定的原则来设计更快的寻找样本点的方法,根据上述算法原理,Platt设计了一个两层嵌套循环:外层循环首先遍历非边界样本,因为非边界样本最需要调整,确定哪些样本违反了KK T条件来进行调整,当所有的非边界样本都满足KK T条件后,再在整个样本空间循环一遍,来检验所有的样本是否都满足KK T条件,如果还有不满足的就再次遍历非边界样本,这样循环进行,直到所有的样本点都满足KK T条件。而内层循环是针对以上违反KK T条件的样本来选择另一个样本与它配对优化,其选择的准则是使选择的一对样本能够对决策函数得到最大的优化步长。

S M O算法速度的瓶颈是在最优条件的判断和在非线性情况下误差的重置方面,本质原因是由于对所有的向量逐个地计算核函数,而核函数本身计算就比较复杂。所以近来对于S M O算法的改进集中在这两个方面。其中,K eerhti对Platt 的S M O算法进行了改进,在迭代过程中的判优条件和循环策略上做了一定的修改,保证了算法的收敛,并减少了迭代的次数,加快了算法的速度。并于此后提出了G eneralized S M O(G S M O)算法,利用violating pair的概念确定工作集,并证

明Πτ>0,以τ2violating pair为工作集则G S M O算法有限终止。G inny在其博士论文中详细阐述了S M O的工作机理,并在算法优化Lagrange乘数方面做出改进,尤其给出了详细的软件实现过程。对于算法结构,文献[5]做了有益的尝试,算法结合分块和分解算法的优点,利用一些策略避免了删除支持向量的可能,并分析了分块大小的影响,指出算法在支持向量较少的情况下可以取得较好的效果。文献[6]提出一种高效的计算决策函数的缓存策略,该策略充分利用了S VM 训练过程中到达上界的拉格朗日乘子变化平稳的特性,有效地降低了计算决策函数的代价,采用该缓存策略的S M O算法在运算速度上得到了显著的提高,而且缓存策略很容易推广到其他分解算法中。文献[7]给出了一种可行方向解释,在综合考虑与工作集相关的目标函数的下降量和计算代价的情况下,提出了一种收益代价平衡的工作集选择方法,提高了缓存的效率,试验证明该方法特别适用于样本较多,支持向量较多的情况。值得注意的是Jain2X iong依据分解的方法提出一种改进的S VM训练算法。实验表明该算法在不牺牲推广能力的情况下比改进的S M O算法速度提高约9倍。

5　结束语

S VM本质上是一种基于统计与PAC学习的非参数机器学习方法,寻找更好的理论模型来改进S VM正成为该领域的研究难点,同时对于S VM的求解算法的改进也方兴未艾。但是S VM仍然存在很多的重点和难点:

511　核函数构造问题

核函数的构造虽然有定理限制,但是对于实际的问题其构造多依赖经验,如何根据经验知识和实际问题,选择和构造核函数至今还缺乏相应的理论指导。

512　处理大规模数据的问题

现在虽然对于S VM产生了一些有效的解法,如S M O及其改进方法,但是如何更好的解决算法的速度和数据集的大小之间的矛盾仍是待研究的问题。

513　对于多类问题

S VM是针对两类问题提出的,在推广到多类问题时的有效算法还有待研究,而且理论证明还不完善。

514　S VM是实现结构风险最小化的成果,但是具体如何实现及其一些关键性的数学证明还没有完备的理论。

此外,S VM方法虽然在实际的应用中已经取得了很大的成功,但是其应用范围仍然没有神经网络广泛,所以应用领域的拓展和如何更有效地应用该理论方法给众多研究者提出了机遇和挑战。

参考文献:

[1]　Vapnik V.统计学习理论的本质[M].张学工.北京:

清华大学出版社,2000.Vapnik V.The Nature of S tatisti2 cal L earning Theory[M].H ANG Xueg ong.Beijing:Tsinghua University P ress,2000.(in Chinese)

[2]　Burges C.A tutorial on support vector machines for pattern

recognition[J].Data Mining and K now led g e Discovery, 1998,2(2):143.

[3]　Osuna E,Freund R,G irosi F.Improved training alg orithm for

support vector machines[C].In:7th IEEE w orkshop on Neural Netw orks for S ignal Processing,NNSP97,IEEE,1997:276～

285.

[4]　Bernd Heisele et al.Hierarchical classification and feature re2

duction for fast face detection with support vector machines [J].Pattern Recognition,2003:36:2007～2017.

[5]　吴翔,谭李,陆文凯,张学工.提高超大规模S VM训练

计算速度的研究.模式识别与人工智能.2003,16(1):

46～49.

[6]　孙剑,郑南宁,张志华.一种训练支撑向量机的改进贯

序最小优化算法.软件学报.2002,13(10):2007～2013.

[7]　李建民,张钹,林福宗.序贯最小优化的改进算法.软件

学报.2003,14(5)919～925.

[8]　Jain2X iong D ong,Ching Y S,Adam K.A Fast S VM T raining

Alg orithm[J].International Jouranl of Pattern Recognition and Artificial Intelligence,2003,17(3):367～384

[作者简介]　杜晓东(1981.22),男,汉族,山东聊城,系统工程专业,山东大学硕士研究生,研究方向:数据挖掘与模式识别。

(收稿日期:2004212210)