改进的SMO算法
S. S. Keerthi等人在Improvements to Platt’s SMO Algorithm for SVM Classifier Design一文中提出了对SMO算法的改进,纵观SMO算法,其核心是怎么选择每轮优化的两个拉格朗日乘子,标准的SMO算法是通过判断乘子是否违反原问题的KKT条件来选择待优化乘子的,由KKT条件:
是否违反它,与这几个因素相关:拉格朗日乘子 、样本标记 、偏置b 。 b的更新依赖于两个优化拉格朗日乘子,这就可能出现这种情况:拉格朗日乘子 已经能使目标函数达到最优,而SMO算法本身并不能确定当前由于两个优化拉格朗日乘子计算得到的b是否就是使目标函数达到最优的那个b,换句话说,对一些本来不违反KKT条件的点,由于上次迭代选择了不合适的,使得它们出现违反KKT条件的情况,导致后续出现一些耗时而无用的搜索,针对标准SMO的缺点,出现了以下改进方法。
对于SVM的最优化问题的解:
定义:
是拉格朗日乘子,通过解下面对偶问题,我们可以得到:
一旦确定,其他参数如:就很容易由KKT条件确定了,并且解是不唯一的,最后得拉格朗日函数如下:
定义:
则对偶问题的KKT条件如下:
这个条件可以简化成下面三种情况:
1.:
2.
3.
定义如下数集:I0 = {i: 0 < αi < C}; I1 ={i: yi = 1,αi = 0}; I2 = {i: yi = −1,αi = C}; I3 = {i: yi = 1,αi = C};I4 = {i: yi = −1,αi = 0}.
可以看到以上的KKT条件成立当且仅当有一个使得下式成立:
定义:
当且仅当blow ≤ bup.成立时KKT条件成立。更进一步KKT条件可以写成如下形式:
是一个正的容忍因子。
最新文章
- C和指针 第十七章 经典数据类型 堆栈 队列 二叉树
- #ifndef 的用法
- Leetcode 95. Unique Binary Search Tree II
- Html/Css(新手入门第一篇)
- VS2010下 LibVLC开发环境搭建
- 区间DP+next求循环节 uva 6876
- J - 病毒
- [GRYZ2015]快排练习
- java Permissions and Security Policy--官方文档
- 关于文件读写IDL
- 本地访问服务器上的wamp
- 2019CVTE技术支持软件编程
- 【转】c语言中的#号和##号的作用
- 19)django-cookie使用
- Zynq-PL中创建AXI Master接口IP及AXI4-Lite总线主从读写时序测试(转)
- vim学习相关链接
- Robot Framework(Collections 库)
- python3 爬虫爬取深圳公租房轮候库(深圳房网)
- HDU-1151
- python bottle学习(三)动态路由配置(通配符)
热门文章
- 2016032101 - eclipse3.7+jdk1.6+maven3.0.5
- FatFsVersion0.01源码分析
- Python元类实践--自己定义一个和collections中一样的namedtuple
- 一个简单的php分页类代码(转载)
- 使用Yeoman搭建 AngularJS 应用 (1) —— 介绍
- Tomcat 性能调优 出现java.lang.OutOfMemoryError: PermGen space
- Javascript与C#相互调用
- MongoDB实战指南(五):MongoDB中的聚集分析
- 在eclipse中将项目发布到tomcat的root目录
- solr的原子更新/局部更新