Svm基本知識與原理.ppt

Svm基本知識與原理,張立新,SVM入門（一）SVM的八股簡介 支持向量機(Support Vector Machine)是Vapnik等于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學(xué)習問題中。 支持向量機方法是建立在統(tǒng)計學(xué)習理論的VC 維理論和結(jié)構(gòu)風險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習精度）和學(xué)習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力 。 所謂VC維是對函數(shù)類的一種度量，可以簡單的理解為問題的復(fù)雜程度，VC維越高，一個問題就越復(fù)雜。結(jié)構(gòu)風險最小聽上去文縐縐，其實說的也無非是下面這回事。,機器學(xué)習本質(zhì)上就是一種對問題真實模型的逼近，但毫無疑問，真實模型一定是不知道的。那么我們選擇的假設(shè)與問題真實解之間究竟有多大差距，我們就沒法得知。這個與問題真實解之間的誤差，就叫做風險。我們選擇了一個假設(shè)后，真實誤差無從得知， 但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實結(jié)果（因為樣本是已經(jīng)標注過的數(shù)據(jù)，是準確的數(shù)據(jù)）之間的差值來表示。這個差值叫做經(jīng)驗風險Remp(w)。以前的機器學(xué)習方法都把經(jīng)驗風險最小化作為努力的目標，但后來發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達到100%的正確率，在真實分類時卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。,此時的情況便是選擇了一個足夠復(fù)雜的分類函數(shù)，能夠精確的記住每一個樣本，但對樣本之外的數(shù)據(jù)一律分類錯誤。 統(tǒng)計學(xué)習引入了泛化誤差界的概念，就是指真實風險應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知樣本上分類的結(jié)果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準確的值。 置信風險與兩個量有關(guān)，一是樣本數(shù)量，顯然給定的樣本數(shù)量越大，我們的學(xué)習結(jié)果越有可能正確，此時置信風險越??；二是分類函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。 R(w)Remp(w)+(h/n)統(tǒng)計學(xué)習的目標從經(jīng)驗風險最小化變?yōu)榱藢で蠼?jīng)驗風險與置信風險的和最小，即結(jié)構(gòu)風險最小。,SVM入門（二）線性分類器Part 1,C1和C2是要區(qū)分的兩個類別，中間的直線就是一個分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。,什么叫線性函數(shù)呢？在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個統(tǒng)一的名稱超平面（Hyper Plane）！ 實際上，一個線性函數(shù)是一個實值函數(shù)，而我們的分類問題需要離散的輸出值，這時候只需要簡單的在實值函數(shù)的基礎(chǔ)上附加一個閾值即可，通過分類函數(shù)執(zhí)行時得到的值大于還是小于這個閾值來確定類別歸屬。,例如我們有一個線性函數(shù) g(x)=wx+b 我們可以取閾值為0，這樣當有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)0，就判別為類別C1，若g(xi)0，則判別為類別C2。此時也等價于給函數(shù)g(x)附加一個符號函數(shù)sgn()，即f(x)=sgn g(x)是我們真正的判別函數(shù)。 關(guān)于g(x)=wx+b這個表達式要注意三點：一，式中的x不是二維坐標系中的橫軸，而是樣本的向量表示。二，這個形式并不局限于二維的情況，在n維空間中仍然可以使用這個表達式，只是式中的w成為了n維向量；三，g(x)不是中間那條直線的表達式，中間那條直線的表達式是g(x)=0，即wx+b=0，我們也把這個函數(shù)叫做分類面。 實際上很容易看出來，中間那條分界線并不是唯一的，我們把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯，仍然可以達到上面說的效果，稍微平移一下，也可以。,SVM入門（三）線性分類器Part 2,對于樣本分類的不適定問題，需要有一個指標來衡量解決方案的好壞，而分類間隔是一個比較好的指標。我們定義一個樣本點到超平面的間隔：i=yi(wxi+b)?，F(xiàn)在把w和b進行歸一化，即用w/|w|和b/|w|分別代替原來的w和b，那么間隔就可以寫成,這個公式是不是看上去有點眼熟？沒錯，這不就是解析幾何中點xi到直線g(x)=0的距離公式嘛?。ㄍ茝V一下，是到超平面g(x)=0的距離) 。|w|叫做向量w的范數(shù)，范數(shù)是對向量長度的一種度量。當用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點到超平面的歐氏距離，同樣可以定義一個點的集合（就是一組樣本）到某個超平面的距離為此集合中離超平面最近的點的距離。下面這張圖更加直觀的展示出了幾何間隔的現(xiàn)實含義：,H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。誤分次數(shù)一定程度上代表分類器的誤差。幾何間隔與樣本的誤分次數(shù)間存在關(guān)系：,注意到間隔與|w|是成反比的，因此最大化間隔與最小化|w|完全是一回事。而我們常用的方法并不是固定|w|的大小而尋求最大幾何間隔，而是固定間隔，尋找最小的|w|。,SVM入門（四）線性分類器的求解問題的描述與轉(zhuǎn)化,由上節(jié)可知 我們的目標函數(shù)：,用另一個完全等價的目標函數(shù)來代替，那就是：,如果直接來解這個求最小值問題，很容易看出當|w|=0的時候就得到了目標函數(shù)的最小值。反映在圖中，就是H1與H2兩條直線間的距離無限大，這個時候，所有的樣本點（無論正樣本還是負樣本）都跑到了H1和H2中間，而我們原本的意圖是，H1右側(cè)的 被分為正類，H2 左側(cè)的被分為負類，位于兩類中間的樣本則拒絕分類。這下可好，所有樣本點都進 入了無法分類的灰色地帶。造成這種結(jié)果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件， 體現(xiàn)在我們的問題中就是樣本點必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能跑到兩者中間。,我們把間隔固定為1，這是指把所有樣本點中間隔最小的那一點的間隔定為1，也就意味著集合中的其他點間隔都不會小于1，按照間隔的定義，滿足這些條件就相當于讓下面的式子總是成立： yi(wxi)+b1 (i=1,2,l) （l是總的樣本數(shù)） 經(jīng)常用變換過的形式： yi(wxi)+b-10 (i=1,2,l) （l是總的樣本數(shù)） 我們分類問題也被轉(zhuǎn)化成一個帶約束的最小值的問題：,在這個問題中，自變量就是w，而目標函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)這種規(guī)劃問題有個很有名氣的稱呼二次規(guī)劃，而且可以更進一步的說，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。凸二次規(guī)劃讓人喜歡的地方就在于，它有解，而且可以找到。,完整重復(fù)。,我們想求得這樣一個線性函數(shù)g(x)=wx+b 求這樣的g(x)的過程就是求w和b兩個參數(shù)的過程。求g(x)的時候，w才是變量。那么w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本,點，三條直線的位置實際上就唯一確定了。樣本確定了w，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合： w=1x1+2x2+nxn 式子中的i是一個一個的數(shù)，而xi是樣本點，因而是向量，n就是總樣本點的個數(shù)。嚴格區(qū)別數(shù)字與向量的乘積和向量間的乘積，用1x1表示數(shù)字和向量的乘積，而用表示向量x1,x2的內(nèi)積。,因此g(x)的表達式嚴格的形式應(yīng)該是：g(x)=+b w不僅跟樣本點的位置有關(guān)，還跟樣本的類別有關(guān)。因此用下面這個式子表示才算完整： w=1y1x1+2y2x2+nynxn （式1） 其中的yi就是第i個樣本的標簽，它等于1或者-1。 其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于 0，這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本唯一的確定了分類函數(shù)，當然，更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需 要。這部分我們真正需要的樣本點，就叫做支持（撐）向量。 因此原來的g(x)表達式可以寫為：,部分可以從內(nèi)積符號中拿出來，得到g(x)的式子為：,SVM入門（五）為何需要核函數(shù),問題只是它不是一個線性函數(shù)，但是，下面要注意看了，新建一個向量y和a：,g(x)=f(y)=ay 在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)，因為自變量y的次數(shù)不大于1。,看出妙在哪了么？原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路向高維空間轉(zhuǎn)化，使其變得線性可分。,如果有這樣的函數(shù)，那么當給了一個低維空間的輸入x以后 g(x)=K(w,x)+b f(x)=+b 這兩個函數(shù)的計算結(jié)果就完全一樣，我們直接拿低維的輸入往g(x)里面代就可以了（這回的g(x)就不是線性函數(shù)啦，因為你不能保證K(w,x)這個表達式里的x次數(shù)不高于1）。萬幸的是，這樣的K(w,x)確實存在，它被稱作核函數(shù)，而且還不止一個，事實上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個低維空間里的向量，能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。,這就是說，盡管給的問題是線性不可分的，但是我們就硬當它是線性問題來求解，只不過求解過程中，凡是要求內(nèi)積的時候就用你選定的核函數(shù)來算。,這樣求出來的再和你選定的核函數(shù)組合，就得到分類器啦！,SVM入門（六）松弛變量,現(xiàn)在我們已經(jīng)把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。圓形和方形的點各有成千上萬個現(xiàn)在想象我們有另一個訓(xùn)練集，只比原先這個訓(xùn)練集多了一個樣本，映射到高維空間以后，也就多了一個樣本點，但是這個樣本的位置是這樣的：,就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題叫做“近似線性可分”的問題。,其實我們會覺得，更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓(xùn)練集的人在人工分類時錯放進去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。 但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點，在此基礎(chǔ)上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。 這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點的控制，這是很危險的。解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點的間距尺度不太一樣，因此用間隔來衡量有利于我們表達形式的簡潔。我們原先對樣本點的要求是：,意思是說離分類面最近的樣本點函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許,因為松弛變量是非負的，因此最終的結(jié)果是要求間隔可以比1小。但是當某些點出現(xiàn)這種間隔比1小的情況時，意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多。回顧我們原始的硬間隔分類對應(yīng)的優(yōu)化問題,|w|2就是我們的目標函數(shù)，希望它越小越好，因而損失就是一個能使之變大的量。那如何來衡量損失，有兩種常用的方式，有人喜歡用,把損失加入到目標函數(shù)里的時候，就需要一個懲罰因子，原來的優(yōu)化問題就變成了下面這樣：,注意 一：并非所有的樣本點都有一個松弛變量與其對應(yīng)。實際上只有“離群點”才有。,所有沒離群的點松弛變量都等于0 二是松弛變量的值實際上標示出了對應(yīng)的點到底離群有多遠，值越大，點就越遠。 三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，你定的C越大，對目標函數(shù)的損失也越大，此時就暗示著你非常不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。 四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數(shù)據(jù)看看結(jié)果怎么樣，如