从感知机(Perceptron)到支持向量机(SVM)

爱音乐的程序员小新人 06-05 412

前言：

目前小伙伴们对“感知器算法matlab代码”大约比较看重，同学们都想要剖析一些“感知器算法matlab代码”的相关文章。那么小编也在网上网罗了一些有关“感知器算法matlab代码””的相关知识，希望咱们能喜欢，小伙伴们一起来了解一下吧！

本文会介绍感知机和支持向量机的原理，着重阐述这两个算法中的一些逻辑推导思路。

1.基础知识：函数距离(functional margins)和几何距离(geometrical margins)

假设x∈R

x∈Rn，那么显然w

x+b=0

wTx+b=0是一个超平面。通过推导，空间中的任意一点x

(i)

x(i)到这个超平面的距离为

L=w

(i)

||w||

L=wTx(i)+b||w||

假设我们有样本点A(x

(i)

),y

(i)

∈{1,−1}

A(x(i),y(i)),y(i)∈{1,−1},

我们定义几何距离(geometrical margins)为

(i)

||w||

)

γ(i)=y(i)(wTx(i)+b||w||)

接着我们定义函数距离(functional margins)为

(i)

+b)

γ^(i)=y(i)(wTx(i)+b)

这两个距离有什么特征呢？

① 函数距离可以表示分类的正确性和确信度：当w

(i)

+b>0

wTx(i)+b>0时，说明样本A在超平面的上方，也就属于1类（记上图圆点为-1，叉点为1），如果此时y

(i)

y(i)=1,那么A样本分类正确，γ

(i)

γ^(i)>0；否则γ

(i)

γ^(i)<0。

② 同倍数扩大或缩小w、b，超平面是不变的，函数距离会同等增减；而几何距离不变，因为点到固定平面的距离是不变的。

③ γ

(i)

=γ

∗||w||

γ^(i)=γ^∗||w||那这些特性有什么用呢？其实它们在感知计算法中起着重要作用

2.感知机(Perceptron)

利用特性①，我们可以判断样本点是否分类正确，最终画出一个超平面能把线性可分的数据正确分类（注意是线性可分的训练数据）；利用特性②，我们可以用误分类样本点的几何距离之和来表示模型的损失函数。

1、具体地，对于误分类点来说，−y

(i)

+b)>0

−y(i)(wTx(i)+b)>0，所以所有误分类点到超平面的总距离是

−1

||w||

∑

(i)

∈M

(i)

+b)

−1||w||∑x(i)∈My(i)(wTx(i)+b)

M为误分类的集合。这里我们可以直接省略1

||w||

1||w||，就得到感知机学习的损失函数L(w,b)=−∑

(i)

∈M

(i)

+b)

L(w,b)=−∑x(i)∈My(i)(wTx(i)+b)。

为什么可以直接省略1

||w||

1||w||?

（1）.因为感知机模型是以误分类点为驱动的，最后损失函数的值必然为零，即无误分类点。所以根据特性①，既然函数距离能判断样本点的分类正确性，我们何必用几何距离呢？实际上我们并不关心lost function具体数值的变化，我们只在乎还有没有误分类点。

（2）.去掉1

||w||

1||w||，我们得到的lost function是关于w,b的连续可导线性函数，可以用梯度下降法轻松地进行优化。2、利用随机梯度下降法SGD，损失函数的梯度为

∇

L(w,b)=−∑

(i)

∈M

(i)

∇

L(w,b)=−∑

(i)

∈M

(i)

∇wL(w,b)=−∑x(i)∈My(i)x(i)∇bL(w,b)=−∑x(i)∈My(i)

随机选取一误分类点，对w,b进行更新：w←w+ηy

(i)

b←b+ηy

(i)

w←w+ηy(i)x(i)b←b+ηy(i)

3、算法：

给定数据集T，学习率η

（1）选取初值w

w0,b0

（2）根据函数距离选取误分类点

（3）更新w,b

w,b

（4）转至（2），直至没有误分类点

4、可证明对于线性可分数据集，感知机算法是收敛的，具体见《统计学习方法》。

3.支持向量机(SVM)3.1.从感知机(Perceptron)到支持向量机(SVM)

感知机学习算法会因采用的初值不同而得到不同的超平面。而SVM试图寻找一个最佳的超平面来划分数据，怎么算最佳呢？我们自然会想到用最中间的超平面就是最好的。如下图

显然在SVM中我们不能在使用函数距离γ

(i)

γ^(i)来作为损失函数了，当我们试图使上图虚线之间的”gap”，最大自然要用几何距离。

我们定义

γ=min

i=1,...,m

(i)

γ=mini=1,...,mγ(i)

,那么一个最优间距分类器可以写成

max

γ,w,b

s.t.

(i)

||w||

)⩾γ,i=1,...,m

maxγ,w,bγs.t.y(i)(wTx(i)+b||w||)⩾γ,i=1,...,m

通过最大化γ

γ就可以找到最大的gap。

根据特性③，我们可以将上面的优化问题转化为max

γ,w,b

s.t.

||w||

(i)

+b)⩾γ

,i=1,...,m

maxγ,w,bγ^||w||s.t.y(i)(wTx(i)+b)⩾γ^,i=1,...,m

