Svm基本知識(shí)與原理PPT課件

1、.,1,Svm基本知識(shí)與原理,張立新,*,.,2,SVM入門（一）SVM的八股簡(jiǎn)介 支持向量機(jī)(Support Vector Machine)是Vapnik等于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。 支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度）和學(xué)習(xí)能力（即無(wú)錯(cuò)誤地識(shí)別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力 。 所謂VC維是對(duì)函數(shù)類的一種度量，可以簡(jiǎn)單的理解為問(wèn)題的復(fù)雜程度，VC維越高，一個(gè)問(wèn)題

2、就越復(fù)雜。結(jié)構(gòu)風(fēng)險(xiǎn)最小聽上去文縐縐，其實(shí)說(shuō)的也無(wú)非是下面這回事。,*,.,3,機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近，但毫無(wú)疑問(wèn)，真實(shí)模型一定是不知道的。那么我們選擇的假設(shè)與問(wèn)題真實(shí)解之間究竟有多大差距，我們就沒(méi)法得知。這個(gè)與問(wèn)題真實(shí)解之間的誤差，就叫做風(fēng)險(xiǎn)。我們選擇了一個(gè)假設(shè)后，真實(shí)誤差無(wú)從得知， 但我們可以用某些可以掌握的量來(lái)逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實(shí)結(jié)果（因?yàn)闃颖臼且呀?jīng)標(biāo)注過(guò)的數(shù)據(jù)，是準(zhǔn)確的數(shù)據(jù)）之間的差值來(lái)表示。這個(gè)差值叫做經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(w)。以前的機(jī)器學(xué)習(xí)方法都把經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化作為努力的目標(biāo)，但后來(lái)發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到1

3、00%的正確率，在真實(shí)分類時(shí)卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。,*,.,4,此時(shí)的情況便是選擇了一個(gè)足夠復(fù)雜的分類函數(shù)，能夠精確的記住每一個(gè)樣本，但對(duì)樣本之外的數(shù)據(jù)一律分類錯(cuò)誤。 統(tǒng)計(jì)學(xué)習(xí)引入了泛化誤差界的概念，就是指真實(shí)風(fēng)險(xiǎn)應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗(yàn)風(fēng)險(xiǎn)，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險(xiǎn)，代表了我們?cè)诙啻蟪潭壬峡梢孕湃畏诸惼髟谖粗獦颖旧戏诸惖慕Y(jié)果。很顯然，第二部分是沒(méi)有辦法精確計(jì)算的，因此只能給出一個(gè)估計(jì)的區(qū)間，也使得整個(gè)誤差只能計(jì)算上界，而無(wú)法計(jì)算準(zhǔn)確的值。 置信風(fēng)險(xiǎn)與兩個(gè)量有關(guān)，一是樣本數(shù)量，顯然給定的樣本數(shù)量越大，我們的學(xué)習(xí)結(jié)果越有可能正確，此時(shí)置信風(fēng)險(xiǎn)越

4、??；二是分類函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險(xiǎn)會(huì)變大。 R(w)Remp(w)+(h/n)統(tǒng)計(jì)學(xué)習(xí)的目標(biāo)從經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化變?yōu)榱藢で蠼?jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的和最小，即結(jié)構(gòu)風(fēng)險(xiǎn)最小。,*,.,5,SVM入門（二）線性分類器Part 1,C1和C2是要區(qū)分的兩個(gè)類別，中間的直線就是一個(gè)分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。,什么叫線性函數(shù)呢？在一維空間里就是一個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱超平面（

5、Hyper Plane）！ 實(shí)際上，一個(gè)線性函數(shù)是一個(gè)實(shí)值函數(shù)，而我們的分類問(wèn)題需要離散的輸出值，這時(shí)候只需要簡(jiǎn)單的在實(shí)值函數(shù)的基礎(chǔ)上附加一個(gè)閾值即可，通過(guò)分類函數(shù)執(zhí)行時(shí)得到的值大于還是小于這個(gè)閾值來(lái)確定類別歸屬。,*,.,6,例如我們有一個(gè)線性函數(shù) g(x)=wx+b 我們可以取閾值為0，這樣當(dāng)有一個(gè)樣本xi需要判別的時(shí)候，我們就看g(xi)的值。若g(xi)0，就判別為類別C1，若g(xi)0，則判別為類別C2。此時(shí)也等價(jià)于給函數(shù)g(x)附加一個(gè)符號(hào)函數(shù)sgn()，即f(x)=sgn g(x)是我們真正的判別函數(shù)。 關(guān)于g(x)=wx+b這個(gè)表達(dá)式要注意三點(diǎn)：一，式中的x不是二維坐標(biāo)系中的

