帶你入門SVM,從較高的層次講解SVM的機制

編者按：無需艱深的數(shù)學，[24]7.ai首席數(shù)據(jù)科學家Abhishek Ghose帶你入門SVM（支持向量機）。

如果你曾經(jīng)使用機器學習解決分類問題，你可能聽說過支持向量機（SVM）。五十年來，SVM隨著時間而演化，并在分類之外得到應用，例如回歸、離散值分析、排序。

SVM是許多機器學習從業(yè)者軍火庫中的最愛。在247.ai，我們同樣使用SVM解決各種各樣的問題。

本文將試圖從較高的層次講解SVM的機制。我將聚焦于發(fā)展直覺而不是嚴謹?shù)募毠?jié)。這意味著我們將跳過盡可能多的數(shù)學，發(fā)展對SVM工作原則的強有力的直覺。

分類問題

假設你的大學開設了一門機器學習（ML）課程。課程導師發(fā)現(xiàn)數(shù)學或統(tǒng)計學好的學生表現(xiàn)最佳。隨著時間的推移，積累了一些數(shù)據(jù)，包括參加課程的學生的數(shù)學成績和統(tǒng)計學成績，以及在ML課程上的表現(xiàn)（使用兩個標簽描述，“優(yōu)”、“差”）。

現(xiàn)在，課程導師想要判定數(shù)學、統(tǒng)計學分數(shù)和ML課程表現(xiàn)之間的關系。也許，基于這一發(fā)現(xiàn)，可以指定參加課程的前提條件。

這一問題如何求解？讓我們從表示已有數(shù)據(jù)開始。我們可以繪制一張二維圖形，其中一根軸表示數(shù)學成績，另一根表示統(tǒng)計學成績。這樣每個學生就成了圖上的一個點。

點的顏色——綠或紅——表示學生在ML課程上的詞表現(xiàn)：“優(yōu)”或“差”。

當一名學生申請加入課程時，會被要求提供數(shù)學成績和統(tǒng)計學成績?；诂F(xiàn)有的數(shù)據(jù)，可以對學生在ML課程上的表現(xiàn)進行有根據(jù)的猜測。

基本上我們想要的是某種“算法”，接受“評分元組”(math_score, stats_score)輸入，預測學生在圖中是紅點還是綠點（綠/紅也稱為分類或標簽）。當然，這一算法某種程度上包括了已有數(shù)據(jù)中的模式，已有數(shù)據(jù)也稱為訓練數(shù)據(jù)。

在這個例子中，找到一條紅聚類和綠聚類之間的直線，然后判斷成績元組位于線的哪一邊，是一個好算法。

這里的直線是我們的分界（separating boundary）（因為它分離了標簽）或者分類器（classifier）（我們使用它分類數(shù)據(jù)點）。上圖顯示了兩種可能的分類器。

好 vs 差的分類器

這里有一個有趣的問題：上面的兩條線都分開了紅色聚類和綠色聚類。是否有很好的理由選擇一條，不選擇另一條呢？

別忘了，分類器的價值不在于它多么擅長分離訓練數(shù)據(jù)。我們最終想要用它分類未見數(shù)據(jù)點（稱為測試數(shù)據(jù)）。因此，我們想要選擇一條捕捉了訓練集中的通用模式（general pattern）的線，這樣的線在測試集上表現(xiàn)出色的幾率很大。

上面的第一條線看起來有點“歪斜”。下半部分看起來太接近紅聚類，而上半部分則過于接近綠聚類。是的，它完美地分割了訓練數(shù)據(jù)，但是如果它看到略微遠離其聚類的測試數(shù)據(jù)點，它很有可能會弄錯標簽。

第二條線沒有這個問題。

我們來看一個例子。下圖中兩個方形的測試數(shù)據(jù)點，兩條線分配了不同的標簽。顯然，第二條線的分類更合理。

第二條線在正確分割訓練數(shù)據(jù)的前提下，盡可能地同時遠離兩個聚類。保持在兩個聚類的正中間，讓第二條線的“風險”更小，為每個分類的數(shù)據(jù)分布留出了一些搖動的空間，因而能在測試集上取得更好的概括性。

