SVM理论与算法分析

硬间隔线性支撑向量机

假设给定一个特征空间上的训练数据集：

T={Gi,yD,62,丫2),…，(XNJN)}

n

其中，XjGRzYie(+l,-l),i=1,2,…,N,Xj为第i个特征向量或实例,%为%的类标记，当y=1时，称Xj为

正例，当力=-1时，称片为负例；',力)为样本点。

假设训练数据集是线性可分的(存在硬间隔)，那么学习的目标是在特征空间找到一个分别超平面，能将实

例分到不同的类。分别超平面方程w-x+b=O,它由法向量W和截距b确定，可用(w,b)表示。分别超平面

将特征空间分为两部分，一部分是三类，一部分是负类。法向量指向的一侧为正类，另一侧是负类。

一般地，当训练数据集线性可分时，存在无穷个分别超平面可将两类数据正确分开,感知机利用误分类最小

的策略，求得分别超平面，不过这是的解有无穷多。线性可分支撑向量机利用间隔最大化求最优分别超平面，

解唯一。

一、模型推导

L函数间隔：一般来说,一个点距离分别超平面的远近可以表示分类预料的确信程度。在超平面w・x+b=0

确定的状况下，|w•x+b|能够相对地表示(留意：真实距离为野手)点x距离超平面的远近.而w•x+b的

IWII

符号与类标记y的符号是否一样能够表示分类是否正确。所以可用标量y(w-x+b)来表示分类的正确性及确信

度，值为正表示分类正确，值为负表示分类错误"

超平猷w,b)关于样本版X,,y、的函数间隔为:

Yi=yj(w-Xj+b)

超平面叫切关于训练数据集T的函数间隔：

Y=min%=minVj(w-x；+b)

i=l,2,...,Ni=l,2，…,N

2.几何间隔：函数间隔可以表示分类预料的正确性及确信度，但是选择分别超平面时，只有函数间隔还不够。

因为只要成比例地变更w和b,虽然超平面并没有变更，但函数间隔(它是(w,b)的线性函数)却依原比例同

等变更。为了将(w,b)表示的超平面的唯Tt,即每个超平面对应Rn+1中的唯一向量(w,b),可以对法向量W

加以规范化约束IIW11=1,这时函数间隔称为几何间隔。

超平跃w,b)关于样本虱A,y、的几何间隔为:

Yi_/wb\

丫户而"队而小+而)

超平面w,b)关于训练数据集T的几何间隔为:

丫=口萼%-=用%力(高・*+岛)

3.间隔最大化

支撑向量机学1习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分别超平面。对于线性可分

的训练数据集而言，线性可分分别超平面有无穷多个,每一个都是一个感知机，但是几何间隔最大的分别超

平面时唯一的。

间隔最大化的直观说明是：对训练数据集找到几何间隔最大的超平面意味着以充分大的却新都对训练数据进

行分类。也就是说，不仅将正负实例点要分开，而且对最难分的实例点(离超平面最近的点)也有足够多大

的确信度将它们分开。

因此所要优化的问题表示为：

max丫

改写为,

max-——-

w.b||W||

s.t.yj(w-Xj+b)>y,i=1,2,N

y的取值不影响最优化问题的解(假如w,b•是最优解，那么入w•，入b♦也是最优解，因此y是变动的可以取到随

意值，假如固定y,w*,b•也就变得唯一了)，令？=1,等价变换为，

max--------

w,b||W||

s.t.yj(w-Xj4-b)>1,i=1,2,...,N

(目标函数是支撑间隔，约束是样本点在间隔边界或外侧，目标是找寻支撑向量使得间隔最大化)等价变换

为(标准无等式约束的凸二次规划，这是为了运算便利)，

min-IIwII2

s.t.1—yj(w,Xj+b)<0,i=1,2,N

凸二次规划问题存在全局最优解w♦力•。

(4)分别超平面与分类决策函数

分别超平面:

w*•x+b"=0

分类决策函数:

f(x)=sign(w*,x+b*)

(5)支撑向量与间隔边界

在线性可分状况下，训练数据集的样本点中与分别超平面距离最近的样本点的实例称为支撑向量，支撑向量

