机器学习算法之SVM（三）

标题：

非线性

核技巧

核函数

常用核函数

多项式核函数

高斯核函数

非线性支持向量机算法总览

算法

1.非线性

两篇关于支持向量机的讨论，将支持向量机从感知机引申到硬间隔最大化支持向量机，又从硬间隔延伸到软间隔，然而直到本篇，我们才真正讨论到让支持向量机辉煌一时的核心算法，也即是通过支持向量机对非线性可分数据划分的方法，事实上前面我们讨论的支持向量机一直是对线性可分数据集进行划分的支持向量机，我们可以先把它们划分到对“线性支持向量机”的讨论，因为接下来，我们要讨论的才是针对“非线性”的支持向量机算法。

回忆前面第一篇关于支持向量机的推文，当时我们给出了一个像下面这样的数据集：

我们知道，线性分类器提供给我们的直线划分方式对这样的数据集是无能为力的，但如果，我们能够将这部分数据集投影到一个新空间，让其在新空间上可分，那么，作用于新空间上的线性分类器或许就能将其分开了。

这么说可能会显得比较模糊，我们可以继续看这个例子，如果我们不再以“x”和“y”作为上面这组数据的坐标轴，而是以“x的平方”和“y的平方”作为坐标轴的话，我们会得到一幅这样的数据集图像：

而这幅图上的数据集显然是能够通过线性分类器分开的。

2.核技巧

我们可以先从上面举得数据集例子中归纳出划分非线性可分数据的两个步骤：

将原空间的数据通过一个变换映射到新空间

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

我们先简单讨论一下在上例中进行“变换”的形式：

设原空间为X⊂R2,x=(x(1),x(2))T∈X，新空间为Z⊂R2,z=(z(1),z(2))T∈Z，我们定义从原空间到新空间的变换（映射）为：

经过变换z=Φ(x)，原空间X⊂R2变换为新空间z⊂R2，原空间中的点也相应地变换为新空间中的点，原空间中的椭圆：

也变换成新空间中的直线：

从而将原本线性不可分的数据划分出来。

a.核函数

但问题是，我们不可能对于任何数据集都将其特征“平方”然后再画超平面作分离，因为事实上我们上面举得数据集例子能够在作“平方”变换后分开仅仅是因为其分布形式恰好是一个在原空间上的椭圆能够分开的，但这不代表所有的非线性数据集都能用椭圆分开，换言之，不是所有的数据集都是对其特征平方就能够完美分开的。

那我们有没有一种“万能”的映射方式，能让各种千奇百怪的数据集都被投射到一个能够被“一条直线”（超平面）分开的空间上呢？

有，也没有。

可能有的pong友觉得我在扯淡了，什么叫“有也没有”，那到底有还是没有？其实，把一个数据集投射至新空间上的“万能”映射是存在的，像是对于上面我们那个有两个特征的数据集，如果我们将原本的特征“x1”和“x2”投射到一个拥有这两个特征一阶和二阶的所有组合特征的新空间上，那么理论上在这个新空间上就可以对所有原空间是二维特征的数据集进行划分，这个新空间的维数为5，它的坐标轴如下：

也可以理解为，我们以这些特征构造的假设函数：

可以构造出能够划分所有二维的可分数据集的分类边界。同样，对于三维数据集，也只需要找到特征一，二，三阶的所有组合就可以划分所有的三维可分数据集，以此类推，四维，五维……SVM仿佛一下子踏上了“模生”的巅峰。

但是，现实往往是残酷的。

如果有pong友了解过机器学习的一些其它内容，那你可能听说过一个结合“科幻”与“魔幻”的机器学习名词——“维数诅咒”。这个略带中二气息的词描述的是所有机器学习方法共同面临的严重障碍——即是在高维情形下所有的机器学习方法都很难都将体现出计算距离困难，面临的样本稀疏等等等等一系列因高维带来的巨大难题，换言之，“算力”不足。

而这个问题在我们的“映射”中也存在，正如我们所说，我们需要先把非线性数据集映射到一个高维空间中来进行线性划分，像是二维划到五维，但是随着数据集的特征增加，这个被划分到的“高维”是爆炸增长的。对于一个三维数据集，其投射的高维空间就已经有十九维，而我们在现实任务中常常会遇见的数据集往往有几十上百维，它再一投射，那个维数就会变成天文数字，而我们显然不希望，我们要因为划分一个不过几万条数据的数据集让自己配置了GTX1080Ti的电脑从年初跑到年末。

那我们该咋办？

其实，我们没有必要一定要把数据集投射到高维空间中再进行运算。

这个时候有的pong友可能又觉得我在扯淡了，因为我前面讲了一堆高维投射，然后又说那个东西用不上，那我前面讲那么多是为了什么？

事实上，我的意思是，我们可以通过某种方式，直接在原空间上对照着高维空间上的“情况”进行运算，而不需要先将数据集投射到高维空间上再运算。

我们可以先来看一个简单的例子，这个例子来自李航教授的《统计学习方法》：

假设输入空间是R2，我们来试着找出与其对应的特征空间H（被投射到的新空间）和映射Φ(x):R2H：

首先我们取特征空间H=R3，记x=(x(1),x(2))T，z=(z(1),z(2))T，根据下面这个式子：

我们可以取映射

从而得到

而我们又恰巧发现，支持向量机的对偶问题：

