基于圖結(jié)構(gòu)的半監(jiān)督字典學(xué)習(xí)

劉晗宇，王 迪，張 磊，張笑欽

(溫州大學(xué)數(shù)理與電子信息工程學(xué)院，浙江溫州 325035)

近年來(lái)，稀疏編碼大量應(yīng)用于圖像去噪、圖像分類[1]等方面．特別地，Wright等人[2]提出了一種基于稀疏表示的分類方法（SRC），Aharon等人[3]提出了K-SVD算法，這些方法只考慮了字典的稀疏表達(dá)能力而忽略了其判別能力．為了提高字典的判別能力，有關(guān)學(xué)者提出了一些有監(jiān)督的字典學(xué)習(xí)算法，例如Zhang和Li[4]提出了具有判別性的K-SVD算法（D-KSVD），Yang等人[5]提出了 Fisher判別字典學(xué)習(xí)算法（FDDL），Jiang等人[6]提出了類別一致性 K-SVD算法（LC-KSCD），這類算法都是利用樣本的類別信息來(lái)得到一個(gè)有判別能力的字典．有監(jiān)督字典學(xué)習(xí)的性能很大程度上依賴于標(biāo)簽樣本的個(gè)數(shù)，但有標(biāo)簽樣本的獲取是非常困難的，因此利用少量的有標(biāo)簽樣本和大量的無(wú)標(biāo)簽樣本共同訓(xùn)練字典即半監(jiān)督字典學(xué)習(xí)成為了研究重點(diǎn)．Shrivastava等人[7]提出了半監(jiān)督判別性字典學(xué)習(xí)算法（S2D2），Zhang等人[8]提出了一種在線的半監(jiān)督字典學(xué)習(xí)算法（OSSDL）．因?yàn)橐延械陌氡O(jiān)督字典學(xué)習(xí)方法很少考慮無(wú)標(biāo)簽樣本與有標(biāo)簽樣本之間的內(nèi)在結(jié)構(gòu)關(guān)系，無(wú)法將無(wú)標(biāo)簽樣本的潛在類別信息融入到訓(xùn)練過(guò)程中，故字典的判別能力沒(méi)有進(jìn)一步加強(qiáng)．本文提出一種基于圖結(jié)構(gòu)的半監(jiān)督字典學(xué)習(xí)方法（Graph-based Semi-supervised Dictionary Learning，G-SSDL）．具體來(lái)說(shuō)：首先獲得訓(xùn)練樣本之間的稀疏編碼，其體現(xiàn)了樣本之間的相似度信息；然后運(yùn)用特殊標(biāo)簽傳播方法（SLP）[9]獲得訓(xùn)練樣本軟標(biāo)簽，其蘊(yùn)含了大量的有監(jiān)督信息；最后利用訓(xùn)練樣本的稀疏編碼和軟標(biāo)簽構(gòu)造樣本之間的圖結(jié)構(gòu)，并將其嵌入到字典學(xué)習(xí)框架中．

1 相關(guān)工作

1.1 稀疏編碼問(wèn)題

1.2 特殊標(biāo)簽傳播

其中Iα是對(duì)角矩陣，它的對(duì)角元素jα是用來(lái)在迭代中平衡樣本xj的原始標(biāo)簽信息和它受到近鄰點(diǎn)的標(biāo)簽信息的影響的參數(shù)，式子（2）的迭代過(guò)程收斂于

1.3 混合軟相似度

樣本之間的成對(duì)約束包括正約束（Must-link）和負(fù)約束（Cannot-link）．通過(guò)SLP算法[9]獲得無(wú)標(biāo)簽樣本的標(biāo)簽信息后，成對(duì)約束可以利用樣本之間的標(biāo)簽關(guān)系來(lái)獲得更多的監(jiān)督信息，因此對(duì)成對(duì)約束的研究具有重要意義．正負(fù)約束集的定義可以寫成：

2 基于圖結(jié)構(gòu)的半監(jiān)督字典學(xué)習(xí)

本部分為本文新算法．

2.1 圖結(jié)構(gòu)約束

