机器学习统计学习理论与支持向量机算法

机器学习统计学习理论与支持向量机算法第一页，共107页。

1引言第二页，共107页。统计学习理论讨论的是基于数据的机器学习问题研究如何从一些观测数据(样本)出发得出目前尚不能通过原理分析得到的规律，即基于观测设计优化过程，然后利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预测。主要任务：对于一种未知的依赖关系，以观测为基础对它进行估计。2.1引言第三页，共107页。现有机器学习方法共同的重要理论基础之一是统计学传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。第四页，共107页。统计学习理论(StatisticalLearningTheory或SLT)是一种专门研究小样本情况下机器学习规律的理论VladimirN.Vapnik等人从六、七十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展,统计学习理论开始受到越来越广泛的重视。第五页，共107页。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。在这一理论基础上发展了一种新的通用学习方法——支持向量机(SupportVectorMachine或SVM)，它已初步表现出很多优于已有方法的性能。

第六页，共107页。

2统计学习理论第七页，共107页。经典的统计基础存在两个理论缺陷没有对经验风险最小化原则下统计学习的一致性进行分析，不能保证经验风险的最小值(或下确界)收敛到(或依概率收敛到)期望风险的最小值(或下确界)。大数定律描述的是一个极限过程，不对收敛速度进行分析，那么在样本数目有限的情况下，以频率代替概率(均值代替期望)并不一定能得到好的近似。2.2统计学习理论的形成与发展第八页，共107页。针对这两个问题，统计学习理论从理论上系统地分析经验最小化原则成立的条件，建立了学习过程收敛速度的界，进而提出了小样本归纳推理原则，并给出控制学习过程的推广能力的方法。到20世纪90年代，统计学习理论已基本成熟。1995年，Vapnik完成专著《TheNatureofStatisticalLearningTheory》，这是统计学习理论走向成熟和得到正式承认的标志。

第九页，共107页。围绕学习问题的一般过程统计学习理论分成从理论向实践渐进的4个部分学习过程一致性的理论（一个基于ERM原则的学习过程一致充分必要条件是什么？）一个基于经验风险最小化原则的学习过程，满足怎样的条件时，它的经验风险与实际风险趋向一致。在分类问题中存在对应的充分必要条件，而对拟合问题目前仅存在充分条件。学习过程收敛速度的理论（这个学习过程收敛的速度有多快？）如果学习过程的经验风险与实际风险趋向一致，那么它们间的接近速度随着训练样本数的增加，是如何变化的，哪些因素控制着它们接近的速度。

第十页，共107页。控制学习过程泛化能力的理论（如何控制这个学习过程的收敛速度，即推广能力？）采用前两部分的结论改进学习过程，认为结构风险最小化原则，而不是经验风险最小化原则，可以使学习过程的经验风险与实际风险最终并且尽可能快地趋向一致。构造学习算法的理论采用前三部分的结论

（如何构造能够控制推广能力的算法？）在分类和拟合问题中构造现实的学习算法。它遵循结构风险最小化原则从而较传统算法有更好的泛化能力。支持向量机SVM是基于该理论最早实现的，也是目前最有影响的分类回归算法之一。

第十一页，共107页。学习过程的一致性及收敛速度学习过程可以一般地表示如下

设有定义在空间Z上的概率测度F(Z)，考虑函数的集合Q(z,a),

aÎL

（L为任意集合，它可以为一个标量集、向量集或抽象元素集）学习的目的是最小化风险泛函

R(a)=

òQ(z,a)dF(z)，aÎL

（2.1）

其中概率测度F(Z)

未知，但给定了一定的独立同分布样本

z1,…,zt

（2.2）

这种一般问题就是在经验数据（2.2）基础上最小化风险泛函（2.1）式,其中z代表了数据对(x,y)，Q(z,a)

就是特定的损失函数第十二页，共107页。为了在未知的分布函数F(Z)下最小化（2-1）式的风险泛函，可以把风险泛函R(a)替换为经验风险泛函

（2.3）

