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

0 前言

SVM，Support Vector Machine，支持向量机。

下面是三种损失函数：

其中，有：

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

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

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

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

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

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

1 完全线性可分支持向量机

1.1 模型的数学形式

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

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

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

1.2 模型的评价策略

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

函数间隔的定义如下：

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

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

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

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

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

下面是几何间隔的定义：

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

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

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

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

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

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

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

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

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

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

有：

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

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

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

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

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

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

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

如下图所示，在H₁和H₂上的点就是支持向量：

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

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

1.3 模型的优化方法

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

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

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

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

首先构建拉格朗日函数(Lagrange function)。为此，对每一个不等式约束(7.14)引进拉格朗日乘子(Lagrange multiplier)α_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)对α的解为α*=(α*₁,α*₂,…,α*_N)^T，可以由α*求得原始最优化问题(7.13)-(7.14)对(w,b)的解w*，b*。有下面的定理：

则：

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

续上图：

下面是支持向量的定义：

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

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

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

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

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

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

原始最优化问题(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<α*_j<C的α*_j，按式(7.51)都可求出b*，但是由于原始问题(7.32)~(7.34)对b*的解并不唯一，所以实际计算时可以取在所有符合条件的样本点上的平均值。

2.1 支持向量

2.2 合页损失函数

线性支持向量机学习的模型为分离超平面w*·x+b*=0及决策函数f(x)=sign(w*·x+b*)，其学习策略为软间隔最大化，学习算法为凸二次规划。线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：

目标函数的第1项是经验损失或经验风险。下面的函数：

称为合页损失函数(hinge loss function)。下标“+”表示以下取正值的函数：

有：

下面是一个定理及其证明：

合页损失函数的图形如下图所示：

其中，横轴是函数间隔y·(w·x+b)，纵轴是损失。由于函数形状像一个合页，故名合页损失函数。图中还画出0-1损失函数，可以认为它是二类分类问题的真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性支持向量机是优化由0-1损失函数的上界(合页损失函数)构成的目标函数。这时的上界损失函数又称为代理损失函数(surrogate loss function)。

3 非线性可分的支持向量机

3.1 非线性分类问题

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。如下图是一个例子：

这是一个分类问题，图中“.”表示正实例点，“×”表示负实例点。由图可见，无法用直线(线性模型)将正负实例正确分开，但可以用一条椭圆曲线(非线性模型)将它们正确分开。如果能用Rⁿ中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。

非线性问题往往不好求解，所以希望能用解决线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解决变换后的线性问题的方法求解原来的非线性问题。

通过变换，将上面那张图中的椭圆变换成下图中的直线：

具体的变换形式如下描述：

上面的例子说明，用线性分类方法求解非线性分类问题分为两步：

1、使用一个变换将原空间的数据映射到新空间。

2、在新空间里用线性分类学习方法从训练数据中学习分类模型。

核技巧就属于这样的方法：

3.2 核函数的定义

其中：

下面举一个简单的例子来说明核函数和映射函数的关系：

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

此时对偶问题的目标函数成为：

而：

3.4 正定核

上图最后提到的步骤详细过程请见《统计学习方法-李航》的P118-121部分。下面是正定核函数的充要条件定理：

正定核的等价定义如下：

有：

3.5 常见核函数

下面分别是多项式核函数与高斯核函数：

3.6 非线性支持向量分类机

如上所述，利用核技巧，可以将线性分类的学习方法应用到非线性分类问题中去。将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数。

下面是非线性支持向量机的定义：

下面叙述非线性支持向量机学习算法：

3.7 序列最小最优化算法

本节讨论支持向量机学习的实现问题。我们知道，支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致无法使用。

下面是序列最小最优化(sequential minimal optimization，SMO)算法：

SMO算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件(Karush-Kuhn-Tucker conditions)，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。注意：

整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。这两个步骤详细过程请见《统计学习方法-李航》的P125-131部分。

END