2.4.3 支持向量机算法

传统的统计研究方法都是基于大数定理而建立起来的渐近理论，要求训练样本数目足够多。然而在实际应用中，由于各个方面的原因，这一要求往往得不到满足。因此在小样本的情况下，建立在传统统计学基础上的机器学习方法，也就很难取得理想的学习效果和泛化性能。

针对小样本问题，以贝尔实验室弗拉基米尔·万普尼克（V. Vapnik）教授为首的研究小组从20世纪60年代开始，就致力于这个问题的研究，并提出了统计学习理论（Statistical Learning Theory，SLT）。支持向量机（Support Vector Machine，SVM）是SLT发展的产物。针对有限样本情况，SVM建立了一套完整、规范的基于统计学的机器学习理论和方法，大大减少了算法设计的随意性，克服了传统统计学中经验风险与期望风险可能具有较大差别的不足。目前，SLT和SVM已成为继人工神经网络以来机器学习领域中研究的热点，在模式识别、函数逼近、概率密度估计、降维等方面得到越来越广泛的应用。

与人工神经网络相比，SVM有坚实的统计学基础，它具有以下优点。

（1）以结构风险最小原理为基础，减小推广错误的上界，具有很好的推广性能，可解决神经网络的过拟合问题。

（2）问题的求解等价于线性约束的凸二次规划问题，具有全局最优解，可解决神经网络的局部极小问题。

（3）把原问题映射到高维空间，通过在高维空间构造线性分类函数来实现原问题的划分，引入核函数，可解决维数灾难问题。

2.4.3.1 支持向量机概述

对于图2.8所示的SVM原理示意，分割线1（平面1）和分割线2（平面2）都能正确地将两类样本分开，都能保证经验风险最小（为0）。这样的分割线（平面）有无限多条，但分割线1使两类样本的间隙最大，被称为最优分类线（平面）。最优分类线（平面）的置信范围最小。

设线性可分样本集为{ x _i , y _i }（ i =1,2,…, N ， x _i ∈R ⁿ ， y ∈{−1,1}是类别标号），在线性可分情况下会有一个超平面使这两类样本完全分开。 n 维空间中线性判别函数的一般形式为 g ( x )=[ w , x ]+ b ， x ∈{ x _i }则超平面描述为[ w , x ]+ b =0， w 是超平面的法向量。

将判别函数归一化，使两类样本都满足| g ( x )|≥1，则判别函数变为

此时样本点与超平面的最小距离为1/|| w ||，分类间隔为2/|| w ||。使2/|| w ||最大，等价于使|| w || ² 最小。满足式（2.27）并且使|| w || ² 最小分界面称为最优分界面。满足| g ( X )|=1的样本点，与分割线（平面）距离最小。这些样本决定了最优分类线（平面），被称为支持向量（Support Vector，SV），图2.8中带斜线的3个样本为支持向量。

根据统计学理论，求最优分类平面的问题可转换为下述优化问题。

利用拉格朗日优化方法把上面的优化问题转换为对偶化问题。

其中， α _i 为每个样本对应的拉格朗日乘子。这是一个在等式约束和不等式约束下的凸二次规化问题，存在唯一解，且解中只有一部分不为0，对应的样本就是支持向量。此时最优分类函数为

其中， 和 b *为最优解。

因为非支持向量满足 α _i =0，所以最优分类函数只需对支持向量进行运算，而 b *可根据任何一个支持向量的约束条件求出。

对于非线性可分问题，我们可以把样本 x 映射到某个高维空间中，然后在高维空间中使用上述的方法。

定义非线性映射 Φ ：R ⁿ → H ， H 为高维希尔伯特空间。

其中 ø _i ( x )是实函数，核函数 K ( x , y )=[ Φ ( x ), Φ ( y )]，则非线性SVM的目标函数变为

分类函数为

可以看出，它只涉及样本变换高维空间的内积运算，而这种内积运算可以用原空间的函数来实现。

2.4.3.2 核函数

对于线性不可分问题，有以下两种解决途径。

一是采用一般线性化方法，引入松弛变量，此时的优化问题为

其中， C 是可调参数，表示对错误的惩罚程度， C 的值越大惩罚越重。

二是采用万普尼克引入的核空间理论：将低维输入空间中的数据通过非线性函数映射到高维属性空间 H （也称为特征空间），将分类问题转换到属性空间进行求解。可以证明，如果选用适当的映射函数，输入空间中的线性不可分问题在属性空间将转换成线性可分问题。因此，如果能找到一个映射函数 K 使得 K ( x _i , x _j )=〈 Φ ( x _i ), Φ ( x _j )〉，这样在高维特征空间中实际上只需进行内积运算，而这种内积运算可以用输入空间中的某些特殊函数来实现，甚至没有必要知道具体的变换。这种特殊的函数称为核函数。根据泛函的有关理论，只要核函数满足Mercer定理的条件，它就对应某一变换空间中的内积。

Mercer定理是指任何半正定的函数都可以作为核函数，它将核解释为特征空间的内积，将低维向高维映射，却不需要过多地考虑维数对机器性能的影响。核函数是SVM的重要组成部分。根据Hilbert-Schmidt定理，只要变换 Φ 满足Mercer条件，就可以构建核函数。Mercer条件：给定对称函数 K ( x , y )和任意函数 φ ( x )≠0，满足约束

目前使用的核函数主要有以下4种。

① 线性核函数： K ( x , y )=[ x , y ]。

② 多项式核函数： K ( x , y )=([ x , y ]+ c ) ^p ，其中 c 为常数， p 为多项式阶数，当 c =0, p =1时函数为线性核函数。

③ 多层感知机核函数（Sigmoid）： K ( x , y )=tanh(scale×[ x , y ]-offset)，其中scale和offset是尺度参数和衰减参数。

④ RBF核函数： ，其中|| x − y ||为两个向量之间的距离， σ 为常数。

从上述的讨论可以看出，应用SVM进行分类的步骤为：①选择合适的核函数；②求解优化方程，获得支持向量及相应的拉格朗日算子；③写出最优分类平面的方程；④根据sgn( f ( x ))的值，输出类别。

图2.9所示为SVM的结构示意。SVM利用输入空间的核函数取代了高维特征空间中的内积运算，解决了算法可能导致的“维数灾难”问题。在构造判别函数时，不是对输入空间的样本做非线性变换，然后在特征空间中求解，而是先在输入空间比较向量（如求内积或某种距离），再对结果做非线性变换。这样大的工作量将在输入空间而不是在高维特征空间中完成。