是使约束条件等号成立的点，即1-%(w•为+b)=0,对于正例点，支撑向量在超平面w・*+b=1上，对

于负例点，支撑向量在超平面W•%+b=-1上，没有实例点落在这两个平行的超平面(间隔边界)之间，

这两个超平面之间的距离称为间隔,它依靠于分别超平面的法向量W,等于扁。

在确定分别超平面时只有支持向量起作用，而其他实例点并不起作用。假如移动支持向量将变更所求的解，

但是假如在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会变更的。明显支撑向量是训练集中

重要的样本。

二、模型求解

将原始问题转化为Lagrange对偶问题,通过求解对偶问题来获得原始问题的最优解：对每个不等式约束引入

Lagrange乘子四，

1.Lagrange对偶函数:

NN

2-W(Xiyi(wXi+b)+W

L(w,b,a)=

i=li=l

其中a=...,0tN)T为拉格朗日乘子向量，四N0,i=1,2,...,NO

2.对偶问题：

maxminL(w,b,a)

aw,b

(1)求minL(w,b,a)

w,b

N

一W四%Xi

VwL(w,b,a)=w0

i=l

N

VL(w,b,a)=一26力=

b0

i=l

得出

N

Xi

w=W四%

i=l

N

w四月=°

i=i

带入拉格朗日函数，得出

NNN//N\\N

minL(w,b,a)四巧力竹«•牛)一分四力|(W修).Xj+b)+乏%

i=lj=li=l\\j=l/Ii=l

1NNN

=一工W%咿yR,牛)+26

i=lj=li=l

(2)求maxminL(w,b,a)

aw,b

1NNN

-5WW%咿”(Xi,Xj)+W«i

