浅谈SVM（四）

三、非线性 SVM
1、引子
为了将线性 SVM 拓展到非线性 SVM,我们对线性 SVM 进行简单地分析，首先就是关于我们的超平面，对于一个数据点 x 进行分类，其实就是通过把 x 带入到 f(x)=wTx+b 中算出结果，然后根据其正负号来进行类别划分的。而在前面的推导中我们得到 w=∑ni=1αiyixi ，因此，分类函数为：

f (x) = (\sum i = 1 n α i y i x i) T x + b = \sum i = 1 n α i y i x T i x + b = \sum i = 1 n α i y i < x i, x > + b

这里形式的有趣之处在于，对于新点 x 的预测，只需要计算它与训练数据点的内积即可（表示向量内积），这一点至关重要，是之后使用 Kernel 函数进行非线性推广的基本前提。此外，所谓支持向量也在这里显示出来，事实上，所有非支持向量所对应的系数 αi 都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据。
为什么非支持向量对应的 αi 等于零呢？直观上来理解的话，就是这些“后方”的点对超平面是没有影响的，由于分类完全由超平面决定，所以这些无关的点并不会参与分类问题的计算，因而也就不会产生任何影响了。下面给出数学上的说明，给出目标函数：

maxα≥0L(w,b,α)=maxα≥012||w||2−∑ni=1αi(yi(wTxi+b)−1)

注意到如果 xi 是支持向量的话，上式中 (yi(wTxi+b)−1) 是等于 0 的，而对于非支持向量来说会大于 0 ，而 αi 又是非负的，为了满足最大化，αi 必须等于 0 ，这也就是这些非支持向量的点的局限性。
2、核函数
在上文中，我们已经了解到了 SVM 处理线性可分的情况，而对于非线性的情况，SVM 的处理方法是选择一个核函数 K(.,.) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。
在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。如图所示，一堆数据在二维空间无法划分，从而映射到三维空间里划分：

浅谈SVM（四）

而在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：

f(x)=∑ni=1wiΦi(x)+b

这里 Φ:X→S 是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：

首先使用一个非线性映射将数据变换到一个特征空间 S；
然后在特征空间使用线性学习器分类。

由于对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：

f(x)=∑ni=1αiyi<Φ(xi),Φ(x)>+b

如果有一种方式可以在特征空间中直接计算内积 <Φ(xi),Φ(x)>，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算的方法称为核函数方法。
下面来看个核函数的例子，如下图所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时咱们该如何把这两类数据分开呢？

事实上，上图所述的这个数据集，是用两个半径不同的圆圈加上了少量的噪声得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用 X1 和 X2 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：

a1X1+a2X21+a3X2+a4X22+a5X1X2+a6=0

注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 Z1=X1,Z2=X21,Z3=X2,Z4=X22,Z5=X1X2 ，那么显然，上面的方程在新的坐标系下可以写作：

∑5i=1aiZi+a6=0

关于新的坐标 Z，这正是一个超平面方程。也就是说，如果我们做一个映射 Φ:R2→R5，将 X 按照上面的规则映射为 Z，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。
核函数相当于把原来的分类函数：

f(x)=∑ni=1αiyi<xi,x>+b

映射成：

f(x)=∑ni=1αiyi<Φ(xi),Φ(x)>+b

而其中的 α 可以通过求解如下对偶问题而得到：

$⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ m a x α \sum n i = 1 α i - 12 \sum n i, j = 1 α i α j y i y j x T i x j s . t . α i \geq 0, i = 1, 2, . . ., n \sum n i = 1 α i y i = 0$

这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射 Φ，然后把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上没有这么简单！刚才的方法其实有一个问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维的，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给 Φ 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。此时就需要 Kernel 函数出马了。
不妨还是从最开始的简单例子出发，设两个向量 x1=(η1,η2) 和 x2=(ξ1,ξ2) ,而 Φ 即是前面说的五维空间的映射，因此映射过后的内积为：

<Φ(x1),Φ(x2)>=η1ξ1+η21ξ21+η2ξ2+η22ξ22+η1ξ1η2ξ2

我们又注意到

(<x1,x2>+1)2=2η1ξ1+η21ξ21+2η2ξ2+η22ξ22+2η1ξ1η2ξ2+1

二者有很多相似的地方，实际上，只要把某几个维度线性缩放一下，然后再加上一个常数维度，具体来说，上面这个式子的计算结果实际上和映射

Φ(X1,X2)=(2√X1,X21,2√X2,X22,2√X1X2,1)T

之后的内积 <Φ(x1),Φ(x2)> 的结果是相等的，那么区别在于什么地方呢？区别在于一个是映射到高维空间中，然后再根据内积的公式进行计算；而另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。
我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数（Kernel Function）。例如，在刚才的例子中核函数为：

K(x1,x2)=(<x1,x2>+1)2

核函数能简化映射空间中的内积运算，碰巧的是，在我们的 SVM 里需要计算的向量总是以内积的形式出现的。现在我们的分类函数为：

f(x)=∑ni=1αiyiK(xi,x)+b

其中 α 由如下对偶问题计算而得：

$⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ m a x α \sum n i = 1 α i - 12 \sum n i, j = 1 α i α j y i y j K (x i, x) s . t . α i \geq 0, i = 1, 2, . . ., n \sum n i = 1 α i y i = 0$

这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的！当然，因为这里的例子非常简单，所以可以手工构造出对应于 Φ(.) 的核函数出来，如果对于任意一个映射，想要构造出对应的核函数就很困难了。
下面我们来看看常用的核函数：
1.多项式核

K(x1,x2)=(<x1,x2>+r)d

该空间的维度是 (m+dd) ，其中 m 是原始空间的维度。
2.高斯核

K(x1,x2)=e||x1−x2||22σ2

这个核函数可以将原始空间映射为无穷维空间。不过，如果 σ 选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果 σ 选得很小，则可以将任意的数据映射为线性可分的数据。当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：

3.线性核

K(x1,x2)=<x1,x2>

这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了。
问：既然有很多的核函数，针对具体问题该怎么选择？
答：对核函数的选择，现在还缺乏指导原则，各种实验的观察结果表明，某些问题用某些核函数效果很好，用另一些就很差，但是一般来说，径向基核函数（高斯核函数）是不会出太大偏差的一种，首选。
最后概括一下：
1.实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的；
2.但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的；
3.此时，核函数就隆重登场了，核函数的价值在于它虽然也是将特征从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。

相关推荐