令风险泛函的最小函数为Q(z,a0)，经验风险泛函的最小函数为Q(z,al)。使用经验风险（2.3）式最小的函数Q(z,al)逼近使风险（2.1）式最小的函数Q(z,a0)

，这一原则称作经验风险最小化（EmpiricalRiskMinimization,ERM）归纳原则。第十三页，共107页。定义2.1

一致性：如果下面两个序列依概率收敛于同一个极限，即

（2.4）

（2.5）

则ERM原则（或方法）对函数集Q(z,a),

aÎL和概率分布函数F(z)是一致的。第十四页，共107页。定理2.1

设函数集Q(z,a),

aÎL满足条件

A£òQ(z,a)dF(z)£B

(A£R(a)£B)

那么ERM原则一致性的充分必要条件是经验风险

Remp(a)在函数集Q(z,a),aÎL上在如下意义下一致收敛于实际风险R(a)：

（2.6）其中P为概率，则把这种一致收敛称作一致单边收敛。

第十五页，共107页。定义2.2随机变量序列

，n=1,2,…,（2.7）

这一随机变量序列既依赖于概率测度F(z),也依赖于函数集Q(z,a),

aÎL，称之为一个双边收敛过程。

第十六页，共107页。学习理论的关键定理（定理2.1）

从概念的角度看，这个定理是十分重要的，因为它指出了ERM原则一致性的条件是必要地（和充分地）取决于函数集中“最坏”的函数的。在传统的统计学中，并没有考虑是否存在一致单边收敛的问题。一致单边收敛是在一个新概念的基础上得到的，这个新概念叫做在n个样本上函数集Q(z,a),

aÎL的熵。第十七页，共107页。定义N^(z1,…,zn)代表用指示函数集Q(z,a),

aÎL中的函数能够把给定的样本分成多少种不同的分类。则称H^(z1,…,zn)=lnN^(z1,…,zn)为随机熵,它描述了函数集在给定数据上的多样性。考虑随机熵在联合分布函数F(z1,…,zn)上的期望；H^(n)=ElnN^(z1,…,zn)（其中E为数学期望），把这个量称作z指示函数集Q(z,a),

aÎL在数量为n的样本上的熵，它依赖于函数集Q(z,a),

aÎL

、概率测度以及观测数目n，反映了给定指示函数集在数目为n的样本上期望的多样性。

第十八页，共107页。在N^(z1,…,zn)值基础上构造两个新概念

退火的VC熵生长函数第十九页，共107页。在指示函数集Q(z,a),

aÎL可测性的一定条件下，一致双边收敛的充分条件是（2.8）它描述了ERM原则一致性的一个充分条件这一等式是学习理论中的第一个里程碑，所有最小化经验风险的机器都要满足这一条件。它回答了：在什么条件下，经验风险最小化的解收敛于期望风险最小化的解？第二十页，共107页。等式（2.9）是风险收敛速度快的一个充分条件（必要条件尚不得而知）。这一等式是学习理论的第二个里程碑，它保证了收敛有快的渐近速度。

注意：VC退火熵是对一个给定的概率测度定义的，因此这两个条件是依赖于这个概率测度的。问题：我们的目标是建立一个学习机器，使它能够解决很多不同的问题（对于很多不同的概率测度）。即：在什么条件下，不依赖于概率测度，ERM原则是一致的且同时有快的收敛速度。第二十一页，共107页。等式（2.10）给出了对任何概率测度ERM具有一致性的充分必要条件；而且，如果这个条件成立，则收敛的速度是快的。等式（2.10）就是学习理论中的第三个里程碑，它描述了在什么充分必要条件下，一个履行ERM原则的学习机器有一个快的收敛的渐近速度，而不管所用的概率测度如何（即不管所要解决的问题如何）

第二十二页，共107页。函数集的VC维

VC维描述了组成学习模型的函数集合的容量，也就是说刻画了此函数集合的学习能力。VC维越大，函数集合越大，其相应的学习能力就越强。第二十三页，共107页。定义2.3指示函数集的VC维：一个指示函数集Q(z,a),

