重構約束的離散矩陣因式分解跨模態哈希

張萬楨，劉同來，李志梅+

(1.桂林航天工業學院 實踐教學部，廣西 桂林 541004；2.廣東工業大學 計算機學院，廣東 廣州510006；3.桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004)

0 引 言

跨模態檢索(cross-modal retrieval)[1-5]是指用戶能用任意一種媒體類型的數據進行檢索，搜索引擎返回多種類型媒體數據的檢索方式。其關鍵問題在于如何高效地解決多媒體數據之間存在的語義鴻溝[6-10]。為此，近年來國內外研究人員提出了多種跨模態哈希(cross-modal hashing)方法[11-15]。其中，基于協同矩陣因式分解(collective matrix factorization，CMF)的跨模態哈希方法[16-20]取得了令人矚目的成果。CMF作為一種簡單但有效的語義挖掘方法能夠高效地學習多模態潛在語義，降低多模態數據間的語義鴻溝。然而這些基于CMF的方法仍然存在一些固有的缺點。首先，在學習潛在語義信息時，過去基于CMF的方法沒有考慮在子空間映射過程中，部分冗余信息會隨同多模態數據的主要語義信息一同嵌入，導致檢索效率下降的問題。此外，許多方法使用松弛-量化的優化方式會導致哈希碼產生大量的量化誤差，降低檢索性能。

為此，本文提出一種重構約束下的離散矩陣因式分解哈希方法(RDMFH)。RDMFH對不同模態使用CMF學習潛在公共語義矩陣的同時，對公共語義矩陣施加數據重構約束、離散約束與圖約束。重構約束保證學習到的潛在語義冗余信息最小化；離散約束減小最終生成哈希碼的量化誤差；圖約束使得最終生成的哈希碼更具可區分性。基于以上3個約束，本文所提出的RDMFH不僅能充分發揮CMF學習多模態潛在語義信息的能力，同時克服了其魯棒性不足，量化誤差大的缺陷，使得哈希碼具有更好的檢索性能。

1 相關工作

根據是否使用數據自身的標簽信息，已有的跨模態哈希方法可以分為有監督跨模態哈希方法和無監督跨模態哈希方法。

1.1 有監督跨模態哈希方法

有監督的跨模態哈希方法利用數據本身標注的真實標簽信息探索異構多模態數據之間的相關性。通常的方法是在學習低維哈希碼的同時嵌入標簽的語義信息，增強哈希碼的可區分性。典型的有監督跨模態哈希方法有最大語義相關哈希[21](semantic correlation maximization，SCM)、監督矩陣因式分解哈希、可擴展離散矩陣因式分解哈希、離散跨模態哈希[22](discrete cross-modal hashing，DCH)、離散潛在因子哈希[23](discrete latent factor hashing，DLFH)、魯棒多視角哈希[24](robust multi-view hashing，RMVH)等。具體地，SCM利用正交約束序列哈希碼，重構多模態數據的相關性矩陣，學習具有可區分性的哈希碼；SMFH首先使用CMF學習多模態數據的潛在公共語義矩陣，然后對其施加圖約束加強哈希碼的可區分性；DCH使用線性分類器學習多模態數據的哈希碼，并對所學習的哈希碼進行標簽回歸增強哈希碼的可區分性；DLFH使用潛在因子模型挖掘標簽的語義信息，通過離散的優化方法得到最終哈希碼；RMVH通過重構潛在語義到原始數據與同時保存多模態數據的模態間和模態內相似性，加強哈希碼的魯棒性和可區分性。

1.2 無監督跨模態哈希方法

無監督的跨模態哈希方法通過挖掘多模態數據本身的分布來學習數據的哈希碼。通常的方法是將多模態數據原始的高維空間映射到低維的漢明空間，同時保存數據的原始分布。典型的無監督跨模態哈希方法有協同矩陣因式分解哈希(collective matrix factorization hashing，CMFH)、潛在語義稀疏哈希(latent semantic sparse hashing，LSSH)、混合相似哈希(fusion similarity hashing，FSH)、協同重構嵌入[25](collective reconstructive embedding，CRE)等。具體地說，CMFH首先使用CMF提取多模態數據的低維潛在語義，然后對其進行量化得到哈希碼；LSSH對圖像和文本分別使用CMF和稀疏編碼學習多模態數據的低維潛在語義；FSH通過在多模態潛在語義中嵌入不同模態數據內部的結構相似性增加哈希碼可區分性；CRE通過對多模態數據進行重構嵌入直接學習多模態離散語義。