SVM試圖找到第二條線。上面我們通過可視化方法挑選了更好的分類器，但我們需要更準確一點地定義其中的理念，以便在一般情形下加以應用。下面是一個簡化版本的SVM：

找到正確分類訓練數(shù)據(jù)的一組直線。

在找到的所有直線中，選擇那條離最接近的數(shù)據(jù)點距離最遠的直線。

距離最接近的數(shù)據(jù)點稱為支持向量（support vector）。支持向量定義的沿著分隔線的區(qū)域稱為間隔（margin）。

下圖顯示了之前的第二條線，以及相應的支持向量（黑邊數(shù)據(jù)點）和間隔（陰影區(qū)域）。

盡管上圖顯示的是直線和二維數(shù)據(jù)，SVM實際上適用于任何維度；在不同維度下，SVM尋找類似二維直線的東西。

例如，在三維情形下，SVM尋找一個平面（plane），而在更高維度下，SVM尋找一個超平面（hyperplane）——二維直線和三維平面在任意維度上的推廣。這也正是支持向量得名的由來。在高維下，數(shù)據(jù)點是多維向量，間隔的邊界也是超平面。支持向量位于間隔的邊緣，“支撐”起間隔邊界超平面。

可以被一條直線（更一般的，一個超平面）分割的數(shù)據(jù)稱為線性可分（linearly separable）數(shù)據(jù)。超平面起到線性分類器（linear classifier）的作用。

允許誤差

在上一節(jié)中，我們查看的是簡單的情形，完美的線性可分數(shù)據(jù)。然而，現(xiàn)實世界通常是亂糟糟的。你幾乎總是會碰到一些線性分類器無法正確分類的實例。

下圖就是一個例子。

顯然，如果我們使用一個線性分類器，我們將永遠不能完美地分割數(shù)據(jù)點。我們同樣不想干脆拋棄線性分類器，因為除了一些出軌數(shù)據(jù)點，線性分類器確實看起來很適合這個問題。

SVM允許我們通過參數(shù)C指定愿意接受多少誤差。C讓我們可以指定以下兩者的折衷：

較寬的間隔。

正確分類訓練數(shù)據(jù)。C值較高，意味著訓練數(shù)據(jù)上容許的誤差較少。

再重復一下，這是一個折衷。以間隔的寬度為代價得到訓練數(shù)據(jù)上更好的分類。

下圖展示了隨著C值的增加，分類器和間隔的變化（圖中沒有畫出支持向量）：

上圖中，隨著C值的增加，分割線逐漸“翹起”。在高C值下，分割線試圖容納右下角大部分的紅點。這大概不是我們想要的結(jié)果。而C=0.01的圖像看起來更好的捕捉了一般的趨勢，盡管和高C值情形相比，他在訓練數(shù)據(jù)上的精確度較低。

同時，別忘了這是折衷，注意間隔是如何隨著C值的增加而收窄的。

在上一節(jié)的例子中，間隔曾經(jīng)是數(shù)據(jù)點的“無人區(qū)”。正如我們所見，這里再也無法同時得到良好的分割邊界和相應的不包含數(shù)據(jù)點的間隔?？傆幸恍?shù)據(jù)點蔓延到了間隔地帶。

由于現(xiàn)實世界的數(shù)據(jù)幾乎從來都不是整潔的，因此決定較優(yōu)的C值很重要。我們通常使用交叉驗證（cross-validation）之類的技術選定較優(yōu)的C值。

非線性可分數(shù)據(jù)

我們已經(jīng)看到，支持向量機有條不紊地處理完美線性可分或基本上線性可分的數(shù)據(jù)。但是，如果數(shù)據(jù)完全線性不可分，SVM的表現(xiàn)如何呢？畢竟，很多現(xiàn)實世界數(shù)據(jù)是線性不可分的。當然，尋找超平面沒法奏效了。這看起來可不妙，因為SVM很擅長找超平面。

