支持向量机1--线性SVM用于分类原理

2021-06-24 11:02:38 浏览数 (1)

在机器学习中，支持向量机（SVM，也叫支持向量网络），是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。是由Vapnik与同事（Boser等，1992；Guyon等，1993；Vapnik等，1997）在AT＆T贝尔实验室开发。支持向量机是基于统计学习框架与由Chervonenkis（1974）和Vapnik（1982，1995）提出Vapnik–Chervonenkis理论上的最强大的预测方法之一。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中。

当数据未被标记时，不能进行监督式学习，需要用非监督式学习，它会尝试找出数据到簇的自然聚类，并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类，当数据未被标记或者仅一些数据被标记时，支持向量聚类经常在工业应用中用作分类步骤的预处理。

以上内容参考维基百科[1]

支持向量机涵盖有监督学习、无监督学习以及半监督学习

功能

有监督学习

线性二分类与多分类（Linear Support Vector Classification）非线性二分类与多分类（Support Vector Classification, SVC）普通连续型变量的回归（Support Vector Regression） 概率型连续变量的回归（Bayesian SVM）

无监督学习

支持向量聚类（Support Vector Clustering，SVC）异常值检测（One-class SVM）

半监督学习

转导支持向量机（Transductive Support Vector Machines，TSVM）

支持向量机在线性和非线性分类中，效果都非常好。

支持向量机的分类方法，是在一组分布中找出一个超平面作为决策边界，使模型在数据上的分类误差尽量接近于零，尤其是在未知数据集上的分类误差（泛化误差）尽量小。

超平面在几何中，超平面是一个空间的子空间，它是维度比所在空间小一维的空间。 如果数据空间本身是三维的，则其超平面是二维平面，而如果数据空间本身是二维的，则其超平面是一维的直线。

边际(margin)越大越好

二维平面内有两类数据点，实心圆与空心菱形表示。很容易找出一条超平面即决策边界将这两类数据分割为两部分，由于这个决策边界有无数条，下面以其中两条为例，演示边际大小对分类结果的影响。

B1

B2

把其中一个决策边界

B_1

向两边平移(

B_2

做相应的操作)，直到碰到离这条决策边界最近的实心圆与空心菱形后停下，形成两个新的超平面，分别是

b_{11}

和

b_{12}

，并且将原始的决策边界移动到

b_{11}

和

b_{12}

的中间，确保到

b_{11}

和

b_{12}

的距离相等。在

b_{11}

和

b_{12}

中间的距离，叫做

B_1

这条决策边界的边际(margin)，通常记作

d

。

在原有数据集中引入测试样本（红色），对于

B_1

而言，仅有一个空心菱形被误分类。而对于

B_2

而言，却有两个实心圆与三个空心菱形被误分类了，这条决策边界上的泛化误差就远远大于

B_1

了。

这个例子表现出，拥有更大边际的决策边界在分类中的泛化误差更小，这一点可以由结构风险最小化定律来证明（SRM）。如果边际小，则任何轻微扰动都会对决策边界的分类产生很大的影响。边际很小的情况，是一种模型在训练集上表现很好，却在测试集上表现糟糕的情况，所以会"过拟合"。所以我们在找寻决策边界的时候，希望边际越大越好。

支持向量机，就是通过找出边际最大的决策边界，来对数据进行分类的分类器。因此支持向量分类器又叫做最大边际分类器。

非线性多维支持向量机SVC

sklearn中非线性多维支持向量机同时支持非线性和线性模型。

代码语言：javascript复制
class sklearn.svm.SVC (C=1.0, 
                       kernel='rbf', 
                       degree=3, 
                       gamma='auto_deprecated', 
                       coef0=0.0, 
                       shrinking=True,
                       probability=False, 
                       tol=0.001, 
                       cache_size=200, 
                       class_weight=None, 
                       verbose=False, 
                       max_iter=-1, 
                       decision_function_shape='ovr', 
                       random_state=None)

线性可分与硬间隔最大化

