《序贯最小化方法》由会员分享，可在线阅读，更多相关《序贯最小化方法（31页珍藏版）》请在金锄头文库上搜索。
1、罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *序贯最小化方法（Sequential Minimal Optimization，SMO）罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *目录 支持向量机模型C-SVC C-SVC的求解方法 大规模问题时的求解方法罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *支持向量机模型C-SVC罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *二分类问题二分类问题：根据给定的训练集，其中要求寻找 上的决策函数 以便能用决策函数 “较好地”推断任一模 式相对应的 值。罗林开罗
2、林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *支持向量机模型C-SVCC-SVC：这里K(xi,xj)为核函数，常用的核函数有高斯径向基核函 数，多项式核函数，线形核函数等；C为经验风险和置 信风险的折中系数(C大要求经验风险小，C小要求置信 风险小).设*是C-SVC的一个最优解，则分类函数为：罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *支持向量机的特色 用间隔定量地定义了置信风险：间隔越大， 置信风险越小，间隔越小，置信风险越大 用参数C实现了经验风险与置信风险的折中 最优分类超平面只由少数支持向量决定，问 题具有稀疏性 模型为凸二次规划模型，没有
3、陷入局部最优 解的问题，任何局部最优解都是全局最优解 通过使用核方法，具备了强大的非线性处理 能力 罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *C-SVC的求解方法 C-SVC是个凸二次规划问题，所有求解凸二次 规划问题的方法都可用来求解该模型 C-SVC的KKT条件为罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *大规模凸二次规划问题的求解 但是对于大规模问题（即决策变量个数 或样本维数较大），传统的方法（如有 效集方法)基本上难以有效求解. 大规模凸二次规划问题的求解思路：通 过求解一系列小规模（即原决策变量的 一个合适子集）的凸二次规划问题
4、，获 得原问题的解，此类方法统称为分块或 分解的方法.罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *大规模C-SVC的求解方法Chunking方法（Vapnik，1982） 根据去掉非支持向量的样本不会影响最终决策超平面 的事实，可将大规模的QP问题分解为一系列的小规模 QP问题来求解。在迭代的每一步，Chunking求解如下 一个QP子问题：上次迭代的非零Lagrange乘子加上违 反KKT条件最多的M个乘子，QP子问题的初始解为上 次迭代QP子问题的解，一直到所有的乘子都满足KKT 条件为止。进入QP子问题的乘子称为工作集。 Osuna方法（Osuna，1997）
5、固定Chunking工作集的大小，比如每次迭代时加入1个 违反KKT条件的乘子，则需在原工作集中去除一个乘 子。 SMO方法（Platt，1998） 固定Chunking工作集的大小为2(最小).罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *Chunking,Osuna和SMO的工作集比较罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *SMO算法 两个Langrange乘子变量问题的求解 不需迭代，可直接求得其解析解 选取两个Langrange乘子变量的启发式 规则罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *两个Langr
6、ange乘子变量问题的求解罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *选取两个Langrange乘子变量的启发式规则 第一个Langrange乘子的启发式规则 第二个Langrange乘子的启发式规则罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *第一个Langrange乘子的启发式规则 任何违反KKT条件(2)的乘子(或样本)都是合法的 第一个Langrange乘子 第一个Langrange乘子的选择构成SMO算法的外 层循环 外层循环分两种情况选择第一个乘子 在所有乘子中选
7、择（第1次或者(0,C)中没有违法KKT 条件的乘子的情行） 在界内(0,C)乘子中选择（其他情形，这是常规情况） 外层循环分两种情况选择第一个乘子的理由 当SMO算法有进展时，界上的乘子（即等于0或C的 乘子）一般仍停留在界上，界内的乘子才发生改变， 因此首先在界内乘子中选择，可以加快算法的运行时 间罗林开罗林开 模式识别与智能系统研究所模式识别与智能系统研究所 * *第二个Langrange乘子的启发式规则 与第一个乘子的结合，应该使第二个乘子 的迭代步长较大。根据(4)式，第二个乘子 的迭代步长大致正比于|E1-E2|，因此应选 择第二个乘子最大化|E1-E2|，即当E1为 正时最小化E
8、2，当为负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
