支持向量机的基础理论解析

1.支持向量机的产生

支持向量机（support vector machine，SVM）是一种新兴的机器学习方法，由Vapnik等人在1995年提出。支持向量机基于统计学习理论，具有严格的理论分析和坚实的数学理论基础，具有理论完备、泛化性好、适应性强等优点，解决了过学习和高维数等问题，在机器学习领域中的是一种新方法和新研究方向。它不但综合了结构风险最小化原则、统计学习等方面的技术，而且在最小化经验风险的同时保证了算法的泛化能力。

2.支持向量机的数学模型

SVM想法最初是从线性可分的情况下的最优分类面提出的。在三维空间中，给定一组训练样本，如果每个样本点均能被某个平面划分到正确的类别中，并且与平面的距离最大，则该平面为最优平面。在三维以上的高维空间中，称这个最优分类平面为最优分类超平面。

二类分类中的最优分类平面如图9-9所示。

二类分类问题，即样本的种类只有两类。将这两类样本正确划分开的平面不唯一，根据支持向量机的基本思想，要使分类距离最大，这样的平面只有一个，这个平面就是最优分类平面。

假定一组样本集（x_i，y_i），i=1，2，…l，x_i∈Rⁿ，y_i=±1，其中x_i是n维空间中样本集的一个样本点，y表示x相应的类别。由于y的取值范围是+1或-1，因此属于二类分类问题。这个分类问题就是要利用这些给定的训练点推算出一个决策函数（超平面），学习的目标是将所有的样本点尽量正确地划分类别，并且使分类距离最大。首先考虑线性可分的情况。

图9-9 最优分类平面

分类超平面为

ω·x+b=0 （9-48）

ω·x_i+b≥+1，y_i=+1 （9-49）

ω·x_i+b≤+1，y_i=-1 （9-50）

式中，ω为超平面的法向矢量，即垂直于超平面的矢量；b为远点到超平面的距离。

超平面ω·x_i+b=1和ω·x_i+b=-1之间没有样本点，这种情况就是线性可分的。这两个超平面之间的距离为2/‖ω‖。因此分类距离最大就是最大化2/‖ω‖，这也等价于最小化：

因此，线性可分情况下构建最优分类超平面可以归结为式（9-52）的数学优化模型：

式（9-52）的最优解为式（9-53）的Lagrange函数鞍点：

式中，α_i≥0为Lagrange乘数；（x_i，y_i）为训练样本点数据。

令ω和b的偏导数为零，有

即

最优解还应该满足：

α_i[y_i（ω·x_i+b）-1]=0 （9-56）

由式（9-56）可以看出，大多数样本点对应的α_i为零，而只有非零的α_i对最优解才有意义，把α_i不等于零的训练点称为支持向量，支持向量机也是由此得名的。

式（9-52）整理后的最后形式为

实际上，大多数情况下训练点并非线性可分，即使是线性可分也难免有一些错误样本点的存在，这种情况可以看成是近似线性可分。与线性可分相似，需要引进两个新的变量C和ξ。近似线性可分的优化模型为

式中，C为惩罚因子；ξ为松弛因子。

线性近似可分的情况将分类的限制放宽，即引入了松弛因子ξ的作用。但对于只有放宽限制才能够被正确分类的点加以惩罚，即引入了惩罚因子C作用。同样，研究式（9-58）的Lagrange对偶问题：

核理论是支持向量机的核心理论。在非线性情况，核函数的引入可以把样本点从输入空间转换到某一高维空间，而在此高维空间中样本点是线性可分的。因此核函数的引进将非线性问题转化成了线性问题来解决。非线性的最优分类超平面的模型为

式中，K（x，y）为核函数，应用最为广泛的是高斯核函数：

K（x，y）=exp{-γx-y²} （9-61）

式中，γ为核半径。

3.支持向量机的参数选择

支持向量机的应用主要有分类和回归两种方法，但无论是分类还是回归，参数的选择都是至关重要的，参数选择的好坏将直接影响预测的结果。这里的参数主要是指惩罚因子C和高斯核半径γ。常用的算法由k-折交叉确认是验证算法和LOO误差算法。