aÎL的VC维是能够被集合中的函数以所有可能的2h种方式分成两类的向量z1,…,zh的最大数目h。VC维是统计学习理论中的一个核心概念，它是目前为止对函数集学习性能的最好描述指标。

第二十四页，共107页。它的另一个等价直观的定义是：假如存在一个有h个样本的样本集能够被一个函数集中的函数按照所有可能的2h

种形式分为两类，则称函数集能够把样本数为h的样本集打散。指示函数集的VC维就是用这个函数集中的函数所能够打散的最大样本集的样本数目。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在有h+1个样本集能够被函数集打散，则函数集的VC维就是h。如果对任意的样本数，总能找到一个样本集能够被这个函数集打散，则函数集的VC维就是无穷大。

第二十五页，共107页。如在二维实数空间R2，函数集为有向直线集。则对一给定有向直线，空间中的数据点被直线分为两类。直线方向如图2.1中箭头所示，位于直线正方向一侧的数据点为一类，位于直线负方向一侧的数据点为另一类。在二维实数空间R2中，找不到有向直线集不能够打散的由三个数据点构成的点集

图2.1在二维空间R2中被有向直线打散的三个点第二十六页，共107页。但能找到有向直线集不能够打散的由四个数据点构成的点集

图2.2在二维空间R2中不能被有向直线打散的四个点因此，此二维实数空间R2中的有向直线集的VC维是3。

第二十七页，共107页。定理2.2任何生长函数，或者满足等式

GL(n)=nln2

或者受下面的不等式约束：其中h是一个整数，使得当n＝h

时有GL(h)=hln2GL(h+1)<(h+1)ln2.

即生长函数或者是线性的，或者以一个对数为上界。

第二十八页，共107页。定义2.4如果指示函数集Q(z,a),

aÎL的生长函数是线性的则这个函数集的VC维是无穷大。如果指示函数集Q(z,a),

aÎL的生长函数以参数为h的对数函数为界，则这个指示函数集的VC维是有限的且等于h。第二十九页，共107页。定理2.3对具有有限VC维h的指示函数集Q(z,a),

aÎL如下两不等式成立：1.一致双边收敛速度不等式

（2.11）

式中ε*=(ε-1/n)2.一致相关收敛速度不等式

（2.12）

不等式(2.11)，(2.12)给出了遵循ERM准则的学习机器的泛化能力的与分布无关的界。第三十页，共107页。则遵循ERM准则的有界函数集0£Q(z,a)£B,aÎL

的风险以1-η的概率满足不等式：

（2.13）式中：式(2.13)表明，经验风险最小化原则下学习机器的实际风险是由两部分组成的，可以写作：（2.14）

第三十一页，共107页。结构风险最小化传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(StructuralRiskMinimization)，即SRM准则。第三十二页，共107页。把函数集S={Q(z,a),

aÎL}分解为一个函数子集序列

S1ÌS2Ì…ÌSk

Ì……ÌS

（2.15）式中Sk={Q(z,a),

aÎLk}，且

考虑容许结构（AdmissibleStructures）满足如下特性：函数集S中任何一个子集Sk的VC维是有限的；任何一个子集Sk包含①有界函数集0£Q(z,a)£Bk,aÎL或者②存在一对值，使得一个非负函数集Q(z,a),

aÎL满足如下不等式 （2.16）函数集S中集合在L1(F)度量空间中是处处紧致的。F=F(z)是关于z的概率分布函数。

第三十三页，共107页。由式（2.15），有如下结论成立：

各子集Sk的VC维hk随着k的增加按非递减规律排列

h1£h2£…£hk£…各子集Sk的界Bk随着k的增加按非递减规律排列

B1£B2£…£Bk£…各子集Sk的界τk

随着k的增加按非递减规律排列τ

τ1£τ2£…£τk£…第三十四页，共107页。则函数集Sk中函数Q(z,)的实际风险至少以概率1-η满足

（2.17）或 （2.18）式中

