SMO（Sequential minimal optimization）

引子

前面章節(jié)中，我們使用了核函數(shù)的軟間隔支持向量機(jī)的優(yōu)化模型為：
$$\underset{a}{\max }\sum _{i=1}^m{a}^{(i)}?\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{a}^{(i)}{a}^{(j)}{y}^{(i)}{y}^{(j)}\kappa (x^{(i)},x^{(j)})$$$$s.t.\sum _{i=1}^m{a}^{(i)}{y}^{(i)}=0,$$$$0\le {\alpha }^{(i)}\le C,i=1,2,3,...,m\text{\hspace{1em}(1)}$$

式 (1) 需要滿足的 KKT 條件為：
$$a^{(i)}=0?y^{(i)}f(x^{(i)})\ge 1,$$$$0\le {\alpha }^{(i)}\le C?f(x^{(i)})=1$$$${\alpha }^{(i)}=C?y^{(i)}f(x^{(i)})\le 1\text{\hspace{1em}(2)}$$

在 SMO（序列最小化）方法出現(xiàn)之前，人們依賴于二次規(guī)劃求解工具來解決上述的優(yōu)化問題，訓(xùn)練 SVM。這些工具需要具有強(qiáng)大計(jì)算能力的計(jì)算機(jī)進(jìn)行支撐，實(shí)現(xiàn)也比較復(fù)雜。1998 年，微軟研究院的 John Platt 提出了 SMO 算法將優(yōu)化問題分解為容易求解的若干小的優(yōu)化問題，來訓(xùn)練 SVM。簡言之，SMO 僅關(guān)注 $alpha$ 對(duì) 和 偏置 $b$ 的求解更新，進(jìn)而求解出權(quán)值向量 $w$ ，得到?jīng)Q策邊界（分割超平面），從而大大減少了運(yùn)算復(fù)雜度。

算法介紹

SMO 會(huì)選擇一對(duì) ${\alpha }^{(i)}$ 及 ${\alpha }^{(j)}$ ，并固定住其他參數(shù)，即將其他參數(shù)認(rèn)為是常數(shù)，則式 （1）中的約束條件就可寫為：

$$a^{(i)}{y}^{(i)}+a^{(j)}{y}^{(j)}=k$$$$0\le {\alpha }^{(i)}\le C$$$$0\le {\alpha }^{(j)}\le C\text{\hspace{1em}(3)}$$

其中：
$$k=?\sum _{k=i,j}{a}^{(k)}{y}^{(k)}\text{\hspace{1em}(4)}$$

那么，式 (1) 的優(yōu)化問題可以推導(dǎo)：
$$\underset{\{a^{(i)}{a}^{(j)}\}}{\max }(a^{(i)}+a^{(j)})?[\frac{1}{2}{K}_{ii}(a^{(i)}{)}^2+\frac{1}{2}{K}_{jj}(a^{(j)}{)}^2+y^{(i)}{y}^{(j)}{K}_{ij}{a}^{(i)}{a}^{(j)}]$$$$?[y^{(i)}{a}^{(i)}\sum _{k=3}^m{y}^{(k)}{a}^{(k)}{K}_{ki}+y^{(j)}{a}^{(j)}\sum _{k=3}^m{y}^{(k)}{a}^{(k)}{K}_{kj}]$$$$s.t.a^{(i)}{y}^{(i)}+a^{(j)}{y}^{(j)}=?\sum _{k=i,j}{a}^{(k)}{y}^{(k)}=k,$$$$0\le {\alpha }^{(i)}\le C,0\le {\alpha }^{(j)}\le C\text{\hspace{1em}(5)}$$

• 由 $0\le {\alpha }^{(i)}\le C,0\le {\alpha }^{(j)}\le C$ 知，${\alpha }^{(i)}$ 及 ${\alpha }^{(i)}$ 的取值需要落在正方形中。
• 由 ${\alpha }^{(i)}{y}^{(i)}+{\alpha }^{(j)}{y}^{(j)}=k$ 知，${\alpha }^{(i)}$ 及 ${\alpha }^{(j)}$ 的取值需要落在正方形中取值還需要落到圖示的斜線段上。

假設(shè)我們放縮了 ${\alpha }^{(i)}$ 的取值：
$$L\le {\alpha }^{(i)}\le H\text{\hspace{1em}(6)}$$

我們可以確定出 ${\alpha }^{(i)}$ 的上下界為：

• $y^{(i)}=y^{(j)}$ 時(shí)：
  $$L=\max (0,{\alpha }^{(j)}?{\alpha }^{(i)}),H=\min (C,C+{\alpha }^{(j)}?{\alpha }^{(i)})\text{\hspace{1em}(7)}$$

• $y^{(i)}=y^{(j)}$ 時(shí)：
  $$L=\max (0,{\alpha }^{(j)}+{\alpha }^{(i)}?C),H=\min (C,{\alpha }^{(j)}+{\alpha }^{(i)})\text{\hspace{1em}(8)}$$

我們將優(yōu)化函數(shù)定義為：
$$\Psi =({\alpha }^{(j)}+{\alpha }^{(i)})?[\frac{1}{2}{K}_{ii}(a^{(i)}{)}^2+\frac{1}{2}{K}_{jj}(a^{(j)}{)}^2+y^{(i)}{y}^{(j)}{K}_{ij}{a}^{(i)}{a}^{(j)}]\text{\hspace{1em}(9)}$$

由于 ${\alpha }^{(i)}$ 與 ${\alpha }^{(j)}$ 有線性關(guān)系，所以式 (9) 可以消去 ${\alpha }^{(i)}$ ，進(jìn)而令 $\Psi$ 對(duì) ${\alpha }^j$ 求二階導(dǎo)，并令二階導(dǎo)為 0 可得（中間過程省略）：
$$a^{(jnew)}=(2K_{ij}?K_{ii}?K_{jj})=a^{(jold)}(2K_{ij}?K_{ii}?K_{jj})?y^{(i)}(E^{(i)}?E^{(j)})\text{\hspace{1em}(10)}$$

