支持向量机（SVM）详解（二）

本文承接上一篇《支持向量机（SVM）详解（一）》，继续对支持向量机进行介绍，这篇文章分为两大部分：软间隔支持向量机和核函数的引入。

一、“软间隔”（Soft-margin）支持向量机

　　“软间隔”支持向量机是一种不满足式（2）的，不可以将训练样本“完美”划分的分类器。

目标函数

　　在现实任务中很多情况下都不满足式（2）这种情况，为了避免使用核函数带来的过拟合问题，软间隔支持向量机允许训练集中的一部分样本不满足“完美”划分条件，但是在最大化间隔时，应使不满足约束的样本点尽可能少。因此在式（4）的优化目标函数中加入损失函数lost(xi,yi)$lost\left({\mathbf{x}}_i,y_i\right)$，来表示上述这些不满足约束的样本点的影响，即

　　当损失函数lost(xi,yi)$lost\left({\mathbf{x}}_i,y_i\right)$采用0/1损失函数

时（其中z=yi(ωTxi+b)−1$z=y_i\left({\omega }^T{\mathbf{x}}_i+b\right)-1$），若参数C$C$无穷大，那么就会迫使所有样本点满足式（2）中的约束条件，而式（10）等价于式（4），反之，如果所有样本点均满足式（2）（此时损失函数不小于零），那么参数 被迫为零，式（10）同样等价与式（4）；若参数 为有限值，那么式（10）允许一部分样本点不满足式（2）。
　　但是，由于0/1损失函数不连续、数学性质不好，且由于其非凸而不满足凸优化条件使得强对偶性不成立【6】，因此不易于直接求解。于是出现了许多用来替代0/1损失函数的“替代损失”函数（Surrogate $$Loss $$Function），这些函数往往具有良好的数学性质，他们通常是凸的连续函数而且是0/1损失函数的上界，如下三种替代损失函数

这几种损失函数的关系由下图所示，其中红色线为0/1损失函数

　　由于损失函数不小于零的性质，在这里引入松弛变量（Slack $$Variable）ξi⩾0${\xi }_i⩾0$，优化目标函数中的损失函数lost(xi,yi)$lost\left({\mathbf{x}}_i,y_i\right)$可以被替换为ξi⩾0${\xi }_i⩾0$，这时，优化目标可以写为

这就是软间隔支持向量机的优化目标，其中松弛变量ξi⩾0${\xi }_i⩾0$由来描述样本点不满足式（2）约束条件的程度，且满足【5】中二次规划问题的条件，可以采用现成的二次规划包来进行求解。
需要注意的是，式（11）中第一项可以看做是“结构风险”（Structural $$Risk），即模型过拟合的风险，另一项可以看做是“经验风险”（Empirical $$Risk），即模型与训练集的契合程度，参数 是正则化系数，因此，式（11）可以称为“正则化问题”（Regularization $$Problem）。

目标函数的对偶问题

　　与硬间隔支持向量机中的讨论类似，在软间隔支持向量机中，优化目标的拉格朗日乘子函数可以表示为

其中αi⩾0${\alpha }_i⩾0$和中μi⩾0${\mu }_i⩾0$是拉格朗日乘子，其KKT条件为

　　由于满足凸优化条件【6】，因此与硬间隔相同，主问题与其对偶问题有相同的解，即

将拉格朗日乘子函数分别对ω$\omega$、b$b$、ξ$\xi$求偏导数并置零，可以得到

将上式带入式（11）即得其对偶问题

可以看出这与式（6）的区别在对αi${\alpha }_i$约束条件的不同，式（6）中αi⩾0${\alpha }_i⩾0$，因此可以采用与硬间隔支持向量机相同的方法求解对偶问题。得到上述参数后，软间隔支持向量机的分类边界可以表示为（注意这里的参数b$b$是由参数ξi${\xi }_i$决定的）

对KKT条件的理解

　　由软间隔支持向量机的KKT条件可知，所有样本点均满足αi=0${\alpha }_i=0$或f(xi)=1−ξi$f\left({\mathbf{x}}_i\right)=1-{\xi }_i$，基于参数αi${\alpha }_i$的几种不同的情况，分别做以下讨论：
(1) αi=0${\alpha }_i=0$
　　这时，该样本点对最终的分类边界没有任何影响；
(2) C>alphai>0$C>alph{a}_i>0$
　　由C=αi+μi$C={\alpha }_i+{\mu }_i$可知μi>0${\mu }_i>0$，这时松弛向量ξi=0${\xi }_i=0$，该样本满足式（2）的约束条件，位于最大间隔上或最大间隔外，这些点决定了参数

