基于聚類(lèi)的智能圖像分析算法畢業(yè)設(shè)計(jì)論文致謝本研究及學(xué)位論文是在我的導(dǎo)師別紅霞老師的親切關(guān)懷和悉心指導(dǎo)下完成的。在將近四個(gè)月的研究中，她嚴(yán)肅的科學(xué)態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神，精益求精的工作作風(fēng)，深深地感染和激勵(lì)著我。別老師不僅在學(xué)業(yè)上給我以精心指導(dǎo)，同時(shí)還在思想、生活上給我以無(wú)微不至的關(guān)懷，在此謹(jǐn)向別老師致以誠(chéng)摯的謝意和崇高的敬意。我還要感謝在一起愉快的度過(guò)畢業(yè)論文小組的同學(xué)們，尤其是盛晶晶、梁慧和邱文杰同學(xué)，正是由于你們的幫助和支持，我才能克服一個(gè)一個(gè)的困難和疑惑，直至本文的順利完成。在論文即將完成之際，我的心情無(wú)法平靜，從開(kāi)始進(jìn)入課題到論文的順利完成，有多少可敬的師長(zhǎng)、同學(xué)、朋友給了我無(wú)言的幫助，在這里請(qǐng)接受我誠(chéng)摯的謝意!最后我還要感謝培養(yǎng)我長(zhǎng)大含辛茹苦的父母，謝謝你們!最后，再次對(duì)關(guān)心、幫助我的老師和同學(xué)表示衷心地感謝！外文譯文支持向量網(wǎng)絡(luò)CorinnaCortesandVladimirVapnikAT&TLabs-Research摘要支持向量網(wǎng)絡(luò)是一種針對(duì)兩類(lèi)問(wèn)題的新學(xué)習(xí)機(jī)器.它的實(shí)現(xiàn)基于以下思想:將輸入向量非線(xiàn)性地映射到一個(gè)很高維的特征空間.并在該特征空間中構(gòu)造一個(gè)線(xiàn)性決策平面.該決策平面的特殊性質(zhì)保證了學(xué)習(xí)機(jī)器具有很好的推廣能力.支持向量網(wǎng)絡(luò)的思想已在完全可分的訓(xùn)練數(shù)據(jù)集上得以實(shí)現(xiàn),這里我們將它擴(kuò)展到不完全可分的訓(xùn)練數(shù)據(jù)集.利用多項(xiàng)式輸入變換的支持向量網(wǎng)絡(luò)被證明具有很好的推廣能力.我們以光學(xué)字體識(shí)別為實(shí)驗(yàn)將支持向量網(wǎng)絡(luò)和其他不同的經(jīng)典學(xué)習(xí)算法進(jìn)行了性能比較.關(guān)鍵詞：模式識(shí)別,有效的學(xué)習(xí)算法,神經(jīng)網(wǎng)路,徑向基函數(shù)分類(lèi)器,多項(xiàng)式分類(lèi)器1介紹60多年前,R.A.Fisher[7]提出了模式識(shí)別領(lǐng)域的第一個(gè)算法.該模型考慮n維向量x正態(tài)分布N(m1,∑1)和N(m2,∑2),m1和m2為各個(gè)分布的均值向量,∑1和∑2為各個(gè)分布的協(xié)方差矩陣,并給出最優(yōu)解為如下二次決策函數(shù):. (1)當(dāng)∑1=∑2=∑時(shí)該二次決策函數(shù)(1)退化為一個(gè)線(xiàn)性函數(shù):.(2)評(píng)估二次決策函數(shù)需要確定n(n+3)/2個(gè)自由參數(shù),而評(píng)估線(xiàn)性函數(shù)只需要n個(gè)自由參數(shù).在觀測(cè)數(shù)目較小(小于10n2)的情況下評(píng)估O(n2)個(gè)參數(shù)是不可靠的.Fisher因此提出以下建議,在∑1≠∑2時(shí)也采用線(xiàn)性判別函數(shù)(2),其中的∑采用如下形式:,(3)這里是某個(gè)常數(shù).Fisher也對(duì)兩個(gè)非正態(tài)分布的線(xiàn)性決策函數(shù)給出了建議.因此模式識(shí)別的算法最開(kāi)始是和構(gòu)建線(xiàn)性決策平面相關(guān)聯(lián)的.1962年,Rosenblatt[11]提出了一種不同的學(xué)習(xí)機(jī)器:感知器(或神經(jīng)網(wǎng)絡(luò)).感知器由相關(guān)聯(lián)的神經(jīng)元構(gòu)成,每個(gè)神經(jīng)元實(shí)現(xiàn)一個(gè)分類(lèi)超平面,因此整個(gè)感知器完成了一個(gè)分段線(xiàn)性分類(lèi)平面.如圖1.Fig1:Asimplefeed-forwardperceptronwith8inputunits,2layersofhiddenunits,and1outputunit.Thegray-shadingoftheVectorentriesreflectstheirnumericvalue.Rosenblatt沒(méi)有提出通過(guò)調(diào)整網(wǎng)絡(luò)的所有權(quán)值來(lái)最小化向量集上誤差的算法,而提出了一種自適應(yīng)僅僅改變輸出節(jié)點(diǎn)上的權(quán)值的方法.由于其他權(quán)值都是固定的,輸入向量被非線(xiàn)性地映射到最后一層節(jié)點(diǎn)的特征空間Z.在該空間的線(xiàn)性決策函數(shù)如下:(4)通過(guò)調(diào)整第i個(gè)節(jié)點(diǎn)到輸出節(jié)點(diǎn)的權(quán)值來(lái)最小化定義在訓(xùn)練集上的某種誤差.Rosenblatt的方法,再次將構(gòu)建決策規(guī)則歸結(jié)為構(gòu)造某個(gè)空間的線(xiàn)性超平面.1986年,針對(duì)模式識(shí)別問(wèn)題出現(xiàn)了通過(guò)調(diào)整神經(jīng)網(wǎng)絡(luò)所有權(quán)值來(lái)局部最小化向量集上誤差的算法[12,13,10,8],即后向傳播算法.算法對(duì)神經(jīng)網(wǎng)絡(luò)的數(shù)學(xué)模型有微小的改動(dòng).至此,神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了分段線(xiàn)性決策函數(shù).本文提出了一種全新的學(xué)習(xí)機(jī)器,支持向量網(wǎng)絡(luò).它基于以下思想:通過(guò)事先選擇的非線(xiàn)性映射將輸入向量映射到一個(gè)高維特征空間Z.在空間Z里構(gòu)建一個(gè)線(xiàn)性決策面,該決策面的一些性質(zhì)保證支持向量網(wǎng)絡(luò)具有好的推廣能力.例如:要構(gòu)造一個(gè)與二階多項(xiàng)式對(duì)應(yīng)的決策面,我們可以構(gòu)造一個(gè)特征空間Z,它有如下的N=n(n+3)/2個(gè)坐標(biāo):,ncoordinates,,ncoordinates,,n(n-1)/2coordinates,其中,x=.分類(lèi)超平面便是在該空間中構(gòu)造的.以上方法存在兩個(gè)問(wèn)題:一個(gè)是概念上的,另一個(gè)是技術(shù)上的.(1)概念上的問(wèn)題:怎樣找到一個(gè)推廣性很好的分類(lèi)超平面?特征空間的維數(shù)將會(huì)很高,能將數(shù)據(jù)分開(kāi)的超平面不一定都具有很好的推廣性.(2)技術(shù)上的問(wèn)題:怎樣在計(jì)算上處理如此高維的空間?要在一個(gè)200維的空間中構(gòu)建一個(gè)4或5階的多項(xiàng)式,需要構(gòu)造一個(gè)上十億的特征空間.概念上的問(wèn)題在1965年[14]通過(guò)完全可分情況下的最優(yōu)超平面得以解決.最優(yōu)超平面是指使兩類(lèi)向量具有最大間隔的線(xiàn)性決策函數(shù),如圖2所示.可以發(fā)現(xiàn),構(gòu)造最優(yōu)超平面只需考慮訓(xùn)練集中決定分類(lèi)隔間的少量數(shù)據(jù),即所謂的支持向量.如果訓(xùn)練集被最優(yōu)超平面完全無(wú)錯(cuò)地分開(kāi),則一個(gè)測(cè)試樣例被錯(cuò)判的期望概率以支持向量的期望數(shù)目與訓(xùn)練集向量數(shù)目比值為上界,即:.(5)注意,這個(gè)界與分類(lèi)空間的維數(shù)無(wú)關(guān).并且由此可知,如果支持向量的個(gè)數(shù)相對(duì)與整個(gè)訓(xùn)練集很小,則構(gòu)建出來(lái)的分類(lèi)超平面將具有很好的推廣性,即便是在一個(gè)無(wú)限維空間.第5節(jié)中,通過(guò)實(shí)際問(wèn)題我們驗(yàn)證了比值(5)能夠小到0.03而相應(yīng)的最優(yōu)超平面在一個(gè)十億的特征空間依然具有很好的推廣能力.Fig2.Anexampleofaseparableproblemina2dimensionalspace.Thesupportvectors,markedwithgreysquares,definethemarginoflargestseparationbetweenthetwoclasses.令為特征空間里的最優(yōu)超平面.我們將看到,特征空間中最優(yōu)超平面的權(quán)值可以寫(xiě)成支持向量的某個(gè)線(xiàn)性組合.(6)從而特征空間里的線(xiàn)性決策函數(shù)I(z)為如下形式:,(7)其中表示支持向量和向量在特征空間里的內(nèi)積.因此,該決策函數(shù)可以通過(guò)一個(gè)兩層的網(wǎng)絡(luò)來(lái)描述.如圖3.盡管最優(yōu)超平面保證了好的推廣性,但如何處理高維特征空間這個(gè)技術(shù)上的問(wèn)題依然存在.1992年,在文獻(xiàn)[3]中證明構(gòu)造決策函數(shù)的步驟可以交換順序:不必先將輸入向量通過(guò)某種非線(xiàn)性變換映射到特征空間再與特征空間中的支持向量做內(nèi)積；而可以先在輸入空間通過(guò)內(nèi)積或者某種別的距離進(jìn)行比較,再對(duì)比較的值進(jìn)行非線(xiàn)性變化.如圖4.這就允許我們構(gòu)造足夠好的分類(lèi)決策面,比如任意精度的多項(xiàng)式?jīng)Q策面.稱(chēng)這種類(lèi)型的學(xué)習(xí)機(jī)器為支持向量網(wǎng)絡(luò).支持向量網(wǎng)絡(luò)的技術(shù)首先針對(duì)能夠完全無(wú)錯(cuò)地分開(kāi)的數(shù)據(jù)集.本文我們將支持向量網(wǎng)絡(luò)推廣到不能完全無(wú)錯(cuò)分類(lèi)的數(shù)據(jù)集.通過(guò)該擴(kuò)展,作為一種全新的學(xué)習(xí)機(jī)器的支持向量網(wǎng)絡(luò)將和神經(jīng)網(wǎng)絡(luò)一樣的強(qiáng)大和通用.第5節(jié)將展示它在256維的高維空間中針對(duì)高達(dá)7階的多項(xiàng)式?jīng)Q策面的推廣性.并將它和其他經(jīng)典的算法比如線(xiàn)性分類(lèi)器、k近鄰分類(lèi)器和神經(jīng)網(wǎng)絡(luò)做了性能上的比較.第2、3、4節(jié)著重引出算法并討論了算法的一些性質(zhì).算法的一些重要細(xì)節(jié)參見(jiàn)附錄.Fig3.Classificationbyasupport-vectornetworkofanunknownpatternisconceptuallydonebyfirsttransformingthepatternintosomehigh-dimensionalfeaturespace.Anoptimalhyperplaneconstructedinthisfeaturespacedeterminestheoutput.Thesimilaritytoatwo-layerperceptroncanbeseenbycomparisontoFig1.Fig4.Classificationofanunknownpatternbyasupport-vectornetwork.Thepatternisininputspacecomparedtosupportvectors.Theresultingvaluesarenon-linearlytransformed.Alinearfunctionofthesetransformedvaluesdeterminestheoutputoftheclassifier.2最優(yōu)超平面本節(jié)回顧文獻(xiàn)[14]中針對(duì)能被完全無(wú)錯(cuò)分開(kāi)的訓(xùn)練數(shù)據(jù)的最優(yōu)超平面方法.下一節(jié)介紹軟間隔的概念,用來(lái)處理訓(xùn)練集不完全可分情況下的學(xué)習(xí)問(wèn)題.2.1最優(yōu)超平面算法訓(xùn)練樣本集,(8)是線(xiàn)性可分的。如果存在向量w和標(biāo)量b使得以下不等式(9)對(duì)(8)中所有元素都成立.我們將不等式(9)寫(xiě)成如下形式:(10)最優(yōu)超平面(11)是指將訓(xùn)練數(shù)據(jù)以最大間隔分開(kāi)的那個(gè)平面:它決定了向量w/|w|的方向,該方向上兩不同類(lèi)別訓(xùn)練向量間的距離最大.可回顧圖2.記這個(gè)距離為,它由下式給定:.(12)最優(yōu)超平面(w0,b0)便是使得距離(12)取最大值的那組參數(shù).根據(jù)(12)和(10)可得.(13)這表明,最優(yōu)超平面就是滿(mǎn)足條件(10)并且使得最小化的超平面.因此,構(gòu)建一個(gè)最有超平面其實(shí)就是一個(gè)二次規(guī)劃問(wèn)題.滿(mǎn)足的向量即為支持向量.附錄中將證明決定最優(yōu)超平面的向量可以寫(xiě)成所有訓(xùn)練向量的一個(gè)線(xiàn)性組合:,(14)其中≥0.由于只有支持向量處的系數(shù)>0(參考附錄),表達(dá)式(14)只是的一種簡(jiǎn)寫(xiě)形式.要求出參數(shù)向量:,需要求解以下二次規(guī)劃問(wèn)題:(15)其中=(),且滿(mǎn)足限制:≥0,(16)Y=0,(17)=(1,...,1)是維的單位向量,是維的類(lèi)標(biāo)簽向量,是×的對(duì)稱(chēng)矩陣其元素.(18)不等式(16)表示非負(fù)象限.因此,問(wèn)題變?yōu)樵诜秦?fù)象限中最大化二次式(15),并服從約束條件(17).當(dāng)訓(xùn)練數(shù)據(jù)可完全無(wú)錯(cuò)地分開(kāi)時(shí),在附錄A中我們證明了在最大泛函(15)、和式(13)的最大間隔之間有以下關(guān)系:.(19)如果存在某個(gè)和某個(gè)較大的常數(shù)使得不等式(20)成立,則所有把訓(xùn)練集(8)分開(kāi)的超平面其間隔都滿(mǎn)足.如果訓(xùn)練集(8)不能被超平面完全分開(kāi),則兩個(gè)類(lèi)的樣本間的間隔變的任意小,使得泛函的值變得任意大.因此,要在約束條件(16)和(17)下最大化泛函(15),要么能求得最大值(這種情況需要構(gòu)造最大間隔為的最優(yōu)超平面),要么求出超過(guò)某個(gè)給定的常數(shù)的最大值(這種情況下不可能以大于的間隔分開(kāi)訓(xùn)練數(shù)據(jù)).在約束條件(16)和(17)下最大化泛函(15)的問(wèn)題如下方法可有效地解決.將訓(xùn)練數(shù)據(jù)集劃分為幾部分,使每部分占有合理的少量數(shù)據(jù).先求解由第一部分訓(xùn)練數(shù)據(jù)決定的二次規(guī)劃問(wèn)題.對(duì)于該問(wèn)題,會(huì)有兩個(gè)結(jié)果:其一,這部分?jǐn)?shù)據(jù)不能被任何超平面分開(kāi)(這種情況下整個(gè)數(shù)據(jù)集都不能被任何超平面分開(kāi));其二,找到了能分開(kāi)這部分?jǐn)?shù)據(jù)的最優(yōu)超平面.假設(shè)對(duì)第一部分?jǐn)?shù)據(jù)泛函(15)的最大化時(shí)對(duì)應(yīng)的向量為.該向量某些維上取值為零,它們是和該部分?jǐn)?shù)據(jù)中非支持向量相關(guān)的.將第一部分?jǐn)?shù)據(jù)中的支持向量和第二部分中不滿(mǎn)足約束條件(10)的向量組成一個(gè)新的訓(xùn)練集,其中w將由決定.對(duì)于這個(gè)新的訓(xùn)練集,構(gòu)建泛函并假設(shè)其在最大化.持續(xù)遞增地構(gòu)造出覆蓋全部訓(xùn)練數(shù)據(jù)的解向量,此時(shí),或者會(huì)發(fā)現(xiàn)無(wú)法找到將整個(gè)訓(xùn)練集無(wú)錯(cuò)分開(kāi)的超平面,或者構(gòu)建出了整個(gè)訓(xùn)練集的最優(yōu)超平面,且=.值得注意的是,在這個(gè)過(guò)程中泛函的值是單調(diào)遞增的,因?yàn)樵絹?lái)越多的訓(xùn)練向量被考慮到優(yōu)化過(guò)程中來(lái),使得兩類(lèi)樣本之間的間隔越來(lái)越小.3軟間隔超平面考慮訓(xùn)練數(shù)據(jù)不能完全無(wú)錯(cuò)地分開(kāi)的情況,此時(shí),我們希望能以最小的錯(cuò)誤將訓(xùn)練集分開(kāi).為形式化進(jìn)行表示,引入非負(fù)變量.現(xiàn)在,最小化泛函(21)參數(shù)>0,約束條件為,(22).(23)對(duì)于足夠小的>0,泛函(21)描述了訓(xùn)練錯(cuò)誤數(shù).最小化泛函(21)可獲得被錯(cuò)分樣本的某個(gè)最小子集:.如果不考慮這些樣本,其他的樣本組成的訓(xùn)練集可以被無(wú)錯(cuò)地分開(kāi).可以構(gòu)造一個(gè)將其他樣本組成的訓(xùn)練集完全分開(kāi)的最優(yōu)超平面.該思想形式化表述如下:最小化泛函(24)約束條件為(22)和(23),其中F(u)是一個(gè)單調(diào)凸函數(shù),C是常數(shù).對(duì)于足夠大的C和足夠小的,在約束條件(22)和(23)下最大化泛函(24)的向量w0和常數(shù)b0決定了最優(yōu)超平面,而該超平面使得訓(xùn)練集上錯(cuò)誤數(shù)最小并將未分錯(cuò)部分以最大間隔分開(kāi).然而,在訓(xùn)練集上構(gòu)建一個(gè)超平面使得錯(cuò)誤數(shù)最小一般說(shuō)來(lái)是NP完全的.為避免出現(xiàn)NP完全性,我們考慮=1的情況(使得最優(yōu)問(wèn)題(15)具有唯一解的最小).此時(shí),泛函(24)描述了如何構(gòu)建一個(gè)分類(lèi)超平面使得訓(xùn)練錯(cuò)誤的偏差之和最小且被正確分類(lèi)的樣本的間隔最大的問(wèn)題(對(duì)于足夠大的C).如果整個(gè)訓(xùn)練集都能被正確地分開(kāi),則此時(shí)構(gòu)建出來(lái)的超平面就是最優(yōu)間隔超平面.相比于<1的情況,=1的情況存在有效的方法尋找(24)的解.稱(chēng)這個(gè)解為軟間隔超平面.在附錄A我們考慮在約束條件(22)和(23)下最小化泛函(25)其中F(u)是個(gè)單調(diào)凸函數(shù)且滿(mǎn)足F(0)=0.為了表述的簡(jiǎn)潔,本節(jié)只考慮F(u)=u2的情況.此時(shí),最優(yōu)化問(wèn)題依然是個(gè)二次規(guī)劃問(wèn)題.附錄A中,我們證明了最優(yōu)超平面算法里的向量w可以寫(xiě)成支持向量的一個(gè)線(xiàn)性組合:.為求向量,需要求解以下雙重二次規(guī)劃問(wèn)題,最大化泛函(26)約束條件為,(27),(28),(29)其中、、和與構(gòu)建最優(yōu)超平面的最優(yōu)化問(wèn)題中的相同,是一個(gè)標(biāo)量,(29)描述了坐標(biāo)取值范圍.根據(jù)(29),可以發(fā)現(xiàn),泛函(26)中所允許的最小的應(yīng)該為.因此,為求解軟間隔分類(lèi)器我們求解出在約束條件≥0和(27)下使泛函(30)最大化的向量.這個(gè)問(wèn)題不同于在泛函(30)中增加這一項(xiàng)來(lái)構(gòu)造最優(yōu)間隔分類(lèi)器的問(wèn)題.由于多了這一項(xiàng),構(gòu)造軟件間隔分類(lèi)器的問(wèn)題對(duì)于任何數(shù)據(jù)集都是唯一的且有解的.因?yàn)檫@一項(xiàng)的存在,泛函(30)不再是二次的.在約束條件≥0和(27)下最大化泛函(30)屬于凸規(guī)劃問(wèn)題的范疇.因此,要構(gòu)建軟間隔分類(lèi)器,我們可以在維的參數(shù)空間解凸規(guī)劃問(wèn)題,也可以在+1維的(,)參數(shù)空間解二次規(guī)劃問(wèn)題.在我們的實(shí)驗(yàn)里,采用的是后者.4特征空間中內(nèi)積的回旋方法前文描述了在輸入空間構(gòu)建分類(lèi)超平面的算法.為建立特征空間里的超平面,首先要通過(guò)選擇一個(gè)N維向量函數(shù):將n維輸入向量x映射成N維特征向量.于是,一個(gè)N維的線(xiàn)性分類(lèi)器(w,b)的構(gòu)造將針對(duì)這些被轉(zhuǎn)換的向量:,.對(duì)一個(gè)未知向量x進(jìn)行分類(lèi),需要先將它轉(zhuǎn)換到分類(lèi)空間(),再考慮以下函數(shù)的符號(hào).(31)根據(jù)軟間隔分類(lèi)方法的性質(zhì),向量w可寫(xiě)成特征空間中支持向量的線(xiàn)性組合.即.(32)由于內(nèi)積的線(xiàn)性特點(diǎn),分類(lèi)函數(shù)(31)對(duì)于一個(gè)未知向量x的判別僅依賴(lài)于內(nèi)積運(yùn)算:.(33)構(gòu)造支持向量網(wǎng)絡(luò)的思想來(lái)自于對(duì)Hilbert空間[2]中內(nèi)積一般形式的考慮:.(34)根據(jù)Hilbert-Schmidt理論[6],任意的對(duì)稱(chēng)函數(shù)∈都能展開(kāi)成以下形式,(35)其中為特征值,為特征函數(shù),由核的如下積分式定義:.保證(34)描述了在某個(gè)特征空間中的一個(gè)內(nèi)積的一個(gè)充分條件是展開(kāi)式(35)中的所有特征值都為正數(shù).要保證所有的這些系數(shù)都為正,充分必要條件是,對(duì)使得成立的所有g(shù),條件成立(Merser’s定理).因此,滿(mǎn)足Merser’s定理的函數(shù)就可以用作內(nèi)積.Aizerman,Braverman和Rozonoer[1]提出了一種特征空間里內(nèi)積的回旋形式,(36)稱(chēng)之為勢(shì)函數(shù).事實(shí)上,特征空間中內(nèi)積的回旋可以用滿(mǎn)足Merser’s條件的任何函數(shù),特別地,要在n維輸入空間構(gòu)造d次多項(xiàng)式分類(lèi)器,我們可以利用以下函數(shù).(37)使用不同的內(nèi)積我們以任意類(lèi)型的決策平面來(lái)構(gòu)造不同的學(xué)習(xí)機(jī)器[3].這些學(xué)習(xí)機(jī)器的決策平面具有如下形式,其中是支持向量在輸入空間的像,是支持向量在特征空間的權(quán)值.求解支持向量和它們的權(quán)值可采用和原來(lái)的最優(yōu)間隔分類(lèi)器或者軟間隔分類(lèi)器類(lèi)似的方法.唯一的不同點(diǎn)是矩陣D(在(18)中定義)的元素變?yōu)?.5支持向量網(wǎng)絡(luò)的一般特征5.1支持向量網(wǎng)絡(luò)建立的決策規(guī)則是有效的要構(gòu)建支持向量網(wǎng)絡(luò)的決策規(guī)則,需要求解如下二次優(yōu)化問(wèn)題:,約束條件為:,,其中矩陣,.由訓(xùn)練數(shù)據(jù)集決定,是決定內(nèi)積回旋的函數(shù).這個(gè)最優(yōu)化問(wèn)題可通過(guò)訓(xùn)練數(shù)據(jù)決定的一個(gè)中間優(yōu)化問(wèn)題來(lái)求解,這個(gè)解是由支持向量組成的.相關(guān)技術(shù)在第3節(jié)已經(jīng)論述過(guò).求得的最優(yōu)決策函數(shù)是唯一的.每一個(gè)最優(yōu)化問(wèn)題都有其相應(yīng)的標(biāo)準(zhǔn)解法.5.2支持向量網(wǎng)絡(luò)是一種通用的學(xué)習(xí)機(jī)器通過(guò)選擇不同的核函數(shù)來(lái)內(nèi)積回旋,可以實(shí)現(xiàn)不同的支持向量網(wǎng)絡(luò).下一節(jié)我們將考慮多項(xiàng)式?jīng)Q策面的支持向量網(wǎng)絡(luò).為實(shí)現(xiàn)多項(xiàng)式的不同階數(shù),選用如下核函數(shù)用于內(nèi)積回旋.具有如下決策函數(shù)形式的徑向基函數(shù)的學(xué)習(xí)機(jī)器可通過(guò)以下核函數(shù)實(shí)現(xiàn).此時(shí),支持向量機(jī)將會(huì)構(gòu)建出近似函數(shù)的中心以及相應(yīng)的權(quán)值.也可以結(jié)合已有問(wèn)題的先驗(yàn)知識(shí)來(lái)構(gòu)建一個(gè)特殊的回旋函數(shù).因此,支持向量網(wǎng)絡(luò)是非常通用的一種學(xué)習(xí)機(jī)器,利用不同的核函數(shù)就能實(shí)現(xiàn)不同的決策函數(shù)集合.5.3支持向量網(wǎng)絡(luò)與推廣能力的控制控制一個(gè)學(xué)習(xí)機(jī)器的推廣能力需要控制兩個(gè)因素:訓(xùn)練集上的錯(cuò)誤率和學(xué)習(xí)機(jī)器的容量VC維[14].測(cè)試集上的誤差概率存在這樣一個(gè)界:不等式(38)以概率1-成立.界(38)中的置信區(qū)間決定于學(xué)習(xí)機(jī)器的VC維,訓(xùn)練集數(shù)據(jù)個(gè)數(shù)和的值.(38)中的兩個(gè)因素形成了一對(duì)矛盾:學(xué)習(xí)機(jī)器的VC維越小,置信區(qū)間越小,但是錯(cuò)誤的頻率越大.結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則用來(lái)解決這個(gè)問(wèn)題:對(duì)于給定的數(shù)據(jù)集,找到一個(gè)使置信區(qū)間與錯(cuò)誤頻率之和最小的解.結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的一個(gè)特例是奧科瑪-剃刀原則:保持第一項(xiàng)為零最小化第二項(xiàng).我們知道,對(duì)于閾值b固定的線(xiàn)性指示函數(shù)其VC維等于輸入空間的維數(shù).然而,對(duì)于函數(shù)集(權(quán)值有界)其VC維可小于輸入空間的維數(shù)且依賴(lài)于.可以看到,最優(yōu)間隔分類(lèi)器方法運(yùn)用了奧科瑪-剃刀原則.將(38)的第一項(xiàng)保持為零(通過(guò)滿(mǎn)足不等式(9)),再最小化第二項(xiàng)(通過(guò)最小化函數(shù)).這樣的最小化避免了過(guò)擬合問(wèn)題.然而,即使是在訓(xùn)練數(shù)據(jù)完全可分的情況下,也可以通過(guò)以訓(xùn)練集上的錯(cuò)誤為代價(jià)來(lái)最小化(38)中的置信區(qū)間那一項(xiàng)進(jìn)一步獲得更好的推廣性.在軟間隔分類(lèi)方法中,這可以通過(guò)選擇恰當(dāng)?shù)膮?shù)C來(lái)實(shí)現(xiàn).在支持向量網(wǎng)絡(luò)算法中,可以通過(guò)調(diào)節(jié)參數(shù)C來(lái)控制決策規(guī)則的復(fù)雜度和錯(cuò)誤頻率這一對(duì)矛盾,即使是對(duì)于訓(xùn)練集無(wú)法完全分開(kāi)這種一般情況.因此,支持向量網(wǎng)絡(luò)能夠控制影像學(xué)習(xí)機(jī)器推廣能力的兩個(gè)因素.6實(shí)驗(yàn)分析為驗(yàn)證支持向量網(wǎng)絡(luò)方法,我們進(jìn)行了兩組實(shí)驗(yàn).(1)構(gòu)建了平面上的人工數(shù)據(jù)集并用2階多項(xiàng)式?jīng)Q策面進(jìn)行了實(shí)驗(yàn);(2)針對(duì)數(shù)字識(shí)別這個(gè)實(shí)際問(wèn)題進(jìn)行了實(shí)驗(yàn).6.1平面上的實(shí)驗(yàn)利用核函數(shù)(39)其中d=2,構(gòu)建平面上不同樣本集的決策規(guī)則.實(shí)驗(yàn)結(jié)果證實(shí)了該算法的強(qiáng)大.圖5給出了一些例子.黑白兩種子彈代表兩類(lèi).在圖中,雙圓圈表示支持向量,十字表示錯(cuò)分的向量.可以發(fā)現(xiàn),支持向量的個(gè)數(shù)相對(duì)于訓(xùn)練樣本的個(gè)數(shù)是很少的.Fig5.Examplesofthedot-product(39)withd=2.Supportpatternsareindicatedwithdoublecircles,errorswithacross.Fig6.ExamplesofpatternswithlabelsfromtheUSPostalServicedigitdatabase.6.2數(shù)字識(shí)別實(shí)驗(yàn)針對(duì)位圖數(shù)字識(shí)別構(gòu)建支持向量網(wǎng)絡(luò)的實(shí)驗(yàn)用到了一大一小兩個(gè)數(shù)據(jù)庫(kù).小的是美國(guó)郵政服務(wù)器上的數(shù)據(jù)庫(kù),包含7300個(gè)訓(xùn)練樣本和2000個(gè)測(cè)試樣本.數(shù)據(jù)的分辨率是16×16像素,圖6給出了一些例子.在這個(gè)數(shù)據(jù)庫(kù)上,我們研究不同階數(shù)的多項(xiàng)式的實(shí)驗(yàn)結(jié)果.大的數(shù)據(jù)庫(kù)包含60,000訓(xùn)練樣本和10,000測(cè)試樣本,是NIST上訓(xùn)練集和測(cè)試集50-50的混合.28×28像素的分辨率導(dǎo)致輸入維數(shù)是784.在這個(gè)數(shù)據(jù)上我們只構(gòu)建了一個(gè)四階的多項(xiàng)式分類(lèi)器.該分類(lèi)器的性能和其他不同學(xué)習(xí)機(jī)器在基準(zhǔn)學(xué)習(xí)[4]上進(jìn)行了比較.實(shí)驗(yàn)中共構(gòu)建了十個(gè)分類(lèi)器,每個(gè)類(lèi)別一個(gè).每個(gè)超平面使用相同的內(nèi)積和數(shù)據(jù)預(yù)處理過(guò)程.對(duì)未知樣本的判別結(jié)果為十個(gè)分類(lèi)器中輸出結(jié)果最大的一個(gè).Table1.Performanceofvariousclassifierscollectedfrompublicationsandownexperiments.Forreferenceseetext.Table2.Resultsobtainedfordotproductsofpolynomialsofvariousdegree.Thenumber“supportvectors”isameanvalueperclassifier.Fig7.Labeledexamplesoferrorsonthetrainingsetforthe2nddegreepolynomialsupport-vectorclassifier.6.2.1美國(guó)郵政服務(wù)數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)美國(guó)郵政服務(wù)數(shù)據(jù)庫(kù)的數(shù)據(jù)是從現(xiàn)實(shí)生活中的郵政編碼采集的,很多研究者在此之上做過(guò)實(shí)驗(yàn).表1列出了公共實(shí)驗(yàn)和我們的實(shí)驗(yàn)中不同分類(lèi)器的性能.人工表現(xiàn)的結(jié)果由J.Bromley和E.Sackinger給出[5].CART的結(jié)果是貝爾實(shí)驗(yàn)室的DarylPregibon和MichaelD.Riley以及NJ的MurrayHill完成的.C4.5的結(jié)果是C.Cortes得到的,最優(yōu)兩層神經(jīng)網(wǎng)絡(luò)的結(jié)果是B.Scholkopf得到的.專(zhuān)門(mén)為此用途的五層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)(LeNet1)結(jié)果是由Y.LeCun等人取得的[9].本實(shí)驗(yàn)我們利用預(yù)處理技術(shù)(居中,傾斜,平滑)來(lái)合并實(shí)驗(yàn)中相關(guān)變量的知識(shí).數(shù)據(jù)平滑作為支持向量網(wǎng)絡(luò)的一項(xiàng)預(yù)處理技術(shù)在文獻(xiàn)[3]中進(jìn)行了研究.本實(shí)驗(yàn)與文獻(xiàn)[3]一致,選擇=0.75的平滑高斯核函數(shù).實(shí)驗(yàn)基于數(shù)據(jù)庫(kù)構(gòu)建了以(39)的內(nèi)積的多項(xiàng)式指示函數(shù).輸入空間的維數(shù)是256,多項(xiàng)式階數(shù)范圍從1到7.表2描述了實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)不是線(xiàn)性可分的.可以發(fā)現(xiàn),支持向量的個(gè)數(shù)增加非常緩慢.7階多項(xiàng)式只比3階多項(xiàng)式多了30%的支持向量,甚至比一階多項(xiàng)式還少.但是特征空間的維數(shù)7階多項(xiàng)式卻比3階多項(xiàng)式的1010倍還多.除此以外還能看到,隨著空間維數(shù)的增加性能并沒(méi)有多大的改變,可見(jiàn)沒(méi)有過(guò)擬合的問(wèn)題.線(xiàn)性分割器的支持向量數(shù)目較多是由于數(shù)據(jù)集的不可分導(dǎo)致的:200個(gè)向量包括了支持向量和值非零的訓(xùn)練向量.如果>1則訓(xùn)練向量被錯(cuò)分;每個(gè)線(xiàn)性分類(lèi)器在訓(xùn)練集上平均有34個(gè)樣本被錯(cuò)分.2階分類(lèi)器訓(xùn)練集上被錯(cuò)分的總數(shù)下降到了4.這4個(gè)樣本如圖7所示.值得注意的是,當(dāng)我們考慮所獲得的支持向量個(gè)數(shù)并不是期望的數(shù)目時(shí),實(shí)驗(yàn)中推廣能力的界保持不變.各種不同情況錯(cuò)誤概率的上界不超過(guò)3%(事實(shí)上在測(cè)試集上對(duì)單個(gè)分類(lèi)器錯(cuò)誤概率不超過(guò)1.5%).構(gòu)建多項(xiàng)式分類(lèi)器的時(shí)間不依賴(lài)于多項(xiàng)式的階數(shù),而僅依賴(lài)于支持向量的個(gè)數(shù).即使是最壞情況,也快于專(zhuān)門(mén)為此用途設(shè)計(jì)的最優(yōu)性能神經(jīng)網(wǎng)絡(luò)(LeNet1[9]).神經(jīng)網(wǎng)絡(luò)的性能是5.1%的粗錯(cuò)誤率.2階或更高階的多項(xiàng)式性能好于LeNetNIST數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)NIST數(shù)據(jù)庫(kù)作為基準(zhǔn)學(xué)習(xí)引入剛剛兩周.時(shí)間的限制只允許構(gòu)建一種類(lèi)型的分類(lèi)器,我們選擇4階多項(xiàng)式,且未進(jìn)行預(yù)處理.該選擇是基于美國(guó)郵政服務(wù)數(shù)據(jù)庫(kù)上的實(shí)驗(yàn).表3列出了10個(gè)分類(lèi)器的支持向量數(shù)目和訓(xùn)練集與測(cè)試集上的性能.可以看到,即使是4階的多項(xiàng)式(多于108的自由參數(shù))也會(huì)在訓(xùn)練集上出錯(cuò).平均訓(xùn)練誤差是0.02%,即平均每類(lèi)12個(gè).分類(lèi)器1錯(cuò)分的14個(gè)樣本如圖8所示.再次注意對(duì)于所得的不同支持向量數(shù)目上界(5)是如何保持的.Table3.Resultobtainedfora4thdegreepolynomialclassifierontheNISTdatabase.Thesizeofthetrainingsetis60,000,andthesizeofthetestsizeis10,000patterns.Fig8.The14misclassifiedtestpatternswithlabelsforclassifier1.Patternswithlabel“1”Fig9.Resultsfromthebenchmarkstudy.十個(gè)分類(lèi)器在測(cè)試集上的聯(lián)合誤差是1.1%.這個(gè)結(jié)果應(yīng)該在學(xué)習(xí)基準(zhǔn)上和其他的分類(lèi)器進(jìn)行比較.包括一個(gè)線(xiàn)性分類(lèi)器,一個(gè)具有60,000個(gè)原型的k(=3)最近鄰分類(lèi)器,兩個(gè)專(zhuān)門(mén)為數(shù)字識(shí)別而設(shè)計(jì)的神經(jīng)網(wǎng)絡(luò)(LeNet1和LeNet4).作者只給出了支持向量網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果.學(xué)習(xí)基準(zhǔn)的比較結(jié)果如圖9所示.我們引用文獻(xiàn)[4]對(duì)學(xué)習(xí)基準(zhǔn)的描述來(lái)作為本節(jié)的總結(jié):“很長(zhǎng)一段時(shí)間LeNet1被認(rèn)為是發(fā)展水平…通過(guò)一系列在結(jié)構(gòu)和錯(cuò)誤特征分析的實(shí)驗(yàn),LeNet4被認(rèn)為是…支持向量網(wǎng)絡(luò)具有很高的精度,很令人矚目,因?yàn)楹推渌咝阅艿姆诸?lèi)器不一樣,它不包括問(wèn)題的幾何學(xué)知識(shí).事實(shí)上,即使是對(duì)圖像像素進(jìn)行加密,比如通過(guò)一個(gè)固定隨機(jī)的置換,它依然可以工作得很好.”最后要說(shuō)的是,支持向量網(wǎng)絡(luò)性能的進(jìn)一步提高可以通過(guò)構(gòu)建一個(gè)反應(yīng)已有問(wèn)題先驗(yàn)信息的內(nèi)積函數(shù).7總結(jié)本文介紹了一種針對(duì)兩類(lèi)分類(lèi)問(wèn)題的新型學(xué)習(xí)機(jī)器支持向量網(wǎng)絡(luò).支持向量網(wǎng)絡(luò)包含3個(gè)思想:求解最優(yōu)超平面的技術(shù)(允許將解向量在支持向量上展開(kāi)),內(nèi)積回旋的思想(將決策面求解從線(xiàn)性擴(kuò)展到非線(xiàn)性),和軟間隔的概念(允許訓(xùn)練集上出現(xiàn)錯(cuò)誤).該算法已經(jīng)過(guò)測(cè)試并和其他分類(lèi)算法進(jìn)行過(guò)性能比較.盡管它的決策面設(shè)計(jì)簡(jiǎn)單但是在比較學(xué)習(xí)上它展現(xiàn)了很好的性能.其他特征例如容量控制能力和決策面變換的簡(jiǎn)易性證實(shí)了支持向量網(wǎng)絡(luò)是一種及其強(qiáng)大和通用的學(xué)習(xí)機(jī)器.References[1]M.Aizerman,E.Braverman,andL.Rozonoer.Theoreticalfoundationsofthepotentialfunctionmethodinpatternrecognitionlearning.AutomationandRemoteControl,25:821-837,1964.[2]T.W.AndersonandR.R.Bahadur.Classificationintotwomultivariatenormaldistributionswithdifferentcovariancematrices.Ann.Math.Stat.,33:420-431,1966.[3]B.E.Boser,I.Guyon,andV.N.Vapnik.Atrainingalgorithmforoptimalmarginclassifiers.InProceedingsoftheFifthAnnualWorkshopofComputationalLearningTheory,volume5,pages144-152,Pittsburg,1992.ACM.[4]L.Bottou,C.Cortes,J.S.Denker,H.Drucker,I.Guyon,L.D.Jackel,Y.LeCun,E.SackingerP.Simard,V.Vapnik,andU.A.Miller.Comparisonofclassifiermethods:Acasestudyinhandwrittendigitrecognition.Proceedingsof12thInternationalConferenceonPatternRecognitionandNeuralNetwork,1994.[5]J.BromleyandE.Sackinger.Neural-networkandk-nearest-neighbor