6、橫軸，而是樣本的向量表示。二，這個(gè)形式并不局限于二維的情況，在n維空間中仍然可以使用這個(gè)表達(dá)式，只是式中的w成為了n維向量；三，g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是g(x)=0，即wx+b=0，我們也把這個(gè)函數(shù)叫做分類面。 實(shí)際上很容易看出來(lái)，中間那條分界線并不是唯一的，我們把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯(cuò)，仍然可以達(dá)到上面說(shuō)的效果，稍微平移一下，也可以。,*,.,7,SVM入門（三）線性分類器Part 2,對(duì)于樣本分類的不適定問(wèn)題，需要有一個(gè)指標(biāo)來(lái)衡量解決方案的好壞，而分類間隔是一個(gè)比較好的指標(biāo)。我們定義一個(gè)樣本點(diǎn)到超平面的間隔：i=yi(wxi+b)。現(xiàn)在把w和b

7、進(jìn)行歸一化，即用w/|w|和b/|w|分別代替原來(lái)的w和b，那么間隔就可以寫成,這個(gè)公式是不是看上去有點(diǎn)眼熟？沒(méi)錯(cuò)，這不就是解析幾何中點(diǎn)xi到直線g(x)=0的距離公式嘛！（推廣一下，是到超平面g(x)=0的距離) 。|w|叫做向量w的范數(shù)，范數(shù)是對(duì)向量長(zhǎng)度的一種度量。當(dāng)用歸一化的w和b代替原值之后的間隔有一個(gè)專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點(diǎn)到超平面的歐氏距離，同樣可以定義一個(gè)點(diǎn)的集合（就是一組樣本）到某個(gè)超平面的距離為此集合中離超平面最近的點(diǎn)的距離。下面這張圖更加直觀的展示出了幾何間隔的現(xiàn)實(shí)含義：,*,.,8,H是分類面，而H1和H2是平行于H，且過(guò)離H最近的兩類樣本的直線，

8、H1與H，H2與H之間的距離就是幾何間隔。誤分次數(shù)一定程度上代表分類器的誤差。幾何間隔與樣本的誤分次數(shù)間存在關(guān)系：,注意到間隔與|w|是成反比的，因此最大化間隔與最小化|w|完全是一回事。而我們常用的方法并不是固定|w|的大小而尋求最大幾何間隔，而是固定間隔，尋找最小的|w|。,*,.,9,SVM入門（四）線性分類器的求解問(wèn)題的描述與轉(zhuǎn)化,由上節(jié)可知 我們的目標(biāo)函數(shù)：,用另一個(gè)完全等價(jià)的目標(biāo)函數(shù)來(lái)代替，那就是：,如果直接來(lái)解這個(gè)求最小值問(wèn)題，很容易看出當(dāng)|w|=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。反映在圖中，就是H1與H2兩條直線間的距離無(wú)限大，這個(gè)時(shí)候，所有的樣本點(diǎn)（無(wú)論正樣本還是負(fù)樣本）都跑

9、到了H1和H2中間，而我們?cè)镜囊鈭D是，H1右側(cè)的 被分為正類，H2 左側(cè)的被分為負(fù)類，位于兩類中間的樣本則拒絕分類。這下可好，所有樣本點(diǎn)都進(jìn) 入了無(wú)法分類的灰色地帶。造成這種結(jié)果的原因是在描述問(wèn)題的時(shí)候只考慮了目標(biāo)，而沒(méi)有加入約束條件， 體現(xiàn)在我們的問(wèn)題中就是樣本點(diǎn)必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能跑到兩者中間。,*,.,10,我們把間隔固定為1，這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為1，也就意味著集合中的其他點(diǎn)間隔都不會(huì)小于1，按照間隔的定義，滿足這些條件就相當(dāng)于讓下面的式子總是成立： yi(wxi)+b1 (i=1,2,l) （l是總的樣本數(shù)） 經(jīng)常用變換

