參考Jerrylead和july-支持向量機(jī)通俗導(dǎo)論

一、由邏輯回歸，引申出SVM（線性可分的SVM）

1.1 邏輯回歸

再回憶一下邏輯回歸：Logistic回歸目的是從特征學(xué)習(xí)出一個0/1分類模型，而這個模型是將特征的線性組合作為自變量，由于自變量的取值范圍是負(fù)無窮到正無窮。因此，使用logistic函數(shù)（或稱作sigmoid函數(shù)）將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于y=1的概率。

中間那條線是θ^Tx=0，logistic回歸強調(diào)所有點盡可能地遠(yuǎn)離中間那條線。學(xué)習(xí)出的結(jié)果也就中間那條線。
但是：
考慮上面3個點A、B和C。從圖中我們可以確定A是×類別的，然而C我們是不太確定的，B還算能夠確定。這樣我們可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點上達(dá)到最優(yōu)（引出了下面的函數(shù)間隔與幾何間隔）。

我想這就是支持向量機(jī)的思路和logistic回歸的不同點：
支持向量機(jī)考慮局部（不關(guān)心已經(jīng)確定遠(yuǎn)離的點），
邏輯回歸一個考慮全局（已經(jīng)遠(yuǎn)離的點可能通過調(diào)整中間線使其能夠更加遠(yuǎn)離，但是也可能使一部分點靠近中間線來換取另外一部分點更加遠(yuǎn)離中間線。）

1.2 先做個簡化

上面已經(jīng)知道，θ^Tx=0是分類的線，在svm中，只考慮局部，只考慮θ^Tx的正負(fù)問題，而不用關(guān)心g（z）。因此，在這里，用w^Tx+b代替θ^Tx，并對g(z)做一個簡化，將其簡單映射到類別標(biāo)簽y=1和y=-1上。

這里的y取值為1和-1（在svm中，只考慮局部，只考慮θ^Tx的正負(fù)問題），是為了方便定義：在分類正確的情況下，函數(shù)間隔（確信度 ）的大小

比如，在分類正確的情況下，y等于1，wx+b應(yīng)該為正數(shù)越大，則情況越好，是正例的確定度就越大。就如上圖的A點。y等于-1，wx+b應(yīng)該為負(fù)數(shù)越大，則情況越好是負(fù)例的確信度就越大。

所以，函數(shù)間隔越大，說明分類正確的置信度越大。函數(shù)間隔越小 ，比如上圖c點，說明越不能確定c點屬于哪一類。

可以為 別的值，只是為了方便。這一點在參考的第二個博客上也已經(jīng)說明了。

1.3functional and geometric margin（函數(shù)間隔 和 幾何間隔）

由上面解釋，已知可以用y(wT x + b) 的正負(fù)性來判定（或表示）分類的正確性。

1.3.1 函數(shù)間隔

定義函數(shù)間隔如下：

也就是，這個樣本點x與超平面之間的間隔（但是現(xiàn)在有些不準(zhǔn)確，所以有下面的幾何間隔）。

此時，若根據(jù)SVM的思想，最大化這個間隔，就能提高分類正確的確信度了嗎？

答案是否定的，因為，如果成比例的改變w 和b（如將它們改成2w 和2b），則函數(shù)間隔的值f(x) 卻變成了原來的2 倍（雖然函數(shù)值增大了，達(dá)到了目標(biāo)，但是此時超平面沒有改變），所以只有函數(shù)間隔還遠(yuǎn)遠(yuǎn)不夠。

1.3.2 幾何間隔

我們真正關(guān)心的，其實是“幾何上”的點到平面的距離，于是可以用幾何知識推理出來的幾何間隔。而不是一開始人們想當(dāng)然定義的函數(shù)間隔。

事實上，我們可以對法向量w 加些約束條件（這就是調(diào)優(yōu)問題的思考了)，從而引出真正定義點到超平面的距離——幾何間隔（geometrical margin）的概念。

