线性可分支持向量机与硬间隔最大化

1.概述

2.线性可分支持向量机与硬间隔最大化

1.函数间隔

2.间隔最大化

3.支持向量和间隔边界

4.学习的对偶算法

3.线性支持向量机与软间隔最大化

学习的对偶算法

0. 支持向量

4.非线性支持向量机与核函数

0. 核技巧

1. 核函数的定义

2. 核技巧在支持向量机中的应用

3. 常用核函数

4. 定理

5. 实际中的选择

5.坐标上升法（ ）

6.序列最小最优化SMO算法

0. a值更新推导

1. b值的更新

2. 拉格朗日乘子ai的启发式选择方法

1、概述

支持向量机是一种二类分类模型.它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机还包括核技巧,这使它成为实质上的非线性分类器.支持向量机的学习策略是间隔最大化,可形式化为一个求解凸二次规划( )的问题,也等价于正则化的合页损失函数的最小化问题.支持向量机的学习算法是求解凸二次规划的最优化算法.

支持向量机学习方法包含构建由简至繁的模型:线性可分支持向量机、线性支持向量机和非线性支持向量机。简单模型是复杂模型的基础，也是复杂模型的特殊情况。

（1）线性可分支持向量机：当训练数据线性可分时（一条线或平面能完全正确分开），通过硬间隔最大化（hard ），学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机。

（2）线性支持向量机：当训练数据近似线性可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机。

（3）当训练数据线性不可分时，通过使用核技巧（ trick）及软间隔最大化，学习非线性支持向量机。

当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数（ ）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高纬的特征空间中学习线性支持向量机。这样的方法称为核技巧。核方法（ ）是比支持向量机更为一般的机器学习方法。

线性可分支持向量机与硬间隔最大化

学习的目的是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应于方程w·x+b=0,它由法向量w和截距b决定,可用(w,b)来表示.分离超平面将特征空间划分为两部分,一部分是正类,一部分是负类.法向量指向的那一侧为正类,另一侧为负类. （例如我们有一个线性函数，g(x)=wx+b，我们可以取阈值为0，这样当有一个样本xi需要判别的时候，我们就看g(xi)的值。若g(xi)>0，就判别为类别C1，若g(xi)

关于g(x)=wx+b这个表达式要注意三点：一，式中的x不是二维坐标系中的横轴，而是样本的向量表示，例如一个样本点的坐标是(3,8)，则xT=(3,8) ，而不是x=3（一般说向量都是说列向量，因此以行向量形式来表示时，就加上转置）。二，这个形式并不局限于二维的情况，在n维空间中仍然可以使用这个表达式，只是式中的w成为了n维向量（在二维的这个例子中，w是二维向量，注意这里的w严格的说也应该是转置的形式，为了表示起来方便简洁，以下均不区别列向量和它的转置，聪明的读者一看便知）；三，g(x)不是中间那条直线的表达式，中间那条直线的表达式是g(x)=0，即wx+b=0，我们也把这个函数叫做分类面。）

当x

当x=0时，sign(x)=0;

当x>0时，sign(x)=1。

我们这次使用的结果标签是y=-1,y=1，替换在回归中使用的y=0和y=1（使用函数（或称作函数）将自变量映射到(0,1)上）

下文你将看到，当我们转化到优化的时候，为了求解方便，会把yf(x)令为1，即yf(x)是y(w^x + b)，还是y(w^x - b)，对我们要优化的式子max1/||w||已无影响。

从而在我们进行分类的时候，将数据点 x代入 f(x) 中，如果得到的结果小于 0 ，则赋予其类别 -1 ，如果大于0 则赋予类别 1 。如果 f(x)=0，则很难办了，分到哪一类都不是。

函数间隔

一般地,当训练数据线性可分时,存在无穷多个分离超平面可将两类数据正确分开.感知机利用误分类最小的策略,求得分离超平面,不过这时的解有无穷多个.线性可分支持向量机利用间隔最大化求最优分离超平面,这时,解是唯一的.