其中：
$$E^{(i)}=f(x^{(i)})?y^{(i)}\text{\hspace{1em}(11)}$$

令：
$$\eta =2K_{ij}?K_{ii}?K_{jj}\text{\hspace{1em}(12)}$$

式 (10) 兩邊除以 $\eta$ 就得 ${\alpha }^{(j)}$ 的更新式：
$$a^{(jnew)}=a^{(jold)}?\frac{y^{(i)}(E^{(i)}?E^{(j)})}{\eta }\text{\hspace{1em}(13)}$$

但是，更新還要考慮上下界截?cái)?#xff1a;
$$a^{(jnewclipped)}=?\begin{array}{l}H,if{a}^{(jnew)}\ge H\\ a^{(jnew)},ifL<a^{(jnew)}<H\\ L,if{a}^{(jnew)}\le L\end{array}\text{\hspace{1em}(14)}$$

從而得到 ${\alpha }^{(i)}$ 的更新：
$$a^{(inew)}=a^{(iold)}+y^{(i)}{y}^{(j)}(a^{(jold)}?a^{(jnewclipped)})\text{\hspace{1em}(15)}$$

令：
$$b_1=b^{old}?E^{(i)}?y^{(i)}{K}_{ii}(a^{(inew)}?a^{(iold)})?y^{(j)}{K}_{ij}(a^{(jnewclipped)}?a^{(jold)})$$$$b_2=b^{old}?E^{(j)}?y^{(i)}{K}_{ij}(a^{(inew)}?a^{(iold)})?y^{(j)}{K}_{jj}(a^{(jnewclipped)}?a^{(jold)})\text{\hspace{1em}(16)}$$

則 $b$ 的更新為：
$$b^{(new)}=?\begin{array}{l}{b}_1,if0<a^{(inew)}<C\\ b_2,if0<a^{(jnewclipped)}<C\\ \frac{b_1+b_2}{2},otherwise\end{array}\text{\hspace{1em}(14)}$$

啟發(fā)式選擇

根據(jù) Osuna 提出的理論，如果兩個(gè)拉格朗日乘子其中之一違背了 KKT 條件，此時(shí)，每一次乘子對(duì)的選擇，都能使得優(yōu)化目標(biāo)函數(shù)減小。

• 若 ${\alpha }^{(i)}=0$ ，可知樣本 $x^{(i)}$ 不會(huì)對(duì)模型 $f(x)$ 產(chǎn)生影響。
• 若 ${\alpha }^{(i)}=C$ ，樣本 $x^{(i)}$ 不會(huì)是支持向量。
• 若 $0<{\alpha }^{(i)}<C$ ，則 ${\alpha }^{(i)}$ 沒有落在邊界上，當(dāng)下式滿足時(shí)， ${\alpha }^{(i)}$ 會(huì)違反 KKT 條件：
  $${\alpha }^{(i)}<Cand{y}^{(i)}f(x^{(i)})?1<0$$$${\alpha }^{(i)}>0and{y}^{(i)}f(x^{(i)})?1>0\text{\hspace{1em}(18)}$$

通常，式 (18) 過于嚴(yán)苛，因此考慮設(shè)置一個(gè)容忍區(qū)間 $[?\tau ,\tau ]$ ，并考慮令:
$$R^{(i)}=y^{(i)}{E}^{(i)}=y^{(i)}(f(x^{(i)})?y^{(i)})=y^{(i)}f(x^{(i)})?1\text{\hspace{1em}(19)}$$

可以將違反 KKT 條件的表達(dá)式寫為：
$${\alpha }^{(i)}<Cand{R}^{(i)}<?\tau$$$${\alpha }^{(i)}>0and{R}^{(i)}>\tau \text{\hspace{1em}(20)}$$

SMO 以編程的眼光，將啟發(fā)式選擇 $({\alpha }^{(i)},{\alpha }^{(j)})$ 描述為了兩層循環(huán)：

• 外層循環(huán)：外層循環(huán)中，如果當(dāng)前沒有 $alpha$ 對(duì) 的變化，意味著所有 $alph{a}^{(i)}$ 都遵從了 KKT 條件，需要在整個(gè)樣本集進(jìn)行迭代；否則，只需要選擇在處在邊界內(nèi)（即 $0<{\alpha }^{(i)}<C$ ）、并且違反了 KKT 條件（即滿足了式 (20) ）的 ${\alpha }^{(i)}$ 。
• 內(nèi)層循環(huán)：選出使得 $|E^{(i)}?E^{(j)}|$ 達(dá)到最大的 $alph{a}^{(j)}$ 。

算法流程

綜上，我們可以概括出 SMO 的算法流程：

在整個(gè)訓(xùn)練集或者非邊界樣本中選擇違反了 KKT 條件的 ${\alpha }^{(i)}$ 。

在剩下的 $\alpha$ 中，選擇 $|E^{(i)}?E^{(j)}|$ 達(dá)到最大的 $alph{a}^{(j)}$ 。

重復(fù)以上過程直到達(dá)到收斂精度或最大迭代次數(shù)。

參考資料

• Platt, John (1998), Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
• Wiki-SMO
• 支持向量機(jī)通俗導(dǎo)論（理解 SVM 的三層境界）
• 《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》
• 《機(jī)器學(xué)習(xí)》
• Sequential Minimal Optimization for SVM

總結(jié)

以上是生活随笔為你收集整理的5.6 SMO-机器学习笔记-斯坦福吴恩达教授的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。