學習SVM（二） 如何理解支援向量機的最大分類間隔

閱讀原文

SVM演算法在在1995年正式發表，在針對中小型資料規模的分類任務上有著卓越的效果，同時有著完整的理論證明，在20世紀末的幾年和21世紀初的10年完勝神經網路，吳恩達在其2003年的《Machien learning》公開課上用兩節課的時間對其進行講解，而神經網路講解了20min左右。就是這個演算法把神經網路按在地上摩擦了大概15年的時間，直到深度學習的興起。但即便這樣，現在SVM演算法依舊被廣泛的使用。

SVM大概的可以不確切的分為三個程度理解：

（1）線性可分情況下的線性分類器，這是最原始的SVM，它最核心的思想就是最大的分類間隔（margin maximization）； （2）線性不可分情況下的線性分類器，引入了軟間隔（soft margin）的概念； （3）線性不可分情況下的非線性分類器，是SVM與核函式（kernel function）的結合。 在下面只會第一部分的內容。

什麼是最大分類間隔

SVM最大分類間隔的靈感來自於一個非常符合直覺的觀察，如果存在兩類資料，資料的特徵是二維的，那麼我們就可以把資料畫在一個二維平面上，此時我想找到一個決策面（決策邊界）去將這兩類資料分開。如下圖所示：

理論上這個決策邊界有無數種選擇，就像圖中畫出的四條黑色的線，都能實現分類，但是哪一種是最好的分類方式呢？SVM演算法認為在上圖中靠近決策平邊界的點（正負樣本）與決策邊界的距離最大時，是最好的分類選擇：

上圖中紅色的線就是要優化的目標，它表徵了資料到決策邊界的距離，這個距離就是所謂的最大分類間隔。同時在上面的幾個資料，如果靠近兩側的資料少了幾個，也不會影響決策邊界的確定，而被紅色框框出來三個資料才決定了最終的決策邊界，所以這三個資料被稱之為支援向量。

線性分類器

支援向量機演算法如何實現最大分類間隔的任務呢？我們可以先從線性分類器開始理解它，支援向量在沒有引入核函式的時候就是一個線性的分類器，我們假設與決策邊界垂直的向量（決策面的法向量）為V：

黑色的線是假設的決策邊界，X1和X2是決策邊界兩側的兩個點，Xt1和Xt2是兩個點在法向量V上面的投影，那麼可以很直觀看到，原點到Xt1的距離<原點到Xt2的距離，而且可以推廣延伸到只要資料點在決策邊界的兩側，那麼在決策邊界左側的資料點在法向量上面的投影距離永遠比右側的距離短，這就是支援向量機實現分類預測的依據。那麼怎麼用公式表徵出這個點到直線投影的距離呢？ 可以做這樣一個假設驗證一下：

如上圖中的情況所示：要求向量b在向量a上的投影距離d，向量的內積可以表示為：

於是角度的餘弦為：

距離d可以表示為：

而在SVM的特徵空間中，a是決策邊界的法向量，那麼a為單位法向量的時候其模為1，所以就有：

最後我們把a和b換成上面設定的值就會有：

有了這個東西，我們總能找到一個常數C分開兩類資料，也就是說：

到了上面的公式後，問題就非常的清晰了，法向量V其實就是決策邊界的係數（這是解析幾何裡面的知識），那麼大家肯定見過一種和它非常像的公式，叫做樣本空間下的超平面線性方程：

線性分類器就是這個樣子！！！ 不經過sigmoid函式的Logistic模型也是這個樣子！！ 不啟用的神經網路中的單個神經元還是這個樣子！！

如何實現最大分類間隔

從上面可以看到，此時的支援向量機（沒有加核函式）就是個線性的分類器，它的卓越效能就體現在線上性分類器基礎上的最大分類間隔。 所以本質上SVM要訓練的引數只有w和b，關鍵就在於SVM如何在優化中體現最大分類間隔的思想！ 針對所有的訓練資料（traindata），SVM都希望：

這裡的正負1就體現的最大分類間隔，這裡是選擇用正負1是為了計算方便，因為無論間隔是多少，都可以依靠伸縮w和b約為1。上述公式就是SVM的最大間隔假設。如下圖：

在這個圖中，決策邊界兩邊的線之間的距離（最大間隔）為：

它是這樣求出來的，資料中的支援向量在影響著最大間隔，那麼假設兩個支援向量x1和x2分別為正負，最大間隔就應該是x2-x1在法向量上的投影：

所以求取d的過程為：

這就是SVM的優化目標，它想要找到max(d)，然後大家可能發現了，這個目標裡面沒有b，之和w有關，那麼是不是任意的b都可以呢？ 顯然不是的，這個優化有一個約束條件，因為推導的過程就有假設條件是兩個支援向量要求在兩側，所以這個約束條件可以寫成：

所以最終的目標為：

或者為：

需要注意的是，約束條件中的i=1…….n，n為樣本的個數。

相關閱讀：學習SVM（三）理解SVM中的對偶問題