下面是一個非線性可分數(shù)據(jù)的例子（這是知名的XOR數(shù)據(jù)集的一個變體），其中的斜線是SVM找到的線性分類器：

顯然這結(jié)果不能讓人滿意。我們需要做得更好。

注意，關鍵的地方來了！我們已經(jīng)有了一項非常擅長尋找超平面的技術，但是我們的數(shù)據(jù)卻是非線性可分的。所以我們該怎么辦？將數(shù)據(jù)投影到一個線性可分的空間，然后在那個空間尋找超平面！

下面我們將逐步講解這一想法。

我們將上圖中的數(shù)據(jù)投影到一個三維空間：

下面是投影到三維空間的數(shù)據(jù)。你是不是看到了一個可以悄悄放入一個平面的地方？

讓我們在其上運行SVM：

太棒了！我們完美地分割了標簽！現(xiàn)在讓我們將這個平面投影到原本的二維空間：

訓練集上精確度100%，同時沒有過于接近數(shù)據(jù)！耶！

原空間的分割邊界的形狀由投影決定。在投影空間中，分割邊界總是一個超平面。

別忘了，投影數(shù)據(jù)的主要目標是為了利用SVM尋找超平面的強大能力。

映射回原始空間后，分割邊界不再是線性的了。不過，我們關于線性分割、間隔、支持向量的直覺在投影空間仍然成立。

我們可以看到，在左側(cè)的投影空間中，三維的間隔是超平面之上的平面和之下的平面中間的區(qū)域（為了避免影響視覺效果，沒有加上陰影），總共有4個支持向量，分別位于標識間隔的上平面和下平面。

而在右側(cè)的原始空間中，分割邊界和間隔都不再是線性的了。支持向量仍然在間隔的邊緣，但單從原始空間的二維情形來看，支持向量好像缺了幾個。

現(xiàn)在讓我們回過頭去分析下發(fā)生了什么？

1. 如何知道應該把數(shù)據(jù)投影到哪個空間？

看起來我找了一個非常特定的解——其中甚至還有√2。

上面我是為了展示投影到高維空間是如何工作的，所以選擇了一個特定的投影。一般而言，很難找到這樣的特定投影。不過，感謝Cover定理，我們確實知道，投影到高維空間后，數(shù)據(jù)更可能線性可分。

在實踐中，我們將嘗試一些高維投影，看看能否奏效。實際上，我們可以將數(shù)據(jù)投影到無窮（infinite）維，通常而言效果很好。具體細節(jié)請看下一節(jié)。

2. 所以我首先投影數(shù)據(jù)接著運行SVM？

否。為了讓上面的例子易于理解，我首先投影了數(shù)據(jù)。其實你只需讓SVM為你投影數(shù)據(jù)。這帶來了一些優(yōu)勢，包括SVM將使用一種稱為核（kernels）的東西進行投影，這相當迅速（我們很快將講解原因）。

另外，還記得我在上一點提過投影至無窮維么？那該如何表示、存儲無窮維呢？結(jié)果SVM在這一點上非常聰明，同樣，這和核有關。

現(xiàn)在是時候查看下核了。

核

這是讓SVM奏效的秘密武器。這里我們需要一點數(shù)學。

讓我們回顧下之前的內(nèi)容：

SVM在線性可分的數(shù)據(jù)上效果極為出色。

使用正確的C值，SVM在基本線性可分的數(shù)據(jù)上效果相當出色。

線性不可分的數(shù)據(jù)可以投影至完美線性可分或基本線性可分的空間，從而將問題轉(zhuǎn)化為1或2.

看起來讓SVM得到普遍應用的關鍵是投影到高維。這正是核的用武之地。

SVM優(yōu)化

之前我們略過了SVM尋找超平面的數(shù)學部分，現(xiàn)在為了更好地說明核的作用，我們需要還下之前的欠債。

