第五讲 支持向量机网络.

Presentation on theme: "第五讲 支持向量机网络."— Presentation transcript:

1 第五讲 支持向量机网络

2 目 录 引言 统计学习理论的基本理论 支持向量机 核函数 支持向量机优化方法 支持向量机方法小结 支持向量机应用领域和研究进展
目录(1/1) 目 录 引言 统计学习理论的基本理论 支持向量机 核函数 支持向量机优化方法 支持向量机方法小结 支持向量机应用领域和研究进展 Support Vector Regression 参考文献

3 1 引言 基于数据的机器学习是现代智能技术中的重要方面,其本质就是从观测数据出发寻找统计规律,并对未来进行预测.
1 引言(1/13) 1 引言 基于数据的机器学习是现代智能技术中的重要方面,其本质就是从观测数据出发寻找统计规律,并对未来进行预测. 人的智慧中一个很重要的方面是从实例学习的能力,通过对已知事实的分析总结出规律,预测不能直接观测的事实。 在这种学习中,重要的是要能够举一反三,即利用学习得到的规律,不但可以较好地解释已知的实例,而且能够对未来的现象或无法观测的现象做出正确的预测和判断。 我们把这种能力叫做泛化（推广）能力。

4 在人们对机器智能的研究中,希望能够用机器(计算机)来模拟这种学习能力,这就是我们所说的基于数据的机器学习问题,或者简单地称作机器学习问题。
1 引言(2/13) 在人们对机器智能的研究中,希望能够用机器(计算机)来模拟这种学习能力,这就是我们所说的基于数据的机器学习问题,或者简单地称作机器学习问题。 我们的目的是,设计某种(某些)方法,使之能够通过对已知数据的学习,找到数据内在的相互依赖关系,从而对未知数据进行预测或对其性质进行判断。 同样,在这里,我们最关心的仍是泛化能力问题。 迄今为止,关于机器学习还没有一种被共同接受的理论框架,关于其实现方法大致可以分为三种: 经典的(参数)统计估计方法 经验非线性方法,如ANN 统计学习理论

5 包括模式识别、NN等在内,现有机器学习方法共同的重要理论基础之一是统计学.
1 引言(3/13) A. 第一种是经典的(参数)统计估计方法. 包括模式识别、NN等在内,现有机器学习方法共同的重要理论基础之一是统计学. 参数方法正是基于传统统计学的,在这种方法中,参数的相关形式(模型结构)是已知的,训练样本用来估计参数的值. 这种方法有很大的局限性, 首先,它需要已知样本分布形式,这需要花费很大代价. 还有,传统统计学研究的是样本数目趋于无穷大时的渐近理论,即当样本趋向于无穷多时的统计性质. 现有学习方法也多是基于样本数大这一假设.

6 但在实际问题中,样本数往往是有限的,有时还十分有限。
1 引言(4/13) 但在实际问题中,样本数往往是有限的,有时还十分有限。 虽然人们实际上一直知道这一点，但传统上仍以样本数目无穷多为假设来推导各种算法，希望这样得到的算法在样本较少时也能有较好的(至少是可接受的)表现。 因此当样本数有限时,一些本来在样本数目无穷多为假设来推导的,理论上很优秀的学习方法实际中表现却可能不尽人意,可能表现出很差的泛化能力。 其中，近年来经常可以听到人们谈论的所谓ANN过学习问题就是一个典型的代表.

7 这种方法利用已知样本建立非线性模型,克服了传统参数估计方法的困难. 但是,这种方法缺乏一种统一的数学理论. C. 统计学习理论.
1 引言(5/13) B. 经验非线性方法,如ANN. 这种方法利用已知样本建立非线性模型,克服了传统参数估计方法的困难. 但是,这种方法缺乏一种统一的数学理论. C. 统计学习理论. 针对小样本学习问题及泛化能力差等机器学习问题，实际上人们一直在努力解决此类问题。 但是，其中多数工作集中在对已有(基于传统统计学原则的)方法的改进和修正，或者利用启发式方法设计某些巧妙的算法。 在人类即将迈进一个新世纪的时候，人们开始逐渐频繁地接触到一个词，就是“统计学习理论”。

8 到90年代中期,随着其理论的不断发展和成熟,也由于NN等学习方法在理论上缺乏实质性进展,该理论开始受到广泛的重视.
1 引言(6/13) 统计学习理论(Statistical Learning Theory, SLT) 创始人V.Vapnik从60年代开始致力于有限样本统计理论的研究,在70年代就已经建立了其基本理论体系，成为机器学习问题研究的新的思路，有着诱人的前景。 到90年代中期,随着其理论的不断发展和成熟,也由于NN等学习方法在理论上缺乏实质性进展,该理论开始受到广泛的重视.

9 SLT指出经验风险最小并不能保证期望风险最小; 提出了结构风险最小化原理;
1 引言(7/13) SLT指出经验风险最小并不能保证期望风险最小; 提出了结构风险最小化原理; 给出了核心概念VC维,指出为了最小化期望风险必须同时最小化经验风险和VC维; SLT从七十年代末诞生,到九十年代之前都处在初级研究和理论准备阶段,近几年才逐渐得到重视,其本身也趋向完善,并在1992直接产生了支持向量机(Support Vector Machine, SVM) 这一将这种理论付诸实现的有效的通用机器学习方法. 或许是由于SLT为人们系统研究有限样本情况下机器学习问题提供了有力的理论基础,或许更是因为在这一基础上的SVM方法所表现出的令人向往的优良特性,人们开始迅速重视起这一早在20年前就该重视的学术方向。

10 SVM就是基于SLT的一种模式识别与机器学习的方法,它是SLT中最新的内容,也是最实用的部分.
1 引言(8/13) SVM就是基于SLT的一种模式识别与机器学习的方法,它是SLT中最新的内容,也是最实用的部分. 定义( Cristianini & Shawe-Taylor ,2000 ) Support Vector Machines are a system for efficiently training linear learning machines in kernel-induced feature spaces, while respecting the insights of generalisation theory and exploiting optimisation theory. SVM becomes popular because of its success in handwritten digit recognition 1.1% test error rate for SVM. This is the same as the error rates of a carefully constructed neural network, LeNet 4.

11 目前,SVM算法在模式识别、回归估计、概率密度函数估计等方面都有应用.
1 引言(9/13) 目前,SVM算法在模式识别、回归估计、概率密度函数估计等方面都有应用. 例如,在模式识别方面,除对于手写数字识别外,在语音识别、人脸图像识别、文章分类等问题,SVM算法在精度上已经超过传统的学习算法或与之不相上下. SVM is now regarded as an important example of “kernel methods”, arguably the hottest area in machine learning.

12 SVMs combine three important ideas
1 引言(10/13) SVMs combine three important ideas Apply optimization algorithms from Operations Reseach Linear Programming and Quadratic Programming Implicit feature transformation using kernels Implicit feature transformation using kernels Control of overfitting by maximizing the margin

13 目前,对SVM的讨论和进一步研究逐渐广泛,但仍有许多方面不完善.比如: 许多理论目前还只有理论上的意义,尚不能在实际算法中实现;
1 引言(11/13) 目前,对SVM的讨论和进一步研究逐渐广泛,但仍有许多方面不完善.比如: 许多理论目前还只有理论上的意义,尚不能在实际算法中实现; 有关SVM算法某些理论解释也并非完美(如结构风险最小原理并不能严格证明SVM为什么有好的泛化能力); 对于一个实际的学习机器的VC维的分析尚没有通用的方法; SVM方法中如何根据具体问题选择适当的内积函数也没有理论依据.

