RLS字典學(xué)習(xí)中遺忘因子的影響

余付平， 馮有前， 雷 騰， 李 哲

1.空軍工程大學(xué)，西安710051

2.中國人民解放軍94559部隊，江蘇徐州221000

近年來，信號稀疏分解已成為熱點問題，并廣泛應(yīng)用于壓縮感知[1]、圖像處理[2-6]、信號去噪[6]、特征提取[7-8]等領(lǐng)域.其中，JPEG2000編碼標準的成功也是由于自然圖像的小波系數(shù)具有稀疏性.然而，信號稀疏分解的實現(xiàn)是一個難題，而過完備字典的構(gòu)造是信號能否實現(xiàn)稀疏分解的關(guān)鍵因素.

目前，關(guān)于字典構(gòu)造一般分為兩大類：根據(jù)一定的先驗知識構(gòu)造固定的字典[4-5,9]；當(dāng)沒有先驗知識或先驗知識不足時，由樣本訓(xùn)練的方法學(xué)習(xí)得到自適應(yīng)的字典[2,7,10-11]. 字典學(xué)習(xí)方法主要包括最優(yōu)方向法[12](method of optimal directions,MOD)、K奇異值分解(K singular value decomposition,KSVD)[3,11]、最大后驗概率逼近(maximum A-posterior probability,MAP)方法[3,11]等.其中，MOD方法簡單，但不適合處理大量數(shù)據(jù)；MAP方法在精確稀疏分解中能獲得更好的恢復(fù)結(jié)果；KSVD方法在圖像處理中得到了較好的效果，然而這些方法均受到初始字典較大的影響.為減小初始字典的影響，獲得更好的字典，文獻[10]提出了遞歸最小二乘(recursive least squares,RLS)字典學(xué)習(xí)方法.

1 稀疏分解理論

或者

式中，‖·‖0表示向量中非零元素的數(shù)目.然而，上述問題的求解是一個NP難題.為了解決這個問題，許多稀疏分解算法被提出[14]，如匹配追蹤(matching pursuit,MP)算法、基追蹤(basis pursuit,BP)算法、框架方法(method of frames,MOF)和最優(yōu)正交基(basis orthogonal best,BOB)算法.

2 RLS字典學(xué)習(xí)

2.1 字典學(xué)習(xí)的基本思路

給定一系列訓(xùn)練信號{yi,i=1,2,···,N}組成矩陣Y，訓(xùn)練信號yi在字典D上的分解系數(shù)表示為xi，則稀疏表示系數(shù)矩陣X={xi,i=1,2,···,N}，于是Y在字典D上的稀疏分解問題表示為

或者

字典學(xué)習(xí)通過一系列訓(xùn)練數(shù)據(jù)學(xué)習(xí)訓(xùn)練一個字典，使得訓(xùn)練信號在該字典上總體表示誤差最小，從而使得訓(xùn)練得到的字典能夠更好地適應(yīng)所要解決的問題.因此，對于訓(xùn)練信號Y，尋找可能的最優(yōu)字典的問題可以表示為

或者

本文根據(jù)式(6)分析字典學(xué)習(xí)問題，從而將字典學(xué)習(xí)問題轉(zhuǎn)化為總體誤差的最小化問題.針對一系列訓(xùn)練信號的字典學(xué)習(xí)主要包括兩個步驟[10]：

步驟1 對于固定的字典D，求解使得總體誤差R最小的分解系數(shù)X；

步驟2 根據(jù)求解的系數(shù)X，求解使得總體誤差R最小的字典D.

2.2 引入遺忘因子w的RLS字典學(xué)習(xí)

固定分解系數(shù)X，求解R關(guān)于字典D的導(dǎo)數(shù)，使得總體誤差最小，從而得到字典D的更新公式

式(7)的字典更新方法被稱為最優(yōu)方向法(method of optimal directions,MOD).

當(dāng)一個新的訓(xùn)練信號出現(xiàn)時，RLS方法均會更新字典.因此，這個算法首先假定已經(jīng)存在i個訓(xùn)練信號，當(dāng)?shù)趇+1個信號出現(xiàn)時，尋找新的字典更新公式.

假定Yi=[y1,y2,···,yi]，且矩陣大小為N×i，對應(yīng)的分解系數(shù)Xi=[x1,x2,···,xi]，大小為K×i.根據(jù)式(7)得到

式中

當(dāng)新的訓(xùn)練信號y=yi+1出現(xiàn)時，y在字典Di上的分解系數(shù)x=xi+1.根據(jù)式(8)得到

式中根據(jù)式(12)和(13)得到