可是这个优化问题并不容易求解，我们期望目标函数是一个凸函数，这样优化起来就比较方便了。

这时注意到函数距离的特性②，我们可以直接让γ

γ^=1。Why?假设我们这个优化问题的最优解是w

opt

，b

opt

wopt，bopt，那么我们可以总是可以同倍数地调整w

opt

，b

opt

wopt，bopt使得γ

γ^=1，而此时最优超平面是不变的，所以上面的优化问题可以化成max

γ,w,b

s.t.

||w||

⟺min

γ,w,b

||w||

(i)

+b)⩾1,i=1,...,m

maxγ,w,b1||w||⟺minγ,w,b12||w||2s.t.y(i)(wTx(i)+b)⩾1,i=1,...,m

这样SVM模型就转化为了一个二次规划问题（Quadratic Programming）。此时我们可以用matlab的一些工具来处理这个优化问题了，可是一旦数据量变大，计算就会变得很缓慢。所以我们此时把这个优化问题转化为一个拉格朗日对偶问题，此时不仅能简化计算，更能引入SVM中最重要的kernel概念。啥是拉格朗日对偶问题？为什么能简化计算？什么是kernel？为什么能引入kernel？好吧，我承认问题有很多，不过让我们一一来窥探。3.2. Lagrange Duality

首先来看看wiki上对Lagrange Multipler和Lagrange Duality的说明

Lagrange Multipler：In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints.

1.对于最简单的只有等式约束的规划问题，例如：

min

s.t.

f(x,y)

g(x,y)=c

minf(x,y)s.t.g(x,y)=c

这个优化问题可以粗略地用函数等高线图来表示

我们的目标就是要找到一点相切点(x

)

(x0,y0)，使得f(x,y)

f(x,y)达到最小值，因为梯度和等高线图是垂直的，所以f(x,y)和g(x,y)

f(x,y)和g(x,y)在点(x

)

(x0,y0)上的梯度是平行的，此时，∇

x,y

f=−λ∇

x,y

∇x,yf=−λ∇x,yg，其中∇

x,y

f=(∂f

∂x

,∂f

∂y

)

∇x,yf=(∂f∂x,∂f∂y)，∇

x,y

g=(∂g

∂x

,∂g

∂y

)

∇x,yg=(∂g∂x,∂g∂y)，−λ

−λ就是两个向量的平行参数。

我们可以引入一个拉格朗日乘子λ

λ得到Lagrange Function

L(x,y,λ)=f(x,y)+λ(g(x,y)−c)

那么令∇

x,y

L=0

∇x,yL=0就是平行条件，∇

L=0

∇λL=0就是原始问题的等式约束，这样就把原问题放到一个Lagrange Function中求解。2.对于更一般的优化问题的原始问题，会有不等式约束例如：

min

s.t.

(x),x∈R

(x)⩽0,i=1,...,m

(x)=0,j=1,...,p

(1)

(2)

minf0(x),x∈Rn(1)s.t.fi(x)⩽0,i=1,...,m(2)hj(x)=0,j=1,...,p

原问题的定义域：D=(∩

i=0

domf

)∩(∩

j=1

domh

)

D=(∩i=0mdomfi)∩(∩j=1pdomhj)

可行点（feasible）：x∈D

x∈D，且满足约束条件。

可行域：所有可行点的集合F。

最优化值：p

∗

=inf{f

(x)|f

(x)⩽0,h

(x)=0}

p∗=inf{f0(x)|fi(x)⩽0,hj(x)=0}（求下确界inf和求最小值min在这里是等价的）

注意定义域和可行域的差别：定义域和约束条件无关，一般来说定义域大于可行域。步骤1：定义一个Lagrange函数为

L(x,λ,ν)=f

(x)+∑

i=1

(x)+∑

j=1

(x)

s.t.λ

⩾0

(3)

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνjhj(x)(3)s.t.λi⩾0

假设对L函数在x∈D

x∈D上逐点求下确界（参考boyd的《convex optimization》）的函数是

g(λ,ν)=inf

x∈D

L(x,λ,ν)

g(λ,ν)=infx∈DL(x,λ,ν)

这里的g(λ,ν)

g(λ,ν)就是我们常说的对偶函数（dual function），很明显它是一个关于λ，ν

λ，ν的线性函数。如果我们把原问题的约束条件(f

(x)⩽0，h

(x)=0)

(fi(x)⩽0，hj(x)=0)代入Lagrange function,那么对于原问题中可行域F中的任意可行点x

x~有

∑

i=1

)+∑

j=1

)⩽0

∑i=1mλifi(x~)+∑j=1pνjhj(x~)⩽0

这个不等式可以推导出两个结果：

① 因为L函数后两项小于等于0，所以，max

λ,ν

L(x,λ,ν)=f

(x)

maxλ,νL(x,λ,ν)=f0(x)（注：这里的f

(x)

f0(x)是关于x的函数），进而min

max

λ,ν

L(x,λ,ν)=p

∗

minxmaxλ,νL(x,λ,ν)=p∗

我们称这个式子为对偶问题中的Primal Problem② 因为L函数后两项小于等于0，所以

L(x

,λ,ν)=f

)+∑

i=1

)+∑

j=1

)⩽f

)