14 现在,越来越多的学者认为,关于SLT和SVM的研究,将很快出现像在80年代后期ANN研究那样的飞速发展阶段。
1 引言(12/13) 现在,越来越多的学者认为,关于SLT和SVM的研究,将很快出现像在80年代后期ANN研究那样的飞速发展阶段。 然而,所不同的是,SLT有完备的理论基础和严格的理论体系(相比之下ANN有更多的启发式成分),而且其出发点是更符合实际情况的有限样本假设. 因此,可以预期的是,SLT的这个研究热潮将持续更长久,而且将在人们关于机器智能的研究中做出影响更深远的贡献。

15 下面开始讨论SVM,主要内容有: 统计学习理论的基本理论 支持向量机 核函数 支持向量机优化方法 SVM的应用领域和研究进展
1 引言(13/13) 下面开始讨论SVM,主要内容有: 统计学习理论的基本理论 支持向量机 核函数 支持向量机优化方法 SVM的应用领域和研究进展

16 2 统计学习理论的基本理论 与传统统计学相比,统计学习理论(SLT)是一种专门研究小样本情况下机器学习规律的理论.
该理论针对小样本统计问题建立了一套新的理论体系,在这种体系下的统计推理规则不仅考虑了对渐近性能的要求,而且追求在现有有限信息的条件下得到最优结果. V. Vapnik等人从六、七十年代开始致力于此方面研究,到九十年代中期,随着其理论的不断发展和成熟,也由于NN等学习方法在理论上缺乏实质性进展,SLT开始受到越来越广泛的重视.

17 在基于经验数据最小化风险泛函的模型基础上对学习问题的表示。 对经验风险最小化原则的深入分析，包括其一致性的充分必要条件。
2 SLT的基本理论(2/4) SLT的主要内容为： 在基于经验数据最小化风险泛函的模型基础上对学习问题的表示。 对经验风险最小化原则的深入分析，包括其一致性的充分必要条件。 用经验风险最小化原则得到的风险的非渐近界。 在这些界的基础上，控制小样本学习机器的泛化能力的原则。 SVM方法，它在用小样本估计函数时能够控制泛化能力。

18 SLT是建立在一套较坚实的理论基础之上的,为解决有限样本学习问题提供了一个统一的框架.
SLT的一个核心概念就是VC维(VC Dimension)概念,它是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标,在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、泛化性能等的重要结论. SLT是建立在一套较坚实的理论基础之上的,为解决有限样本学习问题提供了一个统一的框架. 它能将很多现有方法纳入其中,有望帮助解决许多原来难以解决的问题(比如NN结构选择问题、局部极小点问题等); 同时,这一理论基础上发展了一种新的通用学习方法--SVM,已初步表现出很多优于已有方法的性能.

19 一些学者认为,SLT和SVM正在成为继NN研究之后新的研究热点,并将推动机器学习理论和技术有重大的发展.
经验风险 经验风险最小一致性原理 经验风险最小归纳原理 VC维的概念 模型复杂度和泛化能力

20 2.1 经验风险 学习的目的就是根据给定的训练样本求系统输入输出之间的依赖关系.
2.1 经验风险(1/3) 2.1 经验风险 学习的目的就是根据给定的训练样本求系统输入输出之间的依赖关系. 学习问题可以一般的表示为变量y与x之间存在的未知依赖关系,即遵循某一未知的联合概率F(x,y). 机器学习问题就是根据n个独立同分布观测样本: {x1, y1}, {x2, y2}, ……, {xn, yn} 在一组函数{f(x,w)}中,求一个最优的数f(x,w0)对依赖关系进行估计,使如下期望的风险最小

21 {f(x,w)}称为预测函数集,它可以表示为任何的参数集.
2.1 经验风险(2/3) 其中w为函数的广义参数; {f(x,w)}称为预测函数集,它可以表示为任何的参数集. L(y,f(x,w))为由于用f(x,w)对y进行预测而造成的损失,在两类分类问题中,L(y,f(x,w))通常如下定义:

22 由于期望风险需要掌握联合概率分布F(x,y),在传统的学习方法中,采用了所谓的经验风险最小化准则,即用样本定义经验风险
2.1 经验风险(3/3) 由于期望风险需要掌握联合概率分布F(x,y),在传统的学习方法中,采用了所谓的经验风险最小化准则,即用样本定义经验风险 机器学习的目的就是要设计学习算法,使上述风险最小,作为对R(w)的评估.

23 2.2 经验风险最小一致性原理(1/2) 2.2 经验风险最小一致性原理 为了从有限的观测中构造学习算法,需要一种渐进理论来刻画学习过程一致性的必要和充分条件,这就产生了最小一致性原理. 定义: 对于指示函数集L(y,w)和概率分布函数F(y),如果下面两个序列概率地收敛到同一极限,则称为经验风险最小一致性:

24 上面两个式子可以分别判定风险可能的最小值,
2.2 经验风险最小一致性原理(2/2) 也就是说如果经验风险最小化方法是一致性,那么它必须提供一个函数序列L(y,wl),l=1,2,…,使得期望风险和经验风险收敛到一个可能的最小的风险值. 上面两个式子可以分别判定风险可能的最小值,

25 2.3 经验风险最小归纳原理 SLT系统的研究 了对于各种类型的函数集、经验风险和实际风险之间的关系,即泛化的界限.
2.3 经验风险最小归纳原理(1/3) 2.3 经验风险最小归纳原理 SLT系统的研究 了对于各种类型的函数集、经验风险和实际风险之间的关系,即泛化的界限. 实际上,从经验风险而推出期望风险最小没有可靠的理论依据,统计理论指出: 经验风险Remp(w) 和实际风险R(w)之间至少以1-的概率满足如下关系 其中n是样本数, h是函数集的VC维.

26 由此可见,统计学习的实际风险由两部分组成: 一个是经验风险, 另外一个是置信界限(VC confidence).
2.3 经验风险最小归纳原理(2/3) 由此可见,统计学习的实际风险由两部分组成: 一个是经验风险, 另外一个是置信界限(VC confidence). 置信界限反映了真实风险和经验风险差值的上确界,反映了结构复杂所带来的风险,它和学习机器的VC维h及训练样本数l有关. 上式也可以简单的表示为: 这里(h,l)随着h增大而增加.

27 因此,在有限的训练样本下,学习机器的复杂性越高,VC维越高,则置信界限越大,就会导致真实风险和经验风险之间可能的差别越大.
2.3 经验风险最小归纳原理(3/3) 因此,在有限的训练样本下,学习机器的复杂性越高,VC维越高,则置信界限越大,就会导致真实风险和经验风险之间可能的差别越大. 值得注意的是,如果VC维无穷大的时候,这个界限就不再成立.

28 2.4 VC维的概念 Anthony将VC维定义为:
设F为一个将n维向量集X映射到{0,1}的函数族,则F的VC维为X的子集E的最大元素数,其中E满足: 对于任意SE,总存在函数fsF,使得当xS时fs(x)=1, xS但xE时fs(x) =0. VC维可作为函数族F复杂度的度量,它是一个自然数,其值有可能为无穷大,它表示无论以何种组合方式出现均可被函数族F正确划分为两类的向量个数的最大值. 对于实函数族,可定义相应的指示函数族,该指示函数族的VC维即为原实函数族的VC维.

