深入淺出SVM

【譯者說】

本文翻譯自：https://blog.statsbot.co/support-vector-machines-tutorial-c1618e635e93

個人認為是目前讀到的SVM資料中講的最明白最淺顯的一篇，不敢獨享。第一次在知乎發文，僅用了一天的時間翻譯，如有翻譯不當之處，請不吝指正。有任何問題，歡迎交流。

【正文】

如果你使用過機器學習解決分類問題，那麼你一定聽過SVM。SVM已經被提出50年之久，經過多年的發展，已經能夠處理回歸、異常值分析和排名等分類之外的問題。

SVMs是很多機器學習從業者最喜歡的武器。

本文我們嘗試一種非常容易理解的方式來闡述SVMs是如何工作的。本文將跳過複雜的數學邏輯，更多從直覺的角度來理解SVMs的工作原理。

分類問題

假設在你的大學有一門機器學習的課程，課程指導老師發現擅長數學或者統計學的學生能夠更好的掌握機器學習知識。一直以來，他們了所有學生的成績，然後每個學生的機器學習成績都有一個標籤，標籤的內容只有兩類，一個是"好"，一個是"壞"。

現在，指導老師希望找到數學和統計學分數與機器學習課程分數的關係。之後有可能根據他們的發現來設置一些先修課程。

他們怎麼做呢？首先從表示他們收集的數據開始。我們可以畫一個二維的圖，其中一個軸表示數學成績，另外一個軸表示統計學成績。學生的機器學習成績表示為圖中的一個點。

點的顏色或紅或綠，表示「好」或者「壞」。如下圖所示：

當一個學生申請註冊課程的時候，指導老師會讓她提供數學和統計學的成績。基於已有的數據，他們會預測該學生的機器學習成績。

我們需要的是一種演算法，演算法的輸入是（math_score,stats_score）這種格式的。演算法的輸出是一個紅點或者綠點，即兩種標籤中的一種。我們已經擁有的數據也叫訓練數據。

在本例中，採用線性化分的方式作為演算法是比較合適的。根據輸出點在分割線的那一邊來判斷屬於哪個分類。

這條分割線叫做決策邊界（分類器），上圖展示的是對於該問題的兩種決策邊界。

好壞分類器

這有一個有意思的問題：上面兩個分類器都可以進行劃分，那麼到底哪個是更好的分類器呢？

需要注意的是，對訓練集數據的分割效果並不能評價一個分類器的好壞，最終需要用分類器對測試集數據進行分類。因此，我們希望能夠在訓練集數據中捕獲一般模式，從而獲得較好的泛化能力。

上圖左側的分割線顯得有些「偏斜」，在分割線的下部距離紅點的距離過近，而上部距離綠點的距離過近。儘管對訓練集進行了完美的分割，但是一旦碰到距離聚類中點稍遠的測試數據，就可能出現錯分。而右側的分割線就不會有這樣的問題。下圖中用方形表示的測試數據在兩種分類器中出現了不同的分類結果，而第二種是正確的。

可見第二種分割線在保證對訓練集正確劃分的前提下，距離兩個聚類儘可能遠。在兩個聚類中間的位置風險更小，給了兩種分類的數據更多擺動的空間，在測試集的泛化能力更好。

SVMs試圖找到如第二種分割線一樣的分類器。我們通過肉眼選擇一種較好的分類器用來很好的說明SVMs基礎的工作原理。下面是SVMs的基礎特性：

1.找到對訓練集所有的正確劃分

2.在所有正確的劃分中選擇距離最近數據點距離最大的那個分割線

最近的點（聚類邊緣的點）構成了支持向量，兩個支持向量之間的區域叫做餘量（margin）。

下圖是上邊第二種分割線以及支持向量（黑色邊界的點）和餘量（陰影區域）。

支持向量機的機制就是在多種正確的分類器中挑選泛化能力最強的分類器。是不是很簡單？

