支持向量機（五）——SMO算法

〇、說明

支持向量機(Support Vector Machine,SVM)是監(jiān)督學(xué)習(xí)中非常經(jīng)典的算法。筆者主要參考學(xué)習(xí)的是李航老師《統(tǒng)計學(xué)習(xí)方法（第二版）》[1]和周志華老師的西瓜書《機器學(xué)習(xí)》[2]跷坝。

如有錯誤疏漏，煩請指正序无。如要轉(zhuǎn)載械念，請聯(lián)系筆者，hpfhepf@gmail.com座享。

關(guān)于這個算法婉商，讀者可以參考算法發(fā)明者Platt的原始論文[3][4]。知乎文章《支持向量機原理詳解(六): 序列最小最優(yōu)化(SMO)算法》[5][6]系列也是關(guān)于SMO算法不錯的文章，讀者可一并參考閱讀蕊蝗。

一烁巫、SMO算法簡介

1.1 為什么

支持向量機的學(xué)習(xí)是一個凸二次規(guī)劃問題，凸二次規(guī)劃問題問題具有全局最優(yōu)解蘑秽，有許多最優(yōu)化算法可以用于這一問題饺著。但當(dāng)訓(xùn)練樣本容量很大時，這些算法往往變得比較低效筷狼。目前有很多支持向量機的快速實現(xiàn)算法瓶籽，序列最小最優(yōu)化（Sequential Minimal Optimization，SMO）算法就是其中一個埂材。[1]

1.2 SMO算法思路

1. 在支持向量機的對偶問題優(yōu)化中塑顺，每一輪迭代，將其它變量看作常數(shù)俏险，只優(yōu)化其中兩個變量严拒。

2. 每一輪迭代，啟發(fā)式地選擇優(yōu)化量最大的兩個變量進行優(yōu)化竖独。

二裤唠、SMO算法詳述

支持向量機的對偶優(yōu)化問題如下

優(yōu)化問題一：

$\begin{split}&\mathop{min}\limits_{\alpha} \ &\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}K(x_{i} ,x_{j}) - \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2,\dots,N\end{split} \tag{1}$

優(yōu)化目標(biāo)是找到使目標(biāo)函數(shù)最小的拉格朗日乘子向量 $\alpha^*=(\alpha^*_{1},\alpha^*_{2},\dots,\alpha^*_{N})^T$ 。

2.1 兩個變量的優(yōu)化方法

每一輪迭代中莹痢，假設(shè)已選擇的兩個變量是 $\alpha_{1}$ 和 $\alpha_{2}$ 种蘸，其它變量 $\alpha_{i}(i=3,4,\dots,N)$ 是固定的。則式 $(1)$ 表示的優(yōu)化問題可以寫成

優(yōu)化問題二：