(1=1j=li=l

N

s.t.W四0=0

i=l

«i>0,i=1,2,...»N

转换为求微小

1NNN

^22%%片“(4.牛)一2

(i=lj=li=l

N

WSK=°

S.t.

i=l

«i>0,i=1,2,...,N

依据对偶理论，对上述对偶优化存在，使W,b，是原始问题的解，a*感寸偶问题的解，因此求解原始问题,

可以转化为求解对偶问题。

3.最优解

依据KKT条件

Vw<L(w\b\a*)=w*一况143=0----------------------(a)

VyL(w*,b*,a*)=-Sili<Yi=0-----------------------------(b)

<(Yi(W-Xj+b*)-1)=0,i=1,2,...,N-----------------------------(C)

Yi(w*-X,4-b")-1>0,i=1,2,N----------------------------------(d)

a；>0,i=1,2，…，N----------------------------------------------------(e)

由(a)求得

N

i=l

其中至少有一个硫＞0（假如a*=0,那么w*=0,b，无解，明显它不是原始最优化问题的解），结合KKT

条件（C），得出

Yk(w*-xk+b*)-1=0

将w*带入KKT条件，得出

两边同时乘以yk,由于（yk）?=1

软间隔线性支撑向量机

一、模型推导

假如样本集中存在特异点使得样本集线性不行分，即不能满意函数间隔大于等于1不等式约束条件，为了解

决这个问题，可以对每个样本点(片，%)引入一个松弛变量4>0,使函数间隔加上松弛变量大于等于1.这样

约束条件变为

yi(w*-i+b*)>l-5i

同时对每个松弛变量&,支付一个代价年,目标函数变成

N

min-11w||2+eV国

w,bL乙，

i=l

这里，C>0称为惩处参数，一般由应用问题确定，c值大时对误分类的惩处增大，C值小时对误分类的惩处

减小。最小化上述目标函数有两层含义，要使的｝IIW||2尽量小即间隔尽量大，同时使的误分类的点的个数尽

量小，C是调和二者的系数。这时的间隔称为软间隔，因为间隔内含义特异点。

原始优化问题：

N

min-||w||2+eV5

w.b2Z-j

i=l

s.t.1-5j-Yi(w•X)4-b)<0,i=1,2,...,N

>0,i=1,2，…,N

这仍是一个二次凸优化，存在全局最优解，W的解是唯一的，但b的解不唯一，b的解存在于一个区间。

二、庭求解

仍运用Lagrange对偶方法求解

1.Lagrange函数

1NNN

L(w,b,$aM=彳Hw俨+CW8-£ai(H(w•Xi+b)—1+&)—W内七

i=li=li=l

其中，cqN0,内N0。

2.对偶问题：

maxminL(w,b,ga,n)

apw,b，E

(1)求嬲L(w,b<a,p)

VwL(w,b,*a,p)=w一1四力x,=0

i=l

N

VbL(w,b,$a,u)=-Za.yi=0

i=l

V[L(w,b,a,p)=C-1T-aT-pT=0

得出

N

w=乏四力Xi

i=l

N

WotiYi=o

i=i

C-Qj—|lj=0

带入拉格朗日函数，得出

minL(w,b,&aM=—?乏W叫与力"国.Xj)+2四

i=lj=li=l

留意它与H无关。

(2)求maxminL(w,b,5,a,n)

aw,b，l

NNN

max一乏%%力力(、,’%)+W%

22i=l

N

stW%%=0

i=l

a,>0,i=1»2,...,N

Pi>0,i=

C—a；—|ij=0fi=1,2,...,N

消去内，转换为求微小

min

a

i=lj=li=l

N

S.t.WaiYi=0

i=l

ctj>0,i=1,2,...»N

0<aj<C

(3)最优解

依据KKT条件

Vw*Mw*,b*I，a*N)=w*—优=a；/Xi=0(a)

VbxL(w*,b*W,Q)=-型Ei=0------(b)

T

VvL(w*,b*,「a\n*)=C-l-a--p*=0--(c)

a；(yi(w*•Xj+b*)—1+《；)=0,i=1,2,...,N----------------(d)

痴后=0,i=l,2,...,N---------------------------------------(e)

>0,i=1,2,...,N------------------------------------------(f)

y.(w*•*+b*)-1+培N0,i=1,2,,N---------------------(g)

a*>0,i=1,2,...,N-----------------------------------------(h)

>0,i=1,2，…，N……--------------------------……——(i)

由(a)求得

N

w*=2^a；yixi

i=l

由(c)、(e)、(i)得出

(C-呜岗=0

C-a；>0

再结合(f)得出

假如a；<C,那么寻=0；假如a：=C,^>0;................................(j)

由(d),(h)得出

假如a；>0,那么R(w*•Xj+b")-1+埼=0;假如呜=0,y((w*•X]+b*)—1+*不确定；--------(k)

由(j),(k)得出

假如0Va；VC,那么百=0,yi(w-•Xi+b")-1+4=0,因此为(w*•Xi+b・)=1;

N

b*=ykXj)

j=i

由(j),(g)得出

假如a；=0,那么可=0,yi(w*X1+b*)>l；这说明Xi位于间隔边界上或以外；

由⑴，(k)得出

假如a；=C,那么％(w*•与+b*)=1-Z0;

此种状况下，进一步探讨：

假如¥=0,那么Xi在间隔边界上；

假如0V<1,那么由分类正确，*在间隔边界与分别超平面之间；

假如¥=I,那么Xi在分界面上；

假如K>1,那么Xi在分别超平面误分一侧；

因此可以看出，软间隔的支撑向量(a；>0)*或者在间隔边界上，或者在间隔边界与分别超平面之间，或

者在分别超平面误分一侧。

3.支撑向量的另一种说明

最小化以下目标函数：

N

2

，口-Yi(w-X,+b)]++A||w||

i=l

第一项是阅历损失或阅历风险，函数称为合页损失函数L(y(w-x+b))=[l-yi(w-xi+b)]+,下标"+"表

示以下取正值得函数。

「1fzZ>0

[Z]+=10z<0

也就是说，当样本点被正确分类且函数间隔大于1时,损失函数为0,否则(片为支撑向量时)损失函数是

1-y4w•片+b),其次项是系数为4的w的L2范数，是正则化项；这两种优化是等价的(通过变量替换方

法)；

非线性支撑向量机

对于分类问题是非线性的（线性模型无法将正负实例正确分开），可以利用核技巧，进行一个非线性变换，

将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。

用线性分类方法求解非线性分类问题问题分两步：首先运用一个变换将原空间的数据映射到新空间；然后再

新空间里用线性分类学习方法从训练数据中学习分类模型；

核技巧应用到支持向量机，其基本思想：

通过一个非线性变换将输入空间（欧氏空间R11或离散集合）对应于一个特征空间（希尔伯特空间H）,

使得在输入空间W中的超曲面模型对应于特征空间H中的超平面模型（支撑向量机），这样分类问题的学习

任务通过在特征空间中求解线性支撑向量机就可以完成。

一、非线性支撑向量机

在线性支撑向量机的对偶问题中,无论是目标函数还是决策函数（分别超平面）都只涉及输入实例与实

例之潮勺内积,假如把这个内积。•Xj看作是希尔伯特空间中的两个特征的内积蚁幻•（/）（%；）=K（"）=

A，Xj,其中X[=。（吟，xj=</>（%；）,那么对于在低维线性不行分的样本氯X：,i=1,2，…,N],假如通过映

蝌变换到高维希尔伯特空恒心》,i=1,2，…,N）变得线性可分（假设能找到这样的合适的映射g）z那么就可

以运用核函数代替计算xa,这里Xj未知,但x]x；,K®，M）艮双

运用核函数后的对偶问题的目标函数成为：

1NNN

W（a）=万｛W叫四力力K（Xi.x。一2四

i=lj=li=l

最优解成为

N

W*=2^afYiXi

i=l

N

4

b=yk-^a；yjK（xj-xi）

j=i

分类决策函数成为

fM=signa；yiK（Xi-x）+bj

在实际应用中，往往依靠领域学问干脆选择核函数:核函数选择的有效性须要通过试验验证。

二、核函数方法

核函数：设X是输入空间（欧氏空间Rn的子集或离散集合）,H为特征空间（希尔伯特空间），假如存在一

个从X到H的映射，

（|）（x）:X->H

使得对全部X,zEX,函数K（x,z）满意条件

K（x,z）=6（x）•巾（z）

则称K（x,z）为核函数，6（x）为映射函数，（|）（x）•巾（z）为（|）（x）和6（z）内积；

（希尔伯特空间是完备化的内积空间,其中的每个元素是一个向量（可以无穷维），向量之间定义有内积运

算,且空间关于内积诱导出的范数是完备的）

核技巧的想法是：在学习与预料中只定义核函数K（x,z）,而不显示地定义映射函数也，因为通常干脆计算

K（x,z）比较简洁,而通过Q（x）和0⑵计算K（x,z）并不简洁。留意，0（x）是输入空间R11到特征空间H的映射，

特征空间HT殳是高维的，甚至是无穷维的。我们须要的是特征空间中两个特征的内积结果,而不是特征的

表丞j假如我们能通过简洁的函数K(x,z)得到巾(x)•巾⑵的内积，那就简化了问题，不用考虑巾的形式，这正

是核函数的妙用之处。

对于给定的核函数K(x,z),特征空间H(希尔伯特子空间)和映射函数巾的取法不唯一，因为核函数给出

的是映射后的内积结果，所选取的映射过程可能是不同的。

核函缴定定理：设K：XxXtR是对称函数，则K(x,z)为正定核函数的充要条件是对随意引€X,i=

1,2,…,m,K(x,z)对应的Gram矩阵:K=[K6•内)mxm]是半正定的。

对于一个详细函数K(x,z)来说，检验它是否为正定核函数并不简洁，因为要去对随意有限输入集验证K对应

的Gram矩阵是否为半正定。在实际问题中往往应用已有的核函数。

常用核函数：

(1)多项式核函数：K(x,z)=(x•z+1尸,对应的支撑向量机是一个p次多项式分类器；

(2)高斯核函数：K(x,z)=exp(-甯)，对应的支撑向量机是高斯径向基函数分类器；

(3)字符串核函数：

1)基本定义：

有限字符表£；

字符串s:s(l)s(2)...s(|s|)z字符串s的长度|s|,空字符串长度为0;

字符串连接：St,5和L分别是字符串；

长度为n的字符串集合£n；

全部字符串的集合：£*=11二()即；

S的子串u:给定一个指标序列i=1wii<i2<…<i|U|4⑸,u=s(i)=s(i1)s(i2)...s(i|U|),其

长度记作I⑴=i|u|-h+1,假如i是连续的,则1。)=|u|；否则l(i)>|叽

2)映射定义:

