支持向量机(五)smo算法 - jerrylead - 博客园

1、15-12-11支持向量机（五）SMO算法 - JerryLead - 博客园 支持向量机（五）SMO算法 11 SMO优化算法（Sequential minimal optimization） SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线 性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines了。 我拜读了一下，下面先说讲义上对此方法的总结。 首先回到我们前面一直悬而未解的问题，对偶函数最后的优化问题： 要解决的是在参数上求最大值W的问题，至于和都是已知数。C由我们预先设定，也是已知 数。 按照坐标上升的思路，我们首先固定除以外的所有参数，然后在上求极值。等一下，这个思路有问题，因为如 果固定以外的所有参数，那么将不再是变量（可以由其他值推出），因为问题中规定了 因此，我们需要一次选取两个参数做优化，比如和，此时可以

2、由和其他参数表示出来。这样回带到W 中，W就只是关于的函数了，可解。 这样，SMO的主要步骤如下： 意思是，第一步选取一对和，选取方法使用启发式方法（后面讲）。第二步，固定除和之外的其他参数， 确定W极值条件下的，由表示。 SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效。 下面讨论具体方法： 假设我们选取了初始值满足了问题中的约束条件。接下来，我们固定，这样W就是 和的函数。并且和满足条件： 由于都是已知固定值，因此为了方面，可将等式右边标记成实数值 。 公告 Contact me via 昵称：JerryLead 园龄：4年9个月 粉丝：1468 关注：4 +加关注 导航 博客园 首页 新随笔 联系 订阅 管理 日一二三四五六 272812345 6789101112 13141516171819 20212223242526 272829303112 3456789 统计 随笔 - 27 文章 - 0 评论 - 351 引用 - 0 搜索 找找看 谷歌搜索 常用链接 我的随笔 我的评论 我的参与 最新评论 我的标签 我的标签 Machine Learning(2

3、2) Big Data(3) Maths(1) 随笔档案(27) 2013年4月 (1) 2012年8月 (2) 2012年5月 (1) 2011年8月 (1) 2011年6月 (1) 2011年5月 (2) 2011年4月 (10) 2011年3月 (9) JerryLead All things are difficult before they are easy. 15-12-11支持向量机（五）SMO算法 - JerryLead - 博客园 当和异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1。如下图： 横轴是，纵轴是，和既要在矩形方框内，也要在直线上，因此 ， 同理，当和同号时， ， 然后我们打算将用表示： 然后反代入W中，得 展开后W可以表示成。其中a,b,c是固定值。这样，通过对W进行求导可以得到，然而要保证 满足，我们使用表示求导求出来的，然而最后的，要根据下面情况得到： 这样得到后，我们可以得到的新值。 下面进入Platt的文章，来找到启发式搜索的方法和求b值的公式。 这边文章使用的符号表示有点不太一样，不过实质是一样的，先来熟悉一下文章中符号

4、的表示。 文章中定义特征到结果的输出函数为 与我们之前的实质是一致的。 原始的优化问题为： 求导得到： 经过对偶后为： 积分与排名 积分 - 27628 排名 - 7638 最新评论 1. Re:小谈导数、梯度和极值 giveme5为什么=6?. -midu 2. Re:线性判别分析（Linear Discriminant Analysis）（一） xzf125244170这里(lamba_w 是新引入的一个常数). -邊城浪子 3. Re:Hadoop vs Spark性能对比 Spark本身就是对迭代计算有优势的。 -四通大哥 4. Re:PDF版学习笔记 感谢：） -drsalar 5. Re:PDF版学习笔记 为什么没法下载啊？ -独步苍穹 阅读排行榜 1. Spark安装与学习(117261) 2. （EM算法）The EM Algorithm(114611) 3. 支持向量机SVM（一）(102104) 4. K-means聚类算法(100471) 5. 对线性回归，logistic回归和一般回 归的认识(63705) 评论排行榜 1. （EM算法）The EM Algor

5、ithm(51) 2. 支持向量机（五）SMO算法(36) 3. PDF版学习笔记(29) 4. 支持向量机SVM（一）(21) 5. 主成分分析（Principal components analysis）-最大方差 解释(21) 推荐排行榜 1. （EM算法）The EM Algorithm(53) 2. 支持向量机SVM（一）(34) 3. K-means聚类算法(30) 4. 主成分分析（Principal components analysis）-最大方差 解释(23) 5. 支持向量机（三）核函数(18) 15-12-11支持向量机（五）SMO算法 - JerryLead - 博客园 s.t. 这里与W函数是一样的，只是符号求反后，变成求最小值了。和是一样的，都表示第i个样本的输出结果（1 或-1）。 经过加入松弛变量后，模型修改为： 由公式（7）代入（1）中可知， 这个过程和之前对偶过程一样。 重新整理我们要求的问题为： 与之对应的KKT条件为： 这个KKT条件说明，在两条间隔线外面的点，对应前面的系数为0，在两条间隔线里面的对应为C，在两条间隔 线上的对应的系数在0和