（2.19）第三十五页，共107页。这样，在同一个子集中置信范围就相同：在每一个子集中寻找最小经验风险，通常它随着子集复杂度的增加而减小。选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小。这个子集中使经验风险最小的函数就是要求的最优函数，这种思想称作有序风险最小化或者结构风险最小化，如图2.3所示。

图2.3结构风险最小化示意图

S1S2S3真实风险的界置信范围经验风险h第三十六页，共107页。在SRM原则下，一个分类器的设计过程包括以下两方面任务：选择一个适当的函数子集（使之对问题来说有最优的分类能力）；从这个子集中选择一个判别函数（使经验风险最小）。第一步相当于模型选择，而第二步则相当于在确定了函数形式后的参数估计。与传统方法不同的是，在这里模型的选择是通过对它的推广性的界的估计进行的。第三十七页，共107页。

3支持向量机

第三十八页，共107页。在统计学习理论基础上发展起来的一种新的机器学习方法

1992年，Boser，Guyon和Vapnik等人在《ATrainingAlgorithmforOptimalMarginclassifiers》一书中，提出了最优边界分类器算法，这也是支持向量机算法的最初模型1993年，Cortes和Vapnik在《TheSoft-MarginClassifier》一书中，进一步探讨了非线性情况下的最优边界分类问题1995年，Vapnik在发表的《TheNatureofStatisticalLearningTheory》一书中，完整地提出了基于统计学习理论的支持向量机学习算法1997年，Vapnik，Gokowich和Smola发表的《SupportVectorMethodforFunctionApproximation，RegressionEstimation．andSignalProcessing》一文中，详细介绍了基于支持向量机方法的回归估计方法(SupportVectorRegression，SVR)和信号处理方法2.3支持向量机

第三十九页，共107页。与其它传统的机器学习方法相比，SVM主要有以下几个方面的特点：以严格的数学理论(统计学习理论)为基础，克服了传统神经网络学习中靠经验和启发的先验成分等缺点。采用了结构风险最小化原则，克服了传统神经网络中只靠经验风险最小化来估计函数的缺点，提高了置信水平，克服了过学习等问题，使学习机器有良好的泛化能力。通过求解凸二次规划问题，可以得到全局的最优解，而不是传统神经网络学习中的局部最优解，保证了解的有效性。用内积的回旋巧妙地构造核函数，克服了特征空间中的维数灾难问题，通过非线性映射，只需在原空间中计算样本数据与支持向量的内积，而不需要知道非线性映射的显性表达形式。成功地解决了小样本学习问题，克服了传统上需要以样本数目无穷多为假设条件来推导各种算法的缺点，得到了小样本条件下的全局最优解。通过引入VC维的概念，使网络的收敛速度、样本被错分的界和风险泛函得到了控制。第四十页，共107页。支持向量机的发展理论基础不断拓展统计学习理论作为支持向量机的理论平台，逐渐获得完善和丰富正则化理论成为指导支持向量机参数选择和支持向量核函数的重要思想贝叶斯理论成为构造支持向量机模型的一个理论基础在对支持向量机所呈现的解具有稀疏性的研究上，稀逼近理论渐渐成为支持向量机分析的一个直观工具第四十一页，共107页。支持向量机的发展实现算法不断改进在训练算法优化方面，分块训练思想将大的二次规划问题分解为一系列小的二次规划问题，从而简化了算法的运行成本序列最小优化训练思想是分块训练思想的一种极端情形，每次只针对含两个样本的二次规划问题进行求解。这样求出的解具有解析形式，同时避免了大规模二次优化问题中的不稳定性和复杂性问题在对SVM算法改进方面，出现了一大批较好的变体算法，有C-SVM系列算法、v-SVM系列算法、One-classSVM算法、RSVM算法、WSVM算法和LS—SVM算法等第四十二页，共107页。支持向量机的发展领域不断扩大模式识别方面，SVM和先验语义结合应用于文本分类，取得了较高的识别精度，在图像分类、图像分割、自动图形定位检测、遥感图像分析、蛋白质分类等方面也有很好的表现回归估计方面，SVM在时间序列预测和混沌系统的动态重构中表现出强大的优势数据融合方面，SVM已经应用于个人身份证的多模型数据融合、多信息源的融合、分布式数据融合以及遥感数据融合除此之外，SVM还在过程建模、系统辨识、非线性控制等方面显示了很好的工作能力第四十三页，共107页。支持向量机的实现台湾大学林智仁(Chih-JenLin)博士等开发设计了一个操作简单、易于使用、快速有效的通用SVM软件包（LibSVM），可以解决分类问题（包括C-SVC、n-SVC）、回归问题（包括e-SVR、n-SVR）以及分布估计（one-class-SVM）等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择，可以有效地解决多类问题、交叉验证选择参数、对不平衡样本加权、多类问题的概率估计等。第四十四页，共107页。SVM从线性可分情况下的最优分类面发展而来。最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。支持向量机基本原理

