支持向量機(jī)的增量式學(xué)習(xí)和在線學(xué)習(xí)方法

支持向量機(jī)的增量式學(xué)習(xí)和在線學(xué)習(xí)方法

1增量式和在線式學(xué)習(xí)算法支持向量機(jī)（svm）是魏倫理等人提出的一種新的機(jī)學(xué)習(xí)方法。由于其出色的學(xué)習(xí)能力，它在國內(nèi)外學(xué)術(shù)界引起了廣泛的關(guān)注，并在模式識別和函數(shù)估算方面取得了越來越多的應(yīng)用。上述應(yīng)用程序的示例都是線性的，可以使用線性學(xué)習(xí)算法來解決。當(dāng)學(xué)生的樣本通過時間序列獲得或在線搜索而獲得時，有必要使用漸進(jìn)式學(xué)習(xí)算法或在線學(xué)習(xí)算法。此外，隨著時間的推移，高速學(xué)習(xí)算法的輸出能力可以隨著時間的推移而進(jìn)步。因此，近年來，一些科學(xué)家提出了三種基于參考支持向量機(jī)的數(shù)量或在線學(xué)習(xí)算法。然而，這些算法基于標(biāo)準(zhǔn)支持向量機(jī)，即在線解決了非線性二次規(guī)劃問題，計算復(fù)雜性高。然而，對于在線學(xué)習(xí)算法的一項重要要求是，在采樣時間周期內(nèi)，為了更新參數(shù)，必須完成支持向量機(jī)的完整計算。為了降低支持向量機(jī)的計算復(fù)雜性，suyzer提出了最小二乘支持向量機(jī)（lssvm）。為了將支持向量機(jī)的學(xué)習(xí)問題轉(zhuǎn)換為線性方程組問題，因此具有快速運行的速度。在這項工作中，我們使用了最小的平方檢測算法和支持向量機(jī)的在線學(xué)習(xí)算法。2最小二乘支持向量機(jī)最小二乘支持向量機(jī)與標(biāo)準(zhǔn)支持向量機(jī)的不同在于它把不等式約束改成等式約束,并把經(jīng)驗風(fēng)險由偏差的一次方改為二次方.回歸最小二乘支持向量機(jī)的提法如下:對于一個給定的訓(xùn)練數(shù)據(jù)集:利用高維特征空間中的線性函數(shù):來擬合樣本集,其中非線性映射?(?)?(?)把數(shù)據(jù)集從輸入空間映射到特征空間,以便使輸入空間中的非線性擬合問題變成高維特征空間中的線性擬合問題.根據(jù)結(jié)構(gòu)風(fēng)險最小化原理,綜合考慮函數(shù)復(fù)雜度和擬合誤差,回歸問題可以表示為約束優(yōu)化問題:為了求解上述優(yōu)化問題,把約束優(yōu)化問題變成無約束優(yōu)化問題,建立Lagrange函數(shù):根據(jù)KKT條件有:從方程組(3)中消去ei,w后,可以得到:其中,y=(y1,y2,…,yl)T,e1=(1,1,…,1)T,α=(α1,α2,…,αl)T,Qij=(?(xi)·?(xj))=k(xi,xj),i,j=1,2,…,l.所求的擬合函數(shù),即支持向量機(jī)的輸出為從式(4)可以看出,最小二乘支持向量機(jī)的訓(xùn)練問題歸結(jié)為一個線性方程組的求解問題,而不像標(biāo)準(zhǔn)支持向量機(jī)那樣要求解一個二次型規(guī)劃問題,而解線性方程組比求解二次規(guī)劃要簡單快速.最小二乘支持向量機(jī)與標(biāo)準(zhǔn)支持向量機(jī)比較起來,具有的特點如下:(1)最小二乘支持向量機(jī)比標(biāo)準(zhǔn)支持向量機(jī)具有更小的計算復(fù)雜性;(2)最小二乘支持向量機(jī)的解喪失稀疏性,即解中含有的支持向量的個數(shù)很多,甚至包括全部訓(xùn)練樣本;(3)最小二乘支持向量機(jī)能夠把支持向量機(jī)、調(diào)整神經(jīng)網(wǎng)絡(luò)、高斯過程、bays技術(shù)有機(jī)地統(tǒng)一在一起,能夠探討它們的本質(zhì)聯(lián)系;(4)最小二乘支持向量機(jī)能夠擴(kuò)展為自回歸的形式來處理動態(tài)問題.3最小二乘支持向量增量學(xué)習(xí)首先研究最小二乘支持向量機(jī)的增量式學(xué)習(xí)算法.對于增量式學(xué)習(xí)來講,樣本集是遞增的,即樣本集{(xi,yi)}i=ti=1i=ti=1(t表示一個自然數(shù))隨著時刻t的遞進(jìn)而每次新增一個樣本.學(xué)習(xí)的樣本集可以表示為{x(t),y(t)},其中,x(t)=[x1,x2,…,xt],y(t)=(y1,y2,…,yt)T,xt∈Rn,yt∈R.這樣核函數(shù)矩陣Q、待求的Lagrange乘子α和常值偏差b都是t的函數(shù),表示如下:Qt(i,j)=k(xi,xj),i,j=1,2,…,t,α(t)=(α1,α2,…,αt)T,b(t)=bt,最小二乘支持向量機(jī)的輸出式(5)變?yōu)樵O(shè)H(t)=Qt+C-1I,則式(4)可以改寫為根據(jù)式(7)可得令U(t)=H(t)-1,并在式(9)兩端同乘以e1TU(t),有綜合考慮式(8)、(10),有可得代入式(9),可求得從式(12)、(13)可以看出,為了求出α(t)、b(t),關(guān)鍵點在于求出H(t)的逆U(t).在H(t)的行列數(shù)較高時,求逆的計算復(fù)雜性很大,下面將利用矩陣計算的技巧來求H(t)的逆U(t).在t時刻,核函數(shù)矩陣Qt是t×t的方陣:則H(t)也是t×t的方陣.在t+1時刻,新數(shù)據(jù)樣本(xt+1,yt+1)將會加進(jìn)來,樣本總數(shù)將達(dá)到t+1個,核函數(shù)矩陣Qt+1是(t+1)×(t+1)的方陣,它比t時刻的核函數(shù)矩陣Qt多一行、一列:則H(t+1)也是(t+1)×(t+1)的方陣:比較H(t+1)和H(t)的元素,可以看到,H(t+1)能寫成如下分塊矩陣的形式:其中,V(t+1)=[k(x1,xt+1),…,k(xt,xt+1)]T,v(t+1)=k(xt+1,xt+1)+1/C.對于矩陣A,假設(shè)可以表示成分塊矩陣的形式:當(dāng)A-1及A-111?111存在時,有其中B=A22-A21A-111?111A12,I為單位陣.若分塊陣A1111為一對稱矩陣,A12為一列向量E,A21為行向量ET,A22為一不為零的標(biāo)量d,則式(16)簡化為[A11EEΤd]-1=[A11-1000]+[A-111E-Ι]B-1[EΤA-111-Ι]其中,利用式(17)來求U(t+1):這里,可以看出利用式(18),U(t+1)可以通過U(t)遞推求得,當(dāng)t較小時再直接求矩陣U(t),比如t=2,這樣就消除了大矩陣的求逆運算,因此可以大大提高運算效率.綜合以上討論,最小二乘支持向量增量學(xué)習(xí)算法如下:(1)初始化:t=2;(2)計算U(2),b(2),α(2),t=3;(3)采集新數(shù)據(jù)(xt,yt),用式(18)計算U(t);(4)計算b(t),a(t),y(x,t);(5)t←t+1,goto(3).實際上增量式學(xué)習(xí)算法也可以當(dāng)作離線學(xué)習(xí)算法來用,這種離線學(xué)習(xí)方法并不像批量式學(xué)習(xí)方法那樣一次注入所有的訓(xùn)練樣本,而是在每次迭代過程中增加一個樣本,最后一次迭代中才包括所有的樣本,這樣可以充分利用前一次迭代的運算結(jié)果,減少離線學(xué)習(xí)算法的計算復(fù)雜性.增量式學(xué)習(xí)方法雖然可以用作在線學(xué)習(xí)算法,但是這種增量式學(xué)習(xí)方法是有缺點的,一是它考慮所有的歷史數(shù)據(jù),沒有遺忘機(jī)制;二是當(dāng)樣本增加到較多時,需要保存很多的樣本,計算復(fù)雜性較大,對在線學(xué)習(xí)來說計算負(fù)擔(dān)較重.因此,針對這個問題,下面將設(shè)計出具有遺忘機(jī)制的真正意義上的在線式學(xué)習(xí)算法.4基于核函數(shù)的向量學(xué)習(xí)算法對于在線學(xué)習(xí)來講,樣本是窗式移動的,即樣本{(xi,yi)}i=t+l-1i=t隨著時刻t的遞進(jìn)而翻滾,進(jìn)來一個新樣本,同時丟掉一個舊樣本,個數(shù)不變.學(xué)習(xí)的樣本集可以表示為{x(t),y(t)},其中x(t)=[xt,xt+1,…,xt+l-1],y(t)=(yt,yt+1,…,yt+l-1)T,xt∈Rn,yt∈R,l為窗口長度.和增量式學(xué)習(xí)類似,核函數(shù)矩陣Q、待求的Lagrange乘子α和常值偏差b都是t的函數(shù),表示如下:最小二乘支持向量機(jī)的輸出式(5)變?yōu)樵O(shè)H(t)=Qt+C-1I,則式(4)可以改寫為這里應(yīng)該注意的是,雖然本節(jié)的α(t),b(t),H(t)和上一節(jié)的對應(yīng)參數(shù)有相同的字母表達(dá)形式,但是其內(nèi)部元素的個數(shù)和內(nèi)容是不一樣的.和上一節(jié)的求解方法一樣,可以求得其中U(t)=H(t)-1.和增量式算法遇到的問題一樣,從式(21),(22)可以看出,為了求出α(t)、b(t),關(guān)鍵點在于求出H(t)的逆U(t).在t時刻,核函數(shù)矩陣Qt是l×l的方陣:則H(t)也是l×l的方陣:其中f(t)是一個標(biāo)量,F(t)是(l-1)維列向量,W(t)是一個(l-1)×(l-1)維的方陣.在t+1時刻,新樣本(xt+l,yt+l)加進(jìn)來,舊樣本(xt,yt)被拋棄掉,核函數(shù)矩陣Qt+1變?yōu)閯tH(t+1)也是l×l的方陣:其中v(t+1)=k(xt+l,xt+l)+1/C?V(t+1)=[k(xt+l,xt+1),?,k(xt+l,xt+l-1)]Τ.利用式(17)來計算U(t)、U(t+1),可得U(t)=Η(t)-1=[f(t)F(t)ΤF(t)W(t)]-1=[000W(t)-1]+r2(t)r2(t)Τz2(t)(23)U(t+1)=Η(t+1)-1=[W(t)V(t+1)V(t+1)Τv(t+1)]-1=[W(t)-1000]+r3(t+1)r3(t+1)Τz3(t+1)(24)其中r2(t)=(-1,F(t)ΤW(t)-1)Τ?z2(t)=1f(t)-F(t)ΤW(t)-1F(t)?r3(t+1)=(V(t+1)ΤW(t)-1,-1)Τ?z3(t+1)=1v(t+1)-V(t+1)ΤW(t)-1V(t+1)?f(t)∈R,F(t)∈Rl-1是由于樣本集窗式移動而刪除的樣本所形成的核函數(shù)元素和向量,v(t+1)∈R,V(t+1)∈Rl-1是由于樣本集窗式移動而新增加的樣本所形成的核函數(shù)元素和向量.式(24)含有兩項,第一項是t步數(shù)據(jù)組成的W(t)-1,第二項是t+1步新數(shù)據(jù)所組成的更新項:r3(t+1)r3(t+1)Tz3(t+1),可以看出為了求U(t+1),關(guān)鍵在于求解W(t)-1.下面利用U(t)的值來求W(t)-1.把式(23)重寫如下:U(t)=[000W(t)-1]+[1z2(t)-Η(t)ΤW(t)-1z2(t)-W(t)-1F(t)z2(t)W(t)-1F(t)F(t)ΤW(t)-1z2(t)](25)觀察式(25),可以看出如果U(t)已知,根據(jù)U(t)對角線的第一個元素可以求出1z2(t),根據(jù)U(t)的第一行元素可以求出行向量Ο1(t)=-F(t)ΤW(t)-1z2(t)的值,根據(jù)W(t)的第一列元素可以求出列向量的值,這樣可以求出由式(25)可知,W(t)-1的值等于把U(t)去掉第一行和第一列后所形成的矩陣再減去O3(t),這樣就可以由U(t)求得W(t)-1的值.求出W(t)-1后根據(jù)式(24)可求出U(t+1),于是就完成了用U(t)值來求U(t+1)的遞推計算,這樣做的好處是能利用前一次的計算結(jié)果來求逆,不必直接求逆,從而使學(xué)習(xí)算法減少計算復(fù)雜度.綜合以上討論,完整的最小二乘支持向量機(jī)在線學(xué)習(xí)算法如下:(1)初始化:t+1;(2)求W(1)-1或任意初始化W(1)-1,t=2;(3)采取新數(shù)據(jù)(x(t),y(t)),用式(24)計算U(t);(4)計算b(t),a(t),y(x,t);(5)用式(25)計算出W(t)-1;(6)t←t+1,goto(3).5基于lssvm的在線式學(xué)習(xí)算法仿真考察本文提出的學(xué)習(xí)算法對混沌信號的學(xué)習(xí)能力.Duffing方程:˙x1=x2,˙x2=-p1x1-p2x2-x31+qcos(wt1),在p1=-1.1,p2=0.4,q=1.6,w=1.8時產(chǎn)生混沌動力學(xué)行為,這里t1是表示時間的連續(xù)變量.對Duffing方程離散化,可得定性的方程表達(dá)式:因此可以構(gòu)造學(xué)習(xí)樣本:xt=(x2(t-1),x1(t-1),t1(t)),yt=x2(t).首先仿真研究增量式算法,利用樣本對(xt,yt)組成樣本集(xt,yt)Νt=1,N為樣本數(shù),然后利用樣本集去訓(xùn)練增量式算法.這里我們把提出的增量式學(xué)習(xí)算法當(dāng)作離線學(xué)習(xí)算法來用,這種離線學(xué)習(xí)方法并不像批量式學(xué)習(xí)方法那樣一次注入所有的訓(xùn)練樣本,而是在每次迭代過程中增加一個樣本,最后一次迭代中才包括所有的樣本,這樣可以充分利用前一次迭代的運算結(jié)果,減少離線學(xué)習(xí)算法的計算復(fù)雜性.在仿真中把本文提出的LSSVM增量式學(xué)習(xí)算法和基于直接求逆的LSSVM學(xué)習(xí)方法進(jìn)行比較,所得到的仿真結(jié)果如表1所示.從仿真結(jié)果可以看出,兩種算法的學(xué)習(xí)精度差不多,而運行時間相差很大,本文提出的增量式算法要比直接求逆法快得多.下面仿真研究在線式學(xué)習(xí)算法,利用樣本對(xt,yt)組成窗式樣本集,選窗口的長度為2,即x(t)=[xt,xt-1],y(t)=(yt,yt-1)T,t=1,2…,然后利用樣本集去訓(xùn)練在線式算法.在仿真中比較本文提出的LSSVM的在線式學(xué)習(xí)算法和