- 1、本文档共31页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
序贯最小化方法SequentialMinimalOptimizationSMO
序贯最小化方法(Sequential Minimal Optimization,SMO) 目录 支持向量机模型C-SVC C-SVC的求解方法 大规模问题时的求解方法 支持向量机模型C-SVC 二分类问题 二分类问题:根据给定的训练集, 其中 要求寻找 上的决策函数 以便能用决策函数 “较好地”推断任一模式相对应的 值。 支持向量机模型C-SVC 支持向量机的特色 用间隔定量地定义了置信风险:间隔越大,置信风险越小,间隔越小,置信风险越大 用参数C实现了经验风险与置信风险的折中 最优分类超平面只由少数支持向量决定,问题具有稀疏性 模型为凸二次规划模型,没有陷入局部最优解的问题,任何局部最优解都是全局最优解 通过使用核方法,具备了强大的非线性处理能力 C-SVC的求解方法 C-SVC是个凸二次规划问题,所有求解凸二次规划问题的方法都可用来求解该模型 C-SVC的KKT条件为 大规模凸二次规划问题的求解 但是对于大规模问题(即决策变量个数或样本维数较大),传统的方法(如有效集方法)基本上难以有效求解. 大规模凸二次规划问题的求解思路:通过求解一系列小规模(即原决策变量的一个合适子集)的凸二次规划问题,获得原问题的解,此类方法统称为分块或分解的方法. 大规模C-SVC的求解方法 Chunking方法(Vapnik,1982) 根据去掉非支持向量的样本不会影响最终决策超平面的事实,可将大规模的QP问题分解为一系列的小规模QP问题来求解。在迭代的每一步,Chunking求解如下一个QP子问题:上次迭代的非零Lagrange乘子加上违反KKT条件最多的M个乘子,QP子问题的初始解为上次迭代QP子问题的解,一直到所有的乘子都满足KKT条件为止。进入QP子问题的乘子称为工作集。 Osuna方法(Osuna,1997) 固定Chunking工作集的大小,比如每次迭代时加入1个违反KKT条件的乘子,则需在原工作集中去除一个乘子。 SMO方法(Platt,1998) 固定Chunking工作集的大小为2(最小). Chunking,Osuna和SMO的工作集比较 SMO算法 两个Langrange乘子变量问题的求解 不需迭代,可直接求得其解析解 选取两个Langrange乘子变量的启发式规则 两个Langrange乘子变量问题的求解 选取两个Langrange乘子变量的启发式规则 第一个Langrange乘子的启发式规则 第二个Langrange乘子的启发式规则 第一个Langrange乘子的启发式规则 任何违反KKT条件(2)的乘子(或样本)都是合法的第一个Langrange乘子 第一个Langrange乘子的选择构成SMO算法的外层循环 外层循环分两种情况选择第一个乘子 在所有乘子中选择(第1次或者(0,C)中没有违法KKT条件的乘子的情行) 在界内(0,C)乘子中选择(其他情形,这是常规情况) 外层循环分两种情况选择第一个乘子的理由 当SMO算法有进展时,界上的乘子(即等于0或C的乘子)一般仍停留在界上,界内的乘子才发生改变,因此首先在界内乘子中选择,可以加快算法的运行时间 第二个Langrange乘子的启发式规则 与第一个乘子的结合,应该使第二个乘子的迭代步长较大。根据(4)式,第二个乘子的迭代步长大致正比于|E1-E2|,因此应选择第二个乘子最大化|E1-E2|,,即当E1为正时最小化E2,当为负E1时最大化E2. b,u,E,w 的更新 SMO算法的框架 给定精度?,初始的?(0)=0,k=0; 利用启发式规则选择优化的两个langrange乘子变量?1(k)和?2(k),并求解关于这两个变量的最优化问题(4),得最优解?1(k+1)和?2(k+1),据此更新?得到?(k+1) ; 若在精度内满足停机准则,即KKT条件(2),则转第(4)步;否则令k=k+1,转第(2)步; 取近似最优解?*= ?(k+1). 选择两个乘子变量的一些启发式规则 Maximal Violating Pair (Keerthi et al. 2001).被应用在LIBSVM软件包(Chang and Lin,2001)中. Using Second Order Information (Fan,Chen,and Lin,2005) Maximal Violating Pair KKT条件的另一种描述 Maximal Violating Pair 违反对 Using Second Order Information 但是不象最大违反对准则,在这里要获得最优的2个乘子变量,没有简单规则,可以让我们逃避Cl2的比较。 实现方法:采用一些启发式规则,只检查乘子变量的一些组合,获得可接受(不是最优)的2个乘子变量(WSS2) Non-
文档评论(0)