支持向量机(经典)

§4-1. 线性分类问题的支持向量机

一、 分类问题与机器学习

设有两类模式C1和C2，TX1, y1X2, y2XN, yN是从模式C1和C2中抽样得到的训练集，其中XnRM、yn1, -1。若Xn属于C1类，则对应有yn1；若Xn属于C2类，则对应有yn1；。寻求RM上的一个实函数gX，对于任给的未知模式，有

gX0, XC1 或者 gX0, XC2 C 1gX1, X sgn (4-1) ,  C2gX1Xsgn式中sgn为符号函数，gX称为决策（分类）函数。

前两章学过的前向神经元网络和径向基网络，都可以用来解决此类问题。这一章，我们称解决上述问题的方法为“分类机”。当gX为线性函数时，称为线性分类机；当gX为非线性函数时，称为非线性分类机。

举例：患有心脏病与年龄和胆固醇水平密切相关。对大量病人进行调查，得到表4-1所示数据，图4-1是数据的分布示意图。

表4-1 编号 年龄x1 胆固醇x2 患病否y 1 2 3 4 5 6 56 55 70 74 59 68 192 205 177 155 198 171 -1 1 1 -1 1 -1

图4-1.样本分布

根据数据Xx1x2分布以及所对

应的y值，我们可以目测获得一条分类线gX。gX不仅可以将两类模式分开，并且具有最宽的“边带（Margin）”。以后，对任意一个被观察者进行检验，得到

1

其数据Xx1x2后，若X处于gX上边，即可判定为心脏病疑似；处于gX下边，则认为没有患有心脏病。

以上仅用年龄和胆固醇水平来判定是否患有心脏病显然是极其不可靠的。也就是说仅凭x1和x2两个参数不足以判别一个人是否患有心脏病，还必须考虑更多的参数，Xx1这种情况下已无法人为直观地确定判x2xN的维数很高。

别函数gX了。于是，我们需要一种根据给定的大量样本确定判别函数的方法，即需要一个能够由经验数据学会对某些模式进行分类的“学习机”。

二、 两类可分问题的线性分类机

实际上，以前讲过的“采用硬限幅函数的单个神经元”就是一个线性分类机。这里，我们从最大分类间隔角度，导出另外一种线性分类机。

仍以图4-1为例，对于这个二维问题，线性分类机的作用就是要在C1和C2之间寻找一条分类线l，其表达式为gX。我们已经熟知，在高维情况下gX是一个超平面。

对于线性可分的两类模式C1和C2而言，能够准确将其分开的直线不是唯一的。假设有直线l可以无误地将C1和C2两类模式分开，另有直线l1和直线l2与l之间的间距为k， l1与l2之间形成一个没有学习样本的带状区域，不妨称该带状区域为“边带（Margin）”，而l是边带的中分线。显然，最合理的分类线应该具有最宽的边带。

假设，已知分类线l的法线矢量为W0，则分类线的表达式为：

gXW0Xb00 (4-2)

式中表示矢量点积。显然， gX到原点距离为Nb0。 W0对于给定的所有N个学习样本Xn, ynn1，gX应满足：

2

gXn0, yn1 XnC1 (4-3a)

gXn0, yn1 XnC2或写成

ynsgngXn1XnC1 (4-3b)

ynsgngXn1XnC2如图所示，直线l1和直线l2与分类线l之间的间隔距离为k，则这两条边界线的表达式分别为：

l1:W0Xb0k

l2:W0Xb0k直线l1和直线l2之间的间距为2k，寻找最大带宽的问题，转化为在保证所有学习样本满足(4-3)式的前提下，寻找gX使k达到最大的问题了。

k是一个标量，因此，可以取WW0b；b0。于是，分类线l的表达式可

kk以改写成：

l:gXWXb0 (4-4)

直线l1和直线l2的表达式可以改写成：

l1:WXb1 (4-5)

l2:WXb1当k增大时，WW0变小。于是，寻找最大带宽k的问题，变成了寻找最小k2W的问题，为了计算上的方便，取目标函数为1W。

2对于任意学习样本Xnyn，其分布必然在直线l1之上或直线l2之下。即有

gXnWXnb1;yn1, XnC1 (4-6) gXWXb1;y1, XCnnn2n将以上两式合并，有

ynWXnb1 (4-7)

在选择分类线的过程中，(4-7)式对于任何学习样本都必须成立。在此前提下

3

寻找最宽边界的问题，最后可以表示成一个约束优化问题：

min1W2W,b2 (4-8) s..tynWXnb1, n1, 2, , N这里目标函数中的

1没有其他意义，只是为了下一步导出求解方法时方便。由此2得到两类分类机算法：

(1). 给定学习样本集Xn, ynn1，XnRM、yn1, -1。yn1表示Xn属

