通过上图可以得到α1、α2上下界,显然当y1≠y2时:
下界:
上界:
而当y1=y2时:
下界:
上界:
有了上下界后,即可对新值做剪裁,具体规则为:
剪裁本质就是修改步长系数的过程,将剪裁后的α2新值代入公式(10.1)后获得α1新值。得到α1、α2后按照坐标上升法依次得到其他参数值,然后迭代多轮重复计算,可得到全体α值,同时根据公式(7.1),可得参数ω值。
最后看下如何更新参数b的值,根据条件C-αi-μi=0,αi的新值经剪裁后恒有约束0≤αi≤C,接下来根据αi值的范围分别讨论。优化问题(8.1)有最优解时应满足KKT条件,即有下面等式存在:
(11)情形一、当αi=0时,可得μi>0,ξi=0,此时有
,代表超平面可正确分类样本点xi,样本点xi在支持向量的两侧,大多数样本都是这种情形。情形二、当0<αi<C时,可得μi>0,ξi=0,根据公式(11)判断出
,样本点xi此时是支持向量。情形三、当αi=C时,此时μi=0,ξi≥0并且有,此时样本点xi大概率是一个异常点数据(是否是异常点还要看ξi值)。
对于情形二,由于αi对应的xi是支持向量,不失一般性,可设有0<α1<C:
对于情形一、情形二时,即α1、α2在边界时,这时两个变量的组合有三种:(0,0),(C,C),(0,C),通过观察α1、α2的线性关系图可以发现,在边界时,其实只有(0,C)这种情况。不妨设α1=0,α2=C,设b的目标值为bgoal,α1=0对应着x1是被正确分类的点,这时有:
而x1强行设为支持向量时,可利用公式(11.1)计算出
,此时有