2 方 法

為了加強CMF對哈希學習的魯棒性，同時緩解松弛-量化優化方式對哈希學習的負面效果，提出了一種在重構約束下的離散矩陣因式分解哈希方法。與傳統基于CMF的跨模態哈希方法相比，受魯棒多視角哈希RMVH模型的啟發，通過對多模態數據的潛在語義重構回原始數據，加強哈希學習的魯棒性。同時，對多模態數據使用CMF直接學習離散潛在語義，減少以往使用松弛-量化優化方法產生的量化誤差。為了簡便表示，本文將集中于現實世界中最常見的兩種媒體數據：圖片與文本，下面將詳細介紹本文方法的模型。

2.1 問題描述

因此，本文提出重構約束的離散矩陣因式分解哈希方法的目的是學習數據庫的統一哈希矩陣B與一組用于查詢數據的映射函數：f1:X(1)→B和f2:X(2)→B。通過該組映射函數，用戶的查詢數據可以映射到低維的漢明空間，與數據庫的哈希碼B進行對比，然后返回與查詢數據最相近的數據庫樣本。

2.2 重構約束的離散矩陣因式分解哈希

對于圖片訓練集X(1)與文本訓練集X(2)，假設它們有共同的潛在語義V，根據矩陣因式分解模型可以表示為下式

(1)

其中，U(1)∈Rd1×r和U(2)∈Rd2×r為因子矩陣，P(1)∈Rr×d1和P(2)∈Rr×d2分別為圖片和文本的映射矩陣，α和β為超參數。式(1)中第一項和第二項分別為對圖片集和文本集的矩陣因式分解，以學習它們共同的低維語義，第三項為線性回歸項，以學習一組用于查詢數據的映射矩陣。以往的基于CMF的多模態哈希方法，如CMFH、SMFH直接優化式(1)獲得多模態潛在語義V和對應模態的映射矩陣P(1)和P(2)，然后使用符號函數直接量化矩陣V獲得最終的哈希碼B。

然而這些方法忽略了數據中的冗余信息，一張圖片或一段文字中必然會存在與所描述事物不相關的冗余信息。簡單地通過線性回歸模型去學習映射矩陣P(1)和P(2)，會導致在泛化新樣本時把原始數據中的冗余信息一起映射到潛在語義矩陣V中。在隨后的量化過程中，冗余信息與核心語義信息一同被量化為哈希碼，導致哈希碼的可區分性下降，影響檢索性能。此外，先優化式(1)再使用符號函數量化潛在語義矩陣V生成哈希碼，會導致量化過程中產生大量的量化錯誤，也會影響最終生成哈希碼的檢索性能。

基于以上的討論，受到RMVH的啟發，本文提出一種新的重構約束的離散矩陣因式分解哈希，其公式化描述如下

(2)

其中，Q(t)∈Rd(t)×r為重構矩陣，E(t)∈Rd(t)×n為重構誤差矩陣。與式(1)不同的是，式(2)直接對多模態數據使用CMF學習離散潛在語義，通過優化式(2)，可以直接學習到離散的多模態數據的統一哈希碼矩陣，避免松弛-量化步驟，減少了量化誤差。同時，通過重構約束項X(t)=Q(t)P(t)X(t)+E(t)，將多模態數據分為純凈項Q(t)P(t)X(t)和冗余項E(t)，在學習多模態數據的離散潛在語義B時，只使用P(t)X(t)而排除了冗余信息項E(t)，增強哈希碼的可區分性和映射矩陣的魯棒性。同時，對E(t)施加L1范數約束是為了讓重構誤差盡可能小。此外，變量Q正交是為避免出現平凡解。

