一種在線稀疏LSSVM及其在系統建模中的應用

摘要:為了減少在線最小二乘支持向量機(LSSVM)的計算量和存儲空間，提出了一種在線稀疏LSSVM.這種LSSVM利用滑動時間窗中部分時刻的樣本作為訓練樣本集.新時刻的樣本總是加入訓練樣本集;每次刪除樣本時，若滑動時間窗最前端時刻的樣本在訓練樣本集中，則刪除它，否則從訓練樣本集中選擇留一法預測誤差最小的樣本刪除.與現有的在線LSSVM相比，這種在線稀疏LSSVM能用較少的樣本學習系統較多的特性，能提高時空效率;與現有的在線稀疏LSSVM相比，它能擺脫陳舊樣本的影響，更加適應系統的時變性.系統建模仿真實驗表明，該在線稀疏LSSVM能節省時間和空間，具有較高的預測精度.

關鍵詞:最小二乘支持向量機;學習算法;稀疏性;選擇性刪除;系統建模

中圖分類號:TP18，TP273文獻標識碼:A

AnOnlineSparseLSSVMandItsApplicationinSystemModeling

ZHOUXinran1，2，TENGZhaosheng1

(1.CollegeofElectricalandInformationEngineering，HunanUniv，Changsha，Hunan410082，China;

2.SchoolofInformationScienceandEngineering，CentralSouthUniv，Changsha，Hunan410075，China)

Abstract:Toreducethecomputationtimeandthestoragespaceofonlineleastsquaressupportvectormachine(LSSVM)，anonlinesparseLSSVMwasproposed.ThisLSSVMonlytakessamplesatpartialmomentsamongslidingtimewindowastrainingsamplesset(TSS).Thenewsampleislearnednecessarily.Whensampleeliminationisperformed，ifthesampleattheoldestmomentamongslidingtimewindowexistsinTSS，itwillberemovedduringdecrementallearning.Otherwise，thesamplewiththesmallestleaveoneoutpredictingerroramongTSSisselectedanddeleted.ComparedwiththeexistingonlineLSSVM，theproposedonlinesparseLSSVMcanlearnmorecharacteristicofthesystemwithfewersamples，andheightentimespaceefficiency.ComparedwiththeexistingonlinespareLSSVM，itcangetridoftheobsoletesample，andbetteradapttotimevariantpropertiesofsystem.NumericalsimulationresultsforsystemmodelinghaveshownthattheproposedonlinesparseLSSVMcansavetimeandspace，andprovideaccuratepredictions.

Keywords:leastsquaressupportvectormachine(LSSVM);learningalgorithms;sparsity;selectivedeletion;systemmodelling

最小二乘支持向量機用等式約束代替支持向量機[1-3]的不等式約束，因此其求解問題就變成一個線性方程組求解問題，這比支持向量機訓練中受約束的二次規劃問題求解運算量減少許多.為將LSSVM用于系統在線建模，文獻[4-5]設計了LSSVM在線式學習算法，用滑動時間窗中的所有樣本訓練LSSVM，這類方法的優點是模型能及時反映系統的特性，但當滑動時間窗較長時，在線學習和預測計算量較大，而且要存儲一個較大的矩陣(下文的H-1N);文獻[6-7]設計了在線稀疏LSSVM，這類方法提高了時空效率，但這類方法不一定會將較老樣本刪除，對于時變系統或工作點移動系統而言，較老樣本不僅不能反映系統當前特性，還對LSSVM泛化精度有負作用.本文結合上面兩類方法的優點，設計一種能及時捕捉系統特性的在線稀疏LSSVM.該方法在每一采樣時刻獲得新樣本后總是學習新樣本，刪除樣本時首先看滑動時間窗最前端時刻的樣本是否存在，若在則刪除它，否則在已學習的樣本中挑出一個留一(LeaveOneOut，LOO)交叉驗證預報誤差[8]最小的樣本刪除;因此本文方法是采用滑動時間窗中的部分樣本訓練LSSVM.該方法運行速度快、占用內存少，預測精度高.

1LSSVM簡介

