從大間隔分類器到核函數(shù)：全面理解支持向量機(jī)
自從 Statsbot 團(tuán)隊(duì)發(fā)表了關(guān)于(時(shí)間序列的異常檢測(cè)(time series anomaly detection)的文章之后，很多讀者要求我們介紹支持向量機(jī)方法。因此 Statsbot 團(tuán)隊(duì)將在不使用高深數(shù)學(xué)的前提下向各位讀者介紹 SVM，并分享有用的程序庫(kù)和資源。
如果你曾經(jīng)使用機(jī)器學(xué)習(xí)執(zhí)行分類任務(wù)，應(yīng)該會(huì)聽(tīng)說(shuō)支持向量機(jī)(SVM)。這個(gè)算法的歷史已經(jīng)有五十出頭，它們隨著時(shí)間不斷在進(jìn)化，并適應(yīng)于各種其它問(wèn)題比如回歸、離群值分析和排序等。
在很多深度學(xué)習(xí)開(kāi)發(fā)者的模型儲(chǔ)備中，SVM 都是他們的至愛(ài)。在 [24]7(https://www.247-inc.com/)，我們也將使用它們解決多個(gè)問(wèn)題。
我將更專注于培養(yǎng)直覺(jué)理解而不是嚴(yán)密的數(shù)學(xué)推導(dǎo)，這意味著我們會(huì)盡可能跳過(guò)數(shù)學(xué)細(xì)節(jié)而建立其工作方式的理論的直觀理解。
一、分類問(wèn)題
假設(shè)你們的大學(xué)開(kāi)設(shè)了一項(xiàng)機(jī)器學(xué)習(xí)課程，課程的講師發(fā)現(xiàn)那些擅長(zhǎng)數(shù)學(xué)或者統(tǒng)計(jì)學(xué)的學(xué)生往往表現(xiàn)的***。課程結(jié)束之后，老師們記錄了注冊(cè)課程的學(xué)生的分?jǐn)?shù)，他們對(duì)每一個(gè)學(xué)生根據(jù)其在機(jī)器學(xué)習(xí)課程上的表現(xiàn)加上了一個(gè)標(biāo)簽：「好」或者「壞」。
現(xiàn)在，老師們想要確定數(shù)學(xué)和統(tǒng)計(jì)學(xué)的得分與機(jī)器學(xué)習(xí)課程表現(xiàn)的關(guān)系?；蛟S，根據(jù)他們的統(tǒng)計(jì)結(jié)果，他們會(huì)在學(xué)生注冊(cè)課程時(shí)加上一個(gè)前提條件限制。
他們會(huì)怎么做呢?首先把他們的數(shù)據(jù)表示出來(lái)，我們可以畫(huà)一個(gè)二維圖，一個(gè)坐標(biāo)軸表示數(shù)學(xué)成績(jī)，另一個(gè)表示統(tǒng)計(jì)學(xué)成績(jī)。每個(gè)學(xué)生的具體成績(jī)作為一個(gè)點(diǎn)在圖中表示。
點(diǎn)的顏色(綠色或者紅色)表示學(xué)生在機(jī)器學(xué)習(xí)課程中的表現(xiàn)：「好」或者「壞」。將圖畫(huà)出來(lái)的話應(yīng)該是這樣的：
當(dāng)一個(gè)學(xué)生要求注冊(cè)課程的時(shí)候，講師將會(huì)要求她提供數(shù)學(xué)和統(tǒng)計(jì)學(xué)的成績(jī)。根據(jù)他們已有的數(shù)據(jù)，他們將對(duì)她在機(jī)器學(xué)習(xí)課程上的表現(xiàn)作出合理的猜測(cè)。我們真正想要的是一類以形式(math_score,stats_score)饋送到「分?jǐn)?shù)元組」的算法。這個(gè)算法能告訴你一個(gè)學(xué)生在圖中是以一個(gè)紅點(diǎn)還是一個(gè)綠點(diǎn)表示(紅/綠可理解為類別或者標(biāo)簽)。當(dāng)然，這個(gè)算法已經(jīng)以某種方式包含了訓(xùn)練數(shù)據(jù)的特征。
在這個(gè)案例中，一個(gè)好的算法將能尋找在紅色和綠色群集之間的分界線(即決策邊界)，然后確定一個(gè)分?jǐn)?shù)多元組將依賴于哪一側(cè)。我們選擇綠色方或者紅色方的其中一側(cè)作為他在這項(xiàng)課程中最可能的表現(xiàn)水平標(biāo)簽。
這條線稱為決策邊界(因?yàn)樗鼘⒉煌瑯?biāo)記的群集分離開(kāi)來(lái))或者分類器(我們用它來(lái)將點(diǎn)集分類)。圖中展示了這個(gè)問(wèn)題中可能的兩個(gè)分類器。
二、好分類器和壞分類器
有一個(gè)很有趣的問(wèn)題：以上兩條線都將紅色和綠色的點(diǎn)群集分離開(kāi)來(lái)。有什么合理依據(jù)能讓我們選擇其中一個(gè)而舍棄另一個(gè)嗎?
要注意一個(gè)分類器的價(jià)值并不在于它能將訓(xùn)練數(shù)據(jù)分離的多好。我們最終是希望它能將尚未見(jiàn)過(guò)的數(shù)據(jù)分離(即測(cè)試數(shù)據(jù))。因此我們需要選擇能捕捉訓(xùn)練數(shù)據(jù)的普遍模式的那條線，而這條線更可能在測(cè)試數(shù)據(jù)中表現(xiàn)的更好。
以上所示的***條線看起來(lái)有些許偏差，其下半部分看起來(lái)過(guò)于接近紅點(diǎn)群集，其上半部分過(guò)于接近綠點(diǎn)群集。當(dāng)然它確實(shí)很***的將訓(xùn)練數(shù)據(jù)分離開(kāi)來(lái)，但是如果在測(cè)試數(shù)據(jù)中遇到了有一個(gè)點(diǎn)離群集稍遠(yuǎn)的情況，它很有可能會(huì)將其加上錯(cuò)誤的標(biāo)記。
而第二的點(diǎn)就沒(méi)有這樣的問(wèn)題。例如，下圖為兩個(gè)分類器分離方塊點(diǎn)群集的結(jié)果展示。
第二條線在正確分離訓(xùn)練數(shù)據(jù)的同時(shí)也盡可能的遠(yuǎn)離兩個(gè)群集，即采取***間隔的策略。處于兩個(gè)群集的正中間位置能降低犯錯(cuò)的風(fēng)險(xiǎn)，可以說(shuō)，這給了每一個(gè)類的數(shù)據(jù)分布更多的浮動(dòng)空間，因此它能更好的泛化到測(cè)試數(shù)據(jù)中。
SVM 就是試圖尋找第二類決策邊界的算法。上文我們只是通過(guò)目測(cè)選擇更好的分類器，但實(shí)際上為了在一般案例中應(yīng)用，我們需要將其隱含原理定義地更加精確。以下將簡(jiǎn)要說(shuō)明 SVM 是如何工作的：
- 尋找能準(zhǔn)確分離訓(xùn)練數(shù)據(jù)的決策邊界;
- 在所有這些決策邊界中選擇能***化與最近鄰點(diǎn)的距離的決策邊界。
那些定義了這條決策邊界的最近鄰點(diǎn)被稱作支持向量。而決策邊界周圍的區(qū)域被定義為間隔。下圖展示了支持向量和對(duì)應(yīng)的第二條決策邊界：黑色邊界的點(diǎn)(有兩個(gè))和間隔(陰影區(qū)域)。
支持向量機(jī)提供了一個(gè)方法在多個(gè)分類器中尋找能更準(zhǔn)確分離測(cè)試數(shù)據(jù)的分類器。雖然上圖中的決策邊界和數(shù)據(jù)是處于二維空間的，但是必須注意 SVM 實(shí)際上能在任何維度的數(shù)據(jù)中工作，在這些維度中，它們尋找的是和二維空間決策邊界類似的結(jié)構(gòu)。
比如，在三維空間中它們尋找的是一個(gè)分離面(后面將簡(jiǎn)要提到)，在更高維空間中它們尋找的是一個(gè)分離超平面，即將二維決策邊界和三維分離面推廣到任意維度的結(jié)構(gòu)。一個(gè)可以被決策邊界(或者在普遍意義上，一個(gè)分離超平面)被稱作線性可分?jǐn)?shù)據(jù)。分離超平面被稱作線性分類器。
三、容錯(cuò)性和軟間隔分類器
我們?cè)谏弦还?jié)看到的是一個(gè)線性可分?jǐn)?shù)據(jù)的簡(jiǎn)單例子，但現(xiàn)實(shí)中的數(shù)據(jù)通常是很凌亂的。你也很可能經(jīng)常遇到一些不能正確線性分類的例子。這里展示了一個(gè)這樣的例子：
很顯然，使用一個(gè)線性分類器通常都無(wú)法***的將標(biāo)簽分離，但我們也不想將其完全拋棄不用，畢竟除了幾個(gè)錯(cuò)點(diǎn)它基本上能很好的解決問(wèn)題。那么 SVM 會(huì)如何處理這個(gè)問(wèn)題呢?SVM 允許你明確規(guī)定允許多少個(gè)錯(cuò)點(diǎn)出現(xiàn)。你可以在 SVM 中設(shè)定一個(gè)參數(shù)「C」;從而你可以在兩種結(jié)果中權(quán)衡：
- 擁有很寬的間隔;
- 精確分離訓(xùn)練數(shù)據(jù);
C 的值越大，意味著在訓(xùn)練數(shù)據(jù)中允許的誤差越少。
必需強(qiáng)調(diào)一下這是一個(gè)權(quán)衡的過(guò)程。如果想要更好地分類訓(xùn)練數(shù)據(jù)，那么代價(jià)就是間隔會(huì)更寬。以下幾個(gè)圖展示了在不同的 C 值中分類器和間隔的變化(未顯示支持向量)。
注意決策邊界隨 C 值增大而傾斜的方式。在更大的 C 值中，它嘗試將右下角的紅點(diǎn)盡可能的分離出來(lái)。但也許我們并不希望在測(cè)試數(shù)據(jù)中也這么做。***張圖中 C=0.01，看起來(lái)更好的抓住了普遍的趨勢(shì)，雖然跟更大的 C 值相比，它犧牲了精確性。
考慮到這是一個(gè)權(quán)衡方法，需要注意間隔如何隨著 C 值的增大而縮小。
在之前的例子中，間隔內(nèi)是不允許任何錯(cuò)點(diǎn)的存在的。在這里我們看到，同時(shí)擁有好的分離邊界和沒(méi)有錯(cuò)點(diǎn)的間隔是基本不可能的。由于現(xiàn)實(shí)世界中的數(shù)據(jù)幾乎不可能精確的分離，確定一個(gè)合適的 C 值很重要且很有實(shí)際意義。我們往往使用交叉驗(yàn)證選擇合適的 C 值。
四、線性不可分?jǐn)?shù)據(jù)
我們已經(jīng)介紹過(guò)支持向量機(jī)如何處理***或者接近***線性可分?jǐn)?shù)據(jù)，那對(duì)于那些明確的非線性可分?jǐn)?shù)據(jù)，SVM 又是怎么處理的呢?畢竟有很多現(xiàn)實(shí)世界的數(shù)據(jù)都是這一類型的。當(dāng)然，尋找一個(gè)分離超平面已經(jīng)行不通了，這反而突出了 SVMs 對(duì)這種任務(wù)有多擅長(zhǎng)。
這里有一個(gè)關(guān)于線性不可分?jǐn)?shù)據(jù)的例子(這是著名的異或問(wèn)題變體)，圖中展示了線性分類器 SVM 的結(jié)果：
這樣的結(jié)果并不怎么樣，在訓(xùn)練數(shù)據(jù)中只能得到 75% 的準(zhǔn)確率，這是使用決策邊界能得到的***結(jié)果。此外，決策邊界和一些數(shù)據(jù)點(diǎn)過(guò)于接近，甚至將一些點(diǎn)分割開(kāi)來(lái)。
現(xiàn)在輪到我最喜歡 SVM 的部分登場(chǎng)了。我們目前擁有：一項(xiàng)擅長(zhǎng)尋找分離超平面的技術(shù)，以及無(wú)法線性分離的數(shù)據(jù)。那么怎么辦?
當(dāng)然是，將數(shù)據(jù)映射到另一個(gè)空間中使其線性可分然后尋找分離超平面!我會(huì)一步一步的詳細(xì)介紹這個(gè)想法。
仍然從上圖中的數(shù)據(jù)集為例，然后將其映射到三維空間中，其中新的坐標(biāo)為：
下圖中展示了映射數(shù)據(jù)的表示，你發(fā)現(xiàn)了能塞進(jìn)一個(gè)平面的地方了嗎?
讓我們開(kāi)始在上面運(yùn)行 SVM：
標(biāo)簽分離很***，接下來(lái)將平面映射回初始的二維空間中看看決策邊界是什么樣子：
在訓(xùn)練數(shù)據(jù)中得到了 100% 的準(zhǔn)確率，而且分離邊界并不會(huì)過(guò)于接近數(shù)據(jù)點(diǎn)，太棒了!初始空間中決策邊界的形狀依賴于映射函數(shù)的形式。在映射空間中，分離邊界通常是一個(gè)超平面。
要記住，映射數(shù)據(jù)的最主要的目的是為了使用 SVM 尋找分離超平面。
當(dāng)將分離超平面映射回初始空間時(shí)，分離邊界不再是一條線了，間隔和支持向量也變得不同。根據(jù)視覺(jué)直覺(jué)，它們?cè)谟成淇臻g的形態(tài)是很好理解的。
看看它們?cè)谟成淇臻g中的樣子，再看看在初始空間。3D 間隔(為了避免視覺(jué)混亂，沒(méi)有加上陰影)是分離超平面之間的區(qū)域。
在映射空間中有 4 個(gè)支持向量，這很合理，它們分布在兩個(gè)平面上以確定間隔。在初始空間中，它們依然在決策邊界上，但是看起來(lái)數(shù)量并不足以確定***間隔。
讓我們回過(guò)頭分析一下：
1. 如何確定要將數(shù)據(jù)映射到什么樣的空間?
我之前已經(jīng)很明確的提過(guò)，在某個(gè)地方出現(xiàn)了根號(hào) 2!在這個(gè)例子中，我想展示一下向高維空間映射的過(guò)程，因此我選了一個(gè)很具體的映射。一般而言，這是很難確定的。不過(guò)，多虧了 over』s theorem，我們能確定的是通過(guò)將數(shù)據(jù)映射到高維空間確實(shí)更可能使數(shù)據(jù)線性可分。
2. 所以我要做的就是映射數(shù)據(jù)然后運(yùn)行 SVM?
不是。為了使上述例子更好理解，我解釋的好像我們需要先將數(shù)據(jù)映射。如果你自行將數(shù)據(jù)映射，你要怎么表征無(wú)窮維空間呢?看起來(lái) SVMs 很擅長(zhǎng)這個(gè)，是時(shí)候看看算法的核函數(shù)了。
五、核函數(shù)
最終還是這個(gè)獨(dú)家秘方才使得 SVM 有了打標(biāo)簽的能力。在這里我們需要討論一些數(shù)學(xué)。讓我們盤查一下目前我們所見(jiàn)過(guò)的：
- 對(duì)于線性可分?jǐn)?shù)據(jù)，SVM 工作地非常出色。
- 對(duì)于近似線性可分?jǐn)?shù)據(jù)，只要只用正確的 C 值，SVM 仍然可以工作地很好。
- 對(duì)于線性不可分?jǐn)?shù)據(jù)，可以將數(shù)據(jù)映射到另一個(gè)空間使數(shù)據(jù)變得***或者幾乎***線性可分，將問(wèn)題回歸到了 1 或者 2。
首先 SVM 一個(gè)非常令人驚喜的方面是，其所有使用的數(shù)學(xué)機(jī)制，如精確的映射、甚至是空間的維度都沒(méi)有顯式表示出來(lái)。你可以根據(jù)數(shù)據(jù)點(diǎn)(以向量表示)的點(diǎn)積將所有的數(shù)學(xué)寫(xiě)出來(lái)。例如 P 維的向量 i 和 j，***個(gè)下標(biāo)區(qū)分?jǐn)?shù)據(jù)點(diǎn)，第二個(gè)下標(biāo)表示維度：
點(diǎn)積的定義如下：
如果數(shù)據(jù)集中有 n 個(gè)點(diǎn)，SVM 只需要將所有點(diǎn)兩兩配對(duì)的點(diǎn)積以尋找分類器。僅此而已。當(dāng)我們需要將數(shù)據(jù)映射到高維空間的時(shí)候也是這樣，不需要向 SVM 提供準(zhǔn)確的映射，而是提供映射空間中所有點(diǎn)兩兩配對(duì)的點(diǎn)積。
重提一下我們之前做過(guò)的映射，看看能不能找到相關(guān)的核函數(shù)。同時(shí)我們也會(huì)跟蹤映射的計(jì)算量，然后尋找點(diǎn)積，看看相比之下，核函數(shù)是怎么工作的。
對(duì)于任意一個(gè)點(diǎn) i：
其對(duì)應(yīng)的映射點(diǎn)的坐標(biāo)為：
我們需要進(jìn)行以下操作以完成映射：
- 得到新坐標(biāo)的***個(gè)維度：1 次乘法
- 第二個(gè)維度：1 次乘法
- 第三個(gè)維度：2 次乘法
加起來(lái)總共是 1+1+2=4 次乘法，在新坐標(biāo)中的點(diǎn)積是：
為了計(jì)算兩個(gè)點(diǎn) i 和 j 的點(diǎn)積，我們需要先計(jì)算它們的映射。因此總共是 4+4=8 次乘法，然后點(diǎn)積的計(jì)算包含了 3 次乘法和 2 次加法。
- 乘法：8(映射)+3(點(diǎn)積)=11 次乘法
- 加法：2 次(點(diǎn)積之間)
總數(shù)為 11+2=13 次計(jì)算，而以下這個(gè)核函數(shù)將給出相同的結(jié)果：
首先在初始空間中計(jì)算向量的點(diǎn)積，然后將結(jié)果進(jìn)行平方。把式子展開(kāi)然后看看是否正確：
確實(shí)是這樣。這個(gè)式子需要多少次計(jì)算呢?看看以上式子的第二步。在二維空間中計(jì)算點(diǎn)積只需要 2 次乘法和 1 次加法，平方運(yùn)算是另一次乘法。因此，總計(jì)為：
- 乘法：2(初始空間的點(diǎn)積)+1(平方運(yùn)算)=3 次乘法
- 加法：1(初始空間的點(diǎn)積)
總數(shù)為 3+1=4 次計(jì)算。只有之前計(jì)算量的 31%。
看起來(lái)使用核函數(shù)計(jì)算所需要的點(diǎn)積會(huì)更快。目前看來(lái)這似乎并不是什么重要的選擇：只不過(guò)是 4 次和 13 次的比較，但在輸入點(diǎn)處于高維度，而映射空間有更高的維度的情形中，大型數(shù)據(jù)集的計(jì)算所節(jié)省的計(jì)算量能大大加快訓(xùn)練的速度。因此使用核函數(shù)有相當(dāng)大的優(yōu)勢(shì)。
大部分 SVM 程序庫(kù)已經(jīng)經(jīng)過(guò)預(yù)包裝并包含了一些很受歡迎的核函數(shù)比如多項(xiàng)式，徑向基函數(shù)(RBF)，以及 Sigmoid 函數(shù)。當(dāng)不使用映射的時(shí)候(比如文中***個(gè)例子)，我們就在初始空間中計(jì)算點(diǎn)積，我們之前提過(guò)，這叫做線性核函數(shù)(linear kernel)。很多核函數(shù)能提供額外的手段進(jìn)一步調(diào)整數(shù)據(jù)。比如，多項(xiàng)式核函數(shù)：
該多項(xiàng)式允許選擇 c 和 d(多項(xiàng)式的自由度)的值。在上述 3D 映射的例子中，我使用的值為 c=0，d=2。但是核函數(shù)的優(yōu)點(diǎn)遠(yuǎn)遠(yuǎn)不止于此!
還記得我之前提到向無(wú)窮維空間映射的情況嗎?只需要知道正確的核函數(shù)就可以了。因此，我們并不需要將輸入數(shù)據(jù)映射，或者困惑無(wú)窮維空間的問(wèn)題。
核函數(shù)就是為了計(jì)算當(dāng)數(shù)據(jù)確實(shí)被映射的時(shí)候，內(nèi)積的形式。RBF 核函數(shù)通常在一些具體的無(wú)窮維映射問(wèn)題中應(yīng)用。在這里我們不討論數(shù)學(xué)細(xì)節(jié)，但會(huì)在文末提到一些參考文獻(xiàn)。
如何在空間維度為無(wú)窮的情況計(jì)算點(diǎn)積呢?如果你覺(jué)得困惑，回想一下無(wú)窮序列的加法是如何計(jì)算的，相似的道理。雖然在內(nèi)積中有無(wú)窮個(gè)項(xiàng)，但是能利用一些公式將它們的和算出來(lái)。
這解答了我們前一節(jié)中提到的問(wèn)題。總結(jié)一下：
- 我們通常不會(huì)為數(shù)據(jù)定義一個(gè)特定的映射，而是從幾個(gè)可用的核函數(shù)中選擇，在某些例子中需要做一些參數(shù)調(diào)整，***選出最適合數(shù)據(jù)的核函數(shù)。
- 我們并不需要定義核函數(shù)或者自行將數(shù)據(jù)映射。
- 如果有可用的核函數(shù)，使用它將使計(jì)算更快。
- RBF 核函數(shù)可將數(shù)據(jù)映射到無(wú)窮維空間中。
六、SVM 庫(kù)
你可以在很多 SVM 庫(kù)中進(jìn)行選擇，并開(kāi)始你的實(shí)驗(yàn)：
- libSVM
- SVM—Light
- SVMTorch
很多普適的機(jī)器學(xué)習(xí)庫(kù)比如 scikit-learn 也提供 SVM 模塊，通常在專用的 SVM 庫(kù)中封裝。我推薦使用經(jīng)驗(yàn)證測(cè)試可行的 libSVM。
libSVM 通常是一個(gè)命令行工具，但下載包通常捆綁封裝了 Python、Java 和 MATLAB。只要將你的數(shù)據(jù)文件經(jīng) libSVM 格式化后(下載文件中 README 將解釋這一部分，以及其它可選項(xiàng))，就可以開(kāi)始試驗(yàn)了。
實(shí)際上，如果你想快速理解不同核函數(shù)和 c 值等如何影響決策邊界，試試登陸「Graphical Interface」的 home page。在上面標(biāo)記幾類數(shù)據(jù)點(diǎn)，選擇 SVM 參數(shù)，然后運(yùn)行就可以了。我很快去嘗試了一下：
我給 SVM 出了個(gè)難題，然后我嘗試了幾個(gè)不同的核函數(shù)：
網(wǎng)站界面并沒(méi)有展示分離邊界，但會(huì)顯示 SVM 判斷分類標(biāo)簽的結(jié)果。正如你所見(jiàn)，線性核函數(shù)完全忽略了紅點(diǎn)，認(rèn)為整個(gè)空間中只有黃點(diǎn)。而 RBF 核函數(shù)則完整的為紅點(diǎn)劃出了兩個(gè)圈!
原文：http://www.kdnuggets.com/2017/08/support-vector-machines-learning-svms-examples.html
【本文是51CTO專欄機(jī)構(gòu)“機(jī)器之心”的原創(chuàng)譯文，微信公眾號(hào)“機(jī)器之心( id: almosthuman2014)”】
