零基礎(chǔ)學(xué)SVM―Support Vector Machine系列之一-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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