关于支持向量机（SVM）实现算法SMO的疑问，可能大家都会遇到

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

这阵子在看支持向量机，看了许久，但是还有一些问题一直困扰着我，特来论坛求助：

情景1：
    外层循环分两种情况选择第一个乘子的理由：当SMO算法有进展时，界上的乘子（即等于0或者C的乘子）更新后很有可能仍然停留在界上，界内的乘子才发生改变，因此首先在界内乘子中选择，可以加快算法的运行时间。

问题1：

如何理解以下这句话：

界上乘子更新后很有可能仍然停留在界上。

     （已解决）：

       界上乘子更新后很有可能仍然停留在界上的解释：

上图红点表示待更新的两个乘子的对应坐标，其中a2在界上a2=0，假设核矩阵正定，根据：

η>0,因此若a2更新后值发生变化，必须y2(E1-E2)>0，而在后面的工作集选择并不能够确保该式成立，若y2(E1-E2)<=0，则a2的值保持不变，因此更新失败，仍然留在界上。其他情形依次类推。

情景2：

补充：

问题2.1（已解决）：当a1和a2都在界内时，如何推出b1new=b2new？

问题2.2（已解决）：为什么当a1和a2都在界上时，b1new=b2new之间b都满足要求？

情景3：

问题3（已解决）：

这一块完全不懂。我们在写内循环的时候，要写当L==H的时候，跳出内循环，因为L==H的时候计算的结果肯定不符合KKT条件，可是为什么呢？完全搞不懂呃~。

希望得到大家帮助，临表涕零，不知所言。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：支持向量机 向量机 SVM SMO 运行时间 如何 正定

学习了，谢谢

提供几遍论文的摘要，以供参考：
1、 S.S.Keerthi ..: This paper points out an importance source of confusion and inefficiency in Platt's Sequential Minimal Optimization (SMO) algorithm than is caused by the use of a single treshold value . Using clues from thd KKT conditions for thd dual problem ,two threshold parameters are employed to derive modifications SMO . These modified algorithms perform significatly faster than the original SMO on all benchmark datasets tried ..

2.   Decomposition methods are currently one of the major methods for training support vector machines.
They vary mainly according to different working set selections. Existing implementations
and analysis usually consider some specific selection rules. This article studies Sequential Minimal
Optimization (SMO)-type decomposition methods under a general and flexible way of choosing the
two-element working set. Main results include: 1) a simple asymptotic convergence proof, 2) a general
explanation of the shrinking and caching techniques, and 3) the linear convergence of the methods.
Extensions to some SVM variants are also discussed.

上遍的作者为：Pai-Hsuen Chen 等.
  3。  Rong-En Fan 等： Working set selection is an important step in decomposition methods for training support
vector machines (SVMs). This paper develops a new technique for working set selection in
SMO-type decomposition methods. It uses second order information to achieve fast con-
vergence. Theoretical properties such as linear convergence are established. Experiments
demonstrate that the proposed method is faster than existing selection methods using first
order information.

Leon Bottou
Chih-Jen Lin
Considerable eorts have been devoted to the implementation of an ecient optimization
method for solving the support vector machine dual problem. This chapter
proposes an in-depth review of the algorithmic and computational issues associated
with this problem. Besides this baseline, we also point out research directions that
are exploited more thoroughly in the rest of this book.

大神，这个问题我也不懂，能不能麻烦您讲解一下呢？文章看了，还是不明白b值的更新。