相似度保持跨模態哈希檢索

房小兆，唐寶動，韓 娜，孫為軍，滕少華

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

2(廣東工業大學 自動化學院，廣州 510006)

1 引 言

隨著互聯網技術的迅速發展，人們對多模態數據之間的交叉檢索的需求越來越迫切.多模態數據的最大特點是用多種異構數據描述同一個對象[1-5].例如在維基百科網上，一般由圖片、文本等多個不同模態的異構數據描述同一個語義對象；YouTube視頻網站上每一段視頻大都有相應的文本或者標簽進行描述；在微博上發布動態消息時，往往會同時附加一段文字或者一些標簽描述上傳照片或者視頻中的內容.這里的“模態”(Modality)是指數據的類型或者表現形式，不同數據類型對應不同的模態，如：“圖像”是一個模態、“文本”是一個模態、“音頻”也是一個模態等等.相應的多模態是指用不同的數據類型描述一個共同的語義.在實際應用中，人們經常需要利用圖片檢索相關文本或者用文本檢索相應的圖像，類似這種用一種模態的數據去檢索另外一個模態數據的任務被稱為跨模態檢索.然而不同模態數據之間結構上的異構性(Heterogeneous gap)以及語義鴻溝(Semantic gap)等因素給跨模態檢索任務造成一定的困難.

為了消除異構多模態數據之間的差異性，很多研究者提出通過算法學習異構數據的統一的潛在語義表示.如：典型相關性分析(Canonical Correlation Analysis，CCA)[6]投影兩種模態數據到統一的潛在空間中.偏最小二乘法(PartialLeast Squares，PLS)[7]不但學習統一的空間而且進一步考慮模態內以及模態之間的潛在關聯.然而這些方法面對海量樣本時由于需要大量的內存消耗以及大規模運算等原因造成算法性能急劇下降.鑒于基于哈希檢索算法計算相似度的高效性以及低存儲等特點，近年來許多研究者提出將哈希的思想應用到異構跨模態檢索(Cross-modal retrieval hashing)任務中.

基于哈希的跨模態檢索方法一般是指將描述同一語義對象不同結構的數據映射到相應的潛在語義空間中，再通過某種變換形式用特定長度的“0”、“1”二進制串表示該對象并用于檢索的方法.基于哈希思想的算法在計算相似度時可以直接使用二進制編碼的位運算(異或，xor)來提升計算效率.另外由于是給每一個樣本生成一個對應的二進制序列，所以在存儲原始樣本時可以極大的節省內存儲空間[8-10].Michael[11]等人提出的相似敏感哈希(Learning Using Similarity-Sensitive Hashing)算法第一次將哈希的思想應用到多模態檢索任務上，并獲得了較好的表現.但該算法只考慮了原始樣本模態內的相關性而忽略了模態間的關聯性.為解決這一問題，Kumar[12]等提出通過最小化相似樣本對對應的哈希碼之間的距離并最大化不相似樣本對對應的哈希碼之間的距離來學習哈希碼.Zhen[13]等提出(Multimodal Latent Binary Embedding，MLBE)通過聯合的多模態字典學習以獲取不同模態樣本對的稀疏哈希碼，然后利用得到的哈希碼來進行跨模態檢索.這些工作表明了基于哈希碼的跨模態檢索算法相對傳統的檢索算法更具優越性.

