支持向量機：Numerical Optimization

by pluskid, on 2010-09-15, in Machine Learning???? 15 comments

本文是“支持向量機系列”的第五篇，參見本系列的其他文章。

作為支持向量機系列的基本篇的最后一篇文章，我在這里打算簡單地介紹一下用于優化 dual 問題的 Sequential Minimal Optimization (SMO) 方法。確確實實只是簡單介紹一下，原因主要有兩個：第一這類優化算法，特別是牽涉到實現細節的時候，干巴巴地講算法不太好玩，有時候講出來每個人實現得結果還不一樣，提一下方法，再結合實際的實現代碼的話，應該會更加明了，而且也能看出理論和實踐之間的差別；另外（其實這個是主要原因）我自己對這一塊也確實不太懂。

先回憶一下我們之前得出的要求解的 dual 問題：

maxαs.t.,∑i=1nαi–12∑i,j=1nαiαjyiyjκ(xi,xj)0≤αi≤C,i=1,…,n∑i=1nαiyi=0

對于變量 α 來說，這是一個 quadratic 函數。通常對于優化問題，我們沒有辦法的時候就會想到最笨的辦法——Gradient Descent ，也就是梯度下降。注意我們這里的問題是要求最大值，只要在前面加上一個負號就可以轉化為求最小值，所以 Gradient Descent 和 Gradient Ascend 并沒有什么本質的區別，其基本思想直觀上來說就是：梯度是函數值增幅最大的方向，因此只要沿著梯度的反方向走，就能使得函數值減小得越大，從而期望迅速達到最小值。當然普通的 Gradient Descent 并不能保證達到最小值，因為很有可能陷入一個局部極小值。不過對于 quadratic 問題，極值只有一個，所以是沒有局部極值的問題。

另外還有一種叫做 Coordinate Descend 的變種，它每次只選擇一個維度，例如 α=(α1,…,αn) ，它每次選取 αi 為變量，而將 α1,…,αi?1,αi+1,…,αn 都看成是常量，從而原始的問題在這一步變成一個一元函數，然后針對這個一元函數求最小值，如此反復輪換不同的維度進行迭代。Coordinate Descend 的主要用處在于那些原本很復雜，但是如果只限制在一維的情況下則變得很簡單甚至可以直接求極值的情況，例如我們這里的問題，暫且不管約束條件，如果只看目標函數的話，當 α 只有一個分量是變量的時候，這就是一個普通的一元二次函數的極值問題，初中生也會做，帶入公式即可。

然而這里還有一個問題就是約束條件的存在，其實如果沒有約束條件的話，本身就是一個多元的 quadratic 問題，也是很好求解的。但是有了約束條件，結果讓 Coordinate Descend 變得很尷尬了：比如我們假設 α1 是變量，而 α2,…,αn 是固定值的話，那么其實沒有什么好優化的了，直接根據第二個約束條件 ∑ni=1αiyi=0 ，α1 的值立即就可以定下來——事實上，迭代每個坐標維度，最后發現優化根本進行不下去，因為迭代了一輪之后會發現根本沒有任何進展，一切都停留在初始值。

所以 Sequential Minimal Optimization (SMO) 一次選取了兩個坐標維度來進行優化。例如（不失一般性），我們假設現在選取 α1 和 α2 為變量，其余為常量，則根據約束條件我們有：

∑i=1nαiyi=0?α2=1y2(∑i=3nαiyi?α1y1)?y2(K?α1y1)

其中那個從 3 到 n 的作和由于都是常量，我們統一記作 K ，然后由于 y∈{?1,+1} ，所以 y2 和 1/y2 是完全一樣的，所以可以拿到分子上來。將這個式子帶入原來的目標函數中，可以消去 α2 ，從而變成一個一元二次函數，具體展開的形式我就不寫了，總之現在變成了一個非常簡單的問題：帶區間約束的一元二次函數極值問題——這個也是初中就學過求解方法的。唯一需要注意一點的就是這里的約束條件，一個就是 α1 本身需要滿足 0≤α1≤C ，然后由于 α2 也要滿足同樣的約束，即：

0≤y2(K?α1y1)≤C

也可以得到 α1 的一個可行區間，同 [0,C] 交集即可得到最終的可行區間。這個問題可以從圖中得到一個直觀的感覺。原本關于 α1 和 α2 的區間限制構成途中綠色的的方塊，而另一個約束條件 y1α1+y2α2=K 實際上表示一條直線，兩個集合的交集即是途中紅顏色的線段，投影到 α1 軸上所對應的區間即是 α1 的取值范圍，在這個區間內求二次函數的最大值即可完成 SMO 的一步迭代。

同 Coordinate Descent 一樣，SMO 也會選取不同的兩個 coordinate 維度進行優化，可以看出由于每一個迭代步驟實際上是一個可以直接求解的一元二次函數極值問題，所以求解非常高效。此外，SMO 也并不是依次或者隨機地選取兩個坐標維度，而是有一些啟發式的策略來選取最優的兩個坐標維度，具體的選取方法（和其他的一些細節），可以參見 John C. Platt 的那篇論文 Fast Training of Support Vector Machines Using Sequential Minimal Optimization 。關于 SMO ，我就不再多說了。如果你對研究實際的代碼比較感興趣，可以去看 LibSVM 的實現，當然，它那個也許已經不是原來版本的 SMO 了，因為本來 SVM 的優化就是一個有許多研究工作的領域，在那些主要的優化方法之上，也有各種改進的辦法或者全新的算法提出來。

除了 LibSVM 之外，另外一個流行的實現 SVM^light 似乎是用了另一種優化方法，具體可以參考一下它相關的論文 Making large-Scale SVM Learning Practical 。

此外，雖然我們從 dual 問題的推導中得出了許多 SVM 的優良性質，但是 SVM 的數值優化（即使是非線性的版本）其實并不一定需要轉化為 dual 問題來完成的，具體做法我并不清楚，不過這方面的文章也不少，比如 2007 年 Neural Computation 的一篇 Training a support vector machine in the primal 。如果感興趣可以參考一下

總結

以上是生活随笔為你收集整理的支持向量机：Numerical Optimization的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。