上一篇文章(1)我们讨论了硬间隔SVM的推导及其对偶形式，其对偶问题可以化简成以下形式：
m i n α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i ⋅ x j − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 α i ≥ 0 i = 1 , 2 , . . . , N \begin{align*}
min_ \alpha\quad &\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}\cdot x_{j}-\sum_{i=1}^{N}\alpha_{i}\\
s.t.\quad &\sum_{i=1}^{N}\alpha_{i}y_{i}=0\\
&\alpha_{i}\ge 0\\
&i=1,2,...,N
\end{align*} mi n α s . t . 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j x i ⋅ x j − i = 1 ∑ N α i i = 1 ∑ N α i y i = 0 α i ≥ 0 i = 1 , 2 , ... , N 该问题可以看作是一个以α \alpha α
SMO序列优化算法
SMO序列优化算法先将α \alpha α α 1 , α 2 , . . . , α N = 0 ， \alpha_{1},\alpha_{2},...,\alpha_{N}=0， α 1 , α 2 , ... , α N = 0 ， α \alpha α α 1 , α 2 \alpha_{1},\alpha_{2} α 1 , α 2 α i , α j \alpha_{i},\alpha_{j} α i , α j α i \alpha_{i} α i x i x_{i} x i x j x_{j} x j α j \alpha_{j} α j α 3 , α 4 , . . . , α N \alpha_{3},\alpha_{4},...,\alpha_{N} α 3 , α 4 , ... , α N ∑ i = 1 N α i y i = 0 \sum_{i=1}^{N}\alpha_{i}y_{i}=0 ∑ i = 1 N α i y i = 0 α 1 = − y 1 ∑ i = 2 N α i y i \alpha_{1}=-y_{1}\sum_{i=2}^{N}\alpha_{i}y_{i} α 1 = − y 1 ∑ i = 2 N α i y i K i j = x i ⋅ x j K_{ij}=x_{i}\cdot x_{j} K ij = x i ⋅ x j
m i n α 1 , α 2 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 ∑ i = 3 N y i α i K i 1 + y 2 α 2 ∑ i = 3 N y i α i K i 2 s . t . α 1 y 1 + α 2 y 2 = − ∑ i = 3 N y i α i = ζ α 1 , α 2 ≥ 0 \begin{align*}
min_{\alpha_{1},\alpha_{2}}\quad W(\alpha_{1},\alpha_{2})=&\frac{1}{2}K_{11}\alpha_{1}^{2}+\frac{1}{2}K_{22}\alpha_{2}^{2}+y_{1}y_{2}K_{12}\alpha_{1}\alpha_{2}\\
&-(\alpha_{1}+\alpha_{2})+y_{1}\alpha_{1}\sum_{i=3}^{N}y_{i}\alpha_{i}K_{i1}+y_{2}\alpha_{2}\sum_{i=3}^{N}y_{i}\alpha_{i}K_{i2}\\
s.t.\quad &\alpha_{1}y_{1}+\alpha_{2}y_{2}=-\sum_{i=3}^{N}y_{i}\alpha_{i}=\zeta\\
&\alpha_{1},\alpha_{2}\ge0
\end{align*} mi n α 1 , α 2 W ( α 1 , α 2 ) = s . t . 2 1 K 11 α 1 2 + 2 1 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 i = 3 ∑ N y i α i K i 1 + y 2 α 2 i = 3 ∑ N y i α i K i 2 α 1 y 1 + α 2 y 2 = − i = 3 ∑ N y i α i = ζ α 1 , α 2 ≥ 0 在上述二次规划问题中，由于α 1 y 1 + α 2 y 2 = ζ \alpha_{1}y_{1}+\alpha_{2}y_{2}=\zeta α 1 y 1 + α 2 y 2 = ζ α 1 = ( ζ − y 2 α 2 ) y 1 \alpha_{1}=(\zeta-y_{2}\alpha_{2})y_{1} α 1 = ( ζ − y 2 α 2 ) y 1 W ( α 1 , α 2 ) W(\alpha_{1},\alpha_{2}) W ( α 1 , α 2 )
令v i = ∑ j = 3 N α j y j K ( x i , x j ) v_{i}=\sum_{j=3}^{N}\alpha_{j}y_{j}K(x_{i},x_{j}) v i = ∑ j = 3 N α j y j K ( x i , x j ) α 1 = ( ζ − y 2 α 2 ) y 1 \alpha_{1}=(\zeta-y_{2}\alpha_{2})y_{1} α 1 = ( ζ − y 2 α 2 ) y 1 W ( α 1 , α 2 ) W(\alpha_{1},\alpha_{2}) W ( α 1 , α 2 )
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 + v 1 ( ζ − α 2 y 2 ) + y 2 v 2 α 2 W(\alpha_{2})=\frac{1}{2}K_{11}(\zeta-\alpha_{2}y_{2})^{2}+\frac{1}{2}K_{22}\alpha_{2}^{2}+y_{2}K_{12}(\zeta-\alpha_{2}y_{2})\alpha_{2}-(\zeta-\alpha_{2}y_{2})y_{1}-\alpha_{2}+v_{1}(\zeta-\alpha_{2}y_{2})+y_{2}v_{2}\alpha_{2} W ( α 2 ) = 2 1 K 11 ( ζ − α 2 y 2 ) 2 + 2 1 K 22 α 2 2 + y 2 K 12 ( ζ − α 2 y 2 ) α 2 − ( ζ − α 2 y 2 ) y 1 − α 2 + v 1 ( ζ − α 2 y 2 ) + y 2 v 2 α 2 直接令∂ W ∂ α 2 = 0 \frac{\partial W}{\partial\alpha_{2}}=0 ∂ α 2 ∂ W = 0 α 2 \alpha_{2} α 2 α ^ 2 = α 2 + y 2 ( E 1 − E 2 ) η \hat\alpha_{2}=\alpha_{2}+\frac{y_{2}(E_{1}-E_{2})}{\eta} α ^ 2 = α 2 + η y 2 ( E 1 − E 2 ) E i = ∑ j = 1 N α j y j K i j + b − y i E_{i}=\sum_{j=1}^{N}\alpha_{j}y_{j}K_{ij}+b-y_{i} E i = ∑ j = 1 N α j y j K ij + b − y i η = K 11 + K 22 − 2 K 12 \eta=K_{11}+K_{22}-2K_{12} η = K 11 + K 22 − 2 K 12 α ^ 2 \hat\alpha_{2} α ^ 2 α 1 , α 2 ≥ 0 \alpha_{1},\alpha_{2}\ge 0 α 1 , α 2 ≥ 0 α 1 = ( ζ − y 2 α 2 ) y 1 ≥ 0 \alpha_{1}=(\zeta-y_{2}\alpha_{2})y_{1}\ge0 α 1 = ( ζ − y 2 α 2 ) y 1 ≥ 0 α 2 ≥ 0 \alpha_{2}\ge0 α 2 ≥ 0 α 2 \alpha_2 α 2 H H H L L L α 2 \alpha_{2} α 2
α 2 ∗ = { H , α ^ 2 > H α ^ 2 , L ≤ α ^ 2 ≤ H L , α ^ 2 < L \alpha_{2}^{*}=
\begin{cases}
H,\quad \hat\alpha_{2}>H\\
\hat\alpha_{2},\quad L\le\hat\alpha_{2}\le H\\
L,\quad \hat\alpha_{2}<L
\end{cases} α 2 ∗ = ⎩ ⎨ ⎧ H , α ^ 2 > H α ^ 2 , L ≤ α ^ 2 ≤ H L , α ^ 2 < L 另外根据α 1 ∗ = ( ζ − y 2 α 2 ∗ ) y 1 \alpha_{1}^{*}=(\zeta-y_{2}\alpha_{2}^{*})y_{1} α 1 ∗ = ( ζ − y 2 α 2 ∗ ) y 1 α 1 ∗ \alpha_{1}^{*} α 1 ∗ α \alpha α w w w b b b