王磊西南财经大学.ppt
《王磊西南财经大学.ppt》由会员分享,可在线阅读,更多相关《王磊西南财经大学.ppt(73页珍藏版)》请在三一办公上搜索。
1、2023/7/6,1,王磊 西南财经大学,支持向量机 Support Vector Machines,2023/7/6,2,内容提要,统计学习方法概述统计学习问题学习过程的泛化能力支持向量机SVM寻优算法应用,2023/7/6,3,期望风险,学习到一个假设H=f(x,w)作为预测函数,其中w是广义参数.它对F(X,Y)的期望风险R(w)是(即统计学习的实际风险):其中,f(x,w)称作预测函数集,w为函数的广义参数。f(x,w)可以表示任何函数集。L(y,f(x,w)为由于用f(x,w)对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。,2023/7/6,4,而对train s
2、et上产生的风险Remp(w)被称为经验风险(学习的训练误差):,首先Remp(w)和R(w)都是w的函数,传统概率论中的定理只说明了(在一定条件下)当样本趋于无穷多时Remp(w)将在概率意义上趋近于R(w),却没有保证使Remp(w)最小的点也能够使R(w)最小(同步最小)。,经验风险,2023/7/6,5,根据统计学习理论中关于函数集的推广性的界的结论,对于两类分类问题中的指示函数集f(x,w)的所有函数(当然也包括使经验风险员小的函数),经验风险Remp(w)和实际风险R(w)之间至少以不下于1-(01)的概率存在这样的关系:,结构风险,2023/7/6,6,VC维(函数的多样性),为
3、了研究经验风险最小化函数集的学习一致收敛速度和推广性,SLT定义了一些指标来衡量函数集的性能,其中最重要的就是VC维(Vapnik-Chervonenkis Dimension)。VC维:对于一个指示函数(即只有0和1两种取值的函数)集,如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开,则称函数集能够把h个样本打散,函数集的VC维就是能够打散的最大样本数目。如果对任意的样本数,总有函数能打散它们,则函数集的VC维就是无穷大。,2023/7/6,7,VC维(函数的多样性),2023/7/6,8,VC维(续),一般而言,VC维越大,学习能力就越强,但学习机器也越复杂。目前还没有通用
4、的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。N维实数空间中线性分类器和线性实函数的VC维是n+1。Sin(ax)的VC维为无穷大。,2023/7/6,9,VC维(续),Open problem:对于给定的学习函数集,如何用理论或实验的方法计算其VC维是当前统计学习理论研究中有待解决的一个难点问题。,2023/7/6,10,推广性的界,统计学习理论地研究了经验风险和实际风险之间的关系,也即推广性的界。根据SLT中关于函数集推广性界的理论,对于指示函数集中所有的函数,经验风险 和实际风险 之间至少以概率 满足如下关系:其中,h是函数集的VC维,n是样本数。,202
5、3/7/6,11,推广性的界(续1),学习机器的实际风险由两部分组成:训练样本的经验风险置信范围(同置信水平 有关,而且同学习机器的VC维和训练样本数有关。在训练样本有限的情况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与经验风险之间可能的差就越大。,2023/7/6,12,结构风险最小化,传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此,需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小
6、。这种思想称作结构风险最小化(Structural Risk Minimization),即SRM准则。,2023/7/6,13,一般的学习方法(如神经网络)是基于 Remp(w)最小,满足对已有训练数据的最佳拟和,在理论上可以通过增加算法(如神经网络)的规模使得Remp(w)不断降低以至为0。但是,这样使得算法(神经网络)的复杂度增加,VC维h增加,从而(h/l)增大,导致实际风险R(w)增加,这就是学习算法的过拟合(Overfitting).,过学习,2023/7/6,14,过学习Overfitting and underfitting,Problem:how rich class of
7、classifications q(x;)to use.,underfitting,overfitting,good fit,Problem of generalization:a small emprical risk Remp does not imply small true expected risk R.,2023/7/6,15,支持向量机,SVM是一种基于统计学习理论的机器学习方法,它是由Boser,Guyon,Vapnik在COLT-92上首次提出,从此迅速发展起来Vapnik V N.1995.The Nature of Statistical Learning Theory.
8、Springer-Verlag,New York 564Vapnik V N.1998.Statistical Learning Theory.Wiley-Interscience Publication,John Wiley&Sons,Inc目前已经在许多智能信息获取与处理领域都取得了成功的应用。,2023/7/6,16,支持向量机的特色,用间隔定量地定义了置信风险:间隔越大,置信风险越小,间隔越小,置信风险越大用参数C实现了经验风险与置信风险的折中最优分类超平面只由少数支持向量决定,问题具有稀疏性模型为凸二次规划模型,没有陷入局部最优解的问题,任何局部最优解都是全局最优解通过使用核方法,具
9、备了强大的非线性处理能力,2023/7/6,17,线性分类器,a,yest,2023/7/6,18,线性分类器,f,x,a,yest,denotes+1denotes-1,f(x,w,b)=sign(w.x-b),How would you classify this data?,2023/7/6,19,线性分类器,f,x,a,yest,denotes+1denotes-1,f(x,w,b)=sign(w.x-b),How would you classify this data?,Copyright 2001,2003,Andrew W.Moore,2023/7/6,20,线性分类器,f,x
10、,a,yest,denotes+1denotes-1,f(x,w,b)=sign(w.x-b),How would you classify this data?,Copyright 2001,2003,Andrew W.Moore,2023/7/6,21,线性分类器,f,x,a,yest,denotes+1denotes-1,f(x,w,b)=sign(w.x-b),How would you classify this data?,Copyright 2001,2003,Andrew W.Moore,2023/7/6,22,最大间隔,f,x,a,yest,denotes+1denotes-
11、1,f(x,w,b)=sign(w.x-b),The maximum margin linear classifier is the linear classifier with the maximum margin.This is the simplest kind of SVM(Called an LSVM),Linear SVM,Copyright 2001,2003,Andrew W.Moore,2023/7/6,23,分类超平面,Training set:(xi,yi),i=1,2,N;yi+1,-1Hyperplane:wx+b=0This is fully determined
12、by(w,b),2023/7/6,24,考虑 上的线性可分的分类问题.这里有许多直线 能将两类点正确分开.如何选取 和?简单问题:设法方向 已选定,如何选取?解答:选定 平行直线 极端直线 和 取 和 的中间线为分划直线如何选取?对应一个,有极端直线,称 和 之间的距离为“间隔”.显然应选使“间隔”最大的。,最大间隔法的直观导出,2023/7/6,25,数学语言描述,调整,使得,令,则两式可以等价写为,与此相应的分划直线表达式:,给定适当的法方向 后,这两条极端直线 可表示为,2023/7/6,26,如何计算分划间隔?考虑2维空间中极端直线之间的间隔情况,求出两条极端直线的距离:,2023/7
13、/6,27,wx+b=0,wx+b=1,wx+b=-1,wx+b1,wx+b1,Maximum margin summing up,Given a linearly separable training set(xi,yi),i=1,2,N;yi+1,-1Minimise|w|2Subject to This is a quadratic programming problem with linear inequality constraints.There are well known procedures for solving it,2023/7/6,28,支持向量,The traini
14、ng points that are nearest to the separating function are called support vectors.What is the output of our decision function for these points?,2023/7/6,29,分划直线表达式为“间隔”为极大化“间隔”的思想导致求解下列对变量 和 的最优化问题说明:只要我们求得该问题的最优解,从而构造分划超平面,求出决策函数。上述方法对一般 上的分类问题也适用.,原始问题,2023/7/6,30,Margin=,H1平面:,H2平面:,.(2),.(1),2023
15、/7/6,31,求解原始问题,为求解原始问题,根据最优化理论,我们转化为对偶问题来求解,对偶问题,为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题,存在唯一解,2023/7/6,32,线性可分问题,计算,选择 的一个正分量,并据此计算,事实上,的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点,而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为支持向量(SV),构造分划超平面,决策函数,根据最优解,2023/7/6,33,近似线性可分问题,不要求所有训练点都满足约束条件,为此对第 个训练点 引入松弛变量(
16、Slack Variable),把约束条件放松到。,体现了训练集被错分的情况,可采用 作为一种度量来描述错划程度。,两个目标:1.间隔 尽可能大 2.错划程度 尽可能小,显然,当 充分大时,样本点 总可以满足以上约束条件。然而事实上应避免 太大,所以需在目标函数对 进行惩罚,(即“软化”约束条件),2023/7/6,34,因此,引入一个惩罚参数,新的目标函数变为:,体现了经验风险,而 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时,近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。,近似线性可分问题,2023/7/6,35,(广义)线性支持向量分类机
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 西南财经大学
链接地址:https://www.31ppt.com/p-5429415.html