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

1、零基礎學SVMSupport Vector Machine系列之一本文原作者耳東陳,本文原載于作者的知乎文章。AI 研習社已獲得轉載授權。如果你是一名模式識別專業(yè)的研究生,又或者你是機器學習愛好者,SVM是一個你避不開的問題。如果你只是有一堆數(shù)據需要SVM幫你處理一下,那么無論是Matlab的SVM工具箱,LIBSVM還是python框架下的SciKit Learn都可以提供方便快捷的解決方案。但如果你要追求的不僅僅是會用,還希望挑戰(zhàn)一下“理解”這個層次,那么你就需要面對一大堆你可能從來沒聽過的名詞,比如:非線性約束條件下的最優(yōu)化、KKT條件、拉格朗日對偶、最大間隔、最優(yōu)下界、核函數(shù)等等。這些

2、名詞往往會跟隨一大堆天書一般的公式。如果你稍微有一點數(shù)學基礎,那么單個公式你可能看得明白,但是怎么從一個公式跳到另一個公式就讓人十分費解了,而最讓人糊涂的其實并不是公式推導,而是如果把這些公式和你腦子里空間構想聯(lián)系起來。我本人就是上述問題的受害者之一。我翻閱了很多關于SVM的書籍和資料,但沒有找到一份材料能夠在公式推導、理論介紹,系統(tǒng)分析、變量說明、代數(shù)和幾何意義的解釋等方面完整地對SVM加以分析和說明的。換言之,對于普通的一年級非數(shù)學專業(yè)的研究生而言,要想看懂SVM需要搜集很多資料,然后對照閱讀和深入思考,才可能比較透徹地理解SVM算法。由于我本人也在東北大學教授面向一年級碩士研究生的模式識

3、別技術與應用課程,因此希望能總結出一份相對完整、簡單和透徹的關于SVM算法的介紹文字,以便學生能夠快速準確地理解SVM算法。以下我會分為四個步驟對最基礎的線性SVM問題加以介紹,分別是1問題原型,2數(shù)學模型,3最優(yōu)化求解,4幾何解釋。我盡可能用最簡單的語言和最基本的數(shù)學知識對上述問題進行介紹,希望能對困惑于SVM算法的學生有所幫助。SVM算法要解決什么問題SVM的全稱是Support Vector Machine,即支持向量機,主要用于解決模式識別領域中的數(shù)據分類問題,屬于有監(jiān)督學習算法的一種。SVM要解決的問題可以用一個經典的二分類問題加以描述。如圖1所示,紅色和藍色的二維數(shù)據點顯然是可以被