10、過(guò)的形式： yi(wxi)+b-10 (i=1,2,l) （l是總的樣本數(shù)） 我們分類問(wèn)題也被轉(zhuǎn)化成一個(gè)帶約束的最小值的問(wèn)題：,在這個(gè)問(wèn)題中，自變量就是w，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)這種規(guī)劃問(wèn)題有個(gè)很有名氣的稱呼二次規(guī)劃，而且可以更進(jìn)一步的說(shuō)，由于它的可行域是一個(gè)凸集，因此它是一個(gè)凸二次規(guī)劃。凸二次規(guī)劃讓人喜歡的地方就在于，它有解，而且可以找到。,*,.,11,完整重復(fù)。,我們想求得這樣一個(gè)線性函數(shù)g(x)=wx+b 求這樣的g(x)的過(guò)程就是求w和b兩個(gè)參數(shù)的過(guò)程。求g(x)的時(shí)候，w才是變量。那么w是誰(shuí)決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個(gè)

11、樣本,點(diǎn)，三條直線的位置實(shí)際上就唯一確定了。樣本確定了w，用數(shù)學(xué)的語(yǔ)言描述，就是w可以表示為樣本的某種組合： w=1x1+2x2+nxn 式子中的i是一個(gè)一個(gè)的數(shù)，而xi是樣本點(diǎn)，因而是向量，n就是總樣本點(diǎn)的個(gè)數(shù)。嚴(yán)格區(qū)別數(shù)字與向量的乘積和向量間的乘積，用1x1表示數(shù)字和向量的乘積，而用表示向量x1,x2的內(nèi)積。,*,.,12,因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：g(x)=+b w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)。因此用下面這個(gè)式子表示才算完整： w=1y1x1+2y2x2+nynxn （式1） 其中的yi就是第i個(gè)樣本的標(biāo)簽，它等于1或者-1。 其實(shí)以上式子的那一堆拉格朗日乘子中

12、，只有很少的一部分不等于 0，這部分不等于0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在H1和H2上，也正是這部分樣本唯一的確定了分類函數(shù)，當(dāng)然，更嚴(yán)格的說(shuō)，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以，即便有三五個(gè)都落在上面，我們也不是全都需 要。這部分我們真正需要的樣本點(diǎn)，就叫做支持（撐）向量。 因此原來(lái)的g(x)表達(dá)式可以寫為：,*,.,13,部分可以從內(nèi)積符號(hào)中拿出來(lái)，得到g(x)的式子為：,*,.,14,SVM入門（五）為何需要核函數(shù),問(wèn)題只是它不是一個(gè)線性函數(shù)，但是，下面要注意看了，新建一個(gè)向量y和a：,g(x)=f(y)=ay 在任意維度的空間中，這種形式的

13、函數(shù)都是一個(gè)線性函數(shù)，因?yàn)樽宰兞縴的次數(shù)不大于1。,看出妙在哪了么？原來(lái)在二維空間中一個(gè)線性不可分的問(wèn)題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問(wèn)題的基本思路向高維空間轉(zhuǎn)化，使其變得線性可分。,*,.,15,如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后 g(x)=K(w,x)+b f(x)=+b 這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們直接拿低維的輸入往g(x)里面代就可以了（這回的g(x)就不是線性函數(shù)啦，因?yàn)槟悴荒鼙ＷCK(w,x)這個(gè)表達(dá)式里的x次數(shù)不高于1）。萬(wàn)幸的是，這樣的K(w,x)確實(shí)存在，它被稱作核函數(shù)，而且還不止一個(gè)，事實(shí)上，只要是滿足了

14、Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過(guò)某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。,這就是說(shuō)，盡管給的問(wèn)題是線性不可分的，但是我們就硬當(dāng)它是線性問(wèn)題來(lái)求解，只不過(guò)求解過(guò)程中，凡是要求內(nèi)積的時(shí)候就用你選定的核函數(shù)來(lái)算。,這樣求出來(lái)的再和你選定的核函數(shù)組合，就得到分類器啦！,*,.,16,SVM入門（六）松弛變量,現(xiàn)在我們已經(jīng)把一個(gè)本來(lái)線性不可分的文本分類問(wèn)題，通過(guò)映射到高維空間而變成了線性可分的。圓形和方形的點(diǎn)各有成千上萬(wàn)個(gè)現(xiàn)在想象我們有另一個(gè)訓(xùn)練集，只比原先這個(gè)訓(xùn)練集多了一個(gè)樣本，映射到高維空間以后，也就多了一個(gè)樣本點(diǎn)，但是這個(gè)樣本的位置

