技术心得大数据 爬虫Python AI Sql统计学习方法-李航

统计学习方法-7 支持向量机-3

2019-07-07  本文已影响2人  Eric_i33

3 非线性支持向量机、SMO算法
3.1 目标函数继续变形
理论上,KKT条件可以解出SVM,但是当训练集容量很大时,这种方法显得异常低效,甚至无法使用。SMO(sequential minimal optimization)算法,首先继续优化目标函数,关键点是通过求极值提炼出对偶函数的最小化表达式

3.2 SMO算法
SMO算法是一种启发式算法,选择两个变量(在这里变量就是对偶变量alpha),要求一个是违反KKT条件最严重的一个,另一个由约束条件生成,其余变量固定;不断优化两两组合的变量直到所有变量满足KKT条件;再计算得到原问题的解w和b。

a1和a2的求解思维如下,从目标函数中剥离出一组a1和a2,建立二者的线性关系(公式写到眼瞎):

消元去掉a1,优化得到a2的未剪辑值

再根据约束条件,得到a2的更新值,此处要考虑y1和y2同号和异号两种情况,在同号的情况下,a1y1 + a2y2 的直线斜率为,a2的上确界和下确界如下所示:


在异号的情况下,a1y1 + a2y2 的直线斜率为,a2的上确界和下确界如下所示:


综上,得到a2的更新值,a2有了,a1的更新值也就有了,此时 w 亦可求,关键还要求 b:

求解 b:

3.3 如何挑选a1和a2
步骤:
(1)、选取初始值a = 0,b = 0,计算所有的 Ei 并保存为列表

(2)、外循环:选取违反KKT条件最严重的样本点,定为a1
(2.1)、首先检查支持向量,遍历所有满足 0<a1<C 的点(即在间隔边界上的支持向量),如果出现点违反KKT条件,定为a1
(2.2)、如果(2.1)都满足,再遍历整个训练集,检查是否违反KKT,定为a1

(3)、内循环:当a1确定后,选取a2
(3.1)、取 max|E1-E2| 的点(即更新幅度最大)
(3.2)、若存在多个 max|E1-E2|,取 0<a2<C 的点(支持向量)
(3.3)、如果没有,依次取其他点
(3.4)、如果还是没有,放弃a1,重复(2)

(4)、更新a1, a2, b, Ei
(5)、迭代,直至在精度eps内满足停止条件

未完待续

上一篇下一篇

猜你喜欢

热点阅读