Question

支持向量机SVM（3）核函数、非线性支持向量机

Answer 1

前面已经分别介绍了基于硬间隔最大化的线性可分支持向量机、基于软间隔最大化的线性支持向量机，这次来总结下使用核函数来解决非线性可分问题的非线性支持向量机。

对于非线性可分问题，我们本着简化问题的思想，自然是希望将其转化为熟悉的线性可分问题进行处理，那么怎么做呢？对于一个在样本的原始空间中不是线性可分的数据，如下左图中的红色样本点和蓝色样本点，如果想要进行分类的话，可以将数据映射到更高维的特征空间中，如果映射的合适的话，就能找到一个超平面将数据分类，如下右图所示：

这种做法是特例还是可以普遍使用的呢？《机器学习》书上说：

不过书上并没有解释原因，我们先从低维直观的理解一下，如下图所示：在一维线性不可分的数据，可以映射成在二维线性可分的，在二维线性不可分的数据，可以映射成在三维线性可分的：

在更高的维度也适用吗？实际上，这个论点在理论上是有证明的，即 Cover定理 ，Cover定理可以理解为：当空间的维数D越大时，在该空间的N个数据点间的线性可分的概率就越大。如果固定数据的数量N，维度D小于数据数量N时，特征空间维度越高，越有可能使数据线性可分；在维度超过数据数量时，数据一定线性可分（试想如果我们把每个数据点都映射到不同的坐标轴上，那么可不就是线性可分的了么）。

因此，我们对非线性可分的数据，可以将数据映射至高维空间，然后再用我们熟悉的线性分类器来分类，至此，剩下的问题就是怎么映射呢？这就需要核函数登场了。

核函数是一个广泛使用的技术，事实上它比支持向量机出现的更早，它可以将一个空间的向量映射到另一个空间，刚好符合我们解决非线性可分问题的需求， 核函数定义 ：

核函数的一大优势就是，它通过定义函数 来隐式的定义映射 ，一般来说，直接计算函数 是比较容易的，因为它是在原始低维度进行的，而通过 计算是很困难的，因为 是高维的，甚至是无穷维的。

既然核函数这么棒，那怎么获得一个核函数呢？或者说怎么判断一个函数是不是核函数？通常我们所说的核函数都是正定核函数， 正定核函数的充要条件：

有了这个定义，理论上我们可以构造出核函数，不过对非常困难，因为要保证任意输入的Gram矩阵都要是半正定矩阵，所以在实际使用中，我们一般使用前辈们总结好的常用核函数。

证明：

根据定义，核函数的映射涉及从欧氏空间到希尔伯特空间的转化，其过程是怎样的呢？如果我们在Gram矩阵是半正定的条件下，把这个映射过程推出来不就相当于证明了上述定理的充分性了吗~

前提： 是对称函数、 是半正定矩阵

除去对应的基底，将其表示为希尔伯特空间的向量（一个函数可以看成一个无穷维的向量，空间中的任何一个函数都可以表示为一组正交基的线性组合）：

计算二者内积：

也就是核函数定义中的：

至此就证明了上述定理的充分性，至于必要性，求出Gram矩阵就可以证明，比较简单就不说了。

这个特性叫做 再生性（reproducing property） ，所以这个空间叫做 再生核希尔伯特空间(RKHS, reproducing kernel Hilbert space) 。

对定义的低维度到高纬度的映射 来说，我们不需要知道这个映射是什么就可以计算得到高维的内积 ，这就是SVM中使用的 核技巧 。

*上述核函数及证明中出现较多的各种数学空间，如果不熟悉的话可以看文末的附录，对各种空间的关系有一个大致的展示。

使用线性核函数跟不使用核函数是一样的，还是无法处理非线性可分问题的，不过从这个角度出发，我们可以把 线性可分SVM看作非线性不可分SVM的使用线性核函数的特例 。

SVM中也称为径向基核函数（Radial Basis Function,RBF），是非线性支持向量机中最常用的核函数：

因为在映射后的高维空间中，支持向量机还是在解决线性可分的数据，所以原理、目标函数什么的都跟之前是一样的，只是最终的形式上有所不同，最终可得非线性支持向量机模型：

非线性支持向量机的算法过程：

核函数的引入大大提升了支持向量机的应用范围，使得其在非线性可分问题上也有了很好的分类表现，而且核技巧使得隐式的高维映射成为可能，使用起来也非常便捷。

还记得我们在 逻辑回归 中针对非线性可分问题说过：

所以相对于逻辑回归等线性分类器来说，SVM具有很大的优势，这也是SVM在过去几十年里流行的主要原因之一，其优美的数学推导也让很多学者非常喜欢，不过随着近几年集成学习、神经网络的兴起和数据量的爆炸性增长，SVM也慢慢的不再那么流行了，不过其在特定问题上仍然是一个很有魅力的算法，值得大家掌握。

现在三种SVM都写完了，来总结一下SVM的优缺点吧：

数学空间：数学中的空间的组成包括两个部分：研究的对象和内在的规则，或者叫做元素和结构。