2.12　支持向量机（SVM）

支持向量机（Support Vector Machine，SVM）是一种分类算法，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等机器学习问题中。

2.12.1　什么是SVM

支持向量是指在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。

SVM是通过支持向量运算的分类器。

在一个二维环境中，其中点R、S、G和其他靠近中间g线的点都可以看作为支持向量，它们可以决定分类器，即g线的具体参数。SVM示意图如图2-21所示。

SVM是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割。分割的原则是边界最大化，最终转化为一个凸二次规划问题来求解。其由简至繁的模型包括以下几点。

（1）当训练样本线性可分时，通过硬边界（Hard Margin）最大化，学习一个线性可分支持向量机。

（2）当训练样本近似线性可分时，通过软边界（Soft Margin）最大化，学习一个线性支持向量机。

（3）当训练样本线性不可分时，通过核技巧和软边界最大化，学习一个非线性支持向量机。

2.12.2　SVM能解决的问题

SVM能解决的问题可分为两类。

（1）线性分类

在训练数据中，每个数据都有n个属性和一个二分类类别标志，我们可以认为这些数据在一个n维空间里。我们的目标是找到一个n-1维的超平面，这个超平面可以将数据分成两部分，每部分数据都属于同一个类别。

这样的超平面有很多，假如我们要找到一个最佳的超平面。此时，增加一个约束条件：要求这个超平面到每边最近数据点的距离是最大的，成为最大边距超平面。这个分类器即为最大边距分类器。

（2）非线性分类

支持向量机的一个优势是支持非线性分类。它可以结合使用拉格朗日乘子法（Lagrange Multiplier）、KKT（Karush Kuhn Tucker）条件，以及核函数可以生成非线性分类器，进而支持非线性数据的分类。

2.12.3　核函数特点及其作用

引入核函数的目的是把原坐标系里线性不可分的数据用核函数Kernel投影到另一个空间，尽量使得数据在新的空间里线性可分。

核函数方法的广泛应用，与其特点是分不开的。

（1）核函数的引入避免了“维数灾难”，大大减少了计算量。而输入空间的维数n对核函数矩阵无影响。因此，核函数方法可以有效处理高维输入。

（2）无须知道非线性变换函数的形式和参数。

（3）核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。

（4）核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。

2.12.4　SVM为什么引入对偶问题

在SVM中引入对偶问题，主要有以下几个方面的原因。

（1）对偶问题将原始问题中的约束转为对偶问题中的等式约束，对偶问题往往更加容易求解。

（2）可以很自然地引用核函数（拉格朗日表达式里面有内积，而核函数也是通过内积进行映射的）。

（3）在优化理论中，目标函数f（x）会有多种形式：如果目标函数和约束条件都为变量x的线性函数，则称该问题为线性规划；如果目标函数为二次函数，约束条件为线性函数，则称该最优化问题为二次规划；如果目标函数或者约束条件均为非线性函数，则称该最优化问题为非线性规划。每个线性规划问题都有一个与之对应的对偶问题，对偶问题有非常良好的性质，以下列举几个。

• 对偶问题的对偶是原问题。

• 无论原始问题是否是凸的，对偶问题都是凸优化问题。

• 对偶问题可以给出原始问题一个下界。

• 当满足一定条件时，原始问题与对偶问题的解是完全等价的。

2.12.5　如何理解SVM中的对偶问题

在硬边界支持向量机中，问题的求解可以转化为凸二次规划问题。

假设优化目标为，则

其中w、b是模型参数。SVM中的对偶问题求解步骤如下。

（1）转化问题。

上式等价于原问题，若满足（2-65）中不等式约束，则（2-66）在求max时，必须取0，与（2-65）等价；若不满足（2-65）中不等式约束，则（2-66）在求max时，会得到无穷大。交换min和max获得其对偶问题：

交换之后的对偶问题和原问题并不相等，上式的解小于或等于原问题的解。

（2）如何找到（2-65）的最优值中最好的下界?

若（2-68）、（2-69）无解，则v是问题（2-65）的一个下界。若（2-68）、（2-69）有解，则

根据逆否命题，若

则（2-68）、（2-69）无解。

那么v是问题（2-65）的一个下界。要求得一个好的下界，取最大值即可

（3）令

p*为原问题的最小值，对应的w，b分别为w*，b*，则对于任意的a>0：

那么是问题（2-65）的一个下界。

此时，取最大值即可求得好的下界，即

2.12.6　常见的核函数

常见的核函数如表2-20所示。

2.12.7　SVM的主要特点

SVM的主要特点如下。