定義向量μ=Cix和尺度則

由式(17)可以看出，字典的更新受到表達誤差r的影響.由上述分析可以看出，由于RLS方法在初始迭代時選取的初始字典難以準確反映樣本信息，訓(xùn)練樣本對應(yīng)的表達誤差r較大，可信度較低；隨著新的訓(xùn)練樣本的出現(xiàn)，字典逐步得到更新，于是對訓(xùn)練樣本的表達效果也越好，新樣本的表達誤差r會較小，可信度較高.為了減小初始迭代階段表達誤差較大的影響，對初始階段的表達誤差乘以較小的遺忘因子.隨著表達誤差的減小，遺忘因子應(yīng)該逐漸增大，則引入遺忘因子w的訓(xùn)練信號總體誤差表示為

式中

由式(18)可以看出，初始訓(xùn)練樣本的表達誤差乘以較小的遺忘因子，隨著樣本的增加，遺忘因子逐漸變大.然而字典更新的實際過程為：初始字典對訓(xùn)練樣本的表達效果有限，隨著樣本的增加以及字典的更新，更新字典對樣本的表達能力更強，表達效果更好.為了減小初始字典對訓(xùn)練樣本表達效果的影響，對不同訓(xùn)練樣本的表達誤差乘以不同的遺忘因子，使得初始訓(xùn)練樣本的表達誤差得到較小的信任度，隨著新樣本的引入，新樣本的表達誤差得到較大的信任度.引入遺忘因子后的上述情況與字典更新的實際情形更相符.同時，由于引入遺忘因子，初始樣本對總體誤差的貢獻被消弱，所受到的初始字典的影響被消弱，字典更新過程能夠更快地達到穩(wěn)定.

根據(jù)式(18)可知，當(dāng)遺忘因子取較小值時，樣本表達誤差大大消弱，但也影響樣本本身信息的表達；而當(dāng)遺忘因子取較大值時，樣本信息得到充分表達，但樣本誤差也被充分體現(xiàn)，于是會影響字典學(xué)習(xí)效果.因此，需要選取合適的遺忘因子.引入遺忘因子后的RLS方法的字典更新公式為[10]

式中

尺度

3 仿真結(jié)果

由MATLAB仿真隨機生成大小為20×50的初始字典，且字典的每一列均被歸一化.隨機生成訓(xùn)練數(shù)據(jù)庫，大小為20×1 500，且具有稀疏性.從誤差、字典距離、恢復(fù)比率、運行時間等衡量指標出發(fā)，研究不同方法的字典更新效果以及在RLS方法中遺忘因子對更新結(jié)果的影響.其中，誤差為訓(xùn)練數(shù)據(jù)與重構(gòu)數(shù)據(jù)之間差值的平方和；字典距離為學(xué)習(xí)字典列向量與真實字典列向量之間元素平方和的最小值；恢復(fù)比率表示每次迭代時字典距離大于0.99的原子數(shù)目；字典相似性表示更新字典與真實字典積矩陣的對角元素之和.

3.1 不同字典更新方法的仿真結(jié)果分析

通過200次迭代運算，得到如圖1和2所示的仿真結(jié)果.圖1給出了不同迭代次數(shù)時3種不同方法的表達誤差.從圖1中可以看出，隨著迭代次數(shù)的增加，誤差均下降.其中，KSVD和MOD方法表達誤差下降的速度相近，且在迭代50次之后下降緩慢，接近穩(wěn)定；RLS方法字典下降速度較快，且整體的誤差均小于前兩種方法，表達效果更好.圖2給出了迭代次數(shù)與字典距離之間的關(guān)系.從圖2中可以得到，隨著迭代次數(shù)的增加，KSVD和MOD方法得到的更新字典與真實字典之間的距離逐漸下降，且兩者的變化規(guī)律和大小比較接近.而隨著迭代次數(shù)的增加，RLS方法得到的字典與真實字典之間的距離迅速減小，且每次迭代的距離值均小于KSVD和MOD方法的距離值.因此，RLS方法得到的字典與真實字典更相似，且對訓(xùn)練數(shù)據(jù)的重構(gòu)表達效果更好.表1對比了3種不同字典更新方法的總恢復(fù)比率、字典相似性和運行時間.從表1中可以看出，RLS字典更新方法在總的恢復(fù)比率和字典相似性方面均優(yōu)于KSVD和MOD方法.KSVD方法總體的運行時間最長，而MOD方法運行時間最短.

圖1 分解誤差隨迭代次數(shù)的變化Figure 1 Decomposition errors variation with number of iterations

