支持向量機(jī)及其學(xué)習(xí)算法

1、支持向量機(jī)及其學(xué)習(xí)算法,主講:趙姝zhaoshuzs@163.com安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,主要內(nèi)容,支持向量機(jī)支持向量機(jī)的分類學(xué)習(xí)算法 用于函數(shù)擬合的支持向量機(jī) 支持向量機(jī)算法的研究與應(yīng)用仿真實(shí)例,傳統(tǒng)統(tǒng)計(jì)學(xué)是一種漸進(jìn)理論，研究的是樣本數(shù)目趨于無窮大時(shí)的極限特性。現(xiàn)有的學(xué)習(xí)方法多基于傳統(tǒng)統(tǒng)計(jì)學(xué)理論，但在實(shí)際應(yīng)用中，樣本往往是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方法在實(shí)際中的表現(xiàn)卻不盡人意，存在著一些難以克服的問題，比

2、如說如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學(xué)習(xí)問題、局部極小值問題等，從本質(zhì)上來說就是因?yàn)槔碚撋闲枰獰o窮樣本與實(shí)際中樣本有限的矛盾造成的。,與傳統(tǒng)統(tǒng)計(jì)學(xué)的方向不同，Vapnik等人提出了一個(gè)較完善的基于有限樣本的理論體系－－統(tǒng)計(jì)學(xué)習(xí)理論。統(tǒng)計(jì)學(xué)習(xí)理論是又一種通用的前饋神經(jīng)網(wǎng)絡(luò)，同樣可用于解決模式分類和非線性映射問題。支持向量機(jī)方法是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的通用學(xué)習(xí)方法，它具有全局優(yōu)化、適應(yīng)性強(qiáng)、理論完備、泛化性能好等優(yōu)點(diǎn) 。,支持向量機(jī)

3、（Support Vector Machine，SVM）,90年代中期，在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上發(fā)展出了一種通用的學(xué)習(xí)方法－－支持向量機(jī)。它根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷，以獲得最好的泛化能力。支持向量機(jī)在很多機(jī)器學(xué)習(xí)問題的應(yīng)用中已初步表現(xiàn)出很多優(yōu)于已有方法的性能。,支持向量機(jī)的理論最初來自于對數(shù)據(jù)分類問題的處理。對于線性可分?jǐn)?shù)據(jù)的二值分類，如果采用多層前向網(wǎng)絡(luò)來實(shí)現(xiàn)，其機(jī)理可以簡單描述為：系統(tǒng)隨機(jī)的產(chǎn)生一個(gè)

4、超平面并移動它，直到訓(xùn)練集合中屬于不同類別的點(diǎn)正好位于該超平面的不同側(cè)面，就完成了對網(wǎng)絡(luò)的設(shè)計(jì)要求。但是這種機(jī)理決定了不能保證最終所獲得的分割平面位于兩個(gè)類別的中心，這對于分類問題的容錯性是不利的。,保證最終所獲得的分割平面位于兩個(gè)類別的中心對于分類問題的實(shí)際應(yīng)用是很重要的。支持向量機(jī)方法很巧妙地解決了這一問題。該方法的機(jī)理可以簡單描述為：尋找一個(gè)滿足分類要求的最優(yōu)分類超平面，使得該超平面在保證分類精度的同時(shí)，能夠使超平面兩側(cè)的空白區(qū)

5、域最大化；從理論上來說，支持向量機(jī)能夠?qū)崿F(xiàn)對線性可分?jǐn)?shù)據(jù)的最優(yōu)分類。為了進(jìn)一步解決非線性問題，Vapnik等人通過引入核映射方法轉(zhuǎn)化為高維空間的線性可分問題來解決。,最優(yōu)分類超平面（Optimal Hyperplane ）,對于兩類線性可分的情形，可以直接構(gòu)造最優(yōu)超平面，使得樣本集中的所有樣本滿足如下條件：（1）能被某一超平面正確劃分；（2）距該超平面最近的異類向量與超平面之間的距離最大，即分類間隔（margin ）最大。,設(shè)訓(xùn)練

