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

2、基本原理,線性可分類型,問題描述：我們要用一條直線，將上圖中黑色的點和白色的點分開，很顯然，圖上的這條直線就是我們要求的直線之一（可以有無數(shù)條這樣的直線）,5,行業(yè)重點,SVM基本原理,我們令深色的點 = -1， 淺色的點 = +1，直線f(x) = W X + b，這里的W、X是向量， 這種形式也等價于f(x) = W1X1 + W2X2 + WnXn + b 當(dāng)向量x的維度等于2的時候，f(x) 表示二維空間中的一條直線， 當(dāng)x的維度=3的時候，f(x) 表示3維空間中的一個平面，當(dāng)x的維度=n 3的時候，表示n維空間中的n-1維超平面。 當(dāng)有一個新的點x需要預(yù)測屬于哪個分類的時候， 我們

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

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

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

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

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

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

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

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

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

12、說兩本書，從(顏色，內(nèi)容)兩個維度來說，可能是一樣的，我們可以加上作者這個維度，實在不行我們還可以加入頁碼，可以加入擁有者，可以加入購買地點，可以加入筆記內(nèi)容等等來使它們變得不同。,26,行業(yè)重點,SVM基本原理,回憶剛剛得到的對偶問題表達(dá)式 我們可以將紅色這個部分進(jìn)行改造，令： 這個式子所做的事情就是將線性的空間映射到高維的空間, k(x, xj)有很多種，下面列舉一些常見的核函數(shù)：,27,行業(yè)重點,SVM基本原理,常用的核函數(shù)有以下4種： (1)線性核函數(shù)K(x,y)=xy； (2)多項式核函數(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ù)，我們就可以得到高維空間的分類函數(shù)。 2. 在SVM理論中，采用不同的核函數(shù)將導(dǎo)致不同的SVM算法,28,行業(yè)重點,SVM面臨的一些問題,經(jīng)典的支持向量機(jī)算法只給出了二類分類的算法，上面所談到的分類都是二類分類的情況。而在數(shù)據(jù)挖掘的實際應(yīng)用中，一般要解決多類的分類問題。 多類分類問題可以通過多個二類支持向量機(jī)的組合來解決。 主要有一對多組合模式、一對一組合模式1 vs 1 、和SVM決策樹；再就是通過構(gòu)造多個分類器的組合來解決。主要原理是克服SVM固有的缺點，結(jié)合其他算法的優(yōu)勢，解決多類問題的分類

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

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

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