又因為x₀是超平面w^Tx + b=0上的點，利用向量之間的運算

再令上式乘上對應(yīng)的類別y，即可得出幾何間隔

從上述函數(shù)間隔和幾何間隔的定義可以看出：幾何間隔就是函數(shù)間隔除以∥w∥，而函數(shù)間隔實際上就是，只是人為定義的一個間隔度量，而幾何間隔才是直觀上的點到超平面的距離。

接下來就是我們的目標(biāo)：尋找一個超平面，使得離超平面比較近的點能有更大的間距。也就是我們不考慮所有的點都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點中離它最近的點具有最大間距。也就是找到最大的幾何間隔。

1.4 最優(yōu)化間隔分類器

由上一小節(jié)可以知道，我們這里要找的最大間隔分類超平面中的“間隔”指的是幾何間隔。

上面兩個式子的意思是（注意，函數(shù)間距上面是折線，幾何間距上面是波浪線）：
最大化幾何間隔
約束條件是，每個樣例的函數(shù)間隔都要大于全局的那一個函數(shù)間隔（也就是所有訓(xùn)練集里的最小的那個）

用函數(shù)間隔表示幾何間隔

于是得到了這個式子：

然而這個時候目標(biāo)函數(shù)不是凸函數(shù)，約束條件也不是線性的，沒法直接代入優(yōu)化軟件里計算。我們還要改寫。前面說到同時擴(kuò)大w和b對結(jié)果沒有影響，因此，我們將全局的函數(shù)間隔值定義為1。于是，上述的函數(shù)轉(zhuǎn)變成了

由于求1/||w||的最大值，相當(dāng)于求||w||2的最小值，因此結(jié)果為：

因為現(xiàn)在的目標(biāo)函數(shù)是二次的，約束條件是線性的，所以它是一個凸二次規(guī)劃問題。這個問題可以用現(xiàn)成的QP (Quadratic Programming) 5優(yōu)化包進(jìn)行求解。一言以蔽之：在一定的約束條件下，目標(biāo)最優(yōu)，損失最小。

根據(jù)前面幾個文章的話，SVM作為判別模型，它的的模型，就是 w^Tx_i + b 。參數(shù)就是w和b。學(xué)習(xí)完參數(shù)以后，新來的樣例作為x_i，得到結(jié)果大于1，說明在超平面上面，所以是正例。反之亦然。

根據(jù)SVM的思想，SVM的初步目標(biāo)函數(shù)，就是所有樣例的幾何間隔盡可能的大

至此，得到了SVM的目標(biāo)函數(shù)，算是初步解決了SVM的這個問題，用優(yōu)化包求解得到wb，即可得到具有最大幾何間距的超平面，提高分類每個點的確信度，分類目標(biāo)完成。

接下來介紹的是手工求解w和b的方法了，一種更優(yōu)的求解方法。

1.4.1對于把全局的函數(shù)間隔值定義為1的解釋：

• w和b是SVM模型的參數(shù)，所以必須要有一個確定值才行：
  雖然說，同時擴(kuò)大w和b對結(jié)果沒有影響，但我們最后要求的仍然是w和b的確定值，不是他們的一組倍數(shù)值。函數(shù)間隔γ是方向向量w 和截距b 的函數(shù)。
  因此，我們需要對函數(shù)間隔γ做一些限制，以保證我們解是唯一的。這里為了簡便我們令函數(shù)間隔 γ等于1。

1.4.2同時擴(kuò)大w和b對結(jié)果沒有影響的解釋：

從上可以看出 ，就同時擴(kuò)大w和b就相當(dāng)于等式兩邊同時除以函數(shù)間隔 γ，而新的w和b仍然是舊的wb的函數(shù)，所以最大化仍然可以進(jìn)行。

效果等價于，令函數(shù)間隔γ=1，綜上所述，零γ=1是合理的，而且也方便了原優(yōu)化問題的計算。