對于一組輸入樣本序列{(xi，yi)}，i=1，…，N，xi∈Rd，yi∈R，LSSVM利用非線性映射ψ(#8226;):X→F，將輸入數據映射到一個高維特征空間，使輸入空間中的非線性函數估計問題轉化為高維特征空間中的線性函數估計問題，回歸函數形式為:

y(x)=wTψ(x)+b.(1)

根據結構風險最小化原則，并使樣本擬合誤差最小化，回歸問題變為約束優化問題.

minJ(w，e)=12wTw+C2∑Ni=1e2i，

s.t.yi=wTψ(xi)+b+ei，i=1，2，…，N.(2)

C為懲罰因子.為求解上述優化問題，把約束優化問題變成無約束優化問題，建立Lagrange函數:

L(w，b，e，a)=J(w，e)-∑Ni=1ai(wψ(xi)+b+ei-yi).(3)

根據KKT條件，有

Lw=0→w=∑Ni=1aiψ(xi)，Lb=0→∑Ni=1ai=0，Lei=0→ai=Cei，Lai=0→wψ(xi)+b+ei-yi=0.(4)

湖南大學學報(自然科學版)2010年

第4期周欣然等:一種在線稀疏LSSVM及其在系統建模中的應用

消去方程組(4)中ei，w后得線性方程組:

QN+C-1Ie1e10aNb=yN0.(5)

其中:yN=(y1，y2，…，yN)T，e1=(1，1，…，1)T，aN=(a1，a2，…aN)T，QN，ij=(ψ(xi)#8226;ψ(xj))=k(xi，xj)，i，j=1，2，…，N.k(xi，xj)是滿足Mercer條件的核函數，常用的有線性函數、多項式函數、徑向基函數和多層感知函數等，本文取徑向基函數，即

k(xi，xj)=exp(-‖xi-xj‖22/β2).(6)

β>0，稱為核參數;Q稱為核矩陣.

從式(5)解出b，a，回歸函數(1)化為:

y(x)=∑Ni=1aik(xi，x)+b.(7)

2在線稀疏LSSVM

目前LSSVM在線學習算法有基于分塊矩陣求逆公式算法[4]和基于Cholesky分解更新算法的在線學習算法[5]2種，它們都包括增加樣本和刪除樣本2個過程.為了便于計算滑動時間窗中已學樣本的LOO交叉驗證預報誤差，本文采用分塊矩陣求逆公式進行增加樣本和刪除樣本的處理.本文方法在每一采樣時刻都學習新樣本，這與文獻[7]的選擇性學習不同，這樣做是為了及時學習系統的新特性;本文方法在刪除樣本時不像文獻[4-5]方法那樣固定刪除時間窗中最老的樣本，也不像文獻[6]方法只刪除貢獻最小(|ai|最小)樣本，不像文獻[7]方法只刪除LOO交叉驗證預報誤差最小樣本，而是首先看滑動時間窗最前端時刻的樣本是否存在，若在則刪除它，否則再在已學習的樣本中挑出一個LOO交叉驗證預報誤差最小的樣本刪除.這樣做是為了及時刪除老樣本和降低稀疏化給LSSVM帶來的精度損失.

21增加樣本處理

利用N個樣本構造方程(5)后，記HN=QN+C-1I，bN=b，則方程(5)表示為:

HNe1eT10aNbN=yN0.(8)

方程(8)的解為:

bN=eT1H-1NyNeT1H-1Ne1，(9a)

aN=H-1N(yN-e1eT1H-1NyNeT1H-1Ne1)=

H-1N(yN-e1bN).(9b)

由式(9)可知，求bN，aN的時間主要花在計算H-1N.每當新樣本(xN+1，yN+1)加入樣本集時，有

HN+1=QN+1+C-1I=HNVN+1VTN+1vN+1.(10)

其中:VN+1=[k(xN+1，x1)，…，k(xN+1，xN)]T;vN+1=k(xN+1，xN+1)+1/C.利用分塊矩陣求逆公式[4，9]得:

H-1N+1=HNVN+1VTN+1vN+1-1=H-1N+H-1NVN+1ρ-1VTN+1H-1N-H-1NVN+1ρ-1-ρ-1VTN+1H-1Nρ-1.(11)

其中:ρ=vN+1-VTN+1H-1NVN+1.可見不必重新計算H-1N+1，而是利用H-1N遞推計算，從而減少計算量.而且，HN，H-1N是對稱的，每次只計算其上三角部分元素即可.

22LOO預測誤差計算

文獻[8]介紹了一種留一(LeaveOneOut，LOO)預測誤差計算方法，過程如下.

假設已學習了N個樣本，記式(5)的系數矩陣為:

F=QN+C-1Ie1eT10=d11dT1d1F-1.(12)

其中:d11=k(x1，x1)+1/C，d1=[k(x2，x1)，k(x3，x1)，…，k(xi，x1)，…，k(xN，x1)，1]T，F-1表示F劃去第1行、第1列得到的子矩陣.則式(5)可以寫為:

d11dT1d1F-1a1a2aiaNb=y1y2yiyN0.(13)

由式(13)的第1個方程得出式(14)，后N個方程得出式(15).

d11a1+dT1a2，…，ai，…，aN，bT=y1，(14)

d1a1+F-1a2，…，ai，…，aN，bT=

y2，…，yi，…，yN，0T.(15)

若刪除第1個樣本，則利用其余的N-1個樣本得出LSSVM-1N所對應的方程(5)變為:

F-1a-12，…，a-1i，…，a-1N，b-1T=y2，…，yi，…，yN，0T.(16)

利用LSSVM-1N計算y1的估計值，并利用式(14)~(16)得:

1，LSSVM-1N=yLSSVM-1N(x1)=

dT1a-12，…，a-1i，…，a-1N，b-1T=

dT1F-1-1y2，…，yi，…，yN，0T=

dT1F-1-1(d1a1+F-1a2，…，ai，…，aN，bT)=

dT1F-1-1d1a1+dT1a2，…，ai，…，aN，bT=

dT1F-1-1d1a1+y1-d11a1=

y1-a1(d11-dT1F-1-1d1).(17)

對式(12)利用分塊矩陣求逆公式[4，9]得:

F-1=d11dT1d1F-1-1=-1--1dT1F-1-1-F-1-1d1-1F-1-1+F-1-1d1-1dT1F-1-1.(18)

其中=d11-dT1F-1-1d1.顯然，-1就是F-111，由式(17)知第1個樣本的LOO交叉驗證預報誤差為:

eLOO1=y1-1，LSSVM-1N=

a1(d11-dT1F-1-1d1)=a1ρ=a1/F-111.(19)

同時對調方程組(5)的第1個方程和第i個方程位置，未知數a1與ai位置，同樣可推出第i個樣本的LOO交叉驗證預報誤差為:

eLOOi=yi-i，LSSVM-iN=ai/F-1ii，i=2，…，N.(20)

文獻[8]再次對F利用分塊矩陣求逆公式[4，9]得:

F-1=HNe1eT10-1=H-1N+H-1Ne1λ-1eT1H-1N-H-1Ne1λ-1-λ-1eT1H-1Nλ-1.(21)

其中λ=-eT1H-1Ne1.可見

F-1ii=H-1N，ii+s2iλ-1，i=1，…，N.(22)

其中s=eT1H-1N=s1，…si，…sN.故有:

eLOOi=ai/(H-1N，ii+s2iλ-1)，i=1，…，N.(23)

而λ，s和H-1N，ii在計算式(9)的過程中已經算出.23刪除樣本的選擇與處理

設滑動時間窗長度為WL，在其中選擇TL個時刻的樣本作為訓練樣本在線訓練LSSVM，即訓練樣本數量為TL.當N增至TL時，在用所得模型預測后就要去掉一個樣本，此時首先判斷H-1N的第1行(列)對應樣本是否為當前時刻(記為0時刻)之前第WL-1時刻的樣本，若是，則k=1，否則按式(24)計算k.

k=argmin|eLOOi|，i=1，…，N.(24)

(xk，yk)就是要刪除的節點.從HN中刪除第k行(列)所得矩陣記為N-1，則N-1的逆-1N-1從H-1N如下求得[6，10]:

-1N-1=H-1N(I，J)-[H-1N(k，k)]-1#8226;

H-1N(I，k)H-1N(k，J).(25)

其中I，J=[1，…，k-1，k+1，…，N].-1N-1是對稱的，只計算其上三角部分元素即可.將N-1，-1N-1分別看做新的HN，H-1N，又可進行后續的學習和預測.

24在線稀疏LSSVM的完整學習算法

1)設定無偏LSSVM的核函數及有關參數、滑動時間窗長度WL和訓練樣本數TL的值.

2)在線學習初始的TL個樣本:若當前訓練樣本數N為1，則H-11=1/[k(x1，x1)+1/C]，否則利用式(11)增加樣本更新算法求H-1N，其間獲得2個樣本，即N≥2后就可用式(9)解出模型(7)用于預測.

