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

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

1.1 邏輯回歸

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

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

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

1.2 先做個(gè)簡化

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

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

比如瑟匆，在分類正確的情況下，y等于1栽惶，wx+b應(yīng)該為正數(shù)越大愁溜，則情況越好，是正例的確定度就越大外厂。就如上圖的A點(diǎn)冕象。y等于-1，wx+b應(yīng)該為負(fù)數(shù)越大汁蝶，則情況越好是負(fù)例的確信度就越大渐扮。

所以，函數(shù)間隔越大掖棉，說明分類正確的置信度越大墓律。函數(shù)間隔越小 ，比如上圖c點(diǎn)幔亥，說明越不能確定c點(diǎn)屬于哪一類耻讽。

可以為 別的值，只是為了方便帕棉。這一點(diǎn)在參考的第二個(gè)博客上也已經(jīng)說明了针肥。

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

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

1.3.1 函數(shù)間隔

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

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

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

答案是否定的束昵，因?yàn)椋绻杀壤母淖僿 和b（如將它們改成2w 和2b）葛峻，則函數(shù)間隔的值f(x) 卻變成了原來的2 倍（雖然函數(shù)值增大了锹雏，達(dá)到了目標(biāo)，但是此時(shí)超平面沒有改變）术奖，所以只有函數(shù)間隔還遠(yuǎn)遠(yuǎn)不夠礁遵。

1.3.2 幾何間隔

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

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

又因?yàn)閤₀是超平面w^Tx + b=0上的點(diǎn)既棺，利用向量之間的運(yùn)算

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

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

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

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

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

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

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

于是得到了這個(gè)式子：

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

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

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

根據(jù)前面幾個(gè)文章的話忍弛，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的這個(gè)問題啦扬，用優(yōu)化包求解得到wb中狂，即可得到具有最大幾何間距的超平面，提高分類每個(gè)點(diǎn)的確信度扑毡，分類目標(biāo)完成胃榕。

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

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

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

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

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

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

二讯屈、手工求解SVM，暫時(shí)先得到w和b县习，α留著用SMO算法求

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

前言

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

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

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

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

2.1 拉格朗日對偶

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

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

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

這種極值問題怎么求

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

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

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

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

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

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

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

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

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

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

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

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

2.1.3 引入對偶問題的理由

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

我們定義函數(shù)

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

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

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

對偶問題已經(jīng)表示出來了舅世，這個(gè)對偶問題也相對原問題好求，那么奇徒，這兩個(gè)問題等價(jià)嗎雏亚？或者說，對偶問題的解是不是原問題的解呢摩钙？

需要用KKT條件來判斷了罢低。

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

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

一网持、背景知識

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

• 2身弊、KKT條件

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

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

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

----------1、L對 w 求導(dǎo)為零
----------2阱佛、h(w)=0
----------3帖汞、α_ig_i=0 ，i = 1凑术，...翩蘸，k

注意此時(shí)

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

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

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

注意：這個(gè)是傳統(tǒng)最優(yōu)化問題的一般式，這個(gè)問題有k個(gè)不等式約束方程羞迷，所有的點(diǎn)都要滿足這k個(gè)不等式約束界轩。。假設(shè)有一百個(gè)樣本點(diǎn)闭树，只有有三個(gè)極值N1耸棒，N2，N3报辱，那么說明其余97個(gè)點(diǎn)帶入這k個(gè)方程中去都會小于零与殃。 另外對于這三個(gè)極值點(diǎn)，可能會有g(shù)_i(N1) = 0,除了第i個(gè)g以外碍现，g(N1)都小于0 幅疼。然后對于極值N2，g_j(N2)=0昼接，除了第j個(gè)約束以外爽篷，其余的g(N2)都小于0。

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

另外可以參考這段話：

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

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

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

由上面那句話可以知道恬吕，

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

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

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

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

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

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

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

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

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

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

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

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

得到

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

最后得到

由于最后一項(xiàng)是0，因此簡化為

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

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

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

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

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

注意恬叹，這里的w候生，b，alpha都是 向量绽昼，都是m維的向量

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

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

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

這里考慮另外一個(gè)問題柿估，由于前面求解中得到

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

也就是說陷猫，利用判別模型對新來樣本進(jìn)行判別時(shí)秫舌，以前新來的要分類的樣本首先根據(jù)w和b做一次線性運(yùn)算，然后看求的結(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颜及。

另外，那有人會說蹂楣，與前面所有的樣本都做運(yùn)算是不是太耗時(shí)了俏站？其實(shí)不然，我們從KKT條件中得到痊土，只有支持向量的α_i>0 （不等于零）其他情況α_i是等于零的肄扎。比如，像前面那個(gè)x和圈的圖，新來的樣本只需要和三個(gè)支持向量做運(yùn)算即可犯祠。

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

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

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