6、樣本輸入為 ， ， 對應(yīng)的期望輸出為 如果訓(xùn)練集中的所有向量均能被某超平面正確劃分，并且距離平面最近的異類向量之間的距離最大（即邊緣margin最大化），則該超平面為最優(yōu)超平面（Optimal Hyperplane ） 。,最優(yōu)分類面示意圖,支持向量Support Vector,其中距離超平面最近的異類向量

7、被稱為支持向量（Support Vector），一組支持向量可以唯一確定一個(gè)超平面。SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來，其超平面記為：為使分類面對所有樣本正確分類并且具備分類間隔，就要求它滿足如下約束：,,,可以計(jì)算出分類間隔為 ，因此構(gòu)造最優(yōu)超平面的問題就轉(zhuǎn)化為在約束式下求： 為了解決這個(gè)約束最優(yōu)化問題，引入下式所示的Lagrange函數(shù)： 其中 為Lagrange乘數(shù)。約

8、束最優(yōu)化問題的解由Lagrange函數(shù)的鞍點(diǎn)決定。,,利用Lagrange優(yōu)化方法可以將上述二次規(guī)劃問題轉(zhuǎn)化為其對偶問題，即在約束條件： 下對 求解下列函數(shù)的最大值： 如果 為最優(yōu)解，那么：,以上是在不等式約束下求二次函數(shù)極值問題，是一個(gè)二次規(guī)劃問題（Quadratic Programming，QP），存在唯一解。根據(jù)最優(yōu)性條件－－Karush-Kühn-Tucker條件（KKT條件），這

9、個(gè)優(yōu)化問題的解必須滿足：對多數(shù)樣本 將為零，取值不為零的 所對應(yīng)的樣本即為支持向量，它們通常只是全體樣本中很少的一部分。,,求解上述問題后得到的最優(yōu)分類函數(shù)是：在通過訓(xùn)練得到最優(yōu)超平面后,對于給定的未知樣本x，只需計(jì)算f (x)即可判斷x所屬的分類。,,若訓(xùn)練樣本集是線性不可分的，或事先不知道它是否線性可分，將允許存在一些誤分類的點(diǎn)，此時(shí)引入一個(gè)非負(fù)松弛變量 ，約束條件變?yōu)?目標(biāo)函數(shù)改為在以上約束條件下求

10、： 即折衷考慮最小錯分樣本和最大分類間隔。其中，C＞0 為懲罰因子 ，控制對錯分樣本的懲罰程度 。,,,線性不可分情況和線性可分情況的差別就在于可分模式中的約束條件中的 在不可分模式中換為了更嚴(yán)格的條件 。除了這一修正，線性不可分情況的約束最優(yōu)化問題中權(quán)值和閾值的最優(yōu)值的計(jì)算都和線性可分情況中的過程是相同的。,支持向量機(jī) （Support Vector Machine, SVM）,在現(xiàn)實(shí)世界中

11、，很多分類問題都是線性不可分的，即在原來的樣本空間中無法找到一個(gè)最優(yōu)的線性分類函數(shù)，這就使得支持向量機(jī)的應(yīng)用具有很大的局限性。但是可以設(shè)法通過非線性變換將原樣本空間的非線性問題轉(zhuǎn)化為另一個(gè)空間中的線性問題。SVM就是基于這一思想的。首先將輸入向量通過非線性映射變換到一個(gè)高維的特征向量空間，在該特征空間中構(gòu)造最優(yōu)分類超平面。,由于在上面的二次規(guī)劃（QP）問題中，無論是目標(biāo)函數(shù)還是分類函數(shù)都只涉及內(nèi)積運(yùn)算，如果采用核函數(shù)(Kernel Fu

12、nction)就可以避免在高維空間進(jìn)行復(fù)雜運(yùn)算，而通過原空間的函數(shù)來實(shí)現(xiàn)內(nèi)積運(yùn)算。因此，選擇合適的內(nèi)積核函數(shù) 就可以實(shí)現(xiàn)某一非線性變換后的線性分類，而計(jì)算復(fù)雜度卻沒有增加多少 ，從而巧妙地解決了高維空間中計(jì)算帶來的“維數(shù)災(zāi)難”問題。,此時(shí)，相應(yīng)的決策函數(shù)化為：支持向量機(jī)求得的決策函數(shù)形式上類似于一個(gè)神經(jīng)網(wǎng)絡(luò)，其輸出是若干中間層節(jié)點(diǎn)的線性組合，而

