在線圖正則化非負矩陣分解跨模態哈希

羅雪梅，鄭海紅，安亞強，王笛

西安電子科技大學 計算機科學與技術學院，西安710071

隨著社交網絡的發展，爆炸性增長的多媒體數據如潮水一般涌入互聯網中，數據類型呈現出多模態特征，跨模態信息檢索也因此吸引了大量科研工作者的研究興趣。跨模態哈希檢索的基本思想是利用不同模態的樣本對信息，學習不同模態的哈希變換，將不同模態數據從原始特征空間映射到一個公共漢明空間，通過二進制編碼在漢明空間中保持數據的相似性，實現快速的跨模態檢索[1-5]。基于哈希的跨模態檢索即通過將不同模態的原始特征在同一漢明空間映射為一定長度的二進制編碼，從而節省存儲空間，提升檢索速度。

跨模態哈希檢索算法雖然在面對海量多媒體數據時，取得了較好的檢索結果。但大多數哈希檢索算法采用批量學習模式，即利用當前累積的所有訓練樣本學習哈希函數。然而，由于數據不斷增長，現有的哈希檢索方法無法根據數據的變化自適應更新模型，而重新進行哈希學習勢必會帶來巨大的時間和計算開銷。另一方面，同時利用海量數據訓練哈希函數，具有較大的存儲和計算需求，降低了哈希方法的適用性。

為了應對上述挑戰，提出了在線跨模態哈希方法。該方法從連續到達的數據中逐步更新哈希函數，以適應數據流的變化，同時將新數據編碼為緊湊的二進制代碼，以有效地處理流數據。同時，由于哈希函數只根據當前數據進行更新，與基于批量學習的模式相比，在線跨模態哈希方法大大降低了計算成本和內存需求。

在線跨模態哈希（online cross-modal hashing,OCMH）[6]提出了一種無監督方法，利用矩陣分解將特征矩陣分解為共享潛碼矩陣和支持在線學習的轉移矩陣，然后通過共享潛碼矩陣學習哈希碼。然而，由于該方法是無監督模式，訓練數據點的標簽信息并沒有被用來提高哈希函數的質量，從而降低了檢索性能。動態多視圖哈希（dynamic multi-view hashing，DMVH）[7]通過構造字典來表示多模態數據并支持在線哈希碼生成，根據流數據的變化動態地增加哈希碼的長度。然而，由于數據不斷變化，其生成的哈希碼通常具有較高的冗余度和較長的位長。在線潛在語義哈希（online latent semantic hashing,OLSH）[8]是一種在線監督哈希方法，其將離散標簽映射到連續潛語義空間中獲得哈希碼，僅利用新到達的多媒體數據點對哈希函數進行有效的再訓練，同時保留了舊數據點的語義相關性。然而該方法需要頻繁通過標簽信息矩陣來更新語義相似性矩陣，計算復雜度較高。

本文提出一種新的監督在線跨模態哈希方法，稱為在線圖正則化非負矩陣分解跨模態哈希（online graph regularized non-negative matrix factorization crossmodal hashing，OGNMFH）。首先利用非負矩陣分解，學習不同模態數據的潛在公共因子，使不同模態數據在漢明空間中具有公共的哈希碼，從而保持模態間的相似性。然后利用標簽信息生成相似度矩陣，對矩陣分解的過程進行監督，保持數據的局部幾何結構，從而保持模態內的相似性。如圖1 所示，OGNMFH 根據當前到達的數據，增量地更新哈希函數，并生成哈希碼。每次更新只需要計算當前數據塊，不需要對舊數據重新計算，因此不需要存儲舊數據，緩解了存儲壓力，提高了計算效率。

圖1 OGNMFH 檢索方法框圖Fig.1 Flowchart of OGNMFH retrieval method

本文的主要貢獻包括四方面：

（1）提出一種在線跨模態哈希方法OGNMFH。該方法利用非負矩陣分解對維度較高的不同模態數據提取語義特征，將不同模態數據映射到公共的漢明空間，并通過圖正則化來保持多模態數據之間的語義相似性。

（2）利用建立緩沖區的方式增量處理輸入數據，在線學習哈希函數，可以有效處理大規模數據。

（3）充分利用局部流形結構信息和數據的類別標簽信息，從而學習到更有判別性的哈希碼。

（4）基準數據集上的實驗結果表明，本文提出的在線跨模態哈希算法可有效提升在線哈希學習的檢索精度。

1 相關工作

