作者:RayChiu_Labloy
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
目录
背景
坐标上升算法
定义
过程
举个求解的栗子
基于坐标上升的SMO算法
SMO算法步骤
为什么要选两个参数
SVM算法推导过程:
目标函数转为二元函数
目标函数转为一元函数
一轮迭代中第一步求出a1和a2
先不加约束条件求解
加上约束条件对上边求出的结果修剪
取临界情况
SVM过程中的启发式选择变量
背景
启发式选取第一个变量
启发式选取第二个变量
阈值b的更新
背景
前边三篇文章我们说了关于SVM的三种类别以及中间目标函数的推导和求解原理,中间我们说到在求解的后半部分要用到SMO,具体用到的是max部分求α,如硬间隔的:
还有软间隔的:
回顾非线性第一步求得min情况下的w和b后目标函数的状态:
针对上述问题出现了SMO算法,很快便成为最快的二次规划优化算法,特别是在针对线性SVM和数据稀疏时性能更优。
坐标上升算法
定义
坐标上升法(Coordinate Ascent)每次通过更新函数中的一维,通过多次的迭代以达到优化函数的目的。
过程
假设需要求解的优化问题的具体形式如下:
其中W是向量的函数,更新过程为每次固定除αiαi以外的参数,求得满足条件的αiαi,直到算法收敛,具体的算法过程如下所示:
举个求解的栗子
现在我们来优化它:
我们的思路还是要通过多次迭代来获取最优解,每一次迭代我们这样做,先固定x2,更新x1:
对x1求完导,令其等于0求极值则得到 x1 = x2 。然后固定x1更新x2
同样求极值得到 x2 = x1 / 3 ,然后迭代直到收敛,过程如图
C++代码:
#include <iostream>using namespace std;#define f(x1,x2) (-x1*x1-3*x2*x2+2*x1*x2+6)int main(){double x1 = 1;double x2 = 1;double f0 = f(x1, x2);double err = 1.0e-10;while (true){x1 = x2;x2 = x1 / 3;double ft = f(x1, x2);if (abs(ft - f0) < err){break;}f0 = ft;}cout << "@author:raychiu email:raychiu0202@" << endl;cout << "\nmax{f(x1,x2)}=" << f(x1, x2) << endl;cout << "取得最大值时的坐标:\n(x1,x2)=(" << x1 << "," << x2 << ")" << endl;return 0;}
结果:
基于坐标上升的SMO算法
SMO算法步骤
背景中我们提到求解出w和b后反带回目标函数得到的式子中有多个α待求解,C由我们预先设定的是已知数,其他参数均为已知。
要解决的是在多个参数上求最大值W的问题,至于和都是已知数。C由我们预先设定,也是已知数。
SMO的方法思路就是把原始求解N个α参数二次规划问题分解成很多个子二次规划问题分别求解,每个子问题只需要求解2个参数,求解2个参数的方法类似于坐标上升,节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化,不断循环,直到达到函数最优值。
SMO主要步骤:
意思是说,SMO算法主要分为以下两步:
(1) 选择接下来要更新的一对 αi 和 αj:采用启发式的方法进行选择,以使目标函数最大程度地接近其全局最优值
(2) 将目标函数对 αi 和 αj 进行优化,保持其它所有的 αk (k<> i, j ) 不变
为什么要选两个参数
本来可以按照坐标上升的思路,我们先固定a1之外的N-1个参数,可以转化为类似求a1的一元函数在a1上求极值,但是由于目标函数中还有约束条件,a1也被固定了(可以由其他值推出),因此SMO选择固定N-2个参数,同时优化求解两个参数。
SVM算法推导过程:
目标函数转为二元函数
假设我们选择求解两个变量a1 a2, 固定其他N-2个变量,即视为已知常量,那么目标函数将会转化为关于a1、a2的二元函数:
其中
目标函数转为一元函数
由于a3到an视为已知常量,根据等式约束得
ζ可见为一个定值。
然后带回关于a1、a2的二元函数,最终转换成关于a2的一元函数
一轮迭代中第一步求出a1和a2
先不加约束条件求解
然后求导并等于0求极值:
此时可以求出a2的解,然后由可求得a1。
假设两个乘子a1和a1在更新之前分别是、,更新之后分别是、,又因为a3到an还是固定的,那么
前边我们目标函数求解第一步求得了,带入超平面f(x)=中得:
f(xi) 表示样本 xi的预测值, yi表示样本 xi的真实值,定义 Ei表示预测值与真实值之差为
再根据约束条件可得:
把上述v1、v2结果和上边推出的这个结果,也就是把(4)(6)(7)带入到关于a2的一元函数中得:
注:因为此时求解出的未考虑约束问题,先记为
记,将上式整理入Ei预测值与真实值之差式子中得:
加上约束条件对上边求出的结果修剪
上边我们说到求解未考虑约束问题,什么约束呢,就是
为了确定最终的取值范围。假设它的上下边界分别为H和L,那么有:
当y1!=y2时,即两者异号时, 即一个为+1,另一个为-1,为一条斜率是1的直线:
根据可得,所以有
和,如上图所示。
当y1=y2时,是斜率为-1的直线:
同样根据可得,所以有和,如上图所示
如此,根据y1和y2异号或同号,可得出的上下界分别为:
经过这一番修剪,最优解就可以记为了:
求解:由于其他N-2个变量固定,因此所以可得:
取临界情况
大部分情况下,有。但是在如下两种情况下,需要取临界值L或者H 。
η<0,当核函数K不满足Mercer定理时,矩阵K非正定;η=0,样本x1与x2输入特征相同;
也可以如下理解,对(3)式求二阶导数就是
当η<0时,目标函数为凸函数,没有极小值,极值在定义域边界处取得。
当η=0时,目标函数为单调函数,同样在边界处取极值。
计算方法:
即当=L和=H时,分别带入(9)式中,计算出=L1和=H1,其中s=y1y2
带入目标函数(1)内,比较Ψ(α1=L1,α2=L)与Ψ(α1=H1,α2=H)的大小,α2取较小的函数值对应的边界点。
其中
SVM过程中的启发式选择变量
背景
我们在上边分析了从N个变量中已经选出两个变量进行优化的方法,那么我们说到SMO算法两步中第一步时启发式的选取两个变量,并不是随便随机选取的,这关系到是否可以更快的进行迭代优化。下面分析如何高效地选择两个变量进行优化,使得目标函数下降的最快。
启发式选取第一个变量
第一个变量的选择称为外循环,首先遍历整个样本集,选择违反KKT条件的αi作为第一个变量,接着依据相关规则选择第二个变量(见下面分析),对这两个变量采用上述方法进行优化。当遍历完整个样本集后,然后遍历非边界样本集(0<αi<C)中违反KKT的αi作为第一个变量,同样依据相关规则选择第二个变量,对此两个变量进行优化。当遍历完非边界样本集后,再次回到遍历整个样本集中寻找,即在整个样本集与非边界样本集上来回切换,寻找违反KKT条件的αi作为第一个变量。直到遍历整个样本集后,没有违反KKT条件αi,然后退出。
边界上的样本对应的αi=0或者αi=C,在优化过程中很难变化,然而非边界样本0<αi<C会随着对其他变量的优化会有大的变化,所以优先选择样本前面系数(0<αi<C)的αi作优化(论文中称为无界样例)
选取第一个变量这种启发式的选取是否最后会收敛。可幸的是Osuna定理告诉我们只要选择出来的两个αi中有一个违背了KKT条件,那么目标函数在一步迭代后值会减小。违背KKT条件不代表0<αi<C,在界上也有可能会违背。是的,因此在给定初始值αi=0后,先对所有样例进行循环,循环中碰到违背KKT条件的(不管界上还是界内)都进行迭代更新。等这轮过后,如果没有收敛,第二轮就只针对0<αi<C的样例进行迭代更新。
怎样才算是违反KKT条件呢?
1)如果αi<C,却有yif(xi)<1,本来它应该等于1的。
2)如果αi>0,却有yif(xi)>1,本来它应该等于1的。
启发式选取第二个变量
SMO称第二个变量的选择过程为内循环,假设在外循环中找个第一个变量记为α1,第二个变量的选择希望能使α2有较大的变化,由于α2是依赖于|E1−E2|,当E1为正时,那么选择最小的Ei作为E2,如果E1为负,选择最大Ei作为E2,通常为每个样本的Ei保存在一个列表中,选择最大的|E1−E2|来近似最大化步长。(注:Ei就是上边(5)式说到的预测值与真实值之差)
阈值b的更新
每完成对两个变量的优化后,要对b的值进行更新,因为b的值关系到f(x)的计算,前面的KKT条件指出了αi和的关系,肯定和b有关,最后会关系到下次优化时Ei的计算。所以在每一步计算出αi后,根据KKT条件来调整b。
1.如果,由KKT条件,得到,由此得:
由(5)式得,上式前两项可以替换为:
得出:
2.如果,则
3.如果同时满足,则
4.如果同时不满足则和 以及它们之间的数都满足KKT阈值条件,这时选择它们的中点。
参考:优化算法——坐标上升法_null的专栏-CSDN博客_坐标上升法
机器学习——svm支持向量机的原理 -
支持向量机通俗导论(理解SVM的三层境界)_结构之法 算法之道-CSDN博客_支持向量机通俗导论(理解svm的三层境界)
SVM学习总结_MyArrow的专栏-CSDN博客
【机器学习详解】SMO算法剖析_勿在浮砂筑高台-CSDN博客
支持向量机(五)SMO算法 - JerryLead - 博客园
【如果对您有帮助,交个朋友给个一键三连吧,您的肯定是我博客高质量维护的动力!!!】