標簽局部結構保持的離散哈希方法

敖宇翔,滕少華,張 巍,滕璐瑤

1(廣東工業大學 計算機學院,廣州 510006)

2(Monash University,Melbourne 3800,Australia)

1 引 言

近年來,隨著互聯網應用展開,文本、圖像、視頻等不同模態數據和高維度數據迅速增長.多模態、高維度信息檢索,尤其是跨模態檢索需求大幅度增長.例如,給定一個關于動物的文本查詢,人們不滿足于僅從文本中檢索到該動物的信息,還希望從圖像和視頻等其他模態中瀏覽到該動物.這使傳統的最近鄰搜索無法滿足人們的需求,跨模態哈希檢索技術因其檢索效率高、存儲成本低而使其廣受關注[1-3].源模態數據轉換為二進制哈希碼后能大幅度降低存儲開銷,并且哈希碼之間的硬件級異或操作也提高了漢明空間[4,5]中的搜索效率.

早期的許多工作都只關注單一模態[6,7],即查詢和搜索結果處于同一模態.近年來,跨模態哈希研究成為熱點.跨模態哈希檢索又可分為無監督和有監督方法兩個大類.

無監督跨模態哈希的重點是利用不同模態數據的特征信息來尋找模態之間的相關性.其中跨模態哈希(IMH)[8]使用模態內和模態間關系來構造親和矩陣 再利用親和矩陣學習公共子空間.協同矩陣分解哈希(CMFH)[9]將多模態數據利用矩陣分解,分解為模態特有特征和模態共有特征,再利用共有特征獲得哈希碼.融合相似度哈希(FSH)[10]首先獲取多模態數據之間的相關性并構建融合相似度,然后在漢明空間中保持融合相似度.潛在語義稀疏哈希(LSSH)[11]將稀疏編碼和矩陣分解相結合來獲取潛在語義特征,然后利用潛在語義特征獲取哈希碼.

而有監督跨模態哈希方法則使用監督信息(標簽)填補模態之間的巨大差異.在有監督的跨模態哈希方法中,語義相關性最大化哈希(SCM)[12]通過標簽構造余弦相似度矩陣來學習哈希碼.有監督矩陣分解哈希(SMFH)[13]利用標簽余弦相似度構建圖正則化來約束協同矩陣分解得到的公共特征,從而在生成的哈希碼中保持標簽相似度.然而上述方法都在學習哈希碼的過程中松弛了離散約束,導致可能產生量化誤差,降低哈希碼的質量[14].離散交叉模態哈希(DCH)[14]構建了一個線性分類框架將哈希碼映射到標簽矩陣,DCH采用循環坐標下降策略(DCC)[15]逐位更新哈希碼,減少了松弛離散約束造成的量化誤差.可擴展的離散矩陣分解哈希(SCRATCH)[16]通過集合矩陣分解和語義嵌入來學習一個潛在的語義空間,然后利用潛在語義空間離散生成哈希碼,減少了較大的量化誤差.

近年來,隨著深度學習應用展開,一些基于深度學習的跨模態哈希方法開始出現,并且表現不俗,比如:深度跨模態哈希[17],自監督對抗哈希[18],循環一致性深度生成哈希[19]等.

雖然許多跨模態哈希方法已經被提出,并有較好的效果,但仍有一些問題需要探討：1)一些方法只提取了多模態數據中的信息,而忽略了具有更強語義的標簽信息；2)一些方法只將標簽信息轉化為相似度并嵌入到哈希碼中,但這種轉化也將引起標簽的語義信息損失；3)一些方法沒有使用核函數,難以捕捉到源數據間的非線性關系.

針對這些問題,本文提出了一種新穎的跨模態哈希方法——標簽局部結構保持離散哈希(LSPDH),不同于其他使用流形學習的跨模態哈希方法,本文方法分為哈希碼學習和哈希函數學習兩步.哈希碼學習中運用流形學習在漢明空間中保持標簽信息的局部結構,并將標簽信息映射到哈希碼矩陣,融入哈希碼學習過程,減少了標簽信息轉化為局部保持圖約束所造成的語義信息損失;哈希函數學習中使用了核函數來獲取數據間的非線性關系.最后,通過實驗驗證了本方法的有效性.

本文組織如下:第2節提供了相關工作的概述,第3節闡述了所提出的方法,第4節是實驗的詳細描述和綜合分析,最后在第5節中給出了結論.

