机器学习:完全线性可分/近似线性可分/非线性可分的支持向量机

文章目录 2 近似线性可分支持向量机 3 非线性可分的支持向量机

0 前言

SVM， ，支持向量机。

下面是三种损失函数：

其中，有：

1、在感知机损失中，正确分类的样本不会产生损失，只有错分样本才会产生损失。

2、在对数损失中，不管正确分类的样本，还是错误分类的样本，都会产生损失。

3、在合页损失中，所有正确分类的样本中，有些会产生损失，有些则不会，但是所有的错分样本都会产生损失。

针对数据集的不同程度的线性可分性，把分类问题分为三类：

针对数据集的不同程度的线性可分性，发展出了三种类型的支持向量机模型：

下面就对这三种SVM进行介绍。

1 完全线性可分支持向量机 1.1 模型的数学形式

下面首先用数学语言描述完全线性可分二分类问题：

支持向量机是从几何的角度看待二分类问题的，它最终要找的是一个超平面。如下：

看起来与感知机有点类似，接下来要解决的是如何从数据中学习并确定最优参数，下面才是SVM与感知机的本质区别。

1.2 模型的评价策略

线性可分支持向量机利用(硬)间隔最大化的损失计算原则求最优分离超平面，这时，解是唯一的，即超平面是唯一的。

函数间隔的定义如下：

函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变w和b，例如将它们改为2w和2b，超平面并没有改变，但函数间隔却成为原来的2倍。这一事实启示我们，可以对分离超平面的法向量w加某些约束，如规范化，||w||=1，使得间隔是确定的。这时函数间隔成为几何间隔( )。

下图给出了超平面(w,b)及其法向量w：

点A表示某一实例xi，其类标记为yi=+1，这是点A在超平面正的一侧的情形，点A与超平面(w,b)的距离由线段AB给出，记作：

如果点A在超平面负的一侧，即yi=-1，那么点与超平面的距离为：

一般地，当样本点(xi，yi)被超平面(w,b)正确分类时，点xi与超平面(w,b)的距离是：

下面是几何间隔的定义：

超平面(w,b)关于样本点(xi,yi)的几何间隔一般是实例点到超平面的带符号的距离( )，当样本点被超平面正确分类时就是实例点到超平面的距离。

由公式7.3-7.6得出函数间隔与几何间隔的关系如下：

如果||w||=1，那么函数间隔和几何间隔相等。如果超平面参数w和b成比例地改变(超平面没有改变)，则函数间隔也按此比例改变，而几何间隔不变。

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个(等价于感知机)，但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

下面考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。这个问题可以表示为下面的约束最优化问题：

即我们希望最大化超平面(w,b)关于训练数据集的几何间隔γ，约束条件表示的是超平面(w,b)关于每个训练样本点的几何间隔至少是γ。

考虑几何间隔和函数间隔的关系式(7.8)，可将这个问题改写为：

函数间隔的取值并不影响最优化问题的解。事实上，假设将w和b按比例改变为λw和λb，这时函数间隔成为：

函数间隔的这一改变对上面最优化问题的不等式约束(7.12)没有影响，也就是说，它产生一个等价的最优化问题。这样，就可以取：

有：

于是就得到下面的线性可分支持向量机学习的最优化问题：

这是一个凸二次规划( )问题。

如果求出了约束最优化问题(7.13)-(7.14)的解w*，b*，那么就可以得到最大间隔分离超平面w*·x+b*=0及分类决策函数f(x)=sign(w*·x+b*)，即线性可分支持向量机模型。综上所述，就有下面的线性可分支持向量机的学习算法：

定理7.1：(最大间隔分离超平面的存在唯一性)若训练数据集T线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量( )。支持向量是使约束条件式(7.14)等号成立的点，即yi(w·xi+b)-1=0，其中：

1、对yi=+1的正例点，支持向量在超平面H1：w·x+b=1上。

2、对yi=-1的负例点，支持向量在超平面H2：w·x+b=-1上。

如下图所示，在H1和H2上的点就是支持向量：