假设S是长度大于或等于n字符串的集合,s是S的元素,建立字符串集合S到特征空间Hn=R暧的映射

6式S),RE”表示定义祗n卜的实数空间，其每一维对应一个字符串ueXn,映射将字符串s对应于空

间中R*的一个向量,其在u维上的取值为

[071(s)]〃=Si：S(i)=U^(0Z

这里,0<A<1是一个衰减参数,1(。表示字符串i的长度,求和在S中全部与u相同的子串上迸行。

说明：u代表维,如在字符串u维,明显空间有腰维,每一维是字母表工上的一个长度为n的字符串;

s(i)是表示通过指标序列i,表示的一个s的子串，这个子串可以不连续；s(i)=u表示s的子串s(i)等于u;

l(i)是子串s(i)在s中的指标序列i的最终一个重量减去第一个重量然后加一；

例子：假设Z为英文字符集，n为3,S为长度大于或等于3的字符串集合，考虑将字符集S映射到特征空间

H3=产3,%的一维对应于字符串asd,这是，字符串"Nasdaq"在这一维上的值是[内(Nasdaq)Kd=

5

只有T子串asd,序号是234;字符串"lassdas"在这一维上的值是[加(lassdas)]asd=2A,因为有两

个asd,序号分别为236,246;

3)核函数

两个字符创s和t的字符串核函数是基于映射的特征空间中的内积：

kn(S,t)=如(S)]“血(£)]〃=WW貂⑴

