将原始最优化问题转化成了其对偶问题,因为对偶问题是一个凸二次规划问题,这样的凸二次规划问题具有全局最优解。
其中(xi,yi)(xi,yi)表示训练样本数据,xixi为样本特征,yi∈{−1,1}yi∈{−1,1}为样本标签,C为惩罚系数由自己设定。
前面提到将原始的二次规划问题分解为只含有两个变量的二次规划子问题,所以假设选定两个变量、,其他变量相当于常数,省略常数后,SMO的最优化问题的子问题可以化简成以下形式
(1)式可以看成是一个二元函数,根据于和的约束关系,可以把消去。不过我们的目的是为了关于求导,导数为0的点就是要找的极值点,所以这里既可以把消去后对求导,也可以直接在现在这个式子上对求导。
找到其他博主博客一些很好的参考:
再根据推导:
对约束条件对应的*式,考虑两种情况,分别如上图所示。
需要满足约束条件,所以最优值的取值范围也要满足条件
L和H分别是坐在的对角线段端点的界。
所以在更新时,要先求出的可行域,然后用之前的那个公式求出极值点,然后看极值点处的在不在可行域范围内,在的话就使用极值点处的,不在的话就使用边界值H或者L更新,具体更新规则为:
由于只有两个变量,根据
可以求得