N于C1类，yn1表示Xn属于C2类；

(2). 构造并求解关于变量W和b的优化问题（目标函数加上平方）

min1W21WTWW,b22 s..tynWXnb1, n1, 2, , N求得最优解W*和b*； (3). 构造分类函数

gXW*Xb* (4-9)

对于任意的未知模式X，可以由上式判断其所属类别：

gX0 则 XC1 (4-10)

gX0 则 XC2从以上分析过程可知，对于任意学习样本Xn，有

gXn1 则 XnC1

gXn1 则 XnC2学习样本是实际模式的抽样或特例，工作中的实际模式可能超过学习样本的分布范围。如果能够预测到实际模式的分布，并且根据其分布确定分类函数，我们称之为“预测最优”。但实际上是很难做到的，无论我们得到多大规模的样本都总是实际问题的抽样或特例，以这些数据所做的任何估计都只是以局部推测全局。以上得到的“支持向量机”取两类样本之间最大边带的中心为分类函数，显然是对现有学习样本的最佳分类。尽管这样的分类函数未必是“预测最优”，但这种方法比器硬“限幅函数单个神经元”只能得到一个可行的分类函数来说，有更强的合理性。我们称支持向量机获得的分类函数具有“结构最优”性。

4

从结构上还可以看出，最宽边界只取决于个别样本，大量位于直线l1和直线称恰好位于直线l1和直线l2上的样本为“支l2外边的样本对最宽边界并没有影响。

持向量”。这正是这种算法称为“支持向量机”的原因。 附：用Matlab语言中的优化函数constr求解混合约束问题

语句结构如下：X=constr(‘fun’,x,options)，其中：

fun 是目标函数和约束条件的表达式，可以用Matlab的函数语句或M文件来定义；

x 是一个数组，其中元素为优化参数；

options 是控制参数。

以下举例说明其用法。优化问题：

2min.ex14x122x24x1x22x21x1x20

s..t1.5x1x2x1x20x1x2100(1). 建立.m文件：OPTex01.m

用数组x表示优化参数：x(1)对应于x1、x(2)对应于x2。

function [f,g]= OPTex01 (x)

