平潭城乡住房建设厅网站,专注网站建设与优化,网页设计与网站架设,云南省工程建设交易系统网站SMO算法思想
上面这个优化式子比较复杂#xff0c;里面有m个变量组成的向量α#x1d6fc;需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量#xff0c;将其他的变量都视为常数。由于 ∑ i 1 m α i y i 0 \su…SMO算法思想
上面这个优化式子比较复杂里面有m个变量组成的向量α需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量将其他的变量都视为常数。由于 ∑ i 1 m α i y i 0 \sum\limits_{i1}^{m}\alpha_iy_i 0 i1∑mαiyi0.假如将 α 3 , α 4 , . . . , α m \alpha_3, \alpha_4, ..., \alpha_m α3,α4,...,αm 固定那么 α 1 , α 2 \alpha_1, \alpha_2 α1,α2之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。
为什么是变量化两个不是变量化一个?
因为要是变量化一个,剩余N-1个确定,相当于没有变量化,确定了N-1个另一个也确定了,所以需要两个 把软间隔当例子来求这个问题 m i n ⏟ α 1 2 ∑ i 1 , j 1 m α i α j y i y j K ( x i , x j ) − ∑ i 1 m α i \underbrace{ min }_{\alpha} \frac{1}{2}\sum\limits_{i1,j1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum\limits_{i1}^{m}\alpha_i α min21i1,j1∑mαiαjyiyjK(xi,xj)−i1∑mαi s . t . ∑ i 1 m α i y i 0 s.t. \; \sum\limits_{i1}^{m}\alpha_iy_i 0 s.t.i1∑mαiyi0 0 ≤ α i ≤ C 0 \leq \alpha_i \leq C 0≤αi≤C
满足KKT对偶的互补条件为: α i ∗ ( y i ( w T x i b ) − 1 ξ i ∗ ) 0 \alpha_{i}^{*}(y_i(w^Tx_i b) - 1 \xi_i^{*}) 0 αi∗(yi(wTxib)−1ξi∗)0
原始式子为 m a x γ y ( w T x b ) ∣ ∣ w ∣ ∣ 2 s . t y i ( w T x i b ) γ ′ ( i ) ≥ γ ′ ( i 1 , 2 , . . . m ) max \;\; \gamma \frac{y(w^Tx b)}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i b) \gamma^{(i)} \geq \gamma^{} (i 1,2,...m) maxγ∣∣w∣∣2y(wTxb)s.tyi(wTxib)γ′(i)≥γ′(i1,2,...m)
求max所以为g(X)C.看KKT条件那篇文章
变形式子为 m i n 1 2 ∣ ∣ w ∣ ∣ 2 2 C ∑ i 1 m ξ i min\;\; \frac{1}{2}||w||_2^2 C\sum\limits_{i1}^{m}\xi_i min21∣∣w∣∣22Ci1∑mξi s . t . y i ( w T x i b ) ≥ 1 − ξ i ( i 1 , 2 , . . . m ) s.t. \;\; y_i(w^Tx_i b) \geq 1 - \xi_i \;\;(i 1,2,...m) s.t.yi(wTxib)≥1−ξi(i1,2,...m) ξ i ≥ 0 ( i 1 , 2 , . . . m ) \xi_i \geq 0 \;\;(i 1,2,...m) ξi≥0(i1,2,...m)
我们有 α i ∗ 0 ⇒ y i ( w ∗ ∙ ϕ ( x i ) b ) ≥ 1 \alpha_{i}^{*} 0 \Rightarrow y_i(w^{*} \bullet \phi(x_i) b) \geq 1 αi∗0⇒yi(w∗∙ϕ(xi)b)≥1
代表条件1满足,条件2不满足或者变成线性,其他点间隔大于1(这个1的来历看SVM支持向量机那篇文章) 0 α i ∗ C ⇒ y i ( w ∗ ∙ ϕ ( x i ) b ) 1 0 \alpha_{i}^{*} C \Rightarrow y_i(w^{*} \bullet \phi(x_i) b) 1 0αi∗C⇒yi(w∗∙ϕ(xi)b)1
两个拉格朗日乘子的条件都成立(变等式条件),设置的乘子都0, s . t . y i ( w T x i b ) 1 ( i 1 , 2 , . . . m ) s.t. \;\; y_i(w^Tx_i b) 1 \;\;(i 1,2,...m) s.t.yi(wTxib)1(i1,2,...m), ξ i 0 ( i 1 , 2 , . . . m ) \; \; \xi_i 0 \;\;(i 1,2,...m) ξi0(i1,2,...m) α i ∗ C ⇒ y i ( w ∗ ∙ ϕ ( x i ) b ) ≤ 1 \alpha_{i}^{*} C \Rightarrow y_i(w^{*} \bullet \phi(x_i) b) \leq 1 αi∗C⇒yi(w∗∙ϕ(xi)b)≤1
相当于条件1不满足或者变成线性,条件2满足(所以为0)
由于 w ∗ ∑ j 1 m α j ∗ y j ϕ ( x j ) w^{*} \sum\limits_{j1}^{m}\alpha_j^{*}y_j\phi(x_j) w∗j1∑mαj∗yjϕ(xj),我们令 g ( x ) w ∗ ∙ ϕ ( x ) b ∑ j 1 m α j ∗ y j K ( x , x j ) b ∗ g(x) w^{*} \bullet \phi(x) b \sum\limits_{j1}^{m}\alpha_j^{*}y_jK(x, x_j) b^{*} g(x)w∗∙ϕ(x)bj1∑mαj∗yjK(x,xj)b∗,则有: α i ∗ 0 ⇒ y i g ( x i ) ≥ 1 \alpha_{i}^{*} 0 \Rightarrow y_ig(x_i) \geq 1 αi∗0⇒yig(xi)≥1 0 α i ∗ C ⇒ y i g ( x i ) 1 0 \alpha_{i}^{*} C \Rightarrow y_ig(x_i) 1 0αi∗C⇒yig(xi)1 α i ∗ C ⇒ y i g ( x i ) ≤ 1 \alpha_{i}^{*} C \Rightarrow y_ig(x_i) \leq 1 αi∗C⇒yig(xi)≤1
为了后面表示方便我们定义 K i j ϕ ( x i ) ∙ ϕ ( x j ) K_{ij} \phi(x_i) \bullet \phi(x_j) Kijϕ(xi)∙ϕ(xj)
然后搞两个为变量,固定N-2
补充上条件: s . t . α 1 y 1 α 2 y 2 − ∑ i 3 m y i α i ς s.t. \;\;\alpha_1y_1 \alpha_2y_2 -\sum\limits_{i3}^{m}y_i\alpha_i \varsigma s.t.α1y1α2y2−i3∑myiαiς 0 ≤ α i ≤ C i 1 , 2 0 \leq \alpha_i \leq C \;\; i 1,2 0≤αi≤Ci1,2
SMO算法的优化
上图4
为了求解上面含有这两个变量的目标优化问题我们首先分析约束条件所有的 α 1 , α 2 \alpha_1, \alpha_2 α1,α2都要满足约束条件然后在约束条件下求最小。
根据上面的约束条件 α 1 y 1 α 2 y 2 ς 0 ≤ α i ≤ C i 1 , 2 \alpha_1y_1 \alpha_2y_2 \varsigma\;\;0 \leq \alpha_i \leq C \;\; i 1,2 α1y1α2y2ς0≤αi≤Ci1,2又由于y1,y2均只能取值1或者-1, 这样1,2在[0,C]和[0,C]形成的盒子里面并且两者的关系直线的斜率只能为1或者-1也就是说1,2的关系直线平行于[0,C]和[0,C]形成的盒子的对角线如下图所示 由于1,2的关系被限制在盒子里的一条线段上所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是α22的优化问题。由于我们采用的是启发式的迭代法假设我们上一轮迭代得到的解是 α 1 o l d , α 2 o l d \alpha_1^{old}, \alpha_2^{old} α1old,α2old假设沿着约束方向α2未经剪辑的解是 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc.本轮迭代完成后的解为 α 1 n e w , α 2 n e w \alpha_1^{new}, \alpha_2^{new} α1new,α2new
由于 α 2 n e w \alpha_2^{new} α2new必须满足上图中的线段约束。假设L和H分别是上图中 α 2 n e w \alpha_2^{new} α2new所在的线段的边界。那么很显然我们有 L ≤ α 2 n e w ≤ H L \leq \alpha_2^{new} \leq H L≤α2new≤H
而对于L和H我们也有限制条件如果是上面左图中的情况则 L m a x ( 0 , α 2 o l d − α 1 o l d ) H m i n ( C , C α 2 o l d − α 1 o l d ) L max(0, \alpha_2^{old}-\alpha_1^{old}) \;\;\;H min(C, C\alpha_2^{old}-\alpha_1^{old}) Lmax(0,α2old−α1old)Hmin(C,Cα2old−α1old)
如果是上面右图中的情况我们有 L m a x ( 0 , α 2 o l d α 1 o l d − C ) H m i n ( C , α 2 o l d α 1 o l d ) L max(0, \alpha_2^{old}\alpha_1^{old}-C) \;\;\; H min(C, \alpha_2^{old}\alpha_1^{old}) Lmax(0,α2oldα1old−C)Hmin(C,α2oldα1old)
也就是说假如我们通过求导得到的 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc则最终的 α 2 n e w \alpha_2^{new} α2new应该为 α 2 n e w { H α 2 n e w , u n c H α 2 n e w , u n c L ≤ α 2 n e w , u n c ≤ H L α 2 n e w , u n c L \alpha_2^{new} \begin{cases} H { \alpha_2^{new,unc} H}\\ \alpha_2^{new,unc} {L \leq \alpha_2^{new,unc} \leq H}\\ L {\alpha_2^{new,unc} L} \end{cases} α2new⎩ ⎨ ⎧Hα2new,uncLα2new,uncHL≤α2new,unc≤Hα2new,uncL
超过就取边界
求 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc我们采用图三中的方法,对 α 2 \alpha_2 α2求导
我们下面要对图二图三的公式详细展开 g ( x ) w ∗ ∙ ϕ ( x ) b ∑ j 1 m α j ∗ y j K ( x , x j ) b ∗ g(x) w^{*} \bullet \phi(x) b \sum\limits_{j1}^{m}\alpha_j^{*}y_jK(x, x_j) b^{*} g(x)w∗∙ϕ(x)bj1∑mαj∗yjK(x,xj)b∗
我们令 v i ∑ j 3 m y j α j K ( x i , x j ) g ( x i ) − ∑ j 1 2 y j α j K ( x i , x j ) − b v_i \sum\limits_{j3}^{m}y_j\alpha_jK(x_i,x_j) g(x_i) - \sum\limits_{j1}^{2}y_j\alpha_jK(x_i,x_j) -b vij3∑myjαjK(xi,xj)g(xi)−j1∑2yjαjK(xi,xj)−b
这样我们的图二优化目标函数进一步简化为 W ( α 1 , α 2 ) 1 2 K 11 α 1 2 1 2 K 22 α 2 2 y 1 y 2 K 12 α 1 α 2 − ( α 1 α 2 ) y 1 α 1 v 1 y 2 α 2 v 2 W(\alpha_1,\alpha_2) \frac{1}{2}K_{11}\alpha_1^2 \frac{1}{2}K_{22}\alpha_2^2 y_1y_2K_{12}\alpha_1 \alpha_2 -(\alpha_1 \alpha_2) y_1\alpha_1v_1 y_2\alpha_2v_2 W(α1,α2)21K11α1221K22α22y1y2K12α1α2−(α1α2)y1α1v1y2α2v2
由于 α 1 y 1 α 2 y 2 ς \alpha_1y_1 \alpha_2y_2 \varsigma α1y1α2y2ς,并且 y i 2 1 y_i^2 1 yi21,得到 α 1 y 1 ( ς − α 2 y 2 ) \alpha_1 y_1(\varsigma - \alpha_2y_2) α1y1(ς−α2y2)
优化了深度之眼那个式子,没有必要写成除法,加大求偏导难度
代入得: W ( α 2 ) 1 2 K 11 ( ς − α 2 y 2 ) 2 1 2 K 22 α 2 2 y 2 K 12 ( ς − α 2 y 2 ) α 2 − ( ς − α 2 y 2 ) y 1 − α 2 ( ς − α 2 y 2 ) v 1 y 2 α 2 v 2 W(\alpha_2) \frac{1}{2}K_{11}(\varsigma - \alpha_2y_2)^2 \frac{1}{2}K_{22}\alpha_2^2 y_2K_{12}(\varsigma - \alpha_2y_2) \alpha_2 - (\varsigma - \alpha_2y_2)y_1 - \alpha_2 (\varsigma - \alpha_2y_2)v_1 y_2\alpha_2v_2 W(α2)21K11(ς−α2y2)221K22α22y2K12(ς−α2y2)α2−(ς−α2y2)y1−α2(ς−α2y2)v1y2α2v2
开始求 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc ∂ W ∂ α 2 K 11 α 2 K 22 α 2 − 2 K 12 α 2 − K 11 ς y 2 K 12 ς y 2 y 1 y 2 − 1 − v 1 y 2 y 2 v 2 0 \frac{\partial W}{\partial \alpha_2} K_{11}\alpha_2 K_{22}\alpha_2 -2K_{12}\alpha_2 - K_{11}\varsigma y_2 K_{12}\varsigma y_2 y_1y_2 -1 -v_1y_2 y_2v_2 0 ∂α2∂WK11α2K22α2−2K12α2−K11ςy2K12ςy2y1y2−1−v1y2y2v20
整理上式有 ( K 11 K 22 − 2 K 12 ) α 2 y 2 ( y 2 − y 1 ς K 11 − ς K 12 v 1 − v 2 ) (K_{11} K_{22}-2K_{12})\alpha_2 y_2(y_2-y_1 \varsigma K_{11} - \varsigma K_{12} v_1 - v_2) (K11K22−2K12)α2y2(y2−y1ςK11−ςK12v1−v2) y 2 ( y 2 − y 1 ς K 11 − ς K 12 ( g ( x 1 ) − ∑ j 1 2 y j α j K 1 j − b ) − ( g ( x 2 ) − ∑ j 1 2 y j α j K 2 j − b ) ) y_2(y_2-y_1 \varsigma K_{11} - \varsigma K_{12} (g(x_1) - \sum\limits_{j1}^{2}y_j\alpha_jK_{1j} -b ) -(g(x_2) - \sum\limits_{j1}^{2}y_j\alpha_jK_{2j} -b)) y2(y2−y1ςK11−ςK12(g(x1)−j1∑2yjαjK1j−b)−(g(x2)−j1∑2yjαjK2j−b))
将 ς α 1 y 1 α 2 y 2 \varsigma \alpha_1y_1 \alpha_2y_2 ςα1y1α2y2带入上式我们有 ( K 11 K 22 − 2 K 12 ) α 2 n e w , u n c y 2 ( ( K 11 K 22 − 2 K 12 ) α 2 o l d y 2 y 2 − y 1 g ( x 1 ) − g ( x 2 ) ) (K_{11} K_{22}-2K_{12})\alpha_2^{new,unc} y_2((K_{11} K_{22}-2K_{12})\alpha_2^{old}y_2 y_2-y_1 g(x_1) - g(x_2)) (K11K22−2K12)α2new,uncy2((K11K22−2K12)α2oldy2y2−y1g(x1)−g(x2)) ( K 11 K 22 − 2 K 12 ) α 2 o l d y 2 ( E 1 − E 2 ) \;\;\;\; (K_{11} K_{22}-2K_{12}) \alpha_2^{old} y_2(E_1-E_2) (K11K22−2K12)α2oldy2(E1−E2)
得到: α 2 n e w , u n c α 2 o l d y 2 ( E 1 − E 2 ) K 11 K 22 − 2 K 12 ) \alpha_2^{new,unc} \alpha_2^{old} \frac{y_2(E_1-E_2)}{K_{11} K_{22}-2K_{12})} α2new,uncα2oldK11K22−2K12)y2(E1−E2)
利用公式 α 2 n e w { H α 2 n e w , u n c H α 2 n e w , u n c L ≤ α 2 n e w , u n c ≤ H L α 2 n e w , u n c L \alpha_2^{new} \begin{cases} H { \alpha_2^{new,unc} H}\\ \alpha_2^{new,unc} {L \leq \alpha_2^{new,unc} \leq H}\\ L {\alpha_2^{new,unc} L} \end{cases} α2new⎩ ⎨ ⎧Hα2new,uncLα2new,uncHL≤α2new,unc≤Hα2new,uncL
我们就可以得到我们新的 α 2 n e w \alpha_2^{new} α2new了。利用 α 2 n e w \alpha_2^{new} α2new和 α 1 n e w \alpha_1^{new} α1new的线性关系我们也可以得到新的 α 1 n e w \alpha_1^{new} α1new。
SMO两个变量的选择 反正不是顺序选,要挑着选
选第一个变量
SMO算法称选择第一个变量为外层循环这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点要满足的KKT条件我们在第一节已经讲到了 α i ∗ 0 ⇒ y i g ( x i ) ≥ 1 \alpha_{i}^{*} 0 \Rightarrow y_ig(x_i) \geq 1 αi∗0⇒yig(xi)≥1 0 α i ∗ C ⇒ y i g ( x i ) 1 0 \alpha_{i}^{*} C \Rightarrow y_ig(x_i) 1 0αi∗C⇒yig(xi)1 α i ∗ C ⇒ y i g ( x i ) ≤ 1 \alpha_{i}^{*} C \Rightarrow y_ig(x_i) \leq 1 αi∗C⇒yig(xi)≤1
一般来说我们首先选择违反 0 α i ∗ C ⇒ y i g ( x i ) 1 0 \alpha_{i}^{*} C \Rightarrow y_ig(x_i) 1 0αi∗C⇒yig(xi)1个条件的点。如果这些支持向量都满足KKT条件再选择违反 α i ∗ 0 ⇒ y i g ( x i ) ≥ 1 \alpha_{i}^{*} 0 \Rightarrow y_ig(x_i) \geq 1 αi∗0⇒yig(xi)≥1和 α i ∗ C ⇒ y i g ( x i ) ≤ 1 \alpha_{i}^{*} C \Rightarrow y_ig(x_i) \leq 1 αi∗C⇒yig(xi)≤1的点
选第二个变量
SMO算法称选择第二个变量为内层循环
我们定义 E i g ( x i ) − y i ∑ j 1 m α j ∗ y j K ( x i , x j ) b − y i E_i g(x_i)-y_i \sum\limits_{j1}^{m}\alpha_j^{*}y_jK(x_i, x_j) b - y_i Eig(xi)−yij1∑mαj∗yjK(xi,xj)b−yi
假设我们在外层循环已经找到了α11, 第二个变量2的选择标准是让 ∣ E 1 − E 2 ∣ |E1-E2| ∣E1−E2∣有足够大的变化。由于1定了的时候,1也确定了所以要想 ∣ E 1 − E 2 ∣ |E1-E2| ∣E1−E2∣最大只需要在1为正时选择最小的作为2 在1为负时选择最大的作为2可以将所有的保存下来加快迭代。
如果内存循环找到的点不能让目标函数有足够的下降 可以采用遍历支持向量点来做2,直到目标函数有足够的下降 如果所有的支持向量做2都不能让目标函数有足够的下降可以跳出循环重新选择1
计算阈值b和差值 E i E_i Ei
在每次完成两个变量的优化之后需要重新计算阈值b。当 0 α 1 n e w C 0 \alpha_{1}^{new} C 0α1newC时我们有 y 1 − ∑ i 1 m α i y i K i 1 − b 1 0 y_1 - \sum\limits_{i1}^{m}\alpha_iy_iK_{i1} -b_1 0 y1−i1∑mαiyiKi1−b10
于是新的 b 1 n e w b_1^{new} b1new为: b 1 n e w y 1 − ∑ i 3 m α i y i K i 1 − α 1 n e w y 1 K 11 − α 2 n e w y 2 K 21 b_1^{new} y_1 - \sum\limits_{i3}^{m}\alpha_iy_iK_{i1} - \alpha_{1}^{new}y_1K_{11} - \alpha_{2}^{new}y_2K_{21} b1newy1−i3∑mαiyiKi1−α1newy1K11−α2newy2K21
计算出1为 E 1 g ( x 1 ) − y 1 ∑ i 3 m α i y i K i 1 α 1 o l d y 1 K 11 α 2 o l d y 2 K 21 b o l d − y 1 E_1 g(x_1) - y_1 \sum\limits_{i3}^{m}\alpha_iy_iK_{i1} \alpha_{1}^{old}y_1K_{11} \alpha_{2}^{old}y_2K_{21} b^{old} -y_1 E1g(x1)−y1i3∑mαiyiKi1α1oldy1K11α2oldy2K21bold−y1
可以看到上两式都有 y 1 − ∑ i 3 m α i y i K i 1 y_1 - \sum\limits_{i3}^{m}\alpha_iy_iK_{i1} y1−i3∑mαiyiKi1因此可以将 b 1 n e w b_1^{new} b1new用1表示为 b 1 n e w − E 1 − y 1 K 11 ( α 1 n e w − α 1 o l d ) − y 2 K 21 ( α 2 n e w − α 2 o l d ) b o l d b_1^{new} -E_1 -y_1K_{11}(\alpha_{1}^{new} - \alpha_{1}^{old}) -y_2K_{21}(\alpha_{2}^{new} - \alpha_{2}^{old}) b^{old} b1new−E1−y1K11(α1new−α1old)−y2K21(α2new−α2old)bold
同样的如果 0 α 2 n e w C 0 \alpha_{2}^{new} C 0α2newC, 那么有 b 2 n e w − E 2 − y 1 K 12 ( α 1 n e w − α 1 o l d ) − y 2 K 22 ( α 2 n e w − α 2 o l d ) b o l d b_2^{new} -E_2 -y_1K_{12}(\alpha_{1}^{new} - \alpha_{1}^{old}) -y_2K_{22}(\alpha_{2}^{new} - \alpha_{2}^{old}) b^{old} b2new−E2−y1K12(α1new−α1old)−y2K22(α2new−α2old)bold
最终的 b n e w b^{new} bnew为 b n e w b 1 n e w b 2 n e w 2 b^{new} \frac{b_1^{new} b_2^{new}}{2} bnew2b1newb2new
得到了 b n e w b^{new} bnew我们需要更新 E i E_i Ei: E i ∑ S y j α j K ( x i , x j ) b n e w − y i E_i \sum\limits_{S}y_j\alpha_jK(x_i,x_j) b^{new} -y_i EiS∑yjαjK(xi,xj)bnew−yi
其中S是所有支持向量 x j x_j xj的集合。
SMO算法总结
输入是m个样本 ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) , {(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),} (x1,y1),(x2,y2),...,(xm,ym),其中x为n维特征向量。y为二元输出值为1或者-1.精度e。
输出是近似解α
1)取初值 α 0 0 , k 0 \alpha^{0} 0, k 0 α00,k0
2)按照选第一个变量的方法选择 α 1 k \alpha_1^k α1k,接着按照选第二个变量的方法选择 α 2 k \alpha_2^k α2k,求出新的 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc α 2 n e w , u n c α 2 k y 2 ( E 1 − E 2 ) K 11 K 22 − 2 K 12 ) \alpha_2^{new,unc} \alpha_2^{k} \frac{y_2(E_1-E_2)}{K_{11} K_{22}-2K_{12})} α2new,uncα2kK11K22−2K12)y2(E1−E2)
3)按照下式求出 α 2 k 1 \alpha_2^{k1} α2k1 α 2 k 1 { H α 2 n e w , u n c H α 2 n e w , u n c L ≤ α 2 n e w , u n c ≤ H L α 2 n e w , u n c L \alpha_2^{k1} \begin{cases} H { \alpha_2^{new,unc} H}\\ \alpha_2^{new,unc} {L \leq \alpha_2^{new,unc} \leq H}\\ L {\alpha_2^{new,unc} L} \end{cases} α2k1⎩ ⎨ ⎧Hα2new,uncLα2new,uncHL≤α2new,unc≤Hα2new,uncL
4)利用 α 2 k 1 \alpha_2^{k1} α2k1和 α 1 k 1 \alpha_1^{k1} α1k1的线性关系求出 α 1 k 1 \alpha_1^{k1} α1k1
5)按照4.3节的方法计算 b k 1 b^{k1} bk1和 E i E_i Ei
6在精度e范围内检查是否满足如下的终止条件 ∑ i 1 m α i y i 0 \sum\limits_{i1}^{m}\alpha_iy_i 0 i1∑mαiyi0 0 ≤ α i ≤ C , i 1 , 2... m 0 \leq \alpha_i \leq C, i 1,2...m 0≤αi≤C,i1,2...m α i k 1 0 ⇒ y i g ( x i ) ≥ 1 \alpha_{i}^{k1} 0 \Rightarrow y_ig(x_i) \geq 1 αik10⇒yig(xi)≥1 0 α i k 1 C ⇒ y i g ( x i ) 1 0 \alpha_{i}^{k1} C \Rightarrow y_ig(x_i) 1 0αik1C⇒yig(xi)1 α i k 1 C ⇒ y i g ( x i ) ≤ 1 \alpha_{i}^{k1} C \Rightarrow y_ig(x_i) \leq 1 αik1C⇒yig(xi)≤1
7)如果满足则结束返回 α k 1 \alpha^{k1} αk1,否则转到步骤2。
