SVM支持向量机系列理论（三） 非线性支持向量机与核函数技巧

3.1 核技巧解决非线性SVM

3.1.1 非线性SVM解决思路

对于非线性分类问题，显然无法用一个线性分离超平面来把不同的类别的数据点分开，那么可以用以下思路解决这个问题：

• 首先使用一个变换 z=ϕ(x)$z=\varphi (x)$ 将非线性特征空间x映射到新的线性特征空间z

• 在新的z特征空间里使用线性SVM学习分类的方法从训练数据中学习分类模型

基于这个想法，SVM模型可以表示成：

minα    12∑Nj=1αiαjyiyj(ϕ(xi)⋅ϕ(xj))−∑Ni=1αi$mi{n}_{\alpha }\frac{1}{2}\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(\varphi (x_i)\cdot \varphi (x_j))-\sum _{i=1}^N{\alpha }_i$

            $$
s.t.    ∑Ni=1αiyi=0$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0$

            αi≥0,i=1,2,...,N         (1)${\alpha }_i\ge 0,i=1,2,...,N(1)$

但是，这里有一个问题: ϕ(xi)⋅ϕ(xj)$\varphi (x_i)\cdot \varphi (x_j)$计算起来要分两步，先映射x到z空间，然后在z空间（一般是较高维度）作高维度的內积 zi⋅zj$z_i\cdot z_j$。

为了简化这个运算过程，如果我们找到一个核函数 K(xi,xj)$K(x_i,x_j)$, 即K是关于x的函数，其运算在低维空间上进行，然后使得K(xi,xj)=ϕ(xi)⋅ϕ(xj)$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$，那么只需要计算一个比较好计算的核函数 K(xi,xj)$K(x_i,x_j)$，就可以避免先映射，再在高维空间內积的复杂运算。

---

3.1.2 核技巧下SVM

基于核技巧，非线性SVM模型可以表示成：

minα    12∑Nj=1αiαjyiyjK(xi,xj)−∑Ni=1αi$mi{n}_{\alpha }\frac{1}{2}\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^N{\alpha }_i$

            $$
s.t.    ∑Ni=1αiyi=0$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0$

            αi≥0,i=1,2,...,N         (2)${\alpha }_i\ge 0,i=1,2,...,N(2)$

其中，K(xi,xj)$K(x_i,x_j)$, 是关于原始低维特征空间 x 的函数，其运算在低维空间上进行。因此，降低了计算的复杂度。

在实际中，对一个非线性可分数据，我们不是先去定义转换函数数ϕ(x)$\varphi (x)$，再找出其对应的核函数K，而是直接用一些常用核函数代入上面（2）中的非线性可分支持向量机，然后查看分类效果，再调整核函数的类型，这样就隐式地实现了低维到高维的映射，而不用显式地定义映射函数ϕ(x)$\varphi (x)$和特征空间，这种方法叫核技巧。

比如，现在为了解决非线性可分数据问题，现在直接用 K(x,x′)=(xTx′)2$K(x,x^{\prime })=(x^T{x}^{\prime }{)}^2$ 放进（2），那么就可以解决一些非线性问题了，至于效果怎么样，还需要看实际的数据情况，在做调整。

minα    12∑Nj=1αiαjyiyj(xTx′)2−∑Ni=1αi$mi{n}_{\alpha }\frac{1}{2}\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x^T{x}^{\prime }{)}^2-\sum _{i=1}^N{\alpha }_i$

            $$
s.t.    ∑Ni=1αiyi=0$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0$

            αi≥0,i=1,2,...,N         (3)${\alpha }_i\ge 0,i=1,2,...,N(3)$

而且需要理解的是：
- K(x,x′)=(xTx′)2$K(x,x^{\prime })=(x^T{x}^{\prime }{)}^2$背后的映射ϕ(x)$\varphi (x)$不是唯一的。ϕ(x)$\varphi (x)$可以是不同维数的映射方式，而即使是同一维度的映射，ϕ(x)$\varphi (x)$的具体形式也可以不同。
（统计学习P117例7.3）

3.2 Mercer核

上面提到，在实际应用中，我们直接将使用某种核函数直接带入到非线性可分支持向量（2）式中去，用来解决非线性分类问题。但是，并不是任何一种关于x的函数都可以成为核函数，只有满足以下条件时才能充当核函数：

• 核函数K(x,x′)$K(x,x^{\prime })$是对称函数
• 对任意属于样本集X中的xi$x_i$, 核函数K(x,x′)$K(x,x^{\prime })$对应的Gram矩阵是半正定矩阵
  
  • Gram矩阵定义为：
    G=[K(xi,xj)]mm$G=[K(x_i,x_j){]}_{mm}$，其实就是把不同样本点放到核函数中去计算，因此G的shape和样本数量m相关，为mm。

我们把上面两个条件称Mercer条件。

例题 判断 (−1+xTx′)$(-1+x^T{x}^{\prime })$ 是不是核函数？

可以假设x为一维数据，两个样本 x1=1$x_1=1$及 x2=−1$x_2=-1$,则可以得到Gram矩阵为：

[−1+1⋅1−1+1⋅−1 −1+1⋅−1−1+(−1⋅−1)]=[0−2−20]$\left[\begin{array}{ccc}-1+1\cdot 1& -1+1\cdot -1-1+1\cdot -1& -1+(-1\cdot -1)\end{array}\right]=\left[\begin{array}{cc}0& -2\\ -2& 0\end{array}\right]$

则 xTGx=[x1x2]$x^{T}Gx=\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]$
[0−2 −20]$\left[\begin{array}{ccc}0& -2-2& 0\end{array}\right]$
[x1  x2]=−2x2−2x1$\left[\begin{array}{c}{x}_1{x}_2\end{array}\right]=-2x_2-2x_1$

并不能得到总是大于等于0，因此不是半正定，不能作为核函数。

3.3 常用的核函数

3.3.1 二次多项式核

K(x,x′)=(a+r xTx′)2 a≥0,r>0$K(x,x^{\prime })=(a+r{x}^T{x}^{\prime }){}^{2}a\ge 0,r>0$

其对应的映射函数可以是：

ϕ(x)=(a,a⋅r−−−√x1,...,a⋅r−−−√xd,rx21,...,rx2d)$\varphi (x)=(a,\sqrt{a\cdot r}{x}_1,...,\sqrt{a\cdot r}{x}_d,r{x}_1^2,...,r{x}_d^2)$

3.3.2 高斯核

形式：

K(x,x′)=exp(−r ||x−x′||2)$K(x,x^{\prime })=exp(-r||x-x^{\prime }|{|}^2)$

特点：

可以做无限多维的映射，其保护是large margin，只有一个参数r，当r很大时，很容易就过拟合。

更多查阅：几种核函数的对比