非負矩陣分解（non-negative matrix factorization,NMF）[9]是一種經典的數據降維方法，其基本思想可以簡單描述為：對于任意給定的非負矩陣X∈Rm×n，尋找非負矩陣U∈Rm×k和非負矩陣V∈Rn×k，使得X≈UVT。其中，矩陣X表示原始數據矩陣，矩陣U稱為基矩陣，矩陣V稱為系數矩陣或權重矩陣，k?min(m,n)。NMF 問題可以通過最小化下式來求解基矩陣U和系數矩陣V：

其中，||·||2表示歐幾里德范數。傳統的NMF 在歐氏空間中進行因式分解，不能得到令人滿意的解。事實上保持數據集的底層幾何結構對于非線性降維是非常重要和有效的。圖正則化非負矩陣分解（graphregularized non-negative matrix factorization，GNMF）[10]將幾何結構融入到NMF 中，與傳統的NMF 相比，其性能有顯著的提高。GNMF 基于以下假設：如果兩個數據xi和xj在原始數據分布中的幾何結構是接近的，那么它們在新的空間中的表示應該也是接近的。上述假設表示如下：

因此，GNMF 的損失函數定義如下：

然而，由于NMF 和GNMF 都是在批處理模式下工作的，均要求數據矩陣駐留在內存中，這給計算和存儲帶來了巨大的壓力。而數據以流式增加時，存儲需求更高，計算也更復雜。在線圖正則化非負矩陣分解（online graph-regularized non-negative matrix factorization，OGNMF）[11]以增量的方式處理傳入的數據。首先對在線實現GNMF 算法的瞬時目標函數進行建模，建立一個緩沖區，將數據依次添加到緩沖區，當數據量達到緩沖區設定閾值時，即進行更新訓練。然后，移除緩沖區中最早的一個數據，循環迭代，直到全部數據訓練結束，最后推導迭代乘法更新規則來求解所提出的OGNMF 模型。

給定流式數據集X，t時刻OGNMF 的目標函數定義如下：

其中，Xt是t時刻緩沖區中的數據樣本；Vt是系數矩陣；Ut是基矩陣；Lt是t時刻緩沖區中數據樣本的圖權重矩陣Wt的拉普拉斯矩陣。

2 在線圖正則化非負矩陣分解哈希

本章將詳細介紹所提出的在線圖正則化非負矩陣分解跨模態哈希方法。在不失一般性的情況下，為了簡化表示，首先關注由圖像和文本組成的雙模態數據的OGNMFH 方法，然后將其擴展到多模態情況。

2.1 符號和問題描述

對于在線跨模態哈希，目的是對于每一個模態都要學習相應的哈希函數，第m個模態的哈希函數表示為：

其中，Pm是映射矩陣，sign(·)是符號函數。通過哈希函數可以得到每個模態數據對應的哈希碼B∈{-1,1}n×k，k為哈希編碼長度。

2.2 目標函數

本文提出的在線圖正則化非負矩陣分解跨模態哈希檢索算法在t時刻的目標函數Ot構建如下：

2.3 在線優化

算法1第t輪在線圖正則化非負矩陣分解跨模態哈希檢索算法

通過在線學習哈希函數，獲得了所有訓練數據的哈希碼，對于樣本外數據，OGNMFH 方法可快速生成該樣本的哈希碼。假設獲得一個新的查詢樣本xk，可通過下式計算得到它對應的哈希碼bk：

其中，Pk是數據xk對應模態的哈希函數。OGNMFH方法的整個訓練及查詢過程如算法2 所示。

算法2在線圖正則化非負矩陣分解跨模態哈希

2.4 復雜度分析

2.4.1 時間復雜度分析

OGNMFH 方法的時間復雜度主要由在線優化過程決定。每一輪在線優化共有5 個矩陣變量需要更新。由于在線更新過程使用緩沖區技術，每次通過更新緩沖區中的數據實現在線學習，因此更新每個變量的復雜度是O(s)，s是緩沖區的大小。由于迭代的數量通常較小，因此，整個網絡優化過程的時間復雜度近似為O(s)，它的值與緩沖區的大小成線性關系。

2.4.2 空間復雜度分析

OGNMFH 通過建立緩沖區實現在線學習，每次保留中間矩陣，以便在下一輪更新。這些矩陣的大小只與哈希碼長度和特征向量有關，占用的內存空間不大。在使用的所有變量中，只有數據矩陣的大小和統一表示矩陣與緩沖區大小有關。因此，一般來說，OGNMFH 的整體空間復雜度為O(s)，在大規模數據檢索任務中效率是非常高的。