无论是线性支持向量机还是非线性支持向量机，都是由输入空间转换到特征空间，支持向量机的学习是特征空间进行的。

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

T={(x_1,y_1),(x_2,y_2),cdots,(x_N,y_N)}

其中，

x_1in chi=R^n

,

y_i in Y ={ 1,-1}
i=1,2,cdots,N

,

x_i

为第

i

个特征向量，也称实例，

y_i

为

x_i

的类标记，当

y_i= 1

时，称

x_i

为正例；当

y_i=-1

时，称

x_i

为负例，

(x_i,y_i)

称为样本点。假设训练数据是线性可分的。

定义：线性可分支持向量机 给定线性可分训练数据集合，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

w^Tcdot x b =0

相应的分类决策函数

f(x)=sign(w^T cdot x b)
w^T

为参数向量，

x

是特征向量，

b

是截距。

这边有两个理解：

1）分离超平面

w^Tcdot x b =0

的理解

这与线性回归公司类似

y(x)=theta^Tcdot x theta_0

线性回归中等号的一边是标签，回归后会拟合出一个标签。而决策边界的表达式中却没有标签的存在，全部是由参数，特征和截距组成的一个式子，等号的一边是0。

在特征空间上的训练数据集中，给定固定的

w^T

和

b

，这个式子就可以是一条固定直线。

  • 在
w^T

和

b

不确定的状况下，表达式就可以代表平面上的任意一条直线。

  • 如果在
w^T

和

b

固定时，给定一个唯一的

x

的取值，表达式就可以表示一个固定的点。

在SVM中使用这个表达式来表示决策边界。目标是求解能够让边际最大化的决策边界，所以要求解参数向量

w^T

和截距

b

。

2）指示函数

f(x)=sign(w^T cdot x b)

的理解

上面说到，对于一个样本点

(x_i,y_i)

, 当

y_i= 1

时，

x_i

为正例；当

y_i=-1

时，

x_i

为负例。因此有

  • 决策边界以上的点，标签都为正，并且通过调整
w^T

和

b

的符号，让这个点在

w^Tcdot x b

上得出的结果为正。

  • 决策边界以下的点，标签都为负，并且通过调整
w^T

和

b

的符号，让这个点在

w^Tcdot x b

上得出的结果为负。

  • 决策边界以上的点都为正，以下的点都为负，是为了计算简便，而人为规定的。这种规定，不会影响对参数向量
w^T

和截距

b

的求解。

1、函数间隔和几何间隔

函数间隔(functional margin)

定义：对于给定的训练数据集

T

和超平面

(w^T,b)

，定义超平面

(w^T,b)

关于样本点

(x_i,y_i)

的函数间隔为

hat gamma_i=y_i(w^Tcdot x_i b)

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

w^Tcdot x b =0

确定的情况下，

|w^Tcdot x b|

能够相对地表示

x

距离超平面的远近；而

w^Tcdot x b

的符号与类标记

y

的符号是否一致能够表示分类是否正确。所以用

y(w^Tcdot x b)

来表示分类的正确性及确信度。

几何间隔(geometric margin)

函数间隔表示分类预测的正确性和确信度。但是选择分离超平面时，只用函数间隔还是不够的。因为当成比例的改变参数向量

w^T

和截距

b

时，超平面没有改变，但函数间隔却改变了。因此在分离超平面的法向量

w

加某些约束，使得间隔确定。

gamma_i=y_i(frac{w^T}{||w||}cdot x_i frac{b}{||w||})

几何间隔的本质其实是点

x_i

到超平面

(w^T,b)

（决策边界）的带符号的距离(signed distance)。

函数间隔与几何间隔之间的关系是

gamma_i=frac{hat gamma_i}{||w||},,, or,,,gamma=frac{hat gamma}{||w||}

如果

||w||=1

， 那么函数间隔和几何间隔相等。

2，间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

最大化间隔分离超平面，即表示为下面的约束最优化问题：