$\begin{split}& \mathop{min}\limits_{\alpha_{1},\alpha_{2}} \ \ & W(\alpha_{1},\alpha_{2})= \frac{1}{2} K_{11} \alpha^2_{1} + \frac{1}{2} K_{22} \alpha^2_{2} + y_{1}y_{2}K_{12}\alpha_{1} \alpha_{2} \\&& \qquad - (\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. & \alpha_{1} y_{1} + \alpha_{2} y_{2} = - \sum_{i=3}^N \alpha_{i} y_{i}=\varsigma \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2 \end{split} \tag{2}$

其中竞膳， $K_{ij}=K(x_{i},x_{j})$ 航瞭， $\varsigma$ 是常數(shù)，優(yōu)化目標(biāo)函數(shù)省略了不含 $\alpha_{1}$ 和 $\alpha_{2}$ 的常數(shù)項坦辟。

等式約束決定了這個優(yōu)化問題是一個單變量優(yōu)化問題刊侯，這里考慮為變量 $\alpha_{2}$ 的優(yōu)化問題。

第一步锉走，求解未經(jīng)剪輯的最優(yōu)解

定義

$g(x)=\sum_{i=1}^N \alpha_{i} y_{i} K(x_{i},x)+b \tag{3}$

? $E_{i}=g(x_{i}) - y_{i} = (\sum_{j=1}^N \alpha_{j} y_{j} K(x_{j},x_{i})+b)-y_{i} \tag{4}$

$v_{i}= \sum_{i=3}^N \alpha_{j} y_{j} K(x_{i},x_{j}) = g(x_{i}) - \sum_{j=1}^2 \alpha_{j} y_{j} K(x_{i},x_{j})-b \tag{5}$

則目標(biāo)函數(shù)可寫為

$\begin{split}W(\alpha_{1},\alpha_{2})= & \frac{1}{2}K_{11} \alpha^2_{1}+\frac{1}{2}K_{22}\alpha^2_{2}+y_{1}y_{2}K_{12}\alpha_{1}\alpha_{2}\\ &-(\alpha_{1}+\alpha_{2})+y_{1}v_{1}\alpha_{1}+y_{2}v_{2}\alpha_{2} \end{split} \tag{6}$

由 $\alpha_{1} y_{1}+\alpha_{2} y_{2} = \varsigma$ 可得 $\alpha_{1} = y_{1}(\varsigma -\alpha_{2} y_{2})$ 滨彻，代入上式，目標(biāo)函數(shù)可表示為單變量 $\alpha_{2}$ 的目標(biāo)函數(shù)

$\begin{split}W(\alpha_{2})= & \frac{1}{2}K_{11} (\varsigma -\alpha_{2 } y_{2})^2+\frac{1}{2}K_{22}\alpha^2_{2}+y_{2}K_{12}(\varsigma -\alpha_{2} y_{2})\alpha_{2}\\ &-(y_{1}(\varsigma -\alpha_{2}y_{2})+\alpha_{2})+v_{1}(\varsigma -\alpha_{2}y_{2})+y_{2}v_{2}\alpha_{2} \end{split} \tag{7}$

對 $\alpha_{2}$ 求導(dǎo)

$\begin{split}\frac{\partial}{\partial \alpha_{2}} W(\alpha_{2})= & y_{2} K_{11} (\alpha_{2} y_{2} -\varsigma )+K_{22} \alpha_{2} + y_{2} K_{12} (\varsigma -\alpha_{2} y_{2}) \\& + y_{2} K_{12} (-y_{2}) \alpha_{2} + y_{1} y_{2} -1 - v_{1} y_{2} + y_{2} v_{2} \\= & (K_{11}+K_{22}-2K_{12}) \alpha_{2} +y_{2} \varsigma(K_{12} - K_{11}) \\& + y_{1} y_{2} -1 - v_{1} y_{2} + y_{2} v_{2} \\\end{split} \tag{8}$

令其為0挪蹭，得到

$\alpha_{2} = \frac{1}{K_{11}+K_{22}-2K_{12}} y_{2}(y_{2}-y_{1}+v_{1}-v_{2}+K_{11}\varsigma -K_{12}\varsigma ) \tag{9}$

將等號左邊 $\alpha_{2}$ 用 $\alpha^{new,unc}$ 代替亭饵，等號右邊代入 $v_{i},i=1,2$ 和 $\varsigma = \alpha^{old}_{1} y_{1} + \alpha^{old}_{2} y_{2}$ ，并令 $\eta =K_{11}+K_{22}-2K_{12}$ 梁厉，則有

$\begin{split}\alpha^{new,unc}_{2} = & \frac{1}{\eta} y_{2}[y_{2} - y_{1} + K_{11} \alpha^{old}_{1} y_{1} + K_{11} \alpha^{old}_{2} y_{2} - K_{12} \alpha^{old}_{1} y_{1} - K_{12} \alpha^{old}_{2} y_{2} \\ & + (g(x_{1})-K_{11} \alpha^{old}_{1} y_{1} - K_{12} \alpha^{old}_{2} y_{2} - b) \\& - (g(x_{2}) - K_{12} \alpha^{old}_{1} y_{1} - K_{22} \alpha^{old}_{2} y_{2} - b)] \\= & \frac{1}{\eta} y_{2}[(K_{11} + K_{22} - 2K_{12}) y_{2} \alpha^{old}_{2} + (g(x_{1}) - y_{1}) - (g(x_{2}) - y_{2})] \\= & \alpha^{old}_{2} + \frac{1}{\eta} y_{2}(E_{1} - E_{2})\end{split} \tag{10}$

即

$\alpha^{new,unc}_{2} = \alpha^{old}_{2} + \frac{1}{\eta} y_{2}(E_{1} - E_{2})\tag{11}$

這里需要注意冬骚， $\eta =K_{11}+K_{22}-2K_{12} = ||\phi (x_{1}) - \phi(x_{2})||^2$ 。

第二步，確定剪輯邊界

兩個變量 $(\alpha_{1},\alpha_{2})$ 的約束只冻，如下圖所示

圖1[4]

式 $(2)$ 不等式約束使得 $\alpha_{1}$ 和 $\alpha_{2}$ 正方形 $[0,C]\times [0,C]$ 內(nèi)庇麦，等式約束使得它們在平行于正方形對角線的直線上。

如上所述喜德，優(yōu)化問題二（式 $(2)$ ）實質(zhì)上是一個但變量優(yōu)化問題山橄，同樣，我們?yōu)榭紤] $\alpha_{2}$ 的優(yōu)化問題舍悯。由于 $\alpha^{new}_{2}$ 需要滿足不等式約束航棱，所以有

