SVM-从线性可分到线性不可分

本文为博主原创文章,请勿随意转载。如需转载请联系博主或评论。

支持向量机为二分类模型,由简至繁,可以分为三类:

种类 数据集 学习准则
硬间隔支持向量机(线性可分支持向量机) 线性可分 硬间隔最大化
软间隔支持向量机 近似线性可分 软间隔最大化
非线性支持向量机 线性不可分 核技巧+软间隔最大化

首先从整体上给出支持向量机从问题建模到求解的整个过程:

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

给定训练数据集:

其中,$x_i\in \mathcal X=R^n$,$y_i\in \mathcal Y=\{-1,+1\}$,$i=1,2,…,N$。假设该数据集是线性可分的。

当训练数据集线性可分时,会存在无穷多个分离超平面可以将两类数据分开。例如感知机算法,不同的初始点会得到不同的分离超平面。

为了解决分离超平面不确定的问题,线性可分支持向量机通过间隔最大化来求得最优的、唯一的超平面。

线性可分支持向量机确定的超平面为:

分类决策函数的形式为:

函数间隔和几何间隔

对于属于同一类的两个样本来说,当这两个样本距离分离超平面的距离不同时,模型所给出的类别预测的确信度也应该不同,离分离超平面较远的那个样本点的预测结果的确信度应该更高一些,而离的较近的那个的确信度就相对较低。

那么,如何度量这些样本点的分类确信度呢?

一种比较常用的方法就是使用该样本点离分离超平面的距离作为度量的准则。

首先给出函数间隔的定义:

image-20200322164739306

函数间隔可以表示分类预测的正确性和确定度。但函数间隔有个非常不好的特性,如果成比例地同时改变$w$和$b$的大小,函数间隔也会以相同的比例发生改变。但此时,对应的分离超平面并未发生变化。

此时就需要引出另一种确信度的度量方式。

空间中的一点$x_i$到超平面$w^Tx_i+b$的距离为:

当样本点$(x_i,y_i)$被超平面正确分类时,点$x_i$到超平面的距离可以转换为:

由此引出几何间隔的定义:

image-20200322165635237

实际上,几何间隔就是所有样本距离超平面的距离的最小值。

间隔最大化

支持向量机学习的基本思路是寻找能够将训练数据集正确分类同时几何间隔最大的分离超平面。

几何间隔最大意味着以充分大的确信度对训练数据进行分类。不仅能够将所有样本正确分类,同时对于距离超平面最近的样本点也有着足够大的确信度。

求解具有最大几何间隔的分离超平面的问题可以表示为如下的约束问题:

约束条件表示超平面关于每个样本点的几何间隔至少是$\gamma$,该优化函数的目标是使得这一几何间隔尽可能地大。

依据函数间隔和几何间隔的关系,将上述问题改写为:

对$w,b$成比例缩放任意的倍数都不影响上述约束最优化问题的结果。既然如此,直接通过缩放$w,b$使得$\hat \gamma=1$。

很多人不明白为什么是1,这就是1的由来,是由函数间隔和几何间隔的关系推导而来的。

代入上式,并将$\max_{w,b}\frac{1}{||w||}$替换为$\min_{w,b}\frac{1}{2}||w||^2$,得到如下的优化问题:

上述约束优化问题是一个凸二次优化问题(目标函数为二次,不等式约束为线性)。

至此,我们就将求解具有最大间隔的分离超平面的问题转换为约束优化问题。通过求解该约束优化问题就可以得到具有最大间隔的分离超平面$w^\cdot x+b^=0$,进而得到分类决策函数$f(x)=sign(w^\cdot x+b^=0)$,即线性可分支持向量机。后续的软间隔支持向量机和非线性支持向量机都是在该问题的基础上进行改进得到的。

定理:若训练数据集线形可分,则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

对于训练集中的样本,如果满足:

则称该样本实例为支持向量(support vector)。

如下图所示,落在分离超平面两侧的两个超平面$H_1,H_2$上的点就是支持向量。两个超平面间的间隔大小为$\frac{2}{||w||}$。

image-20200322175858665

学习的对偶算法

将原始约束优化问题转换为对偶问题

通过前面的推导,我们已经将求解使得在训练数据集上几何间隔最大的分离超平面的问题转换为约束优化问题:

既然该问题是一个约束优化问题,那么自然而然可以首先使用拉格朗日乘数法将上述问题转换为拉格朗日函数:

其中,拉格朗日乘子$\alpha_i \ge 0$。

那么,原始的约束优化问题可以等价为如下的无约束优化问题:

根据拉格朗日对偶性,上述问题的对偶问题为:

由于原始的优化问题为凸二次规划问题,因此,原问题和对偶问题满足强对偶性,可以通过求解对偶问题来得到原始问题的解

求解对偶问题

求解内部最小化问题

在求解内部最小化问题时,先假定$\alpha$不变。此时求出的$w,b$是关于$\alpha$的函数。

求解内部最小化问题的方式非常简单,直接将拉格朗日函数$L(w,b,\alpha)$分别关于$w,b$求偏导数,并令偏导数为0:

那么:

将上述两式代入拉格朗日函数中的:

上式即为内部最小化问题的最优解:

即:

将其带入对偶问题中:

极大转换为极小,对偶问题转换为:

通过求解上述问题可以求得$\alpha^$,进而求得原始最优化问题的解$w^,b^$。那么,假设已经求得了$\alpha^$,该如何才能得到$w^,b^$。

这里就要用到$KKT$条件。

借助KKT条件由对偶问题的解求原问题的解

由于原约束优化问题为凸二次规划问题,所以满足强对偶性,进而满足$KKT$条件,借助$KKT$条件就可以推导出原问题的解和对偶问题的解的关系。

由$KKT$条件可以得到如下等式和不等式:

由$\nabla_wL(w^,b^,\alpha^)=w^-\sum_{i=1}^N \alpha^* y_i x_i=0 $求得:

而为了求得$b^$与$\alpha^$的关系,首先观察互补松弛条件和其他两个条件:

由于数据集是线性可分的,对于那些使得$1-y_i(w^x_i+b^)< 0,\ \ i=1,2,…,N $的样本点$(x_i,y_i)$,为了使其满足互补松弛条件:

则其对应的$\alpha_i$必须等于0。

假设所有的样本点都使得$1-y_i(w^x_i+b^)< 0$,则所有的$\alpha_i=0$,进而导致:

这显然无法构成原问题的解。因而,必然存在样本点使得$1-y_i(w^x_i+b^)=0$,对上式进行变换:

代入$w^=\sum_{i=1}^N \alpha^ y_i x_i$,得到$b^*$:

最终:

进而得到最终的决策函数:

观察最终求得的$w^, b^$发现,这两个值是训练数据的线性组合,且由于互补松弛条件的存在,只有位于两个分隔超平面上的样本(支持向量)的权重不为零。

线性可分支持向量机学习算法总结

image-20200322194926794

对于线性可分数据集,线性可分支持向量机是存在且唯一的。但对于线性不可分的数据集,就无法适用。

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

在讨论软间隔支持向量机之前,再来看一下硬间隔支持向量机的原始优化问题:

如果数据集是线性可分的,那么对于所有样本,上述问题中的约束条件均成立。但对于线性不可分的数据集,就无法使得所有的不等式约束都成立。

在给定的训练数据集中,存在一些特异点,将这些特异点去除后剩下的样本点组成的集合是线性可分的。

这些特异点是无法满足函数间隔大于等于1的条件的。为了解决该问题,可以放松约束条件的要求,对于每一个样本,都引入一个松弛变量$\xi_i$,只需要函数间隔加上松弛变量$\xi_i$之后大于等于1即可。即将约束条件放松为:

同时,在优化目标中加入对这些点的惩罚。这样一来,对硬间隔的优化问题进行改造,可得软间隔支持向量机的原始优化问题:

上述优化问题的含义有两点:

  • 使间隔尽可能大;
  • 使误分类的点尽可能少。

软间隔支持向量机的原始优化问题是一个凸二次规划问题,因而必然可以找到使问题最小的解$(w,b,\xi)$,但其中$w$的解是唯一的,但$b$的解可能不唯一,而是一个区间。

通过求解上述问题得到$w^,b^$后,就可以得到软间隔支持向量机的分离超平面为:

决策函数为:

学习的对偶算法

在上一小节中已经得到了软间隔支持向量机的原始问题。该问题为凸二次规划问题,因而满足强对偶性。可以通过求解其对偶问题来得到原始问题的解。

将原始问题转换为对偶问题

