SVM的英文全稱是Support Vector Machines，我們叫它支持向量機。支持向量機是我們用于分類的一種算法。讓我們以一個小故事的形式，開啟我們的SVM之旅吧。

在很久以前的情人節(jié)，一位大俠要去救他的愛人，但天空中的魔鬼和他玩了一個游戲。

魔鬼在桌子上似乎有規(guī)律放了兩種顏色的球，說：”你用一根棍分開它們？要求：盡量在放更多球之后，仍然適用?！?/p>

?

?

?

?

于是大俠這樣放，干的不錯？

?

?

?

?

然后魔鬼，又在桌上放了更多的球，似乎有一個球站錯了陣營。顯然，大俠需要對棍做出調(diào)整。

?

?

?

?

SVM就是試圖把棍放在最佳位置，好讓在棍的兩邊有盡可能大的間隙。這個間隙就是球到棍的距離。

?

?

?

?

現(xiàn)在好了，即使魔鬼放了更多的球，棍仍然是一個好的分界線。

?

?

?

?

魔鬼看到大俠已經(jīng)學(xué)會了一個trick(方法、招式)，于是魔鬼給了大俠一個新的挑戰(zhàn)。

?

?

?

?

現(xiàn)在，大俠沒有棍可以很好幫他分開兩種球了，現(xiàn)在怎么辦呢？當(dāng)然像所有武俠片中一樣大俠桌子一拍，球飛到空中。然后，憑借大俠的輕功，大俠抓起一張紙，插到了兩種球的中間。

?

?

?

?

現(xiàn)在，從空中的魔鬼的角度看這些球，這些球看起來像是被一條曲線分開了。

?

?

?

?

再之后，無聊的大人們，把這些球叫做data，把棍子叫做classifier, 找到最大間隙的trick叫做optimization，拍桌子叫做kernelling, 那張紙叫做hyperplane。

?

概述一下：

當(dāng)一個分類問題，數(shù)據(jù)是線性可分的，也就是用一根棍就可以將兩種小球分開的時候，我們只要將棍的位置放在讓小球距離棍的距離最大化的位置即可，尋找這個最大間隔的過程，就叫做最優(yōu)化。但是，現(xiàn)實往往是很殘酷的，一般的數(shù)據(jù)是線性不可分的，也就是找不到一個棍將兩種小球很好的分類。這個時候，我們就需要像大俠一樣，將小球拍起，用一張紙代替小棍將小球進行分類。想要讓數(shù)據(jù)飛起，我們需要的東西就是核函數(shù)(kernel)，用于切分小球的紙，就是超平面。

也許這個時候，你還是似懂非懂，沒關(guān)系。根據(jù)剛才的描述，可以看出，問題是從線性可分延伸到線性不可分的。那么，我們就按照這個思路，進行原理性的剖析。

線性SVM

先看下線性可分的二分類問題。

?

?

?

?

上圖中的(a)是已有的數(shù)據(jù)，紅色和藍色分別代表兩個不同的類別。數(shù)據(jù)顯然是線性可分的，但是將兩類數(shù)據(jù)點分開的直線顯然不止一條。上圖的(b)和(c)分別給出了B、C兩種不同的分類方案，其中黑色實線為分界線，術(shù)語稱為“決策面”。每個決策面對應(yīng)了一個線性分類器。雖然從分類結(jié)果上看，分類器A和分類器B的效果是相同的。但是他們的性能是有差距的，看下圖：

?

?

?

?

在”決策面”不變的情況下，我又添加了一個紅點?？梢钥吹?#xff0c;分類器B依然能很好的分類結(jié)果，而分類器C則出現(xiàn)了分類錯誤。顯然分類器B的”決策面”放置的位置優(yōu)于分類器C的”決策面”放置的位置，SVM算法也是這么認(rèn)為的，它的依據(jù)就是分類器B的分類間隔比分類器C的分類間隔大。這里涉及到第一個SVM獨有的概念”分類間隔”。在保證決策面方向不變且不會出現(xiàn)錯分樣本的情況下移動決策面，會在原來的決策面兩側(cè)找到兩個極限位置（越過該位置就會產(chǎn)生錯分現(xiàn)象），如虛線所示。虛線的位置由決策面的方向和距離原決策面最近的幾個樣本的位置決定。而這兩條平行虛線正中間的分界線就是在保持當(dāng)前決策面方向不變的前提下的最優(yōu)決策面。兩條虛線之間的垂直距離就是這個最優(yōu)決策面對應(yīng)的分類間隔。顯然每一個可能把數(shù)據(jù)集正確分開的方向都有一個最優(yōu)決策面（有些方向無論如何移動決策面的位置也不可能將兩類樣本完全分開），而不同方向的最優(yōu)決策面的分類間隔通常是不同的，那個具有“最大間隔”的決策面就是SVM要尋找的最優(yōu)解。而這個真正的最優(yōu)解對應(yīng)的兩側(cè)虛線所穿過的樣本點，就是SVM中的支持樣本點，稱為”支持向量”。

1 數(shù)學(xué)建模

求解這個”決策面”的過程，就是最優(yōu)化。一個最優(yōu)化問題通常有兩個基本的因素：1）目標(biāo)函數(shù)，也就是你希望什么東西的什么指標(biāo)達到最好；2）優(yōu)化對象，你期望通過改變哪些因素來使你的目標(biāo)函數(shù)達到最優(yōu)。在線性SVM算法中，目標(biāo)函數(shù)顯然就是那個”分類間隔”，而優(yōu)化對象則是決策面。所以要對SVM問題進行數(shù)學(xué)建模，首先要對上述兩個對象（”分類間隔”和”決策面”）進行數(shù)學(xué)描述。按照一般的思維習(xí)慣，我們先描述決策面。

數(shù)學(xué)建模的時候，先在二維空間建模，然后再推廣到多維。

