smo优化,smo优化算法

将乐信息网 http://www.jianglexinxi.cn 2020-07-01 08:03 出处:网络
smo优化,smo优化算法,SMO优化算法(转) 11 SMO优化算法(Sequential minimal optimization)转自 http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html

smo优化,smo优化算法,SMO优化算法(转)

11 SMO优化算法(Sequential minimal optimization)转自 http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html

SMO算法由Microsoft Research的John C. Platt在1998年提出,并成为最快的二次规划优化算法,特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。

我拜读了一下,下面先说讲义上对此方法的总结。

首先回到我们前面一直悬而未解的问题,对偶函数最后的优化问题:

smo优化,smo优化算法

要解决的是在参数

smo优化,smo优化算法

上求最大值W的问题,至于

smo优化,smo优化算法

smo优化,smo优化算法

都是已知数。C由我们预先设定,也是已知数。

按照坐标上升的思路,我们首先固定除

smo优化,smo优化算法

以外的所有参数,然后在

smo优化,smo优化算法

上求极值。等一下,这个思路有问题,因为如果固定

smo优化,smo优化算法

以外的所有参数,那么

smo优化,smo优化算法

将不再是变量(可以由其他值推出),因为问题中规定了

smo优化,smo优化算法

因此,我们需要一次选取两个参数做优化,比如

smo优化,smo优化算法

smo优化,smo优化算法

,此时

smo优化,smo优化算法

可以由

smo优化,smo优化算法

和其他参数表示出来。这样回带到W中,W就只是关于

smo优化,smo优化算法

的函数了,可解。

这样,SMO的主要步骤如下:

smo优化,smo优化算法

意思是,第一步选取一对

smo优化,smo优化算法

smo优化,smo优化算法

,选取方法使用启发式方法(后面讲)。第二步,固定除

smo优化,smo优化算法

smo优化,smo优化算法

之外的其他参数,确定W极值条件下的

smo优化,smo优化算法

smo优化,smo优化算法

smo优化,smo优化算法

表示。

SMO之所以高效就是因为在固定其他参数后,对一个参数优化过程很高效。

下面讨论具体方法:

假设我们选取了初始值

smo优化,smo优化算法

满足了问题中的约束条件。接下来,我们固定

smo优化,smo优化算法

,这样W就是

smo优化,smo优化算法

smo优化,smo优化算法

的函数。并且

smo优化,smo优化算法

smo优化,smo优化算法

满足条件:

smo优化,smo优化算法

由于

smo优化,smo优化算法

都是已知固定值,因此为了方面,可将等式右边标记成实数值

smo优化,smo优化算法

smo优化,smo优化算法

smo优化,smo优化算法

smo优化,smo优化算法

异号时,也就是一个为1,一个为-1时,他们可以表示成一条直线,斜率为1。如下图:

smo优化,smo优化算法

横轴是

smo优化,smo优化算法

,纵轴是

smo优化,smo优化算法

smo优化,smo优化算法

smo优化,smo优化算法

既要在矩形方框内,也要在直线上,因此

smo优化,smo优化算法

smo优化,smo优化算法

同理,当

smo优化,smo优化算法

smo优化,smo优化算法

同号时,

smo优化,smo优化算法

smo优化,smo优化算法

然后我们打算将

smo优化,smo优化算法

smo优化,smo优化算法

表示:

smo优化,smo优化算法

然后反代入W中,得

smo优化,smo优化算法

展开后W可以表示成

smo优化,smo优化算法

。其中a,b,c是固定值。这样,通过对W进行求导可以得到

smo优化,smo优化算法

,然而要保证

smo优化,smo优化算法

满足

smo优化,smo优化算法

,我们使用

smo优化,smo优化算法

表示求导求出来的

smo优化,smo优化算法

,然而最后的

smo优化,smo优化算法

,要根据下面情况得到:

smo优化,smo优化算法

这样得到

smo优化,smo优化算法

后,我们可以得到

smo优化,smo优化算法

的新值

smo优化,smo优化算法

下面进入Platt的文章,来找到启发式搜索的方法和求b值的公式。

这边文章使用的符号表示有点不太一样,不过实质是一样的,先来熟悉一下文章中符号的表示。

文章中定义特征到结果的输出函数为

smo优化,smo优化算法