一般来说,一个点距离分离超平面的远近可以表示分类预测的确信程度.

在超平面w·x+b=0确定的情况下,|w·x+b|能够相对的表示点x距离超平面的远近(因为跟远近成正比关系).而w·x+b的符号与类标记y的符号是否一致能够表示分类是否正确.所以可用量y(w·x+b)来表示分类的正确性及确信度,这就是函数间隔( )的概念.

我们定义函数间隔 为：

（实际上这两个 是互通的，我们定义 为γˆ=y(wTx+b)=yf(x)，注意前面乘上类别 y 之后可以保证这个 的非负性（因为 f(x)

接着，我们定义超平面(w，b)关于训练数据集T的函数间隔为超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值，其中，x是特征，y是结果标签，i表示第i个样本，有：

r=minri(i=1，...n)

然与此同时，问题就出来了：上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改变为2w和2b，虽然此时超平面没有改变，但函数间隔的值f(x)却变成了原来的2倍。

事实上，我们可以对法向量w加些约束条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离--几何间隔 的概念（很快你将看到，几何间隔就是函数间隔除以个||w||，即yf(x) / ||w||）。

点到超平面的距离定义：几何间隔

对于一个点 x ，令其垂直投影到超平面上的对应的为 x0 ，w 是垂直于超平面的一个向量，为样本x到分类间隔的距离，

我们有

其中，||w||表示的是范数。

又由于 x0 是超平面上的点，满足f(x0)=0 ，代入超平面的方程即可算出：

不过这里的是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别 y即可，因此实际上我们定义 几何间隔 为(注：别忘了，上面的定义， r=y(wTx+b)=yf(x))：

代人相关式子可以得出：yi*(w/||w||xi + b/||w||)。

综上，函数间隔y(wx+b)=yf(x)实际上就是|f(x)|，只是人为定义的一个间隔度量；而几何间隔|f(x)|/||w||才是直观上的点到超平面距离

间隔最大化

下面考虑如何求得一个函数间隔最大的分离超平面,即最大间隔分离超平面,具体的这个问题可以表示为下面的约束最优化问题:

有一个问题就是,当w和b按比例改变为λw和λb时,超平面并没有改变(wx+b=0),而ˆγ则变为λˆγ.此时约束条件没有变,因为两边都变成λ倍.但是目标函数却变为λ倍了.优化问题却变了.解决的办法就是在目标函数上加上一个w的规范化项.

这时,我们发现不管ˆγ变为原来的多少倍,优化问题都没有变化.所以我们直接取ˆγ=1,代入上面的优化问题.注意到最大化1||w||等价于最小化12||w||2,于是就得到下面的线性可分支持向量机学习的最优化问题

这是一个凸二次规划问题.通过求解这个凸二次优化问题,可以得到w,b的最优值,代入wx+b=0就是我们的分离超平面了,然后新样本就可以通过决策函数来进行预测了.这就是最大间隔法.

(我这里省略了函数间隔和几何间隔γ=ˆγ||w||的转换,我觉的不如这样讲来的简单和直接,转换来转换去的,看着都晕)

支持向量和间隔边界

可以通过最大化超平面和其最近的各个类别中数据点的距离来寻找最佳超平面。这个距离我们称之为边际距离

从上图中你可以看到超平面 C 的边际距离最大。因此，我们称 C 为最佳超平面。选择具有最大边际距离的超平面的做法是稳健的。如果我们选择其他超平面，将存在较高的错分率。

学习的对偶算法

为了求解线性可分支持向量机的最优化问题,将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对偶问题(dual )得到原始问题( )的最优解,这就是线性可分支持向量机的对偶算法(dual ).这样做的优点,一是对偶问题往往更容易求解,而是自然引入核函数,进而推广到非线性分类问题.

原始最优化问题:

首先构建拉格朗日函数( ).为此,对每一个不等式约束引进拉格朗日乘子( )ai≥0,i=1,2,...,N,定义拉格朗日函数:

L(w,b,a)=12||w||2−N∑i=1aiyi(w⋅xi+b)+N∑i=1ai

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:

,bL(w,b,a)

所以为了得到对偶问题的解,需要先求L(w,b,a)对w,b的极小,再求对a的极大.(这里跟最大熵里是一样的.不懂请传送到对偶这里)

(1)求minw,bL(w,b,a)

将拉格朗日函数L(w,b,a)分别对w,b求偏导数并令其等于0.

∇wL(w,b,a)=w−N∑i==0∇bL(w,b,a)=N∑i=1aiyi=0

得

w=N∑i=∑i=1aiyi=0

将上面两式代入拉格朗日函数,得:

(2)求minw,bL(w,b,a)对a的极大,即是对偶问题:

(将目标函数求极大变为求极小)

考虑原始最优化问题和对偶最优化问题,原始问题满足强对偶性(不等式只小于0),所以存在w∗,b∗,a∗,使w∗,b∗是原始问题的最优解,a∗是对偶问题的解.这意味着求解原始问题可以转换为求解对偶问题.

对线性可分训练数据集,假设对偶最优化问题的解为a∗=(a∗1,a∗2,....,a∗n)T,则可以由a∗求得原始最优化问题对(w,b)的解w∗,b∗.具体过程如下:

由此定理可知,分离超平面可以写成

[N∑i=1a∗iyi(x⋅xi)]+b∗=0

分类决策函数可以写成

f(x)=sign{[N∑i=1a∗iyi(x⋅xi)]+b∗}

这就是说,分类决策函数只依赖于输入x和训练样本输入的内积(具体是说新样本x和各支持向量的内积,这点很重要,这是后面应用核函数的基础).上式称为线性可分支持向量机的对偶形式.

综上所述,对于给定的线性可分训练数据集,可以首先求对偶问题的解a∗;再利用图中式7.25和7.26求得原始问题的解w∗,b∗;从而得到分离超平面及分类决策函数.这种算法称为线性可分支持向量机的对偶学习算法,是线性可分支持向量机学习的基本算法.(这个算法很重要,是SVM的核心,流程一定要清楚)

为什么a>0的点一定是支持向量,一定在间隔边界上?请看如下证明:

线性支持向量机与软间隔最大化

对于线性可分问题,上述线性可分支持向量机的学习(硬间隔最大化)算法是完美的.但是训练数据集线性可分时理想的情形.在现实问题中,训练数据集往往是线性不可分的,即在样本中出现噪声或特异点.对于这些样本点,不等式约束并能都成立.怎么才能将它扩展到线性不可分问题呢?这就需要修改硬间隔最大化,使其成为软间隔最大化.

具体的做法是对每个样本点(x,y)引进一个松弛变量ξi≥0,使函数间隔加上松弛变量大于等于1.这样,约束条件变为:

yi(w⋅xi+b)≥1−ξi

同时,对每个松弛变量ξi,支付一个代价ξi.原始问题的目标函数由原来的12||w||2变成:

12||w||2+CN∑i=1ξi

这里,C>0称为惩罚参数,一般由应用问题决定,C值大时对误分类的惩罚增大,C值小时对误分类的惩罚减小.最小化上式包含两层含义:使12||w||2尽量小即间隔尽量大,同时使误分类点的个数尽量小,C是调和二者的系数.

有了上面的思路,线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题(原始问题):

上述原始问题是一个凸二次规划问题,因而(w,b,ξ)的解是存在的.可以证明w的解是唯一的,但b的解不唯一,b的解存在与一个区间.

学习的对偶算法

线性支持向量机的对偶算法和线性可分支持向量的对偶算法流程是一样的.只不过多了几个变量需要注意.

以上是推导流程,下面是算法流程

符合条件的样本点上的平均值

支持向量

在线性不可分的情况下,将对偶问题的解a∗=(a∗1,a∗2,....,a∗n)T中对应于a∗i>0的样本点称为支持向量(软间隔支持向量).如下图所示.图中,分离超平面由实线表示,间隔边界由虚线表示,正例点由"。"表示，负例点由“x”表示。图中还标出了实例xi到间隔边界的距离ξ1||w||

