支持向量機(jī)SVM【知識(shí)薈萃】

1、支持向量機(jī)理論及發(fā)展,李保連 2012-11-20,1,行業(yè)重點(diǎn),主要內(nèi)容,SVM基本原理,SVM面臨的一些問(wèn)題,TWIN SVM介紹,SVM簡(jiǎn)介,2,行業(yè)重點(diǎn),支持向量機(jī)理論簡(jiǎn)介,支持向量機(jī)SVM(Support Vector Machine)是統(tǒng)計(jì)機(jī)器學(xué)習(xí)的一類(lèi)重要算法,它根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，以結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則為理論基礎(chǔ)的一種新的機(jī)器學(xué)習(xí)方法，能有效地解決高維數(shù)和非線性等問(wèn)題，有效地進(jìn)行分類(lèi)、回歸等。與其它分類(lèi)器相比，SVM具有更好的泛化性。迄今為止，SVM已經(jīng)在模式分類(lèi)、回歸分析、函數(shù)估計(jì)等領(lǐng)域有廣泛的應(yīng)用。,3,行業(yè)重點(diǎn),什么是svm,原始區(qū)域 svm劃分后的區(qū)域,4,行業(yè)重點(diǎn),SVM

2、基本原理,線性可分類(lèi)型,問(wèn)題描述：我們要用一條直線，將上圖中黑色的點(diǎn)和白色的點(diǎn)分開(kāi)，很顯然，圖上的這條直線就是我們要求的直線之一（可以有無(wú)數(shù)條這樣的直線）,5,行業(yè)重點(diǎn),SVM基本原理,我們令深色的點(diǎn) = -1， 淺色的點(diǎn) = +1，直線f(x) = W X + b，這里的W、X是向量， 這種形式也等價(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維超平面。 當(dāng)有一個(gè)新的點(diǎn)x需要預(yù)測(cè)屬于哪個(gè)分類(lèi)的時(shí)候， 我們

3、用sgn(f(x)，就可以預(yù)測(cè)了 這里sgn表示符號(hào)函數(shù) 當(dāng)f(x) 0時(shí)，sgn(f(x) = +1 當(dāng)f(x) 0時(shí)，sgn(f(x) = 1,6,行業(yè)重點(diǎn),SVM基本原理,怎樣才能取得一個(gè)最優(yōu)的劃分直線f(x)呢？ 下圖的直線表示幾條可能的f(x),7,行業(yè)重點(diǎn),SVM基本原理,一個(gè)很直觀的感受是，讓這條直線到給定樣本中最近的點(diǎn)最遠(yuǎn) 下面有兩種劃分方法 第一種 第二種,右圖中被紅色和藍(lán)色圈中的點(diǎn)即所謂的支持向量（support vector）,8,行業(yè)重點(diǎn),SVM基本原理,原則：分割的間隙越大越好，把兩個(gè)類(lèi)別的點(diǎn)分得越開(kāi)越好 在SVM中，這種最大的分隔間隙稱(chēng)為Maximum Margin

4、al，是SVM的一個(gè)理論基礎(chǔ)。,Classifier Boundary就是f(x)，紅色和藍(lán)色的線（plus plane與minus plane）就是support vector所在的面 紅色、藍(lán)色線之間的間隙就是我們要最大化的分類(lèi)間的間隙,9,行業(yè)重點(diǎn),SVM基本原理,根據(jù)解析幾何可得出M的表達(dá)式: 經(jīng)過(guò)一系列的數(shù)學(xué)變換，得出我們要優(yōu)化求解的表達(dá)式： |w|的意思是w的二范數(shù)，跟上面的M表達(dá)式的分母意思相同，之前得到，M = 2 / |w|，最大化這個(gè)式子等價(jià)于最小化|w|, 另外由于|w|是一個(gè)單調(diào)函數(shù)，為了方便求導(dǎo)，我們可以對(duì)其加入平方和前面的系數(shù),10,行業(yè)重點(diǎn),SVM基本原理,上式有

5、還有一些限制條件，完整的表達(dá)方式如下： s.t.意為subject to，即在后面這個(gè)限制條件下的意思，這個(gè)詞在svm的論文里面出現(xiàn)的頻率很高。 這其實(shí)是一個(gè)帶約束的二次規(guī)劃(quadratic programming, QP)問(wèn)題，是一個(gè)凸問(wèn)題。凸問(wèn)題就是指的不會(huì)有局部最優(yōu)解，可以想象一個(gè)漏斗，不管我們開(kāi)始的時(shí)候?qū)⒁粋€(gè)小球放在漏斗的什么位置，這個(gè)小球最終一定可以掉出漏斗，也就是得到全局最優(yōu)解。s.t.后面的限制條件可以看做是一個(gè)凸多面體，我們要做的就是在這個(gè)凸多面體中找到最優(yōu)解。,11,行業(yè)重點(diǎn),SVM基本原理,這個(gè)優(yōu)化問(wèn)題可以用拉格朗日乘子法去解，使用了KKT條件的理論，這里直接給出這個(gè)式

6、子的拉格朗日目標(biāo)函數(shù) 求解這個(gè)式子的過(guò)程需要拉格朗日對(duì)偶性的相關(guān)知識(shí)，首先讓L關(guān)于w，b最小化，分別令L關(guān)于w，b的偏導(dǎo)數(shù)為0，得到關(guān)于原問(wèn)題的一個(gè)表達(dá)式,12,行業(yè)重點(diǎn),KKT條件,考慮問(wèn)題 min f(x)s.t. g(x)=0 則KKT條件是存在y使得最優(yōu)解滿足 f(x)+yT g(x)=0其中，y=0yTg(x)=0,13,行業(yè)重點(diǎn),SVM基本原理,將兩式帶回L(w,b,a)得到對(duì)偶問(wèn)題的表達(dá)式:,14,行業(yè)重點(diǎn),SVM基本原理,新問(wèn)題加上其限制條件是（對(duì)偶問(wèn)題）: 這個(gè)就是我們需要最終優(yōu)化的式子。至此，得到了線性可分問(wèn)題的優(yōu)化式子。 求解這個(gè)式子，有很多的方法，比如SMO等,15,行

7、業(yè)重點(diǎn),SVM基本原理,線性可分這種假設(shè)局限性比較大，接下來(lái)談?wù)劸€性不可分的情況： 下圖就是一個(gè)典型的線性不可分的分類(lèi)圖，我們沒(méi)有辦法用一條直線去將其分成兩個(gè)區(qū)域，使每個(gè)區(qū)域只包含一種顏色的點(diǎn)。,線性不可分類(lèi)型,16,行業(yè)重點(diǎn),SVM基本原理,要想在這種情況下的分類(lèi)器，有兩種方式: 第一種:用曲線去將其完全分開(kāi),17,行業(yè)重點(diǎn),SVM基本原理,第二種：還是用直線，不過(guò)不用去保證可分性，就是包容那些分錯(cuò)的情況，這里我們得加入懲罰函數(shù)，使得點(diǎn)分錯(cuò)的情況越合理越好。 很多時(shí)候，不是在訓(xùn)練的時(shí)候分類(lèi)函數(shù)越完美越好，因?yàn)橛?xùn)練函數(shù)中有些數(shù)據(jù)本來(lái)就是噪聲，可能就是在人工加上分類(lèi)標(biāo)簽的時(shí)候出現(xiàn)了錯(cuò)誤，如果在訓(xùn)