一般來說，希望同一類別樣本的哈希碼盡可能相似，而不同類別樣本的哈希碼盡可能不同。為了進一步增強所學習哈希碼的可區分性，構造了一個圖拉普拉斯矩陣以保存多模態數據的相似性，其公式化描述如下

(3)

其中，L∈Rn×n為相似矩陣S的拉普拉斯矩陣。把式(3)與式(2)結合，得到本文目標函數式如下

(4)

其中，γ為超參數。

2.3 優化算法

對于多變量的目標函數，通常的優化方法是交替迭代乘子法(ADMM)，優化其中一個變量時固定其它變量，然而式(4)中存在離散變量B，使得直接對式(4)使用ADMM進行優化變得非常困難，為此，我們采取一種靈活的替代優化方式[26]，通過引入一個輔助變量K，簡化式(4)的優化過程。引入輔助變量K的目標函數式如下

(5)

以往的方法已經證明，該替代方式可以很大程度上方便目標函數的優化，同時盡量不影響最終的優化結果。式(5)的增廣拉格朗日函數如下

(6)

其中，Z(t)為增廣拉格朗日乘子，μ為懲罰參數。通過該拉格朗日函數，將帶約束優化變為無約束優化，進一步方便優化。對式(6)使用ADMM交替優化目標變量步驟如下。

步驟1 定除U(t)外的其它變量，式(6)對U(t)求偏導等于0解得

(7)

步驟2 定除K外的其它變量，式(6)對K求偏導等于0解得

A1K+KA2+A3=0

(8)

其中

可以通過使用Matlab直接求解該Sylvester方程求得K。

步驟3 定除P(t)外的其它變量，式(6)對P(t)求偏導為0解得

(9)

其中，D=βBX(t)+μQ(t)X(t)X(t)T-μQ(t)TE(t)X(t)T+Q(t)TZ(t)X(t)T。

步驟4 過解決下面方程，可求得變量Q(t)

(10)

步驟5 定其它變量，令式(6)對B求偏導等于0再用符號函數量化得

(11)

步驟6 過下式更新變量E(t)

(12)

步驟7 過下式更新Z(t),μ

(13)

因此，通過迭代更新以上變量，直到達到設定的迭代次數來優化目標函數的各項參數，具體的優化過程見算法1。

算法1：本文的優化算法

輸入：圖像矩陣X(1)和文本矩陣X(2)，相似矩陣S，參數α，β，γ，α(1),α(2)，哈希碼長r迭代次數T。

輸出：映射矩陣P(1)和P(2)，哈希矩陣B。

(1)隨機初始化所有變量矩陣；

(2)Repeat；

(3)用式(7)更新矩陣U(t)；

(4)用式(8)更新矩陣K；

(5)用式(9)更新矩陣P(t)；

(6)用式(10)更新矩陣Q(t)；

(7)用式(11)更新矩陣B；

(8)用式(12)更新E(t)；

(9)用式(13)更新Z(t)和μ；

(10)Until迭代次數。

2.4 時間復雜度分析

對于算法1，其計算的時間復雜度主要來自于求解Sylvester方程和SVD分解。下面詳細列出算法1的各個步驟所需要的時間復雜度。在每一次迭代中：更新矩陣U(t)的時間復雜度為O(r3+r2d+rdn)；更新矩陣K的時間復雜度為O(n2)；更新矩陣P(t)的時間復雜度為O(rdn)；對一個d×r大小的矩陣進行SVD所需要的時間復雜度為O(dr2)，因此更新矩陣Q的時間復雜度為O(dr2+d2n)。一般來說有n>d>r，因此本文方法每一次迭代的時間復雜度約為O(n2+d2n+drn)。

3 實驗與分析

本文在Wiki、NUS-WIDE和MirFlickr-25k這3個公開的基準數據集上進行實驗驗證與分析，并與最近的基于CMF的跨模態哈希方法進行對比，包括無監督的CMFH、LSSH、RFDH，和有監督的SMFH、SCARTCH對比。此外，為了進一步驗證方法的有效性，還與非基于CMF的跨模態哈希方法RMVH、DCH進行對比。在兩種常見的跨模態檢索任務上進行對比和分析：①本檢索圖片；②片檢索文本。