被称为“自由支持向量”（Free $$SV）。
(3) αi=C${\alpha }_i=C$
　　由C=αi+μi$C={\alpha }_i+{\mu }_i$可知μi=0${\mu }_i=0$，这时若0⩽ξi⩽1$0⩽{\xi }_i⩽1$，那么此样本点位于最大间隔内部或最大间隔上；若ξi>1${\xi }_i>1$，那么此样本点被错误分类，这些点是支持向量。
　　由上述讨论可知，软间隔支持向量机的最终模型同样取决于支持向量，即替代损失函数保留了原优化问题的稀疏性。

二、核函数的引入

　　对于现实任务中不可分的训练样本，除了采用软间隔支持向量机“强行”将这些样本点分开，还可以通过将低维空间中的向量映射到高维空间中，来解决低维空间中的不可分问题，具体的说，如果原始空间是有限维的，即属性数有限，那么一定存在一个高维空间使得样本可分。下面以异或问题为例，将二维空间中的向量映射到了三维空间中，在三维空间中存在一个划分平面，将样本“完美”划分

　　令ϕ(x)$\varphi \left(\mathbf{x}\right)$表示将向量x$\mathbf{x}$映射到高维空间d(ϕ(x))≫d(x)$d\left(\varphi \left(\mathbf{x}\right)\right)\gg d\left(\mathbf{x}\right)$后产生的新向量，那么式（4）在高维空间中可以写成如下形式

其对偶问题的形式为

为了求解上式，需要计算高维空间中的内积ϕ(xi)Tϕ(xj)$\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)$，根据映射的不同，高维空间的维数很高，甚至可能为无限维，因此直接计算ϕ(xi)Tϕ(xj)$\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)$是非常困难的。
　　为了解决上述问题，可以设计这样一个函数

即xi${\mathbf{x}}_i$与xj${\mathbf{x}}_j$在映射后的高维空间中的内积等于他们在原始低维空间中通过函数k(˙,˙)$k\left(\dot{},\dot{}\right)$计算的结果，这样就不用直接计算高维甚至无限维空间中的内积，这个函数就被称为“核函数”（Kernel $$Function）。在引入核函数后，原优化目标的对偶问题可以表示为

求解后得到的分类边界可以表示为

　　核函数具有以下定义，
　　令χ$\chi$为输入空间，k(˙,˙)$k\left(\dot{},\dot{}\right)$是定义在χ×χ$\chi \times \chi$上的对称函数，则k(˙,˙)$k\left(\dot{},\dot{}\right)$是核函数当且仅当对于任意数据D={x1,x2,...,xm}$D=\{{\mathbf{x}}_1,{\mathbf{x}}_2,...,{\mathbf{x}}_m\}$，“核矩阵”（Kernel $$Matrix）K$\mathbf{K}$总是半正定的：

由以上定义可知，只要一个对称函数的核矩阵为半正定的，他就能作为核函数来使用，这就是Mercer定理，每一个核函数都隐式的定义了一个称为“再生希尔伯特空间”的特征空间。需要注意的是由于k(˙,˙)$k\left(\dot{},\dot{}\right)$是对称函数，其核矩阵K$\mathbf{K}$必定是对称矩阵。
核函数的选择决定了最后得到的模型，常用的核函数有：
(1) 线性核

(2) 多项式核

其中d⩾1$d⩾1$为多项式的次数，当d=1$d=1$时，退化为线性核
(3) 高斯核

其中σ>0$\sigma >0$为高斯核的带宽
(4) 拉普拉斯核

其中σ>0$\sigma >0$为拉普拉斯核的带宽
(5) Sigmoid核

其中β>0$\beta >0$，θ<0$\theta <0$
此外，核函数还有以下性质
(1)若k1$k_1$和k2$k_2$为核函数，则对于任意正数γ1${\gamma }_1$，其线性组合γ1k1+γ2k2${\gamma }_1{k}_1+{\gamma }_2{k}_2$也是核函数；
(2)若k1$k_1$和k2$k_2$为核函数，则核函数的内积k1⨂k2(x,z)=k1(x,z)k2(x,z)$k_1⨂k_2\left(\mathbf{x},\mathbf{z}\right)=k_1\left(\mathbf{x},\mathbf{z}\right)k_2\left(\mathbf{x},\mathbf{z}\right)$也是核函数；
(3)若k1$k_1$和k2$k_2$为核函数，则对于任意函数g(x)$g\left(\mathbf{x}\right)$，k(x,z)=g(x)k(x,z)g(z)$k\left(\mathbf{x},\mathbf{z}\right)=g\left(\mathbf{x}\right)k\left(\mathbf{x},\mathbf{z}\right)g\left(\mathbf{z}\right)$也是核函数。

---

至此，关于支持向量机的详细介绍已经完结，下一篇将会介绍与SVM的思想类似的，但是用于回归任务的“支持向量回归”（SVR）。