二、手工求解SVM，暫時先得到w和b，α留著用SMO算法求

由拉格朗日對偶（線性可分條件下SVM的對偶算法）引入核函數(shù)（非線性可分條件下SVM的算法）

前言

上一篇說到，得到了如下的線性可分的SVM的目標(biāo)函數(shù)，可以利用優(yōu)化包進(jìn)行求解。

此外，由于這個問題的特殊結(jié)構(gòu)，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變量(dual variable) 的優(yōu)化問題，即通過求解與原問題等價的對偶問題（dual problem）得到原始問題的最優(yōu)解，這就是線性可分條件下支持向量機(jī)的對偶算法。

引入對偶的優(yōu)點：

• 1、對偶問題往往更容易求解
• 2、可以自然的引入核函數(shù)，進(jìn)而推廣到非線性分類問題。
• 3、 將w的計算提前并消除w，最終使得優(yōu)化函數(shù)變?yōu)槔窭嗜粘俗拥膯我粎?shù)優(yōu)化問題

2.1 拉格朗日對偶

2.1.1、為什么要把存在 等式約束 的極值問題，引入拉格朗日算子變成拉格朗日公式。

因為引入拉格朗日算子可以求出極值。（參考最優(yōu)化方法的解釋）

2.1.2、對于同時存在等式約束以及不等式約束的極值問題的求法

這種極值問題怎么求

首先，同樣定義拉格朗日公式，希望可以利用拉格朗日算子法求得最優(yōu)解，得到：

但是，出現(xiàn)問題了，此時加入的約束條件g已經(jīng)不再等于0了，所以，此時可以調(diào)整算子alpha變成很大很大的 值，使結(jié)果負(fù)無窮，這顯然是不合理的。

所以，我們需要排除在滿足條件下，也會無解的情況。

因此，我們定義下面的函數(shù)

要看這個函數(shù)有什么優(yōu)點，就要看看這個函數(shù)相比于L(ω,α,b)有什么變化：加了max，加了α_I大于等于零。

所以，當(dāng)g和h不滿足約束時，總可以調(diào)整α_i和β_i來使thetap具最大值為正無窮。

只有當(dāng)g和h滿足約束時，此時g<0，我們可以調(diào)整α_i和β_i（使α_i等于0，β_i任意），得到最大值，即θ_p=f(w)。

于是函數(shù)等價于這樣

于是原來的極值問題min f(w) 就等價于求min θ_p了，
即：

也就是說，最小化 θ_p，就是為了得到最小的 f(w)，而能有f(w)就說明了滿足約束條件。所以這個等價于原來的極值問題。

至此，相比于拉格朗日公式L(ω,α,b)，現(xiàn)在即加入了拉格朗日算子，又排除了純粹的拉格朗日公式中出現(xiàn)無窮的情況。

但是，又出現(xiàn)了新的問題，也就是，如果直接求解，首先面對的就是兩個參數(shù)（最里面的是max，這個max問題有兩個參數(shù)），而且alpha也是不等式約束，再在w上求最小值，這個過程并不容易做。那么應(yīng)該怎么辦呢？

2.1.3 引入對偶問題的理由

在最優(yōu)化課程里，當(dāng)遇到不好解的優(yōu)化問題時，可以轉(zhuǎn)化為原問題的對偶問題試試。
此處，d代表對偶。D--dual

我們定義函數(shù)

θ_D 將問題轉(zhuǎn)化為先求L(ω,α,b)關(guān)于 ω 的最小值（此時α和β是固定值），之后再求θ_D 的最大值。上來面對的是一個參數(shù)，相對簡單些。

相對于原問題，更換了min和max的順序，得到了它的對偶問題。

--------------------------------------------------------------------------------------------------------------
一般的更換順序的結(jié)果是MaxMin(X) <= MinMax(X)。也就是，此時有

對偶問題已經(jīng)表示出來了，這個對偶問題也相對原問題好求，那么，這兩個問題等價嗎？或者說，對偶問題的解是不是原問題的解呢？