第四十五页，共107页。设线性可分样本集为d维向量，2类样本，y为类别标签。则线性判别函数为

分类面方程为第四十六页，共107页。作判别函数归一化，即满足|g(x)|1，即距离分类面最近的样本距离为|g(x)|=1，则两类的分类间隔为2/||w||。如图所示第四十七页，共107页。令分类间隔2/||w||最大，等价于||w||或者||w||2最小，使得分类面对于所有的样本能正确分类，即满足

（2.20）则该分类面为最优分类面。过两类样本中离分类面最近的点，且平行于最优分类面的超平面H1,H2上的训练样本则称为支持向量，显见，最优分类面是由支持向量来“支撑”的。

第四十八页，共107页。最优分类面的求取由最优分类面的条件建立目标函数，为二次型由满足条件作为约束条件（样本条件）则有约束优化问题第四十九页，共107页。前面的最优分类面式在线性可分条件下推导出来的。不能应用于线性不可分情况。约束条件1：对于线性不可分情况，许多样本不能满足正确分类条件式因此，增加松弛项，分类条件式为

（2.21）广义最优分类面第五十页，共107页。约束条件2：线性可分条件下的分类间隔最大，线性不可分时引入约束

在两个约束条件下对错分样本最小函数求极小值第五十一页，共107页。支持向量机的数学表达最优分类的优化函数与最优分类函数表达式中都含有内积运算第五十二页，共107页。如果将表达式中的内积运算由内积函数来代替，将原来的特征空间作非线性变换，则优化函数成为最优分类函数成为

（2.23）则称为支持向量机第五十三页，共107页。类似一个RBF神经网络。输入层：中间层：基于s个支持向量的内积变换支持向量机的拓扑结构第五十四页，共107页。输出层：（决策规则）加权系数：

第五十五页，共107页。核函数一般有多项式核、高斯径向基核、指数径向基核、多隐层感知核、傅立叶级数核、样条核、B样条核等核函数及参数选择

第五十六页，共107页。多项式形式核函数（2.24）径向基形式核函数（2.25）S形核函数

（2.26）常用的核函数第五十七页，共107页。目前，核函数种类以及核参数的选择依据尚没有定论，一般情况下都是凭经验选取。值得一提的是，由于径向基核函数对应的特征空间是无穷维的，有限的样本在该特征空间中肯定是线性可分的，因此径向基核是最普遍使用的核函数核函数及参数选择

第五十八页，共107页。理论分析与试验结果都表明，SVM的性能与核函数的类型、核函数的参数以及正则化参数都有很大的关系，其中尤与核函数及其参数关系最大。在支持向量机训练算法中，参数值总是事先给定的，其值的好坏直接影响着预测精度的高低。因此，研究支持向量机参数值的选择，对支持向量机的应用与发展有很重要的实际意义。核函数及参数选择

第五十九页，共107页。然而，目前在理论上还没有足够的理论来指导如何选取有效的参数值。通常，人们通过大量的试验来获得较优的参数，这种方法比较费时，而且获得的参数也不一定是最优的。核函数及参数选择

第六十页，共107页。确定特征空间（选择核函数）确定经验风险

