2.3.3　字典學(xué)習(xí)算法

典型的字典學(xué)習(xí)算法包括主成分分析（Principal Component Analysis，PCA）、最優(yōu)方向法（Method of Optimal Directions，MOD）[18]、K-均值（K-Means）算法、K-奇異值分解（K-SVD）算法[19]、貪婪自適應(yīng)字典（Greedy Adaptive Dictionary，GAD）[17]等。PCA字典學(xué)習(xí)算法通過低維子空間來(lái)聯(lián)合近似表示訓(xùn)練樣本。MOD算法交替更新字典和分解系數(shù)，有效地得到信號(hào)的冗余字典，但是同時(shí)更新字典和系數(shù)帶來(lái)了較大的構(gòu)造復(fù)雜度。K-SVD算法每次選擇字典中的一列進(jìn)行更新，同時(shí)引入約束矩陣，使得迭代不會(huì)搜索到局部極值。該算法可與眾多稀疏編碼算法相結(jié)合，形成改進(jìn)算法，如短時(shí)不變字典EKSVD[20]等。

除了上述直接從訓(xùn)練樣本中學(xué)習(xí)字典的方法之外，另一種構(gòu)建冗余字典的思想是聯(lián)合冗余，即將多個(gè)字典相合并，直接得到一個(gè)更為冗余的字典。利用聯(lián)合冗余字典得到的稀疏表示具有唯一性，這一點(diǎn)得到了理論證明[21-22]。

下面介紹較為常用的字典學(xué)習(xí)算法：K-均值、K-SVD和GAD算法。

1. K-均值字典學(xué)習(xí)算法

K-均值算法實(shí)現(xiàn)了矢量的聚類，可應(yīng)用于碼書的訓(xùn)練，在矢量量化中應(yīng)用廣泛。對(duì)于給定的一批矢量數(shù)據(jù)，K-均值算法可以實(shí)現(xiàn)基本的按距離聚類，即同一類矢量之間的距離較短，而不同類矢量之間的距離較長(zhǎng)，類內(nèi)距離小于類間距離。整個(gè)聚類過程通過迭代實(shí)現(xiàn)，即利用當(dāng)前聚類結(jié)果，計(jì)算同一類矢量的均值作為聚類質(zhì)心，然后根據(jù)這些質(zhì)心對(duì)所有矢量按距離大小重新聚類，直到迭代收斂或大于規(guī)定次數(shù)時(shí)結(jié)束。當(dāng)聚類完成后，這些質(zhì)心所對(duì)應(yīng)的矢量就是構(gòu)成碼書的碼字。利用碼字序號(hào)可以直接表示屬于該類別的任意矢量，這樣就可以實(shí)現(xiàn)矢量降維和信號(hào)壓縮。

K-均值算法的流程可用算法2-1描述。

算法2-1　K-均值算法

輸入：數(shù)據(jù)集合。

輸出：碼書C。每個(gè)數(shù)據(jù)用碼書中最靠近的碼字來(lái)表示，使得總誤差最小，即

式中，e_l表示第l次迭代所對(duì)應(yīng)的逼近誤差矢量，是數(shù)據(jù)集合對(duì)應(yīng)的稀疏表示集。

1）初始化，令碼書矩陣C（0）∈?n×L，迭代次數(shù)J=1。

2）循環(huán)執(zhí)行步驟3～6：

3）　　稀疏逼近，將數(shù)據(jù)按碼字分為L個(gè)集合（胞腔）

劃分規(guī)則：每個(gè)數(shù)據(jù)域?qū)?yīng)胞腔內(nèi)碼字距離均小于與其余碼字距離，即

4）　　更新碼書中每個(gè)碼字：

5）　　按照每個(gè)數(shù)據(jù)到碼字的最近距離更新S。更新迭代次數(shù)J=J+1。

6）　　停止準(zhǔn)則。若（預(yù)設(shè)誤差門限）則停止，否則返回步驟2。

從信號(hào)稀疏表示的角度分析，K-均值算法學(xué)習(xí)得到的碼書就是一個(gè)字典。基于這個(gè)字典對(duì)任意一個(gè)矢量進(jìn)行量化時(shí)，量化得到的表示矢量都只有一個(gè)元素為1，其他元素均為0。這種表示可看作稀疏度為1的信號(hào)稀疏化，表示誤差較大?？梢钥紤]以提高稀疏值為代價(jià)獲得更逼真的表示。另一方面，K-均值算法采用了全部碼字同時(shí)更新的迭代方式，無(wú)法較好地匹配信號(hào)。

2. K-SVD字典學(xué)習(xí)