uernuern(ij)：s(i)=t(j)=u

它给出了字符串s和t中长度等于n的全部子串组成的特征向量的余弦相像度.直观上，两个字符串相同的

子串越多，它们就越相像，字符串核函数的值就越大，字符串核函数可以由动态规划快速计算。

序列最小最优化算法

支撑向量机的学习问题可以形式化为求解凸二次规划问题，具有全局最优解，并且有许多最优化算法可以用

于求解这一问题。但是当训练样本容量很大时,这些算法往往变得特别低效。序列最小最优化算法，由Platt

在1998年提出，它是一种启发式算法，相对上匕较高效。

SMO算法基本思路是：假如全部变量的解都满意次最优化问题的KKT条件，那么这个最优化问题的解就得

到了，因为KKT条件是该最优化问题的充分必要条件,否则，选择两个变量，固定其他变量，针对这个两个

变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应当更接近原始二次规划问题的解，因

为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，子问

题有两个变量，一个是违反KKT条件最严峻的那一个，另一个庄约束条件自动确定-如此，算法将原问题不

断分解为子问题并对子问题求解，进而达到求解原问题的目的。

原始优化问题：

N

min-||w||2+eV4

w,b，EZ乙」

i=l

s.tyj(w-X,+b)>1-,i=1,2,...,N

>0,i=1,2,N

对偶问题：

〔NNN

吗“万2W四%力丫加收”牛)一£四

i=lj=li=l

N

S.t.乏aiVi=0

i=l

0<Qj<C,i=1,2,...,N

子问题的两个变量只有一个是自由变量，假设％,。2为两个变量，固定。3，«4，…，«N，那么依据上面的等

式约束可知：

N

«1Y1=-2

i=3

由于yi*Yi=1/所以

N

=-YiW四%

i=2

假如确定，那么由也随之确定，所以子问题中同时更新两个变量。

优化子问题：

SMO算法包含两个部分：求解两个两个变量二次规划的解析方法和选择变量的启发式方法。不失一般性，假

设选择的两个变量是,。2，其他变量。3，，…，ON固定，于是SMO的优化问题的子问题可以写成：

]]NN

minW(%,a?)=5Kna?+-K22a^+yiy2K12a1a2-+a2)+丫必'+y2c2[力四长2

，a2i=3i=3

N

