通过前几篇博客的介绍，相信大家已经对支持向量机有了一定的了解，我们知道，支持向量机的学习问题可以形式化为求解凸二次规划问题。
min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 0 ⩽ α i ⩽ C , i = 1 , 2 , . . . , N \min_\alpha \quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)- \sum_{i=1}^N\alpha_i \\ s.t. \quad \sum_{i=1}^N\alpha_iy_i =0 \\ 0 \leqslant \alpha_i \leqslant C,\quad i = 1,2,...,N αmin21i=1∑Nj=1∑NαiαjyiyjK(xi,xj)−i=1∑Nαis.t.i=1∑Nαiyi=00⩽αi⩽C,i=1,2,...,N
其中，一个变量 α i \alpha_i αi对应一个样本点 ( x i , y i ) (x_i,y_i) (xi,yi)；
这样的凸二次规划问题具有全局最优解，也有许多最优化算法可以用于求解这一问题，但是当训练数据集容量很大时，这些算法往往变得非常低效。
本篇介绍的 S M O SMO SMO算法（序列最小最优化算法）便是可以快速求解此问题的算法。
S M O SMO SMO算法是由 J o h n P l a t t , 1998 John Platt,1998 JohnPlatt,1998 提出，是一种启发式算法。 S M O SMO SMO算法是将大优化问题分解为多个小优化问题求解的，这些小优化问题往往很容易求解，并且对它们进行顺序求解的结果与将它们作为整体来说求解的结果是一样的。
S M O SMO SMO算法的目标是求出一系列 α \alpha α和 b b b，一旦求出这些 α \alpha α，就很容易计算出权重向量 w w w并且得到分离超平面。
S M O SMO SMO算法的基本思路：
如果所有变量（即拉格朗日乘子 α i \alpha_i αi）的解都满足此最优化问题的 K K T KKT KKT条件，那么这个最优化问题的解就得到了（因为 K K T KKT KKT条件是该最优化问题的充分必要条件）。
此最优化问题的
K
T
T
KTT
KTT条件：
α
i
=
0
⇔
y
i
g
(
x
i
)
⩾
1
0
<
α
i
<
C
⇔
y
i
g
(
x
i
)
=
1
α
i
=
C
⇔
y
i
g
(
x
i
)
⩽
1
\alpha_i = 0 \Leftrightarrow y_ig(x_i) \geqslant 1 \\ 0 < \alpha_i < C \Leftrightarrow y_ig(x_i)=1 \\ \alpha_i = C \Leftrightarrow y_ig(x_i) \leqslant 1
αi=0⇔yig(xi)⩾10<αi<C⇔yig(xi)=1αi=C⇔yig(xi)⩽1
其中：
g
(
x
i
)
=
∑
j
=
1
N
α
j
y
j
K
(
x
i
,
x
j
)
+
b
g(x_i) = \sum_{j=1}^N\alpha_jy_jK(x_i,x_j)+b
g(xi)=j=1∑NαjyjK(xi,xj)+b
那么问题就是：如何使所有变量都满足 K T T KTT KTT条件呢？
先固定 α i \alpha_i αi之外的所有参数，然后求 α i \alpha_i αi上的极值。由于约束条件 ∑ i = 1 N α i y i = 0 \sum_{i=1}^N\alpha_iy_i =0 ∑i=1Nαiyi=0的存在，若固定其他变量，那么 α i \alpha_i αi可由其他变量导出。
于是， S M O SMO SMO算法每次循环选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。
小优化问题（子问题）可以通过解析方法求解，这样可以大大提高整个算法的计算速度，子问题有两个变量，一个是违背 K K T KKT KKT条件最严重的那一个，一个是由约束条件自动确定。如此， S M O SMO SMO算法将原始问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
整个 S M O SMO SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。
不失一般性，假设选择的两个变量为
α
1
,
α
2
\alpha_1,\alpha_2
α1,α2，其他变量
α
i
(
i
=
3
,
4
,
.
.
.
,
N
)
\alpha_i(i=3,4,...,N)
αi(i=3,4,...,N)是固定的，于是上面的最优化问题的子问题就可以写为：
min
α
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
=
ς
0
⩽
α
i
⩽
C
,
i
=
1
,
2
\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_1y_2K_{12}\alpha_1\alpha_2 \\ -(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2} \\ s.t. \quad \alpha_1y_1+\alpha_2y_2 = - \sum_{i=3}^Ny_i\alpha_i = \varsigma \\ 0 \leqslant \alpha_i \leqslant C, \quad i=1,2
α1,α2minW(α1,α2)=21K11α12+21K22α22+y1y2K12α1α2−(α1+α2)+y1α1i=3∑NyiαiKi1+y2α2i=3∑NyiαiKi2s.t.α1y1+α2y2=−i=3∑Nyiαi=ς0⩽αi⩽C,i=1,2
其中， K i j = K ( x i , x j ) , i , j = 1 , 2 , . . . , N K_{ij} = K(x_i,x_j),i,j =1,2,...,N Kij=K(xi,xj),i,j=1,2,...,N， ς \varsigma ς 是常数， y i 2 = 1 y_i^2 = 1 yi2=1，目标函数中省略了不含 α 1 , α 2 \alpha_1,\alpha_2 α1,α2的常数项。
为了求解两个变量的二次规划问题，首先，我们先来分析约束条件，然后在约束条件下求极小。
因为只有两个变量，我们可以在二维空间表示，由约束条件：
0
⩽
α
i
⩽
C
,
i
=
1
,
2
0 \leqslant \alpha_i \leqslant C, \quad i=1,2
0⩽αi⩽C,i=1,2
可画出二维空间图，如下：
由约束条件：
α
1
y
1
+
α
2
y
2
=
−
∑
i
=
3
N
y
i
α
i
=
ς
\alpha_1y_1+\alpha_2y_2 = - \sum_{i=3}^Ny_i\alpha_i = \varsigma
α1y1+α2y2=−i=3∑Nyiαi=ς
可用图中虚线表示，该虚线是平行于对角线的。因此要求的是目标函数在一条平行于对角线的线段（即虚线）上的最优解。
我们可以将两个变量的优化问题变为实质上的单变量的最优化问题，不妨考虑变量为 α 2 \alpha_2 α2的最优化问题。
假设两个变量的初始可行解为 α 1 o l d , α 2 o l d \alpha_1^{old},\alpha_2^{old} α1old,α2old，最优解为 α 1 n e w , α 2 n e w \alpha_1^{new},\alpha_2^{new} α1new,α2new，并且假设在沿着约束方向未经剪辑（即未考虑不等式约束 0 ⩽ α i ⩽ C 0 \leqslant \alpha_i \leqslant C 0⩽αi⩽C）时 α 2 \alpha_2 α2的最优解为 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc
由于 α 2 n e w \alpha_2^{new} α2new满足不等式约束 0 ⩽ α i ⩽ C 0 \leqslant \alpha_i \leqslant C 0⩽αi⩽C，因此最优解 α 2 n e w \alpha_2^{new} α2new的取值范围必须满足条件：
L
⩽
α
2
n
e
w
⩽
H
L \leqslant \alpha_2^{new} \leqslant H
L⩽α2new⩽H
其中，若
y
1
≠
y
2
y_1 \neq y_2
y1̸=y2，如上图中左图，则：
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} )
L=max(0,α2old−α1old)H=min(C,C+α2old−α1old)
若
y
1
=
y
2
y_1 = y_2
y1=y2，如上图中的右图，则：
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} )
L=max(0,α2old+α1old−C)H=min(C,α2old+α1old)
下面我们先求沿着约束方向未经剪辑时 α 2 \alpha_2 α2的最优解 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc；然后再就剪辑后 α 2 \alpha_2 α2的最优解 α 2 n e w \alpha_2^{new} α2new。
再求之前，我们先记：
g
(
x
i
)
=
∑
j
=
1
N
α
j
y
j
K
(
x
i
,
x
j
)
+
b
g(x_i) = \sum_{j=1}^N\alpha_jy_jK(x_i,x_j)+b
g(xi)=j=1∑NαjyjK(xi,xj)+b
令：
E
i
=
g
(
x
i
)
−
y
i
=
(
∑
j
=
1
N
α
j
y
j
K
(
x
i
,
x
j
)
+
b
)
−
y
i
,
i
=
1
,
2
E_i = g(x_i) - y_i = (\sum_{j=1}^N\alpha_jy_jK(x_i,x_j)+b)-y_i, \quad i=1,2
Ei=g(xi)−yi=(j=1∑NαjyjK(xi,xj)+b)−yi,i=1,2
当
i
=
1
,
2
i=1,2
i=1,2时，
E
i
E_i
Ei为函数
g
(
x
)
g(x)
g(x)对输入
x
i
x_i
xi 的预测值与真实输出
y
i
y_i
yi 之差。
定理：
最优化问题沿着约束方向未经剪辑时的解为：
α
2
n
e
w
,
u
n
c
=
α
2
o
l
d
+
y
2
(
E
1
−
E
2
)
η
\alpha_2^{new,unc} = \alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}
α2new,unc=α2old+ηy2(E1−E2)
其中：
η
=
K
11
+
K
22
−
2
K
12
\eta = K_{11}+ K_{22}-2 K_{12}
η=K11+K22−2K12
经剪辑后
α
2
\alpha_2
α2的解是：
α
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, \quad \quad \quad \quad \alpha_2^{new,unc} > H \\ \alpha_2^{new,unc}, \quad \ L \leqslant \alpha_2^{new,unc} \leqslant H \\ L, \quad \quad \quad \quad \alpha_2^{new,unc}<L \end{cases}
α2new=⎩⎪⎨⎪⎧H,α2new,unc>Hα2new,unc, L⩽α2new,unc⩽HL,α2new,unc<L
由
α
2
n
e
w
\alpha_2^{new}
α2new求得
α
1
n
e
w
\alpha_1^{new}
α1new是：
α
1
n
e
w
=
α
1
o
l
d
+
y
1
y
2
(
α
2
o
l
d
−
α
2
n
e
w
)
\alpha_1^{new} = \alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})
α1new=α1old+y1y2(α2old−α2new)
证明：
引进记号：
v
i
=
∑
j
=
3
N
α
j
y
j
K
(
x
i
,
x
j
)
=
g
(
x
i
)
−
∑
j
=
1
2
α
j
y
j
K
(
x
i
,
x
j
)
−
b
,
i
=
1
,
2
v_i = \sum_{j=3}^N\alpha_jy_jK(x_i,x_j) = g(x_i) - \sum_{j=1}^2\alpha_jy_jK(x_i,x_j)-b, \quad i=1,2
vi=j=3∑NαjyjK(xi,xj)=g(xi)−j=1∑2αjyjK(xi,xj)−b,i=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
v
1
α
1
+
y
2
v
2
α
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_1v_1\alpha_1+y_2v_2\alpha_2
W(α1,α2)=21K11α12+21K22α22+y1y2K12α1α2−(α1+α2)+y1v1α1+y2v2α2
由
α
1
y
1
=
ς
−
α
2
y
2
\alpha_1y_1 = \varsigma - \alpha_2y_2
α1y1=ς−α2y2以及
y
i
2
=
1
y_i^2 =1
yi2=1，可将
α
1
\alpha_1
α1表示为：
α
1
=
(
ς
−
y
2
α
2
)
y
1
\alpha_1 = (\varsigma-y_2\alpha_2)y_1
α1=(ς−y2α2)y1
代入改写后的目标函数得：
W
(
α
1
,
α
2
)
=
1
2
K
11
(
ς
−
y
2
α
2
)
2
+
1
2
K
22
α
2
2
+
y
2
K
12
(
ς
−
y
2
α
2
)
α
2
−
(
ς
−
y
2
α
2
)
y
1
−
α
2
+
v
1
(
ς
−
y
2
α
2
)
+
y
2
v
2
α
2
W(\alpha_1,\alpha_2) = \frac{1}{2}K_{11}(\varsigma-y_2\alpha_2)^2+\frac{1}{2}K_{22}\alpha_2^2+y_2K_{12}(\varsigma-y_2\alpha_2)\alpha_2 -(\varsigma-y_2\alpha_2)y_1-\alpha_2+v_1(\varsigma-y_2\alpha_2)+y_2v_2\alpha_2
W(α1,α2)=21K11(ς−y2α2)2+21K22α22+y2K12(ς−y2α2)α2−(ς−y2α2)y1−α2+v1(ς−y2α2)+y2v2α2
对
α
2
\alpha_2
α2求偏导：
∂
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
\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
∂α2∂W=K11α2+K22α2−2K12α2−K11ςy2+K12ςy2+y1y2−1−v1y2+y2v2
另偏导数为0，得到：
(
K
11
+
K
22
−
2
K
12
)
α
2
=
y
2
(
y
2
−
y
1
+
ς
K
11
−
ς
K
12
+
v
1
−
v
2
)
=
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
)
]
(K_{11}+K_{22}-2K_{12})\alpha_2 = y_2(y_2-y_1+\varsigma K_{11}-\varsigma K_{12}+v_1-v_2) \\ = y_2\Big[y_2-y_1+\varsigma K_{11}-\varsigma K_{12}+\Big(g(x_1) - \sum_{j=1}^2y_j\alpha_jK_{1j}-b\Big)-\Big(g(x_2) - \sum_{j=1}^2y_j\alpha_jK_{2j}-b\Big)\Big]
(K11+K22−2K12)α2=y2(y2−y1+ςK11−ςK12+v1−v2)=y2[y2−y1+ςK11−ςK12+(g(x1)−j=1∑2yjαjK1j−b)−(g(x2)−j=1∑2yjαjK2j−b)]
将
ς
=
α
1
o
l
d
y
1
+
α
2
o
l
d
y
2
\varsigma = \alpha_1^{old}y_1+\alpha_2^{old}y_2
ς=α1oldy1+α2oldy2代入，得到：
(
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
−
2
K
12
)
α
2
o
l
d
+
y
2
(
E
1
−
E
2
)
(K_{11}+K_{22}-2K_{12})\alpha_2^{new,unc}=y_2\Big((K_{11}+K_{22}-2K_{12})\alpha_2^{old}y_2+y_2-y_1+g(x_1)-g(x_2)\Big) \\ = (K_{11}+K_{22}-2K_{12})\alpha_2^{old}+y_2(E_1-E_2)
(K11+K22−2K12)α2new,unc=y2((K11+K22−2K12)α2oldy2+y2−y1+g(x1)−g(x2))=(K11+K22−2K12)α2old+y2(E1−E2)
将
η
=
K
11
+
K
22
−
2
K
12
\eta = K_{11}+K_{22}-2K_{12}
η=K11+K22−2K12代入，得到：
α
2
n
e
w
.
u
n
c
=
α
2
o
l
d
+
y
2
(
E
1
−
E
2
)
η
\alpha_2^{new.unc} = \alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}
α2new.unc=α2old+ηy2(E1−E2)
要是其满足不等式约束必须限制在
[
L
,
H
]
[L,H]
[L,H]内，从而得到
α
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, \quad \quad \quad \quad \alpha_2^{new,unc} > H \\ \alpha_2^{new,unc}, \quad \ L \leqslant \alpha_2^{new,unc} \leqslant H \\ L, \quad \quad \quad \quad \alpha_2^{new,unc}<L \end{cases}
α2new=⎩⎪⎨⎪⎧H,α2new,unc>Hα2new,unc, L⩽α2new,unc⩽HL,α2new,unc<L
由等式约束：
α
1
y
1
+
α
2
y
2
=
ς
\alpha_1y_1+\alpha_2y_2 = \varsigma
α1y1+α2y2=ς得到
α
1
n
e
w
\alpha_1^{new}
α1new的表达式：
α
1
n
e
w
=
α
1
o
l
d
+
y
1
y
2
(
α
2
o
l
d
−
α
2
n
e
w
)
\alpha_1^{new} = \alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})
α1new=α1old+y1y2(α2old−α2new)
至此，我们就得到了最优化问题的解：
(
α
1
n
e
w
,
α
2
n
e
w
)
(\alpha_1^{new},\alpha_2^{new})
(α1new,α2new)
S M O SMO SMO称选择第一个变量的过程为外层循环，外层循环在训练样本中选违反 K K T KKT KKT条件最严重的样本点，并将其对应的变量作为第一个变量。具体地，检验训练样本点 ( x i , y i ) (x_i,y_i) (xi,yi)是否满足 K K T KKT KKT条件。
S M O SMO SMO称选择第二个变量的过程为内层循环。假设在外层循环中已经找到第一个变量 α 1 \alpha_1 α1，现在要在内层循环中找第二个变量 α 2 \alpha_2 α2。第二个变量选择的标准是希望能使 α 2 \alpha_2 α2有足够大的变化。有前面的公式可知， α 2 n e w \alpha_2^{new} α2new依赖于 ∣ E 1 − E 2 ∣ |E_1-E_2| ∣E1−E2∣，一种简单的做法就是使其对应的 ∣ E 1 − E 2 ∣ |E_1-E_2| ∣E1−E2∣最大，因为 α 1 \alpha_1 α1已定， E 1 E_1 E1也就确定了。那么，如果 E 1 E_1 E1为正的，那么选择最小的 E i E_i Ei作为 E 2 E_2 E2；如果 E 1 E_1 E1为负的，那么选择最大的 E i E_i Ei作为 E 2 E_2 E2。
一般情况下，采用启发式规则选择第二个变量 α 2 \alpha_2 α2。遍历在间隔边界上的支持向量点，依次将其对应的变量作为 α 2 \alpha_2 α2试用，直到目标函数有足够的下降。若找不到合适的 α 2 \alpha_2 α2，那么遍历整个训练数据集；若找不到合适的 α 2 \alpha_2 α2，则放弃第一个 α 2 \alpha_2 α2，再通过外层循环寻找另一个 α 1 \alpha_1 α1。
在每次完成两个变量的优化后，都要重新计算阀值
b
b
b，当
0
<
α
1
n
e
w
<
C
0 < \alpha_1^{new} < C
0<α1new<C时，由
K
K
T
KKT
KKT条件可知：
∑
i
=
1
N
α
i
y
i
K
i
1
+
b
=
y
1
\sum_{i=1}^N\alpha_iy_iK_{i1} + b = y_1
i=1∑NαiyiKi1+b=y1
于是：
b
1
n
e
w
=
y
1
−
∑
i
=
3
N
α
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_{i=3}^N\alpha_iy_iK_{i1} - \alpha_1^{new}y_1K_{11} - \alpha_2^{new}y_2K_{21}
b1new=y1−i=3∑NαiyiKi1−α1newy1K11−α2newy2K21
由前面我们定义式
E
i
E_i
Ei得：
E
1
=
∑
i
=
3
N
α
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 = \sum_{i=3}^N\alpha_iy_iK_{i1} +\alpha_1^{old}y_1K_{11} + \alpha_2^{old}y_2K_{21} + b^{old}-y_1
E1=i=3∑NαiyiKi1+α1oldy1K11+α2oldy2K21+bold−y1
根据上面式子得：
y
1
−
∑
i
=
3
N
α
i
y
i
K
i
1
=
−
E
1
+
α
1
o
l
d
y
1
K
11
+
α
2
o
l
d
y
2
K
21
+
b
o
l
d
y_1 - \sum_{i=3}^N\alpha_iy_iK_{i1} = -E_1+ \alpha_1^{old}y_1K_{11} + \alpha_2^{old}y_2K_{21} + b^{old}
y1−i=3∑NαiyiKi1=−E1+α1oldy1K11+α2oldy2K21+bold
代入上面
b
1
n
e
w
b_1^{new}
b1new式子得：
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<α2new<C，那么：
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
如果 α 1 n e w , α 2 n e w \alpha_1^{new},\alpha_2^{new} α1new,α2new同时满足 0 < α i n e w < C , i = 1 , 2 0 < \alpha_i^{new} < C, i=1,2 0<αinew<C,i=1,2，那么 b 1 n e w = b 2 n e w b_1^{new} = b_2^{new} b1new=b2new；
如果 α 1 n e w , α 2 n e w \alpha_1^{new},\alpha_2^{new} α1new,α2new 是 0 0 0 或者 C C C，那么 b 1 n e w ， b 2 n e w b_1^{new} ，b_2^{new} b1new，b2new以及他们之前的数都满足 K K T KKT KKT条件的阀值，选择他们的中点作为 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} bnew=2b1new+b2new
在每次计算两个变量的优化之后，还必须更新对应的
E
i
E_i
Ei 值，并保存在列表中。
E
i
E_i
Ei值的更新需要用到
b
n
e
w
b^{new}
bnew值，以及所有支持向量对应的
α
j
\alpha_j
αj：
E
i
n
e
w
=
∑
S
y
j
α
j
K
(
x
i
,
y
j
)
+
b
n
e
w
−
y
i
E_i^{new} = \sum_Sy_j\alpha_jK(x_i,y_j)+b^{new}-y_i
Einew=S∑yjαjK(xi,yj)+bnew−yi
其中，
S
S
S是所有支持向量
x
j
x_j
xj的集合。
输入：训练数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
N
,
y
N
)
}
T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}
T={(x1,y1),(x2,y2),...,(xN,yN)}，其中，
x
i
∈
X
=
R
n
,
y
i
∈
Y
=
{
−
1
,
+
1
}
,
i
=
1
,
2
,
.
.
.
,
N
x_i \in \mathcal{X} = R^n,y_i \in \mathcal{Y} = \{-1,+1\},i =1,2,...,N
xi∈X=Rn,yi∈Y={−1,+1},i=1,2,...,N，精度为$\varepsilon
；
输
出
：
近
似
解
； 输出：近似解
；输出：近似解\alpha$
（1）取初值
α
(
0
)
=
0
\alpha^{(0)} = 0
α(0)=0，令
k
=
0
k=0
k=0；
（2）选取优化变量
α
1
(
k
)
,
α
2
(
k
)
\alpha_1^{(k)},\alpha_2^{(k)}
α1(k),α2(k)，解析求解两个变量的最优化问题，求得最优解
α
1
(
k
+
1
)
,
α
1
(
k
+
1
)
\alpha_1^{(k+1)},\alpha_1^{(k+1)}
α1(k+1),α1(k+1)；
（3）若在进度
ε
\varepsilon
ε范围内满足停止条件：
∑
i
=
1
N
a
i
y
i
=
0
0
⩽
α
i
⩽
C
,
i
=
1
,
2
,
.
.
,
N
y
i
⋅
g
(
x
i
)
=
{
⩾
1
,
{
x
i
∣
α
i
=
0
}
=
1
,
{
x
i
∣
0
<
α
i
<
C
}
⩽
1
,
{
x
i
∣
α
i
=
C
}
\sum_{i=1}^Na_iy_i = 0\\ 0 \leqslant \alpha_i \leqslant C, \quad i = 1,2,..,N \\ y_i \cdot g(x_i) = \begin{cases} \geqslant 1, \quad \{x_i | \alpha_i =0 \} \\ = 1,\quad \{x_i |0 < \alpha_i <C \} \\ \leqslant 1,\quad \{x_i | \alpha_i =C \} \\ \end{cases}
i=1∑Naiyi=00⩽αi⩽C,i=1,2,..,Nyi⋅g(xi)=⎩⎪⎨⎪⎧⩾1,{xi∣αi=0}=1,{xi∣0<αi<C}⩽1,{xi∣αi=C}
其中，
g
(
x
i
)
=
∑
j
=
1
N
α
j
y
j
K
(
x
i
,
x
j
)
+
b
g(x_i) = \sum_{j=1}^N\alpha_jy_jK(x_i,x_j)+b
g(xi)=j=1∑NαjyjK(xi,xj)+b
则转（4）；否则令
k
=
k
+
1
k = k+1
k=k+1，转（2）；
（4）取
α
=
α
(
k
+
1
)
\alpha = \alpha^{(k+1)}
α=α(k+1)。
注：
本篇源自《统计学习方法》李航
由于博主也正在学习，里面肯定会存在一些错误，还望纠正
关于最优化求解，感兴趣的可以通过相关课本学习一下