6、C之间。 将我们之前得到L和H重新拿过来： 之前我们将问题进行到这里，然后说将用表示后代入W中，这里将代入中，得 其中 这里的和代表某次迭代前的原始值，因此是常数，而和是变量，待求。公式（24）中的最后一项是常 数。 由于和满足以下公式 因为的值是固定值，在迭代前后不会变。 15-12-11支持向量机（五）SMO算法 - JerryLead - 博客园 那么用s表示，上式两边乘以时，变为： 其中 代入（24）中，得 这时候只有是变量了，求导 如果的二阶导数大于0（凹函数），那么一阶导数为0时，就是极小值了。 假设其二阶导数为0（一般成立），那么上式化简为： 将w和v代入后，继续化简推导，得（推导了六七行推出来了） 我们使用 来表示： 通常情况下目标函数是正定的，也就是说，能够在直线约束方向上求得最小值，并且。 那么我们在（30）两边都除以 可以得到 这里我们使用表示优化后的值，是迭代前的值，。 与之前提到的一样不是最终迭代后的值，需要进行约束： 那么 在特殊情况下， 可能不为正，如果核函数K不满足Mercer定理，那么目标函数可能变得非正定， 可能出现负值。 即使K是有效的核函数，如

7、果训练样本中出现相同的特征x，那么 仍有可能为0。SMO算法在 不为正值的情况下仍 有效。为保证有效性，我们可以推导出 就是的二阶导数，没有极小值，最小值在边缘处取到（类比 ），时更是单调函数了，最小值也在边缘处取得，而的边缘就是L和H。这样将和分 别代入中即可求得的最小值，相应的还是也可以知道了。具体计算公式如下： 15-12-11支持向量机（五）SMO算法 - JerryLead - 博客园 至此，迭代关系式出了b的推导式以外，都已经推出。 b每一步都要更新，因为前面的KKT条件指出了和的关系，而和b有关，在每一步计算出后，根据KKT条 件来调整b。 b的更新有几种情况： 来自罗林开的ppt 这里的界内指，界上就是等于0或者C了。 前面两个的公式推导可以根据 和对于有的KKT条件推出。 这样全部参数的更新公式都已经介绍完毕，附加一点，如果使用的是线性核函数，我们就可以继续使用w了，这样 不用扫描整个样本库来作内积了。 w值的更新方法为： 根据前面的 公式推导出。 12 SMO中拉格朗日乘子的启发式选择方法 终于到了最后一个问题了，所谓的启发式选择方法主要思想是每次选择拉格朗日乘子

8、的时候，优先选择样本前面系 数的作优化（论文中称为无界样例），因为在界上（为0或C）的样例对应的系数一般不会更改。 这条启发式搜索方法是选择第一个拉格朗日乘子用的，比如前面的。那么这样选择的话，是否最后会收敛。可幸 的是Osuna定理告诉我们只要选择出来的两个中有一个违背了KKT条件，那么目标函数在一步迭代后值会减小。 违背KKT条件不代表，在界上也有可能会违背。是的，因此在给定初始值=0后，先对所有样例进行循 环，循环中碰到违背KKT条件的（不管界上还是界内）都进行迭代更新。等这轮过后，如果没有收敛，第二轮就只 针对的样例进行迭代更新。 在第一个乘子选择后，第二个乘子也使用启发式方法选择，第二个乘子的迭代步长大致正比于，选择第二 个乘子能够最大化。即当为正时选择负的绝对值最大的，反之，选择正值最大的。 最后的收敛条件是在界内（）的样例都能够遵循KKT条件，且其对应的只在极小的范围内变动。 至于如何写具体的程序，请参考John C. Platt在论文中给出的伪代码。 13 总结 15-12-11支持向量机（五）SMO算法 - JerryLead - 博客园 JerryLead 关注

9、- 4 粉丝 - 1468 +加关注 180 (请您对文章做出评价) 这份SVM的讲义重点概括了SVM的基本概念和基本推导，中规中矩却又让人醍醐灌顶。起初让我最头疼的是拉格 朗日对偶和SMO，后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日 乘子的单一参数优化问题。而SMO里面迭代公式的推导也着实让我花费了不少时间。 对比这么复杂的推导过程，SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点（中间加了一 层sigmoid函数变换），而是就在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。 之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了w可以由特征向量内积来表 示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表 现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优 化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日 对偶和SMO算法化解，使SVM趋向于完美。 另外，其他很多议题如SVM背后的学习理论、参数选择问题、二值分类到多值分类等等还没有涉及到，以后有时间 再学吧。其实朴素贝叶斯在分类二值分类问题时，如果使用对数比，那么也算作线性分类器。 标签: Machine Learn

《支持向量机(五)smo算法 - jerrylead - 博客园》由会员小**分享，可在线阅读，更多相关《支持向量机(五)smo算法 - jerrylead - 博客园》请在金锄头文库上搜索。