（1）”決策面”方程

我們都知道二維空間下一條直線的方式如下所示：

?

?

?

?

現(xiàn)在我們做個小小的改變，讓原來的x軸變成x1，y軸變成x2。

?

?

?

?

移項得：

?

?

?

?

將公式向量化得：

?

?

?

?

進一步向量化，用w列向量和x列向量和標(biāo)量γ進一步向量化：

?

?

?

?

其中，向量w和x分別為：

?

?

?

?

這里w1=a，w2=-1。我們都知道，最初的那個直線方程a和b的幾何意義，a表示直線的斜率，b表示截距，a決定了直線與x軸正方向的夾角，b決定了直線與y軸交點位置。那么向量化后的直線的w和r的幾何意義是什么呢？

現(xiàn)在假設(shè)：

?

?

?

?

可得：

?

?

?

?

在坐標(biāo)軸上畫出直線和向量w：

?

?

?

?

藍色的線代表向量w，紅色的先代表直線y。我們可以看到向量w和直線的關(guān)系為垂直關(guān)系。這說明了向量w也控制這直線的方向，只不過是與這個直線的方向是垂直的。標(biāo)量γ的作用也沒有變，依然決定了直線的截距。此時，我們稱w為直線的法向量。

二維空間的直線方程已經(jīng)推導(dǎo)完成，將其推廣到n為空間，就變成了超平面方程。(一個超平面，在二維空間的例子就是一個直線)但是它的公式?jīng)]變，依然是：

?

?

?

?

不同之處在于：

?

?

?

?

我們已經(jīng)順利推導(dǎo)出了”決策面”方程，它就是我們的超平面方程，之后，我們統(tǒng)稱其為超平面方程。

（2）”分類間隔”方程

現(xiàn)在，我們依然對于一個二維平面的簡單例子進行推導(dǎo)。

?

?

?

?

我們已經(jīng)知道間隔的大小實際上就是支持向量對應(yīng)的樣本點到?jīng)Q策面的距離的二倍。那么圖中的距離d我們怎么求？我們高中都學(xué)過，點到直線的距離距離公式如下：

?

?

?

?

公式中的直線方程為Ax0+By0+C=0，點P的坐標(biāo)為(x0,y0)。

現(xiàn)在，將直線方程擴展到多維，求得我們現(xiàn)在的超平面方程，對公式進行如下變形：

?

?

?

?

這個d就是”分類間隔”。其中||w||表示w的二范數(shù)，求所有元素的平方和，然后再開方。比如對于二維平面：

?

?

?

?

那么，

?

?

?

?

我們目的是為了找出一個分類效果好的超平面作為分類器。分類器的好壞的評定依據(jù)是分類間隔W=2d的大小，即分類間隔W越大，我們認(rèn)為這個超平面的分類效果越好。此時，求解超平面的問題就變成了求解分類間隔W最大化的為題。W的最大化也就是d最大化的。

（3）約束條件

看起來，我們已經(jīng)順利獲得了目標(biāo)函數(shù)的數(shù)學(xué)形式。但是為了求解w的最大值。我們不得不面對如下問題：

• 我們?nèi)绾闻袛喑矫媸欠駥颖军c正確分類？
• 我們知道相求距離d的最大值，我們首先需要找到支持向量上的點，怎么在眾多的點中選出支持向量上的點呢？

上述我們需要面對的問題就是約束條件，也就是說我們優(yōu)化的變量d的取值范圍受到了限制和約束。事實上約束條件一直是最優(yōu)化問題里最讓人頭疼的東西。但既然我們已經(jīng)知道了這些約束條件確實存在，就不得不用數(shù)學(xué)語言對他們進行描述。但SVM算法通過一些巧妙的小技巧，將這些約束條件融合到一個不等式里面。

這個二維平面上有兩種點，我們分別對它們進行標(biāo)記：

• 紅顏色的圓點標(biāo)記為1，我們?nèi)藶橐?guī)定其為正樣本；
• 藍顏色的五角星標(biāo)記為-1，我們?nèi)藶橐?guī)定其為負(fù)樣本。

對每個樣本點xi加上一個類別標(biāo)簽yi：

?

?

?

?

如果我們的超平面方程能夠完全正確地對上圖的樣本點進行分類，就會滿足下面的方程：

?

?

?

?

如果我們要求再高一點，假設(shè)決策面正好處于間隔區(qū)域的中軸線上，并且相應(yīng)的支持向量對應(yīng)的樣本點到?jīng)Q策面的距離為d，那么公式進一步寫成：

?

?

?

?

上述公式的解釋就是，對于所有分類標(biāo)簽為1的樣本點，它們到直線的距離都大于等于d(支持向量上的樣本點到超平面的距離)。對于所有分類標(biāo)簽為-1的樣本點，它們到直線的距離都小于等于d。公式兩邊都除以d，就可以得到：

?

?

?

?

其中，

?

?

?

?

因為||w||和d都是標(biāo)量。所上述公式的兩個矢量，依然描述一條直線的法向量和截距。

?

?

?

?

上述兩個公式，都是描述一條直線，數(shù)學(xué)模型代表的意義是一樣的?，F(xiàn)在，讓我們對wd和γd重新起個名字，就叫它們w和γ。因此，我們就可以說：”對于存在分類間隔的兩類樣本點，我們一定可以找到一些超平面面，使其對于所有的樣本點均滿足下面的條件：”

?

?

?

?

上述方程即給出了SVM最優(yōu)化問題的約束條件。這時候，可能有人會問了，為什么標(biāo)記為1和-1呢？因為這樣標(biāo)記方便我們將上述方程變成如下形式：

?

?

?

?

正是因為標(biāo)簽為1和-1，才方便我們將約束條件變成一個約束方程，從而方便我們的計算。