L(x~,λ,ν)=f0(x~)+∑i=1mλifi(x~)+∑j=1pνjhj(x~)⩽f0(x~)

（注：这里的f

)

f0(x~)是一个具体的值）

根据下确界的性质：一系列函数逐点下确界必然小于等于这一系列函数，有g(λ,ν)=inf

x∈D

L(x,λ,ν)⩽L(x

,λ,ν)⩽f

)

g(λ,ν)=infx∈DL(x,λ,ν)⩽L(x~,λ,ν)⩽f0(x~)

因为x

x~是可行域F中的任意值，所以

⟹

g(λ,ν)⩽minf

)

g(λ,ν)⩽p

∗

max

λ,ν

g(λ,ν)⩽p

∗

g(λ,ν)⩽minf0(x~)⟹g(λ,ν)⩽p∗⟹maxλ,νg(λ,ν)⩽p∗

记 dual problem 的最优值为d

∗

d∗ 的话，根据上面的推导，我们就得到了如下性质：d

∗

=max

λ,ν

min

L(x,λ,ν)⩽min

max

λ,ν

L(x,λ,ν)=p

∗

d∗=maxλ,νminxL(x,λ,ν)⩽minxmaxλ,νL(x,λ,ν)=p∗

步骤2：图形解释

如果上面公式没有理解，我们可以通过画图来理解一下拉格朗日对偶性。

我们还是把原问题的约束条件代入Lagrange function，为了简化图像，我们假设L只有一个不等式约束f

(x)

f1(x)且没有等式约束，原问题的函数图像大致如下：

解释：最上面这条是原函数f

(x)

f0(x)，最下面的虚线是约束函数f

(x)

f1(x)，中间的这10条虚线分别是λ=0.1,0.2,...,1

λ=0.1,0.2,...,1时，L函数的图像。在图中我们还可以看到，定义域D至少是[-1,1]（图像没画完整），可行点集合F为[-0.46,0.46]

那么根据上图我们可以画出右侧g(λ)

g(λ)的图像：

解释：因为g(λ,ν)

g(λ,ν)是在x∈D

x∈D上求下确界的，所以我们要考虑定义域D[-1,1]上L的最小值。g(λ)

g(λ)的图像上的那条虚线其实是原问题的最优解p

∗

(−0.46)=1.54

p∗=f0(−0.46)=1.54。

可以看到maxg(λ)

maxg(λ)是小于最优解p

∗

p∗的，约束条件f

(x)

f1(x)在这里的作用是保证g(λ)

g(λ)的下降。

步骤3：

通过数学分析和图形解释，我们都可以看到dual problem和primal problem的关系，即

∗

=max

λ,ν

min

L(x,λ,ν)⩽min

max

λ,ν

L(x,λ,ν)=p

∗

d∗=maxλ,νminxL(x,λ,ν)⩽minxmaxλ,νL(x,λ,ν)=p∗

如果我们能让这个式子取等号，那们我们就成功地在原来约束条件下把primal problem转化为了求解dual problem。通常我们把d

∗

⩽p

∗

d∗⩽p∗的情况叫做weak duality，d

∗

d∗=p∗的情况叫做strong duality， p

∗

−d

∗

p∗−d∗被称作duality gap。需要注意的是，无论 primal problem是什么形式，dual function总是凹的（因为它是关于λ,ν

λ,ν的线性函数），dual problem总是一个 convex optimization 的问题——它的极值是唯一的（如果存在的话）。

与原始问题的最优解相比，dual function多了后面

∑

i=1

(x)+∑

j=1

(x)

∑i=1mλifi(x)+∑j=1pνjhj(x)

这两项。我们只要能让这两项等于零，那么就有d

∗

d∗=p∗了！所以在已有约束条件(1)(2)(3)下，我们最想看到的取等条件就是∑

i=1

∗

)=0

(4)

(4)∑i=1mλifi(x∗)=0

这个就是对偶互补条件complementary slackness：从形式上看，当λ

λi>0时，必须有f

(x)=0

fi(x)=0；当f

(x)<0

fi(x)<0时，必须有λ

λi=0。这就是说，当对偶问题的约束条件不起作用时，原问题的约束条件必须要起作用，反之亦然，或者说，只有原问题的起作用的约束才对应着非零的对偶变量。

然后根据前面的lagrange乘子法，我们要max

λ,ν

min

L(x,λ,ν)

maxλ,νminxL(x,λ,ν)，就要

∇f

∗

)+∑

i=1

∇f

∗

)+∑

j=1

∇h

∗

)=0

(5)

(5)∇f0(x∗)+∑i=1mλi∇fi(x∗)+∑j=1pνj∇hj(x∗)=0

至此，我们得到了著名的Karush–Kuhn–Tucker (KKT) conditions：如果函数f

(x)

fi(x)是凸函数且可微，h

(x)

hj(x)是仿射函数，当满足(1)，(2)，(3)，(4)，(5)时，d

∗

d∗=p∗。

其证明比较简单，见pluskid的blog。这里的对偶问题我感觉我讲的很晦涩，pluskid的比较清楚详细，我主要引入一些优化理论中的结论。步骤4（将lagrange duality应用到svm中）：

① svm的最初优化问题：

min

γ,w,b

s.t.

||w||

(i)

+b)⩾1,i=1,...,m