$L \leq \alpha^{new}_{2} \leq H \tag{12}$

由式 $(2)$ 的等式約束 $\alpha_{1} y_{1} + \alpha_{2} y_{2} = \varsigma$ ，當(dāng) $y_{1} \neq y_{2}$ 時萌衬， $\alpha_{1} - \alpha_{2} = \gamma$ （ $\gamma$ 是一個常數(shù)饮醇，滿足 $|\gamma |=|\varsigma |$ ），則有

$L = max(0,-\gamma ),\quad H=min(C,C-\gamma ) \tag{13}$

當(dāng) $y_{1} = y_{2}$ 時秕豫， $\alpha_{1} + \alpha_{2} = \gamma$ 朴艰，則有

$L = max(0,\gamma - C),\quad H=min(C,\gamma ) \tag{14}$

第三步，剪輯優(yōu)化結(jié)果

綜上所述混移，經(jīng)剪輯后的 $\alpha_{2}$ 為

$\alpha^{new}_{2} = \begin{cases}H, & \alpha^{new,unc}_{2} > H \\\alpha^{new,unc}_{2}, & L \leq \alpha^{new,unc}_{2} \leq H \\L, & \alpha^{new,unc}_{2} </p><p><b>第四步祠墅，求解<img class=$

根據(jù)式 $(2)$ 的等式約束，求解 $\alpha^{new}_{1}$

$\alpha^{new}_{1}=\alpha^{old}_{1} +y_{1} y_{2}(\alpha^{old}_{2} - \alpha^{new}_{2}) \tag{16}$

2.2 第一個待優(yōu)化變量選擇

SMO算法稱選擇第一個優(yōu)化變量的過程為外層循環(huán)歌径。每次只選擇兩個變量進行優(yōu)化毁嗦，那如何選擇呢？

支持向量機是凸優(yōu)化問題回铛，滿足KKT條件的點是支持向量機優(yōu)化問題的解[7]狗准。

線性支持向量機的符合KKT條件如下

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*)\geq 1-\xi^* _{i},\ i=1,2,\dots,N \tag{17a}\\& \xi^*_{i} \geq 0, \ i=1,2,\dots,N \tag{17b} \\& \alpha^*_{i} \geq 0, \ i=1,2,\dots,N \tag{17c} \\& \alpha^*_{i}(y_{i}(w^*\cdot x_{i}+b^*)-1+\xi^*_{i})=0,\ i=1,2,\dots,N \tag{17d} \\& \mu^*_{i}\xi^*_{i}=0, \ i=1,2,\dots,N \tag{17e}\\& \frac{\partial}{\partial w} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \tag{17f} \\& \frac{\partial}{\partial b} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=-\sum_{i=1}^N \alpha^*_{i}y_{i}=0 \tag{17g} \\& \frac{\partial}{\partial \xi_{i}} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=C-\alpha^*_{i}-\mu^*_{i}=0 , \ i=1,2,\dots,N\tag{17h} \end{align}$