現有的基于哈希碼的跨模態檢索算法中按照是否利用樣本的標簽信息可分為有監督跨模態檢索哈希算法和無監督跨模態檢索哈希算法.無監督的算法一般是指直接利用原始樣本對之間的相關性以及原始樣本的特征將多模態數據轉換成哈希序列的方法.例如：Ding等[14]首次提出利用聯合矩陣分解(Collective Matrix Factorization Hashing，CMFH)的思想保持模態間的相似性并利用該相似性來進行跨模態檢索.Zhou等[15]提出潛在語義稀疏哈希(Latent Semantic Sparse Hashing，LSSH)算法通過利用稀疏編碼和聯合矩陣分解分別學習不同模態數據之間潛在的語義空間.相比無監督的跨模態檢索哈希算法，有監督跨模態檢索哈希算法通過同時利用原始數據的標簽和特征去學習更加高效以及有鑒別力的哈希序列.例如：zhang等[16]提出的語義相關性最大化(Semantic Correlation Maximization，SCM)算法，該算法通過將標簽信息嵌入到哈希函數學習過程，并將學習的正交投影(Orthogonal projections)作為哈希函數.Shaishav[17]等提出的跨視角哈希(Cross-View Hashing，CVH)算法，該算法通過利用標簽信息將哈希函數學習過程轉換成一個求解廣義特征值問題(Generalized eigenvalue problem).從實驗結果及分析來看，通常有監督的跨模態檢索算法檢索效果要優于無監督的跨模態檢索算法.這說明利用原始樣本的標簽信息可明顯提升跨模態檢索的準確率.語義標簽信息和原始樣本的局部幾何結構也可以用來提高檢索準確率.例如協同正則化哈希(Co-Regularized Hashing，CRH)[18]算法，該算法利用標簽信息和不同模態內部的相似度來學習哈希編碼.Tang等[19]提出的有監督矩陣分解哈希(Supervised Matrix Factorization Hashing for Cross-modal Retrieval，SMFH)算法，該算法通過利用原始樣本的語義標簽一致性和模態內數據的局部幾何一致性來學習更具鑒別能力的哈希碼.上述眾多跨模態哈希檢索算法中依然存在如下可以改進的地方：1)大部分有監督的跨模態哈希算法利用標簽信息保留哈希碼之間的相似性，沒能充分利用標簽信息挖掘樣本之間的可分性信息；2)大部分有監督跨模態檢索哈希算法僅僅考慮不相同模態數據之間的相似性結構，忽略了同一模態數據之間的相似性結構；3)大部分基于矩陣分解的有監督的跨模態檢索哈希算法在進行矩陣分解時僅僅關注分解的過程，忽略矩陣分解時的殘差結構.

為此，本文提出一種新穎的相似度保持跨模態檢索的哈希算法(Similarity Preserving Cross-Modal Hashing，SPCMH).該算法利用原始樣本對的標簽信息對SPCMH目標函數中的每個子目標函數進行約束并利用聯合矩陣分解學習多模態樣本之間的統一潛在語義空間，并兼顧模態內和模態間的相似度學習，使得1)模態內數據矩陣在分解的過程中能夠保持數據分解時的殘差結構；2)相同模態數據能夠保持數據的局部幾何結構；3)不同模態的數據能夠保持數據之間的相似性結構；4)學習到的哈希碼具有較強的鑒別能力.圖1描述了整個算法的主要流程.

圖1 算法框架圖Fig.1 Framework of our approach

本文將在第2部分介紹子空間學習、近鄰圖等相關工作.在第3部分逐步介紹SPCMH算法以及優化算法.實驗結果、參數敏感性分析在第4部分介紹.第5部分對本文的工作進行總結.本文出現的主要符號說明見表1.

表1 主要符號解釋Table 1 Explanation of main symbols

2 相關工作

2.1 子空間學習

子空間學習在機器學習、模式識別等領域中有著廣泛的應用.它可以將原始高維數據用低維度的數據表示，并盡可能多的保留原始數據的特征.常見的子空間學習方法有主成分分析(Principal Component Analysis，PCA)[20]、線性鑒別分析(Linear Discriminant Analysis，LDA)[21]、局部保持投影(Locality Preserving Projection，LPP)[22]等方法.但是這些方法大都是在同一個模態下進行子空間學習，并不適用于多模態情況下各個異構數據之間的子空間學習.在跨模態檢索領域里也有很多研究關注于學習多模態數據之間潛在子空間結構.其中典型相關分析CCA及其對應的改進算法被廣泛應用在多模態學習和跨領域學習.CCA的目標函數如式(1)所示：

(1)

2.2 近鄰圖

近鄰圖能夠很好地揭示原始數據的局部幾何結構，因此在數據挖掘和模式識別等領域中有著廣泛的應用[25,26].基于近鄰圖正則化的學習方法首先是構造一個表示局部關系的相似矩陣，然后通過構造類似如下所示的優化目標進行學習：

(2)

P為需要學習的線性投影矩陣，W的定義可以如下：

(3)

