3.4 支持向量机

支持向量机（Support Vector Machine,SVM）是由Cortes和Vapnik等人于20世纪90年代，根据统计学习理论中的结构风险最小化原则提出的一种经典的机器学习方法，现已发展为机器学习领域的一个重要分支。它在有限训练样本的学习精度和泛化能力（无错误地识别任意样本的能力）之间取得良好的平衡，从而获得较好的推广应用 ^[16] 。目前，在模式识别方面，SVM 已被应用于手写数字识别、语音鉴定、目标识别和照片人脸识别等分类中；在回归估计方面，SVM 被应用到一系列预测结果的基准实践中。

在多数情况下，SVM 的表现都优于其他机器学习方法的表现。尤其是在密度估计和方差分析（Analysis of Variance,ANOVA）分解中的应用，更加表现出了SVM的优势。

3.4.1 支持向量机主要思想

SVM 主要思想是针对两类分类问题的，寻找一个超平面作为两类训练样本点的分割，以保证最小的分类错误率。在线性可分的情况下，存在一个或多个超平面使得训练样本完全分开，SVM 的目标是找到其中的最优超平面，最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的平面；对于线性不可分的情况，可使用非线性核函数将低维输入空间线性不可分的样本转化为高维特征空间，从而使其线性可分。

3.4.2 支持向量机基础理论

通俗来讲，SVM 是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即 SVM 的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

支持向量机的理论有三个要点 ^[17] ，即：

（1）最大化间隔。

（2）核函数。

（3）对偶理论。

下面先简单介绍一下这些要点。

1． 最大化间隔

在样本线性可分的情况下，可行的分类超平面可能会有很多，如图3-6中的 L 1 、L 2 和L 3 。

那么怎么选择一个最好的呢？从图3-6可以直观地看出，L 2 比另外两条分界线要更好，这是因为L 2 离样本的距离更远一些，让人觉得确信度更高。这好比人（相当于样本）站得离悬崖边（分类边界）越远，人就会感到越安全（分类结果是安全还是危险）。从统计的角度讲，由于正负样本可以看作从两个不同的分布随机抽样而得，分类边界与两个分布的距离越大，抽样出的样本落在分类边界另一边的概率就会越小。

SVM 正是基于这种直观思路来确定最佳分类超平面的：通过选取能够最大化类间间隔的超平面，得到一个具有高确信度和泛化能力的分类器，即最大间隔分类器。

1）间隔

既然 SVM 的目标是最大化间隔，便要先对“间隔”进行定义。所谓间隔，就是分类超平面与所有样本距离的最小值，表示为：

其中，l表示分类超平面，N为样本个数，x i 为第i个样本。接下来还需要定义样本到超平面的“距离”dist（l,x）。

假设任意一个样本点x 0 ，其在分类超平面上的投影记作 。对于分类超平面（w ^T x+b）=0，知道它的法向量是 w，法向量的方向可以由法向量除以其模长所得： 。将dist（l,x i ）记为d（d≥0），则可以得到：

等式两边同时左乘w ^T 并加上 b，并且利用超平面上的点 的性质，可以得到：

记y∈{1,1}为分类标签，由于 ，可以以此消去上式的绝对值。

综上所述，可以得到对于分类超平面l和N个样本x i 的“间隔”的表达式：

2）最大化

有了上述定义的间隔，接下来就是求解能使间隔最大化的参数 w 和 b，即求解以下优化函数：

令 ，上述优化函数也可以写成如下等价的形式：

其中的约束条件是为了满足对“间隔”的定义。

2． 核函数

核函数的定义如下。

设s是输入空间（欧氏空间或离散集合）,H为特征空间（希尔伯特空间），如果存在一个从 s 到 H 的映射φ（ x）: s→H。使得对所有的 x, z∈s，函数K（x,z）=φ（x）.φ（z），则称K（x, z） 为核函数，φ（x）为映射函数，φ（x）.φ（z）为x,z映射到特征空间上的内积。由于映射函数十分复杂，难以进行计算，在实际中，通常都是使用核函数来求解内积，其计算复杂度并没有增加，映射函数仅仅作为一种逻辑映射，表征着输入空间到特征空间的映射关系。

常用的核函数主要有以下几种。

（1）线性（Liner）核函数：

（2）多项式（Polynomial）核函数：多项式核函数经常表示非线性的特征映射，常用的形式为：

（3）高斯（Gaussian）核函数（又称为径向基函数，RBF）：在支持向量机的研究与应用中最常用的一个核函数。

（4）指数型径向基核函数：

当所讨论的问题是不连续的，即离散点时，它所表示的便可应用于产生一个线性的分段解。

（5）Sigmoid（或2层感知机）：

