零基礎學SVM—Support Vector Machine系列之一

本文原作者耳東陳，本文原載於作者的知乎文章。AI 研習社已獲得轉載授權。如果你是一名模式識別專業的研究生，又或者你是機器學習愛好者，SVM是一個你避不開的問題。如果你只是有一堆數據需要SVM幫你處理一下，那麼無論是Matlab的SVM工具箱，LIBSVM還是python框架下的SciKit Learn都可以提供方便快捷的解決方案。但如果你要追求的不僅僅是會用，還希望挑戰一下「理解」這個層次，那麼你就需要面對一大堆你可能從來沒聽過的名詞，比如：非線性約束條件下的最優化、KKT條件、拉格朗日對偶、最大間隔、最優下界、核函數等等。這些名詞往往會跟隨一大堆天書一般的公式。如果你稍微有一點數學基礎，那麼單個公式你可能看得明白，但是怎麼從一個公式跳到另一個公式就讓人十分費解了，而最讓人糊塗的其實並不是公式推導，而是如果把這些公式和你腦子裡空間構想聯繫起來。我本人就是上述問題的受害者之一。我翻閱了很多關於SVM的書籍和資料，但沒有找到一份材料能夠在公式推導、理論介紹，系統分析、變數說明、代數和幾何意義的解釋等方面完整地對SVM加以分析和說明的。換言之，對於普通的一年級非數學專業的研究生而言，要想看懂SVM需要搜集很多資料，然後對照閱讀和深入思考，才可能比較透徹地理解SVM演算法。由於我本人也在東北大學教授面向一年級碩士研究生的《模式識別技術與應用》課程，因此希望能總結出一份相對完整、簡單和透徹的關於SVM演算法的介紹文字，以便學生能夠快速準確地理解SVM演算法。以下我會分為四個步驟對最基礎的線性SVM問題加以介紹，分別是1）問題原型，2）數學模型，3）最優化求解，4）幾何解釋。我儘可能用最簡單的語言和最基本的數學知識對上述問題進行介紹，希望能對困惑於SVM演算法的學生有所幫助。SVM演算法要解決什麼問題SVM的全稱是Support Vector Machine，即支持向量機，主要用於解決模式識別領域中的數據分類問題，屬於有監督學習演算法的一種。SVM要解決的問題可以用一個經典的二分類問題加以描述。如圖1所示，紅色和藍色的二維數據點顯然是可以被一條直線分開的，在模式識別領域稱為線性可分問題。然而將兩類數據點分開的直線顯然不止一條。圖1(b)和(c)分別給出了A、B兩種不同的分類方案，其中黑色實線為分界線，術語稱為「決策面」。每個決策面對應了一個線性分類器。雖然在目前的數據上看，這兩個分類器的分類結果是一樣的，但如果考慮潛在的其他數據，則兩者的分類性能是有差別的。

圖1 二分類問題描述

SVM演算法認為圖1中的分類器A在性能上優於分類器B，其依據是A的分類間隔比B要大。這裡涉及到第一個SVM獨有的概念「分類間隔」。在保證決策面方向不變且不會出現錯分樣本的情況下移動決策面，會在原來的決策面兩側找到兩個極限位置（越過該位置就會產生錯分現象），如虛線所示。虛線的位置由決策面的方向和距離原決策面最近的幾個樣本的位置決定。而這兩條平行虛線正中間的分界線就是在保持當前決策面方向不變的前提下的最優決策面。兩條虛線之間的垂直距離就是這個最優決策面對應的分類間隔。顯然每一個可能把數據集正確分開的方向都有一個最優決策面（有些方向無論如何移動決策面的位置也不可能將兩類樣本完全分開），而不同方向的最優決策面的分類間隔通常是不同的，那個具有「最大間隔」的決策面就是SVM要尋找的最優解。而這個真正的最優解對應的兩側虛線所穿過的樣本點，就是SVM中的支持樣本點，稱為「支持向量」。對於圖1中的數據，A決策面就是SVM尋找的最優解，而相應的三個位於虛線上的樣本點在坐標系中對應的向量就叫做支持向量。

從表面上看，我們優化的對象似乎是這個決策面的方向和位置。但實際上最優決策面的方向和位置完全取決於選擇哪些樣本作為支持向量。而在經過漫長的公式推導後，你最終會發現，其實與線性決策面的方向和位置直接相關的參數都會被約減掉，最終結果只取決於樣本點的選擇結果。

到這裡，我們明確了SVM演算法要解決的是一個最優分類器的設計問題。既然叫作最優分類器，其本質必然是個最優化問題。所以，接下來我們要討論的就是如何把SVM變成用數學語言描述的最優化問題模型，這就是我們在第二部分要講的「線性SVM演算法的數學建模」。

*關於「決策面」，為什麼叫決策面，而不是決策線？好吧，在圖1里，樣本是二維空間中的點，也就是數據的維度是2，因此1維的直線可以分開它們。但是在更加一般的情況下，樣本點的維度是n，則將它們分開的決策面的維度就是n-1維的超平面（可以想像一下3維空間中的點集被平面分開），所以叫「決策面」更加具有普適性，或者你可以認為直線是決策面的一個特例。