（4）線性SVM優(yōu)化問題基本描述

現(xiàn)在整合一下思路，我們已經(jīng)得到我們的目標(biāo)函數(shù)：

?

?

?

?

我們的優(yōu)化目標(biāo)是是d最大化。我們已經(jīng)說過，我們是用支持向量上的樣本點求解d的最大化的問題的。那么支持向量上的樣本點有什么特點呢？

?

?

?

?

你贊同這個觀點嗎？所有支持向量上的樣本點，都滿足如上公式。如果不贊同，請重看”分類間隔”方程推導(dǎo)過程。

現(xiàn)在我們就可以將我們的目標(biāo)函數(shù)進一步化簡：

?

?

?

?

因為，我們只關(guān)心支持向量上的點。隨后我們求解d的最大化問題變成了||w||的最小化問題。進而||w||的最小化問題等效于

?

?

?

?

為什么要做這樣的等效呢？這是為了在進行最優(yōu)化的過程中對目標(biāo)函數(shù)求導(dǎo)時比較方便，但這絕對不影響最優(yōu)化問題最后的求解。我們將最終的目標(biāo)函數(shù)和約束條件放在一起進行描述：

?

?

?

?

這里n是樣本點的總個數(shù)，縮寫s.t.表示”Subject to”，是”服從某某條件”的意思。上述公式描述的是一個典型的不等式約束條件下的二次型函數(shù)優(yōu)化問題，同時也是支持向量機的基本數(shù)學(xué)模型。

求解準(zhǔn)備

我們已經(jīng)得到支持向量機的基本數(shù)學(xué)模型，接下來的問題就是如何根據(jù)數(shù)學(xué)模型，求得我們想要的最優(yōu)解。在學(xué)習(xí)求解方法之前，我們得知道一點，想用我下面講述的求解方法有一個前提，就是我們的目標(biāo)函數(shù)必須是凸函數(shù)。理解凸函數(shù)，我們還要先明確另一個概念，凸集。在凸幾何中，凸集(convex set)是在)凸組合下閉合的放射空間的子集?？匆环鶊D可能更容易理解：

?

?

?

?

左右量圖都是一個集合。如果集合中任意2個元素連線上的點也在集合中，那么這個集合就是凸集。顯然，上圖中的左圖是一個凸集，上圖中的右圖是一個非凸集。

凸函數(shù)的定義也是如此，其幾何意義表示為函數(shù)任意兩點連線上的值大于對應(yīng)自變量處的函數(shù)值。若這里凸集C即某個區(qū)間L，那么，設(shè)函數(shù)f為定義在區(qū)間L上的函數(shù)，若對L上的任意兩點x1，x2和任意的實數(shù)λ，λ屬于(0,1)，總有：

?

?

?

?

則函數(shù)f稱為L上的凸函數(shù)，當(dāng)且僅當(dāng)其上鏡圖（在函數(shù)圖像上方的點集）為一個凸集。再看一幅圖，也許更容易理解：

?

?

?

?

像上圖這樣的函數(shù)，它整體就是一個非凸函數(shù)，我們無法獲得全局最優(yōu)解的，只能獲得局部最優(yōu)解。比如紅框內(nèi)的部分，如果單獨拿出來，它就是一個凸函數(shù)。對于我們的目標(biāo)函數(shù)：

?

?

?

?

很顯然，它是一個凸函數(shù)。所以，可以使用我接下來講述的方法求取最優(yōu)解。

通常我們需要求解的最優(yōu)化問題有如下幾類：

• 無約束優(yōu)化問題，可以寫為：

?

?

?

?

• 有等式約束的優(yōu)化問題，可以寫為：

?

?

?

?

• 有不等式約束的優(yōu)化問題，可以寫為：

?

?

?

?

對于第(a)類的優(yōu)化問題，嘗嘗使用的方法就是費馬大定理(Fermat)，即使用求取函數(shù)f(x)的導(dǎo)數(shù)，然后令其為零，可以求得候選最優(yōu)值，再在這些候選值中驗證；如果是凸函數(shù)，可以保證是最優(yōu)解。這也就是我們高中經(jīng)常使用的求函數(shù)的極值的方法。

對于第(b)類的優(yōu)化問題，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) ，即把等式約束h_i(x)用一個系數(shù)與f(x)寫為一個式子，稱為拉格朗日函數(shù)，而系數(shù)稱為拉格朗日乘子。通過拉格朗日函數(shù)對各個變量求導(dǎo)，令其為零，可以求得候選值集合，然后驗證求得最優(yōu)值。

對于第(c)類的優(yōu)化問題，常常使用的方法就是KKT條件。同樣地，我們把所有的等式、不等式約束與f(x)寫為一個式子，也叫拉格朗日函數(shù)，系數(shù)也稱拉格朗日乘子，通過一些條件，可以求出最優(yōu)值的必要條件，這個條件稱為KKT條件。

必要條件和充要條件如果不理解，可以看下面這句話：

• A的必要條件就是A可以推出的結(jié)論
• A的充分條件就是可以推出A的前提

了解到這些，現(xiàn)在讓我們再看一下我們的最優(yōu)化問題：

?

?

?

?

現(xiàn)在，我們的這個對優(yōu)化問題屬于哪一類？很顯然，它屬于第(c)類問題。因為，在學(xué)習(xí)求解最優(yōu)化問題之前，我們還要學(xué)習(xí)兩個東西：拉格朗日函數(shù)和KKT條件。

拉格朗日函數(shù)

首先，我們先要從宏觀的視野上了解一下拉格朗日對偶問題出現(xiàn)的原因和背景。