minγ,w,b12||w||2s.t.y(i)(wTx(i)+b)⩾1,i=1,...,m

②lagrange function：L(w,b,α)=1

||w||

−∑

i=1

(i)

+b)−1]

L(w,b,α)=12||w||2−∑i=1mαi[y(i)(wTx(i)+b)−1]

primal problem:min

w,b

max

L(w,b,α)

minw,bmaxαL(w,b,α)

假设d

∗

d∗是最优解。

③dual problem：max

min

w,b

L(w,b,α)

maxαminw,bL(w,b,α)

假设p

∗

p∗是最优解。只要kkt条件成立，即：

∇

L(w

∗

,α

∗

)=w

∗

−∑

i=1

∗

(i)

∇

L(w

∗

,α

∗

)=−∑

i=1

∗

(i)

∗

(i)

∗

(i)

∗

)−1]=0,i=1,2,⋅⋅⋅,N

(i)

∗

(i)

∗

)−1⩾0,i=1,2,⋅⋅⋅,N

∗

⩾0,i=1,2,⋅⋅⋅,N

(6)

(7)

(8)

(9)

(10)

(6)∇wL(w∗,b∗,α∗)=w∗−∑i=1mαi∗y(i)x(i)=0(7)∇bL(w∗,b∗,α∗)=−∑i=1mαi∗y(i)=0(8)αi∗[y(i)(w∗x(i)+b∗)−1]=0,i=1,2,⋅⋅⋅,N(9)y(i)(w∗x(i)+b∗)−1⩾0,i=1,2,⋅⋅⋅,N(10)αi∗⩾0,i=1,2,⋅⋅⋅,N

就能使w

∗

w∗,b∗是原始问题的驻点，α

∗

α∗是对偶问题的驻点，且d

∗

d∗=p∗。步骤5：

最后我们来看看wiki上对拉格朗日对偶性的解释

Lagrange Duality：In mathematical optimization theory, duality means that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem (the duality principle). The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition. Thus, a solution to the dual problem provides a bound on the value of the solution to the primal problem; when the problem is convex and satisfies a constraint qualification, then the value of an optimal solution of the primal problem is given by the dual problem.

这里我加粗了一些名词和句子，这些都是拉格朗日对偶性的重要性质。

3.2. 支持向量机（SVM）基础

根据complementary slackness，当α

αi>0时，y

(i)

∗

(i)

∗

)−1=0

y(i)(w∗x(i)+b∗)−1=0，即样本i与超平面的函数距离为1，也就是最近点。

虚线上的三个点就称为支持向量（support vectors）。

回顾KKT条件：

在问题中我们已经满足了条件（9）（10），然后我们依次来看剩余的条件。

根据（6）有

∗

=∑

i=1

∗

(i)

w∗=∑i=1mαi∗y(i)x(i)

那么把w和（7）代回L中有L(w,b,α)

||w||

−∑

i=1

(i)

+b)−1]

w−∑

i=1

(i)

−∑

i=1

(i)

b+∑

i=1

w−∑

i=1

(i)

)+∑

i=1

=−1

∑

i=1

(i)

+∑

i=1

=−1

(∑

i=1

(i)

)

∑

i=1

(i)

+∑

i=1

=−1

∑

i=1

(i)

)

∑

i=1

(i)

+∑

i=1

=−1

∑

i,j=1

(i)

)

(j)

+∑

i=1

=∑

i=1

−1

∑

i,j=1

(i)

(j)

(i)

⋅x

(j)

)

L(w,b,α)=12||w||2−∑i=1mαi[y(i)(wTx(i)+b)−1]=12wTw−∑i=1mαiy(i)wTx(i)−∑i=1mαiy(i)b+∑i=1mαi=wT(12w−∑i=1mαiy(i)x(i))+∑i=1mαi=−12wT∑i=1mαiy(i)x(i)+∑i=1mαi=−12(∑i=1mαiy(i)x(i))T∑i=1mαiy(i)x(i)+∑i=1mαi=−12∑i=1mαiy(i)(x(i))T∑i=1mαiy(i)x(i)+∑i=1mαi=−12∑i,j=1mαiy(i)(x(i))Tαjy(j)x(j)+∑i=1mαi=∑i=1mαi−12∑i,j=1mαiαjy(i)y(j)(x(i)⋅x(j))

这时我们通过kkt条件消去了max

min

w,b

L(w,b,α)

maxαminw,bL(w,b,α)中的w,b

w,b。

最终将primal problem化为了求解

max

s.t.

∑

i=1

−1

∑

i,j=1

(i)

(j)

(i)

⋅x

(j)

)

⩾0,i=1,...,m

∑

i=1

(i)

=0,

maxα∑i=1mαi−12∑i,j=1mαiαjy(i)y(j)(x(i)⋅x(j))s.t.αi⩾0,i=1,...,m∑i=1mαiy(i)=0,

可以看到对偶之后的约束条件比原来的约束条件简单了很多，简化了计算，之后我们用SMO算法求解这个优化问题的时候也可以见其方便性。

当我们求出α

∗

αi∗之后，就可以得到w

∗

=∑

i=1

∗

(i)

w∗=∑i=1mαi∗y(i)x(i)

