數(shù)學(xué)建模-支持向量機(jī).ppt

1、支持向量機(jī) support vector machine，SVM,Outline,SVM的理論基礎(chǔ) 線性判別函數(shù)和判別面 最優(yōu)分類(lèi)面 支持向量機(jī),SVM的理論基礎(chǔ),傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法只有在樣本趨向無(wú)窮大時(shí)，其性能才有理論的保證。統(tǒng)計(jì)學(xué)習(xí)理論（STL）研究有限樣本情況下的機(jī)器學(xué)習(xí)問(wèn)題。SVM的理論基礎(chǔ)就是統(tǒng)計(jì)學(xué)習(xí)理論。 傳統(tǒng)的統(tǒng)計(jì)模式識(shí)別方法在進(jìn)行機(jī)器學(xué)習(xí)時(shí)，強(qiáng)調(diào)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。而單純的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化會(huì)產(chǎn)生“過(guò)學(xué)習(xí)問(wèn)題”，其推廣能力較差。 推廣能力是指: 將學(xué)習(xí)機(jī)器(即預(yù)測(cè)函數(shù),或稱(chēng)學(xué)習(xí)函數(shù)、學(xué)習(xí)模型)對(duì)未來(lái)輸出進(jìn)行正確預(yù)測(cè)的能力。,過(guò)學(xué)習(xí)問(wèn)題,“過(guò)學(xué)習(xí)問(wèn)題”：某些情況下，當(dāng)訓(xùn)練誤差過(guò)小反而

2、會(huì)導(dǎo)致推廣能力的下降。 例如：對(duì)一組訓(xùn)練樣本(x,y),x分布在實(shí)數(shù)范圍內(nèi)，y取值在0，1之間。無(wú)論這些樣本是由什么模型產(chǎn)生的，我們總可以用y=sin(w*x)去擬合，使得訓(xùn)練誤差為0.,SVM,由于SVM 的求解最后轉(zhuǎn)化成二次規(guī)劃問(wèn)題的求解，因此SVM 的解是全局唯一的最優(yōu)解 SVM在解決小樣本、非線性及高維模式識(shí)別問(wèn)題中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中 Joachims 最近采用SVM在Reuters-21578來(lái)進(jìn)行文本分類(lèi)，并聲稱(chēng)它比當(dāng)前發(fā)表的其他方法都好,Outline,SVM的理論基礎(chǔ) 線性判別函數(shù)和判別面 最優(yōu)分類(lèi)面 支持向量機(jī),線性判別函數(shù)和判

3、別面,一個(gè)線性判別函數(shù)(discriminant function)是指由x的各個(gè)分量的線性組合而成的函數(shù) 兩類(lèi)情況:對(duì)于兩類(lèi)問(wèn)題的決策規(guī)則為 如果g(x)0，則判定x屬于C1， 如果g(x)0，則判定x屬于C2， 如果g(x)=0，則可以將x任意 分到某一類(lèi)或者拒絕判定。,線性判別函數(shù),下圖表示一個(gè)簡(jiǎn)單的線性分類(lèi)器，具有d個(gè)輸入的單元，每個(gè)對(duì)應(yīng)一個(gè)輸入向量在各維上的分量值。該圖類(lèi)似于一個(gè)神經(jīng)元。,超平面,方程g(x)=0定義了一個(gè)判定面，它把歸類(lèi)于C1的點(diǎn)與歸類(lèi)于C2的點(diǎn)分開(kāi)來(lái)。 當(dāng)g(x)是線性函數(shù)時(shí)，這個(gè)平面被稱(chēng)為“超平面”(hyperplane)。 當(dāng)x1和x2都在判定面上時(shí)， 這表明

4、w和超平面上任意向量正交， 并稱(chēng)w為超平面的法向量。 注意到：x1-x2表示 超平面上的一個(gè)向量,判別函數(shù)g(x)是特征空間中某點(diǎn)x到超平面的距離的一種代數(shù)度量,從下圖容易看出,上式也可以表示為： r= g(x)/|w|。當(dāng)x=0時(shí)，表示原點(diǎn)到超平面的距離，r0= g(0)/|w|=w0/|w|，標(biāo)示在上圖中。,總之： 線性判別函數(shù)利用一個(gè)超平面把特征空間分隔成兩個(gè)區(qū)域。 超平面的方向由法向量w確定，它的位置由閾值w0確定。 判別函數(shù)g(x)正比于x點(diǎn)到超平面的代數(shù)距離（帶正負(fù)號(hào)）。當(dāng)x點(diǎn)在超平面的正側(cè)時(shí)，g(x)0；當(dāng)x點(diǎn)在超平面的負(fù)側(cè)時(shí)，g(x)0,多類(lèi)的情況,利用線性判別函數(shù)設(shè)計(jì)多類(lèi)分類(lèi)