k-折交叉确认是验证评价一个参数确定算法的有力工具。它的主要思想是：首先把所有的训练点分成k个互不相交的集合（所以称作k-折交叉确认），即L₁，L₂，…，L_n，这些集合中数据样本的个数不需要严格相等，只要大致相等就可以。然后进行k次数据训练与数据测试，即对i=1，…，k进行k次迭代。其中，第i次的算法是，选择L_i作为测试数据集合，其余的n-1个集合，即L₁，L₂，…，L_i-1，L_i+1，L_i+2，…，Ln为算法中的训练数据集合。与普通的支持向量机训练和测试一样，算法根据训练数据样本集合进行训练和得到支持向量机的决策函数模型后，对L_i进行测试。测试后将会得到本次测试错误分类点的个数M_i。k次迭代后，每次都会得到一个测试中错误分类样本点的个数，即得到了M₁，M₂，…，M_n，那么k次所有错误分类样本数据点的个数的和为

所有错误分类样本数据点的个数和与总样本训练点的个数之比为

以这个比值或者说是错误率来评价这个算法的优劣程度。这个比值称为k-折交叉确认误差。

在实际的应用情况中，确定k值的方法有两种。一种是令k=10，这样得到的是10-折交叉确认和10-折交叉确认误差。另一种是令k=n，这样也就意味着每次用n-1个数据样本进行训练，留一个数据样本进行测试。因此此算法称为留一法（leave-one-out），即常用的LOO算法。所以定义n-折交叉确认误差称为LOO误差。从以上两种方法来看，都可以最为参数选择的一个评价标准，以评价某一个参数选择的优劣程度。

4.结构风险最小化原则

从分类问题来看，分类问题的统计学理论是想办法找到一个使其实际风险达到最小或者期望风险达到最小的决策函数。然而，对于实际情况而言，我们知道的只是有限个样本点所组成的数据样本集合，而并不知道所有数据的分布情况，这样期望风险或实际风险就无法计算。

既然期望风险无法计算，可以将问题转化，用经验风险来代替期望风险。所谓经验风险就是指用已知的有限个样本点来代替整个数据集合的分布，也就是说，如果已知的样本点全部正确分类，那么就可以认为期望风险为零，也就是认为可以将所有的包括未知的数据样本进行正确划分。设给定的训练集为

T={（x₁，y₁），…，（x_l，y_l）}∈（Rⁿ×Y） （9-64）

式中：

x_i∈Rⁿ，Y=（-1，1）（i=1，…，l） （9-65）

则决策函数的经验风险为

式中，l为错误分类样本点的个数。

经验风险最小化原则属于传统的统计学习理论的范畴。当样本点个数很大时效果是非常理想的，理论上当样本个数趋于无穷大时，所得到的决策函数是理想的决策函数，经验风险大体上能够代表期望风险，也就是这个决策函数对所有的数据都能够正确分类。但是这只是一个理论上的情况，实际情况中，对于一个问题，我们不可能得到一个无穷大的样本，通常情况下所得到的都是小样本，这样经验风险就不能够代表期望风险，导致经验风险与期望风险有很大差别。

由经验风险最小化的分析可以看出，完全由经验风险来代替期望风险并不是十分合理的。因此引入结构风险最小化。结构风险的数学描述为(www.xing528.com)

式中，R为期望风险。

不等式右边的第一项为前面分析过的经验风险。而不等式右边的第二项是一个新的概念，称为置信区间。由式（9-67）可以看出，期望风险与经验风险和置信区间的和有关，经验风险和置信区间的和就是结构风险。可见，结构风险是期望风险的上界。在分析经验风险时阐述过，期望风险往往是不可计算的，因此想要最小化期望风险也是十分困难的。结构风险最小化示意如图9-10所示。

图9-10 结构风险最小化示意