8、練（學(xué)習(xí)）的時(shí)候把這些錯(cuò)誤的點(diǎn)學(xué)習(xí)到了，那么模型在下次碰到這些錯(cuò)誤情況的時(shí)候就難免出錯(cuò)。 這種學(xué)習(xí)的時(shí)候?qū)W到了“噪聲”的過(guò)程就是一個(gè)過(guò)擬合（over-fitting）,18,行業(yè)重點(diǎn),過(guò)擬合,標(biāo)準(zhǔn)定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)h屬于H，如果存在其他的假設(shè)h屬于H,使得在訓(xùn)練樣例上h的錯(cuò)誤率比h小，但在整個(gè)實(shí)例分布上h比h的錯(cuò)誤率小，那么就說(shuō)假設(shè)h過(guò)度擬合訓(xùn)練數(shù)據(jù)。 -Machine LearningTom M.Mitchell,19,行業(yè)重點(diǎn),SVM基本原理,用直線怎么去分割線性不可分的點(diǎn)： 我們可以為分錯(cuò)的點(diǎn)加上一點(diǎn)懲罰，對(duì)一個(gè)分錯(cuò)的點(diǎn)的懲罰函數(shù)就是這個(gè)點(diǎn)到其正確位置的距離：,在上圖中，

9、藍(lán)色、紅色的直線分別為支持向量所在的邊界，綠色的線為決策函數(shù)，那些紫色的線表示分錯(cuò)的點(diǎn)到其相應(yīng)的決策面的距離，這樣我們可以在原函數(shù)上面加上一個(gè)懲罰函數(shù)，并且?guī)掀湎拗茥l件為：,20,行業(yè)重點(diǎn),SVM基本原理,公式中藍(lán)色的部分為在線性可分問(wèn)題的基礎(chǔ)上加上的懲罰函數(shù)部分，當(dāng)xi在正確一邊的時(shí)候，=0，R為全部的點(diǎn)的數(shù)目，C是一個(gè)由用戶(hù)去指定的系數(shù)，表示對(duì)分錯(cuò)的點(diǎn)加入多少的懲罰，當(dāng)C很大的時(shí)候，分錯(cuò)的點(diǎn)就會(huì)更少，但是過(guò)擬合的情況可能會(huì)比較嚴(yán)重，當(dāng)C很小的時(shí)候，分錯(cuò)的點(diǎn)可能會(huì)很多，不過(guò)可能由此得到的模型也會(huì)不太正確，所以如何選擇C是有很多學(xué)問(wèn)的，不過(guò)在大部分情況下就是通過(guò)經(jīng)驗(yàn)嘗試得到的。,接下來(lái)就是同