13、每一個(gè)中間層節(jié)點(diǎn)對應(yīng)于輸入樣本與一個(gè)支持向量的內(nèi)積，因此也被稱作是支持向量網(wǎng)絡(luò)。,,支持向量機(jī)示意圖,選擇不同的核函數(shù) 可以生成不同的支持向量機(jī)，常有以下幾種：（1）線性核函數(shù)： （2）多項(xiàng)式核函數(shù)：（3）Gauss核函數(shù)：（4）Sigmoid核函數(shù)：,一個(gè)具體核函數(shù)的例子,假設(shè)數(shù)據(jù)是位于 中的向量，選擇： 然后尋找滿足下述條件的空間H：使映射 從 映射到H且滿足： 可以選

14、擇H=R3以及：,,,,用圖來表示該變換：,SVM用于二維樣本分類,,支持向量機(jī)與多層前向網(wǎng)絡(luò)的比較,與徑向基函數(shù)網(wǎng)絡(luò)和多層感知器相比，支持向量機(jī)避免了在前者的設(shè)計(jì)中經(jīng)常使用的啟發(fā)式結(jié)構(gòu)，它不依賴于設(shè)計(jì)者的經(jīng)驗(yàn)知識；而且支持向量機(jī)的理論基礎(chǔ)決定了它最終求得的是全局最優(yōu)值而不是局部極小值，也保證了它對于未知樣本的良好泛化能力而不會出現(xiàn)過學(xué)習(xí)現(xiàn)象。,支持向量機(jī)的分類學(xué)習(xí)算法,對于分類問題，用支持向量機(jī)方法進(jìn)行求解的學(xué)習(xí)算法過程為：第一步

15、 給定一組輸入樣本 ， 及其對應(yīng)的期望輸出 ； 第二步 選擇合適的核函數(shù) 及相關(guān)參數(shù)；第三步 在約束條件 和 下求解 得到最優(yōu)權(quán)值 ；,,,,,,,,第四步 計(jì)算： ；第五步 對于待分類向量x ，計(jì)算： 為＋1或－1，決定x屬于哪一類。,,用于函數(shù)擬合的支持向量機(jī),假定數(shù)據(jù)集

16、 。首先考慮用線性回歸函數(shù) 擬合數(shù)據(jù)集X的問題。所有訓(xùn)練數(shù)據(jù)在精度 下無誤差地用線性函數(shù)擬合，即：考慮到允許擬合誤差存在的情況：,,,,,優(yōu)化目標(biāo)函數(shù)為：對偶問題為：在約束條件 下求下式的最大值?；貧w函數(shù)為：,,,,,用不同的支持向量機(jī)對人工數(shù)據(jù)進(jìn)行分類,（a ）線性可分對下面二維待分類人工數(shù)據(jù)P進(jìn)行分類：X = [2 7; 3 6; 2 2; 8 1

17、; 6 4; 4 8; 9 5; 9 9; 9 4; 6 9; 7 4];Y = [ +1; +1; +1; +1; +1; -1; -1; -1; -1; -1; -1];,（b ）線性不可分對下面二維待分類人工數(shù)據(jù)P進(jìn)行分類：X = [2 7; 3 6; 2 2; 8 1; 6 4; 4 8; 9 5; 9 9; 9 4; 6 9; 7 4;4 4];Y = [ +1; +1; +1; +1; +

18、1; -1; -1; -1; -1; -1; -1; -1];,（1）、實(shí)驗(yàn)環(huán)境 Matlab 7.0（2）、界面設(shè)計(jì),（3）、具體實(shí)現(xiàn)a) 對于線性可分的人工樣本數(shù)據(jù)P。其中共有11個(gè)待分類樣本。使用最簡單的支持向量機(jī)，即以線性核函數(shù)K(x,xi)=(x. xi)作為內(nèi)積函數(shù)的支持向量機(jī)來訓(xùn)練該數(shù)據(jù)集合。懲罰因子C取10。,,黑色線為數(shù)據(jù)集合的兩類分類線，可以看出它能將兩類準(zhǔn)確無誤的分開，錯誤率為0。