上圖展示的是二維空間下的支持向量機，而支持向量機可以在任何維度應用，原理跟二維是類似的。例如，在三維空間上，分類器是一個平面，而在更高的維度是一個超平面。

能夠被一條線或者一個超平面劃分的平面叫做線性可分數據。超平面扮演者線性分類器的作用。

容錯

我們上面的例子處理的是完全線性可分的數據。但在真實的世界中的問題很難找到這樣的數據。下圖就是一個例子。

很明顯，如果我們使用線性分類器不可能完美的劃分上圖中數據。我們也不希望因為極個別的數據而放棄線性分類器，因為對於絕大多數據擬合的很好。

SVMs如何處理這種情況呢？SVMs有一套自己的容錯機制。SVM提供一個參數C來平衡以下兩點：

1.有一個較大的餘量

2.對訓練集正確的劃分。C越大表明訓練集容忍的錯誤越少。

需要注意的是較大的餘量和正確的劃分是一對兒矛盾。下面幾幅圖展示了隨著C的增加分類器和餘量的表現差異（支持向量沒有顯示）：

注意C的增加帶來的分割線傾斜度變化。當C值較大時，它試圖容納位於圖的右下角的大多數紅點的標籤，而這可能導致測試集的錯分。C=0.01時儘管訓練集錯分率較高，但是能在測試集獲得不錯的泛化能力。

注意隨著C的增加餘量的寬度變化，C越大，餘量寬度越窄。

在之前的例子中，餘量中不允許有任何點。但這裡我們看到無法做到完全線性可分，總有一些點會進入餘量區域。

實際中需要去選擇一個合適的C。由於真實世界中幾乎不存在完全線性可分的數據，我們通常需要交叉驗證的方式取一個合適的C。

非線性可分數據

我們已經看到了支持向量機在完全線性可分以及幾乎完全線性可分兩種情況的處理。那麼對於完全不能線性可分的數據該如何處理呢？不巧的是，真實世界中的很多問題都是線性不可分的。這種情況下，找到一個分割超平面是不切實際的。

下面是一個非線性可分數據應用SVM的例子。

必須得承認表現的不好，在訓練集上最高只有75%的準確率。而且分割線穿過了某些數據。

SVM能夠做的可不止這些，這也是我最喜歡SVM的地方。我們現在具備一個尋找超平面的技術，但是我們沒有線性可分的數據。怎麼辦呢？答案是將非線性可分的數據映射到一個線性可分的空間，然後在這個空間找超平面。

下面我將一步步地就這個觀點進行說明。

我們利用上面圖中的數據集，將其映射到一個三維空間，這個三維空間的坐標如下：

下圖展示了投影后數據的分布。能夠看到數據集變得線性可分了。

在這個線性可分的數據上運行SVM得到如下分割效果：

我們得到了一個完美的劃分，現在將這個超平面反映射回到最初的二維空間，得到了如下圖所示的劃分邊界：

我們在訓練集得到了100%的準確率，而且餘量較大，很好的分割結果。

在原空間中分割平面的形狀取決於映射函數，而在映射後的空間，永遠是一個超平面。

記住對數據做映射的首要目的是利用SVM尋找分割超平面。

當超平面反映射回去之後，決策邊界不再是一條線了，餘量以及支持向量也一樣。

讓我們看看在投影空間中以及原始空間中支持向量以及餘量的樣子。在投影空間中餘量是分割平面與支持向量之間的三維空間。而支持向量也成為一個超平面。

在投影空間有四個支持向量，這四個支持向量分別位於兩組平面上。而在映射前的空間，支持向量仍然位於餘量邊界線上。

現在讓我們回顧一下發生了什麼：

1.如何選擇映射函數來映射數據到某個空間？

看起來我很專業，在上面某個地方出現了2的平方根。