我們知道我們要求解的是最小化問題，所以一個直觀的想法是如果我能夠構(gòu)造一個函數(shù)，使得該函數(shù)在可行解區(qū)域內(nèi)與原目標(biāo)函數(shù)完全一致，而在可行解區(qū)域外的數(shù)值非常大，甚至是無窮大，那么這個沒有約束條件的新目標(biāo)函數(shù)的優(yōu)化問題就與原來有約束條件的原始目標(biāo)函數(shù)的優(yōu)化問題是等價的問題。這就是使用拉格朗日方程的目的，它將約束條件放到目標(biāo)函數(shù)中，從而將有約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題。

隨后，人們又發(fā)現(xiàn)，使用拉格朗日獲得的函數(shù)，使用求導(dǎo)的方法求解依然困難。進而，需要對問題再進行一次轉(zhuǎn)換，即使用一個數(shù)學(xué)技巧：拉格朗日對偶。

所以，顯而易見的是，我們在拉格朗日優(yōu)化我們的問題這個道路上，需要進行下面二個步驟：

• 將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)
• 使用拉格朗日對偶性，將不易求解的優(yōu)化問題轉(zhuǎn)化為易求解的優(yōu)化

下面，進行第一步：將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)

公式變形如下：

?

?

?

?

其中αi是拉格朗日乘子，αi大于等于0，是我們構(gòu)造新目標(biāo)函數(shù)時引入的系數(shù)變量(我們自己設(shè)置)。現(xiàn)在我們令：

?

?

?

?

當(dāng)樣本點不滿足約束條件時，即在可行解區(qū)域外：

?

?

?

?

此時，我們將αi設(shè)置為正無窮，此時θ(w)顯然也是正無窮。

當(dāng)樣本點滿足約束條件時，即在可行解區(qū)域內(nèi)：

?

?

?

?

此時，顯然θ(w)為原目標(biāo)函數(shù)本身。我們將上述兩種情況結(jié)合一下，就得到了新的目標(biāo)函數(shù)：

?

?

?

?

此時，再看我們的初衷，就是為了建立一個在可行解區(qū)域內(nèi)與原目標(biāo)函數(shù)相同，在可行解區(qū)域外函數(shù)值趨近于無窮大的新函數(shù)，現(xiàn)在我們做到了。

現(xiàn)在，我們的問題變成了求新目標(biāo)函數(shù)的最小值，即：

?

?

?

?

這里用p*表示這個問題的最優(yōu)值，且和最初的問題是等價的。

接下來，我們進行第二步：將不易求解的優(yōu)化問題轉(zhuǎn)化為易求解的優(yōu)化

我們看一下我們的新目標(biāo)函數(shù)，先求最大值，再求最小值。這樣的話，我們首先就要面對帶有需要求解的參數(shù)w和b的方程，而αi又是不等式約束，這個求解過程不好做。所以，我們需要使用拉格朗日函數(shù)對偶性，將最小和最大的位置交換一下，這樣就變成了：

?

?

?

?

交換以后的新問題是原始問題的對偶問題，這個新問題的最優(yōu)值用d*來表示。而且d*<=p*。我們關(guān)心的是d=p的時候，這才是我們要的解。需要什么條件才能讓d=p呢？

• 首先必須滿足這個優(yōu)化問題是凸優(yōu)化問題。
• 其次，需要滿足KKT條件。

凸優(yōu)化問題的定義是：求取最小值的目標(biāo)函數(shù)為凸函數(shù)的一類優(yōu)化問題。目標(biāo)函數(shù)是凸函數(shù)我們已經(jīng)知道，這個優(yōu)化問題又是求最小值。所以我們的最優(yōu)化問題就是凸優(yōu)化問題。

接下里，就是探討是否滿足KKT條件了。

（7）KKT條件

我們已經(jīng)使用拉格朗日函數(shù)對我們的目標(biāo)函數(shù)進行了處理，生成了一個新的目標(biāo)函數(shù)。通過一些條件，可以求出最優(yōu)值的必要條件，這個條件就是接下來要說的KKT條件。一個最優(yōu)化模型能夠表示成下列標(biāo)準(zhǔn)形式：

?

?

?

?

KKT條件的全稱是Karush-Kuhn-Tucker條件，KKT條件是說最優(yōu)值條件必須滿足以下條件：

• 條件一：經(jīng)過拉格朗日函數(shù)處理之后的新目標(biāo)函數(shù)L(w,b,α)對α求導(dǎo)為零：
• 條件二：h(x) = 0；
• 條件三：α*g(x) = 0；

對于我們的優(yōu)化問題：

?

?

?

?

顯然，條件二已經(jīng)滿足了。另外兩個條件為啥也滿足呢？

這里原諒我省略一系列證明步驟，感興趣的可以移步這里：點擊打開鏈接

這里已經(jīng)給出了很好的解釋。現(xiàn)在，凸優(yōu)化問題和KKT都滿足了，問題轉(zhuǎn)換成了對偶問題。而求解這個對偶學(xué)習(xí)問題，可以分為三個步驟：首先要讓L(w,b,α)關(guān)于w和b最小化，然后求對α的極大，最后利用SMO算法求解對偶問題中的拉格朗日乘子。

對偶問題求解

第一步：

根據(jù)上述推導(dǎo)已知：

?

?

?

?

首先固定α，要讓L(w,b,α)關(guān)于w和b最小化，我們分別對w和b偏導(dǎo)數(shù)，令其等于0，即：

?

?

?

?

將上述結(jié)果帶回L(w,b,α)得到：

?

?

?

?

從上面的最后一個式子，我們可以看出，此時的L(w,b,α)函數(shù)只含有一個變量，即αi。

第二步：

現(xiàn)在內(nèi)側(cè)的最小值求解完成，我們求解外側(cè)的最大值，從上面的式子得到

?

?

?

?