3.1 數據集

Wiki：Wiki數據集是從維基百科的文章中收集的圖片-文本對，有2866組，共分為10大種類。每一張圖片至少對應一段不少于70個單詞的文段描述。每張圖片被表示為128維的SIFT特征，而文本則由10維的主題特征所表達。該數據集共有10大類別，每一組圖片-文本對對應其中一個類別。本文選取2173組樣本作為訓練集，其余的作為測試集。

NUS-WIDE：NUS-WIDE是一個真實的網絡圖像-文本數據集，它包含269 648張帶有標簽注釋的圖片，共有81個類別。本文選取其中10個數量最多的種類，共有186 577張帶有注釋的圖片作為訓練集。每張圖像表示為500維的視覺特征，文本則表示為1000維的詞袋向量，本文選取2000組圖像文本對作為測試集，剩余的作為訓練集。

MirFlickr-25k：MirFlickr-25k是從圖片網站flickr上收集的圖片-文本數據集，包含25 000組圖片-文本對，共有24個類別。每張圖片表示為150維的視覺特征，文本表示為1366維的詞袋模型。本文選取2000組圖像-文本對作為測試集，其余的作為訓練集，數據見表1。

表1 實驗數據集統計信息

值得注意的是，由于SMFH的計算復雜度太高，因此，為了方便實驗，本次實驗在NUS-WIDE數據集上僅采用5000個樣本作為訓練集訓練對比。

3.2 實驗設置

本文方法的參數設置如下：α控制不同模態數據對潛在語義影響的權重，一般設置為0.5；β設置為10；γ控制監督信息的權重，設置為100；α設置為0.001；迭代次數T設為10。此次實驗的性能評估標準采用平均精度均值(mean average precision，MAP)。MAP反映模型的整體準確率，數值越大表示檢索效果越好。為了避免隨機初始化數據的干擾，所有的實驗數值均重復10次取均值。實驗環境為Intel(R) Core(TM) CPU I7-6700@4.0 GHz 32 GB RAM的服務器上運行，系統為WIN10。

3.3 實驗結果與分析

表2與表3分別給出了本方法與對比方法在Wiki、NUS-WIDE和MirFlickr-25k這3個數據集上的兩種跨模態務的MAP數值，哈希碼長分別為16 bit、32 bit和64 bit。

表2 在Wiki和NUS數據集上MAP值

表3 在MirFlickr-25k數據集上MAP數值比較

表2、表3中最優的數值均用黑色加粗字體表示。

對于Wiki數據集，從表2的數據可以看出，本文的方法在不同哈希碼長度下的MAP值優于所對比的方法，驗證了本方法在跨模態檢索任務中的有效性。值得注意的是，通過觀察表2，可以發現大部分有監督跨模態哈希方法比無監督的跨模態哈希方法檢索效果更好，這是因為有監督的方法通過嵌入真實的標簽信息到哈希碼中，可以大幅增加哈希碼的判別力，因此有監督的方法通常比無監督的方法檢索效果好。但是可以看到無監督的RFDH在文本檢索圖像任務中效果比有監督的SMFH好，這是因為RFDH是使用離散的優化方法優化哈希碼，避免了松弛-量化過程造成的量化誤差，而SMFH是使用松弛-量化的方法優化哈希碼，所以無監督的RFDH效果比有監督的SMFH好。而本文方法也是采用離散的優化方法，因此檢索效果優于非離散的方法。此外，通過表2還可以觀察到，哈希碼的碼長越長，效果越好，這是因為哈希碼的碼長越長，哈希碼所能保存的信息越多，因此檢索效果越好。由于本文方法與RMVH均使用數據重構，使得哈希碼能夠盡可能少的受到冗余信息的干擾，哈希碼所保存原始數據的主要信息比其它方法更多，因此檢索的效果優于其它對比方法。