3 實驗

3.1 數據集介紹

為了驗證本文所提OGNMFH 算法的有效性，在3個經典的跨模態數據集MIRFlicker[12]、NUS-WIDE[13]、MSCOCO[14]上分別進行了在線跨模態實驗，并在同等實驗條件下和其他方法進行了對比實驗。

MIRFlickr數據集由來 自Flickr 網站的25 000 個圖像-文本數據對組成。每個數據對都與24 個語義標簽中的一個或多個關聯。選擇一個包含20 015 個數據對的子集，這些數據對與出現頻率最高的20 個標簽對應。每個圖像表示為一個由VGG19 提取的4 096 維非負深度特征。通過對由VGG19 提取的4 096 維文本特征進行PCA（principal component analysis）處理，然后進行非負處理，將每個文本表示為一個1 387 維非負特征，每個標簽表示為一個24 維只包含0 和1 的向量。隨機選擇2 000 個圖像文字對作為查詢集，剩下的數據對作為訓練集，為了支持在線學習，訓練集被分割為9個數據塊，前8個數據塊包含2 000個數據對，最后一個數據塊包含15個數據對。

NUS-WIDE 數據集由來自Flickr 網站的269 648對圖像-文本數據組成。每個數據對都與81 個語義標簽中的一個或多個相關聯。選擇一個包含186 577個數據對的子集，這些數據對與出現頻率最高的10個標簽對應[15]。每個圖像表示為一個由500 維SIFT（scale-invariant feature transform）特征所構成的詞包特征，每個文本表示為一個1 000 維的詞包特征，每個標簽表示為一個10 維只包含0 和1 的向量。隨機選擇2 000 個圖像文字對作為查詢集，剩下的數據對作為訓練集。為了支持在線學習，訓練集被分割為37 個數據塊，前36 個數據塊包含5 000 個數據對，最后一個數據塊包含4 577 個數據對。

MSCOCO 數據集由來自Flickr 網站的122 218對標記為圖像-文本的數據對組成。每個數據對都與80 個語義標簽中的一個或多個相關聯。通過對VGG Net 的Caffe 實現提取的4 096 維圖像深度特征進行非負處理，將每幅圖像表示為一個4 096 維非負特征。通過對VGG Net 的Caffe 實現提取的4 096 維文本深度特征進行PCA 處理，然后進行非負處理，將每個文本表示為一個128 維非負特征，每個標簽表示為一個80 維只包含0 和1 的向量。隨機選擇2 000 個圖像文字對作為查詢集，剩下的數據對作為訓練集。為了支持在線學習，訓練集被分割為25 個數據塊，前24 個數據塊包含5 000 個數據對，最后一個數據塊包含218 個數據對。

3.2 參數設置

本文所提出的在線圖正則化非負矩陣分解跨模態哈希檢索方法（OGNMFH）共有5 個參數：圖像模態權重系數λ1、文本模態權重系數λ2、圖正則化參數α、表示平衡項參數μ以及正則化項參數γ。在本文實驗中設定λ1=0.5，λ2=0.5，α=0.001，μ=0.001，γ=1。另外迭代閾值設置為0.01。

3.3 實驗結果與分析

在本文實驗中，進行兩種類型的跨模態檢索任務：圖像查詢和文本查詢。為了證明本文所提的OGNMFH 方法在流數據點上的有效性，設置了在線進行的實驗，數據點以流的方式到達。通過分割訓練數據模擬流數據，整個在線檢索階段包括若干輪，在每一輪，一個新的數據塊被添加到數據庫，并評估檢索性能。

圖2、圖3 和圖4 是本文提出的在線圖正則化非負矩陣分解跨模態哈希（OGNMFH）方法和在線潛在語義哈希（OLSH）、在線跨模態哈希（OCMH）、動態多視圖哈希（DMVH）三種對比方法在數據集MIRFlickr、NUS-WIDE 和MSCOCO上的mAP曲線圖。本次實驗比較了4 個不同哈希碼長度下的mAP值，分別是16 bit、32 bit、64 bit 和128 bit。實驗結果表明，使用流式數據在線更新哈希模型，本文所提出的OGNMFH 方法的檢索性能比其他對比方法更好，證明了語義信息可以提高檢索性能，本文所提方法是有效的。

圖2 MIRFlickr 數據集上不同哈希碼長度的mAP 曲線Fig.2 mAP curve under different sizes of hash on MIRFlickr dataset

