我對於SVM的理解，以及Python實現

01-26

我先直觀地闡述我對SVM的理解，這其中不會涉及數學公式，然後給出Python代碼。

SVM是一種二分類模型，處理的數據可以分為三類：

線性分類器，在平面上對應直線；非線性分類器，在平面上對應曲線。

硬間隔對應於線性可分數據集，可以將所有樣本正確分類，也正因為如此，受雜訊樣本影響很大，不推薦。

軟間隔對應於通常情況下的數據集（近似線性可分或線性不可分），允許一些超平面附近的樣本被錯誤分類，從而提升了泛化性能。

如下圖：

實線是由硬間隔最大化得到的，預測能力顯然不及由軟間隔最大化得到的虛線。

對於線性不可分的數據集，如下圖：

我們直觀上覺得這時線性分類器，也就是直線，不能很好的分開紅點和藍點。

但是可以用一個介於紅點與藍點之間的類似圓的曲線將二者分開，如下圖：

我們假設這個黃色的曲線就是圓，不妨設其方程為x^2+y^2=1，那麼核函數是幹什麼的呢？

我們將x^2映射為X，y^2映射為Y，那麼超平面變成了X+Y=1。

那麼原空間的線性不可分問題，就變成了新空間的（近似）線性可分問題。

此時就可以運用處理（近似）線性可分問題的方法去解決線性不可分數據集的分類問題。

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

以上我用最簡單的語言粗略地解釋了SVM，沒有用到任何數學知識。但是沒有數學，就體會不到SVM的精髓。因此接下來我會用盡量簡潔的語言敘述SVM的數學思想，如果沒有看過SVM推導過程的朋友完全可以跳過下面這段。

對於求解（近似）線性可分問題：

由最大間隔法，得到凸二次規劃問題，這類問題是有最優解的（理論上可以直接調用二次規劃計算包，得出最優解）
我們得到以上凸優化問題的對偶問題，一是因為對偶問題更容易求解，二是引入核函數，推廣到非線性問題。
求解對偶問題得到原始問題的解，進而確定分離超平面和分類決策函數。由於對偶問題里目標函數和分類決策函數只涉及實例與實例之間的內積，即<xi,xj>。我們引入核函數的概念。

拓展到求解線性不可分問題：

如之前的例子，對於線性不可分的數據集的任意兩個實例：xi,xj。當我們取某個特定映射f之後，f(xi)與f(xj)在高維空間中線性可分，運用上述的求解（近似）線性可分問題的方法，我們看到目標函數和分類決策函數只涉及內積<f(xi),f(xj)>。由於高維空間中的內積計算非常複雜，我們可以引入核函數K(xi,xj)=<f(xi),f(xj)>，因此內積問題變成了求函數值問題。最有趣的是，我們根本不需要知道映射f。精彩！

我不準備在這裡放推導過程，因為已經有很多非常好的學習資料，如果有興趣，可以看：CS229 Lecture notes

最後就是SMO演算法求解SVM問題，有興趣的話直接看作者論文：Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines

我直接給出代碼：SMO+SVM

在線性可分數據集上運行結果：

圖中標出了支持向量

這個非常完美，支持向量都在超平面附近。

在線性不可分數據集上運行結果（200個樣本）：

核函數用了高斯核，取了不同的sigma

sigma=1，有189個支持向量，相當於用整個數據集進行分類。

sigma=10，有20個支持向量，邊界曲線能較好的擬合數據集特點。

我們可以看到，當支持向量太少，可能會得到很差的決策邊界。如果支持向量太多，就相當於每次都利用整個數據集進行分類，類似KNN。

本人才疏學淺，望多指教。