將式 $(16d)$ 、 $(16e)$ 茵肃、 $(16f)$ 和 $(16h)$ 單獨拿出來驶俊，如下

$\begin{align}& \alpha^*_{i}(y_{i}(w^*\cdot x_{i}+b^*)-1+\xi^*_{i})=0,\ i=1,2,\dots,N \\& \mu^*_{i}\xi^*_{i}=0, \ i=1,2,\dots,N \\& \frac{\partial}{\partial w} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \\& \frac{\partial}{\partial \xi_{i}} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=C-\alpha^*_{i}-\mu^*_{i}=0 , \ i=1,2,\dots,N \end{align} \tag{18}$

由上式可推導(dǎo)出

$\begin{align} \alpha^*_{i}=0 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}(x_{i} \cdot x_{j})+b^*) \geq1 \\ 0< \alpha^*_{i} <1 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}(x_{i} \cdot x_{j})+b^*) =1 \\ \alpha^*_{i}=C & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}(x_{i} \cdot x_{j})+b^*) \leq1\end{align} \tag{19}$

這里需要注意，上式中免姿，“ $\Rightarrow$ ”在李航老師《統(tǒng)計學(xué)習(xí)方法（第二版）》中，使用的是“ $\Leftrightarrow$ ”榕酒，這個是不嚴(yán)謹(jǐn)?shù)呐卟病Ｌ鎿Q成核函數(shù)版本，如下

$\begin{align} \alpha^*_{i}=0 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}K(x_{i} , x_{j})+b^*) \geq1 \\ 0< \alpha^*_{i} <1 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}K(x_{i} , x_{j})+b^*) =1 \\ \alpha^*_{i}=C & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}K(x_{i} , x_{j})+b^*) \leq1\end{align} \tag{20}$

代入 $g(x_{i})$ 的定義想鹰，在優(yōu)化過程中紊婉， $\alpha=(\alpha_{1},\alpha_{2},\dots,\alpha_{N})^T$ 不是最優(yōu)解，所以辑舷，驗證條件應(yīng)表述為

$\begin{align} \alpha_{i}=0 & \Rightarrow y_{i} g(x_{i}) \geq1 \\ 0< \alpha_{i} <1 & \Rightarrow y_{i} g(x_{i}) =1 \\ \alpha_{i}=C & \Rightarrow y_{i} g(x_{i}) \leq1\end{align} \tag{21}$

這就是SMO算法選擇第一個優(yōu)化變量的條件喻犁，也是停機條件。

第一個優(yōu)化變量的選擇方法：首先遍歷滿足 $0 < \alpha_{i} < C$ 的樣本點，檢驗它們是否滿足式 $(6b)$ 肢础；如果這些樣本點都不滿足約束还栓，則遍歷 $\alpha_{i}=0$ 和 $\alpha_{i} = C$ 的樣本點，檢驗是否符合式 $(6a)$ 和 $(6c)$ 的約束传轰。

這里需要注意剩盒，在下面選擇第二個優(yōu)化變量時，有可能會拋棄一選擇的第一個變量慨蛙，重新選擇第一個變量辽聊，詳見下文。

2.3 第二個優(yōu)化變量選擇

SMO算法稱選擇第二個優(yōu)化變量的過程為內(nèi)層循環(huán)期贫。假設(shè)已經(jīng)找到了第一個優(yōu)化變量 $\alpha_{1}$ 跟匆。第二個優(yōu)化變量 $\alpha_{2}$ 的選擇標(biāo)準(zhǔn)是希望這個變量有足夠大的變化。

第一種方式

由式 $(11)$ 可知通砍， $\alpha^{new}_{2}$ 是依賴于 $|E_{1}-E_{2}|$ 的玛臂，為了加快計算速度，可以選擇使之最大的 $\alpha_{1}$ 埠帕，一般來講就是選擇與 $E_{1}$ 符號相反垢揩，絕對值最大 $E_{i}$ 對應(yīng)的 $\alpha_{i}$ 作為第二個優(yōu)化變量。