与我们之前的

smo优化,smo优化算法

实质是一致的。

原始的优化问题为:

smo优化,smo优化算法

求导得到:

smo优化,smo优化算法

经过对偶后为:

smo优化,smo优化算法

s.t. 

smo优化,smo优化算法

smo优化,smo优化算法

这里与W函数是一样的,只是符号求反后,变成求最小值了。

smo优化,smo优化算法

smo优化,smo优化算法

是一样的,都表示第i个样本的输出结果(1或-1)。

经过加入松弛变量

smo优化,smo优化算法

后,模型修改为:

smo优化,smo优化算法

smo优化,smo优化算法

由公式(7)代入(1)中可知,

smo优化,smo优化算法

这个过程和之前对偶过程一样。

重新整理我们要求的问题为:

smo优化,smo优化算法

与之对应的KKT条件为:

smo优化,smo优化算法

这个KKT条件说明,在两条间隔线外面的点,对应前面的系数

smo优化,smo优化算法

为0,在两条间隔线里面的对应

smo优化,smo优化算法

为C,在两条间隔线上的对应的系数

smo优化,smo优化算法

在0和C之间。

将我们之前得到L和H重新拿过来:

smo优化,smo优化算法

smo优化,smo优化算法

之前我们将问题进行到这里,然后说将

smo优化,smo优化算法

smo优化,smo优化算法

表示后代入W中,这里将代入

smo优化,smo优化算法

中,得

smo优化,smo优化算法

其中

smo优化,smo优化算法

这里的

smo优化,smo优化算法

smo优化,smo优化算法

代表某次迭代前的原始值,因此是常数,而

smo优化,smo优化算法

smo优化,smo优化算法

是变量,待求。公式(24)中的最后一项是常数。

由于

smo优化,smo优化算法

smo优化,smo优化算法

满足以下公式

smo优化,smo优化算法

因为

smo优化,smo优化算法

的值是固定值,在迭代前后不会变。

那么用s表示

smo优化,smo优化算法

,上式两边乘以

smo优化,smo优化算法

时,变为:

smo优化,smo优化算法

其中

smo优化,smo优化算法

代入(24)中,得

smo优化,smo优化算法

这时候只有

smo优化,smo优化算法

是变量了,求导

smo优化,smo优化算法

如果

smo优化,smo优化算法

的二阶导数大于0(凹函数),那么一阶导数为0时,就是极小值了。

假设其二阶导数为0(一般成立),那么上式化简为:

smo优化,smo优化算法

将w和v代入后,继续化简推导,得(推导了六七行推出来了)

smo优化,smo优化算法

我们使用

smo优化,smo优化算法

来表示:

smo优化,smo优化算法

通常情况下目标函数是正定的,也就是说,能够在直线约束方向上求得最小值,并且

smo优化,smo优化算法

那么我们在(30)两边都除以

smo优化,smo优化算法

可以得到

smo优化,smo优化算法

这里我们使用

smo优化,smo优化算法

表示优化后的值,

smo优化,smo优化算法

是迭代前的值,

smo优化,smo优化算法

与之前提到的一样

smo优化,smo优化算法

不是最终迭代后的值,需要进行约束:

smo优化,smo优化算法

那么

smo优化,smo优化算法

在特殊情况下,

smo优化,smo优化算法

可能不为正,如果核函数K不满足Mercer定理,那么目标函数可能变得非正定,

smo优化,smo优化算法

可能出现负值。即使K是有效的核函数,如果训练样本中出现相同的特征x,那么

smo优化,smo优化算法

仍有可能为0。SMO算法在

smo优化,smo优化算法

不为正值的情况下仍有效。为保证有效性,我们可以推导出

smo优化,smo优化算法

就是

smo优化,smo优化算法

的二阶导数,

smo优化,smo优化算法

smo优化,smo优化算法

没有极小值,最小值在边缘处取到(类比

smo优化,smo优化算法

),

smo优化,smo优化算法

时更是单调函数了,最小值也在边缘处取得,而

smo优化,smo优化算法

的边缘就是L和H。这样将

smo优化,smo优化算法

smo优化,smo优化算法

分别代入

smo优化,smo优化算法

中即可求得

smo优化,smo优化算法

的最小值,相应的

smo优化,smo优化算法

