svm算法的泛化性能

svm算法的泛化性能

1svm的應(yīng)用,源于數(shù)學(xué)人工智能是繼專家系統(tǒng)以來的另一個重要研究領(lǐng)域，也是人工智能和神經(jīng)計算的中心主題之一。對學(xué)習(xí)算法的創(chuàng)新可以極大地推動整個神經(jīng)網(wǎng)絡(luò)的發(fā)展。大多數(shù)機器學(xué)習(xí)算法的研究包括對數(shù)據(jù)的預(yù)測。目的是評估已知數(shù)據(jù)的相關(guān)性，并預(yù)測未來的情況。近年來，基于神經(jīng)網(wǎng)絡(luò)、靈活性統(tǒng)計和統(tǒng)計力學(xué)的學(xué)習(xí)算法取得了一些進展，兩位科學(xué)家提出了一些新的概念和方法。從表面上看，這些概念和方法之間存在一些聯(lián)系，但事實上，它們之間存在許多差異。人們需要一個完整的理論體系來預(yù)測學(xué)習(xí)算法。最近出現(xiàn)的VC理論(Vapnik-Chervonenkis)將學(xué)習(xí)問題的相關(guān)概念和原理進行了很好的結(jié)合,它比基于直覺和生物理論等經(jīng)驗性機器學(xué)習(xí)方法更有說服力,VC理論被認為是從有限數(shù)據(jù)中預(yù)測相關(guān)性的統(tǒng)一數(shù)學(xué)框架.盡管VC理論作為數(shù)學(xué)理論已出現(xiàn)了25年,但人們還沒有充分體會和完全欣賞到它的理論和實際價值,近期的研究已經(jīng)表明VC理論可以改善各種各樣的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法.更為重要的是基于VC理論的創(chuàng)造性機器學(xué)習(xí)方法SVM(SupportVectorMachine)的出現(xiàn).SVM是由Vapnik領(lǐng)導(dǎo)的AT&TBell實驗室研究小組提出的一種新的非常有潛力的分類技術(shù),它開辟了學(xué)習(xí)高維數(shù)據(jù)新的天地,這種新的學(xué)習(xí)算法可以替代多層感知機、RBF神經(jīng)網(wǎng)絡(luò)和多項式神經(jīng)網(wǎng)絡(luò)已有的學(xué)習(xí)算法,它也是一種可實現(xiàn)一些表示問題的建設(shè)性方法,在多層感知機、RBF神經(jīng)網(wǎng)絡(luò)和小波神經(jīng)網(wǎng)絡(luò)中有成功運用,同時SVM方法實際中有一些應(yīng)用(如人面檢測、KDD和信號處理)也說明了VC理論的理論和實用價值.1995年,文獻和文獻的出現(xiàn)是SVM誕生的標(biāo)志,目前國外學(xué)者已取得了一些成果,作者的很多資料都從Internet網(wǎng)絡(luò)獲得,IEEETransactionsonNeuralNetworks也已經(jīng)出版了關(guān)于VC維理論和SVM方面的專輯(見Vol.10(5),1999).但目前在國內(nèi),SVM的研究似乎尚未起步.我們曾對神經(jīng)網(wǎng)絡(luò)理論進行了較深入的研究,在本文中作者以和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法相比較的方式,介紹SVM理論及其研究進展,目的在于激發(fā)國內(nèi)眾多神經(jīng)網(wǎng)絡(luò)理論研究者的興趣,拋磚引玉,以期促進和推動我國該方面的研究.2bp網(wǎng)絡(luò)學(xué)習(xí)算法在過去的十年里,人工神經(jīng)網(wǎng)絡(luò)理論及其應(yīng)用的研究是計算機與人工智能、認知科學(xué)、數(shù)學(xué)和物理學(xué)等相關(guān)專業(yè)的熱點.由于神經(jīng)網(wǎng)絡(luò)具有很強自學(xué)習(xí)能力,即系統(tǒng)在學(xué)習(xí)過程中不斷完善自己,具有創(chuàng)新特點,它不同于AI中的專家系統(tǒng),后者只是專家經(jīng)驗的知識庫,并不能創(chuàng)新和發(fā)展,因而吸引了眾多的研究學(xué)者,學(xué)習(xí)算法的研究也成為神經(jīng)網(wǎng)絡(luò)研究中的關(guān)鍵問題.1958年,Rosenblatt提出了感知機(Peceptron)的概念,感知機在神經(jīng)網(wǎng)絡(luò)的研究中有著重要的地位和意義,它首先提出了自組織、自學(xué)習(xí)的思想,對能夠解決的線性可分問題,有一個非常清楚的收斂算法,并從數(shù)學(xué)給出了嚴格的證明.以后的很多模型都是在這種指導(dǎo)思想下建立的,或是它的改進和推廣.1986年,Rumelhart和McClelland領(lǐng)導(dǎo)的PDP研究小組在Werbos博士論文的基礎(chǔ)上發(fā)展了誤差反向傳播網(wǎng)絡(luò)學(xué)習(xí)算法,即BP算法.BP網(wǎng)絡(luò)可以處理線性不可分問題,具有強大的運算能力,糾正了Minsky等人的片面觀點,神經(jīng)網(wǎng)絡(luò)的研究也由復(fù)興走向第二次高潮.盡管感知機對線性可分問題,有一個收斂的學(xué)習(xí)算法,但由于算法的初始值可任意選定,使得由此產(chǎn)生的分離超平面有無窮多種,往往造成了分類超平面嚴重偏向某一類,即導(dǎo)致了感知機泛化性能不高.另一方面,這種分類算法沒能對在分類中起關(guān)鍵作用的訓(xùn)練元素進行刻劃,當(dāng)分類結(jié)束后添加新的訓(xùn)練樣本時,先前已有的運算結(jié)果已無作用,網(wǎng)絡(luò)須重新學(xué)習(xí)所有樣本,可見這種算法沒有真正起到“學(xué)習(xí)”作用.雖然BP網(wǎng)絡(luò)通過增加隱層具有了非線性映射逼近能力,在神經(jīng)網(wǎng)絡(luò)的研究和應(yīng)用中占著舉足輕重的地位,也為神經(jīng)網(wǎng)絡(luò)的研究起過強烈的推動作用,但由于BP網(wǎng)絡(luò)學(xué)習(xí)算法實際上是利用梯度下降法調(diào)節(jié)權(quán)值使目標(biāo)函數(shù)達到極小,而目標(biāo)函數(shù)僅為各給定輸入和相應(yīng)輸出差的平方和,導(dǎo)致了BP網(wǎng)絡(luò)過分強調(diào)克服學(xué)習(xí)錯誤而泛化性能不強.同時BP網(wǎng)絡(luò)還具有一些其它難以克服的缺陷,如隱單元的個數(shù)難以確定,網(wǎng)絡(luò)的最終權(quán)值受初始值影響大等.另外,對在聯(lián)想記憶中起重要作用的Hopfield網(wǎng)絡(luò),它的能量函數(shù)也是各給定輸入和期望輸出差的平方和,因此學(xué)習(xí)算法與上述情形存在同樣的問題.近年來,隨著人工神經(jīng)網(wǎng)絡(luò)研究的深入,人們更加認識到它存在的嚴重不足,如盡管眾多的研究者已經(jīng)提出了大量的學(xué)習(xí)算法,但大都基于克服訓(xùn)練錯誤,從概率統(tǒng)計的角度說,神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法僅僅試圖使經(jīng)驗風(fēng)險最小化,并沒有使期望風(fēng)險最小化(見3、節(jié)4),與傳統(tǒng)的最小二乘法相比,在原理上卻缺乏實質(zhì)性的突破,同時也缺乏理論依據(jù).總之,神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法缺乏定量的分析與機理完備的理論結(jié)果.3神經(jīng)網(wǎng)絡(luò)的風(fēng)險最小二乘兩類模式的識別問題可描述如下:給定決策函數(shù)集這里∧為參數(shù)集,已知來自于一未知分布P(x,y)一組樣本模式識別的目的是在決策函數(shù)集中尋求函數(shù),最小化期望風(fēng)險這里fλ:RN→{-1,1}稱為假設(shè)函數(shù),集合H={fλ(x):λ∈∧}稱為假設(shè)空間.對神經(jīng)網(wǎng)絡(luò)來說,fλ可以解釋為徑向基函數(shù)或是有一些隱單元的多層感知機形成的非線性映射,在這種情形下,Λ就是網(wǎng)絡(luò)的權(quán)值集合.由于分布P(x,y)未知,因此實際上R(λ)無法計算,因而也就無法最小化期望風(fēng)險.但由于已知P(x,y)的一些樣本點,且當(dāng)樣本點的個數(shù)l趨于無窮大時,經(jīng)驗風(fēng)險趨于期望風(fēng)險R(λ).很多函數(shù)逼近算法,如神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法和最小二乘法正是基于所謂風(fēng)險最小化原理,即最小化經(jīng)驗風(fēng)險試圖使期望風(fēng)險最小化.4基于穩(wěn)定的二值分類函數(shù)早在1971年,Vapnik就指出經(jīng)驗風(fēng)險的最小值未必收斂于期望風(fēng)險的最小值,即經(jīng)驗風(fēng)險最小化原理不成立,并且證明了經(jīng)驗風(fēng)險的最小值收斂于期望風(fēng)險的最小值當(dāng)且僅當(dāng)R(λ)依概率一致收斂于Remp(λ),當(dāng)且僅當(dāng)假設(shè)空間{fλ(x):λ∈∧}的VC維是有限的.下面首先介紹VC維(Vapnik-Chervonenkisdimension).近年來,數(shù)理統(tǒng)計、計算機科學(xué)和統(tǒng)計力學(xué)都試圖對神經(jīng)網(wǎng)絡(luò)的信息處理能力進行深刻的分析,各自都取得了一定的進展,這些進展表面看來有很多聯(lián)系,但實際上又不全相同,這就給問題的綜合分析帶來一定的困難.VC維被認為是數(shù)學(xué)和計算機科學(xué)中非常重要的定量化概念,它可用來刻畫分類系統(tǒng)的性能.但不幸的是,對大部分情形,VC維的精確值無法計算,僅能獲得VC維的界,即便如此,也只是對很簡單的系統(tǒng)而言的.VC維dVC是通過生長函數(shù)Δ(p)來定義的.設(shè)X是一集合,C是將X進行二值分類的所有分類函數(shù)c:X→{-1,1}的集合.對N個輸入和單輸出的感知器來說,設(shè)X是所有輸入向量ζ的集合,ζ∈RN或ζ∈{-1,1}N,分類的結(jié)果由二值輸出σ=±1來確定,此時C就是所有可能權(quán)值和閾值構(gòu)成的感知器分類映射的集合.對任意p個不同的輸入{x1,x2,…,xp},其中xi為N維向量,i=1,2,…,p.定義Δ(p)為網(wǎng)絡(luò)所有輸出構(gòu)成的p維向量(σ1,σ2,…,σp)集合中不同元素的個數(shù),這里σi為對應(yīng)于輸入xi的輸出.由于σ=±1,顯然Δ(p)的最大值為2p.根據(jù)Sauer引理,對二值分類函數(shù)集合C,必存在自然數(shù)dVC(可以是無窮大),使得dVC稱為二值分類函數(shù)集合C的VC維.VC維可以用來描述機器學(xué)習(xí)中的一些極端情形,而基于統(tǒng)計力學(xué)的學(xué)習(xí)方法僅僅考慮典型情形,但是即使對非常簡單的單層感知器,典型情形和最差情形差異都非常巨大.得出基于經(jīng)驗風(fēng)險最小化原理的學(xué)習(xí)算法缺乏理論依據(jù)只是解決了機器學(xué)習(xí)問題的一個方面.為了提出理論依據(jù)更可靠的學(xué)習(xí)算法,Vapnik和Chervonenkis深入研究R(λ)和Remp(λ)的關(guān)系,得出如下不等式以概率1-η成立:這里h是假設(shè)空間H的VC維.從(1)式可以看出,必須使經(jīng)驗風(fēng)險、VC維和訓(xùn)練集元素個數(shù)的比率同時最小化,才能最小化期望風(fēng)險.由于經(jīng)驗風(fēng)險通常是VC維h的減函數(shù),對給定元素數(shù)目的訓(xùn)練集,應(yīng)存在最優(yōu)的h值,使期望風(fēng)險最小化.對多層感知器和RBF網(wǎng)絡(luò)來說,計算VC維相當(dāng)于確定它們隱層單元的數(shù)目,這是非常困難的,它本身也是神經(jīng)網(wǎng)絡(luò)亟待解決的難題.為了克服VC維難以計算這一缺陷,Vapnik在文獻中提出了結(jié)構(gòu)化風(fēng)險最小化原理(StructureRiskMinimizationPrinciple),它基于(1)式,即為了最小化期望風(fēng)險,必須同時最小化經(jīng)驗風(fēng)險和VC維.5svm算法介紹我們知道,訓(xùn)練學(xué)習(xí)機器的一般方法都是調(diào)整參數(shù),使某一定量指標(biāo)最小化,關(guān)鍵是這個定量指標(biāo)如何定義才能使學(xué)習(xí)算法性能優(yōu)越.神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法的指標(biāo)一般都是僅僅依賴于先驗知識,定量指標(biāo)只定義在訓(xùn)練集上,如BP算法的定量指標(biāo)就是其網(wǎng)絡(luò)的目標(biāo)函數(shù),即學(xué)習(xí)錯誤,BP算法采用最速下降法極小化學(xué)習(xí)錯誤.但是低的學(xué)習(xí)錯誤并不能保證對處理未來數(shù)據(jù)低的期望錯誤,這種期望錯誤可以用來衡量泛化性能,因此尋求一種既有低的學(xué)習(xí)錯誤又有好的泛化性能的學(xué)習(xí)算法非常必要,SVM就是這樣一種學(xué)習(xí)算法,它是結(jié)構(gòu)化風(fēng)險最小化原理的近似實現(xiàn),因為它同時最小化經(jīng)驗風(fēng)險和VC維的界.SVM最初用來解決模式識別問題,目的是發(fā)現(xiàn)泛化性能好的決策規(guī)則,SupportVectors實際上是訓(xùn)練集的子集,對SupportVectors的最優(yōu)分類等價于對訓(xùn)練集的分類.下面通過一兩類模式識別問題說明SVM算法的由來.設(shè)數(shù)據(jù)集合Class1和Class2是線性可分的,即存在(w,b),使分類的目的是尋求(w,b),最佳分離Classl和Class2,此時假設(shè)空間由所有的fω,b=Sign(ω·x+b)組成.為減少分類平面的重復(fù),對(w,b)進行如下約束:滿足(2)的超平面稱為典型超平面,可以證明典型超平面集合的VC維是N+1,即所有自由參數(shù)的數(shù)目.如果x1,x2,…,xl位于N維單位球內(nèi),集合{fw,b=sign(w·x+b):||w‖≤A}的VC維h滿足:當(dāng)數(shù)據(jù)點x1,x2,…,xl位于半徑為R的球內(nèi)時,(3)式變?yōu)樽⒁獾近cx到(w,b)確定的超平面的距離為根據(jù)約束條件(2)式可知,典型超平面到最近數(shù)據(jù)點的距離為,顯然如果||w‖≤A,典型超平面到最近數(shù)據(jù)點的距離必然大于或等于,實際上此時典型超平面已將分類的對象由單純的數(shù)據(jù)點變?yōu)閿?shù)據(jù)點的球形鄰域.對線性可分的情形(即經(jīng)驗風(fēng)險為零),求最佳(w,b)歸結(jié)為下列二次規(guī)劃問題:根據(jù)(4)式,問題(6)的意思是指在經(jīng)驗風(fēng)險為零的情形下,使VC維的界最小化,從而最小化VC維,這正是結(jié)構(gòu)風(fēng)險最小化原理.根據(jù)(5)式,最小化||w‖2等價于尋求一種特殊的超平面,它使數(shù)據(jù)集合Class1和Class2凸包之間沿垂直于自己方向的距離最大,故SVM有時也稱為最大邊緣(maximummargin)算法.圖1明顯說明了邊緣大小和泛化性能之間的關(guān)系.下面利用經(jīng)典優(yōu)化中的對偶方法對優(yōu)化問題(6)進行處理:定義問題(6)的Lagrange函數(shù)由于規(guī)劃問題(6)是凸規(guī)劃,根據(jù)鞍點定理,規(guī)劃問題(6)的解由Lagrange函數(shù)的鞍點決定,令用上標(biāo)*表示規(guī)劃問題(6)的解,則將(9)和(10)代入(7)得規(guī)劃問題(6)的對偶問題為這里y=(y1,y2,…,yl),D是對稱的l×l矩陣,Dij=yiyjxi·xj.從互補性條件:容易知道當(dāng)約束(6)有效時必有,對應(yīng)的數(shù)據(jù)點xi我們稱之為Supportvector.對任意Supportvector,根據(jù)(12)可得分類的決策函數(shù)則為值得提出的是,二次規(guī)劃問題(6)是比較簡單的,但通過上述的處理,可以給出SupportVector的定義;更為重要的是,這種方法可以進行推廣,得到處理線性不可分情形的軟邊緣(softmargin)算法和處理非線性問題的核(kernel)方法.以上的分析實際上說明了SVM是一種基于規(guī)劃的學(xué)習(xí)算法,為了定量化研究神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法的性能,將其轉(zhuǎn)化為約束的優(yōu)化問題,這是一條非常值得探索的思路,已有學(xué)習(xí)者提出并加以研究.6其它學(xué)習(xí)算法目前,很多關(guān)于SVM和VC的理論和應(yīng)用問題都亟待研究.一方面,這種基于統(tǒng)計學(xué)原理的理論思路對新的學(xué)習(xí)算法的提出很有啟發(fā),另一方面,由于SVM出現(xiàn)不久,其理論體系和算法實現(xiàn)尚有大量問題有待于發(fā)展和完善.在上述問題中,我們認為下面幾個問題尤其值得研究.1.應(yīng)用VC理論研究泛化性能更好的學(xué)習(xí)算法,如研究基于其它統(tǒng)計學(xué)原理或使期望風(fēng)險近似最小化的其它學(xué)習(xí)算法.2.完善SVM方法.SupportVectors的確定可轉(zhuǎn)化為約束的優(yōu)化問題,但當(dāng)訓(xùn)練集的規(guī)模很大時,傳統(tǒng)的優(yōu)化方法難以滿足實時性要求,如何設(shè)計快速有效算法是SVM中的重要問題之一;另外,對非線性分類問題,SVM的核方法仍有一些理論缺陷.3.SVM的應(yīng)用研究.由于SVM算法是對神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法、最小二乘法的改良,應(yīng)用SVM方法到實際問題中,如建模、參數(shù)辨識和自適應(yīng)控制等問題,并將它與已有的處理結(jié)果進行比較也是非常有實際意義的.對形如(11)的含等式和盒式不等式約束的規(guī)劃問題,文獻提出了一種大范圍收斂的連續(xù)神經(jīng)網(wǎng)絡(luò)模型進行求解,文獻對的模型進行了簡化和完善,使之具有了更好的功能(求解非線性規(guī)劃問題)和性能(指數(shù)收斂性).我們認為這種基于動力系統(tǒng)的方法是解決優(yōu)化問題的先進方法,一方面,這種模型可用電路實現(xiàn),實時求解大規(guī)模的優(yōu)化問題,另一方面,它的離散化可產(chǎn)生不同的數(shù)值算法,克服了普通數(shù)值算法須不斷尋求