机器学习7 非线性SVM

前言

在上节中，我们假设训练样本是线性可分的，然而在现实任务中，训练样本很可能是非线性的。本节将要介绍如何利用SVM进行非线性数据分类。

核函数

在之前的线性模型中，当面临非线性数据时，我们利用多项式回归来解决。这其中有一个重要的思想：将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

 上图样本在二维空间内显然不是线性可分的，将其映射到三维空间：

这时就存在合适的划分超平面。幸运的是，如果原始空间是有限维（特征数有限），那么一定存在一个高维特征空间使样本可分。

令z表示x映射后的特征向量，则在特征空间划分超平面所对应的模型为：

SVM的基本型变为：

对偶问题变为：

求解上式需要计算$z_{i}^{T}z_{j}$，这是样本x 映射到高维空间后求内积。由于特征空间维数很高，甚至可能无穷多维，直接计算很难，为例避开这个障碍，引入了核函数概念。设想这样一个函数：
$k(x_{i},x_{j})=z_{i}^{T}z_{j}$

即在特征空间内zi与zj的内积等于在原始空间内xi和xj通过函数k计算的结果。

有点抽象，以上面的非线性数据为例：

数据分布为两个椭圆的形状，这样的数据本身就是不可分的。不难发现，这两个半径不同的椭圆是加上了少量的噪音生成得到的。所以，一个理想的分界应该也是一个椭圆，而不是一个直线。如果用X1和X2来表示这个二维平面的两个坐标的话，我们知道这个分界椭圆可以写为：

这个方程就是高中学过的椭圆一般方程。注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为：

那么，显然我们可以将这个分界的椭圆方程写成如下形式：

这个关于新的坐标Z1,Z2,Z3,Z4,Z5的方程，就是一个超平面方程，它的维度是5。也就是说，如果我们做一个映射 ϕ : 二维 → 五维，将 X1,X2按照上面的规则映射为 Z1,Z2,··· ,Z5，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。

我们举个简单的计算例子，现在假设已知的映射函数为：

这个是一个从2维映射到5维的例子。如果没有使用核函数，我们需要先结算映射后的结果，然后再进行内积运算。那么对于两个向量a1=(x1,x2)和a2=(y1,y2)有：

另外，如果我们不进行映射计算，直接运算下面的公式：

你会发现，这两个公式的计算结果是相同的。区别在于什么呢？

• 一个是根据映射函数，映射到高维空间中，然后再根据内积的公式进行计算，计算量大；
• 另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果，计算量小。

其实，在这个例子中，核函数就是：

我们通过k(x1,x2)的低维运算得到了先映射再内积的高维运算的结果，这就是核函数的神奇之处，它有效减少了我们的计算量。在这个例子中，我们对一个2维空间做映射，选择的新的空间是原始空间的所有一阶和二阶的组合，得到了5维的新空间；如果原始空间是3维的，那么我们会得到19维的新空间，这个数目是呈爆炸性增长的。如果我们使用ϕ(·)做映射计算，难度非常大，而且如果遇到无穷维的情况，就根本无从计算了。所以使用核函数进行计算是非常有必要的。

利用核函数，我们的对偶问题重写为：

求解可得：

刚刚的例子是非常简单的，我们可以手动构造出来对应映射的核函数出来，如果对于任意一个映射，要构造出对应的核函数就很困难了。因此，通常，人们会从一些常用的核函数中进行选择，根据问题和数据的不同，选择不同的参数，得到不同的核函数

1）线性核 最简单的核函数

优点：计算速度快，容易解释模型意义。缺点：数据必须线性可分

2）多项式核

优点：能处理非线性数据 缺点：参数多，当Q阶数变大时会出现组合爆炸

3）高斯核 普遍使用

优点：参数少，功能强大能映射到无限维 缺点：难以解释模型意义，计算速度比线性核慢，容易过拟合。

硬间隔与软间隔

在前面的讨论中，我们一直假定训练样本无论在样本空间还是在特征空间都是线性可分的，即存在一个超平面能将不同类的样本完全划分开，然而，在现实任务中，往往很难确定合适的核函数使得训练样本在特征空间中线性可分，退一步说，即便恰好找到了某个核函数使训练集在样本空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合造成的。

                                        

左图分类时存在分类错误的，而在右图使用核函数数据完全可分。但我们会选择右图吗？

缓解右图的一个办法就是允许支持向量机在一些样本上出错，为此，引入了“软间隔”概念。

前面介绍的SVM是要求所有样本都必须划分正确，这称为硬间隔；而软间隔是允许某些样本分类错误。在这时，我们的目标变为尽可能使间隔最大和分类错误的个数之间找到动态平衡。

我们来推导目标函数：

允许存在分类错误：

之前的硬间隔：

两者结合：

把约束写在一起：

用C（C>0）来控制间隔宽度和违例数的平衡。当C趋于无穷大时，会迫使所有样本满足：

等价于硬间隔；当C取有限值时，会允许有一些样本不满足约束。

上述

函数性质不好，非凸不连续，通常用其他一些函数进行替代，称为“替代损失”，常用替代损失函数有：hinge损失、指数损失、对数损失。

接着，我们引“松弛变量”来代替分类错误数：

这就是常用的“软间隔支持向量机”基本型。每个样本点都有一个对应的松弛变量，用来该样本不满足约束的程度。

求解方法类似于硬间隔分类。不再赘述。

支持向量回归

前面说过，SVM算法非常全面：它不仅支持线性和非线性分类，而且还支持线性和非线性回归。原理在于：不再是尝试拟合两个类别之间可能的最大间隔同时限制间隔违例，而是让尽可能多的样本位于间隔内，同时限制间隔违例（不在间隔内的样本）。

如上图所示：假设我们能容忍f(x)与y之间最多有$\epsilon$的偏差，即仅当f(x)与y之间的差别绝对值大于$\epsilon$时才计算损失。这就构成了以f(x)为中心，宽度为2$\epsilon$的间隔带，若样本落入间隔带中，则被认为预测正确。

于是，支持向量回归的模型为：

其中C为正则化常数，L为$\epsilon$-不敏感损失函数：

引入松弛变量（两侧松弛程度可能不同）：

求解方法类似于支持向量机，同样可以利用核技巧。

小结

这两节主要介绍了SVM的工作原理，刚接触机器学习时很难理解，需要反复看加深理解。下节将要介绍SVM的使用。

参考资料

【1】机器学习实战教程（九）   https://cuijiahua.com/blog/2017/11/ml_9_svm_1.html

【2】机器学习技法  林轩田  https://www.bilibili.com/video/av12469267?from=search&seid=16189317168232782932

【3】机器学习 周志华