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

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

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

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

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

分類問題

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

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

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

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

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

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

在這個(gè)例子中，找到一條紅聚類和綠聚類之間的直線，然后判斷成績(jī)?cè)M位于線的哪一邊，是一個(gè)好算法。

這里的直線是我們的分界（separating boundary）（因?yàn)樗蛛x了標(biāo)簽）或者分類器（classifier）（我們使用它分類數(shù)據(jù)點(diǎn)）。上圖顯示了兩種可能的分類器。

好 vs 差的分類器

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

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

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

第二條線沒有這個(gè)問題。

我們來(lái)看一個(gè)例子。下圖中兩個(gè)方形的測(cè)試數(shù)據(jù)點(diǎn)，兩條線分配了不同的標(biāo)簽。顯然，第二條線的分類更合理。

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

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

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

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

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

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

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

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

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

允許誤差

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

下圖就是一個(gè)例子。

顯然，如果我們使用一個(gè)線性分類器，我們將永遠(yuǎn)不能完美地分割數(shù)據(jù)點(diǎn)。我們同樣不想干脆拋棄線性分類器，因?yàn)槌艘恍┏鲕墧?shù)據(jù)點(diǎn)，線性分類器確實(shí)看起來(lái)很適合這個(gè)問題。

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

較寬的間隔。

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

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

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

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

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

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

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

非線性可分?jǐn)?shù)據(jù)

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

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

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

注意，關(guān)鍵的地方來(lái)了！我們已經(jīng)有了一項(xiàng)非常擅長(zhǎng)尋找超平面的技術(shù)，但是我們的數(shù)據(jù)卻是非線性可分的。所以我們?cè)撛趺崔k？將數(shù)據(jù)投影到一個(gè)線性可分的空間，然后在那個(gè)空間尋找超平面！

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

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

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

讓我們?cè)谄渖线\(yùn)行SVM：

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

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

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

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

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

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

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

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

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

看起來(lái)我找了一個(gè)非常特定的解——其中甚至還有√2。

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

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

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

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

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

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

核

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

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

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

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

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

看起來(lái)讓SVM得到普遍應(yīng)用的關(guān)鍵是投影到高維。這正是核的用武之地。

SVM優(yōu)化

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

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

wx - b = 0

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

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

相應(yīng)地，確定間隔的兩個(gè)超平面則可以表示為

wx - b = 1 wx - b = -1

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

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

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

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

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

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

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

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

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

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

核函數(shù)

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

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

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

相應(yīng)的投影為：

算下得到投影需要的運(yùn)算量：

計(jì)算第一維：1次乘法

計(jì)算第二維：1次乘法

計(jì)算第三維：2次乘法

共計(jì)1+1+2 =4次乘法

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

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

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

也就是：

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

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

共計(jì)11 + 2 =13次運(yùn)算

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

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

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

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

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

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

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

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

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

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

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

你也許會(huì)納悶，我們?nèi)绾文軌蛴?jì)算無(wú)窮維上的點(diǎn)積？如果你為此困惑，可以想想無(wú)窮級(jí)數(shù)求和。

我們已經(jīng)回答了上一節(jié)提出的問題。總結(jié)一下：

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

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

如果存在我們想要的投影的核，我們將使用它，因?yàn)楹私?jīng)?？旌芏?。

RBF核可以投影數(shù)據(jù)點(diǎn)至無(wú)窮維。

SVM庫(kù)

你可以從以下SVM庫(kù)開始上手：

libSVM

SVM-Light

SVMTorch

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

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

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

這個(gè)可視化工具的魅力無(wú)可阻擋，下面是我標(biāo)記的一些數(shù)據(jù)點(diǎn)：

沒錯(cuò)，我要給SVM一點(diǎn)難度。

接著我嘗試了一些核：

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

有幫助的資源

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

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

推薦的資源

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

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

快樂（機(jī)器）學(xué)習(xí)！