通過(guò)一個(gè)稀疏表達(dá)能力和判別能力較強(qiáng)的字典，稀疏表示系數(shù)A能很好地保持樣本的類別信息和空間結(jié)構(gòu)信息．基于稀疏表示系數(shù)的空間結(jié)構(gòu)性約束，可以定義最小化問(wèn)題：

其中ai為任意樣本xi在字典D下的表示系數(shù)，即為一個(gè)正數(shù)參數(shù)．（13）式可寫成：

2.2 基于圖結(jié)構(gòu)的半監(jiān)督字典學(xué)習(xí)模型

2.2.1 優(yōu)化過(guò)程

針對(duì)模型的非光滑性，本文提出一種基于塊坐標(biāo)下降法（Block Coordinat Descent，BCD）的有效算法交替優(yōu)化A0,iA,D來(lái)求解．另外對(duì)于跡運(yùn)算tr(·)有：

首先固定D和 Ai(i = 1 ,… ,C )更新稀疏編碼A0，獲得以下子優(yōu)化問(wèn)題：

針對(duì)子優(yōu)化問(wèn)題（12），運(yùn)用優(yōu)化最小化算法（Majorization-minimization，MM）迭代求解．具體來(lái)說(shuō)，對(duì)于A的第k步迭代值（記為A(k)），引入以下函數(shù)：

其中constant表示常數(shù)．

同樣地，運(yùn)用MM算法迭代求解子優(yōu)化問(wèn)題（18），即對(duì)于A的第k步迭代值A(chǔ)(k)，引入以下函數(shù)：

其中constant表示常數(shù)．

則A的第k+1步迭代值（記為 A(k+1)）可通過(guò)下式解決：

固定A（其中包括A0和 Ai）更新字典D，獲得關(guān)于D的子優(yōu)化問(wèn)題：

字典D可通過(guò)以下交替方向乘子算法（ADMM）迭代求解，其中Y是拉格朗日乘子矩陣，∏Ξ是向集合的投影算子，μ是一個(gè)給定的正數(shù)．

2.2.2 無(wú)標(biāo)簽樣本的標(biāo)簽信息

1）計(jì)算樣本在第 i(i = 1 ,· ·,C )類的小字典下的稀疏表示系數(shù)

2）計(jì)算重構(gòu)誤差

3）樣本的標(biāo)簽可以由最小化重構(gòu)誤差求得

3 實(shí)驗(yàn)結(jié)果

為了評(píng)估所提算法的分類性能，本節(jié)主要在4個(gè)數(shù)據(jù)集上進(jìn)行分類實(shí)驗(yàn)，其中包括兩大常見(jiàn)的手寫數(shù)據(jù)集：MNIST（http://yann.lecun.com/exdb/mnist）和USPS[10]；人臉數(shù)據(jù)UMIST[11]以及COIL-20數(shù)據(jù)集（http://www.cs.columbia.edu/CAVE/software/softlib/coil20.php）．對(duì)于每個(gè)數(shù)據(jù)庫(kù)，隨機(jī)從每一類中選取τ個(gè)樣本作為標(biāo)簽樣本，v個(gè)樣本作為無(wú)標(biāo)簽樣本，剩下的樣本作為測(cè)試樣本．另外，為了更好地觀察標(biāo)簽樣本個(gè)數(shù)對(duì)算法的影響，單獨(dú)對(duì)數(shù)據(jù)庫(kù)COIL-20進(jìn)行測(cè)試，在每類樣本中隨機(jī)選取35個(gè)作為訓(xùn)練樣本，剩下的37個(gè)樣本作為測(cè)試樣本，在訓(xùn)練樣本中隨機(jī)選取2,3,4,5,6,7個(gè)樣本作為標(biāo)簽樣本，觀察標(biāo)簽樣本個(gè)數(shù)的改變對(duì)算法的影響．表1描述了這些數(shù)據(jù)集的具體信息．

表1 實(shí)驗(yàn)中所有數(shù)據(jù)集的描述Table 1 Description of Data Sets in the Experiment