置信区间描述了经验风险与期望风险之间差距。从图9-10中可以看出，它是与样本训练点个数成反比的，样本训练点个数越多置信区间越大，经验风险就越小，训练后的决策函数或者分类超平面就越不可靠，期望风险与经验风险的误差值就越大，支持向量机趋近于过学习状态。当训练样本点个数越小时，置信区间越小，训练后的决策函数越可靠。但是训练样本点个数少就意味着经验风险大，同样与实际风险有很大的误差。这时支持向量机趋于欠学习状态。

结构风险最小化综合考虑了经验风险与置信区间，并不是单独考虑最小化经验风险或单独考虑最小化结构风险。结构风险最小化在最小化经验风险和最小化置信区间之间找到了一个平衡点，使得经验风险和置信区间之和最小，这也就期望风险的上界使最小化，进而使得实际风险最小化。

5.支持向量机优化算法

在前文已经分析过，支持向量机的数学模型可以归纳为一个优化算法问题，这个优化算法应该属于一个凸二次规划问题。从理论上讲，普通的能求解凸二次规划的优化算法都可以使用。但是，求解支持向量机的凸二次规划问题还有一定的特殊性。

当在实际情况中处理的问题很大时，相对应的样本点的数量也十分庞大，因此，在计算与存储空间的要求就十分高。例如，存储支持向量机中核矩阵就与训练样本点的个数相关，核矩阵在内存中的存储空间与训练点个数的平方正相关。当训练样本点的个数达到4000时，在内存中就需要128M的空间来存放核矩阵数据。并且，这些核矩阵还需要进行计算，计算中的中间结果也需要保存，因此对求解支持向量机算法的时间复杂度和空间复杂度都十分苛刻。因此，一些普通的求解支持向量机的算法就难以胜任。

从式（9-60）可以看出，支持向量机的数学优化模型是比较完美的，它有许多特殊性质。例如，具有求解的稀疏性和凸优化算法的性质，这使得我们利用更少的内存空间设计出速度更快的算法成为可能。因此出现了一些专门求解支持向量机的优化算法，比较著名的支持向量机特殊优化算法有块选算法、分解算法、序列最小优化算法等。这些优化算法的基本思想是：将大规模的原问题分解成为一系列的小规模的子问题，进而将问题简化，逐个求解每一个子问题。这样求解的结果将逐渐逼近原问题的结果，逐步提高求解的精确度。这些算法的主要不同就是求解子问题的求解方法和迭代规则不同。

（1）块选算法 支持向量机的基本思想中提到，在支持向量机各众多训练样本点中，只有一少部分是起作用的，以及在分类线边缘上的那些训练点，它们对分类超平面也就是决策函数起着决定性的作用，这些训练点称为支持向量。如果能得到支持向量，那么剩下的就是非支持向量，这样就可以仅保存支持向量所对应的训练样本点，舍掉非支持向量对应的训练样本点，将会节省大量的内存空间，进而达到降低算法时间复杂度与空间复杂度的目的。

对于大规模的支持向量机问题，这个想法是十分必要的。因为在大规模的问题中支持向量的个数占总训练样本个数的比例是十分小的。因此算法效率的提高是十分可观的。如何确定哪些训练样本点是支持向量哪些不是，是块选算法和核心问题。

块选算法是一种较为简单的启发式算法。块选算法中的块指的是训练集中的子集。块选算法就是通过某种迭代方法逐步排除块中非支持向量的训练样本点，并把支持向量选入块中。首先任选一个块，在该块之中应用标准的支持向量机算法进行求解，得到α，然后调整当前块为新的块。保留块中的支持向量机α为零的矢量，舍掉其他训练点。块选算法的具体算法如下：

①随机选择参数，记作M，确定ε为终止条件，初始化：

α⁰=α⁰₁…α⁰_l^T=0 （9-68）

在工作集中选取初始块，记作W₀，令K=0。

②取出J_k中的分量，构建成α^k。求解如下子集的凸二次规划子问题：

解得α^j。

③由α^j选取