假設訓練數(shù)據(jù)集包含n個數(shù)據(jù)點，其中每個數(shù)據(jù)點用一個元組表示(xi, yi)，其中xi為表示數(shù)據(jù)點的向量，yi為數(shù)據(jù)點的分類/標簽（不妨令yi的取值為-1或1）。那么，分割超平面就可以表示為：

wx - b = 0

其中，w為超平面的法向量。

將某一數(shù)據(jù)點xi代入wx - b后，根據(jù)所得結(jié)果的正負，就可以判斷數(shù)據(jù)點的分類。

相應地，確定間隔的兩個超平面則可以表示為

wx - b = 1 wx - b = -1

這兩個超平面之間的距離，也就是間隔的寬度為2/||w||

SVM的目標是在正確分類的前提下，最大化間隔寬度，也就是說，在滿足yi(wxi- b) >= 1的前提下，最大化2/||w||，也就是最小化||w||。

上式中，i = 1, …, n，也就是說，所有數(shù)據(jù)點都要滿足。但實際上，并不需要為所有數(shù)據(jù)點進行計算，只需要為所有支持向量計算即可。另外，上式中，我們乘上了yi（取值為1或-1），這就同時保證了間隔兩側(cè)的數(shù)據(jù)點都符合要求。

下面我們需要使用一些更深入的數(shù)學。顯然，最小化||w||等價于最小化

這一變換表明這是一個二次優(yōu)化問題，有成熟的方案可以使用。

不過，通過拉格朗日對偶（Lagrange Duality）變換，可以進一步將其轉(zhuǎn)換為對偶變量（dual variable）優(yōu)化問題：

加入拉格朗日乘數(shù)

然后可以找出更高效的求解方法：（這里略去具體推導過程）

另外，在推導過程中，我們得到了一個中間結(jié)果，w可以通過下式計算：

你可以不用在意以上公式的細節(jié)，只需注意一點，以上計算都是基于向量的內(nèi)積。也就是說，無論是超平面的選取，還是確定超平面后分類測試數(shù)據(jù)點，都只需要計算向量的內(nèi)積。

核函數(shù)

而核函數(shù)（kernel function），簡稱核（kernel）正是算內(nèi)積的！核函數(shù)接受原始空間中兩個數(shù)據(jù)點作為輸入，可以直接給出投影空間中的點積。

讓我們回顧下上一節(jié)的例子，看看相應的核函數(shù)。我們同時也將跟蹤投影和內(nèi)積的運算量，以便和核函數(shù)對比。

給定數(shù)據(jù)點i：

相應的投影為：

算下得到投影需要的運算量：

計算第一維：1次乘法

計算第二維：1次乘法

計算第三維：2次乘法

共計1+1+2 =4次乘法

同理，數(shù)據(jù)點j投影也需要4次乘法。

數(shù)據(jù)點i和數(shù)據(jù)點j在投影空間的內(nèi)積為：

內(nèi)積計算需要3次乘法、2次加法。

也就是：

乘法：8（投影）+ 3（內(nèi)積） = 11

加法：2（內(nèi)積）

共計11 + 2 =13次運算

而以下核函數(shù)將給出相同結(jié)果：

以上核函數(shù)在原始空間計算內(nèi)積，然后取平方，直接得到結(jié)果。

只需展開以上公式就可以驗證結(jié)果是一致的：

需要幾次運算？在二維情形下計算內(nèi)積需要2次乘法、1次加法，然后平方又是1次乘法。所以總共是4次運算，僅僅是之前先投影后計算的運算量的31%。

看來用核函數(shù)計算所需內(nèi)積要快得多。在這個例子中，這點提升可能不算什么：4次運算和13次運算。然而，如果數(shù)據(jù)點有許多維度，投影空間的維度更高，在大型數(shù)據(jù)集上，核函數(shù)節(jié)省的算力將飛速累積。這是核函數(shù)的巨大優(yōu)勢。

大多數(shù)SVM庫內(nèi)置了流行的核函數(shù)，比如多項式（Polynomial）、徑向基函數(shù)（Radial Basis Function，RBF）、Sigmoid。當我們不進行投影時（比如本文的第一個例子），我們直接在原始空間計算點積——我們把這叫做使用線性核（linear kernel）。