5、器有多種方法。例如 可以把k類(lèi)問(wèn)題轉(zhuǎn)化為k個(gè)兩類(lèi)問(wèn)題，其中第i 個(gè)問(wèn)題是用線性判別函數(shù)把屬于Ci類(lèi)與不屬于Ci類(lèi)的點(diǎn)分開(kāi)。 更復(fù)雜一點(diǎn)的方法是用k(k-1)/2個(gè)線性判別函數(shù)，把樣本分為k個(gè)類(lèi)別，每個(gè)線性判別函數(shù)只對(duì)其中的兩個(gè)類(lèi)別分類(lèi)。,廣義線性判別函數(shù),在一維空間中，沒(méi)有任何一個(gè)線性函數(shù)能解決下述劃分問(wèn)題（黑紅各代表一類(lèi)數(shù)據(jù)），可見(jiàn)線性判別函數(shù)有一定的局限性。,廣義線性判別函數(shù),如果建立一個(gè)二次判別函數(shù)g(x)=(x-a)(x-b)，則可以很好的解決上述分類(lèi)問(wèn)題。 決策規(guī)則仍是：如果g(x)0，則判定x屬于C1，如果g(x)0，則判定x屬于C2，如果g(x)=0，則可以將x任意分到某一類(lèi)或者

6、拒絕判定。,廣義線性判別函數(shù),廣義線性判別函數(shù),設(shè)計(jì)線性分類(lèi)器,Outline,SVM的理論基礎(chǔ) 線性判別函數(shù)和判別面 最優(yōu)分類(lèi)面 支持向量機(jī),最優(yōu)分類(lèi)面,SVM 是從線性可分情況下的最優(yōu)分類(lèi)面發(fā)展而來(lái)的, 基本思想可用圖2的兩維情況說(shuō)明.,圖中, 方形點(diǎn)和圓形點(diǎn)代表兩類(lèi)樣本, H 為分類(lèi)線,H1, H2分別為過(guò)各類(lèi)中離分類(lèi)線最近的樣本且平行于分類(lèi)線的直線, 它們之間的距離叫做分類(lèi)間隔(margin)。 所謂最優(yōu)分類(lèi)線就是要求分類(lèi)線不但能將兩類(lèi)正確分開(kāi)(訓(xùn)練錯(cuò)誤率為0),而且使分類(lèi)間隔最大. 推廣到高維空間，最優(yōu)分類(lèi)線就變?yōu)樽顑?yōu)分類(lèi)面。,最優(yōu)分類(lèi)面,如何求最優(yōu)分類(lèi)面,最優(yōu)分類(lèi)面,Outline

7、,SVM的理論基礎(chǔ) 線性判別函數(shù)和判別面 最優(yōu)分類(lèi)面 支持向量機(jī),支持向量機(jī),上節(jié)所得到的最優(yōu)分類(lèi)函數(shù)為： 該式只包含待分類(lèi)樣本與訓(xùn)練樣本中的支持向量的內(nèi)積 運(yùn)算，可見(jiàn),要解決一個(gè)特征空間中的最優(yōu)線性分類(lèi)問(wèn)題,我們只需要知道這個(gè)空間中的內(nèi)積運(yùn)算即可。 對(duì)非線性問(wèn)題, 可以通過(guò)非線性變換轉(zhuǎn)化為某個(gè)高維空間中的線性問(wèn)題, 在變換空間求最優(yōu)分類(lèi)面. 這種變換可能比較復(fù)雜, 因此這種思路在一般情況下不易實(shí)現(xiàn).,支持向量機(jī),核函數(shù)的選擇,SVM方法的特點(diǎn),非線性映射是SVM方法的理論基礎(chǔ),SVM利用內(nèi)積核函數(shù)代替向高維空間的非線性映射; 對(duì)特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類(lèi)邊際的思想是SVM方法的核心; 支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類(lèi)決策中起決定作用的是支持向量。 SVM 是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法。它基本上不涉及概率測(cè)度及大數(shù)定律等,因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看,它避開(kāi)了從歸納到演繹的傳統(tǒng)過(guò)程,實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)導(dǎo)推理”(transductive inference) ,大大簡(jiǎn)化了通常的分類(lèi)和回歸等問(wèn)題。,SVM方法的特點(diǎn),SVM 的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上避免了“維數(shù)災(zāi)難”。 少數(shù)支持向量決定了最終結(jié)果,這不但可以