α^k+1=α^k₁₊₁…α^k_l+1T （9-70）

当J=J_k时，α^k+1取为α^k的相应分量；当J≠J_k时，α^k=α^k+1，判断α^k+1是否在精度ε内，如果满足，则认为近似解α^∗=α^k+1，迭代终止，否则转④。

④根据α^j构造支持向量对应的训练点组成的集合S_k，同时在集合中找出最不符合计算准则的点：

然后用被选择的训练点和S_k中的点对块进行更新，共同组成新的块W_k+1，记相应的下标集为J_k+1。

⑤令k=k+1，转②。

块选算法更加适用于支持向量所对应的数据样本点的数量与总样本点的数量之比很小的情况，这样能大幅度地提高算法的运算速度。然而，当支持向量所对应的数据样本点的数量与总样本点的数量之比很大的情况下，算法的效率提高就不是很明显了，算法的收敛速度也就比较缓慢。

（2）分解算法 从块选算法过程可以看出，块选算法仍然要存储由所有支持向量所对应的数据样本点组成的块，以及这些样本点的核矩阵数据。如果支持向量很多时，块选算法需要存储的数据依然十分多，这是块选算法中需要改进的地方。与块选算法不同，分解算法的特点是每次更换部分α，同时保持其他α值不变。要更新的α所组成的集合就是当前工作集。这样每次更新几个新的训练点到工作集中，就必须从工作集中去除相同数量的训练点。迭代过程中只是将当前工作集之外满足条件的样本点与工作集中的同等数量的训练点进行更新，工作集的规模及工作集中训练样本点的个数是不变的。因此，分解算法的工作集不断变化，迭代求解从而达到逼近α^∗的目的。

记下标B为工作集包含的训练点的下标的集合，将α的次序进行调整，则有

其中N与B互余，把y和H表示为

在工作集中，我们更新的目标是训练点α_B，固定的是α_N。由于H是对称的，即H=H^T，所以有

由于α_N是固定不变的，可知：

为常数，所以该优化模型等价于：

可以看出，式（9-77）表示的优化模型只需存储样本点阶数矩阵，存储量远比原来要少得多。分解算法的具体算法如下：

①确定B及终止条件ε，初始化：

令k=0。

②根据初始解，求解B。

③求解子规划，将工作集更新为

④若α^k+1满足终止条件，则取解为α∗=α^k+1，终止迭代。否则令k=k+1，转第②步。

（3）序列最小最优化算法（SMO） 从本质上讲，序列最小最优化算法是分解算法的一个特例。序列最小最优化算法的工作集容量为2，因此只需要更新两个样本点。这个算法中，工作集的容量最小，但子问题的规模和整个算法所要迭代的次数是一对矛盾。若子问题规模较小，那么要迭代的次数就会相应地较多。反之，子问题规模较大，那么要迭代的次数就会相应地较少。序列最小最优化算法属于前者。

由于工作集中只有两个训练样本点，因此所建立的优化问题比较简单，可适合用解析法进行求解。与普通的分解算法相比，序列最小最优化算法可能需要更多的迭代次数，但是每次迭代的计算量十分小。序列最小最优化算法的优点主要体现在其快速收敛性质上。除此之外，序列最小最优化算法还有其他重要的优点，如不需要存储核矩阵、不需要进行矩阵运算、算法实现容易等。后面提到的常用支持向量机工具LIBSVM就是基于序列最小最优化算法的。

序列最小最优化算法如下：

①设定求解精度ε，随机初始化最优解：

α⁰=α⁰₁…α⁰_l^T=0 （9-80）

令k=0。

②根据当前可行的近似解α^k，从集合{1，2，…，l}中选取的两个样本点组成集合{i，j}作为当前工作集。

③求解对应的优化问题，得到解：

α_B^∗=α^k+1_iα^k+1_j （9-81）

据此更新两个分量，得到新的近似解α^k+1。

④若α^k+1在精度范围之内，则得近似解α^∗=α^k+1，停止计算；否则，令k=k+1，转第②步。