入门支持向量机3：巧妙的Kernel Trick

vlambda
2020-02-17

入门支持向量机3：巧妙的Kernel Trick

《》

0x00 前言

之前介绍的SVM，本质上就是个线性分类器，保证Margin最大。实际上都是线性SVM，包括Soft Margin解决的也不是线性不可分问题，而是解决在线性可分问题下存在噪点、异常点等问题。那么如何解决一个线性不可分问题呢？

本篇文章从多项式解决非线性问题开始，一步一步地介绍SVM算法的精妙之处，看看数学家是如何通过“把戏”来解决问题的。

0x01 使用多项式处理非线性数据

处理非线性数据最典型的思路就是使用多项式的方式：扩充原本数据，制造新的多项式特征。

准备数据：

import numpy as npimport matplotlib.pyplot as pltfrom sklearn import datasets
X, y = datasets.make_moons(noise=0.20,random_state=123)
plt.scatter(X[y==0,0], X[y==0,1])plt.scatter(X[y==1,0], X[y==1,1])plt.show()

下面使用多项式特征，用SVM算法进行分类：

from sklearn.preprocessing import PolynomialFeatures, StandardScalerfrom sklearn.svm import LinearSVCfrom sklearn.pipeline import Pipeline
def PolynomialSVC(degree, C=1.0): return Pipeline([ ("poly", PolynomialFeatures(degree=degree)), ("std_scaler", StandardScaler()), ("linearSVC", LinearSVC(C=C)) ])
poly_svc = PolynomialSVC(degree=3)poly_svc.fit(X,y)

然后我们使用之前用到的plot_decision_boundary方法绘制决策边界：

入门支持向量机3：巧妙的Kernel Trick

通过多项式的方式，让决策边界不再是一条直线了，而是一条曲线。

对于SVM算法来说，可以不使用多项式PolynomialFeatures的方式。而是使用一种巧妙的方法。

0x02 SVM解决非线性问题

SVM算法如何解决线性不可分问题？下面通过两个例子进行展示。

2.1 例子1

入门支持向量机3：巧妙的Kernel Trick

上面的图片有两种示例情况。对于最上面的情形来说，是线性可分的一维数据，在红蓝之间找到一个阈值，即可将二者分开（外面套着圆圈的点是支持向量）。

第二种情况就有所不同了，红-蓝-红，不管如何选择阈值，都不能把它分开。

SVM使用了一种非常巧妙的思路：一维空间不能解决，投影到二维空间。空间中的分布变成了如下的样子：

入门支持向量机3：巧妙的Kernel Trick

横坐标是，纵坐标是，相当于引入了一个新的维度。此时，就可以用一条线将其分开。

在原始空间中无法使用线性分类器，就将其映射到另一空间（Feature Space）当中，使其容易分。

2.2 例子2

在下面的样本数据集中，红色点在中心，蓝色点在四周，所以一根线是肯定分不开的。

入门支持向量机3：巧妙的Kernel Trick

如果我们一定要在当前空间将其分开的话，可以找到一个圆圈作为决策边界，将其分离：

入门支持向量机3：巧妙的Kernel Trick

那么如何通过坐标变化，将其映射到新的空间中，得到线性可分的形式呢？将横坐标变为纵坐标变为，这样数据在空间分布中如下图所示：

入门支持向量机3：巧妙的Kernel Trick

我们可以想象，有一个内功深厚的武林高手，面对桌子上的一堆混在一起的绿豆和红豆（数据点），一掌拍在桌子上，用内力将其逼到空中（从低维空间映射到高维空间），再它们在空中分散的时候（在高维空间上线性可分），然后再一刀将其分开（决策平面）。如下图：

入门支持向量机3：巧妙的Kernel Trick

0x03 认识核函数

现在我们已经知道，可以将数据从原始空间映射到Feature Space中去，就可以解决原本的线性不可分问题。那么如何做映射呢？

其实我们并不用特意地去设计映射（实际上我们也很难在高维空间去设计映射），而是使用固定的几种映射方法即可。这些映射方法就是核函数。

核函数本身不是SVM特有的一种技巧，事实上，只要我们在求解最优化问题中，存在，都可以将其转换为，下面让我们具体学习。

3.1 多项式核函数

下面我们介绍一种映射方法：：

入门支持向量机3：巧妙的Kernel Trick

这种映射方法实际上是将维度升上去，映射到一个非常高的维度（大约有维）。

我们知道，高维数据的运算是十分复杂的，那将数据升维的好处是是什么呢？又该如何计算呢？其实这其中就有SVM算法的精妙之处。

在《》中3.1小节，求解有条件限制的最优化问题的过程中最后求解时介绍过：两个向量做内积是SVM运算的精髓。

在原始空间中，两个向量做内积映射到高维空间中则变成。展开后相乘得到：

合并之后得到很复杂的表达式：

但是，数学家们神奇地发现（具体怎么发现的，我们不用知道...），存在这样一个表达式：，它的展开式居然也是上面的表达式，这就是SVM中最重要的一个特性：

这就是SVM算法的精妙之处：数学家设计出一种巧妙的数学变换，使高维空间的操作等价于低维空间的操作，解决了高维空间中的计算量问题，大大减少了运算量。

数据从低维映射到高维以后，问题的可分析性会增加，会变得更容易；但是高维空间的运算量太大，引入了Kernel Trick。

上面就是所谓的多项式核函数。可以拓展为一般形式：

其中为多项式的阶数，在sklearn中，degree的默认参数为3.

3.2 高斯核函数

高斯核函数是SVM算法中使用最多的核函数，也被称作是RBF核（Radial Basis Function Kernel）：

其中与高斯函数的成反比，即越大，高斯分布越窄；越小，高斯分布越宽。表示向量的范数，可以理解为向量的模。

高斯核函数的数据映射是非常复杂的，其本质是将一个样本点映射到一个无穷维的特征空间。我们只需要关注映射后的结果即可。

下面看看高斯核函数本质上是在做什么事？现在先对核函数进行一个改变，将原本的中的值替换成两个固定点。我们称这两个特殊的点为地标landmark。

高斯核函数升维的过程就是对于原本的每个x值，如果有两个landmark的话，就将其维为二维样本点，每个样本的取值是高斯核函数的值：

通过这样的映射，就可以将线性不可分数据变得线性可分。

我们再返过来看高斯核函数：

我们认为就是地标点landmark的话，那么实际上在高斯核函数中，对于每一个数据点都是landmark，有多少样本，就有多少地标点。将m*n的数据映射成m*m的数据。

0x04 SVM最终优化函数

通过这三章的学习，我们循序渐进地推导出了SVM的优化目标函数。下面我们来梳理一下：

SVM本质就是求解下面最优化问题：

为了求解有条件的最优化问题，转换为下面的形式：

要注意，上面的形式是求最大值max，当然，如果不习惯，也可以转换成最小值min。

然后引入核函数进行替换：

其中。但是实际上我们从来不用计算，直接用不同的核函数代入，如：

0xFF 总结

SVM算法作为数据挖掘领域十大经典算法之一，其中设计了很多精妙的思想。在这篇文章中，我们首先回顾了如何使用多项式来解决非线性问题。但在SVM中则使用了更加巧妙的方法。

在低维空间中线性不可能的数据，可以转化成高维度数据，使得数据更具有分析性；然后使用核函数，其在高维空间上的运算等价于低维空间，从而解决了运算量大的问题。数学家玩起了把戏，其中巧妙的数学变换令人惊叹不已，故而本篇文章命名为Kernel Trick。

vlambda博客
学习文章列表