其實在個例子中，我之所以選擇了這麼特殊的一個映射，是為了說明如何將數據映射到高維空間。一般來說，我們也不是十分如何對數據做映射。但是我們知道的是，如果將數據映射到高位空間，大概率可以進行線性劃分，這要感謝封面定理（Covers theorem ）。

在實際應用中，我們通常會選擇幾個多維映射函數進行比較。實際上我們可以將數據映射到無限維度來獲得較好的表現。下面我們將就此展開討論。

2.首先映射數據然後再運行SVM嗎？

答案是No。為了讓上面的例子更加容易接受，我首先做了映射。事實是SVM替你做了這件事情，這有很多好處。其中一個是SVMs使用了一個叫做kernel（以下均稱核）的機制來進行映射，這使得映射過程變得很快。

還記得上小節提到的映射到無限維度空間的事兒嗎？如果你自己做映射，如何表示以及存儲無限維度的數據呢？SVM利用核可以輕鬆的做到。

Kernels（核）

核是SVM的秘密武器，這裡我們需要引入一些數學知識。

現在我們來總結一下目前為止的知識：

1.SVM對於完全線性可分數據的分類表現得非常好。

2.對於幾乎完全線性可分的數據，SVM可以通過調節C參數值來獲得一個不錯的表現。

3.對於非線性可分數據，我們可以將這些數據映射到一個高維空間，則這個映射空間中數據變得完全或幾乎線性可分，從而變成第一步和第二步中的情況。

SVM能夠得以廣泛應用的一個重要的原因就是將數據映射到高維空間，這也是核存在的原因。

讓我們從一點題外話開始。

SVM最令人驚奇的一點在於它運用到的所有數學理論，確切的映射過程以及映射空間的維度都是不可見的。不過我們可以用向量形式的數據做點積的形式來理解這個映射過程。對於一個p維向量i和j，其中向量中元素的第一個下標表示數據，第二個下標表示所在維度，示例如下：

點積表示如下：

假設我們的數據集中有n個點，SVM只需要通過向量兩兩做點積就可以找到一個分類器，僅此而已。將數據映射到高維空間中也是如此，我們不需要提供確切的映射函數給SVM，只需要提供在映射空間中向量兩兩之間的點積即可。

儘管說是題外話，但核就是這麼做的。核是核函數的簡稱，這個函數的輸入是兩個原始空間的數據點，直接輸出映射空間中兩個向量的點積。

現在我們回過頭去看之前的映射過程，看看是否能夠提供的核是否合理。我們還將對兩種映射方式下的運算數量（計算消耗）進行比較。

對於一個點i:

首先，利用之前的映射函數做映射，映射後的點為：

計算這個映射需要下列操作：

• 第一維的映射需要一個乘法運算
• 第二維的映射需要一個乘法運算
• 第三維的映射需要兩個乘法運算

所以，一共需要4個乘法運算。

下面來看一下映射空間的點積：

為了計算這個兩個數據點的點積，我們需要首先進行映射。也就是需要4+4=8個乘法運算，然後點積運算本身有需要3個乘法運算和2個加法運算。

總結一下，利用映射函數尋找分類器，需要以下計算：

• 乘法運算：8（映射過程）+3（點積過程）=11
• 加法運算：2（點積過程）

總共是11+2=13次運算。

下面來看一下核函數是如何達到同樣的效果呢：

這裡首先在原空間對數據做點積，然後再對結果取平方。下面從數學的角度來看一下其中的原理。

從上邊的數學推導中能夠得到最後的結果跟上面先映射再點積是一樣的。那麼一共需要多少運算呢？直接看第二步即可，第三步第四步僅是我們推導的過程，為了計算二維點積需要2個乘法運算和1個加法運算，平方是另外1個乘法運算。

所以，一共需要：

• 乘法運算：2（原始空間點積）+1（結果取平方）=3
• 加法運算：1（原始空間點積）

即一共需要3+1=4次運算，只是第一種方法的31%。

