第六章 支持向量机

6.1 间隔和支持向量

  给定训练样本集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } , y i ∈ { − 1 , + 1 } D = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_m},{y_m})\} ,{y_i} \in \{ - 1, + 1\} D={(x1​,y1​),(x2​,y2​),...,(xm​,ym​)},yi​∈{−1,+1}，分类学习最基本的想法就是基于训练集$D$在样本空间中找到一个划分超平面，将不同类别的样本分开，但能将训练样本分开的划分超平面可能有很多，如下所示：

  直观上看，应该去找位于两类训练样本“正中间”的划分超平面，该超平面对训练样本局部扰动的“容忍”性最好，也就是该划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。划分超平面的线性方程如下所示：
$${\omega }^{T}x+b=0$$
  其中$\omega =({\omega }_1;{\omega }_2;...;{\omega }_d)$为法向量，决定了超平面的方向；$b$为位移项，决定了超平面与原点之间的距离，下面定义样本空间中任意点$x$到超平面$(\omega ,b)$的距离，如下所示：
$$r=\frac{\left|{\omega }^{T}x+b\right|}{\Vert \omega \Vert }$$
  假设超平面$(\omega ,b)$能将训练样本正确分类，有如下定义：
$$\{\begin{array}{r}{\omega }^T{x}_i+b⩾+1,y_i=+1\\ {\omega }^T{x}_i+b⩽-1,y_i=-1\end{array}$$
  如下图所示，距离超平面最近的这几个训练样本点使上式的等号成立，这些点被称为“支持向量”，两个异类支持向量到超平面的距离之和为$\gamma =\frac{2}{\Vert \omega \Vert }$，也被称为“间隔”。

  欲找到具有“最大间隔”的划分超平面，需要找到满足约束条件的参数$\omega$和$b$，使得$\gamma$最大，即
$$\begin{array}{rl}& \underset{\omega ,b}{\max }\frac{2}{\Vert \omega \Vert }\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1,i=1,2,...,m\end{array}$$
  最大化${\Vert \omega \Vert }^{-1}$，等价于最小化${\Vert \omega \Vert }^2$，于是得到如下表达，这也是支持向量机的基本型。
$$\begin{array}{rl}& \underset{\omega ,b}{\min }\frac{1}{2}{\Vert \omega \Vert }^2\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1,i=1,2,...,m\end{array}$$
  虽然间隔看着貌似只与$\omega$有关，但实际上$b$通过约束隐式地影响着$\omega$的取值，因为这些支持向量是使得等号成立的样本点，所以如果$b$发生变化，那么$\omega$也会发生变化。

6.2 对偶问题

  SVM基本型的对偶问题是将原始问题的最小化目标函数转换为最大化拉格朗日函数，利用拉格朗日对偶性，求解出拉格朗日乘子，从而得到超平面的参数。首先对原来的约束条件添加拉格朗日乘子${\alpha }_i⩾0$，得到如下的拉格朗日函数：
$$L(\omega ,b,\alpha )=\frac{1}{2}{\Vert \omega \Vert }^2+\sum _{i=1}^m{\alpha }_i(1-y_i({\omega }^T{x}_i+b))$$
  下面分别对$\omega$和$b$求偏导，得到如下结果：
$$\omega =\sum _{i=1}^m{\alpha }_i{y}_i{x}_i,0=\sum _{i=1}^m{\alpha }_i{y}_i$$
  将上面求偏导的结果再带入到原来的拉格朗日函数中，就可以得到SVM基本型的对偶问题，如下所示：
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$
  上述问题是一个二次规划问题，但该问题的规模正比于训练样本数，会在实际任务中造成很大的开销，为了避开这个障碍，在这里引入了SMO算法来解决这个问题，SMO算法需要注意以下几点：

• SMO算法的基本思想是每次选择两个拉格朗日乘子（${\alpha }_i$ 和 ${\alpha }_j$）作为优化变量，固定其他的乘子，将原问题简化进行求解。
• SMO算法的关键是如何选择合适的 ${\alpha }_i$ 和 ${\alpha }_j$，以及如何更新它们的值，一般来说，选择违反KKT条件最严重的 ${\alpha }_i$ 作为第一个变量，然后在约束条件下选择第二个变量 ${\alpha }_j$，使得目标函数有足够大的变化。
• SMO算法的终止条件是所有的拉格朗日乘子都满足KKT条件，或者达到最大迭代次数。
• SMO算法的优点是可以高效地求解SVM对偶问题，避免了矩阵运算和存储，只需要利用核函数计算样本之间的内积，而缺点是需要调整一些启发式的参数，如容错率和最大迭代次数，以及核函数的选择。

6.3 核函数

  在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面，如下左图所示，对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，如下右图所示。

  令$\varphi (x)$表示将$x$映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为
$$f(x)={\omega }^T\varphi (x)+b$$
  以下为其基本型
$$\begin{array}{rl}& \underset{\omega ,b}{\min }\frac{1}{2}{\Vert \omega \Vert }^2\\ & s.t.y_i({\omega }^T\varphi (x_i)+b)⩾1,i=1,2,...,m\end{array}$$
  以下为对应的对偶问题
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi (x_i{)}^T\varphi (x_j)\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$
  求解上述式子涉及到$\varphi (x_i{)}^T\varphi (x_j)$，这是样本$x_i$与$x_j$映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算$\varphi (x_i{)}^T\varphi (x_j)$通常是困难的。为了避开这个障碍，可以设想这样一个函数：
$$\kappa (x_i,x_j)⩽\varphi (x_i),\varphi (x_j)⩾\varphi (x_i{)}^T\varphi (x_j)$$
  即$x_i$与$x_j$在特征空间的内积等于它们在原始样本空间中通过函数$\kappa (\cdot ,\cdot )$计算的结果，于是可以得到如下式子：
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\kappa (x_i,x_j)\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$
  求解后即可得到$f(x)=\sum _{i=1}^m{\alpha }_i{y}_i\kappa (x_i,x_j)+b$，这里的$\kappa (x_i,x_j)$被称为“核函数”，这一展开式也被称为“支持向量展开”。下面为判断核函数的一个定理。

  以下为常见的核函数。

  对于核函数的选择，可以参考以下规则：

• 如果数据是线性可分的，或者特征的数量很大，接近于样本的数量，可以选择线性核函数，因为线性核函数参数少，速度快，而且可以得到很好的效果。
• 如果数据是非线性的，或者特征的数量比较小，而样本的数量一般，可以选择高斯核函数（也叫RBF核函数），因为高斯核函数可以将数据映射到一个无限维的特征空间，具有很强的拟合能力。不过高斯核函数的分类结果非常依赖于参数的选择，需要通过交叉验证等方法来寻找合适的参数。
• 如果数据是非线性的，而且有明显的结构特征，例如图像、文本等，可以选择与数据结构相匹配的核函数，例如多项式核函数、字符串核函数、图核函数等。这些核函数可以利用数据的先验知识，提取更有效的特征，提高分类或回归的准确性。

6.4 软间隔与正则化

  在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的，缓解这个问题的一个办法是允许支持向量机在一些样本上出错，如下为软间隔示例图，红色圈出了一些不满足约束的样本。

  若要求所有样本都必须划分正确，这称为“硬间隔”，而软间隔则是允许某些样本不满足约束$y_i({\omega }^T{x}_i+b)⩾1$，而在最大化间隔的同时，不满足约束的样本应尽可能少，于是就有了如下优化目标：
$$\underset{\omega ,b}{\min }\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^m{\ell }_{0/1}(y_i({\omega }^T{x}_i+b)-1)$$
  其中类似${\ell }_{0/1}$的函数被称为“替代损失”，常见的替代函数以及它们的图像如下所示：

  下面引入松弛变量${\xi }_i⩾0$，即可得到如下的软间隔支持向量机：
$$\begin{array}{rl}& \underset{\omega ,b,\xi }{\min }\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^m{\xi }_i\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1-{\xi }_i\end{array}$$
  松弛变量${\xi }_i$表示第$i$个样本违反约束条件的程度，$C$是一个正的常数，表示对松弛变量的惩罚系数。可以看到，当$C$很大时，相当于对松弛变量的惩罚很大，要求所有样本都满足约束条件，这就退化为硬间隔的情况；当$C$很小时，相当于对松弛变量的惩罚很小，允许一些样本不满足约束条件，这就增加了模型的泛化能力。因此，$C$的大小决定了svm对分类错误的容忍程度和模型的复杂度。

  而这里需要注意，$C$比较大会增加松弛变量的值，是因为要最小化整个目标函数，而不是只最小化间隔。目标函数由两部分组成，一部分是$\frac{1}{2}{\Vert \omega \Vert }^2$，表示间隔的倒数；另一部分是$C{\sum }_{i=1}^n{\xi }_i$，表示对松弛变量的惩罚。当$C$比较大时，表示对松弛变量的惩罚比较大，也就是要求所有样本都满足约束条件，即$y_i({\omega }^T{x}_i+b)\ge 1-{\xi }_i$。这样的话，如果有一些样本本来不满足约束条件，那么就要增加它们的松弛变量的值，让它们满足约束条件。这样做的好处是可以减少分类错误，提高模型在训练集上的准确率。但是，这样做的坏处是可能导致过拟合，降低模型在测试集上的泛化能力。

  同时这里的$C$也是正则化尝试，正则化可以理解为一种“罚函数法”，即对不希望得到的结果施以惩罚，从而使得优化过程趋向于希望目标，从贝叶斯估计的角度来看，正则化项可认为是提供了模型的先验概率。

6.5 支持向量回归

  对于样本$(x,y)$，传统回归模型通常直接基于模型输出$f(x)$与真实输出$y$之间的差别来计算损失，当且仅当$f(x)$与$y$完全相同时，损失才为零。与此不同，支持向量回归假设我们能容忍$f(x)$与$y$之间最多有$\epsilon$的偏差，即仅当$f(x)$与$y$之间的差别绝对值大于$\epsilon$时才计算损失，如下图所示，相当于以$f(x)$为中心，构建了一个宽度为$2\epsilon$的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。

  引入松弛变量，得到如下优化问题，这里引入两个松弛变量是因为间隔带两侧的松弛程度可以不同。
$$\begin{array}{rl}& \underset{\omega ,b,\xi ,\stackrel{\ast }{\xi }}{\min }\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^m{\xi }_i+{\stackrel{\ast }{\xi }}_i\\ & s.t.f(x_i)-y_i⩽\epsilon +{\xi }_i,\\ & y_i-f(x_i)⩽\epsilon +\underset{i}{\overset{\ast }{\xi }},\\ & {\xi }_i⩾0,\underset{i}{\overset{\ast }{\xi }}⩾0\end{array}$$
  同样的，需要引入拉格朗日乘子进行优化求解，最后得到对偶问题，同时也可以引入核函数。

6.6 核方法

  给定训练样本$\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$，若不考虑偏移项$b$，则无论SVM还是SVR，学得的模型总能表示成核函数$\kappa (\mathbf{x},x_i)$的线性组合，同时可以得到如下被称为“表示定理”的更一般的结论。

  表示定理 令$\mathbb{H}$为核函数$\kappa$对应的再生核希尔伯特空间，${\Vert h\Vert }_{\mathbb{H}}$表示$\mathbb{H}$空间中关于$h$的范数，对于任意单调递增函数$\Omega :[0,\infty ]\mapsto \mathbb{R}$和任意非负损失函数$\ell :{\mathbb{R}}^m\mapsto [0,\infty ]$，优化问题
$$\underset{h\in \mathbb{H}}{\min }F(h)=\Omega ({\Vert h\Vert }_{\mathbb{H}})+\ell (h(x_1),h(x_2),...,h(x_m))$$
  的解总可写为
$$h^{\ast }(x)=\sum _{i=1}^m{\alpha }_i\kappa (\mathbf{x},x_i)$$
  表示定理对损失函数没有限制，对正则化项$\Omega$仅要求单调递增，甚至不要求$\Omega$是凸函数，意味着对于一般的损失函数和正则化项，上述优化问题的最优解都可以表示为核函数的线性组合。

  因此人们发展出一系列基于核函数的学习方法，统称为“核函数”。最常见的是通过“核化”（即引入核方法）来将线性学习器拓展为非线性学习器，比如SVM、PCA、LDA、聚类等等都可以引入核方法。

6.7 一些问题

（1）SVM、BP神经网络和C4.5决策树的异同？

• SVM是一种基于核函数和凸优化的算法，它的目标是在特征空间中寻找一个最大间隔超平面来分割两个类别。SVM的优点是能够处理非线性可分问题，泛化能力强，不容易过拟合。SVM的缺点是计算复杂度高，对参数和核函数的选择敏感，难以解释。

• BP神经网络是一种多层人工神经网络，它的目标是通过反向传播算法来调整网络权重，使得网络输出和期望输出之间的误差最小。BP神经网络的优点是结构灵活，能够拟合复杂的非线性函数，适用于语音、图像、自然语言等领域。BP神经网络的缺点是训练速度慢，容易陷入局部最优解，需要大量数据进行训练。

• 决策树是一种基于信息论和递归划分的算法，它的目标是构建一棵树状结构，每个内部节点表示一个特征判断，每个叶子节点表示一个类别或回归值。决策树的优点是易于理解和解释，非参数型，适合处理离散特征。决策树的缺点是容易过拟合，对噪声数据敏感，可能不稳定。

（2）线性判别分析与线性核SVM在什么条件下等价？

• 数据集是线性可分的，即存在一个超平面可以完美地分割两个类别；
• 数据集服从高斯分布，即每个类别的数据都符合一个多元正态分布；
• 数据集的协方差矩阵相同，即每个类别的数据都有相同的方差和相关性。

  如果数据集是线性可分的，那么LDA和线性核SVM都可以找到一个超平面来完美地分割两个类别，但这个超平面不一定是唯一的。其次，如果数据集服从高斯分布，那么LDA可以通过最大化两个类别均值之差来得到一个最优的投影方向，而线性核SVM可以通过最大化两个类别支持向量之间的距离来得到一个最优的分类器。最后，如果数据集的协方差矩阵相同，那么LDA和线性核SVM的目标函数都可以化简为两个类别均值之差的函数，从而得到相同的超平面。

（3）高斯核SVM与RBF神经网络之间的联系？

  高斯核SVM与RBF神经网络都使用了高斯核函数作为非线性映射的工具，将低维空间中的数据映射到高维空间中，从而实现线性可分或近似线性可分，当RBF神经网络的隐层神经元数设置为训练样本数，且每个训练样本对应一个神经元中心时，RBF神经网络与高斯核SVM的预测函数是相同的。

（4）SVM对噪声敏感的原因？

  SVM的目的是求出与支持向量有最大距离的超平面，以每个样本为圆心，该距离为半径作圆，可以近似认为圆内所有的点都与该样本属于相同分类，若圆内出现了噪声，那么该噪声所造成的错误分类也将最大化，因此SVM对噪声是敏感的。为了克服SVM对噪声敏感的问题，可以引入松弛变量和惩罚因子，构造软间隔分类器，允许一些样本不满足硬间隔约束条件，从而避免过拟合和模型过于复杂。