3)在線學習滑動時間窗中的TL個樣本并預測:

①按2.3節挑選要刪除的樣本并處理;

②接受新樣本并學習，即用式(9)，(11)解出模型(7);③用新模型進行預測.

4)轉向3)進行下一時刻的學習和預測.

3基于在線稀疏LSSVM的系統建模仿真及分析

為檢測本文在線稀疏LSSVM算法的效果，下面利用它對時不變和時變系統模型在線建模預測.設定算法的有關參數:β2=3，C=500，仿真步數SM=654.

仿真系統的輸入信號u1(t)是疊加三角函數波，形式為:

u1(t)=sin(2πt/25)+sin(2πt/50)+sin(2πt/100).

輸入信號u2(t)在仿真時段內周期為50的方波，其第1個周期為:

u2(t)=2，0≤t≤25，0，25

系統S1在仿真時段內是時不變的，其離散形式為:

y(t)=y(t-1)y(t-2)u(t-1)[y(t-3)-1]+u(t-2)1+y2(t-1)+y2(t-2).

系統S2在仿真時段內階段性時變，其離散形式如下:

y(t)=y(t-1)y(t-2)u(t-1)[y(t-3)-1]+u(t-2)1+y2(t-1)+y2(t-2)，t≤150，y(t-1)y(t-2)u(t-1)[y(t-3)-1]+u(t-2)1+y2(t-1)+y2(t-2)+sin(2π(t-150)/50)+(t-150)/300，150