線性SVM算法的數學建模

一個最優化問題通常有兩個最基本的因素：1）目標函數，也就是你希望什麼東西的什麼指標達到最好；2）優化對象，你期望通過改變哪些因素來使你的目標函數達到最優。在線性SVM演算法中，目標函數顯然就是那個「分類間隔」，而優化對象則是決策面。所以要對SVM問題進行數學建模，首先要對上述兩個對象（「分類間隔」和「決策面」）進行數學描述。按照一般的思維習慣，我們先描述決策面。

2.1決策面方程

（請注意，以下的描述對於線性代數及格的同學可能顯得比較啰嗦，但請你們照顧一下用高數課治療失眠的同學們。）

請你暫時不要糾結於n維空間中的n-1維超平面這種超出正常人想像力的情景。我們就老老實實地看看二維空間中的一根直線，我們從初中就開始學習的直線方程形式很簡單。

現在我們做個小小的改變，讓原來的x軸變成x?軸，y變成x?軸，於是公式(2.1)中的直線方程會變成下面的樣子

公式（2.3）的向量形式可以寫成

考慮到我們在等式兩邊乘上任何實數都不會改變等式的成立，所以我們可以寫出一個更加一般的向量表達形式:

看到變數ω、x略顯粗壯的身體了嗎？他們是黑體，表示變數是個向量，，。一般我們提到向量的時候，都默認他們是個列向量，所以我在方括弧[ ]後面加上了上標T，表示轉置（我知道我真的很啰嗦，但是關於「零基礎」三個字，我是認真的。），它可以幫忙把行向量豎過來變成列向量，所以在公式(2.5)裡面ω後面的轉置符號T，會把列向量又轉回到行向量。這樣一個行向量

和一個列向量x就可快快樂樂的按照矩陣乘法的方式結合，變成一個標量，然後好跟後面的標量γ相加後相互抵消變成0。

就著公式(2.5)，我們再稍稍嘗試深入一點。那就是探尋一下向量點積，和標量γ的幾何意義是什麼。讓我們回到公式(2.4)，對比公式(2.5)，可以發現此時的。然後再去看公式(2.2)，還記得那條我們熟悉的直線方程中的a的幾何意義嗎？對的，那是直線的斜率。如果我們構造一個向量，它應該跟我們的公式(2.2)描述的直線平行。然後我們求一下兩個向量的點積，你會驚喜地發現結果是0。我們管這種現象叫作「兩個向量相互正交」。通俗點說就是兩個向量相互垂直。當然，你也可以在草稿紙上自己畫出這兩個向量，比如讓，你會發現在第一象限，與橫軸夾角為60°，而在第四象限與橫軸夾角為30°，所以很顯然他們兩者的夾角為90°。

你現在是不是已經忘了我們討論正交或者垂直的目的是什麼了？那麼請把你的思維從坐標繫上抽出來，回到決策面方程上來。我是想告訴你向量跟直線

是相互垂直的，也就是說控制了直線的方向。另外，還記得小時候我們學過的那個叫做截距的名詞嗎？對了，γ就是截距，它控制了直線的位置。

然後，在本小節的末尾，我冒昧地提示一下，在n維空間中n-1維的超平面的方程形式也是公式(2.5)的樣子，只不過向量ω、x的維度從原來的2維變成了n維。如果你還是想不出來超平面的樣子，也很正常。那麼就請你始終記住平面上它們的樣子也足夠了。

到這裡，我們花了很多篇幅描述一個很簡單的超平面方程（其實只是個直線方程），這裡真正有價值的是這個控制方向的參數ω。接下來，你會有很長一段時間要思考它到底是個什麼東西，對於SVM產生了怎樣的影響。

2.2 分類「間隔」的計算模型

我們在第一章里介紹過分類間隔的定義及其直觀的幾何意義。間隔的大小實際上就是支持向量對應的樣本點到決策面的距離的二倍，如圖2所示。

圖2 分類間隔計算

所以分類間隔計算似乎相當簡單，無非就是點到直線的距離公式。如果你想要回憶高中老師在黑板上推導的過程，可以隨便在百度文庫里搜索關鍵詞「點到直線距離推導公式」，你會得到至少6、7種推導方法。但這裡，請原諒我給出一個簡單的公式如下：

這裡||ω||是向量ω的模，表示在空間中向量的長度，就是支持向量樣本點的坐標。ω，γ就是決策面方程的參數。而追求W的最大化也就是尋找d的最大化。看起來我們已經找到了目標函數的數學形式。

但問題當然不會這麼簡單，我們還需要面對一連串令人頭疼的麻煩。

2.3 約束條件

接著2.2節的結尾，我們討論一下究竟還有哪些麻煩沒有解決：

1.並不是所有的方向都存在能夠實現100%正確分類的決策面，我們如何判斷一條直線是否能夠將所有的樣本點都正確分類？

2.即便找到了正確的決策面方向，還要注意決策面的位置應該在間隔區域的中軸線上，所以用來確定決策面位置的截距γ也不能自由的優化，而是受到決策面方向和樣本點分布的約束。