10、樣的，求解一個(gè)拉格朗日對(duì)偶問(wèn)題，得到一個(gè)原問(wèn)題的對(duì)偶問(wèn)題的表達(dá)式：,21,行業(yè)重點(diǎn),SVM基本原理,藍(lán)色的部分是與線性可分的對(duì)偶問(wèn)題表達(dá)式的不同之處。在線性不可分情況下得到的對(duì)偶問(wèn)題，不同的地方就是的范圍從0, +)，變?yōu)榱?, C，增加的懲罰沒(méi)有為對(duì)偶問(wèn)題增加什么復(fù)雜度。,22,行業(yè)重點(diǎn),SVM基本原理,核函數(shù)： SVM的關(guān)鍵在于核函數(shù)，低維空間向量集通常難于劃分，解決的方法是將它們映射到高維的特征空間。但這個(gè)辦法帶來(lái)的困難就是計(jì)算復(fù)雜度的增加，而核函數(shù)正好巧妙地解決了這個(gè)問(wèn)題。,我們可以讓空間從原本的線性空間變成一個(gè)更高維的空間，在這個(gè)高維的線性空間下，再用一個(gè)超平面進(jìn)行劃分。這兒舉個(gè)例子

11、，來(lái)理解一下如何利用空間的維度變得更高來(lái)幫助我們分類(lèi)的：,23,行業(yè)重點(diǎn),SVM基本原理,下圖是一個(gè)典型的線性不可分的情況 但是當(dāng)我們把這兩個(gè)類(lèi)似于橢圓形的點(diǎn)映射到一個(gè)高維空間后，映射函數(shù)為：,24,行業(yè)重點(diǎn),SVM基本原理,用這個(gè)函數(shù)可以將上圖的平面中的點(diǎn)映射到一個(gè)三維空間（z1,z2,z3)，并且對(duì)映射后的坐標(biāo)加以旋轉(zhuǎn)之后就可以得到一個(gè)線性可分的點(diǎn)集了。,25,行業(yè)重點(diǎn),SVM基本原理,為什么要映射到高維空間: 當(dāng)維度增加到無(wú)限維的時(shí)候，一定可以讓任意的兩個(gè)物體可分了。 舉一個(gè)哲學(xué)例子來(lái)說(shuō)：世界上本來(lái)沒(méi)有兩個(gè)完全一樣的物體，對(duì)于所有的兩個(gè)物體，我們可以通過(guò)增加維度來(lái)讓他們最終有所區(qū)別，比如