2 相關工作

本節將介紹一些與LSPDH相關的研究,主要包括流形學習在哈希學習中的應用和兩步哈希學習.

2.1 流形學習在哈希學習中的應用

流形學習自提出以來就受到了廣泛的關注.近年來哈希學習的一些研究結果表明,保持流形結構可以有效地提高哈希碼的質量.流形學習的應用首先從單模態哈希檢索開始.譜哈希(SH)[6]希望在漢明空間中距離較大的兩個數據點在源數據空間中具有較小的相似度,它將流形學習轉化為Laplace-Beltrami特征函數,通過簡單的閾值操作得到哈希碼.在此基礎上,錨點圖哈希(AGH)[20]被提出來了,它利用錨點將鄰接矩陣替換為近似鄰接矩陣,降低了時間復雜度.此外,還有其他使用流形學習的哈希方法,如離散圖哈希(DGH)[21]和離散多視圖哈希(DMVH)[22].

上述方法只能在單一模態下工作.近年來,在跨模態哈希檢索領域,流形學習的使用也開始變得頻繁起來,例如,跨模態哈希(IMH)[8]通過結合模態間一致性和模態內一致性來學習哈希碼.監督矩陣分解哈希(SMFH)[14]利用標簽信息來計算余弦相似矩陣,并結合協同矩陣分解生成哈希碼.融合相似度哈希(FSH)[10]構造一個融合圖來定義多模態數據之間的相似度,然后在漢明空間中保持融合相似度.此外,還有其他使用流形學習的交叉模態方法提出[23].但是,上述方法和本文方法有很大的不同.上述方法大部分利用流形學習提取原始數據的特征,而本文方法則利用流形學習提取標簽信息的特征,在漢明空間中保持標簽信息的局部結構.

2.2 兩步哈希學習

早期跨模態方面的研究都是采用一步哈希的學習策略.近年來的一些研究[24,25],將哈希學習分解為兩個步驟:1)哈希碼學習;2)哈希函數學習.該學習策略使哈希學習過程更加高效和靈活,從而影響了很多研究.語義保持哈希(SEPH)[24]為哈希碼的每一位學習一個核邏輯回歸函數,但這會增加大量時間消耗.兩步跨模態哈希(TECH)[25]在哈希函數學習的過程中加入了相似度保持.其他一些方法則是使用簡單的線性回歸來學習哈希函數[23].將哈希學習過程分解為兩步,可以將哈希函數學習視為一個分類任務,可以在哈希函數學習中使用更復雜、更強大的模型.與此同時,使用過于復雜的模型會顯著增加訓練時間[24].在本文中,將使用核回歸函數作為哈希函數.

3 提出方法

本文方法基于如下直觀知識:如果兩個樣本數據(文本、圖像、視頻等)共有的標簽類別數越多,代表其描述的內容相似性越高,為使變換不丟失原有標簽信息,因而,要求變換后樣本數據的漢明空間距離也應該保持相近.基于此,本文思路如下:樣本數據共有的標簽數越多,其描述的內容相似度越高,漢明空間應距離越相近,最后,生成的哈希碼的相似性也應越高.由此,本文方法在哈希碼學習過程中,盡量保持數據的標簽信息不變，其示意圖如圖1所示.

圖1 LSPDH示意圖

為便于描述,本文中使用的符號在此統一給出.

3.1 符號

3.2 哈希學習

針對多模態哈希檢索現存的問題,本文提出一個基于標簽局部結構保持的離散哈希方法,分為哈希碼學習和哈希函數學習兩步,詳述如下:

3.2.1 哈希碼學習

1)標簽信息局部結構保持

許多方法利用流形學習在漢明空間中保持多模態數據的結構特征.本文的方法則盡量在漢明空間保持數據的標簽信息不變,這符合檢索目標.因此,采用Locality Preserving Projection(LPP)[26]的思想構造流形相似度矩陣來保持標簽信息的局部結構:

(1)

如上所示,首先需要找到每個樣本數據的K個最鄰近點, 如果Yi是Yj的一個鄰近點,或者Yj是Yi的一個鄰近點(K個最鄰近點之一),則在這兩個點之間的邊上賦予一個熱核權值(其權值與距離成反比),否則這個權值為0,式(1)中t為寬度參數,本文設置為1.在計算完流形相似度矩陣之后,使用它來構建圖約束,以此在漢明空間中保持標簽信息的局部結構.然而,由于哈希碼具有離散性, 在直接約束哈希碼之后,哈希碼的優化求解將很難進行.解決方法是在潛在空間V上施加約束,并讓它近似哈希碼矩陣B:

s.t.B∈{-1,1}k*n

(2)

2)標簽線性映射

利用投影矩陣把標簽矩陣直接映射到哈希碼矩陣B,以此減少構建相似度矩陣所造成的語義信息損失,并使哈希碼包含更多語義信息:

(3)

3)整體目標函數

s.t.B∈{-1,1}k*n

(4)

其中α,β為權重參數,分別控制了流形學習和標簽線性映射對方法效果的影響.

4)優化算法

顯然,直接優化具有3個變量(B,V,Q)的非凸目標函數是很困難的.然而,如果每一次只優化一個變量,然后固定住其他變量,這就變成一個凸優化問題.因此,采用迭代優化策略更新B,V,Q來獲得一個近似解.

更新B:固定V,Q,更新B.目標函數式(4)可寫為如下形式:

s.t.B∈{-1,1}k*n

(5)

將式(5)展開:

(6)

第1項(β+1)tr(BTB)為常數項,將它和與B無關的項舍去可得:

(7)

=-tr((VT+βYTQT)B)

s.t.B∈{-1,1}k*n

(8)

最終,可以在保持離散約束的同時得到B矩陣的優化結果:

B=sgn(V+βQY)

(9)

更新V: 固定B,Q,更新V.拋棄與V不相關的項, 可以將目標函數式(4)寫為:

(10)

令式(10)對V的導數為零,則有等式:

-2B+2V+αV(L+LT)=0

(11)

V=2B(2I+α(LT+L))-1

(12)

更新Q:固定B,V,更新Q.類似于更新V,留下和Q相關的項:

(13)

令式(13)對Q的導數為零,則有等式:

-2BY’+2QYY’=0

(14)

Q=BYT(YYT)-1

(15)

為了得到式(4)的最終局部最優解,可以使用迭代更新策略,通過上述步驟更新B,V,Q,直到它們收斂.

3.2.2 哈希函數學習

如前所述,LSPDH為兩步哈希方法.哈希碼學習所得到的哈希碼矩陣B是用于檢索的數據庫.對于樣本外的數據,需要為它們學習哈希函數,將它們映射到漢明空間.為了捕捉數據間的非線性特征,本文采用核回歸作為哈希函數,可以使得一些低維線性不可分的數據映射到高維后線性可分.t模態的目標哈希函數如下:

(16)

Pt=Bφ(Xt)T(φ(Xt)φ(Xt)T+λI)-1

(17)

(18)

算法1總結了哈希碼學習和哈希函數學習的整個優化過程.

算法1.LSPDH的優化算法

輸入:訓練集Xt;標簽值Y; 參數α,β,λ.

輸出:哈希碼B;哈希函數Pt.

1.將訓練集映射到核空間;

2.隨機初始化V,Q, 將B的值全部賦為-1;

3.迭代

4.根據式(9)更新B;

5.根據式(12)更新V;

6.根據式(15)更新Q;

7.直到式(4)收斂或達到最大迭代次數;

8.根據式(17)學習哈希函數Pt;

9.返回哈希碼B和哈希函數Pt.

3.3 復雜度分析

式(9)和式(15)的時間復雜度分別為O(kn+kln)和O(knl+l2n+l3+kl2).式(16)的時間復雜度為O(d2+d2k+d2n+dkn),k為哈希碼長度,n為訓練數據個數,l為類別總數,d表示使用φ(·)后的特征維數.由于k,l<

4 實驗與結果分析

在3個基準數據集上進行了充分實驗,并與6種近期跨模態哈希方法進行了比較,驗證了本文提出的跨模態哈希方法的有效性.所有實驗都是在Intel Core I5-8300H CPU和16GB RAM平臺上進行.

4.1 數據集

LabelMe[28]:數據集包含2688個圖像-文本樣本對.數據集中有8個類別,每個樣本對都屬于其中一個類別.文本用245維詞頻特征向量表示,圖像則用512維Gist特征向量表示.在這個數據集中,隨機選取2016個樣本對作為訓練集,剩下的672個樣本對作為測試集.

MIRFlickr[29]:它包含了從Flickr網站上下載的25000個圖像-文本樣本對.每個樣本對都用24個標簽中的一個或多個標簽進行標記.圖像通過PCA降維后用150維的邊緣直方圖特征向量表示,對應的文本也通過PCA降維后用500維的特征向量表示.隨機選取5%的樣本對作為查詢集,其余的作為訓練集.

NUS-WIDE[30]:它由從Flickr抓取的269,648個圖像-文本樣本對組成.每個樣本對至少有一個或多個標簽.數據集的所有樣本對可分為81類.由于原始數據集中部分類別樣本對較少,因此選擇樣本對數量最大的10個類別作為實驗數據集,共186577個樣本對.在每個實例中,圖像用500維的視覺詞袋 SIFT直方圖特征向量表示,對應的文本用1000維的索引特征向量表示.為了減少計算量,在NUS-WIDE中隨機選擇5000個訓練樣本對和1867個測試樣本對來訓練和測試所有的方法.

4.2 對比方法及其簡介

將本文方法與6種近期的跨模態哈希方法進行了比較.分別是SCM,SMFH,DCH,SCRATCH,GSPH,SDCH-KDA.

SCM[13]利用標簽信息構造成對相似度矩陣,采用松弛離散策略來生成哈希碼,本文使用SCM_seq版本.

SMFH[14]構建了一種新的哈希協同矩陣分解框架,并利用圖正則化來提高哈希碼的質量.

DCH[12]構建了一個線性分類框架,并采用DCC離散優化策略減少量化誤差,提高哈希碼的質量.

SCRATCH[15]結合了集體矩陣分解和語義嵌入,以保持模態內和模態間的相似性,并離散生成二進制代碼.

GSPH[31]在不同場景下,利用數據點之間的相似性學習哈希碼,同時為哈希碼的每一位學習一個核邏輯回歸模型.

SDCH-KDA[32]將核判別分析(KDA)整合進離散哈?？蚣?提高了哈希碼的判別能力.

所有對比方法的源代碼都是公開的.在實驗中設置了兩個任務,一個是圖像查詢文本任務,另一個是文本查詢圖像任務.在NUS-WIDE, MIRFlickr數據集上α=3,β=5,μ={0.035,0.3},在LabelMe數據集上α=3.5,β=3,μ=0.035.

4.3 評價指標

為了評價各方法的性能,采用了檢索領域常用的評價指標:平均精度均值(mAP).在計算mAP之前,需要計算平均精度(AP).給定一個查詢q和一個檢索到的實例列表R,q的AP定義如下:

(19)

其中N是檢索集中與q真實相關的實例個數,n檢索到的實例列表R的大小,δ(r)=1表示第r個被檢索到的實例與查詢q相關,否則δ(r)=0,precision(r)表示被檢索到的第r個實例的精度.最后對所有查詢實例計算AP值,再進行平均就可以得到mAP.此外還將采用precision-recall曲線作為評價指標.在所有的評價指標中,評價指標值越大代表效果越好.

4.4 實驗結果分析

表1總結了LSPDH和對比方法在3個數據集上的mAP值.從表1中可以得出如下結論:

表1 各方法在3個數據集上的mAP值

1)LSPDH的表現在文本查詢圖像任務中要優于所有對比方法,在NUS-WIDE數據集圖像查詢文本任務中,32和128比特位上略弱于SDCH-KDA,這表明了LSPDH的有效性.

2)在LabelMe數據集32位圖像查詢文本和文本查詢圖像任務中,LSPDH的mAP對比最優方法分別提升約1.1%、0.3%,而在128位下提升分別約為2.7%、1.2%.在MIRFlickr數據集32位同任務中,mAP分別提升近0.2%、1.4%,128位下分別提升近1.1%、2.7%.在NUS-WIDE數據集上,文本查詢圖像任務下32位提升約為0.9%,128位下提升約為2%,而圖像查詢文本任務下則和最優方法差距在0.3%以內.可以看出LSPDH在文本查詢圖像任務中表現更佳,在圖像查詢文本任務中則表現一般,特別是在NUS-WIDE上,表現與SDCH-KDA相似,這可能因為,文本相對于圖像可以更好描述實例,同時文本特征向量和標簽向量在結構上也有一些相似之處,例如一段描述汽車的文本,它里面的某些表述可能就是這個文本的標簽.