在實(shí)驗(yàn)中參與比較的算法為：SRC[3]、三種有監(jiān)督字典學(xué)習(xí)算法（DKSVD[4]、FDDL[5]、LCKSVD[6-7]）、兩種半監(jiān)督字典學(xué)習(xí)算法（OSSDL[8]和 S2D2[9]）．在本文算法中有幾個(gè)比較重要的參數(shù)對(duì)實(shí)驗(yàn)效果有著至關(guān)重要的作用，其中包括在特殊標(biāo)簽傳播方法（SLP）獲得訓(xùn)練樣本軟標(biāo)簽過(guò)程中，用來(lái)在迭代中平衡樣本xj的原始標(biāo)簽信息和它受到近鄰點(diǎn)的標(biāo)簽信息的影響的參數(shù)元素αj．把有標(biāo)簽樣本xj的參數(shù)αj設(shè)定為αl，無(wú)標(biāo)簽樣本xj的參數(shù)αj設(shè)定為αu，根據(jù)文獻(xiàn)[10]的經(jīng)驗(yàn)，參數(shù)αl被固定為0，αu為0.999 999 999．除此之外本文算法中還有4個(gè)比較重要的參數(shù)，即同類樣本之間的拉普拉斯矩陣與不同類樣本之間的拉普拉斯矩陣的平衡參數(shù)σ，以及本文算法所提出的半監(jiān)督字典學(xué)習(xí)模型中的平衡參數(shù)λ1,λ2,λ3．本文采用5折交叉驗(yàn)證的方法對(duì)每個(gè)數(shù)據(jù)集確定最優(yōu)參數(shù)．針對(duì)每個(gè)數(shù)據(jù)集，重復(fù)10次實(shí)驗(yàn)，并計(jì)算這10次實(shí)驗(yàn)的平均分類精度

各算法在數(shù)據(jù)庫(kù)的分類結(jié)果如表2所示．在MIST、USPS、UMIST數(shù)據(jù)集上對(duì)7種算法進(jìn)行比較，可以看出本文所提算法（G-SSDL）在 3種真實(shí)數(shù)據(jù)集上的分類效果顯著，這是因?yàn)楸疚牡乃惴ú粌H將標(biāo)簽樣本與無(wú)標(biāo)簽樣本共同訓(xùn)練，而且還將無(wú)標(biāo)簽樣本與標(biāo)簽樣本的內(nèi)在結(jié)構(gòu)以及無(wú)標(biāo)簽樣本的潛在類別信息融入到了我們的算法中，因此其分類性能優(yōu)于其它算法．

表2 不同算法的分類準(zhǔn)確率Table 2 Classification Accuracy of Different Algorithms

改變數(shù)據(jù)集COIL-20標(biāo)簽樣本數(shù)，各算法的分類準(zhǔn)確率如表3所示．當(dāng)標(biāo)簽樣本個(gè)數(shù)較少時(shí)，SRC和其它有監(jiān)督學(xué)習(xí)算法——DKSVD、FDDL、LCKSVD的分類性能較差，原因在于有監(jiān)督字典學(xué)習(xí)的性能很大程度上依賴于有標(biāo)簽樣本的個(gè)數(shù)．本文所給算法G-SSDL有明顯的分類優(yōu)勢(shì)．

表3 改變數(shù)據(jù)集COIL-20 標(biāo)簽樣本數(shù)各算法的分類準(zhǔn)確率Table 3 Classification Accuracy of Different Algorithms with Varied Number of Labeled Samples on Dataset COIL-20

4 總 結(jié)

本文所給算法G-SSDL將訓(xùn)練樣本之間的稀疏編碼和軟標(biāo)簽所構(gòu)造的圖結(jié)構(gòu)嵌入到字典學(xué)習(xí)框架中，通過(guò)圖結(jié)構(gòu)約束和同類樣本的結(jié)構(gòu)稀疏性，迫使無(wú)標(biāo)簽樣本在字典學(xué)習(xí)過(guò)程中能夠自動(dòng)加入到其所在的樣本類別中，并與其同類的有標(biāo)簽樣本共享少數(shù)字典原子，從而提高字典的稀疏表達(dá)能力和判別能力．此外，針對(duì)模型的非凸非光滑性，本文提出一種基于塊坐標(biāo)下降法（Block Coordinate Descent，BCD）的有效算法．結(jié)果表明，本文算法比其它算法具有更好的分類性能．