max_{w,b},,,,,frac{hat gamma}{||w||}
s.t. ,,,,y_i(w^Tx_i b) geq hat gamma,,,,i=1,2,cdots,N

函数间隔

hat gamma

的取值并不影响最优化问题的解。这样函数间隔可以取

hat gamma=1

，带入上述最优化问题，又最大化

frac{1}{||w||}

和 最小化

frac12||w||^2

是等价的。于是得到线性可分支持向量机学习的最优化问题。

min_{w,b},,,,,frac12||w||^2
s.t. ,,,,y_i(w^Tx_i b) -1geq 0,,,,i=1,2,cdots,N

以上就是SVM的损失函数最初形态。

间隔最大化的理解

决策边界的两边要有两个超平面，这两个超平面在二维空间中就是两条平行线（即图中虚线超平面），而他们之间的距离就是我们的边际

d

。而决策边界位于这两条线的中间，所以这两条平行线必然是对称的。另这两条平行线被表示为：

w^Tcdot x b =1,,,, ,,,,, w^Tcdot x b =-1

表达式两边的1和-1分别表示了两条平行于决策边界的虚线到决策边界的相对距离。此时，可以让这两条线分别过两类数据中距离决策边界最近的点，这些点就被称为"支持向量"。其中参数向量 的方向必然是垂直于决策边界。

边际

d

的距离计算：在两条过支持向量的超平面上的两个点

x_1

和

x_2

，且两点

x_1

和

x_2

之间的连线平行于

w

，则：

frac{w^Tcdot(x_1-x_2)}{||w||} = frac{2}{||w||}
d=frac{2}{||w||}

要最大化间隔

d

，就要求解

w

的最小值。极值问题可以相互转化，可以把求解

w

的最小值转化为求解以下函数的最小值：

min_{w,b},,,,,frac12||w||^2

之所以要在模长上加上平方，是因为模长的本质是一个距离，所以它是一个带根号的存在，对它取平方，是为了消除根号。

两条虚线表示的超平面，是数据边缘所在的点。所以对于任意样本

i

，可以把决策函数写作：

w^T cdot x_i b geq1,,,if,,,y_i=1
w^T cdot x_i b leq-1,,,if,,,y_i=-1

将两个式子整合即得到约束条件

y_i(w^Tx_i b) -1geq 0,,,,i=1,2,cdots,N

拉格朗日对偶函数和决策函数

1、拉格朗日乘数法求解凸优化问题

凸优化问题是指约束最优化问题

min_{w} ,,,,f(w)
s.t.,,,,g_i(w)leq0,,,,,,i=1,2,cdots,k
,,,,,,,,,,,,,,h_i(w)=0,,,,,,i=1,2,cdots,l

其中目标函数

f(w)

和约束函数

g_i(w)

都是实数上的连续可微的凸函数，约束函数

h_i(w)

是实数上的仿射函数（满足

h_i(w)=acdot x b ,,,,ain R^n,,,bin R,,,xin R^n

）

因为我们的损失函数的最初形态：

min_{w,b},,,,,frac12||w||^2
s.t. ,,,,y_i(w^Tx_i b) -1geq 0,,,,i=1,2,cdots,N

是满足凸优化问题，因此使用拉格朗日乘数来将损失函数改写为考虑了约束条件的形式

L(w,b,alpha) =frac12||w||^2-sum^N_{i=1}alpha_i(y_i(w^Tx_i b) -1),,,(alpha_i geq0)

称为拉格朗日函数，其中

alpha_i

叫做拉格朗日乘数。

拉格朗日函数也分为两部分。第一部分和原始的损失函数一样，第二部分呈现了带有不等式的约束条件。

因此希望

L(w,b,alpha)

不仅能够代表原有的损失函数

f(x)

和约束条件，还能够表示最小化损失函数来求解

w

和

b

的意图，所以要先以

alpha

为参数，求解

L(w,b,alpha)

的最大值，再以

w

和

b

为参数，求解

L(w,b,alpha)

的最小值。因此得到原始问题是极小极大问题：