f=exp(x(1))(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1; g(1)=x(1)+x(2);

g(2)=1.5+x(1)*x(2)-x(1)-x(2); g(3)=-x(1)*x(2)-10;

(2). 在窗口或文件中调用优化函数

x=[-1,1];

%给优化参数赋初值；

%参数赋值1，说明第一个约束为等式；

options(13)=1;

x=constr(‘OPTex01’,x，options);

运行结果：x=-1.2247 1.2247

在求解SVM问题时约束条件表达式与样本数量相同，显然，逐个写出表达式不太现实。但表达式的形式均相同，因此，可以写成矩阵运算的形式。

5

§4-2. 求解线性分类问题的优化方法

求解(4-8)式是一个典型的优化问题，而且，(4-8)式中只涉及到变量W的二次关系W，因此，是一个二次规划问题。二次规划问题有唯一的最优解，不存在局部最优，这是本算法的突出优点。后面还可以看到，借助Lagrange方法求解(4-8)式优化问题时，只涉及到Xn之间的点积运算，这将这种方法推广到非线性可分问题提供了极大的方便。为此，首先介绍最优化问题的基本概念。

一、 优化问题的几个基本定义和定理

定义（无约束问题的全局极小点或整体解）：称X*RM是目标函数fX的全局最优解，如果对于任意的XRM有fXfX*。如果对于任意XX*有

fXfX*，则X*称为严格全局最优点。

给定函数fX求解全局最优的问题，称为“无约束优化问题”。记作

minfX，XRM。

定义（约束问题的全局极小点或整体解）：设

DX ciX0, i1, 2, , p; ciX0, ip1, p2, , pq; XRM

是目标函数fX的可行域，称X*D是目标函数fX在D上的最优解，如果对于任意的XD都有fXfX*。如果对于任意XX*，X, X*D有

fXfX*，则X*称为fX在D上的严格最优点。

给定函数fX和约束条件

ciX0，i1, 2, , p

ciX0，ip1, p2, , pq

在可行域上求解目标函数fX最优解的问题称为“约束优化问题”。记作

6

mins.t.fX, Xx1, x2, , xMRMTciX0,i1, 2, , pciX0,ip1, p2, , pq

定义（凸集）：称集合SRM为凸集，如果对于任意X1, X2S和任意的

0, 1，都有X11X2S。

定义（凸组合）：设X1, X2, , XNRM，如果存在非负的1, 2, , N满足n1，则称XnXn是X1, X2, , XN的一个凸组合。

n1n1NN定义（凸函数）：设SRM为非空凸集，称f为定义在S上的凸函数，如果对任意X1, X2S和0, 1都有

fX11X2fX11fX2

如果X1 X2时上式中严格不等号成立，则f称为严格凸函数。

定理（凸函数的充要条件）：设SRM为非空凸集，称f为定义在S上的凸函数，如果对任意X, XXS都有

fXXfXfXX

其中fX是函数f在X点的梯度。（证明从略）。

图4-2.凸函数 二、 最优性条件

定理（凸无约束问题解的充要条件）：设fX是RM上的连续可微凸函数，则X*RM是无约束问题全局最优的充分必要条件是fX*0。

7

下面研究凸约束问题解的必要条件。

1. 等式约束问题的必要条件

先考虑二维且只有一个等式约束的优化问题

mins.t.fXfx1, x2cXcx1, x20

显然，该问题的可行域是由cX0确定的一条曲线，fX在XcX0, XR2取值就是

fXfx1, x2和曲面cx1, x20的交线，如图

cX04-3所示的即空间曲线l:。该约束

fXfx1, x2 图4-3 等式约束问题示意 问题的解X*是交线上的最小点，而X*未必是无约束问题min:fX的最优点，因此，fX*0不一定成立。

考虑fX上的等高线fXk，当k比较大时等高线与l有交点；当k低于

hfX*时就没有了交点。显然，在X*点等高线fXh和l有唯一的交点，即，在x1, x2平面上等高线fXh与曲面cX0相切，于是法线共线。而等高线fXh在切点X*处的法线就是fX在X*点的梯度矢量

fXcXxx1，的法线为。因此，cX0fX*1cX*fXxxcX2XX*2XX*必有常数*使得

fX**cX*0

X*除了满足上述条件外，作为约束问题必然还有cX*0，由此得到约束问题

解的条件为

fX**cX0 cX0

8

引入Lagrange乘子，构造Lagrange函数

LX, fXcX

可以看到，在X*约束问题解的条件可以表达为

XLX, XX*fX**cX*0**LX, XX*cX*0 (4-11)

用矢量函数CXc1Xc2XcpX0表示多个等式约束，令Lagrange

T乘子矢量Α12p，则多个等式约束情况下Lagrange函数为

LX, ΑfXiciXfXCX*Α

i1pTT解的必要条件可以表达为

XLX, ΑXX*fX*CX*Α*0ΑΑ*ΑΑ*TΑLX, ΑXX*CX*0 (4-12)

其中CXc1Xc2XcpX0。显然，最优点满足(4-12) 但满

T足(4-12)不一定是最优点。

2. 不等式约束问题的必要条件

先考虑二维且只有一个不等式约束的优化问题

mins.t.fXfx1, x2cXcx1, x20

如图4-3所示，可以分两种情况考虑：

 最优点X*落在可行域的边界上。该问题解的存在条件与等式约束问题

相同，由(4-11)式给出。还可以证明，在切点X*处fX*指向可行域D的外侧而cX*指向内侧，二者共线但方向相反，所以必有*0使得fX**cX*0。此条件等价于

9

XLX, XX*fX**cX*0**LX, XX*cX*0 (4-13)

*0上式同样适用于等式约束情况。

 最优点X*落在可行域以内。约束条件不起作用，X*就是无约束问题

min:fX的最优解，即有fX*0；同时，由于X*位于约束曲线cX0的内侧，因此，必有cX*0。此条件等价于

XLX, XX*fX**cX*fX*0**LX, XX*cX*0 (4-14)

*0综合(4-13)和(4-14)式，不等式约束问题的必要条件

XLX, XX*fX**cX*0**LX, XX*cX*0 (4-15)

*cX*0把上述结论推广到多个不等式约束的情况

XLX, ΑXX*fX*CX*Α*0ΑΑ*ΑΑ*T*0ΑLX, ΑXX*CX*0Α*0CX*Α*0 (4-16)

3. 一般约束问题的必要条件

一般问题包括等式约束和不等式约束，比较(4-12)、(4-13)和(4-16)式可以看到：

 (4-16)式条件中的第一项是等式、不等式约束两种情况所共同拥有

的；

 对于等式约束和最优点处在可行域边沿上的情况，第二项取“=”、

第三项取“>”；

10

 对于最优点位于约束曲线内侧的情况，第二项取“<”号、第三项取

“=”；

 第四项为所有情况所共有。 于是，可以归纳出“一般约束问题”

minfXXx1x2xMRMs.t.ciX0i1, 2, , p

ciX0ip1, p2, , pqT的必要性条件”：

XLX, ΑXX*fX*CX*Α*0ciX*0， i1, 2, , pciX*0， ip1, p2, , pq (4-17)

i*0 i1, 2, , pciX*i*0 i1, 2, , pΑΑ*T此条件也称为“KKT条件（Karush-Kuhn-Tucher 条件）”。实际上，对于凸一般约束问题，(4-17)式条件就是充分必要条件。

三、 对偶理论

1. 原始问题与对偶问题

为了得到求解优化问题的实用方法，需要借助对偶理论简化问题。用以下例子引出对偶理论的概念：

设有两个人P和D进行博奕，博奕的规则是：

 P的可行策略集为X，D的可行策略集为Y。即P和D所能采用的招数

集合分别为X和Y；

 每次对决，两个人各从自己的策略集中选择一个策略。例如，P采用招

数xX，D采用招数yY，然后对决；

 两人同时公开策略，依照策略不同而确定输赢并决定赔付。假设对决中

D获胜，则由P向D赔付Fx, y0，Fx, y是策略x, y的函数。反过来，若P获胜，则赔付Fx, y0。

11

假设参与者P和D都不是盲目冒险，而是理性地追求最大利益，两人都选择最小风险的决策。首先，参与人P选择的任意一个策略xX，在Y中存在一个yY使他的赔付Fx, y最大。将他选择x时给D的最大可能赔付记作

F*xmaxFx, y (4-18)

yY参与者P应该尽可能F*x实际上就是参与者P选择策略x后的最大风险。的减小F*x，即，P渴望得到以下问题的解

minF*xminmaxFx, y (4-19)

xXxXyY这个问题称为“极小-极大”问题，即最大赔付中的最小。

另一方面，参与人D希望得到对方最大的赔付。他选择的任意一个策略

yY，最差情况下，在X中存在一个xX使他得到的赔付Fx, y最小。将他

选择y时能够得到的最小可能赔付记作

FyminFx, y (4-20)

xXFy实际上就是参与者D选择策略y后的最大风险。参与者D应该尽可能争取最大的Fy，即，D渴望得到以下问题的解

maxFymaxminFx, y (4-21)

yYyYxX该问题称为“极大-极小问题” ，即最小赔付中的最大。

定义（原始问题和对偶问题）：称极小-极大问题(4-19)为原始问题，Fx为原始函数；称极大-极小问题(4-21)为对偶问题，Fy为对偶函数。

2. 弱对偶定理

凭直观可以得到：对于任意的xX和yY，有

FyminFx, yFx, ymaxFx, yFx (4-22)

xXyY由此可以得到定理：

12

定理（弱对偶）：Fx和Fy分别为原始函数和对偶函数，对任意的xX和yY，有FyFx。若原始问题和对偶问题都有最优解，则

maxminFx, ymaxFyminFxminmaxFx, y (4-23)

yYxXyYxXxXyY即，原始问题的最优值以对偶问题的最优值为下界。

例1：两人零和（必决胜负）博奕。P和D的可选策略集分别为X1, 2和

Y1, 2，当他们分别选择iX和jY时，P向 D的赔付为Fi, jaij。P和

12。 D所有可能选择的赔付组成一个矩阵A432对于P而言，任选i1, 2，可能的最大赔付为FimaxFi, j，

j1,24于是，极小-极大问题的最优解为

2minFiminmaxFi, jmin2 i1,2i1,2j1,2i1,24此人的最优选择是i1，这样他的最大赔付是2。若对方失误则还有可能赔付-1。

对于D而言，任选j1, 2，可能的最小获赔为FiminFi, j12，

i1,2于是，极大-极小问题的最优解为

maxFjmaxminFi, jmax122

j1,2j1,2i1,2j1,2即定理中的等号。此人的最优选择是j2，这样他至少获赔是2，如果对方失误则还有可能获赔4。maxFj0显然博奕对D有利。这种情况下“最多赔付”

j1,2与“至少获赔”相等，但是，从矩阵A可以看到这是不公平的对决。

12，极小-极大问题的解没有变，极大-极小问题的解为 改变矩阵A41maxFjmaxminFi, jmax111

j1,2j1,2i1,2j1,2于是，maxFjmaxminFi, j12minmaxFi, jminFi。“最多赔

j1,2j1,2i1,2i1,2j1,2i1,2付”大于“至少获赔”，符合定理中的不等号。maxFj0显然博奕对D有利。

j1,2 13

12以上例子给出了弱对偶定理的两种可能。再假设A这意味着两21，

方的利益和风险相同。根据公式可以得到

22 对于P而言，其最大赔付风险为：minFiminmaxFi, jmini1,2i1,2j1,2i1,22maxFjmaxminFi, jmax111 对于D而言，其最小获赔风险为：

j1,2j1,2i1,2j1,2符合定理中的不等号。

3. 强对偶定理

前面通过例子已经看到原始问题的解minFxminmaxFx, y总是大于

xXxXyY等于对偶问题的解maxFymaxminFx, y。考察例子中的矩阵A，元素

yYyYxXa122是第一行中的最大，同时又是第二列的最小，存在这样的点称该博奕有鞍点。后面可以看到，原始问题和对偶问题的最优是否相等和博奕有没有鞍点密切相关。

定义（鞍点条件）：设给定定义在X, Y上的实值赔付函数Fx,y和一个点

x,y，xX，yY。若对任意的xX，yY，有

Fx,yFx,yFx,y

则称x,y为鞍点。（鞍点即“行中最大、列中最小”）

定理（强对偶性）：原始问题和对偶问题有相同最优值

minFxminmaxFx, ymaxminFx, ymaxFy

xXxXyYyYxXyY的充分必要条件是存在鞍点。

四、 Lagrange对偶理论 1. 原始问题与对偶问题

以只含不等式约束的约束问题为例

14

mins.t.fXciX0, i1, 2, , p (4-24)

在前面的分析中我们还知道，给定Lagrange乘子Α12p则其Lagrange函数

TLX, AfXATCX

满足以下条件：

 若最优点X位于可行域边界上，则fX与CX共线且反向。fX作为凸函数其fX0，所以，必然CX0，在

LX, AXXfXA*TAACX0

T中，Lagrange乘子Α12p一定满足i0；

 若最优点X位于可行域之内，则约束条件没有作用约束问题与相应的无

约束问题同解，即，应有

LX, ΑXXfX0

AA因此，必有i0，i1, 2, , p。

现在，将Lagrange函数LX, A看作定义在XRM，ARp上的赔付函数，与前面讲的内容对应：XRMxX，ARpyY。于是，由此定义的原始函数

TLXmaxLX, AmaxfXACX (4-25) ppARAR考虑到有ciX0，i0，上式中第二项iciX0，所以给定任意X对括号取最大值结果必然是第二项为0，即

LXfX (4-26)

以上结果中已经包含了条件ciX0，i0，所以，此时的极小-极大问题

XRX minLM就是(4-24)式所示的约束优化问题，优化被表示为一个“极小-极大”问题：

15

XRTminLXminmaxLX, AminmaxfXACX (4-27) MMMppXRARXRAR将约束优化问题表示成最小-最大问题的目的，是利用对偶问题将原有的优化问题转化成更容易求解的形式。(4-27)式作为原始问题，其对偶问题为

TmaxLAmaxminLX,AmaxminfXACX (4-28) MMpppARARXRARXR这里的对偶函数为

LAminLX,AminfXATCX， ARp (4-29) MMXRXR利用对偶问题表达的优化问题，将原来的问题变成了容易求解的无约束问题。对于(4-28)式，首先求解关于变量X的极小值问题

XRTminfXACX M得到XA后，代回(4-29)式得到只包含变量A的对偶函数LA，然后求解关于变量A的极大值问题

maxLA pAR得到Lagrange乘子A，然后，可以利用KKT条件中的其它关系式，求得X。

例2：考虑单变量优化问题

minfxx2

s.t.1x0目标函数为抛物面fxx2，约束条件为x1，凭直观就可以判断解为x1。该问题的Lagrange函数为

Lx,x21x

由KKT条件可知0。相应的对偶函数为

LminLx,minx21x

x,x,解等式右边的无约束问题

d2x1x2x0，x dx2于是对偶函数为

L24

16

这是一个开口向下且极大值2的抛物线。用对偶问题表达的优化问题

2maxLmax 0,0,4显然，在0,上的解为2。再利用前面的关系可以得到x1，此结果显然就是原来优化问题的解。20也印证了最优点位于约束边界上。

2. 二次规划问题的对偶性 在上面我们实际上用到一个事实：被表达的优化问题是一个强对偶问题，即

minLXminXXAi0,,i1,2,,pmaxLX, AAi0,,i1,2,,pmaxminLX, AmaxLX

XX如果要用以上方法解决支持向量机问题，必须首先保证(4-8)式是一个强对偶问题。

定理（强对偶性）：考虑连续可微的凸优化问题

minfX (4-30)

s.t.ciX0, i1, 2, , p其中fX和所有ciX都是连续可微的凸函数，并且约束条件满足（约束规格）

(1). ciX均为线性函数；

(2). 梯度集c1X, c2X, , cpX中各个分量线性无关。

T则：

(1). 若原始问题(4-30)有解，则其对偶问题(4-28式)

TmaxLAmaxminLX,AmaxminfXACX，也有解； MMpppARARXRARXR(2). 若原始问题(4-30)和对偶问题(4-28)分别有解X和A，则这两个解分别

为原始问题和对偶问题最优解的充分必要条件是相应的原始问题和对偶问题的目标函数值相等。

利用对偶理论，我们首先可以将(4-30)式优化问题表示成(4-25)和(4-27)式所表示的极小-极大（原始）问题。如果满足强对偶条件，利用对偶理论又可以转

17

化为极大-极小（对偶）问题，对偶问题更加容易求解。

从前面的例子已经看到利用对偶函数求解优化问题的过程是 (1). 求对偶函数

TLAminLX,AminfXACX (4-31) MMXRXR方法是令

XfXATCX0

解出

XA (4-32)

代回对偶函数得到

TLAminLX,ALX,AfXACX MXR(2). 取对偶函数极大值

maxLAmaxLX,AmaxfXATCX pppARARAR方法是令

AfXATCX0

解出A，代回(4-32)式得到优化解XA。

3. Wolfe对偶问题

可以将上面求解过程的两个步骤归纳为一个新的优化问题

maxLX, A (4-33) s.t.XLX, A0i0, i1, 2, , p其中，约束条件XLX, A0实际上就是上面步骤中的第一步，而目标函数就是上面步骤中的第二步。其实，(a). 将XLX, A0求解，然后，(b). 代回

LA就解得了Lagrange乘子。 LX, A就得到了LA，再，(c). 取maxpAR 18

(4-33)式看起来似乎只是将通过对偶理论表达的优化问题及其求解方法，归纳成了另一个数学表达形式。但(4-33)式更加接近原始问题，利用(4-33)式我们无须再涉及关于原始函数LX, A或对偶函数LX, A的运算，而可以直接从Lagrange函数LX, A出发，求解优化问题。

(4-33)式优化问题称为(4-30)式优化问题的“Wolfe对偶（Wolfe Dual）”。

五、 两类线性可分支持向量机的求解 1. 线性支持向量机问题的对偶问题及其求解 现在回到两类线性可分的分类机问题上。(4-8)式所示两类线性可分的支持向量机问题是一个二次规划问题（目标函数上多了一个平方），二次规划问题是典型的凸优化问题，满足强对偶性条件。重写如下：

min1W2W,b2 (4-34) s..t1ynWXnb0, n1, 2, , NN上式中，优化变量为WRM和bR，而Xn,bnn1是学习样本，其中

XnRM是特征矢量、bn1,1是Xn归属的类别值。约束条件的意思就是要保证每个学习样本都能够被正确分类。总共有N个学习样本，相应地就有N个约束表达式。用A12N，n0,1表示Lagrange乘子，则上式

T的Lagrange函数为

2LW,b,A1WnynWXnb12n121WnynWXnbn2n1n121WnynWXnbnynn2n1n1n1NNNNNN (4-35)

其中W和b合起来相当于原始问题Lx, y中的变量x，而Lagrange乘子

A12N则相当于y。

T利用前面已经举例并且归纳的方法求解“极小-极大”问题

19

n0,,n1,,Nmax minLW,b,A MWR,bR就可以得到两类线性可分支持向量机问题。步骤如下：

(a). 求对偶函数LW,b,AWRM,bRminLW,b,A

WLW,b,A0令得到：

LW,b,A0bNWnynXn0n1 (4-36) Nynn0n1代入(4-35)式得到

LW,b,A1WWnynWXnb12n112Nn1NnynXnkykXknynWXnbnk1n1n1NNNNNNN1nkynykXnXknyn2n1k1n1NkykXkXnbnk1n1 (4-37)

NNNNN1nkynykXnXknynkykXkXnbn2n1k1n1k1n1NNNNNN1nkynykXnXknkynykXkXnbnynn2n1k1n1k1n1n11nkynykXnXkn2n1k1n1上式中并没有出现b，但我们可以先解出n。

(b). 由令：

nLW,b,AynkykXnXk10n1, 2, , Nk1NNNNn0,,n1,,maxLW,b,A，求解Lagrange乘子n

(4-38)

由这组线性方程中可以解出所有的Lagrange乘子1, 2, , N，再利用(4-36)式的第一式可以得到

WnynXn (4-39)

n1N 20

于是得到了分类函数gXWXb的法向矢量W。

其实，从线性约束凸优化问题的几何意义可知，只有与n0相对应的那些约束条件才是有效的。对应于支持向量机问题，这些n所对应的学习样本

Xn, yn是支持向量，它们恰好位于分类边带线

l1: WXb1 (4-40) l: WXb12上。其余与k0对应的约束条件中的样本点，都位于上边带l1之上或下边带l2之下，这些点的存在并不影响分类函数的位置。根据已经得到的W和支持向量求出b并构造分类函数gXWXb的工作已不在困难。

假设所得到的Lagrange乘子中k0，表明学习样本Xk是支持向量，它必然满足约束条件

1ykWXkb0

同时考虑到yk1，所以有

bykWXkyknynXnXk (4-41)

n1N于是，得到分类函数

gXnynXn,XnynXn,Xkyk (4-42)

n1n1NN2. 线性支持向量机的Wolfe对偶 以下我们继续研究通过Wolfe对偶求解(4-34)式支持向量机问题的方法，其结果将为解决非线性分类方法找到非常有效的方法。

根据(4-33)式对Wolfe对偶的定义，可以得到(4-34)式问题的Wolfe对偶

21

maxLW, b, As..twLW, b, A0 (4-43)

bLW, b, A0n0, n1, 2, , N式中约束条件中前两式的解如(4-36)所示。由其中第一式得到

WnynXn，将此结果代入(4-43)式的目标函数LW,b,A，并利用(4-36)式

n1N的第二式，得到(4-37)式。(4-37)式中消除了变量W并包含了(4-43)的第一个约束条件，即

LALW,b,A (4-44) 1nkynykXnXkn2n1k1n1NNN因此，若用(4-44)式作为Wolfe对偶的目标函数，则可取掉第一个约束不等式。

由于问题的特殊性，我们只从约束条件wLW,b,A0中解出W并代回了目标函数，由第二个约束条件bLW,b,A0只得到ynn0，没有得到关

n1N于b的表达式并代回目标函数。因此，即使换用(4-44)式作为Wolfe对偶的目标函数，原式中的第二个约束条件只好继续保留。鉴于ynn0从形式上更加简

n1N单，因此，用将该结论替代(4-43)式中原来的约束条件bLW,b,A0。

于是，可以将(4-43)式的Wolfe对偶改写成

p1ppmaxyiyjijXiXjii2i1j1i1s.t.yii1pi0 (4-45)

i0, i1, 2, , p该式不仅更加简洁，尤其是为实现非线性分类奠定了基础。(4-45)式同样也是求解两类线性可分支持向量机的实用算法。

许多软件，例如MatLab软件中都有求解(4-45)式子优化问题的函数可供调用，当然，也可以直接对(4-34)式直接求解。我们前面关于优化问题的所有工作，都是为了得到(4-45)式的结果，为解决非线性分类问题寻找途径。

22

§4-3. 非线性支持向量机——核方法（Kernel Method）

1. 特征空间的非线性影射和核函数

前面已经提到，(4-45)式得到的关于线性支持向量机的Wolfe对偶不仅是为求解该问题提供了一个简洁的优化问题形式，更是为解决非线性两类分类问题开辟了一条新路。

考虑图4-4所示的两个二维空间Xx1, x2R2和Zz1, z2R2，两者之

z1x1间存在影射关系ZXx1, x2，或者表示为。影射使平面

3z2x23发生了连续变形。从图中可以看到点的位置发生了移动，尤其是X平面中的三次

3曲线x2x13，即x1, x1，被影射成为Z平面中的直线z2z1，或表示为x1, x1。

考虑以下从Xx1, x2R2到Yy1, y2, y3R3影射

y1x1xbx1c3X: y22

a2yx2ax1c3b利用这个影射我们可以将X平面中任意给定的二次曲线x2x12x1影射为R3上的空间直线，显然，只需要取a、b、c即可。3同样可以将X平面中给定的直线x2kx1d影射为R3上的空间直线，显然，只需要

图4-4 (a). 原始空间XR 图4 -4 影射示意 (b). 影射ZXR 2 2 23

取a0、bk、cd即可。因此，适当选择系数abc，3可以将X平面中的二次曲线、直线影射为YR3上的空间直线。

通过以上例子很容易想到，如果我们定义XR2到YRN1影射

y1x11Nk1knnx2anx1anx1nk1n0yk (4-46) N1X: akNx2anx1na0n2yN1a1则可以将XR上小于等于N阶的多项式曲线x2anx1n影射为YRN1上的

2Nn0直线。于是，如果影射阶数N，则任意XR2上的多项式曲线都将被影射为直线。

当然，在上面的分析中回避了影射和存在域的问题。这里只是想引申出一个设想：对于非线性可分的两类点集，寻找一个影射将问题影射到新空间ZRS使之成为线性可分问题，然后在新空间上运用前面得到的方法寻找分类函数。

从前面关于影射的分析中可以看到，如果(4-46)式影射的阶数趋于无穷大，则任何多项式曲线边界的两类问题都可以被影射为线性可分的问题。实际上，这个问题和曲线拟合问题是一样的，只要所采用的模型有足够高的阶数，那么，给定的样本总可以被拟合出来。问题是如何选取影射？注意到，上一节得到的(4-45)式，线性可分支持向量机的Wolfe对偶目标函数中只包含学习样本的点积运算XiXj，假设已经找到合适的影射，则非线性可分两类问题的支持向量机的Wolfe对偶为

24

p1ppmaxyiyjijXiXjii2i1j1i1s.t.yii1pi0 (4-47)

i0, i1, 2, , p其实我们并不一定非要知道的表达式，如果能够直接计算XiXj则完全没有必要写出；另一方面，我们对的要求就是它有足够高的阶数，具有足够强的拟合能力。可以想象，对于一个具体的分类问题，这样的并不唯一。

直接寻找不容易，但可以证明，找到一个函数

KXi,XjXiXj (4-48)

使之所隐含的能够满足上述要求却并非困难的事情。例如，径向基函数

KXi,XjeXiXj22

如果将它分解成两个函数的点积，其形式等价的阶数将非常高。

于是，我们不用寻找，转而直接寻找KXi,Xj，非线性可分两类分类问题支持向量机的Wolfe对偶成为

p1ppmaxyiyjijKXi,Xjii2i1j1i1s.t.yii1pi0 (4-49)

i0, i1, 2, , p(4-48)式定义的函数KXi,Xj成为“核函数（Kernel Function）”。利用核函数，两类非线性可分问题转化成了线性问题。相应的分类函数为

gXnynKXn,XnynKXn,Xkyk (4-50)

n1n1NN可见，正因为在支持向量机的Wolfe对偶表达形式中，只出现了学习样本的点积运算，才使得我们有可能运用核函数的方法解决非线性分类问题。这正是支持向量机引起人们广泛关注的意义所在。

25

基于核函数求解机器学习问题的方法又被称为“核方法”，是最近一些年人工智能发展的一个亮点。

2. 核函数存在的条件和常用核函数

我们希望KXi,Xj隐含着的影射具有足够强的非线性拟合能力，或者说，是一个自由度极高的函数。那么什么样的函数隐含影射呢？这是一个复杂的泛函问题，超出了本课程的内容范围，这里不做过多的讨论。我们只从形式上给出KXi,Xj成立的Mercer条件。 1. Mercer条件：

影射以及和表达式

KXYXiYi

i存在的条件是，当且仅当对于任意的gx

gxdx

2有

KXYgXgYdXdY0。

2. 常用核函数：

多项式：KXYXY1

p径向基：KXYeXY2

双曲正弦：KXYtanhXY

26

§4-4. 算法归纳

相关算法：线性(4-8，4-34)、(4-33)、Wolf对偶表示(4-43)、非线性(4-49) 一、两类线性可分的SVM算法

X1X2XNM给定学习样本：，其中，XiR是已知类别M维特征矢

y1y2yN量，yi这里介绍两类可分情况下的SVM算法的MatLab11是Xi的类别值。语言编程实现方法。

需要注意的是调用MatLab优化函数constr时，该函数要求优化参数的变量名必须是“x”，因此，不得不在程序中用x表示Lagrange乘子。

图4-5 用MatLab语言实现SVM分类算法的流程

(1). 求解优化问题(4-45)

p1ppmaxyiyjijXiXjii2i1j1i1s.t.yii1pi0

i0, i1, 2, , p

27

其中XiXj是矢量内积。

求解该优化问题的MatLab程序如下： a. 建立.m文件

function [f, g]=exfun(x,M,N)

fid=fopen(‘Tmp.dat’, r); X=fread(fid, M*N, ’float’); X=reshape(X,M,N); Y=fread(fid,’char’); fclose all f=0;

% 将样本数据还原成M×N矩阵

% M为样本维数，N为样本个数

for i=1:N

for j=1:N end end

f=f-sum(x);

f=f+y(i)*y(j)*x(i)*x(j)*X(i)’*X(j);

g(1)=y’*x; g(2:N+1)=-x;

b. 主程序

{输入学习样本： X：N个M维矢量，即M×N矩阵；

y：N维数组，每个元素与X中的一个矢量对应}

%存储学习样本 fid=fopen(‘Tmp.dat’,’w’); fwrite(fid,X,y,’float’); fclose all opts(13)=1; x=rand(N,1);

% 第一个约束表达式为等式约束； % 优化变量赋初值

A=constr(‘exfun’,x,opts); % A为得到的Lagrange乘自数组

28

{用(4-45)式构造判别函数}

二、非线性可分SVM的MatLab语言实现

与线性可分两类分类问题的区别仅在于，将其中的点积运算：

XiXjxi1xj1xi2xj2xiMxjMximxjm

m1M换成核函数运算（以Gaussian径向基函数为例）：

KXiXjeXiXj222xi1xj12xi2xj22xiMxjM222ximxjmm1M2ee22

.m文件

function [f, g]=exfun(x,M,N)

fid=fopen(‘Tmp.dat’, r); X=fread(fid, M*N, ’float’); X=reshape(X,M,N); Y=fread(fid,’char’); fclose all f=0;

% 将样本数据还原成M×N矩阵

% M为样本维数，N为样本个数

for i=1:N

for j=1:N end end

f=f-sum(x);

f=f+y(i)*y(j)*x(i)*x(j)*exp(-norm(X(i)-X(j))^2/(2*s^2));

g(1)=y’*x; g(2:N+1)=-x;

29