29 下面介绍在模式识别方法中VC维的直观定义. 二分子集(dichotomy)的定义
A dichotomy of a set S is a partition of S into two disjoint subsets. 打散(shatter)的定义 A set of instances S is shattered by hypothesis space H if and only if for every dichotomy of S there exists some hypothesis in H consistent with this dichotomy.

30 对一个指示函数集,如果存在一个h个样本能够被函数集里的函数按照所有可能的2h种形式分开,则称函数集能够把h个样本打散.
2.4 VC维的概念(3/7) VC维的定义 对一个指示函数集,如果存在一个h个样本能够被函数集里的函数按照所有可能的2h种形式分开,则称函数集能够把h个样本打散. 函数集的VC维就是它能打散的最大样本数目h. 若对任何数目的样本都有函数能将它们打散,则函数集的VC维称为无穷大. 有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义.

31 其能够以任意方式打散(分类)的最大样本数为3,如下图所示.
2.4 VC维的概念(4/7) 例如,对于2维空间的线性分类面函数 y=w0+w1x1+w2x2 其能够以任意方式打散(分类)的最大样本数为3,如下图所示. 因此,该线性分类函数的VC维即为3.

32 2.4 VC维的概念(5/7) 一般来说,对于n维空间的线性分类面函数 y=w0+w1x1+…+wnxn 的VC维为n+1.

33 再如,如下图所示,2维空间的矩形分类函数能够以任意方式打散(分类)的最大样本数为4.
2.4 VC维的概念(6/7) 再如,如下图所示,2维空间的矩形分类函数能够以任意方式打散(分类)的最大样本数为4. 因此,该矩形分类函数的VC维即为4.

34 一般而言,VC维越大则学习机器越复杂,学习内容量就越大. 目前没有通用的关于任意函数集VC维计算的理论,只对一些特殊的函数集知道其函数维.
例如 在n维实数空间中线性分类器和线性实函数的VC维是n+1, 而f(x,a)=sin(ax)的VC维则为无穷大. 如何用理论和试验的方法计算其VC维是当前SLT中一个待研究的问题,

35 2.5 模型复杂度和泛化能力(1/4) 2.5 模型复杂度和泛化能力 早期的NN研究中,人们总是把注意力集中在如何使经验风险更小,但很快发现,一味追求训练误差最小并不总能达到好的预测效果. 实际情况是,只要学习机器足够复杂,训练时间足够长,则训练误差可以任意减小. 最极端的情况是,学习机器记住了所有的训练样本,则训练误差为零,但是实际上这种学习机器机器不具有泛化能力. 也就是说训练误差过小反而可能会导致泛化能力下降.

36 例如:考虑使用BP网络对二维平面上两类数据的分类问题. 设有两类数据,是分别从两个不同的数据发生器产生的.
2.5 模型复杂度和泛化能力(2/4) 例如:考虑使用BP网络对二维平面上两类数据的分类问题. 设有两类数据,是分别从两个不同的数据发生器产生的. 实验中,首先从这两个数据发生器中各采集一部分作为训练数据,另外再采集一部分作为测试数据. 所使用的BP网络采用典型的三层结构(输入层,隐层,输出层). 设定网络的隐层节点数,对BP网络训练并测试,重复进行50次,并记录平均训练误差和测试误差;改变隐层节点数,重复前一步骤. 试验的结构如下:

37 经验风险(或者说训练误差)对学习机器的性能有一定的影响,但不起决定作用.
2.5 模型复杂度和泛化能力(3/4) 由上表可以看出,随着隐层节点数的增加,训练误差越来越小,然而测试误差在5个隐层节点的时候达到最低,之后随着隐层节点数的增加呈上升趋势这是一种典型的过学习问题.可以得到如下几个结论: 经验风险(或者说训练误差)对学习机器的性能有一定的影响,但不起决定作用. 执行经验风险最小化原则(即最小化训练误差),并不总能提高学习机器的泛化能力.

38 复杂度高的学习机器,往往具有较低的经验风险. 因此,经验风险最小化原则的结果,将使学习机器变得越来越复杂(隐层节点数增多)
2.5 模型复杂度和泛化能力(4/4) 复杂度高的学习机器,往往具有较低的经验风险. 因此,经验风险最小化原则的结果,将使学习机器变得越来越复杂(隐层节点数增多) 学习机器的复杂度对其性能有较大影响,泛化性能好的学习机器应该具有与实际面对的问题相对应的复杂度. 因此,如何根据实际问题,在学习机器的经验风险和模式复杂度之间取得合理的折中,从而使学习机器具有更高的泛化能力,是一个非常重要的问题.

39 3 支持向量机 SVM方法是建立在SLT的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在
模型的复杂性(即对特定训练样本的学习精度)和 学习能力(即无错误地识别任意样本的能力) 之间寻求最佳折衷,以期获得最好的泛化能力. SVM方法的几个主要优点有: 它是专门针对有限样本情况的,其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值;

40 算法最终将转化成为一个二次型寻优问题,从理论上说,得到的将是全局最优点,解决了在NN方法中无法避免的局部极值问题;
3 SVM(2/3) 算法最终将转化成为一个二次型寻优问题,从理论上说,得到的将是全局最优点,解决了在NN方法中无法避免的局部极值问题; 算法将实际问题通过非线性变换转换到高维的特征空间,在高维空间中构造线性判别函数来实现原空间中的非线性判别函数. 所定义的特殊优化函数的性质能保证机器有较好的泛化能力,同时它巧妙地解决了维数问题,其算法复杂度与样本维数无关. 在SVM方法中,只要定义不同的内积函数,就可以实现多项式逼近、贝叶斯分类器、RBF方法、多层感知器网络等许多现有学习算法.

41 3 SVM(3/3) 下面开始介绍SVM,主要内容有 线性可分的SVM 非线性可分的SVM

42 3.1 线性可分的SVM 所谓线性可分的分类问题是指: 对n维空间的m个数据样本(x1,y1), (x2,y2)…… (xm,ym),
其中xi为n维空间的数据样本; yi{-1,1}为数据样本的类别.取值为-1属于I类,为1则为II类. 存在并求解n维空间内超平面的分类面 f(x)=wTx-b=0 使得如下关系成立

43 对线性分类问题,模式识别领域已有充分研究,得到了许多有效的算法.
3.1 线性可分的SVM(2/4) 对线性分类问题,模式识别领域已有充分研究,得到了许多有效的算法. 但在实际中,传统的线性分类算法,如模式识别的分类学习方法、多层感知器、BP网、RBF网等,还存在如下问题: 分类面仅考虑了对现有样本的分类面的存在与求解, 未考虑其泛化能力,因此泛化能力较弱 分类面部不唯一,到底何为最优的分类面？ 何为最优的分类,最优指标的意义？ 如采用BP网、RBF网分类,其可能的分类面如下图所示

44 3.1 线性可分的SVM(3/4) BP RBF

45 对有污染的或近似线性分类的数据样本,可能严格线性分类意义下的分类面不存在. 因此鲁棒性较差. 对海量数据,求解分类面的时间代价大.
3.1 线性可分的SVM(4/4) 对有污染的或近似线性分类的数据样本,可能严格线性分类意义下的分类面不存在. 因此鲁棒性较差. 对海量数据,求解分类面的时间代价大. 因此,发展泛化能力强,鲁棒性佳,求解的代价小的新的分类算法得到重视. 下面基于SLT,针对传统分类算法中存在的分类面的问题,发展了SVM. 最优分类面SVM 广义最优分类面 SVM