（选择参数C）解凸优化问题最优分类超平面当前特征空间中风险上界是否最小所有特征空间中风险上界是否最小终止训练否否是是图2.5支持向量机的训练过程

第六十一页，共107页。第1类第2类许多决策边界可以分割这些数据点出为两类我们选取哪一个?用于分类的SVM算法

第六十二页，共107页。第1类第2类第1类第2类坏的决策边界的例子第六十三页，共107页。好的决策边界:间隔大决策边界离两类数据应尽可能远最大化间隔m第1类第2类m所谓最优分类线就是要求分类线不但能将两类正确分开，而且要使两类间的分类间隔2/||w||最大。第六十四页，共107页。将上述最优化问题转换成其对偶问题:取Lagrange函数

(2.27)在鞍点上，解必须满足对w和b的偏导数为0，得(2.28)(2.29)又由Kuhn-Tucker条件可知，最优超平面的充分必要条件是使分类超平面满足条件：(2.30)第六十五页，共107页。利用对偶原理，拉格朗日函数可转化为求解如下泛函的优化问题：

(2.31)

设为上面二次优化问题的解，则最优超平面中向量的模为：(2.32)最后得到的分类函数为：

(2.33)第六十六页，共107页。具体算法步骤

Step1：设已知训练集，其中，，；Step2：构造并求解最优化问题式（2-35），得到最优解；Step3：选择的一个分类，并据此计算；Step4：由此计算求得决策函数第六十七页，共107页。虽然SVM首先提出是针对于分类问题的，但是通过引入损失函数的概念,SVM可以延伸推广到函数回归问题中来。

(2.36)其中，ε称为不敏感系数，用于控制拟合精度。若为线性模型，即。假设所有训练样本都可以在精度ε下无误差地用线性函数拟合，考虑到允许拟合误差存在的情况，类似于分类问题，引入松弛因子和，

(2.37)

用于回归的SVM算法

第六十八页，共107页。SVM的优化目标式(2.34)变成最小化：

(2.38)

其中，常数C>0，用以控制松弛系数在目标函数中的作用。标准不敏感支持向量回归机可以表示为

(2.39)建立Lagrange方程

：

(2.40)第六十九页，共107页。参数，，和的偏导都应等于零，即

(2.41)

代入式(2.38)，得到对偶优化问题

(2.42)求解：(2.49)第七十页，共107页。具体算法步骤

Step1：设已知训练集，其中，，；Step2：选择适当的正数

和

；Step3：构造并求解最优化问题(2-41)，得到最优解；

Step4：构造决策函数，其中b由式(2-47)计算。

第七十一页，共107页。假设非线性模型为

(2.50)则目标函数式(2-42)变为

(2.51)从而得到

(2.52)非线性SVM算法

