參考
https://www.cnblogs.com/pinard/p/6097604.html
https://blog.csdn.net/alwaystry/article/details/60957096
http://www.reibang.com/p/55458caf0814
https://blog.csdn.net/luoshixian099/article/details/51227754
概述
支持向量機是一個二分類算法宣决，主要用于2元分類任務（是或不是的問題）洽瞬。
我的理解汇竭，比如在二維空間上有兩種類型的無數(shù)個點，我們需要找到一條線將這兩類點分離開來，這就是支持向量機的本質(zhì)慈格。如果再三維空間上仍秤，就是找到一個平面來分割兩類點失暂。三維以上的空間是超平面彼宠。
這個線或者面定義為 wx + b = 0利虫。 我們的任務就是要算出這個w和b熬词。
訓練樣本一般有三種情況： 線性可分臣咖，軟線性可分男应，線性不可分。
下面就來說說這三種情況某弦。
線性可分支持向量機
當我們的訓練集中的樣本是線性可分的時候页眯，我們可以定義一條線為 y = wx + b瓣窄；y的取值為+1或者-1系宫，當y= +1時按价，說明訓練樣本x為正類，當y = -1時笙瑟，訓練樣本為負類。
函數(shù)間隔與幾何間隔
當超平面 wx + b = 0 確定的情況下癞志，| wx + b | 可以表示點 x 到超平面的距離往枷，而 wx + b 的符號與y值對比可以判斷是否分類正確（只有計算值與y值一樣時才是分類正確的），所以我們可以用 y(wx + b) 來表示分類的正確性以及點離超平面的距離凄杯。
引出函數(shù)間隔的概念:
而超平面 (w, b) 關(guān)于 T 中所有樣本點 (x, y) 的函數(shù)間隔的最小值错洁，為超平面 (w, b) 關(guān)于 T 的數(shù)函間隔。
但是這樣的定義還有問題戒突，如果等量的增加 w 和 b 的值屯碴，這樣超平面不變，函數(shù)間隔會無限的增大膊存。我們可以給 w 增加約束條件导而，這樣引出幾何間隔：
將函數(shù)間隔除上 w的二階范數(shù)忱叭，這樣 w 和 b 即使增加也不會影響幾何間隔的大小。所以我們使用幾何間隔來表示點 (x, y) 到超平面的距離今艺。
而我們知道如果點離超平面的距離越大韵丑，說明這個點的分類可信度越高 (如果點就在超平面的旁邊，是不是會懷疑它是否分類正確)虚缎，所以我們要盡可能的讓所有的點離超平面遠遠的撵彻，這樣分類的確信度就會很高。
在上面的圖中实牡，我們找到了一個超平面 wx + b = 0 陌僵，它使得最近的打叉的點與最近的圓圈的點離超平面的距離是一樣的，我們需要找的超平面就是這樣的超平面创坞。最近的點離超平面的距離我們定義為 1 碗短。
而這些離超平面距離最近的點我們就叫它支持向量。
從上面的圖中我們可以看出超平面的確定摆霉，其實只與這些支持向量有關(guān)系豪椿，而與其它點沒有關(guān)系。如果我們不考慮其它點携栋，只考慮支持向量搭盾，而且定義支持向量到超平面的距離為1，也就是函數(shù)間隔為1婉支，那么幾何間隔就可以化簡成為：
這樣我們只要使這些支持向量的函數(shù)間隔最大鸯隅，就能確定超平面了。
不過也有約束條件向挖，支持向量的函數(shù)間隔我們定義為1了蝌以，那么其它點的函數(shù)間隔呢？肯定是大于1的吧何之，所以約束條件是 y(wx + b) 大于等于 1 跟畅。
而在數(shù)學中，我們求極大值不好求溶推，可以轉(zhuǎn)換為就極小值徊件，就上圖中的極大值相當于是就下圖中的極小值：
這樣我們將問題轉(zhuǎn)換為了求極小值的問題。
拉格朗日乘子法
求極小值的方法有很多蒜危，這里說說拉格朗日乘子法虱痕。
我們通過求解原始問題的對偶問題，間接來原始問題辐赞。(什么是對偶問題呢部翘，我的白話理解就是，兩個問題的解是相同的响委，通過求解其中一個問題的解新思，另外一個問題的解就相應的得到了窖梁，這樣的兩個問題就是對偶問題，具有對偶性表牢。)
至于拉格朗日乘子法轉(zhuǎn)換后的問題為什么是這個原始問題的對偶問題窄绒，這個太深奧了，還需要深入研究學習崔兴，這里我只需要知道這樣轉(zhuǎn)換后的問題是對偶問題就好了彰导。
那什么是拉格朗日對偶轉(zhuǎn)換呢？簡單說敲茄，就是通過給每一個約束條件加上一個拉格朗日乘子位谋，然后在全部相加，得到一個拉格朗日函數(shù)堰燎，拉格朗日乘子大于等于0掏父。
然后令：
(我自己理解一下這個圖，有時候像我這種小白經(jīng)常就是這種基礎的地方不明白：意思就是 調(diào)整參數(shù) 阿爾法 使得拉格朗日函數(shù)的值最大化秆剪。)
在看上面的拉格朗日函數(shù)赊淑，函數(shù)中右邊部分肯定是大于0的，我們要讓拉格朗日函數(shù)值最大仅讽，要么就是 阿爾法 等于0陶缺，要么就是點的函數(shù)間隔 y(wx + b) 是等于1的。這樣右邊的式子等于0了洁灵，才能讓拉格朗日函數(shù)最大饱岸。而 y(wx + b) 等于 1 的這些點是不是就是我們的支持向量啊。
所以徽千，當所有約束條件都滿足的情況下苫费，函數(shù)最后也就只剩下
最后目標函數(shù)就變成了：
在滿足KKT條件的情況下，目標函數(shù)等價于下面的函數(shù)
這樣我們先求最小值双抽，在求最大值百框。
至于為什么目標函數(shù)滿足KKT條件，已經(jīng)滿足KKT條件后兩個式子是等價的牍汹，得在深入研究琅翻，現(xiàn)在就知道我們滿足KKT條件。
KKT條件
一般柑贞，一個最優(yōu)化模型能夠表示成下面的標準形式：
常用的方法是KKT條件，同樣地聂抢，把所有的不等式約束钧嘶、等式約束和目標函數(shù)全部寫為一個式子：
L(a, b, x)= f(x) + ag(x)+bh(x)
而KKT條件就是這個標準形式的最優(yōu)值要滿足：
- L(a, b, x)對x求導為零；
- h(x) = 0琳疏；
- a*g(x) = 0；
x是參數(shù)。
推導
這樣我們分別對 w 和 b 求偏導，由于滿足KKT條件，所以求導都等于0；
還有一種說法赠幕，由于我們滿足KKT條件，目標函數(shù)被轉(zhuǎn)換為了下面的式子：
我們先求 L(w, b, a) 關(guān)于 w 和 b 的最小值康二，然后在求關(guān)于 a 的最大值产雹。
求 w 和 b 的最小值，在數(shù)學中可以分別對 w 和 b 求偏導，使偏導的值等于0，也就得到了最小的極值點，同樣是上面的式子。
將得到的結(jié)果帶入拉格朗日原式中九昧，我們可以得到:
這樣得到了 L(w, b, a) 的關(guān)于 w 和 b 的最小值展姐，然后就求關(guān)于 a 的極大值了擂达，式子轉(zhuǎn)換為
極大值不好求，又要想辦法轉(zhuǎn)換為求最小值。求上面式子的極大值棍掐，那我們給它加個負號作煌，那是不是就可以轉(zhuǎn)換為就加上負號后式子的極小值的呀。
SMO算法求a
先來一段自己的理解文赚瘦，假設有n個特征粟誓，那么a的個數(shù)也有n個，我們?nèi)蓚€ a 變量起意，分別為 a1 和 a2 鹰服，將其他的 ai 都視為常數(shù)，那將所有值帶入揽咕，目標函數(shù)就可以寫成：
注意上面圖中悲酷，約束條件1紅框中的內(nèi)容是不是可以替換掉目標函數(shù)中紅框中的內(nèi)容啊亲善！因為他們都是一個表達式设易，這樣替換上去，目標函數(shù)就剩下了 a1 和 a2 兩個未知變量了蛹头。
現(xiàn)在就剩下求極小值問題了顿肺，我們分別對 a1 和 a2 求偏導等于 0 ，這是一個二元函數(shù)渣蜗，這樣可以直接求出 a1 和 a2 的值屠尊。
不過求出的 a 值需要滿足約束條件，那就是:
當a 不滿足這兩個條件時袍睡，需要對a值進行截取 知染，比如： a1 = -0.5，那么就取 a1 = 0斑胜，然后相應的調(diào)整 a2 使上面的相加條件成立控淡。這樣逐步遞歸，就能求得所有的 a 的值了止潘。
軟線性可分支持向量機
上面的支持向量機算法還不完善掺炭，因為我們有個前提條件是樣本數(shù)據(jù)是完全線性可分的，就是可以找到一條直線凭戴，將所有的樣本分為兩類涧狮。但是萬一有一些干擾點，不按常理出牌，就偏過去了一點點者冤，導致了找不到這樣的線了肤视，上面的算法就不可以用了。
對于這種情況我們有軟線性可分支持向量機的解決辦法涉枫。就是對于每個樣本邢滑，我們允許偏離超平面一定的距離，這個距離我們定義為松弛變量愿汰。
原來困后，我們定義 y (wx + b) 為點到超平面的距離，而約束所有的樣本距離衬廷，都是大于等于1的摇予。
現(xiàn)在我們加入松弛變量：
如果松弛變量無限大的話，那么所有數(shù)據(jù)集都能符合條件了吗跋，所以侧戴，還要在元目標函數(shù)后加上一項，使松弛變量的和也要最小小腊。
這樣整體達到最芯壤稹：
C是固定的一個常量，C >= 0秩冈，為懲罰參數(shù)本缠，可以理解為我們一般回歸和分類問題正則化時候的參數(shù)。C越大入问，對誤分類的懲罰越大丹锹，C越小，對誤分類的懲罰越小芬失。
用之前的拉格朗日乘子法楣黍，同理推導，得新的函數(shù):
然后分別對 w 和 b 和 松弛變量 求導：
w 帶回函數(shù)棱烂，得到和原來一樣的目標函數(shù):
阿爾法 和 r 都是拉格朗日乘子租漂，都是大于0的。而 C - 阿爾法 - r = 0颊糜，所以 阿爾法 <= C哩治，整個問題變成了：
最后使用SMO算法求 阿爾法 就可以了。不過再求得 阿爾法 進行截取時衬鱼，需要使用新的約束條件业筏，0 < 阿爾法 < C。得到 阿爾法的解鸟赫。
線性不可分支持向量機
而還有一種情況蒜胖，所有的樣本點已經(jīng)無法用消别，f(x) = wx + b 這樣的函數(shù)完全分類的時候，這種情況我們叫線性不可分情況台谢。那這種情況下咋辦呢寻狂？
我理解，就是將之前計算得到的目標函數(shù)中 <x_i, x_j> 的內(nèi)積朋沮，替換成一個函數(shù)荆虱，原來的 x 通過這個函數(shù)轉(zhuǎn)換后得到了新的值，這些值是可以線性可分的朽们，更容易計算：
核函數(shù)
核函數(shù)有很多種，我們可以選擇適合的诉位。
- 多項式核函數(shù)
- 高斯核函數(shù)
- 線性核函數(shù) 就是x1 和 x2的內(nèi)積骑脱，相當于不進行映射轉(zhuǎn)換。
問題
- 怎么選擇核函數(shù)
可以先用線性核函數(shù)得到結(jié)果苍糠，然后在使用其他核函數(shù)叁丧，對比結(jié)果，選擇結(jié)果好的岳瞭。
- 怎么判斷是否線性可分
不用判斷拥娄，一般進行訓練時，先選線性核函數(shù)瞳筏，在使用其他核函數(shù)計算稚瘾，選擇最優(yōu)的模型。