46 3.1 线性可分的SVM--最优分类面SVM(1/5)
A. 最优分类面SVM 基于SLT,针对传统分类算法中存在的分类面的问题,发展了SVM. SVM对于线性分类的问题描述为: 对n维空间的m个数据样本(x1,y1), (x2,y2)…… (xm,ym), 存在并求解n维空间内满足条件: 经验风险最小(错分最少) 泛化能力最大(空白最大) 的最优分类面 f(x)=wTx-b=0

47 3.1 线性可分的SVM --最优分类面SVM(2/5)
所谓的泛化能力最大,即所找到的分类面,应使得它能够尽可能多的将两类数据点正确的分开,同时使分开的两类数据点距离分类面最远. 如下图所示的情况(b)就比情况(a)与(c)的泛化能力强,其原因在于其分界面与两类样本中的最近邻的样本的距离最大. (c) (a) (b)

48 3.1 线性可分的SVM --最优分类面SVM(3/5)
下面讨论如何定义分界面与最近邻的样本的距离.如右图所示, 任一样本与分界面的距离为 r=(wTx+b)/||w|| 因此,当选择分类的开关函数为 则分界面与最近邻的样本的距离为 r=1/||w||

49 3.1 线性可分的SVM --最优分类面SVM(4/5)
相应的约束条件为 SVM的最优分界面的优化函数为二次型,约束条件是线性的,因此是典型的二次规划问题,可由拉格朗日乘子法求解.

50 3.1 线性可分的SVM --最优分类面SVM(5/5)
After learning both RBFN and BP decision surfaces might not be at the optimal position. For example, as shown in the figure, both learning rules will not perform further iterations (learning) since the error criterion is satisfied BP RBF

51 3.1 线性可分的SVM –广义最优分类面SVM(1/16)
B. 广义最优分类面SVM 对于许多实际问题,前面讨论的最优分类面的条件 过于严格. 对存在数据污染、近似线性分类的情况,可能并不存在一个最优的线性分类面. 如对于下图所示的分类问题,不存在严格的线性分类面

52 3.1 线性可分的SVM –广义最优分类面SVM(2/16)
Class 1 Class 2 分类面

53 3.1 线性可分的SVM –广义最优分类面SVM(3/16)
此外,对于海量数据,求解最优分类面的时间代价大. 因此,需要发展允许有一定范围内的“错分”,又有较大分界区域的最优分类面. 实际上,广义最优分类面是在分类准确性与泛化特性上寻求一个平衡点. 上图所示的分类问题可以找到如下图所示的广义最优分类面。

54 3.1 线性可分的SVM –广义最优分类面SVM(4/16)
Class 1 Class 2 分类面

55 3.1 线性可分的SVM –广义最优分类面SVM(5/16)
“允许有一定的错分”的分类问题通过引入松弛变量i,可表示为如下优化问题: 相应的约束条件为 因此,SVM的广义最优分类问题可表示为如下优化问题:

56 3.1 线性可分的SVM –广义最优分类面SVM(6/16)
约束条件 其中Parameter C is tradeoff parameter between error and margin and can be viewed as a way to control overfitting. C越大,表示分类越严格,允许错分的样本受到的限制越大,错分的样本数少,越过拟合。 按照上述目标函数进行分类所得到的分类面也称为The Soft Margin Hyperplane incorporating slack variables。

57 3.1 线性可分的SVM –广义最优分类面SVM(6/16)
控制参数的作用如下图所示 虚线与实线为C=1和104所解得的分类面

58 3.1 线性可分的SVM –广义最优分类面SVM(7/16)
下面讨论基于拉格朗日松弛法,求解广义最优分类面问题. 首先引入拉格朗日乘子 其中i与i为拉格朗日乘子,满足 i, i0 根据拉格朗日松弛法的Kuhn-Tucker条件,有

59 3.1 线性可分的SVM –广义最优分类面SVM(8/16)

60 3.1 线性可分的SVM –广义最优分类面SVM(9/16)
可得 只要确定i ,便可解出w,b,i, i

61 3.1 线性可分的SVM –广义最优分类面SVM(10/16)
将上述条件代入拉格朗日函数L中,有 其中w,b,i, i可根据i计算出,即优化变量只有i. 因此,SVM广义最优分类面的优化目标函数可变换为 相应的约束条件为

62 3.1 线性可分的SVM –广义最优分类面SVM(11/16)
In practice, solving the optimization problem involved computing the inner products xiTxj between all training points! SVM广义最优分类面的上述等效优化问题是一个不等式约束下二次函数寻优的问题,存在唯一解. 容易证明,解中将只有一部分(通常是少部分)i不为零,对应的样本就是支持向量. 支持向量（i不为零）与非支持向量（i不零）如下图所示。

63 3.1 线性可分的SVM –广义最优分类面SVM(12/16)
a6=1.4 Class 1 Class 2 a1=0.8 a2=0 a3=0 a4=0 a5=0 a7=0 a8=0.6 a9=0 a10=0

64 3.1 线性可分的SVM –广义最优分类面SVM(13/16)
解上述问题后得到的最优分类函数是 式中的求和实际上只对支持向量进行. b*是分类阈值,可以用任一个支持向量(满足(1)中的等号)求得,或通过两类中任意一对支持向量取中值求得. Notice that 分类函数 relies on an inner product between the test point x and the support vectors （learning sample）xi 。

65 3.1 线性可分的SVM –广义最优分类面SVM(14/16)
Characteristics of the Solution of SVM are Many of the ai are zero w is a linear combination of a small number of data Sparse representation xi with non-zero ai are called support vectors (SV) The decision boundary is determined only by the SV Let tj (j=1, ..., s) be the indices of the s support vectors. We can write

66 3.1 线性可分的SVM –广义最优分类面SVM(15/16)
For testing with a new data z Compute the classifying function and classify z as class 1 if the sum is positive, and class 2 otherwise There are theoretical upper bounds on the error on unseen data for SVM The larger the margin, the smaller the bound The smaller the number of SV, the smaller the bound

67 3.1 线性可分的SVM –广义最优分类面SVM(16/16)
Note that in both training and testing, the data are referenced only as inner product, xi  xj This is important for generalizing to the non-linear case

68 3.2 非线性可分的SVM 非线性分类问题一直是分类领域的困难问题,主要的困难在于难于构造非线性的分类判别函数.
实际上,非线性可分的数据样本有可能在适当的函数变换 下在高维空间有可能转化为线性可分. 如下图所示的2个例子.

69 因此对非线性问题,可以把样本x映射到某个高维特征空间H,并在H中使用线性分类器.
3.2 非线性可分的SVM(2/12) 因此对非线性问题,可以把样本x映射到某个高维特征空间H,并在H中使用线性分类器.