19、藍(lán)線和綠線為兩類樣本的最大間隔邊界。5,11,6三點(diǎn)為支持向量。,樣本點(diǎn),分類結(jié)果,對于線性不可分的人工樣本數(shù)據(jù)P。其中共有12個(gè)待分類樣本。1）用線性核函數(shù)SVM進(jìn)行訓(xùn)練。仍采用最簡單的支持向量機(jī)，即以線性核函數(shù)K(x,xi)=(x. xi)作為內(nèi)積函數(shù)的支持向量機(jī)來訓(xùn)練該數(shù)據(jù)集合。懲罰因子C取10。,,顯然黑色線為數(shù)據(jù)集合的兩類分類線，不能將兩類準(zhǔn)確無誤的分開，點(diǎn)12是錯分的樣本點(diǎn)，而5和點(diǎn)11落在了分類間隔內(nèi)。此時(shí)正確率為91.

20、67%。,樣本點(diǎn),分類結(jié)果,2）利用較為復(fù)雜的RBF核函數(shù)支持向量機(jī)進(jìn)行分類。RBF核函數(shù)中的核寬度這個(gè)參數(shù)是由用戶決定的。因此下面采用三個(gè)不同的RBF核寬度來對該函數(shù)集合進(jìn)行分類。懲罰因子C取100。①選擇RBF核寬度為8,其結(jié)果如圖所示。,,從圖中可以看出，此時(shí)SVM以點(diǎn)12作為類別－1的一個(gè)聚類中心，在其周圍形成了一個(gè)類似“小島”的區(qū)域。并且，點(diǎn)2，3，4，5，6,11和12是支持向量，錯分樣本數(shù)為0。,②使用一個(gè)較小的值

21、1作為RBF核寬度,其結(jié)果如圖所示。,,黑線為分類邊界，藍(lán)線和綠線為兩類的最大間隔邊界。由于較小的核寬度允許了分類邊界的分割，因此圖中的分類邊界有很多條。由此造成了每個(gè)樣本點(diǎn)都是支持向量，所以錯分樣本數(shù)為0。,③使用一個(gè)較大的值36作為RBF核寬度,其結(jié)果如圖所示。,,黑線為分類邊界，藍(lán)線和綠線為兩類的最大間隔邊界。使用較大的核寬度時(shí)分類邊界比較簡化，但是出現(xiàn)了錯分樣本，即點(diǎn)5和12，此時(shí)的分類正確率為83.33%。,實(shí)驗(yàn)小結(jié):

22、 從實(shí)驗(yàn)可以看出，針對同一問題，也即同一組數(shù)據(jù)來說，用不同核函數(shù)的支持向量機(jī)的分類結(jié)果是不同的。而且可以看到針對不同的問題，對同一種核函數(shù)支持向量機(jī)來說，選擇合適的參數(shù)也是很關(guān)鍵的，不同的參數(shù)的選擇就對應(yīng)著不同的分類結(jié)果。,支持向量機(jī)算法的研究與應(yīng)用,支持向量機(jī)算法改進(jìn) 核函數(shù)的改進(jìn) 錯誤懲罰參數(shù)的選擇 不敏感參數(shù)的選擇 支持向量機(jī)解決多類劃分問題 支持向量機(jī)的應(yīng)用,支持向量機(jī)算法改進(jìn),傳統(tǒng)的利用標(biāo)準(zhǔn)二次型優(yōu)化技術(shù)解決對偶問題

23、的方法是訓(xùn)練算法慢的主要原因。 (1) SVM方法需要計(jì)算和存儲核函數(shù)矩陣，當(dāng)樣本點(diǎn)數(shù)目較大時(shí)，需要很大的內(nèi)存，例如，當(dāng)樣本點(diǎn)數(shù)目超過4000時(shí)，存儲核函數(shù)矩陣需要多達(dá)128MB內(nèi)存； (2) SVM在二次型尋優(yōu)過程中要進(jìn)行大量的矩陣運(yùn)算，多數(shù)情況下，尋優(yōu)算法是占用算法時(shí)間的主要部分。,近年來人們針對方法本身的特點(diǎn)提出了許多算法來解決對偶尋優(yōu)問題。這些算法的一個(gè)共同的思想就是采用分而治之的原則將原始QP問題分解為規(guī)模較小的子問題

