在上一次的介紹中，我們稍微了解到了關(guān)于support vector machine 的一些入門知識。今天，我們將真正進入支持向量機的算法之中，大體的框架如下：

1、最大間隔分類器

2、線性可分的情況（詳細(xì))

3、原始問題到對偶問題的轉(zhuǎn)化

4、序列最小最優(yōu)化算法

1、最大間隔分類器

函數(shù)間隔和幾何間隔相差一個∥w∥ 的縮放因子（感覺忘記的可以看一下上一篇文章）。按照前面的分析，對一個數(shù)據(jù)點進行分類，當(dāng)它的間隔越大的候，分類正確的把握越大。對于一個包含n 個點的數(shù)據(jù)集，我們可以很自然地定義它的間隔為所有這n 個點的間隔中最小的那個。于是，為了使得分類的把握盡大，我們希望所選擇的超平面能夠最大化這個間隔值。

????????簡而言之：

1. 函數(shù)間隔明顯是不太適合用來最大化的一個量，因為在超平面固定以后，我們可以等比例地縮放w的長度和b 的值，這樣可以使得f(x) = wTx+b 的值任意大，亦即函數(shù)間隔^γ 可以在超平面保持不變的情況下被取得任意大。

2. 而幾何間隔則沒有這個問題，因為除上了這個分母，所以縮放w 和b 的時候的值是不會改變的，它只隨著超平面的變動而變動，因此，這是更加合適的一個間隔。

最大間隔分類面的公式為：

通過最大化間隔，我們使得該分類器對數(shù)據(jù)進行分類時具有了最大的把握。但，這個最大分類間隔器到底是用來干嘛的呢？很簡單，支持向量機通過使用最大分類間隔來設(shè)計決策最優(yōu)分類超平面，而為何是最大間隔，卻不是最小間隔呢？因為最大間隔能獲得最大穩(wěn)定性與區(qū)分的確信度，從而得到良好的推廣能力（超平面之間的距離越大，分離器的推廣能力越好，也就是預(yù)測精度越高，不過對于訓(xùn)練數(shù)據(jù)的誤差不一定是最小的）。

2、原始問題到對偶問題

????????回憶一下之前得到的優(yōu)化目標(biāo)

max 1/∥w∥

s.t. yi(wTxi + b) ≥ 1, i = 1, 2, · · · , n

由于求1/∥w∥的最大值相當(dāng)于求1/2*∥w∥^2 的最小值，所以上述問題等價于（w 由分母變成分子，從而也有原來的“最大化”問題變?yōu)椤白钚』眴栴}，很明顯，兩者問題等價）

min 1/2*∥w∥^2?

s.t. yi(wTxi + b) ≥ 1, i = 1, 2, · · · , n

到這個形式以后，就可以很明顯地看出來，它是一個凸優(yōu)化問題，或者更具體地說，它是一個二次優(yōu)化問題——目標(biāo)函數(shù)是二次的，約束條件是線性的。這個問題可以用任何現(xiàn)成的QP Quadratic Programming 的優(yōu)化包進行求解。雖然這個問題確實是一個標(biāo)準(zhǔn)的QP 問題，但是它也有它的特殊結(jié)構(gòu)，通過

Lagrange 對偶變換到對偶變量Dual Variable 的優(yōu)化問題之后，可以找到一種更加有效的方法來進行求解，而且通常情況下這種方法比直接使用通用的QP 優(yōu)化包進行優(yōu)化要高效得多。也就說，除了用解決QP 問題的常規(guī)方法之外，還可以應(yīng)用Lagrange 對偶性，通過求解對偶問題得到最優(yōu)解，這就是線性可分條件下支持向量機的對偶算法，這樣做的優(yōu)點在于：一者對偶問題往往更容易解；二者可以自然的引入核函數(shù)，進而推廣到非線性分類問題。

接下來，你將看到“對偶變量的優(yōu)化問題”等類似的關(guān)鍵詞頻繁出現(xiàn)，便是解決此凸優(yōu)化問題的第二種更為高效的解——對偶變量的優(yōu)化求解。至于上述提到，關(guān)于什么是Lagrange 對偶性？簡單地來說，通過給每一個約束條件加上一個Lagrange 乘子，即引入Lagrange 對偶變量，如此我們便可以通過Lagrange 函數(shù)將約束條件融和到目標(biāo)函數(shù)里去（也就是說把條件融合到一個函數(shù)里頭，現(xiàn)在只用一個函數(shù)表達(dá)式便能清楚的表達(dá)出我們的問題）。

L(w, b,) =1/2*∥w∥^2 ?Σαi (yi(wTxi + b) ? 1)?

然后我們令θ(w) = maxL(w, b,a)

容易驗證，當(dāng)某個約束條件不滿足時，例如yi(wTxi + b) < 1，那么我們顯然有θ(w) = +∞（只要令αi = +∞即可）。而當(dāng)所有約束條件都滿足時，則有

θ(w) = 1/2*∥w∥*2，亦即我們最初要最小化的量。因此，在要求約束條件得到滿足的情況下最小化1/2*∥w∥^2，實際上等價于直接最小化θ(w)（當(dāng)然，這里也有約束條件，就是αi ≥ 0, i = 1, 2, · · · , n，因為如果約束條件沒有得到滿足，θ(w) 會等于無窮大，自然不會是我們所要求的最小值。具體寫出來，我們現(xiàn)在的目標(biāo)函數(shù)變成了.

所謂的“滿足某些條件”就是要先滿足Slater 條件，進而就滿足KKT 條件。理由如下3 點所述（觀點來自frestyle）：