xi∈Nk(xj)表示樣本xi是樣本xj的前k個最鄰近的樣本之一，也意味著這兩個樣本不但相似而且具有較大的概率歸屬于同一類.通過這種方式可以讓原始的樣本通過投影之后在對應的空間里依然保持原始樣本之間的近鄰關系.

3 相似度保持哈希

3.1 相關矩陣說明

不同模態內部樣本的局部幾何結構信息對于保持該模態內部的近鄰關系起到非常重要的作用，而模態間的相似性度量側重點在于挖掘模態與模態之間的潛在關聯.這些特征對充分保留原始樣本的特征有重要意義.接下來將給出幾個在本文中用到的矩陣的說明.

(4)

語義關聯矩陣R表示模態X和Y之間的標簽關系.如果來自圖像模態中的樣本xi與來自文本模態的樣本yi具有相同的標簽信息，則Rij的值為1，反之為0.具體公式如下：

(5)

3.2 模型介紹

3.2.1 分類器學習

哈希碼要具有一定的鑒別能力.假設樣本xi對應的哈希碼bi，通過引入矩陣W轉化bi到對應的標簽li，即：

li=WTbi,i∈{1,…，n}

(6)

其中W∈Rr×c為線性分類器參數(c是對應數據集類別的個數).通過求解如下的目標，可以得到W的解：

(7)

3.2.2 哈希函數學習

通過聯合矩陣分解可以將不同結構的數據映射到統一的潛在語義空間里，進而探究異構數據之間的關聯[27-29].據此，我們可以通過線性投影矩陣U，V分別將圖像模態及文本模態的數據映射到共同的潛在語義空間中去，這樣可極大的保留原始多模態樣本對之間的特征.本文通過使用相似度矩陣來約束矩陣S(m)分解的殘差來進一步保持不同模態數據的局部結構.因此我們定義如下的目標函數：

(8)

其中U∈Rd1×k，V∈Rd2×n是線性投影矩陣，即投影原始數據為對應的哈希編碼.通過使用S(m)約束原始圖像和文本數據的分解殘差，使得相似的樣本具有相似的殘差，從而保證學習到的哈希碼能夠保持數據的局部結構通過最小化式(8)可以使得不同模態的樣本投影后能夠逼近對應的哈希碼.

3.2.3 模態內部相似度學習

有效利用模態內部數據之間的局部幾何結構可使得學習到的統一潛在語義空間能夠盡可能的保留原始空間的近鄰結構.

(9)

通過變換，式(9)可轉換為如下形式：

(10)

3.2.4 模態間相似性學習

表示相同語義的樣本對在投影后的目標空間里應該有相似的結構，因此，針對模態間相似性學習我們構造如下的目標函數：

(11)

如果來自圖像模態的樣本xi與來自文本模態的樣本yj具有相同的標簽，則Rij的值為1.通過最小化式(11)可使得來自于不同模態但是相同類別的樣本通過線性投影變換之后依然能保持相似的結構并且能夠聚集在一起.

通過變換，式(11)可轉換為如下形式：

(12)

(13)

3.3 整體目標函數

結合分類器學習、哈希函數學習、模態內部相似度學習和模態間相似度學習，完整的SPCMH算法的總體目標函數如下：

(14)

(15)

3.4 優化算法

目標函數式(14)是一個非凸優化問題.但是，對于每一個優化變量是一個凸優化問題[30].我們使用如下的迭代優化來解決優化目標式(15)：

W=(BBT+ηI)-1BLT

(16)

其中I∈Rr×r表示單位矩陣，(.)-1表示矩陣的逆.

Step2.(更新U，V)：固定W，V，B，式(15)可轉變為：

(17)

U=[2βX(Dv-Sv)XT+2γXD3XT+2ηI]-1 (2αX(Sv)TBT)+γXRYTV+γXRYTV

(18)

同樣地，固定W，U，B，式(15)也可轉變為：

(19)

V=[2βY(Dt-St)YT+2γYD4YT+2ηI]-1(2αY(ST)TBT+γYRTXTU+γYRTXTU)

(20)

Step3.(更新B)：固定W，U，V，式(15)也可轉變為：

(21)