24、，通過循環(huán)解決一系列子問題來求得原問題的解。現(xiàn)有的訓(xùn)練算法分為三類： “塊算法”（chunking algorithm） “Osuna 分解算法” “SMO算法”,核函數(shù)的改進(jìn),核函數(shù)的形式及其參數(shù)決定了分類器的類型和復(fù)雜程度。在不同的問題領(lǐng)域，核函數(shù)應(yīng)當(dāng)具有不同的形式和參數(shù)，應(yīng)將領(lǐng)域知識引入進(jìn)來，從數(shù)據(jù)依賴的角度選擇核函數(shù)。初步嘗試的方法有： Amari－－利用黎曼幾何結(jié)構(gòu)方法來修改核函數(shù) ；

25、 Barzilay－－通過改進(jìn)鄰近核來改進(jìn)核函數(shù)； Brailovsky－－局部核函數(shù)方法； G. F. Smits －－多個(gè)核函數(shù)組合起來使用；,錯誤懲罰參數(shù)的選擇,錯分樣本懲罰參數(shù)C實(shí)現(xiàn)在錯分樣本的比例和算法復(fù)雜度之間的折衷。C值的確定一般是用戶根據(jù)經(jīng)驗(yàn)給定的，隨意性很大，也很難知道所取C值的好壞性。如何消除C值選取的隨意性，而采用某種方法自動地選擇一個(gè)最佳的C值，這個(gè)問題目前尚未解決。,不敏感參數(shù) 的選擇,SVM通過參

26、數(shù) 控制回歸估計(jì)的精度，但 取多少才能達(dá)到所期望的估計(jì)精度是不明確的，為此出現(xiàn)了許多新的SVM方法。 Schölkoph和Smola－－ -SVM方法 Lin C-F －－加權(quán)支持向量機(jī)，通過對每個(gè)樣本數(shù)據(jù)點(diǎn)采用不同的 ，來獲得更準(zhǔn)確的回歸估計(jì)。,,支持向量機(jī)解決多類劃分問題,“多類支持向量機(jī)”（Multi-category Support Vector Machines，M-SVMs）。它們可以大致分為兩大類

27、：（1）通過某種方式構(gòu)造一系列的兩類分類器并將它們組合在一起來實(shí)現(xiàn)多類分類；（2）直接在目標(biāo)函數(shù)上進(jìn)行改進(jìn)，建立K分類支持向量機(jī)。,一對多方法( l - against - rest ，1-a-r),此算法是對于K類問題構(gòu)造K個(gè)兩類分類器。第i個(gè)SVM用第i類中的訓(xùn)練樣本作為正的訓(xùn)練樣本，而將其它的樣本作為負(fù)的訓(xùn)練樣本，即每個(gè)SVM分別將某一類的數(shù)據(jù)從其他類別中分離出來。測試時(shí)將未知樣本劃分到具有最大分類函數(shù)值的那類。缺點(diǎn)：泛化

28、能力較差，且訓(xùn)練樣本數(shù)目大，訓(xùn)練困難。此外，該方法還有可能存在測試樣本同時(shí)屬于多類或不屬于任何一類的情況。,一對一方法( l - against - 1，1-a-1),該算法在K類訓(xùn)練樣本中構(gòu)造所有可能的兩類分類器，每類僅僅在K類中的兩類訓(xùn)練樣本之間訓(xùn)練，結(jié)果共構(gòu)造K(K-1)/2個(gè)分類器。組合這些兩類分類器很自然地用到了投票法，得票最多（ Max Wins ）的類為新點(diǎn)所屬的類。 缺點(diǎn)：推廣誤差無界，分類器的數(shù)目K(K-1)/2隨