min_{w,b}max_{alpha_i geq0}L(w,b,alpha),,,,(alpha_i geq0)

这个式子分两步走，第一步最大化

max L(w,b,alpha)

，有两种情况：

  • 当
y_i(w^Tx_i b) -1 > 0

，函数的第二部分

sum^N_{i=1}alpha_i(y_i(w^Tx_i b) -1)

就一定为正，式子

frac12||w||^2

需要减去一个正数，此时若要最大化

L(w,b,alpha)

，则

alpha

必须取到0。

  • 当
y_i(w^Tx_i b) -1 < 0

，函数的第二部分

sum^N_{i=1}alpha_i(y_i(w^Tx_i b) -1)

就一定为负，式子

frac12||w||^2

需要减去一个负数，此时若要最大化

L(w,b,alpha)

，则

alpha

必须取到正无穷。

若把函数第二部分当作一个惩罚项来看待，则

y_i(w^Tx_i b) -1 >0

时函数没有受到惩罚，而

y_i(w^Tx_i b) -1 < 0

时函数受到了极致的惩罚，即加上了一个正无穷项，函数整体永远不可能取到最小值。所以第二步执行

min

的命令，求解函数整体的最小值，就永远不能让

alpha

取到正无穷，即是说永远不让

y_i(w^Tx_i b) -1 < 0

的状况出现，从而实现了求解最小值的同时让约束条件被满足。

2、对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性（关注公共号，并回复"拉格朗日对偶性"，获取相关解释），通过求解对偶问题得到原始问题的最优解。

这样一是对偶问题更易求解，二是自然引入核函数（参见下一篇非线性SVM），进而推广到非线性分类问题。

原始问题是极小极大问题：

min_{w,b}max_{alpha_i geq0}L(w,b,alpha)

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

max_{alpha_i geq0}min_{w,b}L(w,b,alpha)

对拉格朗日函数

L(w,b,alpha)

展开

L(w,b,alpha)=frac12||w||^2-sum^N_{i=1}alpha_i(y_i(w^T cdot x_i b) -1)
L(w,b,alpha)=frac12||w||^2-sum^N_{i=1}alpha_iy_iw^T cdot x_i alpha_iy_ib -alpha_i)
L(w,b,alpha)=frac12||w||^2-sum^N_{i=1}(alpha_iy_iw^T cdot x_i)-sum^N_{i=1}alpha_iy_ib sum^N_{i=1}alpha_i
L(w,b,alpha)=frac12w^Tw-sum^N_{i=1}(alpha_iy_iw^T cdot x_i)-sum^N_{i=1}alpha_iy_ib sum^N_{i=1}alpha_i

先求

L(w,b,alpha)

对

w,b

的极小，再求对

alpha

的极大。

（1）求

min_{w,b}L(w,b,alpha)
nabla_wL(w,b,alpha) = frac{partial L(w,b,alpha)}{partial w}=w-sum_{i=1}^N(alpha_iy_ix_i)
w=sum_{i=1}^N(alpha_iy_ix_i)
sum^N_{i=1}alpha_iy_i=0

将上述结果带入拉格朗日函数

L(w,b,alpha)

中得

L(w,b,alpha)=frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j)-sum^N_{i=1}alpha_iy_i left(left(sum^N_{j=1}alpha_jy_jx_j right)cdot x_j b right) sum^N_{i=1}alpha_i
L(w,b,alpha)=-frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j) sum^N_{i=1}alpha_i

即

min_{w,b} L(w,b,alpha)=-frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j) sum^N_{i=1}alpha_i

（2）求

min_{w,b} L(w,b,alpha)

对

alpha

的极大，即是对偶问题

max_{alpha}-frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j) sum^N_{i=1}alpha_i
s.t. ,,,,,sum^N_{i=1}alpha_iy_i=0 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
alpha_i geq0,,,,,i=1,2,3,cdots,N,,,,,,,,

因此其对偶最优化问题，转化成求极小问题