4、一條直線分開的,在模式識別領域稱為線性可分問題。然而將兩類數(shù)據點分開的直線顯然不止一條。圖1(b和(c分別給出了A、B兩種不同的分類方案,其中黑色實線為分界線,術語稱為“決策面”。每個決策面對應了一個線性分類器。雖然在目前的數(shù)據上看,這兩個分類器的分類結果是一樣的,但如果考慮潛在的其他數(shù)據,則兩者的分類性能是有差別的。圖1 二分類問題描述SVM算法認為圖1中的分類器A在性能上優(yōu)于分類器B,其依據是A的分類間隔比B要大。這里涉及到第一個SVM獨有的概念“分類間隔”。在保證決策面方向不變且不會出現(xiàn)錯分樣本的情況下移動決策面,會在原來的決策面兩側找到兩個極限位置(越過該位置就會產生錯分現(xiàn)象,如虛線所

5、示。虛線的位置由決策面的方向和距離原決策面最近的幾個樣本的位置決定。而這兩條平行虛線正中間的分界線就是在保持當前決策面方向不變的前提下的最優(yōu)決策面。兩條虛線之間的垂直距離就是這個最優(yōu)決策面對應的分類間隔。顯然每一個可能把數(shù)據集正確分開的方向都有一個最優(yōu)決策面(有些方向無論如何移動決策面的位置也不可能將兩類樣本完全分開,而不同方向的最優(yōu)決策面的分類間隔通常是不同的,那個具有“最大間隔”的決策面就是SVM要尋找的最優(yōu)解。而這個真正的最優(yōu)解對應的兩側虛線所穿過的樣本點,就是SVM中的支持樣本點,稱為“支持向量”。對于圖1中的數(shù)據,A決策面就是SVM尋找的最優(yōu)解,而相應的三個位于虛線上的樣本點在坐標系

6、中對應的向量就叫做支持向量。從表面上看,我們優(yōu)化的對象似乎是這個決策面的方向和位置。但實際上最優(yōu)決策面的方向和位置完全取決于選擇哪些樣本作為支持向量。而在經過漫長的公式推導后,你最終會發(fā)現(xiàn),其實與線性決策面的方向和位置直接相關的參數(shù)都會被約減掉,最終結果只取決于樣本點的選擇結果。到這里,我們明確了SVM 算法要解決的是一個最優(yōu)分類器的設計問題。既然叫作最優(yōu)分類器,其本質必然是個最優(yōu)化問題。所以,接下來我們要討論的就是如何把SVM變成用數(shù)學語言描述的最優(yōu)化問題模型,這就是我們在第二部分要講的“線性SVM算法的數(shù)學建?！薄?關于“決策面”,為什么叫決策面,而不是決策線?好吧,在圖1里,樣本是二維空

7、間中的點,也就是數(shù)據的維度是2,因此1維的直線可以分開它們。但是在更加一般的情況下,樣本點的維度是n,則將它們分開的決策面的維度就是n-1維的超平面(可以想象一下3維空間中的點集被平面分開,所以叫“決策面”更加具有普適性,或者你可以認為直線是決策面的一個特例。線性SVM算法的數(shù)學建模一個最優(yōu)化問題通常有兩個最基本的因素:1目標函數(shù),也就是你希望什么東西的什么指標達到最好;2優(yōu)化對象,你期望通過改變哪些因素來使你的目標函數(shù)達到最優(yōu)。在線性SVM算法中,目標函數(shù)顯然就是那個“分類間隔”,而優(yōu)化對象則是決策面。所以要對SVM問題進行數(shù)學建模,首先要對上述兩個對象(“分類間隔”和“決策面”進行數(shù)學描述

8、。按照一般的思維習慣,我們先描述決策面。2.1決策面方程(請注意,以下的描述對于線性代數(shù)及格的同學可能顯得比較啰嗦,但請你們照顧一下用高數(shù)課治療失眠的同學們。請你暫時不要糾結于n維空間中的n-1維超平面這種超出正常人想象力的情景。我們就老老實實地看看二維空間中的一根直線,我們從初中就開始學習的直線方程形式很簡單?，F(xiàn)在我們做個小小的改變,讓原來的x軸變成x?軸,y變成x?軸,于是公式(2.1中的直線方程會變成下面的樣子公式(2.3的向量形式可以寫成考慮到我們在等式兩邊乘上任何實數(shù)都不會改變等式的成立,所以我們可以寫出一個更加一般的向量表達形式:看到變量、x略顯粗壯的身體了嗎?他們是黑體,表示變量

9、是個向量,。一般我們提到向量的時候,都默認他們是個列向量,所以我在方括號后面加上了上標T,表示轉置(我知道我真的很啰嗦,但是關于“零基礎”三個字,我是認真的。,它可以幫忙把行向量豎過來變成列向量,所以在公式(2.5里面后面的轉置符號T,會把列向量又轉回到行向量。這樣一個行向量和一個列向量x就可快快樂樂的按照矩陣乘法的方式結合,變成一個標量,然后好跟后面的標量相加后相互抵消變成0。就著公式(2.5,我們再稍稍嘗試深入一點。那就是探尋一下向量點積,和標量的幾何意義是什么。讓我們回到公式(2.4,對比公式(2.5,可以發(fā)現(xiàn)此時的。然后再去看公式(2.2,還記得那條我們熟悉的直線方程中的a的幾何意義嗎

10、?對的,那是直線的斜率。如果我們構造一個向量,它應該跟我們的公式(2.2描述的直線平行。然后我們求一下兩個向量的點積,你會驚喜地發(fā)現(xiàn)結果是0。我們管這種現(xiàn)象叫作“兩個向量相互正交”。通俗點說就是兩個向量相互垂直。當然,你也可以在草稿紙上自己畫出這兩個向量,比如讓,你會發(fā)現(xiàn)在第一象限,與橫軸夾角為60°,而在第四象限與橫軸夾角為30°,所以很顯然他們兩者的夾角為90°。你現(xiàn)在是不是已經忘了我們討論正交或者垂直的目的是什么了?那么請把你的思維從坐標系上抽出來,回到決策面方程上來。我是想告訴你向量跟直線是相互垂直的,也就是說控制了直線的方向。另外,還記得小時候我們學過的

11、那個叫做截距的名詞嗎?對了,就是截距,它控制了直線的位置。然后,在本小節(jié)的末尾,我冒昧地提示一下,在n維空間中n-1維的超平面的方程形式也是公式(2.5的樣子,只不過向量、x的維度從原來的2維變成了n維。如果你還是想不出來超平面的樣子,也很正常。那么就請你始終記住平面上它們的樣子也足夠了。到這里,我們花了很多篇幅描述一個很簡單的超平面方程(其實只是個直線方程,這里真正有價值的是這個控制方向的參數(shù)。接下來,你會有很長一段時間要思考它到底是個什么東西,對于SVM產生了怎樣的影響。2.2 分類“間隔”的計算模型我們在第一章里介紹過分類間隔的定義及其直觀的幾何意義。間隔的大小實際上就是支持向量對應的樣

12、本點到決策面的距離的二倍,如圖2所示。圖2 分類間隔計算所以分類間隔計算似乎相當簡單,無非就是點到直線的距離公式。如果你想要回憶高中老師在黑板上推導的過程,可以隨便在百度文庫里搜索關鍵詞“點到直線距離推導公式”,你會得到至少6、7種推導方法。但這里,請原諒我給出一個簡單的公式如下:這里|是向量的模,表示在空間中向量的長度,就是支持向量樣本點的坐標。,就是決策面方程的參數(shù)。而追求W的最大化也就是尋找d的最大化。看起來我們已經找到了目標函數(shù)的數(shù)學形式。但問題當然不會這么簡單,我們還需要面對一連串令人頭疼的麻煩。2.3 約束條件接著2.2節(jié)的結尾,我們討論一下究竟還有哪些麻煩沒有解決:1.并不是所有

13、的方向都存在能夠實現(xiàn)100%正確分類的決策面,我們如何判斷一條直線是否能夠將所有的樣本點都正確分類?2.即便找到了正確的決策面方向,還要注意決策面的位置應該在間隔區(qū)域的中軸線上,所以用來確定決策面位置的截距也不能自由的優(yōu)化,而是受到決策面方向和樣本點分布的約束。3.即便取到了合適的方向和截距,公式(2.6里面的x不是隨隨便便的一個樣本點,而是支持向量對應的樣本點。對于一個給定的決策面,我們該如何找到對應的支持向量?以上三條麻煩的本質是“約束條件”,也就是說我們要優(yōu)化的變量的取值范圍受到了限制和約束。事實上約束條件一直是最優(yōu)化問題里最讓人頭疼的東西。但既然我們已經論證了這些約束條件確實存在,就不

14、得不用數(shù)學語言對他們進行描述。盡管上面看起來是3條約束,但SVM算法通過一些巧妙的小技巧,將這三條約束條件融合在了一個不等式里面。我們首先考慮一個決策面是否能夠將所有的樣本都正確分類的約束。圖2中的樣本點分成兩類(紅色和藍色,我們?yōu)槊總€樣本點加上一個類別標簽:如果我們的決策面方程能夠完全正確地對圖2中的樣本點進行分類,就會滿足下面的公式如果我們要求再高一點,假設決策面正好處于間隔區(qū)域的中軸線上,并且相應的支持向量對應的樣本點到決策面的距離為d,那么公式(2.8就可以進一步寫成:符號是“對于所有滿足條件的” 的縮寫。我們對公式(2.9中的兩個不等式的左右兩邊除上d,就可得到:其中和就當成一條直線

15、的方向矢量和截距。你會發(fā)現(xiàn)事情沒有發(fā)生任何變化,因為直線和直線其實是一條直線?，F(xiàn)在,現(xiàn)在讓我忘記原來的直線方程參數(shù)和,我們可以把參數(shù)和重新起個名字,就叫它們和。我們可以直接說:“對于存在分類間隔的兩類樣本點,我們一定可以找到一些決策面,使其對于所有的樣本點均滿足下面的條件:”公式(2.11可以認為是SVM優(yōu)化問題的約束條件的基本描述。2.4 線性SVM優(yōu)化問題基本描述公式(2.11里面的情況什么時候會發(fā)生呢,參考一下公式(2.9就會知道,只有當是決策面所對應的支持向量樣本點時,等于1或-1的情況才會出現(xiàn)。這一點給了我們另一個簡化目標函數(shù)的啟發(fā)。回頭看看公式(2.6,你會發(fā)現(xiàn)等式右邊分子部分的絕

16、對值符號內部的表達式正好跟公式(2.11中不等式左邊的表達式完全一致,無論原來這些表達式是1或者-1,其絕對值都是1。所以對于這些支持向量樣本點有:公式(2.12的幾何意義就是,支持向量樣本點到決策面方程的距離就是1/|。我們原來的任務是找到一組參數(shù)、使得分類間隔W=2d最大化,根據公式(2.12就可以轉變?yōu)閨的最小化問題,也等效于1/2|2的最小化問題。我們之所以要在|上加上平方和1/2的系數(shù),是為了以后進行最優(yōu)化的過程中對目標函數(shù)求導時比較方便,但這絕不影響最優(yōu)化問題最后的解。另外我們還可以嘗試將公式(2.11給出的約束條件進一步在形式上精練,把類別標簽和兩個不等式左邊相乘,形成統(tǒng)一的表述

17、:好了,到這里我們可以給出線性SVM最優(yōu)化問題的數(shù)學描述了:這里m是樣本點的總個數(shù),縮寫s. t. 表示“Subject to”,是“服從某某條件”的意思。公式(2.14描述的是一個典型的不等式約束條件下的二次型函數(shù)優(yōu)化問題,同時也是支持向量機的基本數(shù)學模型。(此時此刻,你也許會回頭看2.3節(jié)我們提出的三個約束問題,思考它們在公式2.14的約束條件中是否已經得到了充分的體現(xiàn)。但我不建議你現(xiàn)在就這么做,因為2.14采用了一種比較含蓄的方式表示這些約束條件,所以你即便現(xiàn)在不理解也沒關系,后面隨著推導的深入,這些問題會一點點露出真容。接下來,我們將在第三章討論大多數(shù)同學比較陌生的問題:如何利用最優(yōu)化技術求解公式(2.14描述的問題。哪些令人望而生畏的術語,凸二次優(yōu)化、拉格朗日對偶、KKT條件、鞍點等等,大多出現(xiàn)在這個部分。全面理解和熟練掌握這些概念當然不容易,但如果你的目的主要是了解這些技術如何在SVM問題進行應用的,那么閱讀過下面一章后,你有很大的機會可以比較直觀地理解這