圖2 不同迭代次數(shù)下的字典距離Figure 2 Dictionary distances of different number of iterations

綜上所述，通過RLS字典學(xué)習(xí)方法得到的學(xué)習(xí)字典與真實字典更相似，與訓(xùn)練數(shù)據(jù)之間的相關(guān)性更強，表達訓(xùn)練樣本的效果更好.

表1 3種字典學(xué)習(xí)方法的指標結(jié)果Table 1 Results of the indicators of three dictionary learning methods

3.2 不同遺忘因子的仿真結(jié)果分析

由于RLS方法在很多方面均優(yōu)于KSVD和MOD方法，接下來主要討論RLS方法.為分析RLS方法中不同遺忘因子對字典更新結(jié)果的影響，分別對固定遺忘因子和函數(shù)變量遺忘因子進行仿真.

3.2.1 固定遺忘因子的仿真結(jié)果

圖3給出了遺忘因子取不同的固定值時分解誤差隨迭代次數(shù)的變化趨勢.從圖3中可以看出，隨著迭代次數(shù)的增加，不同遺忘因子對應(yīng)的誤差均下降.遺忘因子w為0.995、0.990、0.985時誤差下降得較快，且均明顯優(yōu)于遺忘因子w為1.000時的結(jié)果.當(dāng)遺忘因子w為0.990、0.985時，誤差變化趨勢相近，但遺忘因子w為0.990時誤差變化較平滑，抖動較小.圖4給出了遺忘因子取不同的固定值時字典距離隨迭代次數(shù)的變化趨勢.對比圖3和4可以看出，相同的遺忘因子對應(yīng)的誤差變化趨勢與字典距離變化趨勢相同.當(dāng)遺忘因子w為0.990時，字典距離變化較快，且抖動較小.

表2對比了200次迭代后不同遺忘因子更新字典時的總恢復(fù)比率、字典相似性以及運行時間.從表2中可以看出，當(dāng)遺忘因子w為0.990時，總的字典恢復(fù)比率以及字典相似性最大，更新字典與真實字典之間最相近，遺忘因子不同時運行時間差別很小.

圖3 分解誤差隨迭代次數(shù)的變化Figure 3 Decomposition errors variation with number of iterations

圖4 字典距離隨迭代次數(shù)的變化Figure 4 Dictionary distances of different number of iterations

表2 不同遺忘因子的指標結(jié)果Table 2 Results of the indicators of different forgetting factors

由以上分析可以得到，在RLS字典更新中，引入遺忘因子的字典更新效果優(yōu)于遺忘因子恒等于1.000時的結(jié)果.同時，字典更新效果既不隨遺忘因子的減小而變得更好，也不隨遺忘因子的增加而變得更好，而是在遺忘因子w取0.990附近時相對較好.

3.2.2 遺忘因子為函數(shù)變量時的仿真結(jié)果

為了研究遺忘因子為函數(shù)變量時對字典更新結(jié)果的影響，分析了遺忘因子函數(shù)為w2=1-(1-0.990 )×(1-i/200)3、w3=1-0.08×0.2(i0.3)、w4=1-0.08×0.2(i0.4)時對應(yīng)的仿真結(jié)果，并與w1=1時的結(jié)果進行對比.

圖5和6分別給出了遺忘因子函數(shù)對應(yīng)的分解誤差以及字典距離隨迭代次數(shù)的變化曲線.從圖5和6中可以看出，當(dāng)遺忘因子函數(shù)為w3和w4時，誤差和字典距離的變化規(guī)律與w1=1時相似；當(dāng)遺忘因子函數(shù)為w2時，誤差和字典距離均優(yōu)于遺忘因子函數(shù)為w3和w4時的結(jié)果，且經(jīng)100次迭代后的誤差值和字典距離變化幅度較大，幾乎達到恒定.函數(shù)w3和w4曲率較大，而遺忘因子函數(shù)w2從0.990逐漸變化到1.000，從而說明函數(shù)值的變化曲率影響字典學(xué)習(xí)效果.

表3對比了3種遺忘因子取不同函數(shù)時的衡量指標.從表3中可以看出，選取不同函數(shù)時的運行時間差別很小；當(dāng)函數(shù)為w2、w4時，字典相似性和總恢復(fù)比率較好.通過以上的分析可以看出，當(dāng)遺忘因子為函數(shù)w2時，字典更新的總體衡量指標相對較好，與真實字典的相似性更強.

表3 遺忘因子為不同函數(shù)時的指標結(jié)果Table 3 Results of the indicators with different functions of the forgetting factor