現(xiàn)在我們的優(yōu)化問題變成了如上的形式。對于這個問題，我們有更高效的優(yōu)化算法，即序列最小優(yōu)化（SMO）算法。我們通過這個優(yōu)化算法能得到α，再根據(jù)α，我們就可以求解出w和b，進而求得我們最初的目的：找到超平面，即”決策平面”。

總結(jié)一句話：我們?yōu)樯妒钩龀阅痰膭艃哼M行推導(dǎo)？因為我們要將最初的原始問題，轉(zhuǎn)換到可以使用SMO算法求解的問題，這是一種最流行的求解方法。為啥用這種求解方法？因為它牛逼啊！

?

2 SMO算法

現(xiàn)在，我們已經(jīng)得到了可以用SMO算法求解的目標(biāo)函數(shù)，但是對于怎么編程實現(xiàn)SMO算法還是感覺無從下手。那么現(xiàn)在就聊聊如何使用SMO算法進行求解。

（1）Platt的SMO算法

1996年，John Platt發(fā)布了一個稱為SMO的強大算法，用于訓(xùn)練SVM。SM表示序列最小化(Sequential Minimal Optimizaion)。Platt的SMO算法是將大優(yōu)化問題分解為多個小優(yōu)化問題來求解的。這些小優(yōu)化問題往往很容易求解，并且對它們進行順序求解的結(jié)果與將它們作為整體來求解的結(jié)果完全一致的。在結(jié)果完全相同的同時，SMO算法的求解時間短很多。

SMO算法的目標(biāo)是求出一系列alpha和b，一旦求出了這些alpha，就很容易計算出權(quán)重向量w并得到分隔超平面。

SMO算法的工作原理是：每次循環(huán)中選擇兩個alpha進行優(yōu)化處理。一旦找到了一對合適的alpha，那么就增大其中一個同時減小另一個。這里所謂的”合適”就是指兩個alpha必須符合以下兩個條件，條件之一就是兩個alpha必須要在間隔邊界之外，而且第二個條件則是這兩個alpha還沒有進進行過區(qū)間化處理或者不在邊界上。

（2）SMO算法的解法

先來定義特征到結(jié)果的輸出函數(shù)為：

?

?

?

?

接著，我們回憶一下原始優(yōu)化問題，如下：

?

?

?

?

求導(dǎo)得：

?

?

?

?

將上述公式帶入輸出函數(shù)中：

?

?

?

?

與此同時，拉格朗日對偶后得到最終的目標(biāo)化函數(shù)：

?

?

?

?

將目標(biāo)函數(shù)變形，在前面增加一個符號，將最大值問題轉(zhuǎn)換成最小值問題：

?

?

?

?

實際上，對于上述目標(biāo)函數(shù)，是存在一個假設(shè)的，即數(shù)據(jù)100%線性可分。但是，目前為止，我們知道幾乎所有數(shù)據(jù)都不那么”干凈”。這時我們就可以通過引入所謂的松弛變量(slack variable)，來允許有些數(shù)據(jù)點可以處于超平面的錯誤的一側(cè)，為此要引入“軟間隔”(soft margin)的概念。

具體來說，前面介紹的支持向量機形式是要求所有樣本都滿足約束，即所有樣本都必須劃分正確，這稱為“硬間隔”（hard margin），而軟間隔則是允許某些樣本不滿足約束

（0）

當(dāng)然，在最大化間隔的同時，不滿足約束條件的樣本應(yīng)該盡可能少，于是優(yōu)化目標(biāo)可以寫為：

（1）

其中C>0是一個常數(shù)，ρ是0/1損失函數(shù)，即

（2）

顯然，當(dāng)C為無窮大時，上面的損失函數(shù)迫使所有樣本均滿足約束條件，此時就等價于硬間隔的情況；

當(dāng)C取有限值時，（1）式允許一些樣本不滿足約束。由于（2）式非凸，非連續(xù)，數(shù)學(xué)性質(zhì)不太好，于是人們通常用一些其他的函數(shù)來代替這個損失函數(shù)，稱為"替代損失"（surrogate loss）,具體函數(shù)可參見西瓜書P130

引入松弛變量(slack variables)

可將（1）式重寫為：

(3)---

(3)式就是常見的軟間隔支持向量機，

顯然，（3）中每個樣本都有一個對應(yīng)的松弛變量，用以表征該樣本不滿足約束（0）的程度，但是，與硬間隔時類似，這仍然是一個二次規(guī)劃問題，于是類似

的獲取方法，通過拉格朗日乘子法可得到：

（5）

其中

?

令（5）式對ω，β，ξi的偏導(dǎo)數(shù)為0可得：

（7）

將上面3個式子帶入（5）中得到（3）式的對偶問題：

?

與硬間隔對比可以發(fā)現(xiàn)，我們的優(yōu)化目標(biāo)仍然不變，只是我們的約束條件有所改變：

?

?

?

?

根據(jù)KKT條件：

于是，對于任意訓(xùn)練樣本，總有αi=0或者yif(xi)=1-ξi.? ? 若αi=0,則該樣本不會對f(x)有任何影響；若αi>0,則必有yif(xi)=1-ξi，即該樣本是支持向量。

并且，由(7)知道，若αi<C,則μi>0,進而有ξi=0,所以此時有：yf(x)=1,即該樣本恰好在最大間隔邊界上；若αi=C，則有μi=0,此時若ξi<=1則該樣本落在最大間隔內(nèi)部；若ξi>1則該樣本被錯誤分類。由此可以看出，軟間隔支持向量機的最終模型僅與支持向量有關(guān)。

?

正如下面這個式子所展示的：

?

?

• 對于第1種情況，表明αi是正常分類，在邊界內(nèi)部；
• 對于第2種情況，表明αi是支持向量，在邊界上；
• 對于第3種情況，表明αi是在兩條邊界之間。

而最優(yōu)解需要滿足KKT條件，即上述3個條件都得滿足，以下幾種情況出現(xiàn)將會不滿足：

