機器之心Pro2017-09-18 15:16:51本文將嘗試對 SVMs 的工作方式進行更高層次的理解。我將更專注於培養直覺理解而不是嚴密性。這意味著會盡可能跳過數學細節而建立其工作方式的理論的直觀理解。
自從Statsbot團隊發表了關於time series anomaly detection， （時間序列的異常檢測）的文章之後，很多讀者要求我們介紹支援向量機方法。是時候滿足你們的要求了，我將在不使用高深數學的前提下向你們介紹 SVM，分享有用的程式庫和資源幫助你們入門。
如果你曾經使用機器學習進行分類，應該會聽說支援向量機（SVM）。這個演算法的歷史已經有五十出頭，它們隨著時間不斷在進化，並適應於各種其它問題比如迴歸，離群值分析和排序。
在很多深度學習開發者的武器庫中，SVMs 都是他們的至愛。在 ［24］7，我們也將使用它們解決多個問題。我將更專注於培養直覺理解而不是嚴密性。這意味著我們會盡可能跳過數學細節而建立其工作方式的理論的直觀理解。
分類問題
假設你們的大學開設了一項機器學習課程，課程的講師發現那些擅長數學或者統計學的學生往往表現的最好。課程結束之後，他們記錄了註冊課程的學生的分數。他們對每一個學生根據其在機器學習課程上的表現加上了一個標籤：「好」或者「壞」。
現在，他們想要確定數學和統計學的得分與機器學習課程表現的關係。或許，根據他們的統計結果，他們會在學生註冊課程時加上一個前提條件限制。
他們會怎麼做呢？首先把他們的資料表示出來，我們可以畫一個二維圖，一個座標軸表示數學成績，另一個表示統計學成績。每個學生的具體成績作為一個點在圖中表示。
點的顏色（綠色或者紅色）表示學生在機器學習課程中的表現：「好」或者「壞」。將圖畫出來的話應該是這樣的：
當一個學生要求註冊課程的時候，講師將會要求她提供數學和統計學的成績。根據他們已有的資料，他們將對她在機器學習課程上的表現作出合理的猜測。我們真正想要的是一類以「分數多元組」的形式饋送（math_score，stats_score）的演算法。這個演算法能告訴你一個學生在圖中是以一個紅點還是一個綠點表示（紅/綠可理解為類別或者標記）。當然，這個演算法已經以某種方式包含了訓練資料的特徵。
在這個案例中，一個好的演算法將能尋找在紅色和綠色群集之間的分界線，然後確定一個分數多元組將依賴於哪一側。我們選擇綠色方或者紅色方的其中一側作為她在這項課程中最可能的表現水平的標誌。
這條線稱為分界線（因為它將不同標記的群集分離開來）或者分類器（我們用它來將點集分類）。圖中展示了這個問題中可能的兩個分類器。
好分類器 vs 壞分類器
有一個很有趣的問題：以上兩條線都將紅色和綠色的點群集分離開來。有什麼合理依據能讓我們選擇其中一個而捨棄另一個嗎？
要注意一個分類器的價值並不在於它能將訓練資料分離的多好。我們最終是希望它能將尚未見過的資料分離（即測試資料）。因此我們需要選擇能捕捉訓練資料的普遍模式的那條線，而這條線更可能在測試資料中表現的更好。
以上所示的第一條線看起來有些許偏差，其下半部分看起來過於接近紅點群集，其上半部分過於接近綠點群集。當然它確實很完美的將訓練資料分離開來，但是如果在測試資料中遇到了有一個點離群集稍遠的情況，它很有可能會將其加上錯誤的標記。
而第二的點就沒有這樣的問題。例如，下圖中用兩個分類器分離方塊點群集的表現的結果展示。
第二條線在正確分離訓練資料的同時也儘可能的遠離兩個群集。處於兩個群集的正中間位置能降低犯錯的風險，可以說，這給了每一個類的資料分佈更多的擺動空間，因此它能更好的泛化到測試資料中。
SVMs 試圖尋找第二類分界線。原來我們只是透過目測選擇更好的分類器，但實際上為了在一般案例中應用，我們需要將其隱含原理定義的更加精確。以下將簡要說明 SVMs 是如何工作的：
1。 尋找能準確分離訓練資料的分界線；
2。 在所有這些分界線中選擇能最大化與最近鄰點的距離的分界線。
那些定義了這條分界線的最近鄰點被稱作支援向量。而分界線周圍的區域被定義為邊緣。
下圖展示了支援向量和對應的第二條分界線：黑色邊界的點（有兩個）和邊緣（陰影區域）。
支援向量機提供了一個方法在多個分類器中尋找能更準確的分離測試資料的分類器。
雖然上圖中的分界線和資料是處於二維空間的，但是必須注意 SVMs 實際上能在任何維度的資料中工作，在這些維度中，它們尋找的是二維空間分界線的類似結構。
比如，在三維空間中它們尋找的是一個分介面（後面將簡要提到），在更高維空間中它們尋找的是一個分界超平面-即將二維分界線和三維分介面推廣到任意維度的結構。
一個可以被分界線（或者在普遍意義上，一個分界超平面）被稱作線性可分資料。分界超平面被稱作線性分類器。
容錯性
我們在最後一節來看一個完美線性可分資料的簡單例子，雖然現實中的資料通常是很凌亂的。你也很可能經常遇到一些不能正確線性分類的例子。
這裡展示了一個這樣的例子：
很顯然，使用一個線性分類器通常都無法完美的將標籤分離，但我們也不想將其完全拋棄不用，畢竟除了幾個錯點它基本上能很好的解決問題。那麼 SVMs 會如何處理這個問題呢？SVMs 允許你明確規定允許多少個錯點出現。你可以在 SVM 中設定一個引數「C」；從而你可以在兩種結果中權衡：
1。 擁有很寬的邊緣；
2。 精確分離訓練資料；
C 的值越大，意味著在訓練資料中允許的錯點越少。
必需強調一下這是一個權衡的過程。如果想要更好的分類訓練資料，那麼代價就是邊緣會更寬。以下幾個圖展示了在不同的 C 值中分類器和邊緣的變化（未顯示支援向量）。
注意分界線隨 C 值增大而傾斜的方式。在更大的 C 值中，它嘗試將右下角的紅點儘可能的分離出來。但也許我們並不希望在測試資料中也這麼做。第一張圖中 C=0。01，看起來更好的抓住了普遍的趨勢，雖然跟更大的 C 值相比，它犧牲了精確性。
考慮到這是一個權衡方法，需要注意邊緣如何隨著 C 值的增大而縮小。
在之前的例子中，邊緣內是不允許任何錯點的存在的。在這裡我們看到，同時擁有好的分離邊界和沒有錯點的邊緣是基本不可能的。
由於現實世界中的資料幾乎不可能精確的分離，確定一個合適的 C 值很重要且很有實際意義，經常出現這樣的需求。我們往往使用交叉驗證選擇合適的 C 值。
非線性可分資料
我們已經介紹過支援向量機如何處理完美或者接近完美線性可分資料，那對於那些明確的非線性可分資料，SVMs 又是怎麼處理的呢？畢竟有很多現實世界的資料都是這一型別的。當然，尋找一個分界超平面已經行不通了，這反而突出了 SVMs 對這種任務有多擅長。
這裡有一個關於非線性可分資料的例子（這是著名的 XOR dataset 的變體），圖中展示了線性分類器 SVMs 的結果：
這樣的結果並不怎麼樣，在訓練資料中只能得到 75% 的準確率，這是使用分界線能得到的最好結果。此外，分界線和一些資料點過於接近，甚至將一些點分割開來。
我們需要做的更好。
現在輪到我最喜歡的 SVMs 的部分登場了。我們目前擁有：一項擅長尋找分界超平面的技術，以及無法線性分離的資料。那麼怎麼辦？
當然是，將資料投射到另一個空間中使其線性可分然後尋找分界超平面！
我會一步一步的詳細介紹這個想法。
仍然從上圖中的資料集為例，然後將其投射到三維空間中，其中新的座標為：
下圖中展示了投射資料的表示，你發現了能塞進一個平面的地方了嗎？
讓我們開始在上面執行 SVMs：
Bingo！標籤分離很完美，接下來將平面投射回初始的二維空間中看看分離介面是什麼樣子的：
在訓練資料中得到了 100% 的準確率，而且分離邊界並不會過於接近資料點，太棒了！
初始空間中的分離邊界的形狀依賴於投射的形式。在投射空間中，分離邊界通常是一個超平面。
要記住，投射資料的最主要的目的是為了使用 SVMs 尋找分界超平面的超能力。
當將分界超平面映射回初始空間時，分離邊界不再是一條線了，邊緣和支援向量也變得不同。根據視覺直覺，它們在投射空間的形態是很好理解的。
看看它們在投射空間中的樣子，再看看在初始空間。3D 邊緣（為了避免視覺混亂，沒有加上陰影）是分界超平面之間的區域。
在投射空間中有 4 個支援向量，這很合理，它們分佈在兩個平面上以確定邊緣。在初始空間中，它們依然在邊緣上，但是看起來數量並不足以確定邊緣。
讓我們回過頭分析一下：
1。 如何確定要將資料投射到什麼樣的空間？
我之前已經很明確的提過-在某個地方出現了根號 2！
在這個例子中，我想展示一下向高維空間投射的過程，因此我選了一個很具體的投射。一般而言，這是很難確定的。不過，多虧了 over』s theorem，我們能確定的是透過將資料投射到高維空間確實更可能使資料線性可分。
2。 所以我要做的就是投射資料然後執行 SVM？
不是。為了使上述例子更好理解，我解釋的好像我們需要先將資料投射。如果你自行將資料投射，你要怎麼表徵無窮維空間呢？看起來 SVMs 很擅長這個，是時候看看演算法的核心了。
核心
最終還是這個獨家秘方才使得 SVMs 有了打標籤的能力。在這裡我們需要討論一些數學。
讓我們盤查一下目前我們所見過的：
1。 對於線性可分資料 SVMs 工作的非常出色。
2。 對於幾乎線性可分資料，只要只用正確的 C 值，SVMs 仍然可以工作的很好。
3。 對於非線性可分資料，可以將資料投射到另一個空間使資料變得完美或者幾乎完美線性可分，將問題迴歸到了 1 或者 2。
首先，讓我們稍微離題一會。
SVMs 的一個非常令人驚喜的方面是，其所有使用的數學機構，如精確的投射，甚至是空間的維度，都沒有顯式表示出來。你可以根據資料點（以向量表示）的點積將所有的數學寫出來。例如 P 維的向量 i 和 j，第一個下標區分資料點，第二個下標表示維度：
點積的定義如下：
如果資料集中有 n 個點，SVM 只需要將所有點兩兩配對的點積以尋找分類器。僅此而已。當我們需要將資料投射到高維空間的時候也是這樣，不需要向 SVM 提供準確的投射，而是提供投射空間中所有點兩兩配對的點積。
重提一下我們之前做過的投射，看看能不能找到相關的核心。同時我們也會跟蹤投射的計算量，然後尋找點積，看看相比之下，核心是怎麼工作的。
對於任意一個點 i：
其對應的投射點的座標為：
我們需要進行以下操作以完成投射：
得到新座標的第一個維度：1 次乘法
第二個維度：1 次乘法
第三個維度：2 次乘法
加起來總共是 1+1+2=4 次乘法
在新座標中的點積是：
為了計算兩個點 i 和 j 的點積，我們需要先計算它們的投射。因此總共是 4+4=8 次乘法，然後點積的計算包含了 3 次乘法和 2 次加法。
總計為，
乘法：8（投射）+3（點積）=11 次乘法
加法：2 次（點積之間）
總數為 11+2=13 次計算
而以下這個核心函式將給出相同的結果：
首先在初始空間中計算向量的點積，然後將結果進行平方。
把式子展開然後看看是否正確：
確實是這樣。這個式子需要多少次計算呢？看看以上式子的第二步。在二維空間中計算點積只需要 2 次乘法和 1 次加法，平方運算是另一次乘法。
因此，總計為：
乘法：2（初始空間的點積）+1（平方運算）=3 次乘法
加法：1（初始空間的點積）
看起來使用核心函式計算所需要的點積會更快。目前看來這似乎並不是什麼重要的選擇：只不過是 4 次和 13 次的比較，但在輸入點處於高維度，而投射空間有更高的維度的情形中，大型資料集的計算所節省的計算量能大大加快訓練的速度。因此使用核心函式有相當大的優勢。
大部分 SVM 程式庫已經經過預包裝幷包含了一些很受歡迎的核心函式比如多項式，徑向基函式（RBF），以及 Sigmoid 函式。當不使用投射的時候（比如文中第一個例子），我們就在初始空間中計算點積，我們之前提過，這叫做線性核心。
很多核心函式能提供額外的手段進一步調整資料。比如，多項式核心：
該多項式允許選擇 c 和 d（多項式的度）的值。在上述 3D 投射的例子中，我使用的值為 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 格式化後（下載檔案中 README 將解釋這一部分，以及其它可選項），就可以開始試驗了。
實際上，如果你想快速獲得不同核心函式，不同 c 值等是如何影響分離邊界的理解，試試登陸「Graphical Interface」的 home page。在上面標記幾類資料點，選擇 SVM 引數，然後執行就可以了。
我很快去嘗試了一下：
我給 SVM 出了個難題。
然後我嘗試了幾個不同的核心函式：
網站介面並沒有展示分離邊界，但會顯示 SVMs 判斷分類標籤的結果。正如你所見，線性核心函式完全忽略了紅點，認為整個空間中只有黃點。而 RBF 核心函式則完整的為紅點劃出了兩個圈！
