全部版块 我的主页
论坛 数据科学与人工智能 数据分析与数据科学 数据分析与数据挖掘
5028 6
2014-03-12
这阵子在看支持向量机,看了许久,但是还有一些问题一直困扰着我,特来论坛求助:

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

问题1:

如何理解以下这句话:

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

     (已解决):


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

q1.jpg

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

q2.jpg

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


情景2:

q3.jpg

补充:

q7.jpg

问题2.1(已解决):当a1和a2都在界内时,如何推出b1new=b2new?

问题2.2(已解决):为什么当a1和a2都在界上时,b1new=b2new之间b都满足要求?


情景3:

q5.jpg

q6.jpg

问题3(已解决):

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


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



附件列表
q4.jpg

原图尺寸 36.62 KB

q4.jpg

二维码

扫码加我 拉你入群

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

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

全部回复
2014-3-12 22:39:27
学习了,谢谢
二维码

扫码加我 拉你入群

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

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

2014-3-16 00:51:33
提供几遍论文的摘要,以供参考:
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 ..
二维码

扫码加我 拉你入群

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

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

2014-3-16 00:52:40
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.
二维码

扫码加我 拉你入群

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

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

2014-3-16 00:54:06
上遍的作者为: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.
二维码

扫码加我 拉你入群

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

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

2014-3-16 00:57:57
Leon Bottou
Chih-Jen Lin
Considerable e orts 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.
二维码

扫码加我 拉你入群

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

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

点击查看更多内容…
相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

扫码加好友,拉您进群
各岗位、行业、专业交流群