圖5 分解誤差隨迭代次數(shù)的變化Figure 5 Decomposition errors variation with number of iterations

圖6 字典距離隨迭代次數(shù)的變化Figure 6 Dictionary distances of different number of iterations

3.2.3 遺忘因子函數(shù)取不同圓周函數(shù)時的仿真結(jié)果

為了研究與3.2.2中函數(shù)w2類似的不同圓周函數(shù)的字典更新效果，分別分析了遺忘因子取3種不同曲度的圓周函數(shù)時的各種字典更新效果的指標.3種不同曲度圓周函數(shù)曲線為：w1=1-(1-0.990)×(1-i/200)3、w2=1-(1-0.990)×(1-i/100)3、w3=3-(1-0.990)×(1-i/250)3.

經(jīng)過200次循環(huán)迭代，得到了遺忘因子取3種不同曲率圓周函數(shù)時對應(yīng)的誤差曲線和字典距離曲線，如圖7和8所示.分析圖7和8可以得出，3種函數(shù)對應(yīng)的誤差和距離的變化趨勢幾乎相同，差別很?。缓瘮?shù)w3對應(yīng)的誤差下降速度在迭代次數(shù)100次附近加快，收斂效果稍好.當(dāng)遺忘因子函數(shù)的曲率在一定范圍內(nèi)時，字典更新效果差別不大.表4對比了遺忘因子取不同圓周函數(shù)時的3種衡量指標.從表4中可以看出，取不同函數(shù)時的運行時間差別很小；在字典相似性和總恢復(fù)比率方面，遺忘因子為函數(shù)w3時結(jié)果較好.

圖7 分解誤差隨迭代次數(shù)的變化Figure 7 Decomposition errors variation with number of iterations

圖8 字典距離隨迭代次數(shù)的變化Figure 8 Dictionary distances of different number of iterations

由以上分析可以看出，遺忘因子取圓周函數(shù)w3時的字典學(xué)習(xí)總體衡量指標相對較好，字典學(xué)習(xí)效果更好，與真實字典更相似.

3.2.4 遺忘因子為逆退火閥值函數(shù)時的仿真結(jié)果

為了進一步研究RLS字典更新方法中遺忘因子對字典更新結(jié)果的影響，尋找合適的遺忘因子，取遺忘因子函數(shù)為不同逆退火閥值函數(shù)w1=1-(1-0.990)×(1-i/200)3、w2=1-0.08×0.5(i0.4)、w3=1-0.08×0.5(i0.3)、w4=1-0.04×0.8(i0.6)、w5=1-0.04×0.8(i0.5)、w6=1-0.04×0.8(i0.4)，并分析不同逆退火閥值函數(shù)字典更新的效果.

圖9和10分別給出了不同逆退火閥值函數(shù)對應(yīng)的分解誤差以及字典距離隨迭代次數(shù)的變化曲線.從圖9和10中可以看出，遺忘因子取不同逆退火閥值函數(shù)對分解誤差和字典距離的影響不大.表5列出了遺忘因子取不同逆退火閥值函數(shù)時對應(yīng)的3種衡量指標.從表5中可以看出，不同逆退火閥值函數(shù)的運行時間略有差別；函數(shù)為w5時的字典相似性和總恢復(fù)比率較好，且運行時間為899.922 s，相對較小.由此可知，不同的逆退火閥值函數(shù)會對字典學(xué)習(xí)結(jié)果產(chǎn)生影響，但影響較小.

表4 不同圓周函數(shù)的指標結(jié)果Table 4 Results of the indicators of different cycle functions

圖9 分解誤差隨迭代次數(shù)的變化Figure 9 Decomposition errors variation with number of iterations

表5 遺忘因子為逆退火閥值函數(shù)時的指標結(jié)果Table 5 Results of the indicators with different annealing threshold functions of the forgetting factor

圖10 字典距離隨迭代次數(shù)的變化Figure 10 Dictionary distances of different number of iterations

4 結(jié)語

RLS字典學(xué)習(xí)方法與KSVD、MOD字典學(xué)習(xí)方法相比，學(xué)習(xí)字典與訓(xùn)練數(shù)據(jù)之間的相似性更強，更能反映訓(xùn)練數(shù)據(jù)的信息，減小了初始字典對學(xué)習(xí)字典的影響.在RLS方法中，當(dāng)遺忘因子w在一定范圍內(nèi)取固定值時的字典學(xué)習(xí)效果較好，本文中的w為0.990時字典學(xué)習(xí)效果較好；遺忘因子為函數(shù)變量時的字典學(xué)習(xí)效果優(yōu)于固定值時的字典學(xué)習(xí)效果.而對于不同的遺忘因子函數(shù)，當(dāng)遺忘因子函數(shù)是曲率在一定范圍內(nèi)的圓周函數(shù)時，字典學(xué)習(xí)效果較好.當(dāng)遺忘因子函數(shù)為逆退火閥值函數(shù)時，學(xué)習(xí)字典與遺忘因子為圓周函數(shù)時的學(xué)習(xí)字典之間的差別很??；同時，不同逆退火閥值函數(shù)對學(xué)習(xí)字典的結(jié)果影響較小.仿真結(jié)果與理論分析一致.

