機器學習實戰（7）—— 支持向量機原理部分
話說小明上次用樸素貝葉斯預測對了！小姐姐果然在圖書館複習
小明想，這次不能再等了，於是走上前去 ...
小明：同學，你好啊，你這是在看什麼呢？
小明看了一眼，哇，竟然是機器學習，哈哈，不慌，這個我會！【竊喜】
小姐姐：機器學習啊，最近發現這個很有意思，不過感覺挺難的
小明：我是數學系的 , 以後有問題可以問我，交個朋友吧~
小姐姐：這書上寫的這個什麼 SVM，寫的都是公式 ,
你能不能通俗易懂的講講看什麼是 SVM 呢 ? 我感覺這個挺有意思的~
小明：那我給你講個故事吧，在很久以前，一個數學家要去追求一名他愛慕的姑娘
這名姑娘數學特別好，雖然心裏也對這個數學家有好感，但還是要考考他數學怎麼樣
於是，姑娘在桌子上似乎有規律放了兩種顏色的球，說："你用一根棍分開它們？要求：儘量在放更多球之後，仍然適用。"
小明接着說：於是數學家快速放下了棍子：
小姐姐：這個不難啊，我也會放~
小明：姑娘又在桌上放了一些球，此時，原來放好的棍子，好像已經不能正確分開兩種球了，因爲有個球好像站錯了陣營：
小姐姐：是啊，有個球沒分對啊！
小明：如果球是有類別的，那麼如何根據當前的球的情況，放下棍子，使得之後再放入球的時候儘量不被棍子分錯呢？
小姐姐：這個不難啊，我就把棍子調整，讓它儘量不靠近兩種球，棍子距離兩種分界面附近的球都儘量遠。
小明：你好棒棒哦！其實你已經學會了支持向量機的精髓！
小姐姐：emmm，你不要逗我玩哦！
小明：SVM 就是試圖把棍放在最佳位置，好讓在棍的兩邊有儘可能大的間隙。這個間隙就是球到棍的距離。
小明接着說：此時即使放更多球，很大可能還是將棍子作爲一個不錯的分界線
小明接着說：故事裏的姑娘說，第一關你算是通過了，今晚一起去看電影吧~
小姐姐：感覺似懂非懂，比如這個棍的兩邊有儘可能大的間隙，這間隙怎麼求呢？
小明：那我們一起來看看吧，當一個分類問題，數據是線性可分的，也就是用一根棍就可以將兩種小球分開的時候，我們只要將棍的位置放在讓小球距離棍的距離最大化的位置即可，尋找這個最大間隔的過程，就叫做最優化。
先看下線性可分的二分類問題：
上圖中的 (a) 是已有的數據，紅色和藍色分別代表兩個不同的類別。數據顯然是線性可分的，但是將兩類數據點分開的直線顯然不止一條。上圖的 (b) 和(c)分別給出了 B、C 兩種不同的分類方案，其中黑色實線爲分界線，術語稱爲“決策面”。
每個決策面對應了一個線性分類器。雖然從分類結果上看，分類器 A 和分類器 B 的效果是相同的。但是他們的性能是有差距的，看下圖：
在 "決策面" 不變的情況下，我又添加了一個紅點。可以看到，分類器 B 依然能很好的分類結果，而分類器 C 則出現了分類錯誤。
顯然分類器 B 的 "決策面" 放置的位置優於分類器 C 的 "決策面" 放置的位置，SVM 算法也是這麼認爲的，它的依據就是分類器 B 的分類間隔比分類器 C 的分類間隔大。
這裏涉及到第一個 SVM 獨有的概念 " 分類間隔 "。在保證決策面方向不變且不會出現錯分樣本的情況下移動決策面，會在原來的決策面兩側找到兩個極限位置（越過該位置就會產生錯分現象），如虛線所示。
虛線的位置由決策面的方向和距離原決策面最近的幾個樣本的位置決定。而這兩條平行虛線正中間的分界線就是在保持當前決策面方向不變的前提下的最優決策面。兩條虛線之間的垂直距離就是這個最優決策面對應的分類間隔。
顯然每一個可能把數據集正確分開的方向都有一個最優決策面（有些方向無論如何移動決策面的位置也不可能將兩類樣本完全分開），而不同方向的最優決策面的分類間隔通常是不同的，那個具有 “最大間隔” 的決策面就是 SVM 要尋找的最優解。
而這個真正的最優解對應的兩側虛線所穿過的樣本點，就是 SVM 中的支持樣本點，稱爲 " 支持向量 "。
支持向量機是一種二分類模型，簡稱 SVM, 英文全稱是 Support Vector Machines。
求解這個 "決策面" 的過程，就是最優化。一個最優化問題通常有兩個基本的因素：1）目標函數，也就是你希望什麼東西的什麼指標達到最好；
2）優化對象，你期望通過改變哪些因素來使你的目標函數達到最優。
在線性 SVM 算法中，目標函數顯然就是那個 " 分類間隔 "，而優化對象則是決策面。
所以要對 SVM 問題進行數學建模，首先要對上述兩個對象（"分類間隔" 和 "決策面"）進行數學描述。按照一般的思維習慣，我們先描述決策面。
由淺入深，考慮剛纔棍子與球的二維空間的情況：
二維空間的直線方程爲：
現在我們做個小小的改變，讓原來的 x 軸變成 x1，y 軸變成 x2：
移項得：
將公式向量化得：
（向量化，即將一系列數據放入矩陣中來表示公式，這裏是兩個矩陣乘法）
進一步向量化，用 w 列向量和 x 列向量和標量 b 進一步向量化：
其中，向量 w 和 x 分別爲：
T 表示轉置，（沿着對角線翻折）
這裏 w1=a，w2=-1
我們都知道，最初的那個直線方程 a 和 b 的幾何意義，a 表示直線的斜率，b 表示截距，a 決定了直線與 x 軸正方向的夾角，b 決定了直線與 y 軸交點位置。
則平面上任意一個球 ( x0，y0）到棍子直線的距離爲
如果推廣到一般的二維平面上的直線：
Ax+By+C=0
則任意一個球到棍子的距離爲:
我們之前說的棍子，或者說是決策面（超平面）
可以用向量的方式簡化表示：
如果從 2 維變成多維情況，雖然公式
未改變
但是其中的向量有變化：
爲法向量，決定了超平面的方向（垂直於超平面），如果是二維情況，超平面的方向與直線（棍子）的方向垂直！
b 爲位移項，決定了超平面和原點之間的距離。
所以，超平面被 w 和 b 確定！ 將超平面記爲（w，b）
所以空間中任意點 x 到超平面 （w，b）的距離可以寫爲
假設超平面（w，b）能夠將訓練樣本正確分類，即對於一點（xi，yi），其中 xi 爲向量，長度爲維度。yi 表示類別，對於二分類問題 yi = +1 表示一類，yi = -1 表示另一類。
假設超平面能將兩類樣本正確分類，則：
當 yi = +1 時，根據公式得：
當 yi = -1 時，根據公式得：
如果我們要求再高一點，假設決策面正好處於間隔區域的中軸線上，並且支持向量到決策面的距離爲 d，則：
當 yi = +1 時，根據公式得：
當 yi = -1 時，根據公式得：
對上面兩不等式左右兩邊除 d，
就能得到：
其中，
距離超平面最近的幾個點能使得上式
的等號成立，他們就是 “支持向量”。
（下圖中的 G/R/S 點）
兩種異類支持向量到超平面的距離之和稱爲 “間隔”（margin）
我們將 wd、bd 重新記爲 w、b
則 y = +1 的支持向量到超平面的距離爲：
則 y = -1 的支持向量到超平面的距離爲：
所以 “間隔” 爲：
我們最初的目標就是要找到 “最大間隔” 的劃分超平面，也就是轉化爲了以下問題：
目標：
約束條件：
i=1,2，...，m （表示第 i 個點）
那這個約束如何理解呢？感覺不直觀！
當 yi = +1（即爲正樣本時），
所以
當 yi = -1（即爲負樣本時），
所以
爲了方便求解，
可以轉化爲
爲什麼要做這樣的等效呢？這是爲了在優化的過程中對目標函數求導時比較方便，但這絕對不影響最優化問題最後的求解。
所以轉化爲了：
求解如下：將有約束的原始目標函數轉換爲無約束的新構造的拉格朗日
目標函數
αi 爲拉格朗日乘子，
容易驗證，當某個約束條件不滿足時，例如
那麼我們顯然只要令
即可最大化 L，使得
而當所有約束條件都滿足時，則有
即我們最初要最小化的量。因此，在要求約束條件得到滿足的情況下最小化
實際上等價於直接最小化
（當然，這裏也有約束條件，就是式中的
引入拉格朗日函數的對偶問題，即：
爲何引入對偶問題呢？因爲求解對偶問題比求解原問題更方便！
（涉及太多數學理論和推導，感興趣課後大家可以研究一下）
下面我們將先求 L 對 w、b 的極小，再求 L 對 α 的極大！
先求解
因爲拉格朗日乘子αi 未知，所以還是不能求解出 w 和 b，處理不等式約束問題的一種方法是把它變換成一組等式約束，只要限制拉格朗日乘子非負，這種變換就是可行的。
應用此約束後，神奇的事情發生了！
這個約束表明：除非點滿足
否則拉格朗日乘子 αi 必須爲 0
所謂魚與熊掌不可兼得（兩者不可都不爲 0），大概能很好詮釋這點！
所以只剩兩種情況：（1）αi 爲 0，（2）αi>0 時
我們看看
熟悉不？這不就是支持向量滿足的條件嘛！
αi 爲 0 的點肯定不在決策邊界的超平面上了
再看這個公式，
發現定義決策邊界的參數 w 和 b 僅僅依賴於這些αi>0 的支持向量！
前方手推公式，高能預警！看不懂問題不大，可跳過！
合併了前兩項，且用了導數條件
合併了前兩項， 且用了導數條件 w
此時 L（w，b，α）函數中只剩下一個變量αi 了（xi ，yi 是已知點的座標）
再求外層的
此時，原問題轉化爲：
目標：
約束：
（約束是求導得到的）
這個式子可以通過 SMO 等算法進行求解得到結果（SMO 算法有興趣可以課後去了解一下包含大量數學公式【壞笑】）
小姐姐：我大概聽懂了！但是如果要分的兩部分球明顯用一條直線無法分開呢？
這就是非線性 SVM 了！
利用核技巧將輸入空間非線性問題轉化到特徵空間線性可分問題。
數學家沒有棍可以很好幫他分開兩種球了，現在怎麼辦呢？當然像所有武俠片中一樣數學家桌子一拍，球飛到空中。然後，數學家抓起一張紙，插到了兩種球的中間。
從空中角度看這些球，這些球看起來像是被一條曲線分開了。
當然這裏的空中角度不一定是 3 維，可能是更高維度 !
我們再來看一個：
我們將數據才能夠原先的座標空間 x 變換到一個新的座標空間 K（x）中，從而可以在變換後的座標空間中，從而可以在變換後的座標空間中使用一個線性的決策邊界來劃分這些點！
以上就是支持向量機的原理部分，你學會了麼？
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3E_vr-5eAL4Fn6DqQIXPzg