通常敛瓷，為了加快速度叁巨， $E_{i}$ 保存在一個列表里。

第二種方式

特殊情況下呐籽，如果內(nèi)層循環(huán)找到的 $\alpha_{2}$ 不能使目標(biāo)函數(shù)有足夠的下降锋勺，則采用另一種啟發(fā)方式繼續(xù)選擇 $\alpha_{2}$ ：遍歷在間隔邊界上的支持向量點（滿足 $0<\alpha_{i} <C$ 的樣本），依次試用狡蝶，直到目標(biāo)函數(shù)有足夠的下降庶橱。

如果還找不到合適的 $\alpha_{2}$ ，遍歷所有數(shù)據(jù)集贪惹；如果仍然找不到苏章，則放棄這個 $\alpha_{1}$ ，重新選擇奏瞬。

2.4 更新 $b$

為什么要更新 $b$ 枫绅，因為后面更新 $E_{i}$ 時要用到。在前面幾篇筆記所述的支持向量機[b][c]理論中硼端，參數(shù) $b$ 是根據(jù)最優(yōu)拉格朗日乘子 $\alpha^*$ 來計算的并淋。但是在SMO算法中， $b$ 是跟隨 $\alpha_{i}(i=1,2)$ 優(yōu)化的變量珍昨。

如何優(yōu)化參數(shù) $b$ 呢县耽，KKT條件就是優(yōu)化的方向（符合KKT條件的解是最優(yōu)解[5]）句喷。因為是局部優(yōu)化，需要先分別求解 $b^{new}_{1}$ 和 $b^{new}_{2}$ 兔毙，然后再求出 $b^{new}$ 唾琼，先求 $b^{new}_{1}$ ，根據(jù)式 $(21)$ 瞒御，當(dāng) $0<\alpha_{1} < C$ 時父叙，

$\begin{split}b^{new}_{1} & = y_{1} - \sum_{i=1}^N \alpha_{i} y_{i} K_{i1} \\ &= y_{1} - \sum_{i=3}^N \alpha_{i} y_{i}K_{i1} - \alpha^{new}_{1} y_{1}K_{11} - \alpha^{new}_{2} y_{2} K_{12}\end{split}\tag{22}$

因為 $E_{1}$ 已經(jīng)保存在列表里，可以利用其來計算 $b^{new}_{1}$ 肴裙，減少計算量趾唱。由 $E_{i}$ 定義可知

$\begin{split}E_{1} &= \sum_{i=1}^N \alpha_{i} y_{i}K_{i1} + b^{old} - y_{1} \\&= \sum_{i=3}^N \alpha_{i} y_{i} k_{i1} + \alpha^{old}_{1} y_{1} K_{11} + \alpha^{old}_{2} y_{2} K_{12} + b^{old} - y_{1}\end{split} \tag{23}$

可得

$y_{1} - \sum_{i=3}^N \alpha_{i} y_{i} K_{i1} = -E_{1} + \alpha^{old}_{1} y_{1} K_{11} + \alpha^{old}_{2} y_{2} K_{12} + b^{old} \tag{24}$

代入式 $(22)$ ，可得

