SVM系列第九讲--核方法

1、线性可分到线性不可分

前面我们介绍了线性情况下的支持向量机，它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过，由于是线性方法，所以对非线性的数据就没有办法处理了。例如图中的两类数据，分别分布为两个圆圈的形状，不论是任何高级的分类器，只要它是线性的，就没法处理，SVM 也不行。因为这样的数据本身就是线性不可分的。

线性不可分

上面的数据集生成它的时候就是用两个半径不同的圆圈加上了少量的噪音得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。那么上面的两条二次曲线由下面的公式产生：

二次曲线
我们想要在二维空间中找到一条线将数据分开，是不可能的，但假如我们做如下的变换： 令Z1=X1^2, Z2=X2^2, Z3=X2,我们就能把现在的数据点从二维空间中映射到高维空间中，那么上面的方程在映射后可以转换为如下的形式（5应该改为3）：

不难看出，在映射之后我们的数据变成线性可分的了，如果将三维空间中的数据点画出，它大概是下面的样子，我们可以看到，能够找到一个超平面，将两类数据点准确分开：

现在让我们再回到 SVM 的情形，假设原始的数据时非线性的，我们通过一个映射 ϕ(⋅) 将其映射到一个高维空间中，数据变得线性可分了，这个时候，我们就可以使用原来的推导来进行计算，只是所有的推导现在是在新的空间，而不是原始空间中进行。当然，推导过程也并不是可以简单地直接类比的，例如，原本我们要求超平面的法向量 w ，但是如果映射之后得到的新空间的维度是无穷维的（确实会出现这样的情况，比如后面会提到的 Gaussian Kernel ），要表示一个无穷维的向量描述起来就比较麻烦。于是我们不妨先忽略过这些细节，直接从最终的结论来分析，回忆一下，我们上一次得到的最终的分类函数是这样的：

原分类函数

现在则是在映射过后的空间，即：

新分类函数
而其中的 α 也是通过求解如下 dual 问题而得到的：

2、核函数(Kernel Function)

这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射 ϕ(⋅) ，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。其实刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给 ϕ(⋅) 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要 Kernel 出马了。
假设我们现在的二次曲线的方程为：

此时我们需要构造一个五维空间进行映射，令Z1=X1, Z2=X1^2, Z3=X2, Z4=X2^2, Z5=X1X2，假设此时有两个数据点：x1=(η1,η2)T 和 x2=(ξ1,ξ2)T ，而 ϕ(⋅) 即是到前面说的五维空间的映射，因此映射过后的内积为：

映射内积
另外，我们注意到有这么一个公式：

二者有很多相似的地方，实际上，我们只要把某几个维度线性缩放一下，然后再加上一个常数维度，具体来说，如果将映射的方式改变一下，变为下面的形式，再计算内积的时候，得到的结构就与上面的式子相同：

可以看到上面两种方法得到了同样的结果，但区别是什么呢，一个是先将低维空间中的数据点映射到了高维空间中，另一种方式是直接在原来的地位空间中进行运算，对运算结果又进行了一定的处理。回忆刚才提到的映射的维度爆炸，在前一种方法已经无法计算的情况下，后一种方法却依旧能从容处理，甚至是无穷维度的情况也没有问题。

我们把这里的计算两个向量在映射过后的空间中的内积的函数叫做核函数 (Kernel Function) ，例如，在刚才的例子中，我们的核函数为：

核函数

核函数能简化映射空间中的内积运算——刚好“碰巧”的是，在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们写出来的式子，现在我们的分类函数为：

而求解α的规划问题变为：

这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的，实在是一件非常美妙的事情！当然，因为我们这里的例子非常简单，所以我可以手工构造出对应于 φ(⋅) 的核函数出来，如果对于任意一个映射，想要构造出对应的核函数就很困难了。

最理想的情况下，我们希望知道数据的具体形状和分布，从而得到一个刚好可以将数据映射成线性可分的 ϕ(⋅) ，然后通过这个 ϕ(⋅) 得出对应的 κ(⋅,⋅) 进行内积计算。然而，第二步通常是非常困难甚至完全没法做的。不过，由于第一步也是几乎无法做到，因为对于任意的数据分析其形状找到合适的映射本身就不是什么容易的事情，所以，人们通常都是“胡乱”选择映射的，所以，根本没有必要精确地找出对应于映射的那个核函数，而只需要“胡乱”选择一个核函数即可——我们知道它对应了某个映射，虽然我们不知道这个映射具体是什么。由于我们的计算只需要核函数即可，所以我们也并不关心也没有必要求出所对应的映射的具体形式。
当然，说是“胡乱”选择，其实是夸张的说法，通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），例如：

常用核函数

最后，总结一下：对于非线性的情况，SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。由于核函数的优良品质，这样的非线性扩展在计算量上并没有比原来复杂多少，这一点是非常难得的。当然，这要归功于核方法——除了 SVM 之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。

3、核函数的选择问题

之前在面试今日头条算法工程师的时候，被问到了常用的核函数如何选择的问题，根据网上的答案，总结如下：
在选取核函数解决实际问题时，通常采用的方法有：一是利用专家的先验知识预先选定核函数；二是采用Cross-Validation方法，即在进行核函数选取时，分别试用不同的核函数，归纳误差最小的核函数就是最好的核函数．如针对傅立叶核、RBF核，结合信号处理问题中的函数回归问题，通过仿真实验，对比分析了在相同数据条件下，采用傅立叶核的SVM要比采用RBF核的SVM误差小很多。

在我的研究做实验过程中，最常用的是Linear核与RBF核。
1）. Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。
2）. RBF核（高斯核）：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。我个人的体会是：使用libsvm，默认参数，RBF核比Linear核效果稍差。通过进行大量参数的尝试，一般能找到比linear核更好的效果。