系統S3在仿真時段內持續時變，其離散形式為:

y(t)=y(t-1)y(t-2)u(t-1)[y(t-3)-1]+u(t-2)1+y2(t-1)+y2(t-2)+

2sin(2πt/50).

用文獻[4-5]的在線LSSVM和本文的在線稀疏LSSVM對S1，S2(輸入取u1)在線建模預測，將TL取不同值時的預測均方根誤差RMSE=1SM∑SMi=1(yi-i)2如表1所示.

由表1可知，本文方法在WL=100，TL=25時，預測RMSE與文獻[4-5]方法在WL=TL=100時的RMSE接近.對于文獻[4-5]的在線LSSVM建模而言，有TL=WL，要學習更多時刻的動態特性，必須加大TL和WL，勢必要付出更大的計算代價和存儲空間;對于本文方法而言，要學習更多時刻的動態特性可以通過設置較大的WL實現，但不必學習所有WL時刻的樣本，而只學習其中TL個時刻的樣本，這就節省了計算時間和存儲空間.測得本文方法在WL=100，TL=25時所花時間為1.1116s，而文獻[4]方法在WL=TL=100時所花時間為5.9886s，文獻[5]方法此時所花時間為3.8155s;本文方法需要存儲的矩陣(H-1N)大小為25×25空間單位，而文獻[4-5]方法則為100×100空間單位，前者為后者的1/16.換句話說，本文方法花較少的時空代價，就能獲得與文獻[4-5]方法相近的預測精度.本文方法在WL=TL時的情形就是文獻[4]方法.

下面再利用文獻[4-7]方法和本文方法對上面3個系統分別在線建模預測，各方法的預測均方根誤差RMSE如表2所示，各方法的TL=25.

由表2可以看出，對時不變系統S1建模時，本文方法比文獻[4-6]方法的RMSE要小，而與文獻[7]方法的RMSE相差很小;事實上，本文方法在WL=∞時的情形就是文獻[7]方法在PEB=0時的情形.