$b^{new}_{1} = -E_{1} - y_{1} K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) - y_{2} K_{12} (\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{old} \tag{25}$

同理蜻懦，當(dāng) $0<\alpha_{2} < C$ 時甜癞，有

$b^{new}_{2} = -E_{2} - y_{1} K_{12}(\alpha^{new}_{1} - \alpha^{old}_{1}) - y_{2} K_{22} (\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{old} \tag{26}$

通過 $b^{new}_{1}$ 和 $b^{new}_{2}$ 計算 $b^{new}$ ，分兩種情況：

第一種情況

當(dāng) $0<\alpha^{new}_{i} <C,i=1,2$ 時宛乃， $b^{new}_{1} = b^{new}_{2}$ 悠咱，證明如下

將式 $(16)$ 的變形 $\alpha^{new}_{1} - \alpha^{old}_{1} = -y_{1} y_{2} (\alpha^{new}_{2} - \alpha^{old}_{2})$ 代入式 $(25)$ 和 $(26)$ ，計算

$\begin{split}b^{new}_{1} - b^{new}_{2} &= -(E_{1} - E_{2}) + y_{2} (K_{11} + K_{22} - 2K_{12})(\alpha^{new}_{2} - \alpha^{old}_{2}) \\&=y_{2}\eta (-\frac{y_{2}(E_{1} - E_{2})}{\eta} - \alpha^{old}_{2} + \alpha^{new}_{2}) \\&= y_{2}\eta (\alpha^{new}_{2} - \alpha^{new,unc}_{2})\end{split} \tag{27}$

上式中征炼， $\eta = K_{11} + K_{22} -2K_{12}$ 析既。當(dāng) $0<\alpha^{new}_{i} <C,i=1,2$ 時， $\alpha^{new}_{2}$ 在約束邊界內(nèi)谆奥，剪輯前后相同眼坏，所以有

$b^{new}_{1} - b^{new}_{2} = 0 \tag{28}$

此時，

$b^{new} = b^{new}_{1} \tag{29}$

第二種情況

當(dāng) $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在邊界上酸些，且 $L\neq H$ 時宰译，第一種情況求得的值還可以繼續(xù)使用。 $b^{new}_{1}$ 和 $b^{new}_{2}$ 以及它們之間的數(shù)都符合KKT條件（因為證明較復(fù)雜魄懂，且用到后面的知識沿侈，證明放在附錄），選擇他們的中點作為 $b^{new}$ 市栗，也即

$b^{new} = \frac{1}{2}(b^{new}_{1} + b^{new}_{2}) \tag{30}$

這里需要注意缀拭，這里有一個 $L\neq H$ 的條件。為什么有這樣一個條件填帽？如下圖蛛淋，當(dāng) $L = H$ 時，直線 $\alpha_{1} - \alpha_{2} = \gamma$ 或 $\alpha_{1} + \alpha_{2} = \gamma$ 在約束范圍內(nèi)退化成一個點（讀者可自己證明）盲赊，沒有優(yōu)化的空間，這樣的 $(\alpha_{1},\alpha_{2})$ 需要重新選擇敷扫。

圖2

2.5 更新 $E_{i}$

如前所述哀蘑，挑選和計算 $\alpha^{new}_{2}$ 時诚卸，都會用到 $E_{i}$ 。每次迭代都需要更新 $E_{i}$ 绘迁，以備下一輪迭代使用合溺。

根據(jù) $E_{i}$ 的定義（式 $(4)$ ），有

$E^{old}_{i} = \sum_{j=3}^N \alpha_{j} y_{j} k_{ij} + \alpha^{old}_{1} y_{1} K_{1i} + \alpha^{old}_{2} y_{2} K_{2i} + b^{old} - y_{i}\tag{31}$

$E^{new}_{i} = \sum_{j=3}^N \alpha_{j} y_{j} k_{ij} + \alpha^{new}_{1} y_{1} K_{1i} + \alpha^{new}_{2} y_{2} K_{2i} + b^{new} - y_{i}\tag{32}$

變換式 $(31)$ 和式 $(32)$ 可得

$E^{new}_{i} = E^{old}_{i} + y_{1}K_{1i}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{2i}(\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{new} - b^{old} \tag{33}$

可以證明（讀者可自行證明）缀台，當(dāng) $0<\alpha^{new}_{i} <C,i=1,2$ 時棠赛，

$E^{new}_{i} = 0 \tag{34}$

原始論文中[4]，作者表示式 $(33)$ 用來更新沒有參與優(yōu)化且不在邊界上的支持向量對應(yīng)的 $E_{i}$ 膛腐，也即更新除 $\alpha_{1}$ 和 $\alpha_{2}$ 以外且 $0<\alpha_{i} <C$ 對應(yīng)的 $E_{i}$ 睛约。

但我認(rèn)為，當(dāng) $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在邊界上哲身，不符合式 $(34)$ 辩涝，此時至少有一個參與優(yōu)化的變量對應(yīng)的 $E_{i}$ 也需要更新。

三勘天、SMO算法總結(jié)

第一步怔揩，給定精度參數(shù) $\varepsilon$ ，初始化 $\alpha = \boldsymbol 0$ 脯丝， $b=0$ 商膊。

第二步，按照2.2節(jié)和2.3節(jié)選擇優(yōu)化變量宠进，按照2.1節(jié)解析求解優(yōu)化問題晕拆，更新這兩個變量。

第三步砰苍，按照2.4節(jié)和2.5節(jié)更新 $b$ 和 $E_{i}$ 潦匈。

第四步，在精度 $\varepsilon$ 范圍內(nèi)檢查是否滿足KKT條件（式 $(21)$ ）：若滿足赚导，則轉(zhuǎn)第五步茬缩；不滿足，則轉(zhuǎn)第二步吼旧。

第五步凰锡，得到最優(yōu)解 $\alpha^*,b^*$ 。

這里圈暗，精度 $\varepsilon$ 內(nèi)檢查讀者可參看參考資料[6]掂为。

四、附錄

A员串、 $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在邊界上時 $b^{new}$ 符合KKT條件的證明

重復(fù)正文2.4節(jié)的結(jié)論：當(dāng) $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在邊界上勇哗，且 $L\neq H$ 時， $b^{new}_{1}$ 和 $b^{new}_{2}$ 以及它們之間的數(shù)都符合KKT條件寸齐。

這里參考[8]予以證明欲诺。

如正文2.5節(jié)所述抄谐，當(dāng) $0<\alpha^{new}_{i} < C, i=1,2$ 時， $E^{new}_{i} = 0, i=1,2$ 扰法。但當(dāng) $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在剪輯邊界上時蛹含，也即 $\alpha^{new}_{1}$ 和 $\alpha^{new}_{2}$ 至少有一個為0或 $C$ 。當(dāng)某一個變量為0或C時塞颁， $E^{new}_{i},i=1,2$ 不一定為0浦箱。更一般的，我們暫時認(rèn)為它們不為0祠锣。由正文式 $(33)$ 酷窥，有

$E^{new}_{1} = E^{old}_{1} + y_{1}K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{12}(\alpha^{new}_{2} - \alpha^{old}_{2}) + \Delta b \tag{a1}$

$E^{new}_{2} = E^{old}_{2} + y_{1}K_{12}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{22}(\alpha^{new}_{2} - \alpha^{old}_{2}) + \Delta b \tag{a2}$

當(dāng)變量在邊界時，經(jīng)過剪輯锤岸，由正文式 $(11)$ 竖幔，有

$\alpha^{new}_{2} - \alpha^{old}_{2} = \frac{1}{\eta} \lambda y_{2}(E^{old}_{1} - E^{old}_{2}) \tag{a3}$

其中， $0 \leq \lambda \leq 1$ 是偷， $\eta = K_{11} +K_{22} - 2K_{12}$ 拳氢。又由正文式 $(16)$ ，有

$\alpha^{new}_{1} - \alpha^{old}_{1} = -y_{1} y_{2}(\alpha^{new}_{2} - \alpha^{old}_{2}) \tag{a4}$

將式 $(a3)$ 代入式 $(a4)$ 蛋铆，可得

$\alpha^{new}_{1} - \alpha^{old}_{1} = -\frac{1}{\eta} \lambda y_{1} (E^{old}_{1} - E^{old}_{2}) \tag{a5}$

將式 $(a3)$ 和式 $(a5)$ 代入正文式 $(25)$ 馋评，有

$\begin{split}b^{new}_{1} &= -E^{old}_{1} - y_{1} K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) - y_{2} K_{12} (\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{old} \\&= - E^{old}_{1} + \frac{1}{\eta} \lambda K_{11} (E^{old}_{1} - E^{old}_{2}) - \frac{1}{\eta} \lambda K_{12} (E^{old}_{1} - E^{old}_{2}) + b^{old}\\&=-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) + b^{old}\end{split} \tag{a6}$

同理有

$b^{new}_{2} = -E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2}) + b^{old} \tag{a7}$

