支持向量机及其学习算法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《支持向量机及其学习算法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 支持 向量 及其 学习 算法 课件
- 资源描述:
-
1、主要内容主要内容一、一、历史背景历史背景二、二、统计学习理论统计学习理论三、三、支持向量机支持向量机四、四、支持向量机的分类学习算法支持向量机的分类学习算法 五、五、用于函数拟合的支持向量机用于函数拟合的支持向量机 六、六、支持向量机算法的研究与应用支持向量机算法的研究与应用七、七、仿真实例仿真实例传统统计学是一种渐进理论渐进理论,研究的是样本数目趋于无穷大时的极限特性。现有的学习方法多基于传统统计学理论传统统计学理论,但在实际应用中,样本往往是有限的,因此一些理论上很优秀的学习方法在实际中的表现却不尽人意,存在着一些难以克服的问题,比如说如何确定网络结构的问题、过学习问题、局部极小值问题等,
2、从本质本质上来说就是因为理论上需要无穷样本与实际中样本有限的矛盾造成的。与传统统计学的方向不同,Vapnik等人提出了一个较完善的基于有限样本的理论体系统统计学习理论计学习理论。统计学习理论是一种专门研究小样本研究小样本情况下机器学习规律的理论,它从更本质上研究机器学习问题,为解决有限样本学习问题提供了一个统一的框架。支持向量机方法是在统计学习理论基础上发展起来的通用学习方法,它具有全局优化、适应性强、理论完备、泛化性能好等优点。Return统计学习理论统计学习理论 (Statistical Learning Theory,SLT)机器学习的基本问题统计学习理论机器学习问题的表示机器学习问题的
3、表示基于数据的机器学习是现有智能技术中的重要方面,其研究的实质实质是根据给定的训练样本求出对系统输入输出之间依赖关系的估计,使它能对未知样本的输出做出尽可能准确的预测。定义期望风险:,RLfdFyxx y,fx,Lfyx 预测函数集 广义参数 损失函数,F x y联合概率分布 经验风险最小化经验风险最小化 (Empirical Risk Minimization,ERM)实际应用中,一般根据概率论中的大数定理,即采用下式的算术平均来逼近期望风险。用对参数 求经验风险 的最小值代替求期望风险 的最小值。11,nempiiiRLfnyx empR R事实上,从期望风险最小化到经验风险最小化并没有可
4、靠的理论依据,只是直观上合理的想当然做法。经验风险最小化原则不成功的一个例子就是神经网络的过学习过学习问题:训练误差(经验风险)过小反而会导致推广能力的下降,即真实误差(期望风险)的增加。出现过学习现象的原因主要是由于学习样本不充分和学习机器设计不合理。当试图用一个复杂的模型去拟合有限的样本,必然会丧失推广能力。由此可见,有限样本下学习机器的复杂性复杂性与推广性推广性之间存在矛盾。机器的复杂度高,必然会导致其推广性差;反之,一个推广性好的学习机器,其分类能力必然不够强。设计一个好的学习机器的目标目标就变成如何在学习能力和推广性之间取得一个平衡,使得在满足给定学习能力的前提下,提高其推广性。Re
5、turn统计学习理论统计学习理论(SLT)统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。它从理论上较为系统的研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系以及如何利用这些理论找到新的学习原则和方法等问题。其中,最有指导性的理论结果是推广性的界推广性的界的结论,和与此相关的一个核心概念是函数集的函数集的VC维维。函数集的函数集的VC维维 (Vapnik Chervonenkis Dimension)模式识别方法中VC维的直观定义是:对于一个指标函数集,如果存在n个样本能够被函数集中的函数按所有可能的 种形式分开,则称函数集能够把n个样本打散;函数集的VC
6、维就是它能打散的最大样本数目h。有界实函数的VC维可以通过用一定的阈值将其转化为指示函数来定义。VC维反映了函数集的学习能力,维反映了函数集的学习能力,VC维越大则维越大则学习机器越复杂(学习能力越强)。学习机器越复杂(学习能力越强)。2h推广性的界推广性的界 统计学习理论系统地研究了各种类型函数集的经验风险经验风险(即训练误差)(即训练误差)和实际风险实际风险(即期望(即期望风险)风险)之间的关系,即推广性的界。关于两类分类问题有如下结论:对指示函数集中的所有函数,经验风险和实际风险之间至少以概率 满足如下关系:其中h是函数集的VC维,l是样本数。1 lhlhRRemp4ln12ln置信范围
7、置信范围实际实际风险风险学习机器的实际风险由两部分组成:经验风险 ,即训练误差;置信范围(Confidence Interval)可以简单的表示为:它表明在有限样本训练下,学习机VC维越高(机器的复杂性越高),则置信范围越大,导致真实风险与经验风险之间可能的差别越大。这就是为什么出现过学习现象的原因。empR lhRRemp结构风险最小化结构风险最小化 (Structural Risk Minimization,SRM)经验风险最小化原则在样本有限(即 较大)时是不合理的,此时一个小的经验风险值并不能保证小的实际风险值。为解决此问题,就需要在保证分类精度(即减小经验风险)的同时,降低学习机器的
8、VC维,从而使得学习机器在整个样本集上的期望风险得到控制,这就是结构风险最小化(SRM)原则的基本思想。结构风险最小化为我们提供了一种不同于经验风险最小化的更科学的学习机器设计原则,显然,利用结构风险最小化原则的思想,就可以完美解决神经网络中的过学习问题。支持向量机方法实际上就是这种思想的具体实现。lh风险欠学习过学习实际风险的界置信范围经验风险1S2S3Sh函数集子集:VC维:结构风险最小化示意图 321SSS321hhh支持向量机支持向量机 (Support Vector Machine,SVM)90年代中期,在统计学习理论的基础上发展出了一种通用的学习方法支持向量机。它根它根据有限的样本
9、信息在模型的复杂性和学习能力据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以获得最好的泛化能力之间寻求最佳折衷,以获得最好的泛化能力。支持向量机在很多机器学习问题的应用中已初步表现出很多优于已有方法的性能。支持向量机的理论最初来自于对数据分类问题的处理。对于线性可分数据的二值分类,如果采用多层前向网络来实现,其机理可以简单描述为:系统随机的产生一个超平面并移动它,直到训练集合中属于不同类别的点正好位于该超平面的不同侧面,就完成了对网络的设计要求。但是这种机理决定了不能保证最终所获得的分割平面位于两个类别的中心,这对于分类问题的容错性容错性是不利的。保证最终所获得的分割平面位于两个类
10、别的中心对于分类问题的实际应用是很重要的。支持向量机方法很巧妙地解决了这一问题。该方法的机理可以简单描述为:寻找一个满足分类要求的最优分类超平面,使得该超平面在保证分类精度保证分类精度的同时,能够使超平面两侧的空使超平面两侧的空白区域最大化白区域最大化;从理论上来说,支持向量机能够实现对线性可分数据的最优分类。为了进一步解决非线性问题,Vapnik等人通过引入核映核映射射方法转化为高维空间的线性可分问题来解决。最优分类超平面最优分类超平面 (Optimal Hyperplane)对于两类线性可分两类线性可分的情形,可以直接构造最优超平面,使得样本集中的所有样本满足如下条件:(1)能被某一超平面
11、正确划分;(2)距该超平面最近的异类异类向量与超平面之间的距离最大,即分类间隔(margin)最大;以上两个条件体现了结构风险最小化(SRM)的原则。保证经验风险最小保证置信范围最小设训练样本输入为 ,对应的期望输出为 如果训练集中的所有向量均能被某超平面正确划分,并且距离平面最近的异类异类向量之间的距离最大(即边缘margin最大化),则该超平面为最优超平面(Optimal Hyperplane)。ix1,ildiRx1,1iy最优分类面示意图最优分类面示意图 支持向量Support Vector其中距离超平面最近的异类向量被称为支持向量(Support Vector),一组支持向量可以唯一
12、确定一个超平面。SVM是从线性可分情况下的最优分类面发展而来,其超平面记为:为使分类面对所有样本正确分类并且具备分类间隔,就要求它满足如下约束:0bxw1 110 1 1iiiiiibforyybbfory xwxwxw可以计算出分类间隔为 ,因此构造最优超平面的问题就转化为在约束式下求:为了解决这个约束最优化问题,引入下式所示的Lagrange函数:其中 为Lagrange乘数。约束最优化问题的解由Lagrange函数的鞍点决定。2 w 211min 22www w21112lliiiiiiLybwxw 0i利用Lagrange优化方法可以将上述二次规划问题转化为其对偶问题对偶问题,即在约束
13、条件:下对 求解下列函数的最大值:如果 为最优解,那么:liiiy10lii,1,0i 1,112lliijijijii jWy yxxi1liiiiywx以上是在不等式约束下求二次函数极值问题,是一个二次规划问题(Quadratic Programming,QP),),存在唯一解。根据最优性条件Karush-Khn-Tucker条件(KKT条件),这个优化问题的解必须满足:对多数样本对多数样本 将为零,取值不为零的将为零,取值不为零的 所对应所对应的样本即为支持向量,它们通常只是全体样本的样本即为支持向量,它们通常只是全体样本中很少的一部分。中很少的一部分。10,1,iiib yilx wi
14、i求解上述问题后得到的最优分类函数是:在通过训练得到最优超平面后,对于给定的未知样本x,只需计算f(x)即可判断x所属的分类。1sgnliiiifybxxx若训练样本集是线性不可分的,或事先不知道它是否线性可分,将允许存在一些误分类的点,此时引入一个非负松弛变量非负松弛变量 ,约束条件变为:目标函数改为在以上约束条件下求:即折衷考虑最小错分样本和最大分类间隔。其中,C0 为惩罚因子,控制对错分样本的惩罚程度。0i1 0 1,iiiiybil w x,11min ,2liiCww w线性不可分情况和线性可分情况的差别差别就在于可分模式中的约束条件中的 在不可分模式中换为了更严格的条件 。除了这一
15、修正,线性不可分情况的约束最优化问题中权值和阈值的最优值的计算都和线性可分情况中的过程是相同的。0i0iC支持向量机支持向量机 (Support Vector Machine,SVM)在现实世界中,很多分类问题都是线性不可分的,即在原来的样本空间中无法找到一个最优的线性分类函数,这就使得支持向量机的应用具有很大的局限性。但是可以设法通过非线性通过非线性变换将原样本空间的非线性问题转化为另一个变换将原样本空间的非线性问题转化为另一个空间中的线性问题空间中的线性问题。SVM就是基于这一思想的。首先将输入向量通过非线性映射变换到一个高维的特征向量空间,在该特征空间中构造最优分类超平面。由于在上面的二
16、次规划(QP)问题中,无论是目标函数还是分类函数都只涉及内积运算,如果采用核函数(Kernel Function)就可以避免在高维空间进行复杂运算,而通过原空间的函数来实现内积运算。因此,选择合适的内积核函数核函数 就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加多少,从而巧妙地解决了高维空间中计算带来的“维数灾难”问题。,ijijK x xxx此时,相应的决策函数化为:支持向量机求得的决策函数形式上类似于一个神经网络,其输出是若干中间层节点的线性组合,而每一个中间层节点对应于输入样本与一个支持向量的内积,因此也被称作是支持向量网络。1sgn,liiiifyKbxx x支持向量机示
展开阅读全文