圖3 NUS-WIDE 數據集上不同哈希碼長度的mAP 曲線Fig.3 mAP curve under different sizes of hash on NUS-WIDE dataset

圖4 MSCOCO 數據集上不同哈希碼長度的mAP 曲線Fig.4 mAP curve under different sizes of hash on MSCOCO dataset

圖5、圖6 和圖7 顯示了所有方法在3 個數據集上哈希碼長度為32 bit 的mAP 值隨輪數的變化曲線。可以看出，每種方法的mAP 值一般都隨著可用訓練數據點的增加而增加。這反映出隨著輪數的增加，在線哈希方法可以根據數據的變化自適應更新模型。本文所提出的OGNMFH 方法在每一輪的所有數據集上的性能都有顯著的提高，總體呈現波動上升的趨勢，說明其性能較好。

圖5 MIRFlickr數據集上隨數據輪數增長mAP 曲線Fig.5 mAP curve with increasing of data rounds on MIRFlickr dataset

圖6 NUS-WIDE 數據集上隨數據輪數增長mAP 曲線Fig.6 mAP curve with increasing of data rounds on NUS-WIDE dataset

圖7 MSCOCO 數據集上隨數據輪數增長mAP 曲線Fig.7 mAP curve with increasing of data rounds on MSCOCO dataset

3.4 訓練時間分析

圖8顯示了每種方法在NUS-WIDE數據集上，哈希碼長度設為32 bit，隨數據集增加后訓練時間變化曲線。從圖中可以看出，在所有在線哈希方法中，OGNMFH比OCMH 略慢，但檢索效果更好。而相較于DMVH 和OLSH，OGNMFH 的計算復雜度相對更低，訓練速度要快很多。因此，OGNMFH 有較好的訓練效率。

圖8 NUS-WIDE數據集上所有方法訓練時間Fig.8 Training time of all methods on NUS-WIDE dataset

3.5 參數敏感性分析

本節詳細分析了在MIRFlickr數據集上OGNMFH方法各個參數的敏感性，其中哈希碼長度設置為32 bit。通過每次固定其余參數，在一定范圍內變化其中一個參數來對各個參數進行分析。

圖9 顯示了OGNMFH 方法的mAP 值隨λ1和λ2變化的曲線。從圖中可以發現，控制兩個模態非負矩陣分解項的權重系數λ1和λ2，參數變化對模型最終的性能影響較小，因此通過經驗將其設置為λ1=λ2=0.5。

圖9 參數λ1 和參數λ2 敏感性測試mAP 曲線Fig.9 mAP curve of parameter sensitivity test about λ1 and λ2

圖10 顯示了圖正則化參數α敏感性測試mAP曲線。從圖中可以看出，當α在[10-5,10-3]內時，本文方法的mAP 值較高，性能較好，因此在本文方法訓練時設置α=10-3。

圖10 參數α 敏感性測試mAP 曲線Fig.10 mAP curve of parameter sensitivity test about α

圖11 顯示了平衡項參數μ敏感性測試mAP 曲線。從圖中可以看出，當μ小于等于10-1時，OGNMFH方法的mAP 值較高，性能較好，因此在OGNMFH 方法訓練時設置μ=10-3。

圖11 參數μ 敏感性測試mAP 曲線Fig.11 mAP curve of parameter sensitivity test about μ

圖12 顯示了正則化參數γ敏感性測試mAP 曲線。從圖中可以看出，當γ的值大于10-1時，本文方法可以達到穩定的性能，在本文方法訓練時設置γ=100。

圖12 參數γ 敏感性測試mAP 曲線Fig.12 mAP curve of parameter sensitivity test about γ

4 結束語

本文提出了一種新的有監督在線跨模態哈希檢索算法，稱為在線圖正則化非負矩陣分解跨模態哈希。它增量地更新哈希函數，并通過新到達的數據生成哈希代碼。通過一次處理一個數據塊，可以節省大量的計算和存儲空間。該算法首先通過非負矩陣分解學習跨模態數據公共語義；然后利用標簽信息建立相似度矩陣，對非負矩陣分解過程進行監督，使在原始數據空間中相似的樣本學習到的哈希碼也相似，不相似的樣本學習到的哈希碼不相似，保持哈希碼模態內和模態間相似度；最后松弛離散約束，在線優化目標函數，學習到質量更高的哈希碼，從而提高檢索性能。在三個經典數據集上的大量實驗表明，該方法優于幾種現有的先進方法。