構(gòu)造 $b^{new}$ 如下，其中 $0 \leq t \leq 1$ 刺啦，使得 $b^{new}$ 在 $b^{new}_{1}$ 和 $b^{new}_{2}$ 之間

$b^{new} = tb^{new}_{1} + (1-t)b^{new}_{2} \tag{a8}$

將式 $(a6)$ 和式 $(a7)$ 代入式 $(a8)$ 留特，構(gòu)造 $\Delta b$ ，有

$\begin{split}\Delta b &= & b^{new} - b^{old} \\&= & tb^{new}_{1} + (1 - t) b^{new}_{2} - b^{old} \\&= & t(-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) + b^{old}) \\&& + (1 - t)(-E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2}) + b^{old}) - b^{old} \\&= & t(-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) ) \\&& + (1 - t)(-E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2}) ) \end{split} \tag{a9}$

將式 $(a3)$ 玛瘸、式 $(a4)$ 和式 $(a9)$ 代入式 $(a1)$ 蜕青，可得

$\begin{split}E^{new}_{1} &=& E^{old}_{1} + y_{1}K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{12}(\alpha^{new}_{2} - \alpha^{old}_{2}) + \Delta b \\&=& E^{old}_{1} - \frac{1}{\eta} \lambda K_{11}(E^{old}_{1} - E^{old}_{2}) + \frac{1}{\eta} \lambda K_{12}(E^{old}_{1} - E^{old}_{2}) + \Delta b \\&=& E^{old}_{1} - \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) + \Delta b \\&=& E^{old}_{1} - \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) \\&& + t(-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2})) \\&& +(1 - t)(-E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2})) \\&=& E^{old}_{1} - E^{old}_{2} - t(E^{old}_{1} - E^{old}_{2}) \\&& - \frac{1}{\eta} \lambda (K_{11} - 2K_{12} + K_{22})(E^{old}_{1} - E^{old}_{2}) \\&& + \frac{1}{\eta} \lambda t (K_{11} - 2K_{12} + K_{22})(E^{old}_{1} - E^{old}_{2}) \\&=& (1 - t - \lambda + \lambda t)(E^{old}_{1} - E^{old}_{2}) \\&=& (1 - t)(1 - \lambda)(E^{old}_{1} - E^{old}_{2})\end{split}\tag{a10}$