12、說(shuō)兩本書(shū)，從(顏色，內(nèi)容)兩個(gè)維度來(lái)說(shuō)，可能是一樣的，我們可以加上作者這個(gè)維度，實(shí)在不行我們還可以加入頁(yè)碼，可以加入擁有者，可以加入購(gòu)買(mǎi)地點(diǎn)，可以加入筆記內(nèi)容等等來(lái)使它們變得不同。,26,行業(yè)重點(diǎn),SVM基本原理,回憶剛剛得到的對(duì)偶問(wèn)題表達(dá)式 我們可以將紅色這個(gè)部分進(jìn)行改造，令： 這個(gè)式子所做的事情就是將線性的空間映射到高維的空間, k(x, xj)有很多種，下面列舉一些常見(jiàn)的核函數(shù)：,27,行業(yè)重點(diǎn),SVM基本原理,常用的核函數(shù)有以下4種： (1)線性核函數(shù)K(x,y)=xy； (2)多項(xiàng)式核函數(shù)K(x,y)=(xy)+1d； (3)徑向基函數(shù)K(x,y)=exp(-|x-y|2/d2) (

13、4)二層神經(jīng)網(wǎng)絡(luò)核函數(shù)K(x,y)=tanh(a(xy)+b) 小結(jié): 1. 只要選用適當(dāng)?shù)暮撕瘮?shù)，我們就可以得到高維空間的分類(lèi)函數(shù)。 2. 在SVM理論中，采用不同的核函數(shù)將導(dǎo)致不同的SVM算法,28,行業(yè)重點(diǎn),SVM面臨的一些問(wèn)題,經(jīng)典的支持向量機(jī)算法只給出了二類(lèi)分類(lèi)的算法，上面所談到的分類(lèi)都是二類(lèi)分類(lèi)的情況。而在數(shù)據(jù)挖掘的實(shí)際應(yīng)用中，一般要解決多類(lèi)的分類(lèi)問(wèn)題。 多類(lèi)分類(lèi)問(wèn)題可以通過(guò)多個(gè)二類(lèi)支持向量機(jī)的組合來(lái)解決。 主要有一對(duì)多組合模式、一對(duì)一組合模式1 vs 1 、和SVM決策樹(shù)；再就是通過(guò)構(gòu)造多個(gè)分類(lèi)器的組合來(lái)解決。主要原理是克服SVM固有的缺點(diǎn)，結(jié)合其他算法的優(yōu)勢(shì)，解決多類(lèi)問(wèn)題的分類(lèi)

14、精度。如：與粗集理論結(jié)合，形成一種優(yōu)勢(shì)互補(bǔ)的多類(lèi)問(wèn)題的組合分類(lèi)器。 一對(duì)多組合模式1 vs (N 1) ：需要訓(xùn)練N個(gè)分類(lèi)器，第i個(gè)分類(lèi)器是看看是屬于分類(lèi)i還是屬于分類(lèi)i的補(bǔ)集（除去i的N-1個(gè)分類(lèi)） 一對(duì)一組合模式1 vs 1 ：需要訓(xùn)練N * (N 1) / 2個(gè)分類(lèi)器，分類(lèi)器(i,j)能夠判斷某個(gè)點(diǎn)是屬于i還是屬于j,這種處理方式不僅在SVM中會(huì)用到，在很多其他的分類(lèi)中也是被廣泛用到 從已有的研究來(lái)看，1 vs 1的方式要優(yōu)于1 vs (N 1),SVM如何進(jìn)行多分類(lèi),29,行業(yè)重點(diǎn),SVM面臨的一些問(wèn)題,SVM算法對(duì)大規(guī)模訓(xùn)練樣本難以實(shí)施 由于SVM是借助二次規(guī)劃來(lái)求解支持向量，而求解