?

?

?

?

也就是說，如果存在不能滿足KKT條件的αi，那么需要更新這些αi，這是第一個約束條件。此外，更新的同時還要受到第二個約束條件的限制，即：

?

?

?

?

因為這個條件，我們同時更新兩個α值，因為只有成對更新，才能保證更新之后的值仍然滿足和為0的約束，假設(shè)我們選擇的兩個乘子為α1和α2：

?

?

?

?

其中， ksi為常數(shù)。因為兩個因子不好同時求解，所以可以先求第二個乘子α2的解（α2 new），得到α2的解（α2 new）之后，再用α2的解（α2 new）表示α1的解（α1 new ）。為了求解α2 new ，得先確定α2 new的取值范圍。假設(shè)它的上下邊界分別為H和L，那么有：

?

?

?

?

接下來，綜合下面兩個條件：

?

?

?

?

當(dāng)y1不等于y2時，即一個為正1，一個為負(fù)1的時候，可以得到：

?

?

?

?

所以有：

?

?

?

?

此時，取值范圍如下圖所示：

?

?

?

?

當(dāng)y1等于y2時，即兩個都為正1或者都為負(fù)1，可以得到：

?

?

?

?

所以有：

?

?

?

?

此時，取值范圍如下圖所示：

?

?

?

?

如此，根據(jù)y1和y2異號或同號，可以得出α2 new的上下界分別為：

?

?

?

?

這個界限就是編程的時候需要用到的。已經(jīng)確定了邊界，接下來，就是推導(dǎo)迭代式，用于更新 α值。

我們已經(jīng)知道，更新α的邊界，接下來就是討論如何更新α值。我們依然假設(shè)選擇的兩個乘子為α1和α2。固定這兩個乘子，進行推導(dǎo)。于是目標(biāo)函數(shù)變成了：

?

?

?
點擊放大圖片

?

?

為了描述方便，我們定義如下符號：

?

?

?

?

最終目標(biāo)函數(shù)變?yōu)?#xff1a;

?

?

?

?

我們不關(guān)心constant的部分，因為對于α1和α2來說，它們都是常數(shù)項，在求導(dǎo)的時候，直接變?yōu)?。對于這個目標(biāo)函數(shù)，如果對其求導(dǎo)，還有個未知數(shù)α1，所以要推導(dǎo)出α1和α2的關(guān)系，然后用α2代替α1，這樣目標(biāo)函數(shù)就剩一個未知數(shù)了，我們就可以求導(dǎo)了，推導(dǎo)出迭代公式。所以現(xiàn)在繼續(xù)推導(dǎo)α1和α2的關(guān)系。注意第一個約束條件：

?

?

?

?

我們在求α1和α2的時候，可以將α3,α4,…,αn和y3,y4,…,yn看作常數(shù)項。因此有：

?

?

?

?

我們不必關(guān)心常數(shù)B的大小，現(xiàn)在將上述等式兩邊同時乘以y1，得到(y1y1=1)：

?

?

?

?

其中γ為常數(shù)By1，我們不關(guān)心這個值，s=y1y2。接下來，我們將得到的α1帶入W(α2)公式得：

?

?

?

?

這樣目標(biāo)函數(shù)中就只剩下α2了，我們對其求偏導(dǎo)（注意：s=y1y2，所以s的平方為1，y1的平方和y2的平方均為1）：

?

?

?

?

繼續(xù)化簡，將s=y1y2帶入方程。

?

?

?

?

我們令：

?

?

?

?

Ei為誤差項，η為學(xué)習(xí)速率。

再根據(jù)我們已知的公式：

?

?

?

?

將α2 new繼續(xù)化簡得：

?

?

?

?

這樣，我們就得到了最終需要的迭代公式。這個是沒有經(jīng)過剪輯的解，需要考慮約束：

?

?

?

?

根據(jù)之前推導(dǎo)的α取值范圍，我們得到最終的解析解為：

?

?

?

?

又因為：

?

?

?

?

消去γ得：

?

?

?

?

這樣，我們就知道了怎樣計算α1和α2了，也就是如何對選擇的α進行更新。

當(dāng)我們更新了α1和α2之后，需要重新計算閾值b，因為b關(guān)系到了我們f(x)的計算，也就關(guān)系到了誤差Ei的計算。

我們要根據(jù)α的取值范圍，去更正b的值，使間隔最大化。當(dāng)α1 new在0和C之間的時候，根據(jù)KKT條件可知，這個點是支持向量上的點。因此，滿足下列公式：

?

?

?

?

公式兩邊同時乘以y1得(y1y1=1)：

?

?

?

?

因為我們是根據(jù)α1和α2的值去更新b，所以單獨提出i=1和i=2的時候，整理可得：

?

?

?

?

其中前兩項為：

?

?

?

?

將上述兩個公式，整理得：

?

?

?

?

同理可得b2 new為：

?

?

?

?

當(dāng)b1和b2都有效的時候，它們是相等的，即：

?

?

?

?

當(dāng)兩個乘子都在邊界上，則b閾值和KKT條件一致。當(dāng)不滿足的時候，SMO算法選擇他們的中點作為新的閾值：

?

?

?

?

最后，更新所有的α和b，這樣模型就出來了，從而即可求出我們的分類函數(shù)。

現(xiàn)在，讓我們梳理下SMO算法的步驟：

• 步驟1：計算誤差：?

  ?

  ?

?

• 步驟2：計算上下界L和H：?

  ?

  ?

?

• 步驟3：計算η：?

  ?

  ?

?

• 步驟4：更新αj：?

  ?

  ?

?

• 步驟5：根據(jù)取值范圍修剪αj：?

  ?

  ?

?

• 步驟6：更新αi：?

  ?

  ?

?

• 步驟7：更新b1和b2：?

  ?

  ?

