机器学习中的算法：支持向量机(SVM)基础
前言：
?
最近一段時(shí)間看了看關(guān)于SVM(Support Vector Machine)的文章，覺得SVM是一個(gè)非常有趣，而且自成一派的方向，所以今天準(zhǔn)備寫一篇關(guān)于關(guān)于SVM的文章。
?
關(guān)于SVM的論文、書籍都非常的多，引用強(qiáng)哥的話“SVM是讓應(yīng)用數(shù)學(xué)家真正得到應(yīng)用的一種算法”。SVM對于大部分的普通人來說，要完全理解其中的數(shù)學(xué)是非常困難的，所以要讓這些普通人理解，得要把里面的數(shù)學(xué)知識用簡單的語言去講解才行。而且想明白了這些數(shù)學(xué)，對學(xué)習(xí)其他的內(nèi)容也是大有裨益的。我就是屬于絕大多數(shù)的普通人，為了看明白SVM，看了不少的資料，這里把我的心得分享分享。
?
其實(shí)現(xiàn)在能夠找到的，關(guān)于SVM的中文資料已經(jīng)不少了，不過個(gè)人覺得，每個(gè)人的理解都不太一樣，所以還是決定寫一寫，一些雷同的地方肯定是不可避免的，不過還是希望能夠?qū)懗鲆稽c(diǎn)與別人不一樣的地方吧。另外本文準(zhǔn)備不談太多的數(shù)學(xué)（因?yàn)楹芏辔恼露颊勥^了），盡量簡單地給出結(jié)論，就像題目一樣-機(jī)器學(xué)習(xí)中的算法（之前叫做機(jī)器學(xué)習(xí)中的數(shù)學(xué)），所以本系列的內(nèi)容將更偏重應(yīng)用一些。如果想看更詳細(xì)的數(shù)學(xué)解釋，可以看看參考文獻(xiàn)中的資料。
?
一、線性分類器：
?
首先給出一個(gè)非常非常簡單的分類問題（線性可分），我們要用一條直線，將下圖中黑色的點(diǎn)和白色的點(diǎn)分開，很顯然，圖上的這條直線就是我們要求的直線之一（可以有無數(shù)條這樣的直線）
?
?
假如說，我們令黑色的點(diǎn) = -1， 白色的點(diǎn) = ?+1，直線f(x) = w.x + b，這兒的x、w是向量，其實(shí)寫成這種形式也是等價(jià)的f(x) = w1x1 + w2x2 … + wnxn + b, 當(dāng)向量x的維度=2的時(shí)候，f(x) 表示二維空間中的一條直線， 當(dāng)x的維度=3的時(shí)候，f(x) 表示3維空間中的一個(gè)平面，當(dāng)x的維度=n > 3的時(shí)候，表示n維空間中的n-1維超平面。這些都是比較基礎(chǔ)的內(nèi)容，如果不太清楚，可能需要復(fù)習(xí)一下微積分、線性代數(shù)的內(nèi)容。
?
剛剛說了，我們令黑色白色兩類的點(diǎn)分別為+1, -1，所以當(dāng)有一個(gè)新的點(diǎn)x需要預(yù)測屬于哪個(gè)分類的時(shí)候，我們用sgn(f(x))，就可以預(yù)測了，sgn表示符號函數(shù)，當(dāng)f(x) > 0的時(shí)候，sgn(f(x)) = +1, 當(dāng)f(x) < 0的時(shí)候sgn(f(x)) = –1。
?
但是，我們怎樣才能取得一個(gè)最優(yōu)的劃分直線f(x)呢？下圖的直線表示幾條可能的f(x)
?
?
一個(gè)很直觀的感受是，讓這條直線到給定樣本中最近的點(diǎn)最遠(yuǎn)，這句話讀起來比較拗口，下面給出幾個(gè)圖，來說明一下：
?
第一種分法：
?
?
第二種分法：
?
?
這兩種分法哪種更好呢？從直觀上來說，就是分割的間隙越大越好，把兩個(gè)類別的點(diǎn)分得越開越好。就像我們平時(shí)判斷一個(gè)人是男還是女，就是很難出現(xiàn)分錯(cuò)的情況，這就是男、女兩個(gè)類別之間的間隙非常的大導(dǎo)致的，讓我們可以更準(zhǔn)確的進(jìn)行分類。在SVM中，稱為Maximum Marginal，是SVM的一個(gè)理論基礎(chǔ)之一。選擇使得間隙最大的函數(shù)作為分割平面是由很多道理的，比如說從概率的角度上來說，就是使得置信度最小的點(diǎn)置信度最大（聽起來很拗口），從實(shí)踐的角度來說，這樣的效果非常好，等等。這里就不展開講，作為一個(gè)結(jié)論就ok了，:)
?
上圖被紅色和藍(lán)色的線圈出來的點(diǎn)就是所謂的支持向量(support vector)。
?
???
?上圖就是一個(gè)對之前說的類別中的間隙的一個(gè)描述。Classifier Boundary就是f(x)，紅色和藍(lán)色的線（plus plane與minus plane）就是support vector所在的面，紅色、藍(lán)色線之間的間隙就是我們要最大化的分類間的間隙。
????
這里直接給出M的式子：（從高中的解析幾何就可以很容易的得到了，也可以參考后面Moore的ppt）
?
?
另外支持向量位于wx + b = 1與wx + b = -1的直線上，我們在前面乘上一個(gè)該點(diǎn)所屬的類別y（還記得嗎?y不是+1就是-1），就可以得到支持向量的表達(dá)式為：y(wx + b) = 1，這樣就可以更簡單的將支持向量表示出來了。
?
當(dāng)支持向量確定下來的時(shí)候，分割函數(shù)就確定下來了，兩個(gè)問題是等價(jià)的。得到支持向量，還有一個(gè)作用是，讓支持向量后方那些點(diǎn)就不用參與計(jì)算了。這點(diǎn)在后面將會(huì)更詳細(xì)的講講。
?
在這個(gè)小節(jié)的最后，給出我們要優(yōu)化求解的表達(dá)式：
?
?
?||w||的意思是w的二范數(shù)，跟上面的M表達(dá)式的分母是一個(gè)意思，之前得到，M = 2 / ||w||，最大化這個(gè)式子等價(jià)于最小化||w||, 另外由于||w||是一個(gè)單調(diào)函數(shù)，我們可以對其加入平方，和前面的系數(shù)，熟悉的同學(xué)應(yīng)該很容易就看出來了，這個(gè)式子是為了方便求導(dǎo)。
?
這個(gè)式子有還有一些限制條件，完整的寫下來，應(yīng)該是這樣的：（原問題）
?
?
s.t的意思是subject to，也就是在后面這個(gè)限制條件下的意思，這個(gè)詞在svm的論文里面非常容易見到。這個(gè)其實(shí)是一個(gè)帶約束的二次規(guī)劃(quadratic programming, QP)問題，是一個(gè)凸問題，凸問題就是指的不會(huì)有局部最優(yōu)解，可以想象一個(gè)漏斗，不管我們開始的時(shí)候?qū)⒁粋€(gè)小球放在漏斗的什么位置，這個(gè)小球最終一定可以掉出漏斗，也就是得到全局最優(yōu)解。s.t.后面的限制條件可以看做是一個(gè)凸多面體，我們要做的就是在這個(gè)凸多面體中找到最優(yōu)解。這些問題這里不展開，因?yàn)檎归_的話，一本書也寫不完。如果有疑問請看看wikipedia。
?
二、轉(zhuǎn)化為對偶問題，并優(yōu)化求解:
?
這個(gè)優(yōu)化問題可以用拉格朗日乘子法去解，使用了KKT條件的理論，這里直接作出這個(gè)式子的拉格朗日目標(biāo)函數(shù)：
?
求解這個(gè)式子的過程需要拉格朗日對偶性的相關(guān)知識（另外pluskid也有一篇文章專門講這個(gè)問題），并且有一定的公式推導(dǎo)，如果不感興趣，可以直接跳到后面用藍(lán)色公式表示的結(jié)論，該部分推導(dǎo)主要參考自plukids的文章。
?
首先讓L關(guān)于w，b最小化，分別令L關(guān)于w，b的偏導(dǎo)數(shù)為0，得到關(guān)于原問題的一個(gè)表達(dá)式
?
??
將兩式帶回L(w,b,a)得到對偶問題的表達(dá)式
?
?
?新問題加上其限制條件是（對偶問題）:
?
?
這個(gè)就是我們需要最終優(yōu)化的式子。至此，得到了線性可分問題的優(yōu)化式子。
?
求解這個(gè)式子，有很多的方法，比如SMO等等，個(gè)人認(rèn)為，求解這樣的一個(gè)帶約束的凸優(yōu)化問題與得到這個(gè)凸優(yōu)化問題是比較獨(dú)立的兩件事情，所以在這篇文章中準(zhǔn)備完全不涉及如何求解這個(gè)話題，如果之后有時(shí)間可以補(bǔ)上一篇文章來談?wù)?)。
?
三、線性不可分的情況（軟間隔）：
?
接下來談?wù)劸€性不可分的情況，因?yàn)榫€性可分這種假設(shè)實(shí)在是太有局限性了：
?
下圖就是一個(gè)典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個(gè)區(qū)域，每個(gè)區(qū)域只包含一種顏色的點(diǎn)。
?
要想在這種情況下的分類器，有兩種方式，一種是用曲線去將其完全分開，曲線就是一種非線性的情況，跟之后將談到的核函數(shù)有一定的關(guān)系：
?
?
另外一種還是用直線，不過不用去保證可分性，就是包容那些分錯(cuò)的情況，不過我們得加入懲罰函數(shù)，使得點(diǎn)分錯(cuò)的情況越合理越好。其實(shí)在很多時(shí)候，不是在訓(xùn)練的時(shí)候分類函數(shù)越完美越好，因?yàn)橛?xùn)練函數(shù)中有些數(shù)據(jù)本來就是噪聲，可能就是在人工加上分類標(biāo)簽的時(shí)候加錯(cuò)了，如果我們在訓(xùn)練（學(xué)習(xí)）的時(shí)候把這些錯(cuò)誤的點(diǎn)學(xué)習(xí)到了，那么模型在下次碰到這些錯(cuò)誤情況的時(shí)候就難免出錯(cuò)了（假如老師給你講課的時(shí)候，某個(gè)知識點(diǎn)講錯(cuò)了，你還信以為真了，那么在考試的時(shí)候就難免出錯(cuò)）。這種學(xué)習(xí)的時(shí)候?qū)W到了“噪聲”的過程就是一個(gè)過擬合（over-fitting），這在機(jī)器學(xué)習(xí)中是一個(gè)大忌，我們寧愿少學(xué)一些內(nèi)容，也堅(jiān)決杜絕多學(xué)一些錯(cuò)誤的知識。還是回到主題，用直線怎么去分割線性不可分的點(diǎn)：
?
我們可以為分錯(cuò)的點(diǎn)加上一點(diǎn)懲罰，對一個(gè)分錯(cuò)的點(diǎn)的懲罰函數(shù)就是這個(gè)點(diǎn)到其正確位置的距離：
?
?
在上圖中，藍(lán)色、紅色的直線分別為支持向量所在的邊界，綠色的線為決策函數(shù)，那些紫色的線表示分錯(cuò)的點(diǎn)到其相應(yīng)的決策面的距離，這樣我們可以在原函數(shù)上面加上一個(gè)懲罰函數(shù)，并且?guī)掀湎拗茥l件為：
?
?
公式中藍(lán)色的部分為在線性可分問題的基礎(chǔ)上加上的懲罰函數(shù)部分，當(dāng)xi在正確一邊的時(shí)候，ε=0，R為全部的點(diǎn)的數(shù)目，C是一個(gè)由用戶去指定的系數(shù)，表示對分錯(cuò)的點(diǎn)加入多少的懲罰，當(dāng)C很大的時(shí)候，分錯(cuò)的點(diǎn)就會(huì)更少，但是過擬合的情況可能會(huì)比較嚴(yán)重，當(dāng)C很小的時(shí)候，分錯(cuò)的點(diǎn)可能會(huì)很多，不過可能由此得到的模型也會(huì)不太正確，所以如何選擇C是有很多學(xué)問的，不過在大部分情況下就是通過經(jīng)驗(yàn)嘗試得到的。
?
接下來就是同樣的，求解一個(gè)拉格朗日對偶問題，得到一個(gè)原問題的對偶問題的表達(dá)式：
?
?
藍(lán)色的部分是與線性可分的對偶問題表達(dá)式的不同之處。在線性不可分情況下得到的對偶問題，不同的地方就是α的范圍從[0, +∞)，變?yōu)榱薣0, C]，增加的懲罰ε沒有為對偶問題增加什么復(fù)雜度。
?
四、核函數(shù)：
?
剛剛在談不可分的情況下，提了一句，如果使用某些非線性的方法，可以得到將兩個(gè)分類完美劃分的曲線，比如接下來將要說的核函數(shù)。
?
我們可以讓空間從原本的線性空間變成一個(gè)更高維的空間，在這個(gè)高維的線性空間下，再用一個(gè)超平面進(jìn)行劃分。這兒舉個(gè)例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的（例子以及圖片來自pluskid的kernel函數(shù)部分）：
?
下圖是一個(gè)典型的線性不可分的情況
?
?
但是當(dāng)我們把這兩個(gè)類似于橢圓形的點(diǎn)映射到一個(gè)高維空間后，映射函數(shù)為：
?
用這個(gè)函數(shù)可以將上圖的平面中的點(diǎn)映射到一個(gè)三維空間（z1,z2,z3)，并且對映射后的坐標(biāo)加以旋轉(zhuǎn)之后就可以得到一個(gè)線性可分的點(diǎn)集了。
?
?
?
用另外一個(gè)哲學(xué)例子來說：世界上本來沒有兩個(gè)完全一樣的物體，對于所有的兩個(gè)物體，我們可以通過增加維度來讓他們最終有所區(qū)別，比如說兩本書，從(顏色，內(nèi)容)兩個(gè)維度來說，可能是一樣的，我們可以加上 作者 這個(gè)維度，是在不行我們還可以加入 頁碼，可以加入 擁有者，可以加入 購買地點(diǎn)，可以加入 筆記內(nèi)容等等。當(dāng)維度增加到無限維的時(shí)候，一定可以讓任意的兩個(gè)物體可分了。
?
回憶剛剛得到的對偶問題表達(dá)式：
?
?
?我們可以將紅色這個(gè)部分進(jìn)行改造，令：
?
這個(gè)式子所做的事情就是將線性的空間映射到高維的空間,k(x, xj)有很多種，下面是比較典型的兩種：
?
上面這個(gè)核稱為多項(xiàng)式核，下面這個(gè)核稱為高斯核，高斯核甚至是將原始空間映射為無窮維空間，另外核函數(shù)有一些比較好的性質(zhì)，比如說不會(huì)比線性條件下增加多少額外的計(jì)算量，等等，這里也不再深入。一般對于一個(gè)問題，不同的核函數(shù)可能會(huì)帶來不同的結(jié)果，一般是需要嘗試來得到的。
?
五、一些其他的問題：
?
如何進(jìn)行多分類問題：
?
上面所談到的分類都是2分類的情況，當(dāng)N分類的情況下，主要有兩種方式，一種是1 vs (N – 1)一種是1 vs 1，前一種方法我們需要訓(xùn)練N個(gè)分類器，第i個(gè)分類器是看看是屬于分類i還是屬于分類i的補(bǔ)集（出去i的N-1個(gè)分類）。
?
后一種方式我們需要訓(xùn)練N * (N – 1) / 2個(gè)分類器，分類器(i,j)能夠判斷某個(gè)點(diǎn)是屬于i還是屬于j。
?
這種處理方式不僅在SVM中會(huì)用到，在很多其他的分類中也是被廣泛用到，從林教授（libsvm的作者）的結(jié)論來看，1 vs 1的方式要優(yōu)于1 vs (N – 1)。
?
SVM會(huì)overfitting嗎？
?
SVM避免overfitting，一種是調(diào)整之前說的懲罰函數(shù)中的C，另一種其實(shí)從式子上來看，min ||w||^2這個(gè)看起來是不是很眼熟？在最小二乘法回歸的時(shí)候，我們看到過這個(gè)式子，這個(gè)式子可以讓函數(shù)更平滑，所以SVM是一種不太容易o(hù)ver-fitting的方法。
?
?
來源：LeftNotEasy
cnblogs.com/LeftNotEasy/archive/2011/05/02/basic-of-svm.html
轉(zhuǎn)載于:https://my.oschina.net/u/3100313/blog/897360
總結(jié)
以上是生活随笔為你收集整理的机器学习中的算法：支持向量机(SVM)基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Movavi Video Editor
- 下一篇： C++ Primer Plus_读书笔记