那么b的取值必然是两个离决策面最近的异类样本（支持向量）的中点，即b

∗

=−max

i:y

(i)

=−1

∗

(i)

+min

i:y

(i)

∗

(i)

b∗=−maxi:y(i)=−1w∗x(i)+mini:y(i)=1w∗x(i)2

这里b需要对任意样本满足对偶互补条件（8）。

于是得到了最终的决策面w

x+b=∑

i=1

∗

(i)

⋅x)+b

∗

wTx+b=∑i=1mαi∗y(i)(x(i)⋅x)+b∗

至此我们通过了所有KKT条件的要求，得到了最终决策面。其实对偶互补条件会在我们使用SMO算法计算的时候来也要作为一个更新约束的（后文的更新b规则），所以对偶互补条件是作为最后一道关卡的。Cool！3.3. 核技巧（kernels）：处理非线性数据

当数据是线性可分时，我们可以直接采用上面得到的线性SVM模型，可是当数据不可分时，我们要非线性SVM模型。

从Linear regression可以联想到，如果要处理线性不可分的情况，样本特征函数除了原始特征x

,...,x

x1,x2,...,xn，我们还要引入一些特殊项，比如x

等

x12,x13,x1x2等，我们的特征函数为

ϕ(x)=⎡

⎣

⎢

⎤

⎦

⎥

ϕ(x)=[x12x13x1x2]

之前我们通过对偶化把原问题写成了x的内积形式(x

(i)

⋅x)

(x(i)⋅x)，所以特征函数变化之后，我们可以直接代入(ϕ(x

(i)

)⋅ϕ(x))

(ϕ(x(i))⋅ϕ(x))，这就是我们的Kernel：K(x

(i)

,x)=ϕ(x

(i)

)

ϕ(x)

K(x(i),x)=ϕ(x(i))Tϕ(x)

通过Kernel就可以处理非线性函数了，不过这里有个问题，如果原始特征是2维，那通过特征组合加上常数项，ϕ(x)

ϕ(x)就有6维；原始特征是3维的话，ϕ(x)

ϕ(x)就有20维。这个数目是呈爆炸性增长的，而且如果遇到无穷维的情况，就根本无从计算了。

不过如果kernel是这样的话，且x原始特征有3维：K(x,z)

=(x

z+c)

=(x

+2cx

z+c

=(∑

i=1

)(∑

j=1

)+2c∑

i=1

=∑

i=1

∑

j=1

+2c∑

i=1

=∑

i,j=1

)(z

)+∑

i=1

(2c

−

√

)(2c

−

√

)+c

K(x,z)=(xTz+c)2=(xTz)2+2cxTz+c2=(∑i=1nxizi)(∑j=1nxjzj)+2c∑i=1nxizi+c2=∑i=1n∑j=1nxizixjzj+2c∑i=1nxizi+c2=∑i,j=1n(xixj)(zizj)+∑i=1n(2cxi)(2czi)+c2

惊奇的发现就这么一个平方式就把(x⋅z)

(x⋅z)算好了，而且此时的ϕ(x)

ϕ(x)就是∑

i,j=1

，∑

i=1

−

√

∑i,j=1nxixj，∑i=1n2cxi,c的组合：ϕ(x)=⎡

⎣

⎢

−

√

−

√

−

√

⎤

⎦

⎥

ϕ(x)=[x12x22x32x1x2x1x3x2x32cx12cx22cx3c]

（注意：这里只是两个特征之间的组合，如果3个特征组合的话，那K(x,z)=(x

z+c)

K(x,z)=(xTz+c)3，这样可以得到20维的ϕ

ϕ）核函数通过巧妙的计算，把高维ϕ(x)

ϕ(x)的计算转化成了低维原始空间的计算，大大降低计算复杂度，实现了线性不可分数据的分割。

常用的几个核函数：

多项式核 K(x,z)=(x

z+c)

K(x,z)=(xTz+c)d：显然刚才我们举的例子是这里多项式核的一个特例（R = c，d = 2）。这个核所对应的特征空间ϕ(x)

ϕ(x)的维度是C

n+d

Cn+dd，n是原始空间的维度。

高斯核 K(x,z)=exp(−||x−z||

2σ

)

K(x,z)=exp⁡(−||x−z||22σ2)，将高斯核泰勒展开为

exp(−||x−z||

2σ

)=∑

n=0

∞

(−1

2σ

)

(||x−z||

)

exp⁡(−||x−z||22σ2)=∑n=0∞1n!(−12σ2)n(||x−z||2)n

这个核会将原始空间映射为无穷维空间。从展开式中可见，如果σ

σ选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。

线性核 K(x,z)=(x⋅z)

K(x,z)=(x⋅z)，这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说，咱们有的时候，写代码，或写公式的时候，只要写个模板或通用表达式，然后再代入不同的核，便可以了，于此，便在形式上统一了起来，不用再分别写一个线性的，和一个非线性的)。当然不是每个函数都可以作为核函数的，关于kernel的有效性可以参考mercer定理。

3.4. svm的泛化能力：正则化处理

右图只因为一个数据（这种异常数据称作outlier）而大幅度地改变了分割平面，这是我们不想看到的；当使用kernel处理线性不可分数据时，我们没法保证处理之后就一定是线性可分的。