70 对非线性不可分的问题经函数变换为高维的线性可分的性质,有如下定理：
3.2 非线性可分的SVM(3/12) 对非线性不可分的问题经函数变换为高维的线性可分的性质,有如下定理： 定理(Cover's theorem): A complex pattern-classification problem cast in a high-dimensional space nonlinearly is more likely to be linearly separable than in a low-dimensional space. A binary classification is -separable if there is an m-dimensional function vector  that cast the inputs into a m-dimensional space, where the classification is linearly separable by the hyperplane wT(x) = 0, where w is the weight vector associated to an output neuron.

71 This hyperplane is called the separation surface of the network.
3.2 非线性可分的SVM(4/12) This hyperplane is called the separation surface of the network. A corollary of Cover's theorem: Corollary: In a space of dimensionality of m, the expected maximum number of randomly assigned vectors that are linearly separable is 2m.

72 将特征向量(x)代替输入向量x,则可以得到相应的分类函数与非线性分类的广义最优分类的目标函数
3.2 非线性可分的SVM(5/12) 设实函数 (x): RnH 为向量x对应的特征空间H中的特征向量. 将特征向量(x)代替输入向量x,则可以得到相应的分类函数与非线性分类的广义最优分类的目标函数 相应的函数优化的约束条件仍然为

73 由上式可以看出,分类函数与优化函数中只是涉及样本x的特征向量(x)之间的内积,而未直接需要求解出特征向量(x).
3.2 非线性可分的SVM(6/12) 由上式可以看出,分类函数与优化函数中只是涉及样本x的特征向量(x)之间的内积,而未直接需要求解出特征向量(x). 因此,实际上,在高维的特征空间H中只需进行特征向量(x)内积运算,而这种内积运算是可以用原空间中的函数实现的,我们甚至不需要知道变换(x)的形式. 根据泛函理论,只要一种核函数K(xi,xj)=T(xi)(xj)满足Mercer条件,它就对应某一空间中的内积. 因此,在最优分类中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算的复杂度没有增加. 正是这一思路产生了现在非常有效的非线性分类的SVM.

74 SVM的这一特点提供了解决算法可能导致的“维数灾难”问题的方法: 在构造判别函数时,不是对输入空间的样本作非线性变换,然后在特征空间中求解;
而是先在输入空间比较向量(例如求点积或是某种距离),对结果再作非线性变换. 这样,大的工作量将在输入空间而不是在高维特征空间中完成. SVM分类函数形式上类似于一个NN,输出是s中间节点的线性组合,每个中间节点对应一个支持向量,如下图所示.

75 3.2 非线性可分的SVM(8/12)

76 基于核函数K(xi,xj),上述非线性SVM的分类函数与广义最优分类的目标函数分别为
In practical use of SVM, only the kernel function (and not f(.)) is specified. 选取适宜核函数是成功进行非线性分类的关键.

77 则对偶问题的Lagrange函数可以写成：
3.2 非线性可分的SVM(10/12) 下面对偶问题的最优解做一些推导. 定义 则对偶问题的Lagrange函数可以写成： 因此KKT条件为

78 若i=0, 则i0, i=0  (Fibi)yi0
3.2 非线性可分的SVM(11/12) i (i  C ) =  i 由此,我们可以推导出如下关系式： 若i=0, 则i0, i=0  (Fibi)yi0 若0<i<C, 则i=0, i=0  (Fibi)yi=0 若i=C, 则i=0, i0  (Fibi)yi0 由于KKT条件是最优解应满足的充要条件,所以目前提出的一些算法几乎都是以是否违反KKT条件作为迭代策略的准则.

79 Steps for Classification with SVM Prepare the pattern matrix
Select the kernel function to use Select the parameter of the kernel function and the value of C You can use the values suggested by the SVM software, or you can set apart a validation set to determine the values of the parameter Execute the training algorithm and obtain the ai Unseen data can be classified using the ai and the support vectors

80 K2(xi,xj)K(xi,xi)K(xj,xj)
4 核函数(1/8) 4 核函数 对非线性问题,SVM首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间,在这个空间中求广义最优分类面,这里根据不同的内积核函数将形成不同的算法. K(xi,xj)=T(xi)(xj)能选作为SVM方法的核函数须满足如下条件: 1. Must be symmetric K(xi,xj)=K(xj,xi) 2. Must satisfy Cauchy-Schwarz inequality K2(xi,xj)K(xi,xi)K(xj,xj)

81 must be positive semi-definite, 根据上述条件,构造核函数的方法有:
4 核函数(2/8) 3. 满足Mercer’s Theorem,即 must be positive semi-definite, 根据上述条件,构造核函数的方法有: K(xi,xj)=exp[-||xi-xj||2/2] K(xi,xj)=fT(xi)f(xj) K(xi,xj)=K1(xi,xj)+K2(xi,xj) K(xi,xj)=K1(xi,xj) >0

82 K(xi,xj)=exp[K1(xi,xj)] K(xi,xj)=K1(xi,xj)K2(xi,xj)
4 核函数(3/8) K(xi,xj)=exp[K1(xi,xj)] K(xi,xj)=K1(xi,xj)K2(xi,xj) 常用的核函数有 线性内核函数 K(x,xi)=xTxi 多项式核函数 K(x,xi)=(xTxi+1)d 所得到得是d阶多项式分类器

83 K(x,xi)=exp[-||x-xi||2/2] 其经典的径向基函数分类器为
4 核函数(4/8) 径向基函数 K(x,xi)=exp[-||x-xi||2/2] 其经典的径向基函数分类器为 其中kr(||x-xi||) 取决于两个向量之间的距离||x-xi||. 多层感知机,核函数采用sigmoid函数 K(x,xi)=tanh(b1xTxi+b2) 所得到得的非线性分类器为

84 这是1999年Amari和Wu通过对核函数的黎曼几何分析,提出利用实验数据逐步修正原有的核函数,使之更好的适应实际问题.
4 核函数(5/8) 动态核函数 这是1999年Amari和Wu通过对核函数的黎曼几何分析,提出利用实验数据逐步修正原有的核函数,使之更好的适应实际问题. 在应用核函数法时,一般不需要求出核函数K(xi,xj)所对应的特征变换函数(x). 实际上,对许多实用的核函数,也难于求出对应的特征函数. 对2维的多项式核函数 K(x,xi)=(xTxi+1)2 ,可证明对应的特征变换函数(x)为

85 实际上,Mercer定理给出了核函数K(xi,xj)所对应的特征变换函数(x)的存在性.
4 核函数(6/8) 实际上,Mercer定理给出了核函数K(xi,xj)所对应的特征变换函数(x)的存在性. 定理( Mercer定理). 要保证L2下对称的核函数K(x,z)函数能展开成 其中k(x)为一组正交基函数,充分必要条件为对所有非恒为0的L2函数f(x),下式成立

86 核函数K(xi,xj)的实质可以认为是为对输入的样本进行相似性的度量.
4 核函数(7/8) 核函数K(xi,xj)的实质可以认为是为对输入的样本进行相似性的度量. Kernel function can be thought of as a similarity measure between the input objects However, not all similarity measure can be used as kernel function. The kernel function needs to satisfy the Mercer function, i.e., the function is “positive-definite” This has the consequence that the kernel matrix, where the (i,j)-th entry is the K(xi, xj), is always positive definite

87 Note that xi needs not be vectorial for the kernel function to exist.
4 核函数(8/8) Note that xi needs not be vectorial for the kernel function to exist. This opens up enormous opportunities for classification with sequences, graphs, etc., by SVM

88 5 SVM优化方法(1/3) 5 SVM优化方法 由于SVM方法较好的理论基础和它在一些领域的应用中表现出来的优秀的泛化性能,近年来,许多关于SVM方法的研究,包括算法本身的改进和算法的实际应用,都陆续提了出来. 尽管SVM算法的性能在许多实际问题的应用中得到了验证,但是该算法在计算上存在着一些问题,包括 训练算法速度慢、 算法复杂而难以实现以及 检测阶段运算量大 等等.

89 传统的利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的主要原因:
5 SVM优化方法(2/3) 传统的利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的主要原因: 首先,SVM方法需要计算和存储核函数矩阵,当样本点数目较大时,需要很大的内存. 例如,当样本点数目超过4000时,存储核函数矩阵K(xi,xj)需要多达128兆内存. 其次,SVM在二次型寻优过程中要进行大量的矩阵运算,多数情况下,寻优算法是占用算法时间的主要部分.

90 SVM方法的训练运算速度是限制其应用的主要方面,近年来人们针对方法本身的特点提出了许多算法来解决对偶寻优问题.
大多数算法的一个共同的思想就是循环迭代: 将原问题分解为若干子问题,按照某种迭代策略,通过反复求解子问题,最终使结果收敛到原问题的最优解. 根据子问题划分和迭代策略的不同,又可以大致分为： 块算法 固定工作样本集的方法 序贯极小优化以及 其它改进算法

91 A. 块算法 第一类是所谓的“块算法”(chunking algorithm).
5 SVM优化方法--块算法(1/2) A. 块算法 第一类是所谓的“块算法”(chunking algorithm). “块算法”基于的是这样一个事实,即去掉Lagrange乘子等于零的训练样本不会影响原问题的解. 对于给定的训练样本集,如果其中的支持向量是已知的,寻优算法就可以排除非支持向量,只需对支持向量计算权值(即Lagrange乘子)即可. 实际上支持向量是未知的,因此“块算法”的目标就是通过某种迭代方式逐步排除非支持向量.

92 选择一部分样本构成工作样本集进行训练,剔除其中的非支持向量,
5 SVM优化方法--块算法(2/2) 具体的作法是: 选择一部分样本构成工作样本集进行训练,剔除其中的非支持向量, 并用训练结果对剩余样本进行检验,将不符合训练结果(一般是指违反KKT条件)的样本(或其中的一部分)与本次结果的支持向量合并成为一个新的工作样本集,然后重新训练. 如此重复下去直到获得最优结果. 当支持向量的数目远远小于训练样本数目时,“块算法”显然能够大大提高运算速度. 然而,如果支持向量的数目本身就比较多,随着算法迭代次数的增多,工作样本集也会越来越大,算法依旧会变得十分复杂.

93 5 SVM优化方法--固定工作样本集的方法(1/5)
B. 固定工作样本集的方法 因此第二类方法把问题分解成为固定样本数的子问题: 工作样本集的大小固定在算法速度可以容忍的限度内,迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换, 即使支持向量的个数超过工作样本集的大小,也不改变工作样本集的规模,而只对支持向量中的一部分进行优化.

94 5 SVM优化方法--固定工作样本集的方法(2/5)
固定工作样本集的方法和块算法的主要区别在于: 块算法的目标函数中仅包含当前工作样本集中的样本, 而固定工作样本集方法虽然优化变量仅包含工作样本,其目标函数却包含整个训练样本集,即工作样本集之外的样本的Lagrange乘子固定为前一次迭代的结果,而不是像块算法中那样设为0. 而且固定工作样本集方法还涉及到一个确定换出样本的问题(因为换出的样本可能是支持向量). 这样,这一类算法的关键就在于找到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果.

95 5 SVM优化方法--固定工作样本集的方法(3/5)
固定工作样本集的方法最早是由Osuna等人提出的,并对人脸识别问题进行了实验.该方法思想是: 将样本集分为两个集合B和N,集合B作为子问题工作样本集进行SVM训练,集合N中所有样本的Lagrange乘子均置为零. 显然,如果把集合B中对应Lagrange乘子为零的样本i(即i =0,iB)与集合N中的样本j(即i=0,jN)交换,不会改变子问题与原问题的可行性(即仍旧满足约束条件); 而且,当且仅当样本满足条件 (Fibi)yi0 时,替换后的子问题的最优解不变.

96 5 SVM优化方法--固定工作样本集的方法(4/5)
于是可以按照以下步骤迭代求解: 选择集合B,构造子问题; 求子问题最优解i,iB及b,并置j=0,jN; 计算Fj,jN找出其中不满足条件 (Fibi)yi0 的样本j,与B中满足i=0的样本i交换,构成新的子问题. Osuna等人证明了这种迭代算法的收敛性,并给出了两阶多项式分类器在人脸识别问题中的应用结果.

97 5 SVM优化方法--固定工作样本集的方法(5/5)
需要说明的是, Osuna没有说明集合B的大小是否改变. 作者期望的是支持向量的数目非常少,当然可以固定B的大小,作者的意图正是如此. 不过为此需要选择一个较大的B集合,这样看来,其效率可能还不如块算法. 而且如果如果集合B不足以包括所有的支持向量,该算法没有提出改变B的大小的策略,有可能得不到结果.

98 C. 序贯极小优化 前面提到,固定工作样本集方法的关键在于选择一种合适的换入换出策略.
5 SVM优化方法--序贯极小优化(1/5) C. 序贯极小优化 前面提到,固定工作样本集方法的关键在于选择一种合适的换入换出策略. Joachims指出如果采用某种启发式的迭代策略将会提高算法的收敛速度. 最近John C. Platt提出序贯极小优化(Sequential Minimal Optimization, SMO)算法. 该方法将工作样本集的规模减到最小--两个样本. 之所以需要两个样本是因为等式线性约束的存在使得同时至少有两个Lagrange乘子发生变化.

99 由于只有两个变量,而且应用等式约束可以将其中一个用另一个表示出来,所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来.
5 SVM优化方法--序贯极小优化(2/5) 由于只有两个变量,而且应用等式约束可以将其中一个用另一个表示出来,所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来. 这样,算法避开了复杂的数值求解优化问题的过程; 此外,Platt还设计了一个两层嵌套循环分别选择进入工作样本集的样本,这种启发式策略大大加快了算法的收敛速度. 标准样本集的实验结果证明,SMO表现出在速度方面的良好性能.

100 子问题的规模和迭代的次数是一对矛盾,SMO将工作样本集的规模减少到2,一个直接的后果就是迭代次数的增加.
5 SVM优化方法--序贯极小优化(3/5) 子问题的规模和迭代的次数是一对矛盾,SMO将工作样本集的规模减少到2,一个直接的后果就是迭代次数的增加. 所以SMO实际上是将求解子问题的耗费转嫁到迭代上,然后在迭代上寻求快速算法. 但是,SMO迭代策略的思想是可以用到其他迭代算法中的,可见,SMO还有改进的余地.

101 SMO在实际应用中取得了较好的效果,但它也存在着一些问题.
5 SVM优化方法--序贯极小优化(4/5) SMO在实际应用中取得了较好的效果,但它也存在着一些问题. SMO算法每次迭代都要更新b值,但是该值有可能是无法确定的(例如不存在0<i<C的样本,尽管这种情况很少出现),这时SMO采用的方法是确定出的上下界然后取平均值; 另外,每一次迭代过程中的b值仅取决于上次迭代结果的两个变量的最优值,用这个b值判断样本是否满足迭代结果,这就可能存在某些达到最优值的样本却不满足KKT条件的情况,从而影响了该算法的效率.

102 解决算法速度问题的另一个途径是采用序列优化的思想.
5 SVM优化方法--序贯极小优化(5/5) 解决算法速度问题的另一个途径是采用序列优化的思想. 这种方法主要目的是研究当出现新的单个样本时,它与原有样本集或其子集,或是原有样本集训练结果的关系, 例如,它的加入对原有样本集的支持向量集有什么样的影响,怎样迅速地确定它对新的分类器函数的贡献等等. Freitas等人提出了一种用卡尔曼滤波器求解的方法.

103 D. 其它改进算法 针对求解SVM问题的优化命题的困难,研究人员还陆续提出如下改进的优化方法. 修改优化问题法.
由SVM原理可知,对于错分样本,SVM的惩罚项是对松弛因子的累加,但这种累加不必一定是线性的. 因此, 的基本思想是将SVM原问题的惩罚项由线性累加 改为二次累加

104 修改后的对偶问题变为边界约束条件下的二次规划问题,适合迭代求解.
5 SVM优化方法--其它改进算法(2/9) 通过这样修改,可以将Ci作为w的一个分量,同时将样本维数增加一维并规定新的一维为常数yi/C,改写后的目标函数中将不再包含惩罚项,而约束条件中也没有了松弛因子,从而使问题转化为无错分情况下求最大边际的问题. 连续超松弛方法 (Successive Over Relaxation, SOR) 通过在原目标函数中加一项b2,从而使其对偶问题多出一项 ,而约束条件则少了一项等式约束. 修改后的对偶问题变为边界约束条件下的二次规划问题,适合迭代求解. 同时应用矩阵分解技术,每次只更新Lagrange乘子的一个分量,从而不需将所有样本放入内存,大大提高了收敛速度.

105 最小二乘(最小平方,Least Squares,LS)SVM将LS函数引入到SVM中,其目标函数为
约束条件为: 定义相应的Lagrange函数,并运用KT最优条件,可得到一组线性方程. 通过解线性方程组可得到问题的解. 该方法显示出了较低的计算代价.

106 增量学习(Incremental Learning)方法
5 SVM优化方法--其它改进算法(4/9) 增量学习(Incremental Learning)方法 上述两种方法均假设训练集大小是固定的,但现实问题中这一要求在很多情况下是不能满足的. 因此,希望学习机的学习精度应随应用过程中样本集的积累而逐步提高,即学习机应具有增量学习能力. 经典SVM学习算法并不直接支持增量学习.

107 5 SVM优化方法--其它改进算法(5/9) Syed中给出了SVM增量训练算法. 它们直接通过支持向量实现增量SVM学习,即每次只选一小批常规二次规划算法能处理的训练样本,然后保留支持向量,抛弃非支持向量,和新进来的样本混合进行训练,直到训练样本用完. 这种方法可以实现近似的增量学习. 为解决加入新样本后的SVM训练问题,Mettera等人用统计力学上的Adatron方法训练SVM中的系数,它将系数的求解看成系统由不稳定态到稳定态的变化过程. 由Adatron算法改进得出的Kernel-Adatron算法,Frieb通过在线学习构建了大边际超平面,该算法实现简单,但只对于可分数据集有效.

108 萧嵘提出了一种基于遗忘因子的SVM增量学习算法-ISVM.
Cauwenburghs等人提出了增量式求解全局优化问题精确解的方法,增加一个样本或减少一个样本对Lagrange系数和支持向量的影响实验表明算法是有效的. 萧嵘提出了一种基于遗忘因子的SVM增量学习算法-ISVM. 该算法通过在增量学习中逐步积累样本的空间分布知识,使得对样本进行有选择地遗忘成为可能. Fung等人引入了增量线性近似SVM. 该方法的分类精度与常规SVM相同,但训练速度显著提高.

109 该类方法利用了训练集中的几何信息,从SVM的几何意义出发求解问题.
几何方法 该类方法利用了训练集中的几何信息,从SVM的几何意义出发求解问题. 最近点算法 (Nearest Point Algorithm, NPA)通过对样本点进行几何分析,基于两类之间相邻的样本最有可能构成支持向量集的邻域原理来挑选支持向量集. 研究表明,在大规模样本情况下,用邻域原理方法求解支持向量速度极快,同时对计算机资源要求很低. 使用邻域原理方法求出的是一组近似最优的支持向量.

110 邻域原理求支持向量的过程本质上是简化SVM中二次归划目标函数的Hessian矩阵的过程.
该方法不但几何意义明确,而且计算速度快,每次可以消掉内积矩阵的多行多列,所需内存开销小. Fang等人利用了训练向量的结构信息,提出了用几何方法提取卫向量集,并使用卫向量集构建SVM的优化决策面的方法. 张文生等人把SVM原理建立在距离空间上,设计出基于邻域原理的计算海量数据支持向量的算法,并进行了实验分析.

111 A list of SVM implementation can be found at
Some implementation (such as LIBSVM) can handle multi-class classification SVMLight is among one of the earliest implementation of SVM Several Matlab toolboxes for SVM are also available

112 6 SVM方法小结(1/6) 6 支持向量机方法小结 SVM’s Key Ideas, main contributions to learning theory, are maximize the margin between positive and negative examples and optimal classification hyperplane the kernel trick and nonlinear classification non-linear Kernels map examples into a new, hihg-dimension space in which these examples are linear discriminable. Other contributions are Penalize errors in non-separable case Only the support vectors contribute to the solution

113 同时SVM是基于小样本统计理论的基础上的,高维空间特征空间的小样本分类问题,这符合机器学习的目的. 而且SVM比NN具有较好的泛化能力.
优点: SVM理论提供了一种避开高维空间的复杂性,直接用此空间的内积函数(既是核函数),再利用在线性可分的情况下的求解方法直接求解对应的高维空间的决策问题. 当核函数已知,可以简化问题的求解难度. 同时SVM是基于小样本统计理论的基础上的,高维空间特征空间的小样本分类问题,这符合机器学习的目的. 而且SVM比NN具有较好的泛化能力.

114 Given a kernel and a C, there is one unique solution
6 SVM方法小结(3/6) Given a kernel and a C, there is one unique solution Kernels allow very flexible hypotheses The kernel trick allows for a varying complexity of the classifier Training is relatively easy No local optimal, unlike in neural networks Tradeoff between classifier complexity and error can be controlled explicitly Non-traditional data like strings and trees can be used as input to SVM, instead of feature vectors variable-sized hypothesis space sized

115 polynomial-time exact optimization rather than approximate methods
6 SVM方法小结(4/6) polynomial-time exact optimization rather than approximate methods unlike decision trees and neural networks The kernel trick allows for especially engineered representations for problems No strict data model is required (when you can assume it, then use it) The foundation of the SVC is pretty solid (when the slack-variables are not used) An error estimate is available using just the training data (but it is a pretty loose estimate, and cross-validation is still required to optimize K or C)

116 Need to choose a “good” kernel function
6 SVM方法小结(5/6) 缺点: Need to choose a “good” kernel function 对于每个高维空间在此空间的映射F,如何确定F也就是核函数及相应的核函数参数,现在还没有合适的方法. Very large problems are computationally intractable The kernel and C have to be optimized 所以对于一般的问题,SVM只是把高维空间的复杂性的困难转为了求核函数的困难.

117 problems with more than 20,000 examples are very difficult to solve
6 SVM方法小结(6/6) 而且即使确定核函数以后,在求解问题分类时,由于核函数的稠密性,需要大量时间计算核函数及求解函数的二次规划,这就需要大量的计算时间和存储空间(although more and more specialized optimizers appear). 时间复杂性为O(m3) problems with more than 20,000 examples are very difficult to solve 空间复杂性为O(m2) 这也是SVM的一个问题.  Batch algorithm The SVC tends to have problems with highly overlapping classes

118 7 SVM的应用领域和研究进展 SVM的研究进展 核函数的改进
多值分类器的构造 SVM本质是一个二值分类器,而现实中的问题多数都是多类分类问题. 构造K(K为类数量)个SVM二值分类器是解决多值分类的最原始方法,如何利用SVM构造性能更好的多值分类器,是当前的一个研究热点.

119 精度是指SVM的归纳能力,速度是指SVM的分类速度. 海量数据的分类
包括解决SVM中二次规划求解问题,对大规模SVM的求解问题,对SVM中QP问题的求解问题等. 对SVM中算法的优化,包括解决SVM中二次规划求解问题,对大规模SVM的求解问题,对SVM中QP问题的求解问题等.

120 通常,SVM都是批量学习(Batch Learning),即在SVM开始训练前所有的样本都已经产生.
在线学习 通常,SVM都是批量学习(Batch Learning),即在SVM开始训练前所有的样本都已经产生. 然而,在实践中,我们常常会遇到在线学习问题. 如何将SVM理论成功的用于解决在线学习问题无疑具有重要的意义,是SVM研究和应用的一个热点问题. 然而对于标准SVM,每增加一个新的样本,需进行一次二次优化求解问题,运算过于复杂则不具有实时性. 为提高求解速度,研究者们提出了‘分块法’、‘分解法’以及LS-SVM.

121 LS-SVR估计将二次规划问题转变成线性方程组的求解,简化计算的复杂性,在函数估计、逼近和系统建模中得到了广泛应用.
7 SVM的应用领域和研究进展(4/7) LS-SVR估计将二次规划问题转变成线性方程组的求解,简化计算的复杂性,在函数估计、逼近和系统建模中得到了广泛应用. 由于每个样本对估计器都有贡献,LS-SVM失去了支持向量解的稀疏性优点,样本量极大,则模型的维数也极大. 冗余信息的噪声被全部拟合到模型参数里,削弱了模型的鲁棒性,使辨识参数的泛化能力下降. 因此,从大量的训练样本中筛选出有意义的信息,使LS-SVM的支持向量具有稀疏性,Suyken等人对算法进行了改进,取得了一定的效果. 尽管如此,这些算法的运算量都很大,不适用于实时性要求较高的应用场合.

122 7 SVM的应用领域和研究进展(5/7) 最近,一种新的LS-SVM稀疏解算法--矢量基学习算法(Vector Base Learning：VBL)在一定程度上解决了SVM在线学习的问题. 在基矢量集(Base Vector Sets：BVS)张成的解空间基础上,通过判别新样本是否可由这个解空间近似表示,该方法具有剔除样本冗余信息、提升LS-SVM建模鲁棒性、运算量小的优点,避免加入新样本需重新训练所有样本的问题. SVM的应用领域 文本识别 在模式识别领域比NN方法更具有优势,部分的克服了NN方法的缺点,贝尔实验室对美国邮政标准数字库进行了On-line识别试验,还有对手写相似汉字的识别等.

123 研究发现SVM方法的绝对性能对表示空间和预处理技术是相对不敏感的,比特征脸方法更好, 其他获得非常富有竞争性成果的interesting应用
人脸识别 研究发现SVM方法的绝对性能对表示空间和预处理技术是相对不敏感的,比特征脸方法更好, 其他获得非常富有竞争性成果的interesting应用 3D object recognition 网络信息过滤问题 工程勘探识别 生物工程 Stock forecasting Intrusion Detection Systems (IDSs) Image classification

124 Detecting Steganography in digital images
7 SVM的应用领域和研究进展(7/7) Detecting Steganography in digital images Medical applications: diagnostics, survival rates ... Technical: Combustion Engine Knock Detection Elementary Particle Identification in High Energy Physics Bioinformatics: protein properties, genomics, microarrays Information retrieval, text categorization In the following web, more SVM applications can be found

125 8 Support Vector Regression(1/15)
回归分析是建模及参数估计的一种重要方法,在许多领域有重要的应用. 传统的回归分析是针对建模的不同要求,建立使回归分析误差极小的目标函数. 一般这个误差函数多定义为对样本数据的拟合误差的极小化,如拟合误差的平方和极小化. 这样定义的回归目标函数及其给出的优化求解方法(回归分析方法)带来的一个问题是所建立的模型鲁棒性差,对噪声敏感. 此外,对非线性回归,传统的回归分析存在一个结构建模的问题.

126 8 Support Vector Regression(2/15)
针对传统回归分析的局限性,基于SVM的思想,提出一种新的具有良好鲁棒性的回归分析方法—支持向量回归(Support Vector Regression,SVR)法. SVR的主要思想是： nonlinear regression the with approximation of kernel function Linear regression in feature space Unlike in least square regression, the error function is e-insensitive loss function Intuitively, mistake less than e is ignored This leads to sparsity similar to SVM

127 8 Support Vector Regression(3/15)
传统LS回归分析与SVR所定义的回归目标函数分别如下图所示. Value off target Penalty Square loss function e -e Value off target Penalty e-insensitive 1-norm loss function

128 8 Support Vector Regression(4/15)
Value off target Penalty e-insensitive 2-norm loss function

129 8 Support Vector Regression(5/15)
对于传统LS回归分析,回归函数如下图所示：

130 8 Support Vector Regression(6/15)
对基于-insensitive函数的SVR回归分析,回归函数如下图所示：

131 8 Support Vector Regression(7/15)
下面讨论SVR算法： Given: a data set {x1, ..., xn} with target values {u1, ..., un}, we want to do e-SVR The optimization problem is

132 8 Support Vector Regression(8/15)
其中C is a parameter to control the amount of influence of the error The ½||w||2 term serves as controlling the complexity of the regression function This is similar to ridge regression. Similar to SVM, this can be solved as a quadratic programming problem

133 8 Support Vector Regression(9/15)
Similar to SVM, the SVR optimization problem can be solved by the Lagrange method as follows: 其中i, *i, i与*i为拉格朗日乘子,满足 i, *i, i, *i0 根据拉格朗日松弛法的Kuhn-Tucker条件,有

134 8 Support Vector Regression(10/15)

135 8 Support Vector Regression(11/15)
因此,可得 只要确定i, *i,便可解出w,b,i, *i, i, *i

136 8 Support Vector Regression(12/15)
将上述条件代入拉格朗日函数L中,有 其中w,b,i, *i, i, *i可根据i, *i计算出,即优化变量只有i和*i.

137 8 Support Vector Regression(13/15)
因此,SVM广义最优分类面的优化目标函数可变换为如下对偶优化函数 相应的约束条件为

138 8 Support Vector Regression(14/15)
解上述问题后得到的最优回归函数是 式中的求和实际上只对支持向量进行.

139 8 Support Vector Regression(15/15)
Similar to SVM, foe the nonlinear regressiove peoblem, the regressive function with the kernel function is as foloows. 其中K(x,z)为核函数. 对上述SVR问题的对偶优化问题,目前提出如下求解方法： 序贯优化法 分解法 递推法

140 参考文献(1/2) 参考文献 [1] B.E. Boser et al. A Training Algorithm for Optimal Margin Classifiers. Proceedings of the Fifth Annual Workshop on Computational Learning Theory , Pittsburgh, 1992. [2] L. Bottou et al. Comparison of classifier methods: a case study in handwritten digit recognition. Proceedings of the 12th IAPR International Conference on Pattern Recognition, vol. 2, pp [3] V. Vapnik. The Nature of Statistical Learning Theory. 2nd edition, Springer, 1999. [4] C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2): , 1998. [5] N. Cristianini and J. Shawe-Taylor. An introduction to support vector machines, Cambridge University Press

141 参考文献(2/2) 参考文献(续) [6] A. J. Smola and B. Schölkopf. A Tutorial on Support Vector Regression. NeuroCOLT Technical Report NC-TR , Royal Holloway College, University of London, UK, 1998. [7] Feng J., and Williams P. M. (2001) The generalization error of the symmetric and scaled support vector machine IEEE T. Neural Networks Vol.  12, No. 5.  [8] [9] [10] [11]