?

• 步驟8：根據(jù)b1和b2更新b：?

  ?

  ?

?

四 編程求解線性SVM

已經(jīng)梳理完了SMO算法實現(xiàn)步驟，接下來按照這個思路編寫代碼，進行實戰(zhàn)練習(xí)。

（1）可視化數(shù)據(jù)集

我們先使用簡單的數(shù)據(jù)集進行測試，數(shù)據(jù)集下載地址：https://github.com/Jack-Cherish/Machine-Learning/blob/master/SVM/testSet.txt

編寫程序可視化數(shù)據(jù)集，看下它是長什么樣的：

# -*- coding:UTF-8 -*-

import matplotlib.pyplot as plt

import numpy as np

?

"""

函數(shù)說明:讀取數(shù)據(jù)

?

Parameters:

fileName - 文件名

Returns:

dataMat - 數(shù)據(jù)矩陣

labelMat - 數(shù)據(jù)標(biāo)簽

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-21

"""

def loadDataSet(fileName):

dataMat = []; labelMat = []

fr = open(fileName)

for line in fr.readlines(): #逐行讀取，濾除空格等

lineArr = line.strip().split('\t')

dataMat.append([float(lineArr[0]), float(lineArr[1])]) #添加數(shù)據(jù)

labelMat.append(float(lineArr[2])) #添加標(biāo)簽

return dataMat,labelMat

?

"""

函數(shù)說明:數(shù)據(jù)可視化

?

Parameters:

dataMat - 數(shù)據(jù)矩陣

labelMat - 數(shù)據(jù)標(biāo)簽

Returns:

無

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-21

"""

def showDataSet(dataMat, labelMat):

data_plus = [] #正樣本

data_minus = [] #負(fù)樣本

for i in range(len(dataMat)):

if labelMat[i] > 0:

data_plus.append(dataMat[i])

else:

data_minus.append(dataMat[i])

data_plus_np = np.array(data_plus) #轉(zhuǎn)換為numpy矩陣

data_minus_np = np.array(data_minus) #轉(zhuǎn)換為numpy矩陣

plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1]) #正樣本散點圖

plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1]) #負(fù)樣本散點圖

plt.show()

?

if __name__ == '__main__':

dataMat, labelMat = loadDataSet('testSet.txt')

showDataSet(dataMat, labelMat)

• ?
• ?

運行程序，查看結(jié)果：

?

?

?

這就是我們使用的二維數(shù)據(jù)集，顯然線性可分?，F(xiàn)在我們使用簡化版的SMO算法進行求解。

（2）簡化版SMO算法

按照上述已經(jīng)推導(dǎo)的步驟編寫代碼：

# -*- coding:UTF-8 -*-

from time import sleep

import matplotlib.pyplot as plt

import numpy as np

import random

import types

?

"""

函數(shù)說明:讀取數(shù)據(jù)

?

Parameters:

fileName - 文件名

Returns:

dataMat - 數(shù)據(jù)矩陣

labelMat - 數(shù)據(jù)標(biāo)簽

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-21

"""

def loadDataSet(fileName):

dataMat = []; labelMat = []

fr = open(fileName)

for line in fr.readlines(): #逐行讀取，濾除空格等

lineArr = line.strip().split('\t')

dataMat.append([float(lineArr[0]), float(lineArr[1])]) #添加數(shù)據(jù)

labelMat.append(float(lineArr[2])) #添加標(biāo)簽

return dataMat,labelMat

?

?

"""

函數(shù)說明:隨機選擇alpha

?

Parameters:

i - alpha

m - alpha參數(shù)個數(shù)

Returns:

j -

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-21

"""

def selectJrand(i, m):

j = i #選擇一個不等于i的j

while (j == i):

j = int(random.uniform(0, m))

return j

?

"""

函數(shù)說明:修剪alpha

?

Parameters:

aj - alpha值

H - alpha上限

L - alpha下限

Returns:

aj - alpah值

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-21

"""

def clipAlpha(aj,H,L):

if aj > H:

aj = H

if L > aj:

aj = L

return aj

?

"""

函數(shù)說明:簡化版SMO算法

?

Parameters:

dataMatIn - 數(shù)據(jù)矩陣

classLabels - 數(shù)據(jù)標(biāo)簽

C - 松弛變量

toler - 容錯率

maxIter - 最大迭代次數(shù)

Returns:

無

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-23

"""

def smoSimple(dataMatIn, classLabels, C, toler, maxIter):

#轉(zhuǎn)換為numpy的mat存儲

dataMatrix = np.mat(dataMatIn); labelMat = np.mat(classLabels).transpose()

#初始化b參數(shù)，統(tǒng)計dataMatrix的維度

b = 0; m,n = np.shape(dataMatrix)

#初始化alpha參數(shù)，設(shè)為0

alphas = np.mat(np.zeros((m,1)))

#初始化迭代次數(shù)

iter_num = 0

#最多迭代matIter次

while (iter_num < maxIter):

alphaPairsChanged = 0

for i in range(m):

#步驟1：計算誤差Ei

fXi = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b

Ei = fXi - float(labelMat[i])

#優(yōu)化alpha，更設(shè)定一定的容錯率。

if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):

#隨機選擇另一個與alpha_i成對優(yōu)化的alpha_j

j = selectJrand(i,m)

#步驟1：計算誤差Ej