min_{alpha}frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j)-sum^N_{i=1}alpha_i
s.t. ,,,,,sum^N_{i=1}alpha_iy_i=0 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
alpha_i geq0,,,,,i=1,2,3,cdots,N,,,,

这里需要使用梯度下降，SMO或者二次规划(QP，quadratic programming)来求解

alpha

，考虑到这一过程对数学的要求已经远远超出了我们需要的程度，更是远远超出我们在使用sklearn时需要掌握的程度，如何求解对偶函数中的在这里就不做讲解了。

一旦我们求得了值，我们就可以使用求导后得到

w

。

3、线性可分支持向量机学习算法

输入：线性可分训练集

T={(x_1,y_1),(x_2,y_2),cdots,(x_N,y_N)}

,其中，

x_1in chi=R^n

,

y_i in Y ={ 1,-1}
i=1,2,cdots,N

输出：分离超平面和分类决策函数

  1. 构造并求解约束最优化问题
min_{alpha},,,,frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j)-sum^N_{i=1}alpha_i
s.t. ,,,,,sum^N_{i=1}alpha_iy_i=0 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
alpha_i geq0,,,,,i=1,2,3,cdots,N,,,,

求得最优解

alpha^*=(alpha^*_1,alpha^*_2,cdots,alpha^*_N)^T
  1. 计算
w^*=sum_{i=1}^N(alpha^*_iy_ix_i)

并选择

alpha^*

的一个正分量

alpha^*_j>0

，计算

b^*=y_j-sum^N_{i=1}alpha^*_iy_i(x_icdot x_j)
  1. 求得分离超平面
w^*cdot x b^*=0

分类决策函数：

f(x)=sign(w^*cdot x b^*)

在以上第二步计算

w^*

和

b^*

时看出，

w^*

和

b^*

只依赖于训练数据中对应于

alpha^*_i>0

的样本点

(x_i,y_i)

，而其他样本点对

w^*

和

b^*

没有影响。因此将对应于

alpha^*_i>0

的样本点

(x_i,y_i)

成为支持向量。

4、对拉格朗日对偶性算法的理解

对于任何一个拉格朗日函数

L(x,alpha)=f(x) sum^N_{i=1}alpha_ih_i(x)

，都存在一个与它对应的对偶函数

g(alpha)

，只带有拉格朗日乘数

alpha

作为唯一的参数。如果

L(x,alpha)

的最优解存在并可以表示为

min_{x}L(x,alpha)

，并且对偶函数的最优解也存在并可以表示为

max_{alpha}g(alpha)

，则我们可以定义对偶差异(dual gap)，即拉格朗日函数的最优解与其对偶函数的最优解之间的差值：

Delta=min_x L(x, alpha)-max_{alpha}g(alpha)

如果个拉格朗日函数满足KKT(Karush-Kuhn-Tucker)条件：

frac{partial L}{partial x_i}=0,,,,forall_i=1,2,cdots,d
,,,,,,h_ileq0,,,,forall_i=1,2,cdots,q
,,,,,,alpha_i geq 0,,,,forall_i=1,2,cdots,q
,alpha_ih_i = 0,,,,forall_i=1,2,cdots,q

则

Delta=0

，则称

L(x,alpha)

与其对偶函数之间存在强对偶关系(strong duality property)，此时我们就可以通过求解其对偶函数的最优解来替代求解原始函数的最优解。

拉格朗日函数

L(w,b,alpha)=frac12||w||^2-sum^N_{i=1}alpha_i(y_i(w cdot x_i b) -1)

第一个条件函数求偏导为零条件成立，并得到如下结果

sum^N_{i=1}alpha_iy_i=0
w^=sum_{i=1}^Nalpha_iy_ix_i

第二、三个条件，在得到原始问题极小极大原始函数时

min_{w,b}max_{alpha_i geq0}L(w,b,alpha),,,,(alpha_i geq0)

已经分析得到

-(y_i(w^Tcdot x_i b)-1) leq0
alpha_i ge 0