29、類數(shù)K的增加急劇增加，導(dǎo)致在決策時(shí)速度很慢。此外，還可能存在一個(gè)樣本同時(shí)屬于多個(gè)類的情況。,決策導(dǎo)向非循環(huán)圖SVM方法 （Decision Directed Acyclic Graph，DDAG）,在訓(xùn)練階段，其與1-a-1方法相同，對于K類問題，DDAG含有K(K-1)/2個(gè)兩類分類器。然而在決策階段，使用從根節(jié)點(diǎn)開始的導(dǎo)向非循環(huán)圖（DAG），具有K(K-1)/2個(gè)內(nèi)部節(jié)點(diǎn)以及K個(gè)葉子節(jié)點(diǎn)，每個(gè)內(nèi)部節(jié)點(diǎn)都是一個(gè)兩類分類器，葉子

30、節(jié)點(diǎn)為最終的類值。缺點(diǎn)：根節(jié)點(diǎn)的選擇直接影響著分類的結(jié)果，不同的分類器作為根節(jié)點(diǎn)，其分類結(jié)果可能會不同，從而產(chǎn)生分類結(jié)果的不確定性。,基于二叉樹的多類SVM分類方法,對于K類的訓(xùn)練樣本，訓(xùn)練K-1個(gè)支持向量機(jī)。第1個(gè)支持向量機(jī)以第1類樣本為正的訓(xùn)練樣本，將第2，3，…，K類訓(xùn)練樣本作為負(fù)的訓(xùn)練樣本訓(xùn)練SVM1，第i個(gè)支持向量機(jī)以第i類樣本為正的訓(xùn)練樣本，將第i + l，i + 2，…，K類訓(xùn)練樣本作為負(fù)的訓(xùn)練樣本訓(xùn)練SVMi，直到第K

31、-1個(gè)支持向量機(jī)將以第K-1類樣本作為正樣本，以第K類樣本為負(fù)樣本訓(xùn)練SVM（K-1）。,優(yōu)點(diǎn)：所需要訓(xùn)練的兩類支持向量機(jī)的數(shù)量少 ；消除了決策時(shí)存在同時(shí)屬于多類或不屬于任何一類的情況 ；總共需要訓(xùn)練的樣本和前兩種方法相比減少了許多。 缺點(diǎn)：若在某個(gè)節(jié)點(diǎn)上發(fā)生分類錯誤，將會把錯誤延續(xù)下去，該節(jié)點(diǎn)后續(xù)下一級節(jié)點(diǎn)上的分類就失去意義。,最小最大模塊化支持向量機(jī) （Min-Max-Modular -SVM, M3-SVM ）,該方法充分利用

32、分布式并行計(jì)算系統(tǒng)，將一個(gè)K類問題分解成K(K-1)/2個(gè)二類問題，然后把一個(gè)二類問題分解成一系列指定規(guī)模的小的二類子問題。優(yōu)點(diǎn)：這些二類子問題的特點(diǎn)是在訓(xùn)練過程中完全相互獨(dú)立，因此可以容易地在集群計(jì)算機(jī)和網(wǎng)格上實(shí)現(xiàn)超并行學(xué)習(xí)。在保證推廣能力的前提下，能夠明顯提高訓(xùn)練速度，是一種解決大規(guī)模模式分類問題的有效方法。,支持向量機(jī)的應(yīng)用,隨著對SVM研究的進(jìn)展和深入，其應(yīng)用也越來越廣泛，基于SVM思想的一些模型和方法被廣泛應(yīng)用于各個(gè)領(lǐng)域，包

33、括模式識別，如人臉識別、字符識別、筆跡鑒別、文本分類、語音鑒別、圖像識別、圖像分類、圖像檢索等等；回歸估計(jì)，如非線性系統(tǒng)估計(jì)、預(yù)測預(yù)報(bào)、建模與控制等等；以及網(wǎng)絡(luò)入侵檢測、郵件分類、數(shù)據(jù)挖掘和知識發(fā)現(xiàn)、信號處理、金融預(yù)測、生物信息等新領(lǐng)域。,Libsvm的使用,安裝python,下載解壓libsvm,gnuplotSvmtoy.exe 圖像顯示,可修改參數(shù)Svmtrain.exe tdata 生成一個(gè)modelPython.grid