需要用KKT條件來判斷了。

2.1.4 用KKT條件來判斷對偶問題的解是不是原問題的解

對于拉格朗日算子的深入理解可以看看《最優(yōu)化方法》，講義的最后一頁。

一、背景知識

• 1、等式約束的時候，采用拉格朗日乘子法即可得到最優(yōu)解。而KKT條件是拉格朗日乘子法的泛化（從條件1就可以看出，對w求導(dǎo)為0）

• 2、KKT條件

含有不等式約束的問題，常常用KKT條件求得候選最優(yōu)解

對于一般化的拉格朗日公式：

最優(yōu)值 w 必須滿足以下三個條件：

----------1、L對 w 求導(dǎo)為零
----------2、h(w)=0
----------3、α_ig_i=0 ，i = 1，...，k

注意此時

第三個條件表明了KKT的思想：極值會在可行域邊界取得。----解釋：
-----對于一個特定的自變量w1，當(dāng)自變量w1在第 i 個可行域邊界（g_i(w1)=0）時，說明此時這個約束是起到了作用的。這個約束是w1被g_i約束了。此時只能到g_i的平面上（即邊界），再多就出界了。。。而對于最優(yōu)解來說，就是f(w)達(dá)到最優(yōu)，所以L中，除了f(w)部分，其余應(yīng)該都等于0，所以此時α>0(或許等于零也可以？疑問）

----而此時，w1在其他的約束條件g_非i下，有g(shù)_非i(w1)<0），說明W1可以隨意些，說明此時這個約束并沒有起到作用，但是作為最優(yōu)解，為了除了f(w)部分，其余應(yīng)該都等于0，所以其系數(shù)α應(yīng)該等于零。

----------------------------------------------------------------------------------------

注意：這個是傳統(tǒng)最優(yōu)化問題的一般式，這個問題有k個不等式約束方程，所有的點都要滿足這k個不等式約束。。假設(shè)有一百個樣本點，只有有三個極值N1，N2，N3，那么說明其余97個點帶入這k個方程中去都會小于零。 另外對于這三個極值點，可能會有g(shù)_i(N1) = 0,除了第i個g以外，g(N1)都小于0 。然后對于極值N2，g_j(N2)=0，除了第j個約束以外，其余的g(N2)都小于0。

而本節(jié)一開始討論的問題，只有一個約束方程（因為參數(shù)只有w和b）即：y（w^Tx+b）>=1，所有的點（一共m個）都要滿足這個約束方程。而關(guān)于為什么非支持向量的系數(shù)alpha會等于零呢？也就是相當(dāng)于前面的，k=1（有k個約束條件）的情況下，m個樣本點中，非支持向量的約束g<0，為了最優(yōu)解，除了f(w)應(yīng)該都等于零，所以alpha應(yīng)該等于零。

另外可以參考這段話：

• 3、最優(yōu)解 x * 滿足KKT條件 是 強對偶條件（對偶問題的解等于原問題的解）的必要條件。（由B推出A）
  即，若d* = p*，則有x * 滿足KKT條件。

• 4、當(dāng)目標(biāo)函數(shù)是凸規(guī)劃問題的時候，就升級了==>
  x * 滿足KKT條件 是 強對偶條件（對偶問題的解等于原問題的解）的充要條件。

即，若d* = p* <==> x * 滿足KKT條件

由上面那句話可以知道，

折騰這么長時間，也就是為了說明，已經(jīng)知道原問題

是凸優(yōu)化問題，所以，只要對偶問題的自變量w滿足了KKT條件，那么它就是對偶問題的最優(yōu)解w * ，同時也是原問題的最優(yōu)解了。

所以，由上可知，只要解出了2.1.3中的問題的參數(shù)w和b，也就是原問題的解了。

2.2最優(yōu)間隔分類器

重新回到SVM的優(yōu)化問題（其中每個約束式實際就是一個訓(xùn)練樣本）：

我們將約束條件改寫為拉格朗日的形式：

由KKT條件可知，只有當(dāng)函數(shù)間隔是1（g=0）的時候，α_i>0。此時，這個樣例 w_i 在約束平面上受到約束 。對于其它的不在線上的樣例點（g<0），極值不會在其范圍內(nèi)去的，所以這些樣例點前面的系數(shù)α_i=0.

實線是最大間隔超平面，假設(shè)×號的是正例，圓圈的是負(fù)例。在虛線上的點就是函數(shù)間隔是1的點，他們前面的系數(shù)α_i>0，這三個點被稱作 支持向量。

由上面問題，構(gòu)造拉格朗日函數(shù)如下（沒有等式約束，所以沒有β）：

————————————————————————————————

下面我們按照對偶問題的求解步驟來一步步進(jìn)行，由2.1.3可知，對偶問題的形式為：

首先求解L的最小值（最里面的先求），此時αi是固定的，L的最小值只與w和b有關(guān)。對w和b分別求偏導(dǎo)數(shù)。

得到

將上式帶回到拉格朗日函數(shù)中得到，此時得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)），即里面的min L已經(jīng)求出，接下來就是求max了
代入后，化簡過程如下：