第四个条件，落在虚线的超平面上的样本点可以使得

y_i(w^Tcdot x_i b)-1=0

，即支持向量。所有所有不是支持向量的样本点则必须满足

alpha_i=0
alpha_i(y_i(w^Tcdot x_i b)-1) =0

满足第四个条件说明了，求解的参数

w

和

b

以及求解的超平面的存在，只与支持向量相关，与其他样本点都无关。现在KKT的五个条件都得到了满足，就可以使用的对偶函数来求解了。

可视化决策边界及支持向量

代码语言：javascript复制
from sklearn.datasets import make_blobs
from sklearn.svm import SVC
import matplotlib.pyplot as plt
import numpy as np
plt.rcParams['axes.unicode_minus']=False

#将上述过程包装成函数：
def plot_svc_decision_function(model,ax=None):
    if ax is None:
        ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()
    x = np.linspace(xlim[0],xlim[1],30)
    y = np.linspace(ylim[0],ylim[1],30)
    Y,X = np.meshgrid(y,x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)
    ax.contour(X, Y, P,colors="k",levels=[-1,0,1],alpha=0.8,linestyles=["--","-","--"])
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)
#则整个绘图过程可以写作：
X,y = make_blobs(n_samples=50, centers=2, random_state=0,cluster_std=0.6)
clf = SVC(kernel = "linear").fit(X,y)
supports = clf.support_vectors_
plt.figure(figsize=(10,6))
plt.scatter(X[:,0],X[:,1],c=y,s=80,cmap="copper")
plot_svc_decision_function(clf)
plt.scatter(supports[:,0],supports[:,1],marker='o',s=200,facecolors='none', edgecolors='r')

输出

决策边界

线性不可分与软间隔最大化

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为约束条件并不能成立。

如以上数据集，不是完全线性可分的，如果仍使用硬间隔最大化，其边际将会变得很小，且存在一个误分类的数据。当引入更多的训练数据，或引入测试数据时其泛化能力将会很小。

那怎样才能将线性支持向量机扩展到线性不可分问题中呢？这就引入了软间隔最大化。

线性不可分意味着某些样本点

(x_i,y_i)

不能满足函数间隔大于等于1的约束条件。可以对每个样本点

(x_i,y_i)

引进一个松弛变量

zeta ge 0

,使得函数间隔加上松弛变量大于等于1。约束条件为

y_i(w cdot x_i b)ge1-zeta_i

通过将将硬间隔推广到软间隔的情况上，让决策边界能够忍受一小部分训练误差。这个时候，决策边界就不是单纯地寻求最大边际了，因为对于软间隔的数据来说，边际越大被分错的样本也就会越多，因此我们需要找出一个"最大边际"与"被分错的样本数量"之间的平衡。

松弛变量的理解来看上面的图像。位于黄色色点附近的黑色点

x_p

在原本的判别函数中必定会被分为黄色，所以一定会被判断错。现在作一条与决策边界平行，但是过点

x_p

的直线

wcdot x_i b=1-zeta_i

（图中的红色虚线）。这条直线是由

wcdot x_i b=1

平移得到，所以两条直线在纵坐标上的差异就是

zeta

（竖直的黑色箭头）。而

x_p

点到

wcdot x_i b=1

的距离就可以表示为

frac{zetacdot w}{||w||}

，即

zeta

在

w

方向上的投影。由于单位向量是固定的，所以

zeta

可以作为点

x_p

在原始的决策边界上的分类错误的程度的表示，隔得越远，分得越错。但

zeta

并不是点到决策超平面的距离本身。 虽然把异常的黑色点

x_p

分类正确了，但同时也分错了一系列黄色的点。所以必须在求解最大边际的损失函数中加上一个惩罚项，用来惩罚具有巨大松弛系数的决策超平面。

因此线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题（原始问题）

min_{w,b,zeta}frac{||w||^2}{2} Csum^n_{i=1}zeta_i
s.t.,,,y_i(w^Tcdot x b ge1-zeta_i)
,,,,,,,,,,,,zeta_i ge0,,,,i=1,2,cdots,N