K-均值算法學(xué)習(xí)得到的字典，每次只能用一個(gè)原子表示信號(hào)，較為粗糙。為了解決這個(gè)問題，K-SVD算法在借鑒K-均值算法聚類思想的基礎(chǔ)上采用多個(gè)原子的線性組合來(lái)表示信號(hào)，改善了字典學(xué)習(xí)的性能。為了準(zhǔn)確地更新每個(gè)原子，避免像K-均值算法那樣一次更新全部均值，K-SVD算法在迭代中使用奇異值分解（SVD）算法來(lái)選擇每個(gè)原子所對(duì)應(yīng)的更新誤差，并逐個(gè)對(duì)原子進(jìn)行更新。

K-SVD算法流程可用算法2-2描述。

算法2-2　K-SVD算法

輸入：訓(xùn)練樣本，初始字典D。

輸出：最終字典D，稀疏分解系數(shù)S。

1）初始化。隨機(jī)得到初始化字典D，令迭代次數(shù)J=1。

2）循環(huán)直到滿足停止條件：

3）　　稀疏逼近。用已有稀疏分解算法對(duì)所有數(shù)據(jù)求出分解系數(shù)：

4）　　更新字典。對(duì)字典中每列d_l，l=1，2，…，L：

①定義S的第l行為，則該行中所有非零元素使用了原子d_l，這些非零元素的下標(biāo)構(gòu)成的集合為

②計(jì)算當(dāng)前稀疏表示誤差矩陣：

③根據(jù)下標(biāo)集合ω_l從E_l中選出稀疏表示時(shí)用到d_l的列，記為。

④使用SVD算法計(jì)算，更新字典第l列，更新誤差V（:，l）。

5）　　更新迭代次數(shù)J=J+1。

6）　　停止準(zhǔn)則：若≤預(yù)設(shè)誤差門限，則停止；否則返回步驟2。

K-SVD算法每次選擇字典中的一列進(jìn)行更新，同時(shí)引入約束矩陣，使得字典更新過程更加精細(xì)，且不會(huì)陷入局部極值。K-SVD算法是目前學(xué)習(xí)型字典方案中較好的一種，字典對(duì)樣本的適應(yīng)性較強(qiáng)，無(wú)須信號(hào)先驗(yàn)信息即可獲得較好的稀疏化效果。同時(shí)也需要注意，采用學(xué)習(xí)法的字典學(xué)習(xí)過程計(jì)算量大，學(xué)習(xí)過程復(fù)雜。

3. 貪婪自適應(yīng)字典學(xué)習(xí)

K-SVD算法從逼近誤差方面（如式（2-3））約束字典學(xué)習(xí)過程，而貪婪自適應(yīng)字典（Greedy Adaptive Dictionary，GAD）算法以稀疏性（如式（2-4））為約束進(jìn)行字典訓(xùn)練，以期得到盡可能稀疏的信號(hào)表達(dá)，同時(shí)兼顧原子的稀疏性。為了得到最佳的稀疏表示字典，GAD分析每個(gè)（殘差）信號(hào)的稀疏性，每次迭代都優(yōu)先選擇稀疏性最好的（殘差）信號(hào)作為原子。這樣的迭代過程可以快速減少信號(hào)的能量，同時(shí)保證l₁范數(shù)降為最低。

GAD算法的具體流程可用算法2-3描述。

算法2-3　GAD算法

1）初始化：令j=0，初始字典D0=［］（空矩陣），殘差R0=X，下標(biāo)集T0=?（空集）。

2）循環(huán)直到滿足停止條件：

3）　　尋找殘差中稀疏度量最低的列：

4）　　更新原子，即將第j個(gè)原子更新為歸一化的：

5）　　更新字典和下標(biāo)集：

Dj=［Dj-1|dj］，　Tj=Tj-1∪{kj}

6）　　計(jì)算新的誤差：

7）　　更新j=j+1。

8）若滿足停止準(zhǔn)則則停止，否則返回步驟2。

為便于計(jì)算，在該算法中用稀疏度量（sparsity index）來(lái)衡量信號(hào)的稀疏程度：對(duì)于任意矢量x，其稀疏度量定義為

稀疏度量越低，則說明信號(hào)稀疏程度越高。舉例來(lái)說，若有兩個(gè)二維矢量x₁=［1，1］，x₂=［0，1］，x₂更為稀疏。它們的稀疏度量分別為，ξ₂=1/1=1，ξ₁>ξ₂。

另外，需要構(gòu)造原始信號(hào)矩陣X?？蓪⑿盘?hào)按時(shí)序分為長(zhǎng)度為L的矢量x_k，相鄰兩矢量之間有M點(diǎn)重疊：

x_k=［x（（k-1）（L-M）+1），…，x（kL-（K-L）M）］T

（2-8）

再將K個(gè)矢量組合為RL×K維矩陣X：

X（l，k）=x（l+（k-1）（L-M））

（2-9）

GAD算法中的停止條件可靈活選擇如下兩種方式之一：

①獲得L個(gè)原子形成字典方陣，即重復(fù)步驟2～7共L次。

②根據(jù)信號(hào)稀疏逼近重構(gòu)誤差

式中，σ為設(shè)定的誤差門限。重構(gòu)信號(hào)可由當(dāng)前字典得到：