3)LSPDH在32位圖像查詢文本任務和文本查詢圖像任務中,平均提升很低,分別約為0.4%、0.8%,而在128位同任務下,平均提升分別約為1.3%、2%.可能的原因是低位數哈希碼包含的語義信息不足所導致的.此外可以發現,大部分方法的性能會隨著哈希碼的位數增加而增加,其原因是更長的哈希碼可以包含更多的信息.

圖2展示了LSPDH和對比方法的precision-recall曲線,理論上,方法的mAP值越高,其precision-recall曲線也會越高.從圖2中可以得出如下結論:

圖2 LSPDH與對比方法的precision-recall曲線圖

LSPDH基本上高于所有對比方法,在NUS-WIDE圖像查詢文本任務上表現和SDCH-KDA相似,這與表1的觀察結果是一致的.

綜上所述,LSPDH與一些先進的方法相比表現出了良好的性能,說明LSPDH可以學習到更加精確的哈希碼.

4.5 收斂性分析

圖3顯示了目標函數值在3個數據集上隨迭代次數的變化曲線.如圖3所示,LSPDH可以快速收斂.在NUS-WIDE和LabelMe數據集上,可以觀察到LSPDH在5次迭代中收斂,而在MIRFlickr數據集上,它在15次迭代中收斂.這說明本文提出的方法在大多數據集上的訓練是有效率的.

圖3 收斂性分析

4.6 參數敏感性分析

本節進行了參數敏感性分析實驗來分析各參數(α,β和μ)的變化對mAP的影響.參數α控制流形學習在方法中的影響程度,參數β控制標簽線性映射在方法中的影響程度,參數μ控制正則化項的懲罰程度.在測試每個參數的同時保持其他參數不變.3個參數的變化曲線如圖4所示.從圖4中可觀察到,本文方法可以在參數(α,β和μ)較大范圍內表現良好,同時可以觀察到α和β分別在 [1e-3,1],[1e-2,10]范圍內變化的時,mAP值有比較明顯的提升,這表明流形學習和標簽線性映射對提升哈希碼的質量是有效的.對于單個參數來說,β對mAP的影響大于α,這說明標簽值所包含的語義信息非常重要.對于μ,可以看出,它的值不宜過大或過小,過大會導致欠擬合,而過小會導致過擬合,對于不同的模態,其μ值可能不同.綜上所述,本文方法α設置在[0.1,10]之間,β設置在[1,10]之間,μ設置在[1e-2,1]之間.

圖4 參數敏感性分析

4.7 時間成本分析

在MIRFlickr數據集上進行了時間消耗實驗來對方法復雜度做進一步分析,結果如表2所示.從表2中可以看出,構建圖約束的方法(LSPHS)由于時間復雜度為O(kn2),會比時間復雜度為O(n)的方法(SCRATCH)花費更多的時間.此外可以觀察到,采用DCC策略學習哈希碼的方法(DCH)時間消耗也非常的高,這是因為每一次迭代優化過程中都要逐位學習哈希碼.GSPH由于為每一比特位學習了一個核邏輯回歸模型,因此GSPH的時間復雜度會隨著哈希碼位數的增長而顯著提升.SDCH-KDA需要計算散度矩陣,在使用了核函數后,SDCH-KDA的時間成本也會明顯上升.本文所提出的方法時間消耗較高,其主要原因是LSPDH在MIRFlickr數據集上需要迭代15次,而其他兩個數據集只需迭代5次.

表2 各方法在MIRFlickr-5k上的訓練時間成本(單位:秒)

5 結束語

本文提出了一種新穎的有監督跨模態哈希方法,命名為標簽局部結構保持的離散哈希,簡稱LSPDH.LSPDH是一個集哈希碼學習與哈希函數學習的兩步方法,第1步,該方法計算標簽相似度矩陣并在潛在空間構建圖約束來保持標簽的局部結構,再使用標簽線性映射降低構建流形相似度所造成的語義損失,使哈希碼包含更多的語義信息,因而具有更高的質量;第2步,在哈希函數學習中加入了核函數,用于獲取源數據間的非線性信息.LSPDH在3個基準數據上的實驗結果表明其性能基本優于近期跨模態哈希方法.在未來的工作中,將考慮保持標簽語義的同時,解決使用圖約束導致時間復雜度過高的問題,結合深度學習進一步研究跨模態哈希方法.