許多核函數(shù)提供了微調(diào)的選項，比如，多項式核函數(shù)：

讓你可以選擇c和d的值。在上面的三維投影問題中，我使用的就是c=0、d=2的多項式核函數(shù)。

不過我們還沒有說完核函數(shù)的酷炫之處呢！

還記得我之前提過投影至無窮維？你應該已經(jīng)猜到了吧，這需要正確的核函數(shù)。只需找到正確的核函數(shù)，我們就可以計算所需內(nèi)積，并不用真的投影輸入數(shù)據(jù)，也不用操心存儲無窮維度。

RBF核就常常用于特定的無窮維投影。我們這里就不介紹相關的數(shù)學了，如果你想深入數(shù)學，可以參考文章底部給出的資源。

你也許會納悶，我們?nèi)绾文軌蛴嬎銦o窮維上的點積？如果你為此困惑，可以想想無窮級數(shù)求和。

我們已經(jīng)回答了上一節(jié)提出的問題?？偨Y(jié)一下：

我們通常并不定義數(shù)據(jù)的投影。相反，我們從現(xiàn)有的核中選取一個，加以微調(diào)，以找到最匹配數(shù)據(jù)的核函數(shù)。

我們當然可以定義自己的核，甚至自行投影。但許多情形下不必如此。至少，我們從嘗試現(xiàn)有核函數(shù)開始。

如果存在我們想要的投影的核，我們將使用它，因為核經(jīng)?？旌芏?。

RBF核可以投影數(shù)據(jù)點至無窮維。

SVM庫

你可以從以下SVM庫開始上手：

libSVM

SVM-Light

SVMTorch

scikit-learn之類的許多通用ML庫也提供了SVM模塊，這些模塊常常是專門SVM庫的封裝。我建議從久經(jīng)考驗的libSVM開始。

libSVM可以作為命令行工具使用，也提供了Python、Java、Matlab封裝。只要你的數(shù)據(jù)文件的格式可以被libSVM理解（詳見README），你就可以開始使用了。

事實上，如果你需要快速了解不同核、C值等對尋找分割邊界的影響，你可以嘗試libSVM主頁上的“圖形界面”。標記數(shù)據(jù)點分類，選擇SVM參數(shù)，然后點擊運行（Run）！

這個可視化工具的魅力無可阻擋，下面是我標記的一些數(shù)據(jù)點：

沒錯，我要給SVM一點難度。

接著我嘗試了一些核：

這個可視化工具不顯示分割邊界，但會顯示SVM學習的屬于某一特定標簽的區(qū)域。如你所見，線性核完全忽略了紅點。它認為整個空間是黃色的（更準確地說，黃綠色）。而RBF核干凈利落地為紅點劃出了一個圈。

有幫助的資源

本文主要依靠可視化的直觀理解。雖然這是很棒的初步理解概念的方式，我仍然強烈建議你深入一點。畢竟有些地方可視化的直觀理解是不夠的。其中一些概念用于決定折衷優(yōu)化，除非你查看數(shù)學，否則很難直觀地理解一些結(jié)果。

另外，數(shù)學也有助于理解核函數(shù)。例如，本文對RBF核的介紹一筆帶過。我希望它的“神秘”——和無窮維投影的關系，以及最后數(shù)據(jù)集上奇妙的結(jié)果（“圈”）——能讓你想要更深入地了解它。

推薦的資源

視頻講座：Learning from Data—— Yaser Abu-Mostafa的第14講至第16講討論了SVM以及核函數(shù)。如果你正在找ML的入門講座，我強烈推薦整個系列，它在數(shù)學性和直觀性上平衡得很好。

書籍：統(tǒng)計學習基礎—— Trevor Hastie、Robert Tibshirani、Jerome Friedman著。第4章介紹了SVM背后的基本想法，而第12章全面討論了SVM的細節(jié)。

快樂（機器）學習！