1. 在凸優(yōu)化問題中，d? 和p? 相同的條件是Slater 條件，該條件保證鞍點 ? ? ? ?Saddle Point 存在。

2. 至于KKT 條件，首先原問題的最優(yōu)值可以通過求Lagrange 函數(shù)的鞍點（如果有的話）來得到，再者，KKT 條件里面進一步引入了更強的前提，也就是在滿足Slater 條件的同時（前面說了，Slater條件保證鞍點存在），f(·) 和gi(·) 都是可微的，這樣鞍點不僅存在，而且能通過對Lagrange 函數(shù)求導(dǎo)得到，

3. 所以KKT 條件是一個點是最優(yōu)解的條件，而不是d? = p? 的條件，當(dāng)然這個KKT 條件對后邊簡化對偶問題很關(guān)鍵。

那KKT 條件的表現(xiàn)形式是什么呢？據(jù)維基百科：KKT 條件的介紹，一般地，一個最優(yōu)化數(shù)學(xué)模型能夠表示成下列標(biāo)準(zhǔn)形式

這里的問題是滿足KKT 條件的（首先已經(jīng)滿足Slater 條件，再者f(·) 和gi(·) 也都是可微的，即L 對w 和b 都可導(dǎo)），因此現(xiàn)在我們便轉(zhuǎn)化為求解第二個問題。也就是說，現(xiàn)在，咱們的原問題通過滿足一定的條件，已經(jīng)轉(zhuǎn)化成了對偶問題。而求解這個對偶學(xué)習(xí)問題，分為3 個步驟，首先要讓L(w, b,) 關(guān)于

w 和b 最小化，然后求對 的極大，最后利用SMO 算法求解對偶因子。

第一步首先固定，要讓L 關(guān)于w 和b 最小化，我們分別對w 和b 求偏導(dǎo)數(shù)=0。

從上面的最后一個式子，我們可以看出，此時的Lagrange 函數(shù)只包含了一個變量，那就是αi，然后下文的第2 步，求出αi 了便能求出w 和b，由此可見，上文第1.2 節(jié)提出來的核心問題：分類函數(shù)f(x) = wTx + b也就可以輕而易舉的求出來了。由此看出，使用Lagrange 定理解凸最優(yōu)化問題可以使用一個對偶變量表示，轉(zhuǎn)換為對偶問題后，通常比原問題更容易處理，因為直接處理不等式約束是困難的，而對偶問題通過引入Lagrange 乘子（又稱為對偶變量）來解。

第二步求對 的極大，即是關(guān)于對偶變量 的優(yōu)化問題，從上面的式子得到

如前面所說，這個問題有更加高效的優(yōu)化算法，即我們常說的SMO 算法。

3、序列最小最優(yōu)化算法SMO

實際上，關(guān)于 的求解過程即是我們常說的SMO 算法，這里簡要介紹下。

要解決的是在參數(shù) 上求W 的最大值的問題，至于xi 和yi 都是已知數(shù)。其中C 是一個參數(shù)，用于控制目標(biāo)函數(shù)中兩項（“尋找間隔最大的超平面”和“保證數(shù)據(jù)點偏差量最小”）之間的權(quán)重。和上文最后的式子對比一下，可以看到唯一的區(qū)別就是現(xiàn)在對偶變量 多了一個上限C，關(guān)于C的由來在下一次的博文中會有。

4、線性不可分的情況

OK，為過渡到下節(jié)2.2節(jié)所介紹的核函數(shù)，讓我們再來看看上述推導(dǎo)過程中得到的一些有趣的形式。首先就是關(guān)于我們的超平面，對于一個數(shù)據(jù)點x 進行分類，實際上是通過把x 代入到f(x) = wTx + b 算出結(jié)果然后根據(jù)其正負(fù)號來進行類別劃分的。而前面的推導(dǎo)中我們得到

，因此分類函數(shù)為

這里的形式的有趣之處在于，對于新點x 的預(yù)測，只需要計算它與訓(xùn)練數(shù)據(jù)點的內(nèi)積即可（?·, ·? 表示向量內(nèi)積），這一點至關(guān)重要，是之后使用核函數(shù)進行非線性推廣的基本前提。此外，所謂“支持向量”也在這里顯示出來——事實上，所有非支持向量所對應(yīng)的系數(shù) 都是等于零的，因此對于新點的內(nèi)積計算實際上只要針對少量的“支持向量”而不是所有的訓(xùn)練數(shù)據(jù)即可。

為什么非支持向量對應(yīng)的 等于零呢？直觀上來理解的話，就是這些“后方”的點——正如我們之前分析過的一樣，對超平面是沒有影響的，由于分類完全有超平面決定，所以這些無關(guān)的點并不會參與分類問題的計算，因而也就不會產(chǎn)生任何影響了。

????????通過Lagrange 乘數(shù)法得到的優(yōu)化目標(biāo)：

注意到如果xi 是支持向量的話，(2.1.23)式中紅顏色的部分是等于0 的（因為支持向量的函數(shù)間隔等于1），而對于非支持向量來說，函數(shù)間隔會大于1，因此紅顏色部分是大于零的，而αi 又是非負(fù)的，為了滿足最大化，αi 必須等于0。這也就是這些非支持向量的點的局限性。從上述所有這些東西，便得到了一個最大間隔分類器，這就是一個簡單的支持向量機。當(dāng)然，到目前為止，我們的支持向量機還比較弱，只能處理線性可分的情況，不過，在得到了目標(biāo)函數(shù)的對偶形式之后，通過核函數(shù)推廣到非線性可分的情況就變成了一件非常容易的事情。