其中，a 是一个标量，v 为位移参数。此时，SVM 是包含一个隐层的多层感知器，隐层节点数由算法自动确定。

（6）傅里叶（Fourier）核函数：

此外，还有条件正定核函数（CPD核函数） ^[18] ：

它并不满足 Mercer 条件，但却可以用于核学习方法中。另外还有样条核函数及张量积核函数等。

3． 对偶理论（Duality Theory）

1947年，美籍匈牙利数学家冯·诺依曼创立了对偶理论。线性规划（Linear Programming,LP）是运筹学中研究较早、发展较快、应用广泛、方法较为成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。线性规划中普遍存在配对现象，即对每一个线性规划问题，都存在另一个与它有密切关系的线性规划问题，其中之一称为原问题，而另一个称它的对偶问题。对偶理论就是研究线性规划中原问题与对偶问题之间关系的理论。对偶问题有许多重要的特征，它的变量能提供关于原问题最优解的许多重要资料，有助于原问题的求解和分析。对偶问题与原问题之间存在的具体关系如表3-8所示。

原—对偶优化方法如下。

1）凸优化问题

对于如上线性优化问题，若f（x）,ω（x）是凸函数，可行解集合x是可行域F上的凸集，则称这类优化问题为凸优化问题。

凸优化问题是线性规划中一种重要的特殊情形，它具有很好的性质。如果凸规划的目标函数是严格凸函数，又存在极小点，那么它的极小点是唯一的，局部极小点就是全局极小点。

2）原—对偶算法

网络问题一般被视为具有特殊限制式结构的线性规划问题。因此，一般用来求解线性规划问题的方法亦可被应用于求解网络问题。原—对偶算法（Primal-Dual Algorithm）作为一种解决复杂调度和整数规划问题的有效方法，已经被成功应用于网络调度问题。它的灵活性为许多问题提供适当的解决方案，已成为如整数规划、线性规划、组合优化和非线性规划等最优化问题的一个最好的解决工具。应用原—对偶算法的前提条件是待求解优化问题必须是严格的凸优化问题。其核心思想是设计算法通过求解原优化问题的对偶问题，来得到原问题的最优解。

采用子梯度算法来求解对偶问题，现对算法基本流程表述如下。

（1）用拉格朗日松弛法对造成原问题不易解决的约束条件进行松弛，并使得目标函数仍保持线性，令λ,η为拉格朗日乘子，其中要求满足λ≥0，则对原问题松弛后的拉格朗日函数如下：

（2）求原问题的对偶问题，并推知 ，对偶问题为

（3）子梯度法求解对偶问题。

和其他数学优化方法相比，原—对偶算法具有一些不可比拟的优点。最突出的特点是通过使用拉格朗日乘法原则放松了原数学模型中的约束条件，这样可以把原问题中耦合在一起的原变量分离，把复杂的原问题分成几个独立且易解决的子问题进行求解，降低算法的复杂度，能够实现分布式计算。

接下来介绍一下损失函数和结构风险最小化。

4． 几种常用的损失函数

1）l p 损失函数

其中，p≥1, 表示 l p 范数。显然常用的平方损失和绝对值损失是 l p 损失函数的特例。在回归问题中，平方损失因其光滑性有着广泛的应用（如最小二乘法估计）。而近年来，由于计算能力的改进，绝对值损失也因其良好的稳健性而逐渐成为热点（如最小一乘法估计）。

2）∈-不灵敏损失函数

支持向量机（SVM）就是采用上述损失函数的一种处理高维问题的学习算法。

3）logistic损失函数

logistic 损失函数多用于分类问题的研究。近期研究发现，AdaBoost 可以看成采用上述损失函数的函数空间的梯度下降算法 ^[19] 。

5． 结构风险最小化

结构风险最小化思想：首先，把函数集分解为一个函数子集序列，使各个子集能够按照复杂性大小排列，也就是按照VC维（Vapnik-Chervonenkis Dimension）大小排列，这样在同一个子集中置信范围就相同。其次，在每个子集中寻找最小经验风险，通常它随着子集复杂度的增加而减少。最后，选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小，这个子集中使经验风险最小的函数就是要求的最优函数。

结构风险最小化原则为我们提供了一种不同于经验风险最小化的更科学的学习机器设计原则。但是，实施这一原则却非常困难，关键是如何构造函数子集结构。遗憾的是，目前尚无关于如何构造预测函数子集结构的一般性理论。支持向量机是一种比较好的实现结构风险最小化思想的方法。

3.4.3 支持向量机原理

1． 支持向量机（SVM）

支持向量机（SVM）是一种分类算法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。