写出对偶问题并进行求解的过程与硬间隔支持向量机的过程一样,都是首先利用拉格朗日乘数法写出拉格朗日函数:

再在拉格朗日函数的基础上写出原始问题的等价优化问题($\min- \max$问题),接着写出对偶形式的$\max-\min$问题:

求解对偶问题

求解内部极小化问题

首先利用令偏导数为0的方式求解对偶问题内部的$\min$问题来求得$w,b,\xi$:

将上述结果代入对偶问题中,得:

通过求解上述问题可以求得对偶问题的解$\alpha$。进而利用强对偶性得到原问题的解。

使用KKT条件得到原问题的解

和求解硬间隔支持向量机一样,写出原始问题的$KKT$条件,则可求得:

软间隔支持向量机的求解过程

image-20200323165032350

image-20200323165046375

软间隔支持向量机的支持向量

在硬间隔支持向量机中,支持向量对应$\alpha_i\ge0$的点,这些点都位于间隔边界上。同样,在软间隔支持向量机中,支持向量同样对应$\alpha_i\ge0$的样本点,但由于互补松弛条件更为复杂,所以支持向量的分布也更为复杂。

$KKT$条件中的互补松弛条件为:

同时:

当$\alpha_i< C,\xi_i=0$,则支持向量$x_i$在间隔边界上;

当$\alpha_i=C,0<\xi_i<1$,则分类正确,支持向量$x_i$在分离超平面和间隔平面之间;

当$\alpha_i=C,\xi_i=1$,支持向量$x_i$在分离超平面上;

当$\alpha_i=C,\xi_i>1$,支持向量$x_i$在分类超平面误分的一侧。

支持向量的分布情况正如下图所示:

image-20200323174351163

软间隔支持向量机的求解可以等价为损失函数为合页损失的优化问题。

image-20200323175520687

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

非线性可分到线性可分

在上文中介绍了硬间隔支持向量机和软间隔支持向量机,这两种支持向量机分别适用于线性可分数据集和带有少量不线性可分点的数据集。但当数据集完全为非线性可分时,上述两种支持向量机就不再适用,那么该如何解决这一问题?

一般情况下,当数据集非线性可分时,可以采用如下的两种方法:

  • 从模型角度进行改进:例如单层感知机到多层感知机,再到深度学习的演化就是遵循这一思路。单层感知机只适用于求解线性可分数据集,为此可以使用多层感知机,同时引入非线性变化来进行改进;

  • 借助核方法引入非线性,进而将非线性可分数据转换为线性可分数据:可有如下例子:

线性可分 一点点错误 严格线性可分
PLA(感知机学习算法) Pocket Algorithm $\phi(x)+PLA$
硬间隔SVM 软间隔SVM $\phi(x)$+硬间隔(软间隔)SVM

那么该如何理解通过引入非线性变换将非线性可分数据转换为线性可分数据呢?以异或问题为例:

对于上图中的四个点,无论如何,我们都无法找到一个超平面对其进行正确划分。此时,假设原始点坐标为$x=(x_1,x_2)$,引入非线性变换$z=(x_1,x_2,(x_1-x_2)^2)$,则可以将上述四个点转换到三维空间上,如下图所示:

可以看出,将低维空间的点映射到高维空间之后,就很容易找到一个分离超平面将四个点正确划分。

为了对支持向量机进行改进,以使其可被用于求解非线性可分问题,就需要借助上面的思想。以软间隔SVM为例,通过一系列转换,其对偶问题如下:

借助上面的思想,引入非线性映射$\phi(x)$将样本数据映射到高维空间,则对偶问题转化为:

此时就将非线性可分数据转换为线性可分数据。

但在实际应用中,往往存在如下的两个问题:

  • 我们很难正确找到非线性映射$\phi(x)$;
  • 使用$\phi(x)$将样本映射到高维空间后,特征的维度会变得非常高,甚至无限维,内积操作的计算复杂度过高。

那么,该如何解决上述两个问题?

核函数

此时就需要用到核函数。在上述的分析中,实际上我们关心的只是最终的内积$\phi(x_i) \cdot \phi(x_j)$的结果,没有必要非得求出非线性变换。那么,就可以直接找到一个函数,使得该函数的结果等于经过非线性变换和内积操作后的结果。

定义核函数如下:

则称$k(x,x’)$为核函数。