fXj = float(np.multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b

Ej = fXj - float(labelMat[j])

#保存更新前的aplpha值，使用深拷貝

alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();

#步驟2：計算上下界L和H

if (labelMat[i] != labelMat[j]):

L = max(0, alphas[j] - alphas[i])

H = min(C, C + alphas[j] - alphas[i])

else:

L = max(0, alphas[j] + alphas[i] - C)

H = min(C, alphas[j] + alphas[i])

if L==H: print("L==H"); continue

#步驟3：計算eta

eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T

if eta >= 0: print("eta>=0"); continue

#步驟4：更新alpha_j

alphas[j] -= labelMat[j]*(Ei - Ej)/eta

#步驟5：修剪alpha_j

alphas[j] = clipAlpha(alphas[j],H,L)

if (abs(alphas[j] - alphaJold) < 0.00001): print("alpha_j變化太小"); continue

#步驟6：更新alpha_i

alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])

#步驟7：更新b_1和b_2

b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T

b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T

#步驟8：根據(jù)b_1和b_2更新b

if (0 < alphas[i]) and (C > alphas[i]): b = b1

elif (0 < alphas[j]) and (C > alphas[j]): b = b2

else: b = (b1 + b2)/2.0

#統(tǒng)計優(yōu)化次數(shù)

alphaPairsChanged += 1

#打印統(tǒng)計信息

print("第%d次迭代 樣本:%d, alpha優(yōu)化次數(shù):%d" % (iter_num,i,alphaPairsChanged))

#更新迭代次數(shù)

if (alphaPairsChanged == 0): iter_num += 1

else: iter_num = 0

print("迭代次數(shù): %d" % iter_num)

return b,alphas

?

"""

函數(shù)說明:分類結(jié)果可視化

?

Parameters:

dataMat - 數(shù)據(jù)矩陣

w - 直線法向量

b - 直線解決

Returns:

無

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-23

"""

def showClassifer(dataMat, w, b):

#繪制樣本點

data_plus = [] #正樣本

data_minus = [] #負(fù)樣本

for i in range(len(dataMat)):

if labelMat[i] > 0:

data_plus.append(dataMat[i])

else:

data_minus.append(dataMat[i])

data_plus_np = np.array(data_plus) #轉(zhuǎn)換為numpy矩陣

data_minus_np = np.array(data_minus) #轉(zhuǎn)換為numpy矩陣

plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1], s=30, alpha=0.7) #正樣本散點圖

plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1], s=30, alpha=0.7) #負(fù)樣本散點圖

#繪制直線

x1 = max(dataMat)[0]

x2 = min(dataMat)[0]

a1, a2 = w

b = float(b)

a1 = float(a1[0])

a2 = float(a2[0])

y1, y2 = (-b- a1*x1)/a2, (-b - a1*x2)/a2

plt.plot([x1, x2], [y1, y2])

#找出支持向量點

for i, alpha in enumerate(alphas):

if abs(alpha) > 0:

x, y = dataMat[i]

plt.scatter([x], [y], s=150, c='none', alpha=0.7, linewidth=1.5, edgecolor='red')

plt.show()

?

?

"""

函數(shù)說明:計算w

?

Parameters:

dataMat - 數(shù)據(jù)矩陣

labelMat - 數(shù)據(jù)標(biāo)簽

alphas - alphas值

Returns:

無

Author:

Jack Cui

Blog:

http://blog.csdn.net/c406495762

Zhihu:

https://www.zhihu.com/people/Jack--Cui/

Modify:

2017-09-23

"""

def get_w(dataMat, labelMat, alphas):

alphas, dataMat, labelMat = np.array(alphas), np.array(dataMat), np.array(labelMat)

w = np.dot((np.tile(labelMat.reshape(1, -1).T, (1, 2)) * dataMat).T, alphas)

return w.tolist()

?

?

if __name__ == '__main__':

dataMat, labelMat = loadDataSet('testSet.txt')

b,alphas = smoSimple(dataMat, labelMat, 0.6, 0.001, 40)

w = get_w(dataMat, labelMat, alphas)

showClassifer(dataMat, w, b)

• 程序運行結(jié)果：

?

?

?

其中，中間的藍線為求出來的分類器，用紅圈圈出的點為支持向量點。

五 總結(jié)

• 本文主要進行了線性SVM的推導(dǎo)，并通過編程實現(xiàn)一個簡化版SMO算法；
• 本文的簡化版SMO算法在選取α的時候，沒有選擇啟發(fā)式的選擇方法，并且沒有兩個乘子的計算沒有進行優(yōu)化，所以算法比較耗時，下一篇文章會講解相應(yīng)的優(yōu)化方法；
• 本文討論的是線性SVM，沒有使用核函數(shù)，下一篇文章將會講解如何應(yīng)用核函數(shù)，將SVM應(yīng)用于非線性數(shù)據(jù)集；
• 如有問題，請留言。如有錯誤，還望指正，謝謝！

PS： 如果覺得本篇本章對您有所幫助，歡迎關(guān)注、評論、贊！

參考資料：

• [1] 五歲小孩也能看懂的SVM：https://www.zhihu.com/question/21094489/answer/8627319
• [2] 五歲小孩也能看懂的SVM ：https://www.reddit.com/r/MachineLearning/comments/15zrpp/please_explain_support_vector_machines_svm_like_i/
• [3] pluskid大牛博客：http://blog.pluskid.org/?page_id=683
• [4] 陳東岳老師文章：https://zhuanlan.zhihu.com/p/24638007
• [5] 深入理解拉格朗日乘子法和KKT條件：http://blog.csdn.net/xianlingmao/article/details/7919597
• [6] 充分條件和必要條件：https://www.zhihu.com/question/30469121
• [7] 凸函數(shù)：https://zh.wikipedia.org/wiki/%E5%87%B8%E5%87%BD%E6%95%B0
• [8]《機器學(xué)習(xí)實戰(zhàn)》第6章內(nèi)容。
• [9] SVM之SMO算法：http://www.cnblogs.com/zangrunqiang/p/5515872.html
• 來源：https://blog.csdn.net/hx14301009/article/details/79762666

總結(jié)

以上是生活随笔為你收集整理的小白学习机器学习---第六章:SVM算法原理（1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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