-2WL+2WWTB+α(B(Dv)T+BDv)-2αUTX(Sv)T+α(B(Dt)T+BDt)-2αVTY(St)T=0

(22)

式(22)可變換為：

AB+CB=E

(23)

其中：

A=WWT.C=α(Dv+Dt).E=WL+α(UTX(Sv)T+VTY(St)T)

這是一個典型的希爾維斯特方程(Sylvester).

當輸入一個任意模態的檢索樣本qi時，SPCMH算法會通過相應的哈希函數生成對應的哈希序列bi=sgn(UTqi) orbi=sgn(VTqi).算法1描述了SPCMH算法更新迭代的具體步驟.

算法1.相似度保持跨模態哈希

輸入：圖像矩陣X，文本矩陣Y，樣本標簽矩陣L，關聯矩陣Sv、St、R等.隨機初始化哈希矩陣B、線性變換矩陣U，V與分類器W.

輸出：哈希碼B，以及線性變換矩陣U，V.

1.中心化圖像矩陣X，文本矩陣Y，初始化矩陣L，S與R；

2.重復步驟3-步驟5；

3.通過式(16)更新W；

4.通過式(18)、式(20)更新U，V；

5.通過式(23)學習矩陣B；

6.直至收斂.

4 實 驗

本部分將詳細介紹SPCMH算法在Wiki[31]、NUS_WIDE[32]、MIRFlickr-25k[33]3個基準數據集上的實驗結果與分析，每一個數據集都包含若干個圖像及文本對.此外本文還對算法的各個參數的敏感性進行了分析.值得注意的是，本算法也可直接應用到其它模態數據的交叉檢索，例如圖像-視頻、文本-音頻等.

4.1 數據集介紹

Wiki數據集：總共包含10個類別(Categories)共2，866個樣本，每一個類代表不同的語義.這些樣本都是從維基百科(Wikipedia)網站上收集而來，每一個樣本對都包含一張圖片和對應的文本，兩者共同描述同一個對象.在數據特征上，數據集中每張圖片都是用128維的SIFT(Scale-invariant feature transform)特征向量進行表示，每個文本用10維的Latent Dirichlet Allocation(LDA)特征向量進行表示.為了實驗對比，實驗時隨機選取2，173個數據對構成訓練集，剩余的693個數據對作為測試集.

NUS_WIDE：新加坡國立大學公開的數據集，總共包含269，648張從Flickr網站上收集的圖片.每一個樣本對都有一張圖片與對應的文本進行注釋，每張圖片上有多個標簽，全部樣本被分為81個類別.為了實驗對比，本文篩選了樣本數量最多的10個類別進行實驗，總共有186，577個樣本對.其中圖片用500維的視覺詞袋SIFT直方圖表示，對應的文本用1，000維的BOW向量表示.實驗時隨機選取5，000圖像-文本對構成訓練集，然后在余下的數據中隨機挑選1，866個圖像-文本對作為測試集.

MIRFlickr-25k：包含25，000張從Flickr網站上下載下來的圖像以及附帶的文本標記構成，每一個數據樣本分別屬于24個語義類之一.每一張圖像也都對應著唯一的與其相關的文本標簽.用150維直方圖特征(Edge Histogram)表示圖像數據，對應的文本用500維的特征向量表示.數據集樣本選擇時，本文剔除那些標簽不超過20個的樣本.余下的數據集中隨機選取5，000對圖像-文本對作為訓練集，836個圖像-樣本對為測試集.

4.2 評估度量及參數設置

本文選取跨模態信息檢索中最常用的平均查準率Mean Average Precision(mAP)作為主要指標評價算法的整體性能.

平均準確率(Average Precision，AP)定義如下：

(24)

其中M是被檢索數據集中與檢索數據樣本相關聯的數據的個數，G表示前G個查詢結果.Precision(r)表示被檢索到的前項數據的精確度，δ(r)=1時表示被檢索到的第r個數據項與要檢索的數據是相關聯的，相反δ(r)=0時表示被檢索的第r個數據項與要檢索的數據一定不是同一類.在Wiki數據集中，具有相同標簽的樣本稱之為相似樣本，在MIRFlickr-25k、NUS_WIDE多標簽數據集上，至少有一個相同的標簽則稱為相似樣本.