[1]焦李成，楊淑媛，劉芳，侯彪.壓縮感知回顧與展望[J].電子學(xué)報，2011,39(7):1651-1662.JIAOLicheng,YANGShuyuan,LIUFang,HOU Biao.Development and prospect of compressive sensing[J].Acta Electronica Sinica,2011,39(7):1651-1662.(in Chinese)

[2]SKRETTING K,ENGAN K.Image compression using learned dictionariesby RLS-DLA and compared with K-SVD[C]//Proceedings of IEEE International Conferenceon Acoustics,Speech,Signal Process Pargue,Czech Republic,2011:1517-1520.

[3]ELADM.Sparse and redundant representations from theory to applications in signal and image processing[D].New York:Springer,2010.

[4]鄧承志，曹漢強.多尺度脊波字典的構(gòu)造及其在圖像編碼中的應(yīng)用[J].中國圖象圖形學(xué)報，2009,14(7):1273-1278.DENG Chengzhi,CAO Hanqiang.Construction of multi-scale ridgelet dictionary and its application for imagecoding[J].China Journal of Image and Graphics,2009,14(7):1273-1278.(in Chinese)

[5]孫玉寶，肖亮，韋志輝，邵文澤.基于Gabor感知多成份字典的圖像稀疏表示算法研究[J].自動化學(xué)報，2008,34(11):1379-1387.SUN Yubao,XIAO Liang,WEI Zhihui,SHAO Wenze.Sparse representations of images by a multicomponent Gabor perception dictionary[J].Acta Automatica Sinica,2008,34(11):1379-1387.(in Chinese)

[6]SHEN Bin,HU Wei,ZHANG Yimin,ZHANG Yujin.Image inpainting via sparse representation[C]//Proceedings IEEE International Conference on Acoustics,Speech,Signal Process.Taiwan,2009:697-700.

[7]劉金江，王春光，孫即祥.基于稀疏分解和神經(jīng)網(wǎng)絡(luò)的心電信號波形檢測即識別[J].信號處理，2011,27(6):843-850.LIU Jinjiang,WANG Chunguang,SUN Jixiang.The detection and recognition of electrocardiogram's waveform based on sparse decomposition and neural network[J].Signal Processing,2011,27(6):843-850.(in Chinese)

[8]楊清山，郭成安，金明錄.基于Gabor多通道加權(quán)優(yōu)化與稀疏表征的人臉識別方法[J].電子與信息學(xué)報，2011,33(7):1618-1624.YANG Qingshan,GUO Cheng'an,JIN Minglu.Face recognition based on Gabor multi-channel weighted optimization and sparserepresentation[J].Journal of Electronics&Information Technology,2011,33(7):1618-1624.(in Chinese)

[9]彭富強，于德介，劉堅.一種基于多尺度線調(diào)頻基的稀疏信號分解方法[J].振動工程學(xué)報，2010,23(3):333-338.PENG Fuqiang，YU Dejie，LIU Jian.Sparse signal decomposition method based on multi-scale chirplet[J].Journal of Vibration Engineering,2010,23(3):333-338.(in Chinese)

[10]SKRETTINGK,ENGANK.Recursiveleast squaresdictionary learning algorithm[J].IEEE Transactions on Signal Processing,2010,58(4):2121-2130.

[11]AHARON M,ELAD M,BRUCKSTEIN A.K-SVD:an algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing,2006,54(11):4311-4322.

[12]ENGANK,AASESO,HUSOYJ H.Method of optimal directions for frame design[C]//Proceedings IEEE International Conference on Acoustics,Speech,Signal Process,1999:2443-2446.

[13]JAFARIM G,PLUMBLEY M D.Fast dictionary learning for sparse representations of speech signals[J].IEEE Journal of Selected Topic in Signal Processing,2011,5(5):1025-1031.

[14]HYDER M M,MAHATA K.An improved smoothed l0approximation algorithm for sparse representation[J].IEEE Transactions on Signal Processing,2010,58(4):2194-2205.