15、是這樣的：,就是圖中黃色那個(gè)點(diǎn)，它是方形的，因而它是負(fù)類的一個(gè)樣本，這單獨(dú)的一個(gè)樣本，使得原本線性可分的問(wèn)題變成了線性不可分的。這樣類似的問(wèn)題叫做“近似線性可分”的問(wèn)題。,*,.,17,其實(shí)我們會(huì)覺(jué)得，更有可能的是，這個(gè)樣本點(diǎn)壓根就是錯(cuò)誤，是噪聲，是提供訓(xùn)練集的人在人工分類時(shí)錯(cuò)放進(jìn)去的。所以我們會(huì)簡(jiǎn)單的忽略這個(gè)樣本點(diǎn)，仍然使用原來(lái)的分類器，其效果絲毫不受影響。 但這種對(duì)噪聲的容錯(cuò)性是人的思維帶來(lái)的，我們的程序可沒(méi)有。由于我們?cè)镜膬?yōu)化問(wèn)題的表達(dá)式中，確實(shí)要考慮所有的樣本點(diǎn)，在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會(huì)使得整個(gè)問(wèn)題無(wú)解。

16、這種解法其實(shí)也叫做“硬間隔”分類法，因?yàn)樗残缘囊笏袠颖军c(diǎn)都滿足和分類平面間的距離必須大于某個(gè)值。因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點(diǎn)的控制，這是很危險(xiǎn)的。解決方法也很明顯，就是仿照人的思路，允許一些點(diǎn)到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點(diǎn)的間距尺度不太一樣，因此用間隔來(lái)衡量有利于我們表達(dá)形式的簡(jiǎn)潔。我們?cè)葘?duì)樣本點(diǎn)的要求是：,*,.,18,意思是說(shuō)離分類面最近的樣本點(diǎn)函數(shù)間隔也要比1大。如果要引入容錯(cuò)性，就給1這個(gè)硬性的閾值加一個(gè)松弛變量，即允許,因?yàn)樗沙谧兞渴欠秦?fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點(diǎn)出現(xiàn)這種間隔比1小的情況時(shí)，意

17、味著我們放棄了對(duì)這些點(diǎn)的精確分類，而這對(duì)我們的分類器來(lái)說(shuō)是種損失。但是放棄這些點(diǎn)也帶來(lái)了好處，那就是使分類面不必向這些點(diǎn)的方向移動(dòng)，因而可以得到更大的幾何間隔。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多?；仡櫸覀?cè)嫉挠查g隔分類對(duì)應(yīng)的優(yōu)化問(wèn)題,*,.,19,|w|2就是我們的目標(biāo)函數(shù)，希望它越小越好，因而損失就是一個(gè)能使之變大的量。那如何來(lái)衡量損失，有兩種常用的方式，有人喜歡用,把損失加入到目標(biāo)函數(shù)里的時(shí)候，就需要一個(gè)懲罰因子，原來(lái)的優(yōu)化問(wèn)題就變成了下面這樣：,注意 一：并非所有的樣本點(diǎn)都有一個(gè)松弛變量與其對(duì)應(yīng)。實(shí)際上只有“離群點(diǎn)”才有。,*,.,20,所有沒(méi)離群的點(diǎn)松弛變量都等于0 二是松弛變量的值實(shí)際上標(biāo)示出了對(duì)應(yīng)的點(diǎn)到底離群有多遠(yuǎn)，值越大，點(diǎn)就越遠(yuǎn)。 三是懲罰因子C決定了你有多重視離群點(diǎn)帶來(lái)的損失，顯然當(dāng)所有離群點(diǎn)的松弛變量的和一定時(shí)，你定的C越大，對(duì)目標(biāo)函數(shù)的損失也越大，此時(shí)就暗示著你非常不愿意放棄這些離群點(diǎn)，最極端的情況是你把C定為無(wú)限大，這樣只要稍有一個(gè)點(diǎn)離群，目標(biāo)函數(shù)的值馬上變成無(wú)限大，馬上讓問(wèn)題變成無(wú)解，這就退化成了硬間隔問(wèn)題。 四是懲罰因子C不是一個(gè)變量，整個(gè)優(yōu)化問(wèn)題在解的時(shí)候，C是一個(gè)你必須事先指定的值，指定這個(gè)值以后，解一下，得到一個(gè)分類器，然后用測(cè)試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個(gè)C