計算每個樣本的平均準確率的平均值即為mAP：

(25)

Q是查詢集合的大小.本文主要驗證兩種跨模態檢索任務，一種是利用圖像去檢索相關文本，即“Img2Txt”，另一種是文本檢索相關圖片，即“Txt2Img”.本文實驗是在Matlab2016a，Intel(R) Core i9CPU @3.6GHz環境下進行的.

在后續試驗中，我們設置η的值為1，對于α，β，γ我們從{0,1e-6，1e-5，…，1}中選取最優組合.K-近鄰的參數設置為5.為了全面的評估本文算法，哈希碼長度設置為16bits、32bits、64bits以及128bits.

4.3 實驗結果與分析

為了驗證算法SPCMH的有效性，本文選取了6個相關的跨模態檢索算法進行對比.具體為LSSH、CMFH、CRH、SMFH、DCH、語義保持哈希(Semantics-preserving hashing，SePH-km)[34].

其中LSSH、CMFH為無監督算法，CRH、SCM、SePH、DCH為有監督算法.LSSH通過稀疏編碼和聯合矩陣分解分別學習不同模態數據之間潛在的語義空間；CMFH是無監督的聯合矩陣分解哈希，通過利用聯合矩陣分解來學習多模態統一的潛在空間并且兼顧了模態之間的關聯性.但該算法未能充分利用標簽信息；CRH既利用了標簽信息也考慮了樣本之間的關聯.但該算法未能考慮模態內部之間的關聯；SMFH算法雖然利用了原始樣本的標簽信息，但是沒能充分利用給定的標簽信息挖掘樣本之間的分類信息.SePH算法通過利用概率分布最小化Kullback-Leibler散度來學習哈希碼.DCH算法利用了標簽信息指導不同模態樣本的哈希函數學習.

實驗過程中，對比算法的實驗參數都是依據相關文獻建議中的參數進行設置的.本文取5次相應的實驗結果的平均值作為最終的實驗結果.

4.3.1 在Wiki數據集上的結果

實驗中設置α=1e-6，β=1e-6，γ=0.001附件時可取得較高的mAP值.相應的結果如表2所示.

表2 在Wiki數據集上的mAP值Table 2 MAP results on Wiki data set

由表2可知：

1)本文提出的SPCMH算法的mAP值在整體上均優于對比算法.特別是在Txt2Img檢索任務上，SPCMH算法相對無監督算法CMFH等最高提升了約19%，相對于有監督算法DCH最高提升約3%.這說明SPCMH算法確實能夠有效地提高交叉檢索的準確率；

2)整體上有監督的跨模態哈希檢索算法效果要優于無監督的算法，這說明有效利用語義標簽信息可以提升檢索的準確率；

3)總體上，Img2Txt任務的mAP值要低于Txt2Img任務.其原因可能是因為通常文本的特征描述相對于圖像的特征描述更接近于實際樣本的語義特征.

4.3.2 在NUS_WIDE數據集上的結果

本文進一步在數據集NUS_WIDE上進行實驗.算法中相關參數范圍的設定如同在Wiki數據集上一樣，實驗結果如表3所示.

從表3中可知：

表3 NUS_WIDE數據集上的mAP值Table 3 MAP results on NUS_WIDE data set

1)SPCMH算法在NUS_WIDE數據集上的表現也比較穩定，相對于無監督算法LSSH、CMFH或者是有監督的跨模態交叉檢索哈希算法DCH、SMFH等，SPCMH在Img2Txt與Txt2Img任務上mAP的值都有明顯的提升.尤其是相比有監督的DCH，SPCMH在Img2Txt任務上最高提升約20%，在Txt2Img任務上最高提升約12%.主要原因可能是有效地利用語義標簽的同時在聯合矩陣分解時保留了原始數據的殘差結構；

2)實驗中可以發現隨著哈希編碼的位數增加SPCMH算法在Img2Txt任務和Txt2Img任務的mAP值呈現出平穩的增長趨勢，這說明在一定哈希碼長度范圍內，越長的哈希碼有利于保持更多地鑒別信息.而有的算法甚至出現了略微下降的現象，例如：LSSH算法在Txt2Img任務上，CMFH算法在Img2Tx任務上.這主要的原因可能是這些算法隨著哈希碼長度的增加，可能引入了噪聲等負面因素，導致算法性能下降；