里面的目标函数只涉及输入实例与实例之间的内积（事实上决策函数、分离超平面也是一样），这个时候我们可以就可以用上面例子中发现的函数K(xi,xj)=Φ(xi)⋅Φ(xj)来代替目标函数中的内积xi⋅xj，将目标函数转变成

同样，我们又恰好可以用这个函数代替分类决策函数中的内积：

这个时候，如果我们要用支持向量机解决的是一个二维可分数据集，那么这个简单的替换就等价于通过映射函数Φ将原来的二维输入空间变换到一个新的三维特征空间，然后将输入空间中的内积xi⋅xj变换为特征空间中的内积Φ(xi)⋅Φ(xj)，并在新的特征空间里从训练样本中学习线性支持向量机。促使这一切成立的这个恰好出现的函数K(x,z)我们就称为——核函数。

核函数的标准定义是：

设X是输入空间（欧式空间Rn或离散集合），H为特征空间（希尔伯特空间H），如果存在一个从X到H的映射

使得对所有的x,z∈X，函数K(x,z)满足条件：

我们就称K(x,z)为核函数（式中Φ(x)⋅Φ(z)是Φ(x)和Φ(z)的内积）。

要注意的是，对给定的核K(x,z),特征空间H和映射函数Φ的取法并不是唯一的。不仅可以取不同的特征空间，甚至即便是在同一空间也可以取不同的映射。

以上，我们就知道了，给定核函数K(x,z)，我们就可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。模型的学习是在特征空间中隐式的进行的，不需要显式地定义特征空间和映射函数。这样的技巧我们就称之为核技巧。

3.常用核函数

我们很少自己构造一个核函数来进行运算，因为在不构造高维映射的情况下我们很难判断一个函数是否为“核函数”，这种判断核函数或称“判断正定核”的原理非常复杂（有兴趣的同学可以参考一下《统计学习方法》7.3.2正定核，或者参考其它资料），并且实现起来也很困难，因此，我们往往使用现有的核函数来解决实际中遇到的问题。

在实际应用中，核函数的选取往往依赖领域知识直接选择，而它的有效性则需要通过实验验证，我们这里仅提供两个常用的核函数作参考：

a.多项式核函数

对应的支持向量机是一个p次多项式分类器，其分类决策函数为

poly核因为参数比较多，所以擅长应付一些变化比较“剧烈”的数据集，换言之就是适合对付那种要在样本空间上画个九拐十八弯的奇形怪状的分离面才能分开的数据集。

b.高斯核函数

对应高斯径向基函数分类器（radial basis function），分类决策函数：

高斯径向核函数在机器学习框架中的参数常为“rbf”，是最常用的应对非线性数据集的核，基本上如果我们使用SVM时用线性核（Linear kernel ，其实就是不映射直接内积）发现数据不能线性可分时，下一个能采取的最优策略就是换rbf kernel，它的原理是将样本空间投射到无穷维空间作划分。

rbf的参数也更加少，至少比上面那个poly kernel少，参数少意味着模型更简单，更不容易产生过拟合，速度更快，对于比较不那么“剧烈”的样本集效果更佳。

并且，rbf核方便计算，因为其取值在[0,1]之间，poly则取值在(0,inf)，sigmoid核则在某些参数下是无效的。

但是，这并不是说明rbf核是一个可以“无脑往上a”的核，有三种情况rbf核是不适用的：

样本数量远小于特征数量的时候

样本数量核特征数量都非常大的时候

样本数量远大于特征数量的时候

这三种情况出现的时候，往往还是添加一些能让数据集线性可分的特征再换回Linear Kernel，或者利用一些其它方法会比较好。

4.非线性支持向量机算法总览

到目前为止，我们知道，要用支持向量机解决非线性分类问题，我们只需要将线性支持向量机对偶形式中的内积换成核函数即可。

于是我们就有了非线性支持向量机的定义：

从非线性分类训练集中，通过核函数与软间隔最大化或凸二次规划学习得到的分类决策函数：

K(x,z)是正定核函数。

a.算法

下面我们给出SVM算法的整体应用过程：

输入：训练集T （xi∈Rn,yi={+1,−1},i=1,...,N）

输出：分类决策函数

步骤：

1. 选取适当的核函数和适当的参数C，构造并求解最优化问题

求得最优解α∗=(α∗1,α∗2,...,α∗N)T

2.选择α∗的一个正分量

3.构造决策函数

（当K(x,z)是正定核函数时，该最优化问题是凸二次规划问题。）

5.小结

SVM可能和我们之前学习的模型稍有不同，它的原理更加抽象，并且更加复杂，实现起来也会比之前的更加困难，不仅因为其本身的内容，也因为它涉及的知识面比以往的模型更广，学习起来更费劲。另外，我们这里讨论的也仅仅是对SVM的一个初步认识，对SVM更深的内容还远远没有涉及到，如果有非常感兴趣的pong友可以参考一些专业的资料与论文，至于我们，关于SVM的内容就暂且先介绍到这里吧。

资料参考来源：

清华大学出版社 周志华 《机器学习》

清华大学出版社 李航 《统计学习方法》

cs229 lecture 3 support vector machine

A Practical Guide to Support Vector Classification（https://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf）

SVM核函数如何选取？—知乎（https://www.zhihu.com/question/21883548）

AI遇见机器学习

mltoai