其中，

C>0

称为惩罚参数，

C

值越大对误分类的惩罚越大。是"最大边际"与"被分错的样本数量"的调节系数。

需要满足的KKT条件为

frac{partial L(w,b,alpha,zeta)}{partial w} = frac{partial L(w,b,alpha,zeta)}{partial b}=frac{partial L(w,b,alpha,zeta)}{partial zeta}=0
alpha_i ge0,zeta ge0,mu_i ge0
alpha_i(y_i(w^Tcdot x b) -1 zeta_i)=0
mu_izeta_i=0

原始问题的对偶问题是

min_{alpha}frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j)-sum^N_{i=1}alpha_i
s.t. ,,,,,sum^N_{i=1}alpha_iy_i=0 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
0 le alpha_i le C,,,,,i=1,2,3,cdots,N,,,,

这种状况下的拉格朗日对偶函数看起来和线性可分状况下的对偶函数一模一样，但在这个函数中，拉格朗日乘数

alpha

的取值的限制改变了。在硬间隔的状况下，拉格朗日乘数值需要大于等于0，而现在它被要求不能够大于用来控制惩罚项的惩罚力度的系数

C

。

原始最优化问题的拉格朗日函数是

L(w,b,zeta,alpha,mu)=frac12||w||^2 Csum^N_{i=1}zeta_i-sum^N_{i=1}alpha_i(y_i(w^Tcdot x b) -1 zeta_i)-sum^N_{i=1}mu_izeta_i

其中，

alpha_ige0,mu ge0

。

线性支持向量机学习算法

输入：训练数据集

T={(x_1,y_1),(x_2,y_2),cdots,(x_N,y_N)}

,其中，

x_1in chi=R^n

,

y_i in Y ={ 1,-1}
i=1,2,cdots,N

输出：分离超平面和分类决策函数

  1. 选择惩罚参数
C>0

，并构造并求解凸二次规划问题

min_{alpha},,,,frac12sum^N_{i=1}sum^N_{j=1}alpha_ialpha_jy_iy_j(x_icdot x_j)-sum^N_{i=1}alpha_i
s.t. ,,,,,sum^N_{i=1}alpha_iy_i=0 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,0 le alpha_i le C,,,,,i=1,2,3,cdots,N

求得最优解

alpha^*=(alpha^*_1,alpha^*_2,cdots,alpha^*_N)^T
  1. 计算
w^*=sum_{i=1}^N(alpha^*_iy_ix_i)

并选择

alpha^*

的一个正分量并适合条件

C>alpha^*_j>0

，计算

b^*=y_j-sum^N_{i=1}alpha^*_iy_i(x_icdot x_j)
  1. 求得分离超平面
w^*cdot x b^*=0

分类决策函数：

f(x)=sign(w^*cdot x b^*)

步骤二中，对任一适合条件的

C>alpha^*_j>0

的

alpha_j^*

，都可以求出

b^*

。由于原始问题对

b

的解不唯一，实际中取所有符号条件的样本点上的平均值。

支持向量

软间隔的支持向量

x_i

或者在间隔边界上，或在间隔边界与分离超平面之间，或在分离超平面误分类一侧。实例

x_i

到间隔边界的距离为

frac{zeta_i}{||w||}
  • 若 alpha_i^*<czeta_i="0x_i="" 恰好落在间隔边界上<="" section="">
  • 若
alpha_i^*=C

，则

0<zeta_i<1

，则分类正确，

x_i

在间隔边界与分离超平面之间

  • 若
alpha_i^*=C

，则

zeta_i=1

，则

x_i

在分离超平面上

  • 若
alpha_i^*=C

，则

zeta_i>1

，则

x_i

位于分离超平面误分一侧

参考资料

[1]

支持向量机: https://en.wikipedia.org/wiki/Support-vector_machine

线性回归 机器学习 神经网络 深度学习 人工智能

0 人点赞