s.t.a1y1+a2y2=-^aiyi=<;

i=3

0<aj<C,i=1,2

其中,旧=K(Xj,Xj),ij=1,2，…,N,s是常数，目标函数中省略了不含四,。2的常数项。

(1)求解两变量二次规划的解析方法：

■可行解范围：

假设子问题的初始可行解为哨M,吗”，最优解为吧ew,anew,明显最优解受等式约束(直线约束)和

不等式约束(盒子约束)条件的限制：

0<吗<C------------------------(a)

ew,dew

0<a?=y.一吗ewy2yl=%(a；】dyi+a°y2)-agy2yi<C

化简为

ew,dew

0<a；ew=y遥_ajy2y1=a?+ag^yzYi—ctjy2y1<C

>假如y2=yi»那么

,d

0<a?+叫Id-anew<c

a?,d+吗E-C<吗ew<a?Id+娉d-----------------------(b)

由(a),(b)得出：

假如y?=Yir那么L=max(0,a?,d+a?ld-C)<a^ew<min(a;,d+a^d,C)=H................(C)

>假如丫2工yi<那么

,d

0<a?-吗d+吗ew<C

吗Id_aold<anew<C_aold+aold.................(d)

由(a),(d)得出：

假如丫2#yi,那么L=max(O,a?ld-a?ld)<ajew<min(C-a?,d+砂,C)=H------------(e)

假如最优解不在约束内，必需被剪辑。假设在沿着约束方向a1yi+a2y2=q未经剪辑时。2的最优解为

a：w，unc；然后再求剪辑后的解吗ew.

■下面忽视不等式约束，求取迭代解《""，UnC：

K22«2+y】y2K12%。2-（％+«2）+yi«i（金％四收1）

由于由yi=q-a2y2，得出

«iyiYi=（s-a2y2）y1

=（9-a2y2）y1

带入目标函数

W(a)=TK(^-ay)2+-Kai+yK(^-ay)a2~(＜；-«2y2)yi-«2+(，-a2y2)(2力5%1

2乙11乙222221222

\t=3

+y2a2(£力四%2)

对。2求导

9W件邓J+y2。力。得2)

旃=-y2Kli(S-a2y2)+K22a2+y2Kl2s-2Kl2a2+Y1Y2_1_Yz

=一丫2%遇+a2Kli+K22c2+y2Kl2S-2Kl2a2+YiYz-1一丫2(金力印打)+Vzgyi«jKJ

i2

i=3

N

力哂，+y2力印，

=一丫2&1，+«2(K11+K22-2K12)+y2Kl2s+YiYz-1-Yz

a

=2(Kn+K22-2K12)-y2y2-y1+KU(；-K12＜；+

令其为0,得到

《ew,unc(K[]+_2Kl?)=y2y2.Yi+Ku,—K2S+

将,=a?,dy!+吟dy?带入，得到

a广u.K+K22-2K12)

ld

Ǥy2+(g

ld,d工力。得2

=y2y2-yi+Ku。泮%+Kua§y2-K12a?yi-K12yj«iKii

i=3i=3

,dld

^YiOiKii-yia?Kn-y2a?K21

，d：d

y2y2-yi+K^a泮yi+Kua5y2-K12瞰yi-K12a?y2+

ld,d

-([Jyi«iKi2-yia?K12-y2a5K22

,d,d,dldld|

=y2y2-yi+Kna?yi+Kna5y2-占2。”丫1一K12a5y2-yia?Kn-y2a2＜2i

NN

lc,d工力四％1-2%四s2

+y1a?K12+y2a5K22+

=1i=l

/NN

,d

Y2-yi+(Kn+K22-2K12)a?y2+('力四K1一'为四K2

(\i=li=l

NN

=(Ku+-2K12)+y21y2-y1+

K22吟日〉YiOtiKi!-y为四与2

N

,d2%四51一丫1

=(K11+K22-2K12)a?+y2yi«iKi2-y2

i=l

令Ei=邓1*6。+b-力，i=1,2；其中邓旧印旧+b是对输入Xj的预料，因此Ej表示对输入Xj的预料

与真实输出力之差；那么

,d

=(Li+K22