基于以上两点不足之处，我们把SVM模型改为

min

γ,w,b

s.t.

||w||

+C∑

i=1

(i)

+b)⩾1−ξ

,i=1,...,m

⩾0,i=1,...,m.

minγ,w,b12||w||2+C∑i=1mξis.t.y(i)(wTx(i)+b)⩾1−ξi,i=1,...,mξi⩾0,i=1,...,m.

其中ξ

ξ称为松弛变量 (slack variable) ，对应数据点允许偏离的 functional margin 的量。当然，如果我们运行ξ

ξ任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些的总和也要最小，这样就做到了相互制约。其中C

C是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中ξ

ξ是需要优化的变量（之一），而C

C是一个事先确定好的常量。优化后模型的拉格朗日函数：

L(w,b,ξ,α,β)=1

||w||

+C∑

i=1

−∑

i=1

(i)

+b)−1+ξ

]−∑

i=1

L(w,b,ξ,α,β)=12||w||2+C∑i=1mξi−∑i=1mαi[y(i)(wTx(i)+b)−1+ξi]−∑i=1mβiξi

通过∇

w,b,ξ

∇w,b,ξ=0得到对偶问题就是：

max

s.t.

∑

i=1

−1

∑

i,j=1

(i)

(j)

(i)

⋅x

(j)

)

0⩽α

⩽C,i=1,...,m

∑

i=1

(i)

=0,

maxα∑i=1mαi−12∑i,j=1mαiαjy(i)y(j)(x(i)⋅x(j))s.t.0⩽αi⩽C,i=1,...,m∑i=1mαiy(i)=0,

根据KKT的对偶互补条件

∑

i=1

(i)

+b)−1+ξ

]=∑

i=1

∑i=1mαi[y(i)(wTx(i)+b)−1+ξi]=∑i=1mβiξi=0

和∇

=C−α

−β

∇ξi=C−αi−βi=0

得α

=0⇒ξ

=0⇒y

(i)

+b)⩾1

=C⇒ξ

⩾0⇒y

(i)

+b)⩽1

0<α

<C⇒ξ

=0⇒y

(i)

+b)=1

αi=0⇒ξi=0⇒y(i)(wTx(i)+b)⩾1αi=C⇒ξi⩾0⇒y(i)(wTx(i)+b)⩽10<αi<C⇒ξi=0⇒y(i)(wTx(i)+b)=1

以上给出了不同数值的lagrange乘子α

αi所对应于的样本与决策面之间的位置关系。由于决策面∑

i=1

(i)

k(x

(i)

,x)+b=0

∑i=1mαiy(i)k(x(i),x)+b=0是由非零α

αi的样本确定的，因此我们把α

αi>0的样本称为支持向量。其中0<α

0<αi<C时，样本与决策面的函数距离为1；α

αi=C时，样本就是outliers。3.4. SMO优化算法（Sequential minimal optimization）

SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。

SMO算法的核心思想就是分治法，把大问题化成一个个小问题。

SMO的主要步骤如下：

意思是，第一步选取一对α

αi和α

αj，选取方法使用启发式方法（后面讲）。第二步，固定除α

αi和α

αj之外的其他参数，然后就变成了二元优化问题，可以直接用换元法求解。不断重复，直到优化函数收敛。

首先把原问题变成最小化形式是

min

s.t.

W(α

)=1

∑

i,j=1

(i)

(j)

(i)

⋅x

(j)

)−∑

i=1

0⩽α

⩽C,i=1,...,m

∑

i=1

(i)

=0,

minαW(αi)=12∑i,j=1mαiαjy(i)y(j)(x(i)⋅x(j))−∑i=1mαis.t.0⩽αi⩽C,i=1,...,m∑i=1mαiy(i)=0,

接下来就来野生推导smo了：(一) 确定α1α1和α2α2的范围

假设选取变量α

α1和α

α2，固定其他α

αi，根据∑

i=1

(i)

∑i=1mαiy(i)=0有

(1)

+α

(2)

=−∑

i=3

(i)

=ς

α1y(1)+α2y(2)=−∑i=3mαiy(i)=ς

ς是常数。

①当样本1，2异类，即一个为1，一个为-1，函数α

(1)

+α

(2)

=ς

α1y(1)+α2y(2)=ς的图像如下：

可以看出更新后的α

new

α2new必须在以下范围内

L⩽α

new

⩽H

L=max(0,α

old

−α

old

),H=min(C,C+α

old

−α

old

)

L⩽α2new⩽HL=max(0,α2old−α1old),H=min(C,C+α2old−α1old)

那么更新后的α

new

=α

old

(1)

(2)

(α

old

−α

new

)

α1new=α1old+y(1)y(2)(α2old−α2new)。②同理得当样本1，2同类

L=max(0,α

old

+α

old

−C),H=min(C,α

old

+α

old

)

L=max(0,α2old+α1old−C),H=min(C,α2old+α1old)

(二) 求出αnew2α2new和αnew1α1new

为了推导方便我们记

g(x)=∑

i=1

(i)

K(x

,x)+b

=g(x

)−y

=∑

j=3

(j)

K(x

)=g(x

)−∑

j=1

(j)

K(x

)−b