第七十二页，共107页。设核函数K(x,x')满足

(2.53)

用K(x,x')代替运算，则都可以统一转化成如下的二次优化问题：(2.54)则式(2.33)的分类判别函数和(2-49)的函数回归方程可以分别表示如下：

(2.55)(2.56)为与每个数据点对应的拉格朗日乘子，式（2.55）存在唯一解，其解中只有一少部分的不为0，其对应的数据就是支持向量第七十三页，共107页。具体算法步骤

Step1：设已知训练集，其中，，；Step2：选择适当的正数和，选择适当的核函数K(x,x')；Step3：构造并求解最优化问题(2-54)，得到最优解；

Step4：若是分类问题则构造决策函数（2.55），其中

;若是回归问题则构造决策函数（2.56），其中b由式(2-47)计算。第七十四页，共107页。目前SVM的变形算法主要有C-SVM系列、v-SVM系列、One-classSVM、RSVM、WSVM和LS-SVM等。这些变形算法主要是通过增加函数项、变量或系数等方法使公式变形，产生出有某一方面优势或一定应用范围的算法。

变形的支持向量机算法

第七十五页，共107页。采用SVM方法求解最优分类问题，本质上是一个二次规划问题。对于海量数据(样本数在105～106以上)，常规的数值优化算法及软件已无法实现二次规划问题的求解。运行时间和计算内存是海量样本求解SVM的主要瓶颈。针对海量样本数据如何减少二次规划求解过程的计算时间和内存一直是SVM的研究热点，目前主要有以下3种方法。

优化的支持向量机算法

第七十六页，共107页。Vapnik提出了求解支持向量机二次规划问题的“Chunking”算法，其依据是支持向量机最终的判决函数只与支持向量(Lagrange乘子不等于零的训练样本)有关，而与非支持向量(Lagrange乘子等于零的训练样本)无关。而大多情况下，特别是训练样本很多时，样本中绝大多数是非支持向量，这些非支持向量在计算和内存上占用了大量的资源，在优化的过程中，若每次迭代后只保留当前的支持向量，这将会节省大量的计算时间和内存空间。基于这一思想，“Chunking”的目标就是通过某种迭代方式逐步排除非支持向量。Chunking算法

第七十七页，共107页。具体的实现方法是，随机选择一小部分样本作为初始样本集进行QP问题（QuadraticProgrammingProblem）求解，从结果中剔除非支持向量，并用训练结果对剩余样本进行检验，将不符合优化条件的样本(或其中的一部分)与当前的的支持向量合并成为一个新的QP训练样本集，然后重新训练。如此重复下去直到获得最优结果。增量学习方法(IncrementalLearning)本质上就是分块法。分块法求解规模随着SV数量的增加而增加，尽管如此，在训练集的SV数目非常大时，块算法仍然无法将矩阵放入内存中，优化计算仍难以实现。Chunking算法

第七十八页，共107页。当支持向量的数目远远小于训练样本数目时，分块法显然能够大大提高运算速度。然而，如果支持向量的数目本身就比较多，随着算法迭代次数的增多，工作样本集也会越来越大，算法依旧会变得十分复杂。因此，可把问题分解成为固定样本数的子问题:工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集，也不改变工作样本集的规模，而只对支持向量中的一部分进行优化。固定样本工作集方法第七十九页，共107页。固定工作样本集的方法和分块算法的主要区别在于:分块算法的目标函数中仅包含当前工作样本集中的样本。而固定工作样本集方法中虽然优化变量仅包含工作样本，其目标函数却包含整个训练样本集，即工作样本集之外的样本的Lagrange乘子固定为前一次迭代的结果，而不是像块算法中那样设为0。而且固定工作样本集方法还涉及到一个换出样本确定的问题(因为换出的样本可能是支持矢量)。这样，这一类算法的关键就在于找到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果。固定样本工作集方法第八十页，共107页。在固定样本工作集算法的基础上，微软研究院的JohnC．Platt提出的序列最小优化算法(SMO)。将工作样本集的规模减到最小——两个样本。之所以需要两个样本是因为等式线性约束的存在使得同时至少要调整两个Lagrange乘子。根据等式约束条件，两个样本对应的乘子变量可相互表示出来，所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来。这样，算法避开了复杂的数值求解优化问题的过程。SMO(SequentialMinimalOptimizition)算法第八十一页，共107页。修改支持向量机的二次规划形式，并在在所有样本的基础上求解一个大的二次规划问题，一次完成多类问题的分类。这种方法计算量很大，预测效果也并不理想，整体来说并不占优。

构造若干个的二分类器，并按照某种方式将它们组合起来实现多类问题的分类。

多分类的支持向量机算法--主要有两种

第八十二页，共107页。一对一的方法是在每两类不同的训练样本之间都构造一个最优决策面的二分类SVM，将一个多类问题转化为多个二分类问题来求解从样本集中取出所有满足

与

的样本点（其中1≤s,t≤k,s≠t），通过二分类的SVM算法构造最优决策函数：

(2.62)同样，对k类样本中的每一对构造一个决策函数，所以一个类问题需要k(k-1)/2个分类平面。一对一支持向量机（1-against-1SVM）第八十三页，共107页。一对一支持向量机（1-against-1SVM）1-against-1SVM方法每次投入训练的样本相对较少，所以单个决策面的训练速度较快，并且精度也较高。该方法的确定是由于k类问题需要训练k(k-1)/2个决策面，当k较大的时候决策面的总数将会变的很多，直接影响到预测速度，这是一个有待改进的地方。第八十四页，共107页。一对余类支持向量机（1-against-therestSVM）是在一类样本与剩余的多类样本之间构造决策平面，从而达到多类识别的目的。这种方法只需要在每一类样本和剩余样本之间产生一个最优决策面，而不用在两两之间都进行分类。因此如果仍然是一个k类问题的话，那么该方法仅需要构造k个分类平面(k>2)。该方法其实也可以认为是两类SVM方法的推广。实际上它是将剩余的多类看成一个整体，然后进行k次两类识别一对余类支持向量机（1-against-therestSVM）第八十五页，共107页。假设第j类样本看作正类(j=1,2,…,k)，而将其它k−1类样本看作负类，通过两类SVM方法求出一个决策函数：

(2.63)

具体方法第八十六页，共107页。一对余类支持向量机（1-against-therestSVM）相比较1-against-1SVM，1-against-therestSVM方法构造的决策平面数大大减少，因此在类别数目k较大时，其预测速度将比1-against-1SVM方法快许多，但同时预测的准确率也会有所下降。不过，由于它每次构造决策平面都会用上全部的样本集，所以其训练的时间并不比1-against-1SVM短。

第八十七页，共107页。决策树算法（DAGSVM）与1-against-therestSVM和1-against-1SVM两种方法不太一样，DAGSVM是通过排除在每层节点处对不符合要求的类别，进而最后得到样本所属的类别。第八十八页，共107页。决策树算法（DAGSVM）DAGSVM的训练阶段和1-against-1SVM的步骤一样，首先从k(k−1)/2个分类决策面中任意选取一个，不妨设为，然后将未知样本x代入该决策函数进行判定：若在此决策函数中x被判定为第s类，那么将所有与第t类样本相关的决策函数全部删除，然后从剩下的与第s类样本相关的分类决策面中任取一个重复以上步骤；若是被判定为第t类，方法也是完全类似。依此类推，直到决出样本x的最终类别。

第八十九页，共107页。决策树算法（DAGSVM）和1-against-1SVM方法不同的是，由于在每个节点预测的时候同时排除了许多类别的可能性，因此预测的时候用到的总分类平面只有k-1个，比1-against-1SVM要少很多，预测速度自然提高不少。但DAGSVM算法也有其不足之处。正由于它采取的是排除策略，那么最开始的判定显得尤为重要，如果在开始阶段就决策错误的话，那么后面的步骤都没有意义了。第九十页，共107页。支持向量机聚类算法

聚类就是将数据库中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同。支持向量机聚类（SupportVectorClustering，SVC）是一个使用支持向量机技术的算法，也是近年来受关注度很高的一种聚类技术，通过其算法的不断改进和参数的优化选择，聚类的精确度以及速度都得到了很大提高。第九十一页，共107页。支持向量机聚类

支持向量聚类就是在无监督的环境下，使用支持向量技术进行类别学习的算法SVC的基本思想是：将样本点经过一个非线性映射Φ映射到一个高维特征空间，并在此空间中寻找一个包围所有样本点且具有最小半径的超球，将该球体逆映射回原输入空间，位于球表面的点即为支持向量第九十二页，共107页。支持向量机优化过程Step1：给定数据集，其中。设a是特征空间中包含了所有数据的最小超球体球心，R是超球体半径，ξi是松弛因子，Φ是从原空间到特征空间的非线性映射，SVC软间隔目标优化函数为：

（2.64）Step2：将其转化为Lagrange函数：（2.65）

其中，它们作为Lagrange乘子，将两个约束条件引入了目标函数。C衡量半径和松弛因子之间比重。第九十三页，共107页。支持向量机优化过程

Step3：对R，a和ξi分别求偏导，并根据KTT条件，消去R，a及γ，再转换成Wolfe对偶形式，得到关于βi的目标为：