注意到H1和H2平行，并且没有实例点落在它们中间。在H1与H2之间形成一条长带，分离超平面与它们平行且位于它们中央。长带的宽度，即H1与H2之间的距离称为间隔()。间隔依赖于分离超平面的法向量w，等于2/||w||。H1和H2称为间隔边界。

在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用。如果移动支持向量将改变所求的解。但是如果在间隔边界以外移动其他实例点，甚至去掉这些点，则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用，所以将这种分类模型称为支持向量机。支持向量的个数一般很少，所以支持向量机仅由很少的“重要的”训练样本确定。

1.3 模型的优化方法

线性可分支持向量机学习的最优化问题如下：

将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题(dual )得到原始问题( )的最优解，这就是线性可分支持向量机的对偶算法(dual )。这样做的优点：

1、对偶问题往往更容易求解。

2、自然引入核函数，进而推广到非线性分类问题。

首先构建拉格朗日函数( )。为此，对每一个不等式约束(7.14)引进拉格朗日乘子( )αi≥0，i=1,2,…,N，有：

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

所以，为了得到对偶问题的解，需要先求L(w,b,α)对w,b的极小，再求对α的极大。即：

下面求解上述对偶问题，首先：

将式(7.19)代入拉格朗日函数(7.18)，并利用式(7.20)，即得：

然后：

将式(7.21)的目标函数由求极大转换成求极小，就得到下面与之等价的对偶最优化问题：

从上述对偶问题得到α的最优解向量，然后通过：

可以得到w的最优解向量，那么偏置b怎么求出来呢？

对线性可分训练数据集，假设对偶最优化问题(7.22)-(7.24)对α的解为α*=(α*1,α*2,…,α*N)T，可以由α*求得原始最优化问题(7.13)-(7.14)对(w,b)的解w*，b*。有下面的定理：

则：

这就是说，分类决策函数只依赖于输入x和训练样本输入的内积。式(7.30)称为线性可分支持向量机的对偶形式。综上所述，对于给定的线性可分训练数据集，可以首先求对偶问题(7.22)-(7.24)的解α*；再利用式(7.25)和式(7.26)求得原始问题的解w*，b*；从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。如下：

续上图：

下面是支持向量的定义：

2 近似线性可分支持向量机

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为公式中的不等式约束并不能都成立，要将其扩展到线性不可分问题，就需要修改硬间隔最大化，使其成为软间隔最大化。

先假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点()，将这些特异点除去后，剩下大部分的样本点组成的集合是线性可分的。有：

这里，C>0称为惩罚参数，一般由应用问题决定，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化目标函数(7.31)包含两层含义：使||w||2/2尽量小，从而使间隔尽量大，同时使误分类点的个数尽量小，C是调和二者的系数。

有了上面的思路，可以和训练数据集线性可分时一样来考虑训练数据集线性不可分时的线性支持向量机学习问题。相应于硬间隔最大化，它称为软间隔最大化。线性不可分的线性支持向量机的学习问题变成如下凸二次规划( )问题(原始问题)：

下面给出线性支持向量机的定义：

原始最优化问题(7.32)-(7.34)的拉格朗日函数是：

原始最优化问题的对偶问题是拉格朗日函数的极大极小问题。首先求L(w,b,ξ,α,μ)对w,b,ξ的偏导数并分别令其为0，即：

将式(7.41)-(7.43)代入式(7.40)，得：

然后：

最后：

原始问题(7.32)-(7.34)是一个凸二次规划问题，因而关于(w,b,ξ)的解是存在的。可以证明w的解是唯一的，但b的解可能不唯一，而是存在于一个区间。

设问题(7.32)-(7.34)的解是w*，b*，于是可以得到分离超平面w*·x+b*=0及分类决策函数f(x)=sign(w*·x+b*)。称这样的模型为训练样本线性不可分时的线性支持向量机，简称为线性支持向量机。显然，线性支持向量机包含线性可分支持向量机。由于现实中训练数据集往往是线性不可分的，线性支持向量机具有更广的适用性。

可以通过求解对偶问题而得到原始问题的解，进而确定分离超平面和决策函数。下面以定理的形式叙述原始问题的最优解和对偶问题的最优解的关系：

于是有下面的算法：

在步骤(2)中，对任一适合条件0