15、二次規(guī)劃將涉及m階矩陣的計(jì)算（m為樣本的個(gè)數(shù)），當(dāng)m數(shù)目很大時(shí)該矩陣的存儲(chǔ)和計(jì)算將耗費(fèi)大量的機(jī)器內(nèi)存和運(yùn)算時(shí)間。 針對(duì)以上問(wèn)題的主要改進(jìn)有有J.Platt的SMO算法、T.Joachims的SVM 、C.J.C.Burges等的PCGC、張學(xué)工的CSVM以及O.L.Mangasarian等的SOR算法,SVM處理大規(guī)模數(shù)據(jù)問(wèn)題,30,行業(yè)重點(diǎn),SVM面臨的一些問(wèn)題,SVM避免overfitting ，一種是調(diào)整之前說(shuō)的懲罰函數(shù)中的C，另一種其實(shí)從式子上來(lái)看，min |w|2這個(gè)式子可以讓函數(shù)更平滑，所以SVM是一種不太容易o(hù)ver-fitting的方法。,SVM會(huì)overfitting嗎,31

16、,行業(yè)重點(diǎn),TWIN SVM介紹,TWSVM(對(duì)支持向量機(jī))是一種通過(guò)解決SVM相關(guān)問(wèn)題確定兩個(gè)非平行平面的新的二元SVM分類(lèi)器,與傳統(tǒng)的SVM方法相比,Twin SVM不僅達(dá)到了更快的檢測(cè)速度及更優(yōu)的檢測(cè)效果,而且大大降低了算法的時(shí)間復(fù)雜度. Jayadeva和RKhemchandani于2007年提出了一種該改進(jìn)的二值數(shù)據(jù)的分類(lèi)器雙分界面支持向量機(jī)(TwinSVMs，以下簡(jiǎn)稱(chēng)TwSVMs)。它在形式上類(lèi)似于傳統(tǒng)的支持向量機(jī)，具有支持向量機(jī)的優(yōu)點(diǎn)，卻對(duì)大規(guī)模數(shù)據(jù)具有更好的處理能力。TWSVMs模型的目標(biāo)是為兩個(gè)類(lèi)各自得到一個(gè)分類(lèi)平面，屬于每個(gè)類(lèi)的數(shù)據(jù)盡量圍繞在與之相對(duì)應(yīng)的分類(lèi)平面周?chē)?。假設(shè)屬于1類(lèi)和-1類(lèi)的數(shù)據(jù)點(diǎn)分別由矩陣A和矩陣B來(lái)表示,1類(lèi)和-1類(lèi)中模型的個(gè)數(shù)分別是m1和m2，那么TWSVMs分類(lèi)器可以通過(guò)以下一對(duì)二次規(guī)劃問(wèn)題得到：,什么是twin svm,32,行業(yè)重點(diǎn),TWIN SVM介紹,什么是twin svm,TWSVM算法為每一個(gè)類(lèi)都找到一個(gè)超平面，式1中的第1項(xiàng)是屬于A類(lèi)的所有數(shù)據(jù)點(diǎn)到與之對(duì)應(yīng)的分類(lèi)面的距離的平方和，第2項(xiàng)是誤差變量的和。式2中各項(xiàng)的意義與之類(lèi)似。,33,行業(yè)重點(diǎn),TWIN SVM介紹,通過(guò)解以上一對(duì)二次規(guī)劃問(wèn)題，可以得到TWSVMs的分類(lèi)面：,twin svm的原問(wèn)題,34,行業(yè)重點(diǎn),TWIN SVM介紹,twin sv