分類演算法之支持向量機:SVM（理論篇）

01-29

起步

支持向量機這部分比較難，本身也涉及很多數學理論，並不好懂，需要花費不少的時間和精力去理解。

背景

最早在1963年，由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 提出。而目前的版本(soft margin)是由Corinna Cortes 和 Vapnik在1993年提出，並在1995年發表。

在深度學習出現之前（2012），支持向量機被認為機器學習中近十幾年最成功，表現最好的演算法。

了解SVM

支持向量機( support vector machine )，簡稱SVM，它是一種二類分類模型，其基本模型定義為特徵空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。

看個例子：

在這個二維的平面中，用一條直線將上面的點分成兩類，顯然 H1 無法將點區分開，而H2 和 H3 都可以，但這兩條哪個更好呢？作為分界線，H3 是更合適的，因為分界線其兩邊有儘可能大的間隙，這樣的好處之一就是能在使用中有利於預測。

這是在二維上的，我們找的是線，如果是三維，我們找的是面。總的來說我們是尋找區分兩類的超平面( hyper plane )，使邊界( margin )最大。在一個 n 維空間中，超平面的方程定義為:

總共可以有多少個可能的超平面？無數條。

我們要尋找的超平面是到邊界一測最近點的距離等於到另一側最近點的距離，在這個邊界中，邊界兩側的超平面平行。

點到超平面的距離

在二維平面中，計算點 (x0, y0) 到線 ax + by + c = 0 的距離是:

在 n 維空間中，點到超平面的距離：

將點的坐標和係數都向量化表示，距離公式可以視為:

其中 w = {w0, w1, w2,...,wn}

我們尋找的超平面，是先尋找各分類到超平面的距離最小，在尋找距離之和最大的超平面，在 N 個訓練點，點的坐標記為 xi，結果分類為yi，構成 (xi, yi)：

因為 SVM 是僅支持二分類的模型，因此 yi 僅有兩種取值，我們就定義為 1 和 -1，為什麼是這兩個值，因為這兩個值會簡化求解過程。

再從超平面推導

在 (xi, yi) 中，我們用 Xi 表示了點的坐標，yi 表示了分類結果，這樣多引入了一個維度。該怎麼算呢，別急，回頭看看我們的超平面:

在超平面的上方的點滿足：

在超平面下面的點則滿足:

因為 yi 只有兩種取值 1 和 -1。因此就滿足：

整合這兩個等式（左右都乘以 yi，當yi是負值時，不等號要改方向）得：

支持向量

那麼什麼是支持向量呢？所有坐落在邊界的邊緣上的點被稱作是 「支持向量」。分界邊緣上的任意一點到超平面的距離為:

其中，||w|| 是向量的範數( norm )，或者說是向量的模。它的計算方式為：

所以，最大邊界距離為:

找出最大邊界的超平面

那麼，SVM 如何找出最大邊界的超平面( MMH )呢？由於這部分的推導比較難，有空時我再整理這部分的過程，在這邊呢，就簡單說下步驟，然後給出結果。

利用一些數學推導，把 yi(w^T*x + b) >= 1 變為有限制的凸優化問題( convex quadratic optimization )；
利用 Karush-Kuhn-Tucker ( KKT ) 條件和拉格朗日公式，可以推出 MMH 可以被表示為以下的「決定邊界( decision boundary )」

公式中各符號的含義為:

l ：表示 支持向量點 的個數；
yi : 第i個支持向量點；
Xi ：支持向量的類別標記( class label )；
ai 與 b0：都是單一數值型參數。

對於測試實例，代入以上公式，按得出結果的正負號來進行分類。

SVM 演算法有這幾個特性：

訓練好的模型的演算法複雜度是由支持向量的個數決定的，而不是由數據的維度決定的。所以 SVM 不太容易產生過擬合( overfitting )的情況；
SVM 訓練出來的模型完全依賴於支持向量，即使訓練集里所有非支持向量的點都被去除，重新訓練，結果仍然會得到完全一樣的模型；
一個 SVM 如果訓練得出的支持向量個數比較小，那訓練出的模型比較容易被泛化。

線性不可區分的情況

有些情況下，是無法用一條直線來進行劃分的：

多數情況下，數據集在空間中對應的向量不可被一個超平面區分開。這種情況要怎麼使用 SVM 呢？這種情況用兩個步驟來解決：

利用一個非線性的映射把原數據集中的向量點轉化到一個更高維度的空間中；
在這個高維度的空間中找一個線性的超平面來進行可區分處理。

如上圖表示的，將其從一維轉為二維空間，然後在二維空間進行求解。youtube上有個可視化的演示: https://www.youtube.com/watch?v=3liCbRZPrZA

本章討論的是映射到高維空間的方式。

原始數據轉化到高維

舉個例子，在三維空間中的向量 X = (x1, x2, x3) 轉化到六維空間 Z 中去，令:

新的決策超平面為:

其中，W 和 Z 都是向量，這個超平面是線性的，解出 W 和 b 後，待會原方程：

這類轉換的求解過程中，是需要計算內積，而內積的複雜度非常高，改怎麼解決？這就需要使用 核方法。

核方法

在處理非線性的情況中，SVM 選擇一個核函數 ( kernel trick )，通過函數 k(.,.) 將數據映射到高維空間。支持向量機首先在低維空間中完成計算，然後通過核函數將輸入空間映射到高維特徵空間，最終在高維空間中構造出最優分離超平面。

核函數例子： 假設兩個向量：x = (a1, a2, a3) y = (b1, b2, b3) ，定義方程：

f(x) = (x1x1, x1x2, x1x3, x2x1, x2x2, x2x3, x3x1, x3x2, x3x3)n

假設核函數為: K(x, y) = (<x, y>)^2 , 且設 x = (1, 2, 3) y=(4, 5, 6) 則有：

f(x) = (1, 2, 3, 2, 4, 6, 3, 6, 9)nf(y) = (16, 20, 24, 20, 25, 36, 24, 30, 36)n<f(x), f(y)> = 16 + 40 + 72 + 40 + 100 + 180 + 72 + 180 + 324 = 1024n

而核函數計算為: K(x, y) = (4 + 10 + 18 ) ^2 = 32^2 = 1024 ，相同的結果，使用核函數是不是容易計算很多。

核函數能很好的避開直接在高維空間中進行計算，而結果卻是等價的。常見的幾個核函數 ( kernel functions )有:

h度多項式核函數(polynomial kernel of degree h)

高斯徑向基核函數(Gaussian radial basis function kernel)

S型核函數(Sigmoid function kernel)

如何選擇使用哪個核函數？根據先驗知識，比如圖像分類，使用RBF，嘗試不同的核函數，根據結果準確度而定。

多分類的情況

SVM 是二分類模型，如果空間中有多個分類，比方有蘋果，梨，香蕉。那麼SVM就需要對每個類別做一次模型，是蘋果還是不是蘋果？是香蕉還是不是香蕉？是梨子還是不是梨子？從中選出可能性最大的。也可以兩兩做一次SVM：是蘋果還是香蕉？是香蕉還是梨子？是梨子還是蘋果？最後三個分類器投票決定。因此，多分類情況有兩種做法：

對於每個類，有一個當前類和其他類的二類分類器( one-versus-the-rest approach)
兩兩做一次二類分類器( one-versus-one approace )