對于NUS-WIDE數據集，從表2的MAP數值比較中可以觀察到，本文方法優于其它的方法，這與在Wiki數據集中的觀察一致，再次驗證了本文方法在跨模態檢索任務中的有效性。此外，可以觀察到，文本檢索圖片任務的MAP值比圖片檢索文本的MAP值普遍要高，這是因為文本所包含的信息比圖片的信息要直觀，能更好表達數據的核心語義。

對于MirFlickr-25k數據集，從表3的MAP數值對比中可以觀察到，本文方法優于其它的對比方法，與Wiki、NUS數據集中的觀察一致，進一步驗證本文方法的有效性。

3.4 收斂分析

下面分析本文方法的收斂性，由于本文方法的優化方式是基于迭代的優化方式，因此優化算法的收斂性對模型的性能起到至關重要的作用。這里主要通過實驗驗證本文優化算法的收斂性。

圖1為迭代次數與目標函數值的曲線圖。從圖1中可以觀察到，本文方法在10次迭代左右就基本收斂，因此本文方法的整體計算成本并不高，可以有效地用于大規模的跨模態檢索任務。

圖1 目標函數迭代曲線

3.5 參數分析

下面分析參數對實驗結果的影響，重點分析3個主要參數α，β，γ對實驗的影響。由于實驗過程中發現參數αt對本文方法實驗影響很小，這里不作進一步分析。為了研究以上3個參數對實驗結果的影響，在研究其中一個參數時，固定其它兩個參數，固定參數的取值如上文所述，哈希碼長定為16 bit，以MAP作為評價指標。

圖2顯示了各個參數在Wiki和NUS-WIDE數據集上的實驗結果。從圖2中觀察到，當α取值為0.5時，本文方法在兩個數據集中取得最優結果；參數β控制線性回歸項對整個模型的影響，從圖中可以看到，當β處于[1,50]時，模型的性能往上提升，當大于50時，模型性能下降，因此β的取值取中間值10為最佳；參數γ控制監督信息對模型性能的影響，從圖中可以觀察到，當γ的取值為100時，模型性能達到最佳，繼續往上升模型性能下降，因此γ取值100。通過以上分析可知，本文方法參數能在一個較寬范圍內取得不錯的結果，對參數敏感性不強。

3.6 消融分析

為了進一步驗證數據重構和離散約束對實驗結果的影響，進行了以下3組消融對比實驗。第一組對比實驗為本文方法對比本文方法去除重構約束但保留離散約束項的結果，記為RDMFH-1；第二組對比實驗為對比本文方法與本文方法去除離散約束但保留重構約束項的結果，記為RDMFH-2；第三組對比實驗為對比本文方法與本文方法去除重構約束與離散約束的結果,記為RDMFH-3。實驗在Wiki數據集上進行，采取MAP數值評估，實驗結果見表4。表4中本文方法與RDMFH-1對比可以得出，重構約束項在檢索性能上有約1%的提升，驗證了重構約束項的有效性；對比本文方法與RDMFH-2可以看出，離散約束對哈希碼的檢索能力有較大的提升，在每一位哈希碼上均有10%以上的MAP數值提升，說明離散約束能大幅度減少量化誤差，提高哈希碼的可區分性，增加檢索能力。對比RDMFH-2與RDMFH-3可以觀察到，在哈希碼非離散的情況下，重構約束項仍然對哈希碼有約1%的性能提升，再次驗證重構項的有效性。

4 結束語

本文提出了一種重構約束的離散矩陣因式分解哈希方法。與以往的基于矩陣因式分解的哈希方法不同，考慮了異構多模態數據中普遍存在的冗余信息對學習公共語義空間的影響，通過添加數據重構約束，將由稀疏項建模的冗余信息與映射項建模的主要信息進行分離，增強所學習哈希碼的魯棒性與可區分性。同時直接學習離散的哈希碼，避免松弛-量化造成的大量量化誤差。大量的實驗結果表明，本文方法優于其它基于矩陣因式分解的跨模態哈希方法。

圖2 參數調優折線

表4 消融對比實驗結果