最后得到

由于最后一項是0，因此簡化為

這里，上式中左右邊的向量內(nèi)積，用方括號表示。

到這一步，拉格朗日函數(shù)只包含了一個變量α_i。接著進(jìn)行下一步 ，最大化的過程，求得α_i。

假設(shè)求得了α_i 就能根據(jù)求導(dǎo)得到的結(jié)果

求得w，然后就能得到b。

b 就是 距離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。 （其實，由前面的那個x和圈的圖，可以認(rèn)為b就是截距，這個截距b等于上下兩條虛線的截距的平均值。）

注意，這里的w，b，alpha都是 向量，都是m維的向量

至于這里的α怎么求得，即上面的最大化問題怎么求解，將留給下一篇中的SMO算法來闡明。

也就是說，手動解的話，還是需要利用SMO算法，求得α才行。

————————————————————————————————

這里考慮另外一個問題，由于前面求解中得到

用α_i代替w帶入判別模型w^Tx+b，得到：

也就是說，利用判別模型對新來樣本進(jìn)行判別時，以前新來的要分類的樣本首先根據(jù)w和b做一次線性運算，然后看求的結(jié)果是大于1還是小于1來判斷正例還是負(fù)例。大于1，說明在超平面的上面，說明是正例。同理，小于1說明在超平面的下面，說明是負(fù)例。

約束條件是wx+b-1小于等于零，所以判斷就是wx+b與1進(jìn)行大小比較

現(xiàn)在有了alpha，不需要求出w（那b呢，b怎么求呢，前面已經(jīng)解釋，b是由離超平面最近的間隔和負(fù)的函數(shù)間隔相等。。。得到的。所以，將新來的樣本與訓(xùn)練數(shù)據(jù)中支持向量做內(nèi)積以后，再確定最大的正數(shù)函數(shù)間隔以及最小的負(fù)數(shù)函數(shù)間隔，即可。）

就沖上面這段話，支持向量的系數(shù)alpha，也不能等于0。

另外，那有人會說，與前面所有的樣本都做運算是不是太耗時了？其實不然，我們從KKT條件中得到，只有支持向量的α_i>0 （不等于零）其他情況α_i是等于零的。比如，像前面那個x和圈的圖，新來的樣本只需要和三個支持向量做運算即可。

由此可以看到，求出α_i以后，只需要利用支持向量，就可以來判斷新來的樣例是正例還是負(fù)例了。也許這也是是為什么叫支持向量機(jī)吧。

上面這個公式，為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。

下面，先把沒求得的alpha放一放，趁著剛剛得到的這個公式的熱乎勁，再去看看核函數(shù)。