还是

smo优化,smo优化算法

也可以知道了。具体计算公式如下:

smo优化,smo优化算法

至此,迭代关系式出了b的推导式以外,都已经推出。

b每一步都要更新,因为前面的KKT条件指出了

smo优化,smo优化算法

smo优化,smo优化算法

的关系,而

smo优化,smo优化算法

和b有关,在每一步计算出

smo优化,smo优化算法

后,根据KKT条件来调整b。

b的更新有几种情况:

smo优化,smo优化算法

来自罗林开的ppt

这里的界内指

smo优化,smo优化算法

,界上就是等于0或者C了。

前面两个的公式推导可以根据

smo优化,smo优化算法

和对于

smo优化,smo优化算法

smo优化,smo优化算法

的KKT条件推出。

这样全部参数的更新公式都已经介绍完毕,附加一点,如果使用的是线性核函数,我们就可以继续使用w了,这样不用扫描整个样本库来作内积了。

w值的更新方法为:

smo优化,smo优化算法

根据前面的

smo优化,smo优化算法

公式推导出。

12 SMO中拉格朗日乘子的启发式选择方法

终于到了最后一个问题了,所谓的启发式选择方法主要思想是每次选择拉格朗日乘子的时候,优先选择样本前面系数

smo优化,smo优化算法

smo优化,smo优化算法

作优化(论文中称为无界样例),因为在界上(

smo优化,smo优化算法

为0或C)的样例对应的系数

smo优化,smo优化算法

一般不会更改。

这条启发式搜索方法是选择第一个拉格朗日乘子用的,比如前面的

smo优化,smo优化算法

。那么这样选择的话,是否最后会收敛。可幸的是Osuna定理告诉我们只要选择出来的两个

smo优化,smo优化算法

中有一个违背了KKT条件,那么目标函数在一步迭代后值会减小。违背KKT条件不代表

smo优化,smo优化算法

,在界上也有可能会违背。是的,因此在给定初始值

smo优化,smo优化算法

=0后,先对所有样例进行循环,循环中碰到违背KKT条件的(不管界上还是界内)都进行迭代更新。等这轮过后,如果没有收敛,第二轮就只针对

smo优化,smo优化算法

的样例进行迭代更新。

在第一个乘子选择后,第二个乘子也使用启发式方法选择,第二个乘子的迭代步长大致正比于

smo优化,smo优化算法

,选择第二个乘子能够最大化

smo优化,smo优化算法

。即当

smo优化,smo优化算法

为正时选择负的绝对值最大的

smo优化,smo优化算法

,反之,选择正值最大的

smo优化,smo优化算法

最后的收敛条件是在界内(

smo优化,smo优化算法

)的样例都能够遵循KKT条件,且其对应的

smo优化,smo优化算法

只在极小的范围内变动。

至于如何写具体的程序,请参考John C. Platt在论文中给出的伪代码。

13 总结

这份SVM的讲义重点概括了SVM的基本概念和基本推导,中规中矩却又让人醍醐灌顶。起初让我最头疼的是拉格朗日对偶和SMO,后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w,使得优化函数变为拉格朗日乘子的单一参数优化问题。而SMO里面迭代公式的推导也着实让我花费了不少时间。

对比这么复杂的推导过程,SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点(中间加了一层sigmoid函数变换),而是就在样本中去找分隔线,为了评判哪条分界线更好,引入了几何间隔最大化的目标。

之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中,发现了w可以由特征向量内积来表示,进而发现了核函数,仅需要调整核函数就可以将特征进行低维到高维的变换,在低维上进行计算,实质结果表现在高维上。由于并不是所有的样本都可分,为了保证SVM的通用性,进行了软间隔的处理,导致的结果就是将优化问题变得更加复杂,然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题,也被拉格朗日对偶和SMO算法化解,使SVM趋向于完美。

另外,其他很多议题如SVM背后的学习理论、参数选择问题、二值分类到多值分类等等还没有涉及到,以后有时间再学吧。其实朴素贝叶斯在分类二值分类问题时,如果使用对数比,那么也算作线性分类器。

本文标题:smo优化,smo优化算法
http://www.jianglexinxi.cn/yanergaozhi/411011.html

0

精彩评论

暂无评论...
验证码 换一张
取 消