软间隔支持向量xi或者在间隔边界上,或者在间隔边界与分离超平面之之间,或者在分离超平面误分的一侧.

下面讨论的是支持向量,所以前提都是a∗i>0的(a∗i=0的点都是分对的,且在间隔边界上或以外.由于a不可能>C所以不讨论):

(1)若a∗i0,才是非负定的.至于使得K非负定,这些参数应满足的充要条件,之间还没有答案.对某些参数,它与高斯核非常近似.

(能满足这些核函数的映射函数都是映射到希尔伯特空间的.希尔伯特空间可以理解为无限维空间.在低维上,是找不到满足核函数的映射函数的.虽然我们并不知道具体的映射函数是什么,但是知道它必须是高纬的才行.)

定理

一个核函数是有效的核函数,也就是说有ϕ(x)⋅ϕ(y)能表达它,或者说能花等号.拿线性核来说,必须能找到映射函数使下式成立:

xTy+c=ϕ(x)⋅ϕ(y)

那么什么样的核函数有映射函数与之对应呢?定理告诉我们,在训练集上得到的核函数矩阵K应该是半正定的K≥0.也就是说:

K是有效的核函数 ==> 核函数矩阵K是对称半正定的。

实际中的选择

在实际中,基本都用的RBF核,它相比其他核函数有以下优点:

1）RBF核函数可以将一个样本映射到一个更高维的空间，而且线性核函数是RBF的一个特例，也就是说如果考虑使用RBF，那么就没有必要考虑线性核函数了。

2）与多项式核函数相比，RBF需要确定的参数要少，核函数参数的多少直接影响函数的复杂程度。另外，当多项式的阶数比较高时，核矩阵的元素值将趋于无穷大或无穷小，而RBF则在上，会减少数值的计算困难。

3）对于某些参数，RBF和具有相似的性能。

坐标上升法（ ）

在最后讨论如何如何求W(a)之前,我们先介绍一下坐标上升法的基本原理(后面要讲的求W(a)中a的值的SMO算法就是基于这种思想).

假设要求解下面的优化问题：

maxaW(a1,a2,...,am)

这里W是a向量的函数.之前我们在回归中提到过两种求最优解的方法，一种是梯度下降法，另外一种是牛顿法。现在我们再讲一种方法称为坐标上升法（求解最小值问题时，称作坐标下降法，原理一样）.

方法过程:

最里面语句的意思是固定除ai之外的所有aj(j≠i)，这时W可看作只是关于ai的函数，那么直接对ai求导优化即可。这里我们进行最大化求导的顺序i是从1到m，可以通过更改优化顺序来使W能够更快地增加并收敛。如果W在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。

(如果你看过我之前写的梯度下降的博客,你会发现这里其实就是共轭方向是欧式空间单位方向的共轭方向法)

下面通过一张图来展示：

椭圆代表了二次函数的各个等高线，变量数为2，起始坐标是(2,-2)。图中的直线式迭代优化的路径，可以看到每一步都会向最优值前进一步，而且前进路线是平行于坐标轴的，因为每一步只优化一个变量。

注:本小节摘抄自

序列最小最优化SMO算法

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

首先回到我们前面一直悬而未解的问题，对偶函数最后的优化问题：

要解决的是在参数(a1,a2,...,an)上求W的极小值问题.至于xi,yi是训练样本,是已知数.C由我们预先设定,也是已知数.

按照坐标上升的思路，我们首先固定除a1以外的所有参数，然后在a1上求极值。等一下，这个思路有问题，因为如果固定a1以外的所有参数，那么a1将不再是变量（可以由其他值推出），因为问题中规定了:

a1y1+N∑i=2aiyi=0

因此，我们需要一次选取两个参数做优化，比如a1和a2，此时a2可以由a1和其他参数表示出来。这样回带到W中，W就只是关于a1的函数了，可解。

这样,SMO的主要步骤如下:

(1)选取一对ai,aj,选取方法是用启发式方法(具体方法后面讲).

(2)固定ai,aj以外的其他参数,确定W极值下的ai,其中aj由ai表示.

SMO之所以高效就是因为在固定其他参数后,对一个参数的优化过程很高效.

a值更新推导

假设我们选取了初始值(a1,a2,...,an)满足了问题中的约束条件.接下来,我们固定(a3,a4,...,an),这样W就是a1和a2的函数.并且a1和a2满足条件:

a1y1+a2y2=−N∑i=3aiyi

由于(a3,a4,...,an)都是已知固定值,因此为了方便,可将等式右边标记为实数值ζ.

a1y1+a2y2=ζ

a1和a2的取值范围

当y1和y2异号时,也就是一个为1,一个为-1时,他们可以表示成一条直线,斜率为1.如下图:

横轴是a1,纵轴是a2,a1和a1既要在矩形方框内(满足0≤ai≤C的约束),也要在直线上(满足N∑i=1aiyi=0的约束),因此

L=max(0,a2−a1),H=min(C,C+a2−a1)

(由于不知道y1,y2符号谁正谁负,所有图中直线有两条,而a1,a2的取值范围相应的就有两种,所以用L和H这样的形式表示了)

同理,当y1和y2同号时(同负或同正):

L=max(0,a2+a1−C),H=min(C,a2+a1)

用a2表示a1

这里我们用和代表某次迭代前的原始值.因此是常数,而a1和a2是变量,待求.由于a1和a2要满足N∑i=1aiyi=0的约束,所以:

+=−N∑i=3aiyi=a1y1+a2y2

那么用s表示y1y2,上式两边乘以y1

a1+sa2=+=δ

其中

δ=−y1N∑i=3aiyi

变换式子:

a1=δ−sa2

至此我们用a2表示了a1,下一步就是代如W(a)使W(a)变为只含一个变量的方程了.

变换W(a)为一个a变量形式

首先我们将W(a)中的a1和a2项展开:

W(a)=++++−a1−a2+

(最后一项是常数项)

其中:

我们将a1=δ−sa2代入W(a)的展开式中得:

这时候就只有a2是变量了.

a1和a2的更新

W(a)对a2求导:

如果W的二阶导数大于0(凸函数),那么一阶导数为0时,就是极小值了.假设其一阶导数为0(一般成立),那么上式化简为:

a2(K11+K22−2K12)=s(K11−K12)δ+y2(v1−v2)+1−s

将δ和v代入后,继续化简推导,得:

a2(K11+K22−2K12)=(K11+K22−2K12)+y2(u1−u2+y2−y1)

我们用η来表示:

η=K11+K22−2K12

通常情况下目标函数是正定的,也就是说,能够在直线约束方向上求得最小值,并且η>0.(实际上η就是W(a)的二阶导,可自己求一下试试)

那么我们在式两边都除以η可以得到

a2=+y2(E1−E2)η

其中Ei=ui−yi.

上面的a2还不是最终迭代后的值,还需要进行取值范围约束:

那么:

anew1=+a(−anew2)

在特殊情况下,η可能不为正,如果核函数K不满足定理,那么目标函数可能变得非正定,η可能出现负值.即使K是有效的核函数,如果训练样本中出现相同的特征x,那么η仍有可能为0.为保证SMO算法在η不为正值的情况下仍有效,我们可以推导出η就是W(a)的二阶导数,当ηy=−x2),当η=0时,W(a)是单调函数,最小值也在边缘处取得,而a2的边缘就是L和H.那么到底是左边还是右边W(a)取极小值呢,那就要将a2=L和a2=H分别带进W(a)中看看哪个W(a)小了,哪个小a2就取对应的边界.然后通过关系式求得a1.

b值的更新

由于a1,a2的选取(选取规则最后讲)要依赖如下条件的判断:

而上式右边的计算需要用到b值,所以在每一次迭代更新完a1,a2后,要根据KKT条件来调整b.

当0