半監(jiān)督學(xué)習(xí)的流形總則化改進(jìn)算法

半監(jiān)督學(xué)習(xí)的流形總則化改進(jìn)算法

0半監(jiān)督學(xué)習(xí)過程事實(shí)上，收集無標(biāo)記樣本比收集有標(biāo)記樣本更簡單。如果把有標(biāo)簽樣本和無標(biāo)簽樣本共同作為學(xué)習(xí)的樣本集合,這種學(xué)習(xí)就是半監(jiān)督學(xué)習(xí)。在模式識(shí)別的方法中,如果能夠利用無標(biāo)簽數(shù)據(jù)的學(xué)習(xí)來提高識(shí)別性能,將具有更好的實(shí)用性。文獻(xiàn)在全局風(fēng)險(xiǎn)最小化(OverallRiskMinimization,ORM)下引入了半監(jiān)督支持向量機(jī)(S3VM),與傳統(tǒng)的支持向量機(jī)(SupportVectorMachine,SVM)相比,在性能上有了明顯的提高,但它的求解計(jì)算卻十分復(fù)雜,尤其不便于新數(shù)據(jù)的加入。目前最主要的研究成果是直推式支持向量機(jī)(TSVM),該算法是在半監(jiān)督學(xué)習(xí)問題上的一種擴(kuò)展,但它存在訓(xùn)練速度慢、回溯式學(xué)習(xí)多、學(xué)習(xí)性能不穩(wěn)定,主要針對(duì)分類問題等缺點(diǎn)。文獻(xiàn)提出了一種改進(jìn)算法PTSVM,通過成對(duì)標(biāo)注和標(biāo)記重置的辦法改進(jìn)了TSVM的性能,但其計(jì)算相對(duì)復(fù)雜,且主要針對(duì)分類問題。文獻(xiàn)中提到了流形正則化的一種算法,此算法比TSVM算法在學(xué)習(xí)性能上又進(jìn)了一步,但是從文章中可以看出,該算法也主要針對(duì)分類問題。目前,很多研究都在分類問題上都取得了進(jìn)步,但對(duì)于回歸問題的研究相對(duì)較少。本文提出了一種流形正則化算法,主要針對(duì)半監(jiān)督學(xué)習(xí)中的回歸問題,有效解決了傳統(tǒng)TSVM中過多的回溯式學(xué)習(xí)問題,與支持向量回歸相比,該算法在學(xué)習(xí)精度上有明顯提高,即使輸入數(shù)據(jù)帶有噪音時(shí),也能表現(xiàn)其優(yōu)越性。1傳統(tǒng)正則化因子ty為了簡單起見,假定回歸模型的輸出為一維,其實(shí)這并不失一般性。給定包含l個(gè)由輸入和輸出組成的訓(xùn)練集:(xi,di)(i=1,…,l,di∈R)。對(duì)于線性模型y=f(x)=b-wTx,傳統(tǒng)的正則化方法認(rèn)為,當(dāng)xi∈Rn時(shí):f=argminy∈l2l∑i=1?i(di-yi)+δ?yΤy/2(1)f=argminy∈l2∑i=1l?i(di?yi)+δ?yTy/2(1)其中,y=(y1,y2,…,yl)T,yl=f(xl)為模型的輸出;而l∑i=1?i(di-yi)∑i=1l?i(di?yi)為懲罰項(xiàng),?i(·)為非負(fù)的一元凸函數(shù),δ·yTy/2為傳統(tǒng)正則化項(xiàng),δ為yTy的傳統(tǒng)正則化因子。由半監(jiān)督學(xué)習(xí)理論,樣本點(diǎn)(xi,di)(i=1,2,…,l)為已知的,而對(duì)于xi(i=l+1,l+2,…,L),其目標(biāo)值di是未知而需要求解的。這種情況下,根據(jù)流形正則化理論,在高維空間中,數(shù)據(jù)一般被認(rèn)為是嵌在低維的流形上的,特別是在輸入數(shù)據(jù)維數(shù)比較高的情況下。根據(jù)維數(shù)災(zāi)理論可以知道,樣本在高維總是非常稀疏的,這樣要達(dá)到理想的泛化效果,就有必要使用流形上的正則化項(xiàng),即在式(1)的基礎(chǔ)上加入式(2):wΤw/2+a/2L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2(2)wTw/2+a/2∑i=1L∑j=1Lhij(yi?yj+wT(xi?xj))2(2)其中,hij為樣本xi和xj相鄰程度,比如,如果j∈Ni,Ni是和xi相鄰的K個(gè)最近樣本點(diǎn)的集合,那么hij可以有三種取值情況:1)hij=1;2)hij=exp(-‖xj-xi‖2/σ);3)hij=1/‖xj-xi‖2;否則hij=0。a為流形上的正則化因子。那么我們的優(yōu)化目標(biāo)是:f=argminywΤw/2+δ?yΤy/2+a/2+L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2+l∑i=1?i(di-yi)(3)f=argminywTw/2+δ?yTy/2+a/2+∑i=1L∑j=1Lhij(yi?yj+wT(xi?xj))2+∑i=1l?i(di?yi)(3)其中,y=(y1,y2,…,yl,yl+1,…,yL)T,這時(shí)yi+wTxi=b,其中b為一常數(shù),i=1,…,l一般不再成立。可以看到,a充分大的時(shí)候,(x,y)在y+wTx=b的超平面上;a較小的時(shí)候,則(x,y)在y+wTx=b的平面上上下波動(dòng)。需要特別說明的是,在建立最終的優(yōu)化目標(biāo)中,由于利用已知的有限樣本數(shù)據(jù)來估計(jì)潛在的未知流形,估計(jì)的結(jié)果很難完全準(zhǔn)確,這樣在式(3)中加入傳統(tǒng)的正則化項(xiàng)是完全有必要的。式(3)的優(yōu)化問題是一個(gè)嚴(yán)格凸優(yōu)化的問題,因此存在全局唯一最小點(diǎn),這樣就避免了存在局部最小等問題。2矩陣求取基本參數(shù)下面使用最小化目標(biāo)函數(shù)式(3)來求解半監(jiān)督學(xué)習(xí)的問題,以達(dá)到整個(gè)算法的實(shí)現(xiàn)和求解最終結(jié)果的目的。為了在推導(dǎo)過程中方便使用對(duì)偶定理,可以引入變量ξi,使得di-yi=ξi,其中i=1,2,…,l。這樣目標(biāo)函數(shù)變?yōu)榈仁郊s束下的優(yōu)化問題:f=argminywΤw/2+δ?yΤy/2+a/2L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2+l∑i=1?i(ξi)(4)s.t.di-yi=ξi;i=1,2,?,lf=argminywTw/2+δ?yTy/2+a/2∑i=1L∑j=1Lhij(yi?yj+wT(xi?xj))2+∑i=1l?i(ξi)(4)s.t.di?yi=ξi;i=1,2,?,l其中,y=(y1,y2,…,yl,yl+1,…,yL)T。由式(4),利用Lagrange乘子法可得:L(w,y,λ)=wΤw/2+δ?yΤy/2+a/2L∑i=1L∑j=1hij(yi-yj+wΤ(xi-xj))2+l∑i=1?i(ξi)+l∑i=1λi(di-ξi-yi)=12zΤ[(Ι00δ?Ι)+a?(XΙ)V(XΤΙ)〗z-zΤμ+L(w,y,λ)=wTw/2+δ?yTy/2+a/2∑i=1L∑j=1Lhij(yi?yj+wT(xi?xj))2+∑i=1l?i(ξi)+∑i=1lλi(di?ξi?yi)=12zT[(I00δ?I)+a?(XI)V(XTI)〗z?zTμ+l∑i=1λidi+l∑i=1(?i(ξi)-λiξi)(5)∑i=1lλidi+∑i=1l(?i(ξi)?λiξi)(5)其中:z=(wy)X=(x1,x2,?,xL)V=L∑i=1L∑j=1(ei-ej)hij(ei-ej)Τλ=(λ1,λ2,?,λl)Τμ=(0,?,0,nλ1,?,λl,0,?,0L-1)Τz=(wy)X=(x1,x2,?,xL)V=∑i=1L∑j=1L(ei?ej)hij(ei?ej)Tλ=(λ1,λ2,?,λl)Tμ=(0,?,0,nλ1,?,λl,0,?,0L?1)TI表示單位矩陣,它的位數(shù)根據(jù)上下文確定,后面所出現(xiàn)的I也類似。記H=(hij),則V=diag(He)+diag(HTe)-H-HT,其中e=(1,…,1)T:A=(Ι00δ?Ι)+α(XΙ)V(XΤΙ)(6)這時(shí)式(5)轉(zhuǎn)化為:L(w,y,λ)=12zΤAz-zΤμ+l∑i=1λidi+l∑i=1(?i(ξi)-λiξi)(7)L(λ)=-12μΤA-1μ+l∑i=1λidi-l∑i=1?*i(λi)其中,?*i(·)為?(·)的共軛,即?*i(λi)=minξiλiξi-?i(ξi)利用矩陣求逆引理:(A+BC)-1=A-1-A-1B(I+CA-1B)-1CA-1,對(duì)式(6)中A可得:A-1=(1-δ?XCXΤ-XC-CXΤB)其中:B=1δ(Ι-C)C=V((δ/a)?Ι+δ?XΤXV+V)-1(8)注意到μ=(0,…,0,λT,0,…,0)T前面的n個(gè)分量為零,這樣對(duì)偶優(yōu)化問題可以寫為:L(λ)=-12λΤB(1:l,1:l)λ+l∑i=1λidi-l∑i=1?*i(λi)其中,B(1:l,1:l)表示取矩陣B的前l(fā)階主子矩陣,即前l(fā)行和前l(fā)列構(gòu)成的矩陣。注意B=((1/a)·I+XTXV)((δ/a)·I+δ·XTXV+V)-1,這樣在計(jì)算時(shí)可以避免溢出的問題。由式(8)可以看出,C的計(jì)算僅僅需要兩個(gè)樣本的內(nèi)積。這樣就可以利用在支持向量機(jī)中使用的核函數(shù)技術(shù)或者稱為核技巧,將原始輸入空間的樣本x映射到高維甚至無窮維的特征空間得到ψ(x),然后使用核函數(shù)的方法,使得K(xi,xj)=(ψ(xi),ψ(xj)),其中(·,·)表示特征空間中的兩個(gè)向量的內(nèi)積。本文使用的是Gauss核函數(shù)K(xi,xj)=exp(-‖xi-xj‖2/ρ2),其中ρ為Gauss核參數(shù)。至于其他有關(guān)核函數(shù)的理論可以參考文獻(xiàn)。不妨記為B(1:l,1:l)=D-L-LT=D-G,其中,D表示對(duì)角矩陣,而L和LT表示為下三角部分和上三角部分,G=L+LT。這時(shí)我們?cè)O(shè)計(jì)的優(yōu)化算法為:λ(t+1)=φ(G·λ(t)+d)或者寫成分量形式有:λi(t+1)=φi(di+l∑j=1,j≠igijλj(t));i=1,2,…,l而φi(ζ)=argmaxλ{(lán)λζ-(12diiλ2+?*i(λ))},那么現(xiàn)在針對(duì)于回歸問題再繼續(xù)討論:?i(ξ)為常用的支持向量回歸的ε-不敏感誤差損失函數(shù):?(ξ)ε={|ξ|-ε,|ξ|>ε0,|ε|≤ε其中ε>0。然后經(jīng)過一些列的演算,可以得到迭代時(shí)的函數(shù)φi(ζ)如下:φ(ξ)ε={0,|ζ|≤ε(ζ-ε)/dii,ζ>ε(ζ+ε)/dii,ζ<ε其中dii是D的對(duì)角線上第i個(gè)元素。在求出λ之后,令η=(λ1,?,λl,0,?,0L-l)Τ有w=-XCη,y=(1/δ)η-(1/δ)Cη,求得實(shí)際輸出值。經(jīng)過以上推導(dǎo),算法步驟如下:1)輸入帶已知輸出的樣本點(diǎn)(xi,di)(i=1,2,…,l)和不帶已知輸出的數(shù)據(jù)xi(i=l+1,l+2,…,L),記X=(x1,x2,x3,…,xL)。2)求X的相鄰矩陣hij,H=(hij),V=diag(He)+diag(HTe)-H-HT,e=(1,…,1)T。3)求B=((1/a)·I+XTXV)((δ/a)·I+δ·XTXV+V)-1,其中Kij=K(xi,xj),然后取B矩陣的前l(fā)行和前l(fā)列得B(1:l,1:l)=D-L-LT=D-G,其中,D表示對(duì)角矩陣,而L和LT表示為下三角部分和上三角部分,G=L+LT。4)在時(shí)刻t,對(duì)i=1,2,…,l,依次計(jì)算λi(t+1)=φi(di+l∑j=1,j≠igijλj(t)),利用迭代計(jì)算出λ每一個(gè)分量。然后對(duì)于最終求得的λ=(λ1,λ2,…,λl)T,根據(jù)η=(λ1,?,λl,0,?,0L-l)Τ,求得η。5)根據(jù)y=(1/δ)η-(1/δ)Cη,求得最終的學(xué)習(xí)結(jié)果。3試驗(yàn)結(jié)果主要針對(duì)回歸問題進(jìn)行試驗(yàn),根據(jù)以上的算法步驟,以Matlab為試驗(yàn)平臺(tái),可以直觀地看到試驗(yàn)結(jié)果,以便證實(shí)本算法的可行性、有效性及其優(yōu)越性。為了使試驗(yàn)具有說服力,同時(shí)還采用網(wǎng)上通用的SVM工具箱(SVM_SteveGunn)作為支持向量機(jī)的試驗(yàn)工具,并且選擇與本算法相同的參數(shù)。3.1求相鄰矩陣時(shí)的-不敏感誤差損失的函數(shù),如果以較低的方式計(jì)算其為了輸入直觀,先選取嵌入在二維空間中的y=x3一維流形上的采樣作為輸入樣本點(diǎn),選取函數(shù)z=1/(x2+y2+1)+γ·n(其中y=x3,n為噪音項(xiàng),稱γ為噪音系數(shù))作為輸出,輸入點(diǎn)(x,y)就在y=x3這個(gè)一維的流形上。其中噪音項(xiàng)n是均值為0,方差為1的正態(tài)分布上的隨機(jī)向量(下文提到的噪音項(xiàng)n與此相同)。選取γ=0.02,已知樣本點(diǎn)x的取值范圍在-1和1之間且間隔0.02,未知樣本點(diǎn)的取值范圍在-0.99和0.99之間且間隔0.04。選取相鄰矩陣hij=exp(-‖xj-xi‖2/σ),σ=5;求C時(shí)使用的Gauss核參數(shù)ρ=0.1,δ=0.005,a=10;求函數(shù)φi(ζ)時(shí)使用的ε-不敏感誤差損失函數(shù),其中ε=0.005。如圖1,實(shí)線為期望輸出曲線,實(shí)心圓點(diǎn)為SVM學(xué)習(xí)后的輸出曲線,空心方塊為本算法學(xué)習(xí)后的輸出曲線。很明顯,輸出具有噪音時(shí),學(xué)習(xí)后的曲線也能較好地達(dá)到期望輸出效果,從圖1中也可以看到本算法的學(xué)習(xí)精度要高于SVM的學(xué)習(xí)精度,并且經(jīng)過計(jì)算,此算法的相對(duì)誤差為0.83%,而使用SVM的相對(duì)誤差為3.62%。圖2表示為求φi(ζ)時(shí)使用ε-不敏感誤差損失函數(shù)中的ε,在有噪音和無噪音時(shí)對(duì)平均誤差的影響。在有噪音的圖2(a)中,ε很小或稍大,平均誤差都會(huì)增大,此時(shí)ε不能取零;而無噪音時(shí)如圖2(b),ε取得越小越好,此時(shí)ε可以取零。在圖3(a)中,隨著噪音的增加,平均誤差是逐漸增加的,沒有突變的發(fā)生,那么我們認(rèn)為該算法具有較強(qiáng)的抗干擾能力。圖3(b)為求相鄰矩陣H時(shí)用到的σ對(duì)平均誤差的影響。在本文算法推導(dǎo)中已經(jīng)介紹hij的三種取值情況,從圖中可以看到隨著σ的增大,hij的取值很快退到第一種情況,達(dá)到了理想的效果。由此可見,在文獻(xiàn)中提到的基于選擇第二種鄰域函數(shù)所得到的結(jié)論,在回歸問題中并不適用。本文算法是對(duì)文獻(xiàn)相關(guān)內(nèi)容的一個(gè)改進(jìn)。3.2svm的輸出函數(shù)為c.n,為2.在上一個(gè)試驗(yàn)中,輸入數(shù)據(jù)位于一個(gè)嚴(yán)格的一維流形上,但在很多實(shí)際應(yīng)用中,輸入數(shù)據(jù)本身是帶有噪音的,這些輸入就不一定嚴(yán)格在一個(gè)流形上,這時(shí)選取x=sin(θ)+β·n,y=cos(θ)+β·n作為二維輸入,其中n為噪音項(xiàng),β為噪音系數(shù),θ為參數(shù)。已知樣本點(diǎn)的θ取0到2π之間間隔0.04的值,未知樣本點(diǎn)的θ取-π到π之間,間隔0.04的值,β=0.02。選取輸出函數(shù)z=1/(x·y+1)+γ·n(n為噪音項(xiàng),γ為噪音系數(shù)),γ=0.03。選取相鄰矩陣hij=exp(-‖xj-xi‖2/σ),σ=3;求C時(shí)使用的Gauss核參