下载掌阅APP，畅读海量书库
立即打开
|
1.4 支持向量机 |
Vapnik与其领导的贝尔实验室从20世纪60年代开始致力于统计学习理论的研究，其为支持向量机打下了坚实的理论基础。支持向量机以统计学习理论的VC维理论和结构风险最小化原则为基础，其良好的泛化能力来源于有限样本信息在模型的学习能力和复杂性之间合适的比例。它具有简洁的数学形式、直观的几何解释、完备的理论基础和良好的推广能力，有效地克服了“维数灾难”，其学习训练过程转化为一个二次规划问题，避免了局部最优解，较好地解决了非线性、高维及小样本模式识别中的实际问题，目前已经成为机器学习领域研究的热点之一，并成功应用推广到分类、函数拟合和时间序列预测等其他机器学习中。
统计学习理论提出的结构风险最小化原则以降低机器学习复杂度为出发点。学习机器以此原则为基础在可容许的经验风险范围内，总是采用具有最低复杂度的函数集。统计学习理论与神经网络不同，它是建立在坚实的数学基础之上的，具有复杂和完整的理论体系。目前由于统计学习理论受到关注的时间比较短，而导致工程上应用还比较少，但是统计学习理论在理论上已经比较成熟，为解决小样本的问题提供了统一的框架。其核心概念就是用VC维来描述学习机器的复杂度，并以VC维为出发点推导出了表示学习机器推广能力的界的概念。统计学习理论在不需要利用样本数趋于无穷大的渐进性条件的情况下致力于寻找在小样本情况下学习问题的最优解，这使得在小样本情况下统计学习理论同样具有良好的推广价值。
1 . VC 维
指示函数集的VC维是指用来刻画指示函数集容量的系数h。如果指示函数集的生长函数以参数h的对数函数为界，则该指示函数的VC维等于h且是有限的；以线性函数为生长函数的指示函数集的VC维是无穷大。
VC维反映了学习机器复杂程度和函数集的学习能力。目前只知道一些特殊函数集的VC维，比如在n维实数空间中线性函数的VC维是n+1。关于计算任意函数集VC维的通用理论还没成型。比较复杂的学习机器的VC维就更不容易确定，因为VC维除了与函数集有关外，还受学习算法的影响。如何计算给定的函数集的VC维是当前统计学习理论中一个有待解决的问题。
2. 推广的界
在统计学习理论中，推广的界是指实际风险和经验风险之间的关系。它们是发展新的学习算法和分析学习机器性能的重要理论基础。对于两类分析问题中指示函数集里的函数，经验风险和实际风险至少以1-η的概率满足下式：
式中，h为函数集的VC维；n为训练样本数。
式（1.15）说明学习机器在经验风险最小化原则下的实际风险由两部分组成，第一部分为训练样本的经验风险，第二部分称为置信范围（即VC置信，它是函数集的训练样本数目和VC维的函数），并且受置信水平1-η的影响。为了说明简洁，式（1.15）可写为：
式（1.16）给出了真实风险和经验风险间差距的上界，反映了机器学习在经验风险最小化原则下的推广能力。
3. 结构风险最小化原则
统计学习理论提出了结构风险最小化原则（SRM原则），用它来解决经验风险与置信范围之和最小化的泛函问题。SRM原则可以称为支持向量机和统计学习理论的基石。SRM原则的思想如下：
把函数集S={f （x，α），α∈∧}分解为一个函数子集序列：
让子集能够按照VC维的大小排列：
此时同一子集S k 的置信范围相同。
SRM原则的思想是最小化期望风险，即选择经验风险与置信范围之和最小的子集S ＊ ，S ＊ 中使经验风险最小的函数就是所求的最优函数。其中：
SRM原则提供了一种不同于经验风险最小化的学习机器设计原则，在实际应用中，支持向量机是“保持经验风险固定，然后最小化置信范围”这条原则的具体实现。
支持向量机（SVM） [22] 是于1992—1995年完成的，它较好地实现了结构风险最小化的思想。对于线性可分两分类问题，假设 n 个样本的训练集D={（x i ，y i ） | i=1，2，…，n}，x i ∈R n ，y i ∈{+1，-1}能被超平面H： w ·x+b=0无误地分开，并且超平面到离超平面最近的向量的距离最大，如图1-5所示。
图1-5 支持向量机最优超平面示意图
分类间隔是平行于分类超平面且离分类超平面最近的样本的平面H 1 和H 2 之间的距离，而且间隔=2 w 。
为了使超平面的分类间隔2 w 最大化，应该使 w = ww 最小化，并且保证H 1 和H 2 之间没有样本存在，即样本集D中所有的n个样本 （ x i ， y i ） 都应该满足下式：
两个条件合并为：
因此，支持向量机的目的是采用式（1.22）构造分类超平面对所有样本正确分类：
SVM 的核心思想之一就是使分类间隔最大。因此使 w 2 = w T w 最小是实现SRM原则中对函数复杂性的选择，即让VC维的上界最小。
对于这个凸二次线性规划优化问题，其解可以通过求解拉格朗日函数获得，把构建最优超平面的问题转化为一个简单的对偶二次规划问题：
这是一个不等式约束下的凸二次规划问题，存在唯一解。
若
为上式的最优解，则：
即最优分类面的权系数向量是训练样本向量的线性组合。
通常对多数样本而言，其对应的
等于零。其他使
的任意样本即使发生来回移动，只要不超越标准超平面，就不会对分类面的求解产生影响
[23]
。根据KKT条件
[24]
（拉格朗日乘子与不等式的乘积），这个优化问题的解还必须满足：
通过选择不为零的
，代入上式进而求解分类阈值b
＊
。
求解上述问题后得到的最优分类函数为：
式中sgn（·）是符号函数。
根据泛函的理论，满足Mercer条件 [25] 的核函数K （x i ，x j ）对应某一变换空间中的内积（x i ·x j ）。对非线性问题，若采用适当的核函数K（x i ，x j ）可以在不增加计算复杂度的条件下实现某一非线性变换后的线性分类。此时目标函数变为：
而相应的最优分类函数为：
这就是支持向量机。
在支持向量机中核函数决定了特征空间的结构，常用的主要有以下三类。
（1）多项式核函数：
（2）径向基函数（RBF）：
（3）Sigmoid核函数：
支持向量机在特征空间中构建最优超平面从而得到全局最优。它是统计学习理论的具体实现，与神经网络为代表的传统机器学习方法相比，具有以下 4 个重要的优点 [26] ：
（1）它解决了小样本学习问题。支持向量机是专门针对有限样本情况的，其目标不仅仅是样本数趋于无穷大时的最优值，而是得到现有信息下的最优解，其在解决小样本学习问题中表现出了许多特有的优势。
（2）它解决了高维问题。在解决高维问题时，神经网络比较容易陷入局部最优，为了避免这一点，支持向量机只选择具有最大分类间隔的最优超平面，使用大间隔因子来控制训练过程。从而使其在满足分类要求的情况下，具有最高和最广的特性。
（3）它解决了结构选择的难题。支持向量机的结构相当简单，采用固定的三层结构，隐含层节点数由支持向量机确定。
（4）它解决了局部极值问题。支持向量机得到的解是理论上的全局最优解，因为算法最终转化为凸二次规划的优化问题。