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

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

1 非线性可分问题怎么解决

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

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

如果原始空间是有限维，且属性数有限，那么一定存在一个高维特征空间使样本可分

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

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

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

2 核函数登场

2.1 什么是核函数

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

假设 $ϕ$ 是一个从低维的输入空间 $χ$ （欧式空间的子集或者离散集合）到高维的希尔伯特空间的 $H$ 映射： $\phi(x):χ\rightarrow H$ ，如果存在函数 $K(x,z)$ ，对于任意 $x,z∈χ$ ，都满足：

$K(x, z) = \phi(x) \cdot \phi(z)$

则称 $K(x,z)$ 为核函数， $ϕ(x)$ 为映射函数。

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

2.2 怎么得到核函数

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

设 $χ\subset R^n$ ， $K(x,z)$ 是定义在 $χ\times χ$ 上的对称函数（ $K(x,z)=K(z,x)$ ），如果对任意的 $x_i∈χ，i=1,2,3...m, K(x_i,x_j)$ 对应的 $Gram$ 矩阵（格拉姆矩阵） $K=[K(x_i,x_j)]_{m\times m}$ 是半正定矩阵，则 $K(x,z)$ 是正定核函数。

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

证明：

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

前提： $K$ 是对称函数、 $[K(x_i,x_j)]$ 是半正定矩阵

对于低维度的数据 $x$ ，定义一个映射 $x\rightarrow \phi(x)=K(x,\cdot)$ ；
K(x,z)是一个二维半正定矩阵，因为其是对称矩阵，特征向量相互正交，可以视为一组正交基，对K(x,z)进行特征分解，同样因为对称性，所以 $\psi_i (z)$ 视为变量z时的特征向量，是 $\psi_i (x)$ 的转置，可得：

$K(x,z)=\psi \lambda\psi ^T= \sum_{i=1} \lambda_i \psi_i (x) \psi_i (z)$

由基底 $\{ \sqrt{\lambda_i} \psi_i \}_{i=1}^{\infty}$ 构建一个空间，因为 $[K(x_i,x_j)]$ 是半正定矩阵，可以证明这个空间可以定义内积运算，是一个内积空间，将其完备化得到希尔伯特空间（各种空间的关系见文末附录），这个空间中的任何一个函数（向量）都可以表示为这组基的线性组合，因此有：

$K(x,\cdot) = \sum_{i=1}^{\infty} \lambda_i \psi_i (x) \psi_i$

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

$K(x,\cdot) = (\sqrt{\lambda_1} \psi_1 (x), \sqrt{\lambda_2} \psi_2 (x), \cdots )_\mathcal{H}^T$

$K(z,\cdot) = (\sqrt{\lambda_1} \psi_1 (z), \sqrt{\lambda_2} \psi_2 (z), \cdots )_\mathcal{H}^T$

计算二者内积：

$K(x,\cdot)\cdot K(z,\cdot) = \sum_{i=0} \lambda_i \psi_i (x) \psi_i(z) = K(x,z)$

也就是核函数定义中的：

$K(x, z) = \phi(x) \cdot \phi(z)$

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

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

对定义的低维度到高纬度的映射 $\phi(x)$ 来说，我们不需要知道这个映射是什么就可以计算得到高维的内积 $K(x, z) = \phi(x) \cdot \phi(z)$ ，这就是SVM中使用的核技巧。

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

2.3 常用核函数

线性核函数（Linear Kernel）

$K(x,z)=x\cdot z$

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

多项式核函数（Polynomial Kernel）

$K(x,z)=(x\cdot z+1)^p$

高斯核函数（Gaussian Kernel）

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

$K(x,z)=exp(-\frac{||x-z||}{2\sigma^2})^p$

3 基于核函数的非线性支持向量机

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

$f(x)=sign(\sum_{i=1}^N \lambda_i^*y_iK(x,x_i)+b^*)$

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

输入：样本 $T=(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ ， $x$ 为 $n$ 维特征向量， $y\in[+1,-1]$ ；

输出： $\lambda^*,b^*$ ，支持向量机模型 $f(x)=sign(\sum_{i=1}^m \lambda_i^*y_iK(x,x_i)+b^*)$ 。

确定核函数 $K(x,z)$ 和惩罚系数 $C>0$ ，确定目标函数：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_i\lambda_jy_jK(x_i,x_j)-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;\;0\leq\lambda_i\leq C$

使用SMO优化目标函数，得到对应的 $λ^*$ ；

根据 $λ^*$ 找到样本中的k个支持向量，计算参数 $b$ ：

$b^*=\frac{1}{k}\sum_i^k (y_i-\sum_{i=1}^m \lambda_i^*y_iK(x,x_i))$

得到支持向量机模型 $f(x)=sign(\sum_{i=1}^m \lambda_i^*y_iK(x,x_i)+b^*)$ 。