3)對比無監督算法CMFH和有監督算法SMFH、DCH等，SPCMH在mAP值上有明顯的提升.原因可能是本文將標簽信息應用到優化目標的各個部分對提升檢索準確率有很大的幫助.

4.3.3 MIRFlickr-25k數據集上的結果

在數據集MIRFlickr-25k上的參數的設置依然如上述兩個數據集一樣.實驗結果如表4所示.

從表4中可知：

表4 MIRFlickr-25k數據集上的mAP值Table 4 MAP results on MIRFLICKR-25k data set

1)SPCMH算法在MIRFlickr-25k數據級上明顯優于對比的無監督或者是有監督的跨模態檢索哈希算法.在Img2Txt任務上相對于表現最好的DCH算法提升了約14%，在Txt2Img任務上相對于DCH提升了約4%；

2)大部分算法隨著哈希碼長度的增加mAP的值也相應地增加，但是，SPCMH算法的增長并不是很明顯.這說明了該算法在實際應用中能用較少的哈希碼表示原始樣本的特征，相比其他算法可以進一步節省存儲內存以及提升運算效率；

3)SPCMH算法的效果都要明顯高于另一個有監督算法SMFH.其中在Img2Txt任務上mAP提升約16%，在Txt2Img任務上提升約10%.本文算法明顯優于SMFH的原因可能是：1.聯合矩陣分解過程中保持數據的殘差結構可以使得哈希碼保持數據的局部幾何結構；2.模態間的相似性學習對提高哈希碼鑒別能力十分重要.

4.3.4 參數敏感性分析

本文進一步分析了優化目標式(14)中各個參數的敏感性.因為在所有的實驗中η=1，所以在本節不在對此參數進行討論.在分析參數α，β，γ時采用固定其中一個分析另外兩個參數對算法性能的影響.本文選擇NUS_WIDE數據集作為基準數據集，哈希長度固定為32bits.整體上α可視為哈希函數學習過程的權重，β為不同模態內部的相似度學習權重，γ為不同模態間的相似度學習權重.

圖2中(a)(d)對應固定γ，分析β、α在區間{0,1e-6,1e-5，…，1}范圍內在Img2Txt和Txt2Img兩個任務上mAP數值.相應的(b)(e)，(c)(f)分別表示固定β，α而分析另外兩個參數時的結果.圖(a)(d)對應的是固定γ=1e-3.由結果可知當α∈{1e-1,1e-2,1e-3}且β∈{1e-6,1e-5,1e-4,1e-3}時算法可取得較高的mAP值.圖(b)(e)是固定β=1e-4得到的結果.由圖可知當α∈{1e-3,1e-2,1e-1}且γ∈{1e-3,1e-2,1e-1}時可得到較高的mAP值.圖(c)(f)中說明在實際應用中，固定α=1e-3，當γ∈{1e-1,1e-2,1e-3}區間時可得到較高的mAP值，此時的最優值范圍區間較大.另外當α，β，γ中其中一個參數數值為0時，相比于非0時對應的mAP值有明顯的降低.綜上可知該算法對參數α，β，γ在{0，1e-6,…，1}區間變換時大都能取得較高的mAP值，這說明了SPCMH算法的幾個參數在該區間內不敏感.另外，由于參數α，β，γ分別控制算法的各個部分的重要性，所以上述的分析結果說明本算法的哈希函數學習部分、模態內部相似度保持部分、模態之間相似度保持部分對提升算法檢索的準確率都至關重要.

圖2 參數敏感性分析Fig.2 Parameter sensibilityanalysis

5 結 論

本文提出一種新穎的相似度保持跨模態檢索哈希算法.該算法將原始樣本的標簽信息嵌入到算法的每一個子目標的學習過程中，同時本算法通過在聯合矩陣分解過程中保持數據的殘差結構，以提高跨模態檢索的檢索性能在3個常用的基準數據集Wiki、NUS_WIDE、MIRFlickr-25k的實驗結果顯示，與相關的跨模態哈希檢索算法相比，SPCMH算法能更好地提升跨模態檢索性能.