3.即便取到了合適的方向和截距，公式(2.6)裡面的x不是隨隨便便的一個樣本點，而是支持向量對應的樣本點。對於一個給定的決策面，我們該如何找到對應的支持向量？

以上三條麻煩的本質是「約束條件」，也就是說我們要優化的變數的取值範圍受到了限制和約束。事實上約束條件一直是最優化問題里最讓人頭疼的東西。但既然我們已經論證了這些約束條件確實存在，就不得不用數學語言對他們進行描述。儘管上面看起來是3條約束，但SVM演算法通過一些巧妙的小技巧，將這三條約束條件融合在了一個不等式裡面。

我們首先考慮一個決策面是否能夠將所有的樣本都正確分類的約束。圖2中的樣本點分成兩類（紅色和藍色），我們為每個樣本點加上一個類別標籤：

如果我們的決策面方程能夠完全正確地對圖2中的樣本點進行分類，就會滿足下面的公式

如果我們要求再高一點，假設決策面正好處於間隔區域的中軸線上，並且相應的支持向量對應的樣本點到決策面的距離為d，那麼公式(2.8)就可以進一步寫成：

符號是「對於所有滿足條件的」 的縮寫。我們對公式(2.9)中的兩個不等式的左右兩邊除上d，就可得到：

其中

把和就當成一條直線的方向矢量和截距。你會發現事情沒有發生任何變化，因為直線和直線其實是一條直線。現在，現在讓我忘記原來的直線方程參數ω和γ，我們可以把參數和重新起個名字，就叫它們ω和γ。我們可以直接說：「對於存在分類間隔的兩類樣本點，我們一定可以找到一些決策面，使其對於所有的樣本點均滿足下面的條件：」

公式(2.11)可以認為是SVM優化問題的約束條件的基本描述。

2.4 線性SVM優化問題基本描述

公式(2.11)裡面的情況什麼時候會發生呢，參考一下公式(2.9)就會知道，只有當是決策面所對應的支持向量樣本點時，等於1或-1的情況才會出現。這一點給了我們另一個簡化目標函數的啟發。回頭看看公式(2.6)，你會發現等式右邊分子部分的絕對值符號內部的表達式正好跟公式(2.11)中不等式左邊的表達式完全一致，無論原來這些表達式是1或者-1，其絕對值都是1。所以對於這些支持向量樣本點有：

公式(2.12)的幾何意義就是，支持向量樣本點到決策面方程的距離就是1/||ω||。我們原來的任務是找到一組參數ω、γ使得分類間隔W=2d最大化，根據公式(2.12)就可以轉變為||ω||的最小化問題，也等效於1/2||ω||2的最小化問題。我們之所以要在||ω||上加上平方和1/2的係數，是為了以後進行最優化的過程中對目標函數求導時比較方便，但這絕不影響最優化問題最後的解。

另外我們還可以嘗試將公式(2.11)給出的約束條件進一步在形式上精練，把類別標籤和兩個不等式左邊相乘，形成統一的表述：

好了，到這裡我們可以給出線性SVM最優化問題的數學描述了：

這裡m是樣本點的總個數，縮寫s. t. 表示「Subject to」，是「服從某某條件」的意思。公式(2.14)描述的是一個典型的不等式約束條件下的二次型函數優化問題，同時也是支持向量機的基本數學模型。（此時此刻，你也許會回頭看2.3節我們提出的三個約束問題，思考它們在公式2.14的約束條件中是否已經得到了充分的體現。但我不建議你現在就這麼做，因為2.14採用了一種比較含蓄的方式表示這些約束條件，所以你即便現在不理解也沒關係，後面隨著推導的深入，這些問題會一點點露出真容。）

接下來，我們將在第三章討論大多數同學比較陌生的問題：如何利用最優化技術求解公式(2.14)描述的問題。哪些令人望而生畏的術語，凸二次優化、拉格朗日對偶、KKT條件、鞍點等等，大多出現在這個部分。全面理解和熟練掌握這些概念當然不容易，但如果你的目的主要是了解這些技術如何在SVM問題進行應用的，那麼閱讀過下面一章後，你有很大的機會可以比較直觀地理解這些問題。

*一點小建議，讀到這裡，你可以試著在紙上隨便畫一些點，然後嘗試用SVM的思想手動畫線將兩類不同的點分開。你會發現大多數情況下，你會先畫一條可以成功分開兩類樣本點的直線，然後你會在你的腦海中想像去旋轉這條線，旋轉到某個角度，你就會下意識的停下來，因為如果再旋轉下去，就找不到能夠成功將兩類點分開的直線了。這個過程就是對直線方向的優化過程。對於有些問題，你會發現SVM的最優解往往出現在不能再旋轉下去的邊界位置，這就是約束條件的邊界，對比我們提到的等式約束條件，你會對代數公式與幾何想像之間的關係得到一些相對直觀的印象。

（未完待續）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！

本站內容充實豐富，博大精深，小編精選每日熱門資訊，隨時更新，點擊「搶先收到最新資訊」瀏覽吧！

請您繼續閱讀更多來自 AI研習社 的精彩文章: