1. 线性SVM模型

线性支持向量机的思想非常朴素：用一个超平面将两类数据分割开来。

如上图，这样的超平面有无数个，选择哪个超平面更好呢？从上图可以看出，平面①会将红色的两个数据分错，平面②则不会，这是因为平面②将两边的间隔分得更大。所以，我们应该选择将两边间隔分割得最大的超平面。

设超平面为 w T x + b = 0 w^Tx+b=0 wTx+b=0,类别标记 y i ∈ [ − 1 , 1 ] y_i\in[-1,1] yi​∈[−1,1]。现将超平面上下平移，直到有数据穿过为止，此时 w T x i + b = 1 或 w T x i + b = − 1 w^Tx_i+b=1或w^Tx_i+b=-1 wTxi​+b=1或wTxi​+b=−1。如下图：

被穿过的数据 x i x_i xi​称为支持向量，而某支持向量到超平面的距离的2倍称为间隔： m a r g i n = 2 ∣ ∣ w ∣ ∣ margin=\cfrac{2}{||w||} margin=∣∣w∣∣2​，要最大化间隔可以最小化 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣。并且,所有数据满足：
{ w T x i + b ≥ + 1 , y i = + 1 w T x i + b ≤ − 1 , y i = − 1 即 ： y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m \begin{aligned} \begin{cases} w^Tx_i+b \geq +1& , y_i=+1 \\ w^Tx_i+b \leq -1 & , y_i=-1 \end{cases} \\ \\ 即：y_i(w^Tx_i+b) \geq 1,i=1,2,...,m \end{aligned} {wTxi​+b≥+1wTxi​+b≤−1​,yi​=+1,yi​=−1​即：yi​(wTxi​+b)≥1,i=1,2,...,m​
上述不等式表达的意思是：所有数据点都要分类正确。

总之，线性SVM模型目标在于求解 w , b w,b w,b，使得数据点均分类正确的情况下，同时间隔要最大化，即：

m i n [ w , b ] 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m \begin{aligned} & min_{[w,b]} \enspace \frac{1}{2}||w||^2 \\ \\ &s.t. \enspace y_i(w^Tx_i+b) \geq 1,i=1,2,...,m \end{aligned} ​min[w,b]​21​∣∣w∣∣2s.t.yi​(wTxi​+b)≥1,i=1,2,...,m​

这就是线性支持向量机的模型。它是一个凸二次规划问题，关于这类问题有很多方法可以求解，有兴趣的可以去学习凸优化理论。然而，伟大的数学家发明出了更高效的方法(对偶问题)来求解。

2. 对偶理论

一般的优化问题如下：

m i n [ x ] g ( x ) s . t . f i ( x ) ≤ 0 , i = 1 , 2 , . . . , m h i ( x ) = 0 , i = 1 , 2 , . . . , q \begin{aligned} &min_{[x]} \enspace g(x) \\ \\ &s.t. \enspace f_i(x)\leq 0,i=1,2,...,m \\ & \qquad h_i(x)= 0,i=1,2,...,q \end{aligned} ​min[x]​g(x)s.t.fi​(x)≤0,i=1,2,...,mhi​(x)=0,i=1,2,...,q​
构造拉格朗日辅助函数: L ( x , α , v ) = g ( x ) + ∑ i = 1 m α i f i ( x ) + ∑ i = 1 q v i h i ( x ) , ( α i ≥ 0 ) L(x,\alpha,v)=g(x)+\sum_{i=1}^m \alpha_if_i(x)+\sum_{i=1}^qv_ih_i(x),(\alpha_i\geq0) L(x,α,v)=g(x)+∑i=1m​αi​fi​(x)+∑i=1q​vi​hi​(x),(αi​≥0)

现在我们对L最大化 α , v \alpha,v α,v得：
m a x [ α , v ] L ( x , α , v ) = g ( x ) + m a x { ∑ i = 1 m α i f i ( x ) + ∑ i = 1 q v i h i ( x ) } \begin{aligned} max_{[\alpha,v]} \enspace L(x,\alpha,v)=g(x)+max\{\sum_{i=1}^m \alpha_if_i(x)+\sum_{i=1}^qv_ih_i(x)\} \end{aligned} max[α,v]​L(x,α,v)=g(x)+max{i=1∑m​αi​fi​(x)+i=1∑q​vi​hi​(x)}​
由于 f i ( x ) ≤ = 0 且 α i ≥ 0 f_i(x)\leq=0且\alpha_i\geq0 fi​(x)≤=0且αi​≥0，则 α i f i ( x ) \alpha_if_i(x) αi​fi​(x)的取值为负无穷到0,得到 m a x ∑ i = 1 m α i f i ( x ) = 0 max\enspace \sum_{i=1}^m \alpha_if_i(x)=0 max∑i=1m​αi​fi​(x)=0；又 h i ( x ) = 0 , 则 m a x ∑ i = 1 q v i h i ( x ) = 0 h_i(x)=0,则max\enspace \sum_{i=1}^qv_ih_i(x)=0 hi​(x)=0,则max∑i=1q​vi​hi​(x)=0。故推导出:
g ( x ) = m a x [ α , v ] L ( x , α , v ) \begin{aligned} g(x)= max_{[\alpha,v]} \enspace L(x,\alpha,v) \end{aligned} g(x)=max[α,v]​L(x,α,v)​
那么原问题可以表达为： p ∗ = m i n [ x ] m a x [ α , v ] L ( x , α , v ) p^*=min_{[x]} max_{[\alpha,v]} \enspace L(x,\alpha,v) p∗=min[x]​max[α,v]​L(x,α,v)

其对偶问题为： d ∗ = m a x [ α , v ] m i n [ x ] L ( x , α , v ) d^*= max_{[\alpha,v]}min_{[x]}\enspace L(x,\alpha,v) d∗=max[α,v]​min[x]​L(x,α,v) (强对偶条件成立时)

观察原问题和对偶问题的表达式，其实就是交换了一下求解次序。这样做的意义在于：直接求解 p ∗ p^* p∗ 是非常困难的。但是交换了次序后，先求解 m i n [ x ] L ( x , α , v ) min_{[x]}\enspace L(x,\alpha,v) min[x]​L(x,α,v)可能非常简单，再求解 m a x [ α , v ] max_{[\alpha,v]} max[α,v]​也可能非常简单。

我们现在看d*是如何推导出来的：

设拉格朗日对偶函数： h ( α , v ) = m i n [ x ] L ( x , α , v ) h(\alpha,v)=min_{[x]}L(x,\alpha,v) h(α,v)=min[x]​L(x,α,v)。再任取 x 0 x_0 x0​是原问题可行的点，即满足 f i ( x 0 ) ≤ 0 , h i ( x 0 ) = 0 f_i(x_0)\leq0,h_i(x_0)=0 fi​(x0​)≤0,hi​(x0​)=0，有：
由 于 α i ≥ 0 , 则 ∑ i = 1 m α i f i ( x 0 ) + ∑ i = 1 q v i h i ( x 0 ) ≤ 0 L ( x 0 , α , v ) = g ( x 0 ) + ∑ i = 1 m α i f i ( x 0 ) + ∑ i = 1 q v i h i ( x 0 ) ≤ g ( x 0 ) h ( α , v ) = m i n [ x ] L ( x , α , v ) ≤ L ( x 0 , α , v ) ≤ g ( x 0 ) \begin{aligned} 由于\alpha_i\geq 0,则\sum_{i=1}^m \alpha_if_i(x_0)+\sum_{i=1}^qv_ih_i(x_0) &\leq 0 \\ L(x_0,\alpha,v)=g(x_0)+\sum_{i=1}^m \alpha_if_i(x_0)+\sum_{i=1}^qv_ih_i(x_0)&\leq g(x_0) \\ h(\alpha,v)=min_{[x]}L(x,\alpha,v)\leq L(x_0,\alpha,v)&\leq g(x_0) \end{aligned} 由于αi​≥0,则i=1∑m​αi​fi​(x0​)+i=1∑q​vi​hi​(x0​)L(x0​,α,v)=g(x0​)+i=1∑m​αi​fi​(x0​)+i=1∑q​vi​hi​(x0​)h(α,v)=min[x]​L(x,α,v)≤L(x0​,α,v)​≤0≤g(x0​)≤g(x0​)​
即， h ( α , v ) h(\alpha,v) h(α,v)恒小于等于 g ( x ) g(x) g(x)，有：
m a x [ α , v ] h ( α , v ) ≤ m i n [ x ] g ( x ) 即 ， d ∗ ≤ p ∗ \begin{aligned} &max_{[\alpha,v]}h(\alpha,v)\leq min_{[x]}g(x) &\\ \\ &即 ，d^*\leq p^* \end{aligned} ​max[α,v]​h(α,v)≤min[x]​g(x)即，d∗≤p∗​

强对偶条件：（1）问题是凸的（2）存在 x x x, f i ( x ) < 0 均 成 立 f_i(x)<0均成立 fi​(x)<0均成立，此时 p ∗ = d ∗ = m a x [ α , v ] m i n [ x ] L ( x , α , v ) p^*=d^*= max_{[\alpha,v]}min_{[x]}\enspace L(x,\alpha,v) p∗=d∗=max[α,v]​min[x]​L(x,α,v)。

另外，凸优化问题的最优解满足KKT条件：
α i ≥ 0 f i ( x ) ≤ 0 h i ( x ) = 0 α i f i ( x ) = 0 ∇ x L ( x , α , v ) = 0 \begin{aligned} \alpha_i &\geq 0 \\ f_i(x) &\leq 0 \\ h_i(x)& = 0 \\ \alpha_i f_i(x)& =0 \\ \nabla_xL(x,\alpha,v)&=0 \end{aligned} αi​fi​(x)hi​(x)αi​fi​(x)∇x​L(x,α,v)​≥0≤0=0=0=0​

3.线性SVM的对偶问题

回顾一下线性SVM的模型为：
m i n [ w , b ] 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m \begin{aligned} & min_{[w,b]} \enspace \frac{1}{2}||w||^2 \\ \\ &s.t. \enspace y_i(w^Tx_i+b) \geq 1,i=1,2,...,m \end{aligned} ​min[w,b]​21​∣∣w∣∣2s.t.yi​(wTxi​+b)≥1,i=1,2,...,m​
我们令 g ( w , b ) = 1 2 ∣ ∣ w ∣ ∣ 2 , f i ( x ) = 1 − y i ( w T x i + b ) g(w,b)=\cfrac{1}{2}||w||^2,f_i(x)=1- y_i(w^Tx_i+b) g(w,b)=21​∣∣w∣∣2,fi​(x)=1−yi​(wTxi​+b).构造朗日辅助函数：
L ( w , b , α ) = g ( w , b ) + ∑ i = 1 m α i [ 1 − y i ( w T x i + b ) ] , α i ≥ 0 \begin{aligned} L(w,b,\alpha)=g(w,b)+\sum_{i=1}^m\alpha_i[1- y_i(w^Tx_i+b)],\alpha_i\geq0 \end{aligned} L(w,b,α)=g(w,b)+i=1∑m​αi​[1−yi​(wTxi​+b)],αi​≥0​
原问题： p ∗ = m i n [ w , b ] m a x [ α ] L ( w , b , α ) p*=min_{[w,b]} max_{[\alpha]} \enspace L(w,b,\alpha) p∗=min[w,b]​max[α]​L(w,b,α)
对偶问题： d ∗ = m a x [ α ] m i n [ w , b ] L ( w , b , α ) d*=max_{[\alpha]}min_{[w,b]}\enspace L(w,b,\alpha) d∗=max[α]​min[w,b]​L(w,b,α)
拉格朗日对偶函数： h ( α ) = m i n [ w , b ] L ( w , b , α ) h(\alpha)=min_{[w,b]}\enspace L(w,b,\alpha) h(α)=min[w,b]​L(w,b,α).

显然线性SVM模型满足强对偶条件，存在对偶问题，且最优解满足KKT条件中的： ∇ [ w , b ] L ( w , b , α ) = 0 \nabla_{[w,b]}L(w,b,\alpha)=0 ∇[w,b]​L(w,b,α)=0。所以求 h ( α ) h(\alpha) h(α)，对w,b分别求偏导即可：
L ( w , b , α ) = 1 2 w T w + ∑ i = 1 m α i [ 1 − y i ( w T x i + b ) ] ∂ L ∂ w = w − ∑ i = 1 m α i y i x i = 0 ∂ L ∂ b = − ∑ i = 1 m α i y i = 0 得 到 ： ( 1 ) w = ∑ i = 1 m α i y i x i ( 2 ) 0 = ∑ i = 1 m α i y i \begin{aligned} L(w,b,\alpha)=&\cfrac{1}{2}w^Tw+\sum_{i=1}^m\alpha_i[1- y_i(w^Tx_i+b)] \\ \cfrac{\partial L}{\partial w}=&w-\sum_{i=1}^m\alpha_iy_ix_i=0\\ \cfrac{\partial L}{\partial b}=&-\sum_{i=1}^m\alpha_iy_i=0\\ \\得到： (1)\enspace w=&\sum_{i=1}^m\alpha_iy_ix_i \\ (2)\enspace 0=&\sum_{i=1}^m\alpha_iy_i \end{aligned} L(w,b,α)=∂w∂L​=∂b∂L​=得到：(1)w=(2)0=​21​wTw+i=1∑m​αi​[1−yi​(wTxi​+b)]w−i=1∑m​αi​yi​xi​=0−i=1∑m​αi​yi​=0i=1∑m​αi​yi​xi​i=1∑m​αi​yi​​
上述得到的(1)(2)式非常重要，后续会用。现在将(1)(2)式带回 L ( w , b , α ) 得 h ( α ) L(w,b,\alpha)得h(\alpha) L(w,b,α)得h(α):
h ( α ) = 1 2 w T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i − w T ∑ i = 1 m α i y i x i = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i y i α j y j x i T x j \begin{aligned} h(\alpha)=&\frac{1}{2}w^T\sum_{i=1}^m\alpha_iy_ix_i+\sum_{i=1}^m\alpha_i-w^T\sum_{i=1}^m\alpha_iy_ix_i \\ =&\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\alpha_jy_jx_i^Tx_j \end{aligned} h(α)==​21​wTi=1∑m​αi​yi​xi​+i=1∑m​αi​−wTi=1∑m​αi​yi​xi​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​yi​αj​yj​xiT​xj​​
则得对偶问题 d ∗ = m a x [ α ] h ( α ) d^*=max_{[\alpha]}h(\alpha) d∗=max[α]​h(α)，即：
m a x α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i y i α j y j x i T x j s . t . ∑ i = 1 m α i y i = 0 ， α i ≥ 0 \begin{aligned} &max_{\alpha}\enspace\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\alpha_jy_jx_i^Tx_j \\ \\ &s.t. \sum_{i=1}^m\alpha_iy_i = 0，\alpha_i \geq 0 \end{aligned} ​maxα​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​yi​αj​yj​xiT​xj​s.t.i=1∑m​αi​yi​=0，αi​≥0​
这就是线性SVM模型得对偶问题,求解出 α \alpha α就能求解出 w , b w,b w,b。此时 α i \alpha_i αi​应该满足KKT条件：
{ α i ≥ 0 1 − y i ( w T x i + b ) ≤ 0 α i [ 1 − y i ( w T x i + b ) ] = 0 \begin{aligned} \begin{dcases} \alpha_i\geq0 & \\ 1-y_i(w^Tx_i+b)\leq 0&\\ \alpha_i[1- y_i(w^Tx_i+b)]=0 \end{dcases} \end{aligned} ⎩⎪⎨⎪⎧​αi​≥01−yi​(wTxi​+b)≤0αi​[1−yi​(wTxi​+b)]=0​​​
从KKT条件可以看出，总有 α i = 0 或 y i ( w T x i + b ) = 1 \alpha_i=0或y_i(w^Tx_i+b)=1 αi​=0或yi​(wTxi​+b)=1.若 α i = 0 \alpha_i=0 αi​=0，说明样本 x i x_i xi​不会出现在对偶问题得表达式中，对求解没有任何影响；若 α i > 0 ， 则 y i ( w T x i + b ) = 1 \alpha_i>0，则y_i(w^Tx_i+b)=1 αi​>0，则yi​(wTxi​+b)=1，说明该样本是支持向量。所以，支持向量机最终模型仅仅和少量的支持向量有关。

4.SMO算法

回顾一下线性SVM模型的对偶问题：
m a x α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i y i α j y j x i T x j s . t . ∑ i = 1 m α i y i = 0 ， α i ≥ 0 \begin{aligned} &max_{\alpha}\enspace\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\alpha_jy_jx_i^Tx_j \\ \\ &s.t. \sum_{i=1}^m\alpha_iy_i = 0，\alpha_i \geq 0 \end{aligned} ​maxα​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​yi​αj​yj​xiT​xj​s.t.i=1∑m​αi​yi​=0，αi​≥0​
这个问题是个二次规划问题，有m个参数，求解起来也相当复杂，于是伟大的数学家又发明了SMO算法来高效的解决二次规划问题。

SMO算法思想：对于有m个参数的二次规划问题，先选取两个参数做为变量，固定其余m-2个参数的值（看成常量），这样m个参数的二次规划问题就分解成了一系列2个参数的子问题，而单个子问题通过迭代求解是非常快的，所以SMO算法效率是很高的。

推导过程：
我们假设选取 α 1 , α 2 \alpha_1,\alpha_2 α1​,α2​,固定 [ α 3 , . . . , α m ] [\alpha_3,...,\alpha_m] [α3​,...,αm​]，则有：
α 1 y 1 + α 2 y 2 = C C = − ∑ i = 3 m α i y i \begin{aligned} \alpha_1y_1+\alpha_2y_2=C\\ C=-\sum_{i=3}^m\alpha_iy_i \end{aligned} α1​y1​+α2​y2​=CC=−i=3∑m​αi​yi​​
我们将目标函数展开：
F ( α ) = α 1 + α 2 + ∑ i = 3 m α i − 1 2 { α 1 2 y 1 2 x 1 T x 1 + 2 α 1 α 2 y 1 y 2 x 1 T x 2 + 2 ∑ j = 3 m α 1 α j y 1 y j x 1 T x j + α 2 2 y 2 2 x 2 T x 2 + 2 ∑ j = 3 m α 2 α j y 2 y j x 2 T x j + ∑ i = 3 m ∑ j = 3 m α i α j y i y j x i T x j } \begin{aligned} F(\alpha)=&\alpha_1+\alpha_2+\sum_{i=3}^m\alpha_i-\cfrac{1}{2}\{\alpha_1^2y_1^2x_1^Tx_1+2\alpha_1\alpha_2y_1y_2x_1^Tx_2 \\&+2\sum_{j=3}^m\alpha_1\alpha_jy_1y_jx_1^Tx_j+\alpha_2^2y_2^2x_2^Tx_2\\&+2\sum_{j=3}^m\alpha_2\alpha_jy_2y_jx_2^Tx_j+\sum_{i=3}^m\sum_{j=3}^m\alpha_i\alpha_jy_iy_jx_i^Tx_j\} \end{aligned} F(α)=​α1​+α2​+i=3∑m​αi​−21​{α12​y12​x1T​x1​+2α1​α2​y1​y2​x1T​x2​+2j=3∑m​α1​αj​y1​yj​x1T​xj​+α22​y22​x2T​x2​+2j=3∑m​α2​αj​y2​yj​x2T​xj​+i=3∑m​j=3∑m​αi​αj​yi​yj​xiT​xj​}​
常数项对求导不会有影响直接扔掉，并记 K i j = x i T x j K_{ij}=x_i^Tx_j Kij​=xiT​xj​,化简后得：
F ( α ) = α 1 + α 2 − 1 2 { α 1 2 K 11 + 2 α 1 α 2 y 1 y 2 K 12 + 2 ∑ j = 3 m α 1 α j y 1 y j K 1 j + α 2 2 K 22 + 2 ∑ j = 3 m α 2 α j y 2 y j K 2 j } \begin{aligned} F(\alpha)=&\alpha_1+\alpha_2-\cfrac{1}{2}\{\alpha_1^2K_{11}+2\alpha_1\alpha_2y_1y_2K_{12}+2\sum_{j=3}^m\alpha_1\alpha_jy_1y_jK_{1j}\\&+\alpha_2^2K_{22}+2\sum_{j=3}^m\alpha_2\alpha_jy_2y_jK_{2j}\} \end{aligned} F(α)=​α1​+α2​−21​{α12​K11​+2α1​α2​y1​y2​K12​+2j=3∑m​α1​αj​y1​yj​K1j​+α22​K22​+2j=3∑m​α2​αj​y2​yj​K2j​}​
将 α 1 = y 1 ( C − α 2 y 2 ) \alpha_1=y_1(C-\alpha_2y_2) α1​=y1​(C−α2​y2​)带入上式得，关于 α 2 的 一 元 函 数 \alpha_2的一元函数 α2​的一元函数：
F ( α 2 ) = y 1 ( C − α 2 y 2 ) + α 2 − 1 2 { ( C − α 2 y 2 ) 2 K 11 + 2 ( C − α 2 y 2 ) α 2 y 2 K 12 + 2 ∑ j = 3 m ( C − α 2 y 2 ) α j y j K 1 j + α 2 2 K 22 + 2 ∑ j = 3 m α 2 α j y 2 y j K 2 j } \begin{aligned} F(\alpha_2)=&y_1(C-\alpha_2y_2)+\alpha_2-\cfrac{1}{2}\{(C-\alpha_2y_2)^2K_{11}+2(C-\alpha_2y_2)\alpha_2y_2K_{12}\\&+2\sum_{j=3}^m(C-\alpha_2y_2)\alpha_jy_jK_{1j}+\alpha_2^2K_{22}+2\sum_{j=3}^m\alpha_2\alpha_jy_2y_jK_{2j}\} \end{aligned} F(α2​)=​y1​(C−α2​y2​)+α2​−21​{(C−α2​y2​)2K11​+2(C−α2​y2​)α2​y2​K12​+2j=3∑m​(C−α2​y2​)αj​yj​K1j​+α22​K22​+2j=3∑m​α2​αj​y2​yj​K2j​}​
对 α 2 \alpha_2 α2​求偏导，令其等于0：
∂ F ∂ α 2 = 1 − y 1 y 2 + ( C − α 2 y 2 ) y 2 K 11 − C y 2 K 12 + 2 α 2 K 12 − α 2 K 22 + ∑ j = 3 m α j y 2 y j K 1 j − ∑ j = 3 m α j y 2 y j K 2 j = 0 \begin{aligned} \cfrac{\partial F}{\partial \alpha_2}=&1-y_1y_2+(C-\alpha_2y_2)y_2K_{11}-Cy_2K_{12}+2\alpha_2K_{12}-\alpha_2K_{22}\\&+\sum_{j=3}^m\alpha_jy_2y_jK_{1j}-\sum_{j=3}^m\alpha_jy_2y_jK_{2j}=0 \end{aligned} ∂α2​∂F​=​1−y1​y2​+(C−α2​y2​)y2​K11​−Cy2​K12​+2α2​K12​−α2​K22​+j=3∑m​αj​y2​yj​K1j​−j=3∑m​αj​y2​yj​K2j​=0​
整理得：
α 2 ( K 11 + K 22 − 2 K 12 ) = 1 − y 1 y 2 + C y 2 K 11 − C y 2 K 12 + ∑ j = 3 m α j y 2 y j K 1 j − ∑ j = 3 m α j y 2 y j K 2 j \begin{aligned} \alpha_2(K_{11}+K_{22}-2K_{12})=&1-y_1y_2+Cy_2K_{11}-Cy_2K_{12}\\&+\sum_{j=3}^m\alpha_jy_2y_jK_{1j}-\sum_{j=3}^m\alpha_jy_2y_jK_{2j} \end{aligned} α2​(K11​+K22​−2K12​)=​1−y1​y2​+Cy2​K11​−Cy2​K12​+j=3∑m​αj​y2​yj​K1j​−j=3∑m​αj​y2​yj​K2j​​

这是一个迭代式，因为C与 α 2 o l d \alpha_2^{old} α2old​有关，将 α 1 o l d y 1 + α 2 o l d y 2 = C \alpha_1^{old}y_1+\alpha_2^{old}y_2=C α1old​y1​+α2old​y2​=C代入上式得：
α 2 n e w ( K 11 + K 22 − 2 K 12 ) = y 2 { y 2 − y 1 + α 1 o l d y 1 K 11 + α 2 o l d y 2 K 11 − α 1 o l d y 1 K 12 − α 2 o l d y 2 K 12 + ∑ j = 3 m α j y j K 1 j − ∑ j = 3 m α j y j K 2 j } \begin{aligned} \alpha_2^{new}(K_{11}+K_{22}-2K_{12})=&y_2\{y_2-y_1+\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{11}\\&-\alpha_1^{old}y_1K_{12}-\alpha_2^{old}y_2K_{12}+\sum_{j=3}^m\alpha_jy_jK_{1j}\\&-\sum_{j=3}^m\alpha_jy_jK_{2j}\} \end{aligned} α2new​(K11​+K22​−2K12​)=​y2​{y2​−y1​+α1old​y1​K11​+α2old​y2​K11​−α1old​y1​K12​−α2old​y2​K12​+j=3∑m​αj​yj​K1j​−j=3∑m​αj​yj​K2j​}​
其中SVM的线性模型为：
f ( x 1 ) = w T x 1 + b = ∑ i = 1 m α i y i x i T x 1 + b = α 1 o l d y 1 K 11 + α 2 o l d y 2 K 12 + ∑ i = 3 m α i y i K 1 i + b 同 理 ： f ( x 2 ) = α 1 o l d y 1 K 12 + α 2 o l d y 2 K 22 + ∑ i = 3 m α i y i K 2 i + b \begin{aligned} f(x_1)=&w^Tx_1+b \\=&\sum_{i=1}^m\alpha_iy_ix_i^Tx_1+b \\=&\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{12}+\sum_{i=3}^m\alpha_iy_iK_{1i}+b \\ 同理：f(x_2)=&\alpha_1^{old}y_1K_{12}+\alpha_2^{old}y_2K_{22}+\sum_{i=3}^m\alpha_iy_iK_{2i}+b \end{aligned} f(x1​)===同理：f(x2​)=​wTx1​+bi=1∑m​αi​yi​xiT​x1​+bα1old​y1​K11​+α2old​y2​K12​+i=3∑m​αi​yi​K1i​+bα1old​y1​K12​+α2old​y2​K22​+i=3∑m​αi​yi​K2i​+b​
将上述两个推导式代入迭代式得：
α 2 n e w ( K 11 + K 22 − 2 K 12 ) = y 2 { y 2 − y 1 + α 1 o l d y 1 K 11 + α 2 o l d y 2 K 11 − α 1 o l d y 1 K 12 − α 2 o l d y 2 K 12 + f ( x 1 ) − α 1 o l d y 1 K 11 − α 2 o l d y 2 K 12 − b − f ( x 2 ) + α 1 o l d y 1 K 12 + α 2 o l d y 2 K 22 + b } \begin{aligned} \alpha_2^{new}(K_{11}+K_{22}-2K_{12})=&y_2\{y_2-y_1+\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{11}\\&-\alpha_1^{old}y_1K_{12}-\alpha_2^{old}y_2K_{12}\\&+f(x_1)-\alpha_1^{old}y_1K_{11}-\alpha_2^{old}y_2K_{12}-b\\&- f(x_2)+\alpha_1^{old}y_1K_{12}+\alpha_2^{old}y_2K_{22}+b\} \end{aligned} α2new​(K11​+K22​−2K12​)=​y2​{y2​−y1​+α1old​y1​K11​+α2old​y2​K11​−α1old​y1​K12​−α2old​y2​K12​+f(x1​)−α1old​y1​K11​−α2old​y2​K12​−b−f(x2​)+α1old​y1​K12​+α2old​y2​K22​+b}​
整理得：
α 2 n e w ( K 11 + K 22 − 2 K 12 ) = y 2 { f ( x 1 ) − y 1 − ( f ( x 2 ) − y 2 ) + α 2 o l d y 2 ( K 11 + K 22 − 2 K 12 ) } 令 η = ( K 11 + K 22 − 2 K 12 ) E i = f ( x i ) − y i 则 有 ： α 2 n e w = α 2 o l d + y 2 ( E 1 − E 2 ) η α 1 n e w = y 1 ( C − α 2 n e w y 2 ) ( E 1 − E 2 ) = y 2 − y 1 + w o l d T ( x 1 − x 2 ) \begin{aligned} \alpha_2^{new}(K_{11}+K_{22}-2K_{12})=&y_2\{f(x_1)-y_1-(f(x_2)-y_2)\\&+\alpha_2^{old}y_2(K_{11}+K_{22}-2K_{12})\}\\ \\ 令\eta=&(K_{11}+K_{22}-2K_{12})\\ E_i=&f(x_i)-y_i \\ \\ 则有：\alpha_2^{new}=&\alpha_2^{old}+\cfrac{y_2(E_1-E_2)}{\eta}\\ \alpha_1^{new}=&y_1(C-\alpha_2^{new}y_2)\\ (E_1-E_2)=&y_2-y_1+w_{old}^T(x_1-x_2) \end{aligned} α2new​(K11​+K22​−2K12​)=令η=Ei​=则有：α2new​=α1new​=(E1​−E2​)=​y2​{f(x1​)−y1​−(f(x2​)−y2​)+α2old​y2​(K11​+K22​−2K12​)}(K11​+K22​−2K12​)f(xi​)−yi​α2old​+ηy2​(E1​−E2​)​y1​(C−α2new​y2​)y2​−y1​+woldT​(x1​−x2​)​

上述就是SMO算法关于 α 1 和 α 2 的 迭 代 式 \alpha_1和\alpha_2的迭代式 α1​和α2​的迭代式，SMO算法已经证明过是具有收敛性的，所以能够求解两个参数。并且，这个迭代式仅与选取的两个参数( α 1 和 α 2 \alpha_1和\alpha_2 α1​和α2​)所对应的样本( x 1 和 x 2 x_1和x_2 x1​和x2​)的预测值、标记值和向量内积有关。这样做一轮迭代仅和两个样本相关，效率是非常高的，所以SMO算法可以称为最快的二次规划求解算法。

两个变量的选择：
注意，上述推导过程我们假设取 α 1 和 α 2 \alpha_1和\alpha_2 α1​和α2​为参数，实际上参数的选取是有讲究的。

• 第一个变量的选择：违法KKT条件最严重的点，即违背 α i > 0 , y i f ( x i ) = 1 \alpha_i>0,y_if(x_i)=1 αi​>0,yi​f(xi​)=1和 α i = 0 , y i f ( x i ) ≥ 1 \alpha_i=0,y_if(x_i) \geq1 αi​=0,yi​f(xi​)≥1。
• 第二变量的选择：选择 ∣ E 1 − E 2 ∣ |E_1-E_2| ∣E1​−E2​∣最大化的点。

用SMO算法求出所有 α \alpha α之后， w = ∑ i = 1 m α i y i x i w=\sum_{i=1}^m\alpha_iy_ix_i w=∑i=1m​αi​yi​xi​。

b的求解只于支持向量有关。对于任意支持向量 ( x s , y s ) (x_s,y_s) (xs​,ys​)都有 y s f ( x s ) = 1 y_sf(x_s)=1 ys​f(xs​)=1,那么令 S = { s = i ∣ α i > 0 } S=\{s=i|\alpha_i>0\} S={s=i∣αi​>0}为支持向量的下标集合，则有：

b = 1 ∣ S ∣ ∑ s ∈ S ( y s − w T x s ) \begin{aligned} b=\cfrac{1}{|S|}\sum_{s \in S}(y_s-w^Tx_s) \end{aligned} b=∣S∣1​s∈S∑​(ys​−wTxs​)​