那么,如果能找出一个满足上述条件的核函数,就无需去求非线性变换,直接通过核函数就可以得到所需的内积。

非线性支持向量机

有了上述的讲解,为了将支持向量机应用于非线性数据集,实际上只需要将硬间隔支持向量机或软间隔支持向量机中有关样本内积的操作使用核函数替代即可。

以软间隔支持向量机为例,引入核函数之后,其对偶问题转换为:

通过求解对偶问题得到各个参数的值后,得到决策函数为:

序列最小最优化算法

在之前的3节内容中,分别介绍了硬间隔支持向量机、软间隔支持向量机和非线性支持向量机。这三种支持向量机的求解过程都是一样的:

  • 通过求解原始凸二次规划的对偶问题得到拉格朗日乘数$\alpha$的值;
  • 将$\alpha$代入到利用$KKT$条件推导出的$w^, b^$的表达式中求得$w^$和$b^$。

可以看出,求解支持向量机的重点就是求解关于拉格朗日乘数$\alpha$的对偶问题。本节要研究的就是求解该问题的方法,序列最小最优化算法(sequential minimal optimization, SMO)。

SMO算法

在非线形支持向量机中,求解拉格朗日乘数的对偶问题的形式为:

我们要求解的就是上述约束优化问题。针对该问题,SMO算法采用的是一种启发式的优化算法。通过将上述凸二次规划问题转换为一系列的子问题进行求解。

SMO算法所依据的核心是,如果所有变量$\alpha$的解都满足优化问题的KKT条件,那么这些变量就是该优化问题的解。

基于此准则,SMO算法每次从所有的待求解变量中选择两个变量(固定其他变量保持不变)。针对这两个变量求解一个二次规划问题。通过反复选择两个变量,最终使得所有的变量都满足KKT条件,进而找到了原问题的解。

那么,就可以将SMO算法划分为如下两步:

  • 选取两个变量$\alpha_1,\alpha_j$;
  • 求解由这两个变量构成的二次优化问题。

重复上述两步,直到所有的变量都满足$KKT$条件,或者达到预设的终止条件。

求解两个变量的二次优化问题

不失一般性,选择两个变量$\alpha_1,\alpha_2$,其他变量都固定,则对偶问题可以转换为:

首先对约束条件进行整合:

对于选中的两个变量,如果求得了其中一个,便可以求得另一个。因而,该问题可以转换为单变量的优化问题。这里选择$\alpha_2$。

假设两个变量的初始值为$\alpha_1^{old},\alpha_2^{old}$,对$\alpha_2$的约束条件进行整合后满足$L\le\alpha_2\le H$

  • 当$y_1=y_2$时:$L=\max(0,\alpha_2^{old}+\alpha_1^{old}-C),H=min(C,\alpha_2^{old}+\alpha_1^{old})$;
  • 当$y_1\ne y_2$时:$L=\max(0,\alpha_2^{old}-\alpha_1^{old}),H=\min(C,C+\alpha_2^{old}-\alpha_1^{old})$。

上述两个式子相当于限定了$\alpha_2$的范围。

接着,为了将优化问题转换为只关于$\alpha_2$的问题,借助约束条件,将$\alpha_1$表示为$\alpha_2$的形式。之后,使用转换后的问题对$\alpha_2$求偏导数并令其等于0,则可求得$\alpha_2$的值。接着,再使用上述的两个范围对$\alpha_2$取值进行限定,便可以得到最终的$\alpha_2$的值。

最终求得的值的公式如下:

image-20200324191704484

其中,$E_i$为函数$g(x)$对输入$x_i$的预测值与真实输出$y_i$的误差。

上面的定理给出了一种从$\alpha_2^{old}$计算$\alpha_2^{new}$的方法。更新得到$\alpha_2^{new}$之后,就可以接着计算得到$\alpha_1^{new}$。可以看出,上述求解过程是求解析解的过程。

选择两个变量的方法

选择两个变量的方法被划分为内层和外层。

  • 选择第一个变量:第一个变量的选取准则是,在训练样本中选择违反$KKT$条件最严重的点;
  • 选择第二个变量:在第一个变量选定以后,选择第二个变量。第二个变量的选择准则是希望能使$\alpha_2$有足够大的变化。

SMO算法

image-20200324194107684

SMO算法最终求得的$\alpha_i$是近似解。

参考