g(x)=∑i=1mαiy(i)K(xi,x)+bEi=g(xi)−yivi=∑j=3mαjy(j)K(xj,xi)=g(xi)−∑j=12αjy(j)K(xj,xi)−b

此时的优化函数W(α

)

W(αi)需要优化含有α

α1和α

α2两个变量的项，所有我们可以忽略其他常数项，化简得W(α

,α

)=1

(1)

(2)

(1)

(2)

−(α

+α

)

W(α1,α2)=12K11α12+12K22α22+y(1)y(2)K12α1α2+y(1)v1α1+y(2)v2α2−(α1+α2)

把α

=(ς−y

(2)

(1)

α1=(ς−y(2)α2)y(1)代入上式得只含α

α2的W(α

)

W(α2)。

W(α

)

W(α2)对α

α2的二阶导数为∂

∂α

−2K

=||ϕ(x

)−ϕ(x

)||

∂2W∂α22=K11+K22−2K12=||ϕ(x1)−ϕ(x2)||2

由上式可知一般情况W(α

)

W(α2)的二阶导数都是大于0的；而在样本1，2特征相同时，二阶导数为0；在核函数不满足mercer定理时，二阶导数可能非正定。

①第一种情况，目标函数为凸函数，通过令W(α

)

W(α2)的一阶导数等于0求得极小点，得到α

unc

=α

old

(2)

−E

)

−2K

(11)

(11)α2unc=α2old+y(2)(E1−E2)K11+K22−2K12

这里求出的α

unc

α2unc表示未约束过的α

α2，还需要满足前面的约束范围，所以最终的α

new

=⎧

⎩

⎨

⎪

unc

L⩽α

unc

⩽H

unc

new

=α

old

(1)

(2)

(α

old

−α

new

)

(12)

α2new={H,α2unc>Hα2unc,L⩽α2unc⩽HL,α2unc<L(12)α1new=α1old+y(1)y(2)(α2old−α2new)

②后两种情况分别使目标函数变为了线性函数和凹函数。这时，α

α1和α

α2在边界L或H时，目标函数取得最小值。具体地，当α

new

α2new=L时，

new

=α

old

(1)

(2)

(α

old

−L)

(1)

−α

(1)

−b)−α

−y

(1)

(2)

−α

(2)

−b)−α

−y

(1)

(2)

W(L)=L

+Lf

new

L+y

(1)

(2)

Lα

new

α1new=α1old+y(1)y(2)(α2old−L)f1=y(1)v1α1−α1=y(1)(E1−b)−α1K11−y(1)y(2)α2K12f2=y(2)v2α2−α2=y(2)(E2−b)−α2K22−y(1)y(2)α1K12W(L)=L1f1+Lf2+12K11α1new+12K22L+y(1)y(2)K12Lα1new

同理可得W(H)

W(H)，然后通过比较W(H)

W(H)和W(L)

W(L)的大小来确定α

new

α2new是取L还是H时得到最小值。(三) 更新b，E

更新了α

α之后，我们还要更新b。b的更新规则如下:

若α

new

α1new和α

new

α2new有一个在界内（这里的界是指0<α

new

0<αinew<C），b取对应b

new

binew（i=1,2）。如果两个都在界内，那么b

new

b1new=b2new。

若α

new

α1new和α

new

α2new都在界上（即α

new

=C或0

αinew=C或0）且L\neqH

L\neqH，那么b

new

b1new和b

new

b2new之间的任意数都满足KKT条件，都可作为b的更新值，一般取b

new

b1new+b2new2。

为什么是这样呢？

A. 0<α

new

0<α1new<C时，样本刚好在离决策面函数距离为1的间隔边界上，所以可以直接利用y

(1)

+b)=1

y(1)(wTx(1)+b)=1求出b

new

b1new，具体地

∑

i=1

(i)

+b=y

(1)

⟹b

new

(1)

−∑

i=3

(i)

−α

new

(1)

−α

new

(2)

⟹b

new

=−E

−y

(1)

(α

new

−α

old

)−y

(2)

(α

new

−α

old

)+b

old

(13)

(13)∑i=1mαiy(i)Ki1+b=y(1)⟹b1new=y(1)−∑i=3mαiy(i)Ki1−α1newy(1)K11−α2newy(2)K21⟹b1new=−E1−y(1)K11(α1new−α1old)−y(2)K21(α2new−α2old)+bold

同理可得b

new

=−E

−y

(1)

(α

new

−α

old

)−y

(2)

(α

new

−α

old

)+b

old

(14)

(14)b2new=−E2−y(1)K12(α1new−α1old)−y(2)K22(α2new−α2old)+bold

我们把(11)(12)代入得b

new

−b

new

b2new−b1new=0，即b

new

b2new=b1new.B.α

new

α1new和α

new

α2new都在边界上，情况较复杂。接下来我们就来证明此时b

new

b1new和b

new

b2new之间的任意数都满足KKT条件。

首先假设

new

=(1−t)b

new

+tb

new

bnew=(1−t)b1new+tb2new

由于α

new

=C或0

αinew=C或0，因此α

new

α2new是经过约束条件得来的，我们可以令α

new

=α

old

+λy

(2)

−E

)

−2K

,λ∈[0,1)

(15)

(15)α2new=α2old+λy(2)(E1−E2)K11+K22−2K12,λ∈[0,1)