同理可得

$E^{new}_{2} = - t (1 - \lambda)(E^{old}_{1} - E^{old}_{2}) \tag{a11}$

當(dāng) $\alpha^{new}_{2} = 0$ 時

$\begin{split} & \alpha^{new}_{2} - \alpha^{old}_{2} \leq 0 \\ \Leftrightarrow \quad &\frac{1}{\eta} \lambda y_{2} (E^{old}_{1} - E^{old}_{2}) \leq 0 \\\Leftrightarrow \quad & y_{2}(E^{old}_{1} - E^{old}_{2}) \leq 0 \\\Leftrightarrow \quad & y_{2}(-t (1 - \lambda)(E^{old}_{1} - E^{old}_{2})) \geq 0 \\\Leftrightarrow \quad & y_{2} E^{new}_{2} \geq 0 \\\Leftrightarrow \quad & y_{2}(g(x_{2}) - y_{2}) \geq 0 \\\Leftrightarrow \quad & y_{2}g(x_{2}) \geq 1\end{split} \tag{a12}$

符合正文式 $(21)$ KKT條件。

當(dāng) $\alpha^{new}_{2} = C$ 時

$\begin{split} & \alpha^{new}_{2} - \alpha^{old}_{2} \geq 0 \\ \Leftrightarrow \quad &\frac{1}{\eta} \lambda y_{2} (E^{old}_{1} - E^{old}_{2}) \geq 0 \\\Leftrightarrow \quad & y_{2}(-t (1 - \lambda)(E^{old}_{1} - E^{old}_{2})) \leq 0 \\\Leftrightarrow \quad & y_{2} E^{new}_{2} \leq 0 \\\Leftrightarrow \quad & y_{2}g(x_{2}) \leq 1\end{split} \tag{a13}$