也可以这么表达，SVM 是一种以统计学习理论为基础，具有较好的分类能力和泛化能力的分类算法。SVM主要有以下3种情况 ^[20] 。

1）线性可分情况

设训练集T ={（x 1 .y 1 ）,…,（x i .y i ）}∈（x× y） ^l ，其中，x i ∈x∈R ⁿ ,y i ∈y∈{1,1}, i= 1,2,…,l，如果存在w∈R ⁿ ,b∈R和正数ξ，使得对于所有使y i =1下标 i，都有（w.x i ）+b≥ξ。而对于所有使y i =1的下标 i，都有（w.x i ）+b≤ξ，那么称该训练集 T是线性可分的，其对应的分类问题也是线性可分的，如图3-7所示。

图3-7中的圈和叉代表待分类的两类样本，H就是要求的最优分类超平面，H 1 和H 2 是与最优分类面平行的直线，且分别通过这两类样本里距离 H 最近的样本点。从图3-7可以看出，在 H 1 和 H 2 之间可以有很多条直线与它们平行，但是能够保证两类样本之间的最近距离最大的却只有最优分类超平面。

SVM 是一种有监督的机器学习算法，即需要通过对训练样本进行训练得到 SVM，获得最优分类超平面，然后根据训练结果进行分类。由图3-7可知，有分类能力的平面表述如下：

可以看出，分类间隔是 ，要使得分类间隔最大，那么需要 尽可能小，因此最优分类超平面可以通过求解下式得到：

将其转化成对偶形式：

求解得到拉格朗日系数的值 a ^* ，则 ，选取 a ^* 的一个正分量 ，并据此计算 ，此时的分类函数为：

2）线性不可分情况

线性可分就是在样本存在的空间中，可以找到可能正确划分训练样本的最优分类超平面。但在现实世界中，得到的样本所组成的训练样本集往往都无法找到这样一个使得所有训练样本关于分类超平面的间隔都是正值的分类超平面。然而仍然希望找到一个超平面，那么就必须适当软化条件，允许存在不满足约束条件y i （（w.x i ）+b）≥1的样本。因此，最优分类超平面的求解就表述为：

将其转化为对偶形式为：

求解得到拉格朗日系数的值 a ^* ，则 ，选取 a ^* 的一个小于 c 的正分量 ，并据此计算 ，此时的分类函数为：

对于那些需要软化的条件，将它们分为两类：一类是虽不满足 KKT（Karush-Kuhn-Tucker）条件但是可以被正确划分的点；另一类是不满足 KKT 条件也不能被正确划分的点。对于第一类点，通过调整惩罚参数 c 来使松弛变量ξ i 不取太大的值；对于第二类点，由于该类点往往无法对提高分类器性能提供任何帮助，还会使得分类器的计算负担大大增加，造成过学习现象，因此应该剔除掉。

遇到线性不可分时，常用做法是把样例特征映射到高维空间中去，如图3-8所示。

线性不可分映射到高维空间，可能会导致维度大小高到可怕的程度，导致计算复杂。核函数的价值在于它虽然也是将特征从低维到高维转换，但核函数事先在低维上进行计算，而将实质上的分类效果表现在了高维上，这避免了直接在高维空间中的复杂计算。

3）非线性可分情况

即便是引入了松弛变量，用直线划分有些问题还是存在很大的误差，即输入空间中不存在该问题的线性分类超平面，这种问题叫非线性可分问题。处理这类问题时，通过某种映射使得训练样本线性可分，即将输入空间映射到高维空间中后，通过训练支持向量机得到该问题在高维空间中的最优分类超平面，解决该类分类问题。

设原问题对应输入空间R ⁿ 的训练集为：

则对应的高维空间的新训练集为：

于是相应特征空间的原问题为：

转化为对偶问题为：

其中，K（x i .x j ）=φ（x i ）.φ（x j ）。

求解得到拉格朗日系数的值 a ^* ，则 ，选取 a ^* 的一个正分量 （支持向量），并据此计算 。

2．支持向量机（SVM）的优点

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

（2）假设现在你是一个农场主，圈养了一批羊群，但为预防狼群袭击羊群，你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢？你很可能需要依据羊群和狼群的位置建立一个“分类器”，图3-9是几种不同的分类器解决方案。

比较图3-9中这几种不同的分类器，可以看到支持向量机（SVM）完成了一个很完美的解决方案。这从侧面简单说明了支持向量机（SVM）使用非线性分类器的优势，而逻辑模式及决策树模式都使用了直线方法。明显看出，支持向量机的方案要好过其他两种方案。 b8BhEXMqHiMknQIsMlS1mj0ek+C/t8V62hwwUxnxh1qA5WwoPS71SvSdtUOD3Jny