（1）SVM算法的理论基础是非线性映射，SVM利用内积核函数向高维空间进行非线性映射。

（2）SVM的目标是对特征空间划分得到最优超平面，SVM算法的核心是最大化分类边界。

（3）支持向量是SVM的训练结果，在SVM分类决策中起决定作用的是支持向量。

（4）SVM是一种有坚实理论基础的新颖的适用小样本学习方法。它基本上不涉及概率测度及大数定律等问题，也简化了通常的分类和回归等问题。

（5）SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

（6）少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本，而且注定了SVM算法简单，具有较好的“鲁棒性”。这种鲁棒性主要体现在：

• 增删非支持向量样本对模型没有影响。

• 支持向量样本集具有一定的鲁棒性。

• 在有些成功的应用中，SVM对核的选取不敏感。

（7）SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。

（8）SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。

（9）SVM在小样本训练集上能够得到比其他算法好很多的结果。SVM优化目标是结构化风险最小，而不是经验风险最小，避免了过拟合问题，通过得到对数据分布的结构化描述，降低了对数据规模和数据分布的要求，有优秀的泛化能力。

（10）SVM是一个凸优化问题，因此具有局部最优解一定是全局最优解的优点。

2.12.8　SVM的主要缺点

SVM主要有以下缺点。

（1）SVM算法对大规模训练样本难以实施。SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量的，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时，该矩阵的存储和计算将耗费大量的机器内存和运算时间。如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测没有使用SVM分类器，而是使用简单的朴素贝叶斯分类器，或者是使用逻辑回归模型分类。

（2）用SVM解决多分类问题存在困难。经典的SVM算法只给出了二类分类的算法，而在实际应用中，一般可以通过多个二类SVM的组合来解决多类的分类问题，主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决多类的分类问题。

（3）对缺失数据敏感，对参数和核函数的选择敏感。SVM性能的优劣主要取决于核函数的选取，目前比较成熟的核函数及其参数的选择都是人为根据经验来选取的，带有一定的随意性。在不同的问题领域，核函数应当具有不同的形式和参数，所以在选取时应该引入领域知识，但是目前还没有好的方法来解决核函数的选取问题。

2.12.9　逻辑回归与SVM的异同

逻辑回归与SVM有以下几个相同点。

（1）逻辑回归和SVM都是分类算法。

（2）逻辑回归和SVM都是监督学习算法。

（3）逻辑回归和SVM都是判别模型。

（4）如果不考虑核函数，那么逻辑回归和SVM都是线性分类算法，也就是说它们的分类决策面都是线性的。

注：逻辑回归也是可以用核函数的，但逻辑回归通常不采用核函数的方法。

逻辑回归与SVM有以下几个不同点。

（1）逻辑回归采用log损失，SVM采用合页（Hinge）损失。

逻辑回归的损失函数：

SVM的目标函数：

逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值。

SVM基于几何边界最大化原理，认为存在最大几何边界的分类面为最优分类面。

（2）逻辑回归对异常值敏感，SVM对异常值不敏感。

SVM只考虑局部的边界线附近的点，而逻辑回归考虑全局。LR模型找到的那个超平面，是尽量让所有点都远离它，而SVM找到的那个超平面，只是让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。

SVM改变非支持向量样本并不会引起决策面的变化。在逻辑回归中改变任何样本都会引起决策面的变化。

（3）计算复杂度不同。对于海量数据，SVM的效率较低，逻辑回归效率比较高。

当样本较少，特征维数较低时，SVM和LR的运行时间均比较短，SVM的运行时间更短一些。逻辑回归的准确率明显比SVM高。当样本稍微增加时，SVM的运行时间开始增长，但是准确率赶超了逻辑回归。SVM的运行时间虽长，但在可接受范围内。当数据量增长到20000，特征维数增长到200时，SVM的运行时间剧烈增加，远远超过了逻辑回归的运行时间，准确率却和逻辑回归相差无几，这其中主要原因是大量非支持向量参与计算，造成SVM的二次规划问题。

（4）对非线性问题的处理方式不同。

逻辑回归主要靠特征构造，必须组合交叉特征，特征离散化。SVM也可以这样，还可以通过核函数。利用核函数，SVM可以通过对偶求解高效处理。逻辑回归则在特征空间维度很高时，表现较差。

（5）SVM的损失函数自带正则。

SVM损失函数中的项，认为SVM是结构风险最小化算法的主要原因，而逻辑回归必须另外在损失函数上添加正则项。

（6）SVM自带结构风险最小化，逻辑回归则是经验风险最小化。

（7）SVM会用核函数，逻辑回归一般不用核函数。