所以達到同樣的目的核函數速度更快。對於計算機來說，比例中4和13的差異幾乎可以忽略，但是如果原始空間的數據有很高的維度或者需要映射到一個更高的維度，核函數處理速度快的優勢將大大地顯現。

大多數SVM庫已經整合了一些較為流行的核如Polynomial，Radial Basic Function(RBF)以及Sigmoid。如果我們在原始空間做點積而不像第一個例子中用映射函數做映射，這種操作可以看作使用的是線性核。

大部分核都提供可調的參數，例如對於polynomial 核：

允許調節c和d。在上邊舉的例子中，我們取了c=0，d=2。

核強大的地方還遠不止這些。

記得上面提到的映射到無限空間這件事兒吧？如果你還沒猜到怎麼做，這裡可以告訴你，答案是找到合適的核函數。這種方式不需要映射原始數據，也不需要擔心存儲無限維度數據的問題。

核函數將對映射後的數據計算點積（這句沒明白，不是不映射直接點積嘛？）。

RBF核就是這樣一種處理無限維度映射的核。這裡我們先不講數學原理，具體可以參見文末的參考文件。

如果你對於如何計算無限維度點積有疑問，可以參考一下計算無限序列之和的運算過程，兩者比較類似。在點積中有無數的項，正巧存在計算它們和的公式。這就解決了上節中提到的問題。現在我們總結一下：

1.我們不需要一個特定的映射函數。相反，我們從可用的核中選擇幾個作比較，挑選表現最好的一個核。

2.當然，我們也可以自定義核函數，或者手動執行映射，但是大部分情況下我們不需要這麼做。最起碼應該先選擇已有的核進行嘗試。

3.如果有一個有合適的核，一定首先考慮使用核，因為速度通常較快。

4.RBF核可以處理無限維度映射。

幾個推薦的SVM庫

有很多優秀的SVM庫可供使用：

• libSVM
• SVM-Light
• SVMTorch

很多通用的機器學習庫如scikit-learn也提供了SVM模塊，其中封裝了專用的SVM庫。我的建議是從libSVM開始學習。

libSVM是一個命令行工具，也可以使用Python，Java和Matlab中的封裝實現。只要你的數據符合libSVM要求的格式（參見libSVM 的說明文檔），可以很方便的使用。

實際上，如果你想要快速的感受到不同的核在不同參數下的表現，可以試試這些庫官網首頁的圖形介面。首先將數據標記為不同的類別，然後選擇不同的SVM參數，運行即可看到效果！

我不自覺地標記了如下圖所示的點：

這些數據對於SVM並不簡單，下面看一下運用不同核的效果：

圖形介面並沒有顯示出決策邊界，而只是顯示了不同顏色的區域來標識不同的分類。如圖所示，線性核完全忽略了紅色的點將所有的點歸為一類。而RBF核的分類效果非常完美。

有用的資源

我們到目前為止一直從直覺的角度對SVM進行理解。還有一種更棒的方式來加強理解，我強烈推薦你利用這種方式深入研究。直覺理解比較欠缺的一個例子是對非線性可分數據餘量和支持向量的理解。

優化平衡的好壞決定了餘量和支持向量（還是計算次數啊，這裡不是特別明白。）除非你研究數學，否則有些結果會反直覺。

數學有助於理解的另一個方面在理解核函數上。拿我粗略介紹的RBF核來說，他的神奇（處理無限維度映射和點積）之處應該能夠吸引你進一步深入了解。

推薦資源如下：

1.Video Lectures: Learning from Data by Yaser Abu-Mostafa. Lectures from 14 to 16 talk about SVMs and kernels. I』d also highly recommend the whole series if you』re looking for an introduction to ML, it maintains an excellent balance between math and intuition.

2.Book: The Elements of Statistical Learning?—?Trevor Hastie, Robert Tibshirani, Jerome Friedman.Chapter 4 introduces the basic idea behind SVMs, while Chapter 12 deals with it comprehensively.

最後，祝機器學習之旅愉快！