要证明此时满足KKT，其实就是要证明：当α

αi=C时，

⟺

(i)

(∑

j=1

new

(j)

K(x

)+b

new

)⩽1

(i)

new

(i)

)⩽1

y(i)(∑j=1mαjnewy(j)K(xi,xj)+bnew)⩽1⟺y(i)(Einew+y(i))⩽1

；当α

αi=0时，

⟺

(i)

(∑

j=1

new

(j)

K(x

)+b

new

)⩾1

(i)

new

(i)

)⩾1

y(i)(∑j=1mαjnewy(j)K(xi,xj)+bnew)⩾1⟺y(i)(Einew+y(i))⩾1

那么更新后的E

new

E1new和E

new

E2new是多少呢？E

new

=∑

j=1

old

(j)

K(x

)+b

old

−y

(1)

+Δ(new−old)

old

+(α

new

−α

old

(2)

+(α

new

−α

old

(1)

+(1−t)(b

new

−b

old

)+t(b

new

−b

old

)

E1new=∑j=1mαjoldy(j)K(x1,xj)+bold−y(1)+Δ(new−old)=E1old+(α2new−α2old)y(2)K21+(α1new−α1old)y(1)K11+(1−t)(b1new−bold)+t(b2new−bold)

把(12)(13)(14)(15)代入上式得E

new

=t(1−λ)(E

−E

)

E1new=t(1−λ)(E1−E2)

同理得E

new

=[t(1−λ)−1](E

−E

)

E2new=[t(1−λ)−1](E1−E2)

(i). 若α

new

=α

new

α1new=α2new（同为0或者C）1) y

(1)

≠y

(2)

y(1)≠y(2)。不妨令α

new

=α

new

α1new=α2new=C，根据(12)有α

old

=α

old

α1old=α2old<C，所以根据(15)有y

(2)

−E

)>0

y(2)(E1−E2)>0，最后有y

(2)

new

(2)

)<1

y(2)(E2new+y(2))<1，y

(1)

new

(1)

)<1

y(1)(E1new+y(1))<1。因此更新的两个乘子都满足KKT条件，同理可证明α

new

=α

new

α1new=α2new=0的情形。这种情况L≠H

L≠H

2)y

(1)

(2)

y(1)=y(2)。根据(12)有α

new

=α

new

=α

old

=α

old

α1new=α2new=α1old=α2old，此时λ=0

λ=0，这时无论y

(2)

−E

)

y(2)(E1−E2)取正还是负，此时最多只有一个乘子满足KKT，所以不进行更新处理。这里注意到，α

old

+α

old

=2C或0

α1old+α2old=2C或0这两条可能取到的范围函数对应着L=H

L=H。

(i). 若α

new

≠α

new

α1new≠α2new

1)y

(1)

(2)

y(1)=y(2)。不妨令α

new

=0，α

new

α1new=0，α2new=C，根据(12)有α

old

α2old<C，所以根据(15)有y

(2)

−E

)>0

y(2)(E1−E2)>0，最后有y

(2)

new

(2)

)<1

y(2)(E2new+y(2))<1，y

(1)

new

(1)

)>1

y(1)(E1new+y(1))>1。因此更新的两个乘子都满足KKT条件，同理可证α

new

=C，α

new

α1new=C，α2new=0的情况。这种情况L≠H

L≠H。

2)y

(1)

≠y

(2)

y(1)≠y(2)。这时两个乘子都无法满足KKT条件。这里注意到，α

old

−α

old

=−C或0

α1old−α2old=−C或0这两条可能取到的范围函数对应着L=H

L=H。

所以最后我们得到了更新规则B。

最后还要更新E，保存在列表中，方便下次更新使用。

(四) SMO中拉格朗日乘子的启发式选择方法

终于到了最后一个问题了，Osuna定理告诉我们只要选择出来的两个α

αi中有一个违背了KKT条件，那么目标函数在一步迭代后值会减小。为了加快收敛，我们使用启发式方法（Heuristics）选择拉格朗日乘子。

这条启发式搜索方法选择第一个拉格朗日乘子时，先对所有样例进行循环，循环中碰到违背KKT条件的都进行迭代更新。等这轮过后，如果没有收敛，第二轮就只针对0<α

0<αi<C的样例进行迭代更新。因为0<α

0<αi<C时是最容易违反KKT条件的。

在第一个乘子选择后，第二个乘子也使用启发式方法选择，根据(15)第二个乘子的迭代步长大致正比于|E

−E

|E1−E2|的，所以选择第二个乘子要能够最大化|E

−E

|E1−E2|。即当E

E1为正时选择负的绝对值最大的E

E2，反之，选择正值最大的E

E2。

最后的收敛条件是在界内（clip_image142[5]）的样例都能够遵循KKT条件，且其对应的clip_image084[10]只在极小的范围内变动。

呜！到此我们结束了SMO算法的推导。可以参考John C. Platt在论文中给出的伪代码。

其实SVM还有很多的小细节没有谈到，比如核函数，比如mercer定理的证明。如果有时间再整理一下。

下篇我想从合页损失函数的角度来看看SVM。

本文地址：http://www.longkongtuishu.com/caa75BA1sBFEPC1Y.html

标签： #感知器算法matlab代码