對時變系統S2，S3建模時，本文方法比其他方法的RMSE都要小.這是因為本文方法與獻[4-5]方法相比，能用較少的樣本(TL=25)學習較多時刻(WL=100)的特性;與文獻[6-7]的在線稀疏LSSVM建模方法相比，它能將較老的樣本刪除，而文獻[6-7]方法沒有滑動時間窗的概念，學習樣本的個數TL=25，這25個樣本中可能有些很老的樣本，它們可能不能反映時變系統的最新動態特性，對模型學習作用較小或反而有負面影響，因此本文方法比文獻[6-7]方法的RMSE要小.

利用LSSVM在線建模時，除了其固有的超參數需要設定外，還要額外設定滑動時間窗長度或學習樣本數，而目前無理論上的方法，一般憑主觀經驗或試探確定.尤其對時變系統在線建模時如何讓這些參數自適應變化更是困難.這些都是有待繼續研究的問題.

4結論

本文提出了一種在線稀疏LSSVM算法，它用滑動時間窗中部分時刻的樣本作為學習樣本;新時刻的樣本總是加入學習樣本集，每次刪除樣本時，若滑動時間窗最前端時刻的樣本在學習樣本集中，則刪除它，否則從學習樣本集中選擇LOO預測誤差最小的樣本刪除.仿真實驗表明，本文方法能用較少的樣本學習系統較多的特性，能及時學習系統的新特性，又能擺脫陳舊樣本的影響，具有較高的預測精度，適合時變或時不變系統的在線建模.

參考文獻

[1]SUYKENSJAK.Leastsquaressupportvectormachineclassifiers[J].NeuralProcessLetter，1999，9(3):293-299.

[2]SUYKENSJAK.Nonlinearmodelingandsupportvectormachines[C]//IEEEInstrumentationandMeasurementTechnologyConference.Budapest，Hungary:IEEE，2001:287-294.

[3]VAPNIKV.Statisticallearningtheory[M].NewYork:Wiley，1998:443-492.

[4]張浩然，汪曉東.回歸最小二乘支持向量機的增量和在線式學習算法[J].計算機學報，2006，29(3):400-406.

ZHANGHaoran，WANGXiaodong.Incrementalandonlinelearningalgorithmforregressionleastsquaressupportvectormachine[J].ChineseJournalofComputers，2006，29(3):400-406.(InChinese)

[5]蔡艷寧，胡昌華.一種基于Cholesky分解的動態無偏LSSVM學習算法[J].控制與決策，2008，23(12):1363-1367.

CAIYanning，HUChanghua.DynamicnonbiasLSSVMlearningalgorithmbasedonCholeskyfactorization[J].ControlandDecision，2008，23(12):1363-1367.(InChinese)

[6]唐和生，薛松濤，陳镕，等.序貫最小二乘支持向量機的結構系統識別[J].振動工程學報，2006，19(3):382-387.

TANGHesheng，XUESongtao，CHENRong，etal.SequentialLSSVMforstructuralsystemsidentification[J].JournalofVibrationEngineering，2006，19(3):382-387.(InChinese)

[7]劉毅，陳坤，王海清，等.選擇性遞推LSSVR及其在過程建模中的應用[J].高校化學工程學報，2008，6(22):1043-1048.

LIUYi，CHENKun，WANGHaiqing，etal.SelectiverecursiveLSSVRanditsapplicationsinprocessmodeling[J].JournalofChemicalEngineeringofChineseUniversities，2008，6(22):1043-1048.(InChinese)

[8]CAWLEYGC，TALBOTNLC.Preventingoverfittingduringmodelselectionviabayesianregularisationofthehyperparameters[J].JMachLearnRes，2007，8(4):841-861.

[9]毛漢清.可逆矩陣的分塊求逆方法研究[J].上海鐵道學院學報，1994，15(3):110-117.

MAOHanqing.Researchofmethodstoobtainaninversematrixbypartitioninganinversiblematrix[J].JournalofShanghaiInstituteRailwayTechnology，1994，15(3):110-117.

(InChinese)

[10]吳春國.廣義染色體遺傳算法與迭代式最小二乘支持向量機回歸算法研究[D].長春:吉林大學計算機科學與技術學院，2006.

WUChunguo.Studyongeneralizedchromosomegeneticalgorithmanditerativeleastsquaressupportvectormachineregression[D].Changchun:CollegeofComputerScienceandTechnology，JilinUniversity，2006.(InChinese)