捕獲局部語義結構和實例辨別的無監督哈希?

李長升,閔齊星,成雨蓉,袁 野,王國仁

1(北京理工大學 計算機學院,北京 100081)

2(電子科技大學 計算機科學與工程學院,四川 成都 611731)

隨著互聯網的快速發展以及數據(例如圖片、視頻、文檔等)的爆炸式增長,如何快速地檢索到用戶需要的信息,已經成為學術界和工業界研究的熱點問題之一.作為已經被公認為是一種非常高效地用于大規模信息檢索的手段之一,哈希技術近年來得到了突飛猛進的發展.從原理上來講,哈希方法通常將高維連續空間的數據(例如圖像、視頻、文本等)映射到一個低維的二進制空間中(也就是,哈希空間),如圖1 所示.在映射的過程中,期望在哈希空間中能夠保持原始空間的信息.由于使用二進制編碼對數據進行特征表示,哈希方法可以極大地減少存儲代價以及計算復雜度,并因此可以快速地對大規模數據集進行檢索查詢.因此,哈希方法可以被視為一種支持大規模數據檢索的高效特征學習的新技術.由于其具有廣泛的潛力,目前為止,哈希方法已經被廣泛地應用于各種各樣的任務中,包括跨媒體檢索[1]、推薦系統[2]、復制檢測[3]等.

Fig.1 Brief introduction of Hashing圖1 哈希過程的簡單介紹

早先的哈希方法大部分是不依賴于數據的,例如,經典的局部敏感哈希(locality sensitive Hashing,簡稱LSH)[4]試圖通過隨機映射的方式產生嵌入表示.這類技術的一個優勢是在極限情況下,隨著哈希編碼位數的增加,隨機映射可以保持輸入間的距離.由于這類方法產生哈希函數不依賴于數據集本身,因此得到的哈希函數未必是全局最優的.近年來,數據依賴的哈希方法在學術界得到了更多的關注,并得到迅速發展[5].這類方法對目標數據集進行學習建模,從而產生更為精確簡潔的哈希編碼.由于數據依賴的方法常常獲得令人滿意的效果,因此各種各樣的哈希方法逐漸被提出.從哈希編碼學習過程中是否有監督信息介入的角度進行劃分,現有的哈希方法大致可分為監督的方法[6?8]、半監督的方法[9,10]和無監督的方法[11?17].監督的哈希方法通常利用監督的信息(例如標簽信息)進行哈希編碼學習.監督的信息包括單個樣本的標簽信息、成對樣本的標簽信息以及序列標簽信息.代表性的方法包括監督離散哈希(supervised discrete Hashing,簡稱SDH)[18]、快速監督哈希(fast supervised Hashing,簡稱FastH)[6]、基于排序的監督哈希(ranking-based supervised Hashing,簡稱RSH)[19]、卷積神經網絡哈希(convolutional neural network Hashing,簡稱CNNH)[20].監督的方法存在著一些問題:首先,監督的方法通常要求哈希函數具有較強的辨識力,否則難以保證模型的性能.實際場景中的數據相對復雜,往往需要較多的編碼來保證模型的精度,然而這無形之中增加了存儲的空間.Wang 等人[9]提出了半監督的哈希方法,他們通過對數據對進行學習,保證相似的數據對的哈希編碼仍然是相似的,不相似的數據對其哈希編碼仍然是不相似的,同時要求哈希編碼在沒有標簽的數據上的信息熵最大化.Mu 等人[10]對部分數據進行人工標注,標注數據對為語義上相似的數據對和語義上不相似的數據對,利用二次規劃對問題進行求解,從而獲得較為精確地哈希函數.無監督的哈希方法沒有利用任何的監督信息,而是僅僅利用數據的特征信息進行學習訓練.代表性的工作包括迭代量化方法(iterative quantization,簡稱ITQ)[11]、離散圖哈希(discrete graph Hashing,簡稱DGH)[13]、大規模圖哈希(scalable graph Hashing,簡稱SGH)[21]等等.無監督哈希在學習過程中由于沒有使用標簽信息,節省了數據標注的成本,因此簡單易實現.然而,也正因為沒有涉及監督信息,無監督哈希問題是非常具有挑戰性的.因此,本文主要研究無監督哈希問題.

在過去幾年,盡管有大量的無監督哈希方法相繼被學者提出來,然而這些方法仍存在著下面的問題:1)由于數據是沒有標簽信息的,如何精確地構建數據間的語義相似結構仍然是一個開放的問題;2)在哈希編碼的學習過程中,大部分方法僅僅試圖去保持數據的語義結構,然而忽視了哈希編碼的辨別力.眾所周知,數據特征表征的辨別力對于下游任務起著非常關鍵的作用[22],因此,如何提高哈希編碼的辨別力是值得探索的.

基于以上情況并受到實例分辨力工作[23]的啟發,本文提出了一種新的深度無監督的哈希學習方法:通過自監督學習對數據的語義相似性結構進行精確描述;提出一個新的目標損失函數,期望在哈希空間中,數據的語義結構能夠得到保持,同時能夠提升哈希編碼的辨識力.另外,本文增加了一個規則項以期減少引入松弛帶來的損失.本文提出的框架是端到端可訓練的,并采用標準的反向傳播算法進行優化.本文對圖像分類模型VGG-F 模型[24]做了以上改造及訓練,通過在FLICKR25K 和NUSWIDE 兩個常用的數據集上與目前流行的無監督哈希學習方法進行檢索實驗對比,證明了本方法的可行性與有效性

本文第1 節主要介紹目前已有的哈希學習算法及其分類,同時介紹現有的無監督哈希學習存在的問題以及本文工作的主要技術路線.第2 節從問題定義、網絡架構、損失函數等幾個方面詳細闡述本文提出的模型性能提升方法.第3 節在兩個常用數據集上證明本方法能夠在不同哈希編碼長度的條件下,均能夠提高模型的檢索精度.第4 節對本文工作做出總結,并給出未來的工作展望.

1 相關工作

面向大規模數據集設計高效的特征學習算法,對于檢索具有十分重要的應用價值.在構建高效的大規模檢索系統時,往往存在著兩個最主要的問題:數據的存儲成本和檢索速度.當前,文本、圖像、視頻等多媒體數據往往具有高維度的特征,因此檢索方法面臨著“特征維數災難”的嚴峻挑戰,使得系統的存儲空間、計算復雜度都急劇增加,從而影響了檢索系統的性能.為了解決上面的難題和挑戰,哈希學習技術被提出來,并成為信息檢索領域和機器學習領域的研究熱點.哈希學習(learning to Hash)[5]對數據自身的特點和結構進行分析,依靠機器學習的方法將高維連續數據映射為哈希編碼(也就是二進制串的形式),同時在哈希空間中盡可能地保持原空間中的結構信息.由于其二進制表示形式,哈希學習能夠顯著減少數據的存儲成本以及計算復雜度,從而有效提高檢索系統的效率.由于本文主要研究無監督哈希方法,因此本節主要對無監督哈希學習方法進行回顧總結.

傳統的無監督哈希學習方法通常基于淺層的結構進行哈希編碼學習,這些方法通常將特征學習和哈希編碼當作兩個分開的過程.代表性的算法包括ITQ[11]等.ITQ 試圖先對原始空間的數據集用PCA 進行降維處理,將數據集中的數據點映射到一個二進制超立方體的頂點上,使得對應的量化誤差最小,從而得到對應該數據集較為精確的哈希編碼.近幾年,隨著深度學習在各種視覺任務和機器學習中取得了令人驚訝的效果,深度學習也逐漸被應用到哈希學習中,例如語義哈希(semantic Hashing)[25]、深度自編碼哈希(deep auto-encoder Hashing)[26]和深度二進制描述子(deep binary descriptors,簡稱DeepBit)[27].語義哈希使用預訓練的限制玻爾茲曼機構建自編碼網絡,從而能夠產生有效的哈希編碼,并且能夠準確地重構原始輸入.深度自編碼哈希設計了一個非常深的自編碼器用于映射原始輸入到哈希空間中,并且利用重構損失指導哈希編碼的學習.深度二進制描述子將特征學習和哈希編碼學習融合到一個框架中,并取得了不錯的效果.

2 提出的方法

本文提出了一種基于局部語義結構和實例辨別的深度無監督哈希方法.本文認為:在哈希編碼學習過程中,提升哈希編碼的分辨力可以提高模型的表達能力和檢索能力.該方法主要包含兩個部分:一是利用對比學習(contrastive learning)對局部語義相似結構進行提煉,使其具有不僅能夠表示數據的語義信息,同時能夠表示數據的辨識信息;二是提出一個新的目標損失函數,在哈希空間中利用對比學習,使得哈希編碼不僅能夠保持數據的語義信息,同時提升哈希編碼的辨識能力.下面將分別從問題定義、網絡架構、語義結構矩陣以及哈希編碼學習等幾個方面進行具體的闡述.

2.1 問題定義

首先,本文給出一些主要符號的表示,見表1.

Table 1 Summarization of notations表1 符號表示

給定一組訓練數據X=[x1,x2,…,xn]∈?d×n,本文的目標是學習一組二進制哈希編碼:

為了達到這個目的,本文試圖求解一組有效的哈希函數,如下式所示:

其中,W1,…,WL表示模型學習的參數.sgn(?)表示符號函數,定義為

受深度學習在哈希學習方法中突出的表現激勵[27,28],為了能夠較好地將原始數據映射到哈希空間,本文仍然采用了深度神經網絡作為基本架構對哈希函數進行學習.盡管先前許多方法試圖在哈希空間中保持數據的結構信息,然而他們忽視了哈希編碼的辨識力.因此,本文目的是在哈希空間中不僅保持數據的語義相似結構,而且試圖提升哈希編碼的辨識力.

2.2 模型學習

為了完成上面的目標,本文提出了基于實例辨識力的框架用于哈希編碼學習,如圖2 所示.

Fig.2 The architexture of the proposed method圖2 本文提出方法的框架

整個框架主要分成兩個部分:(1)構建語義結構相似矩陣;(2)哈希編碼學習.具體地,為了構建相似矩陣S,本文首先利用對比學習的策略對目標數據集進行訓練,使得學習到的特征具有一定的辨識力.模型更新結束后,利用網絡中間層的特征作為數據新的特征表示.基于新的特征表示構建語義相似結構S;為了學習哈希編碼,首先利用結構損失函數優化網絡,試圖在哈希空間中保持數據的語義局部結構;同時,對原始數據和增強數據組成訓練樣本對,使用對比損失增強特征表達的辨識力.

為了構建語義局部結構矩陣S,本文利用VGG-F[24]模型作為卷積主干結構進行特征提取.由于本文研究的是無監督哈希學習問題,因此數據的標簽信息是不可得的.為了能夠訓練網絡,本文采用自監督學習的機制構建輔助任務對網絡進行學習.本文使用如下的損失函數:

其中,τ是一個超參數.和是xi的兩個增強樣本,例如通過隨機旋轉、加噪音等方式對原圖像進行數據增強.等式(3)的目的是以數據的兩個增強樣本構成正樣本對,同時以這個數據的增強樣本與其他數據的增強樣本構成負樣本對,以此訓練一個分類器,試圖將同一樣本的增強樣本分類到同一類中去.通過上述輔助任務,網絡學習到的特征能夠具有一定的辨識力.注意:為了防止數據過擬合,本文沒有使用原始數據去更新網絡,僅僅使用了原始數據的增強樣本去更新網絡.

當網絡更新停止后,本文利用fc-7 層的特征作為數據新的特征表示,并構建如下的結構矩陣:

其中,Θk(xi)表示數據點xi的K個最近鄰點,Ωk(xi)表示所有數據點中離著數據點xi最遠的K個數據點.在等式(4)中,如果兩個點是近鄰點,那么認為他們的語義信息是相似的,因此,這兩個數據點在哈希空間中的距離應該是比較小的;如果兩個點的距離較遠,那么認為他們的語義信息是不相似的,因此,這兩個數據點在哈希空間中的距離應該是比較遠的.算法1 給出了構建結構矩陣的具體步驟.

算法1.語義相似結構矩陣構建.

輸入:訓練數據X,迷你批(mini-batch)大小m;

輸出:語義相似結構矩陣S.

為了在哈希空間中保持數據的語義結構,同時提升哈希特征的辨識力,本文提出下面的目標函數:

其中,bi和分別表示數據樣本xi和它的增強樣本的哈希編碼,bi=sgn(F(xi;Φ)),Φ表示網絡學習的參數.矩陣M定義為

在等式(5)中,第1 項的目的是希望數據樣本與它的增強樣本在哈希空間中盡可能的接近,從而使得哈希編碼具有一定的辨識力;第2 項的目的是希望數據在哈希空間中和連續特征空間中的語義結構保持一致.通過聯合優化這兩項,數據的語義結構能夠得到保持,同時數據的辨識力得到提升.

在等式(5)中,二進制表示使得網絡的優化變得十分困難.為了有效地對網絡進行梯度更新,本文使用tanh(?)函數代替sgn(?)函數,從而對目標函數進行松弛,因此提出下面的目標函數:

另外,為了盡可能地減少上述松弛帶來的損失,本文增加了另外一個規則項,使得哈希編碼的值盡可能接近1 或者?1,因此得到下面的目標函數:

其中,α≥0 和β≥0 是兩個超參數.

為了求解等式(8),本文采用標準反向傳播算法對梯度進行更新,整個訓練過程見算法2.

算法2.哈希編碼訓練.

輸入:訓練數據X,迷你批(mini-batch)大小m,超參數α和β;

輸出:神經網絡參數Φ={W1,…,WL}和訓練數據的哈希編碼.

當網絡訓練完成后,對于任意其他不在訓練集中的數據點xt,可以利用下式直接計算其哈希編碼:

任意數據點的哈希編碼映射過程如算法3 所示.

算法3.哈希編碼測試.

輸入:查詢數據xt,神經網絡的參數Φ;

輸出:查詢數據xt的哈希編碼bt.

3 實驗及分析

本節驗證了所提方法的有效性,包括實驗平均精度均值(MAP)、參數敏感分析、消融實驗.本文利用Pytorch實現深度哈希模型,通過動量式的批量隨機梯度下降法優化模型參數,其中批量大小為16,動量參數設置為0.9,學習率固定為0.001.為了與其他哈希模型進行公平比較,本方法將原始圖像直接裁剪為224×224 的尺寸作為模型的輸入,不做任何數據增強,并在VGG-F 的fc-7 提取特征向量.隨后將特征向量輸入哈希層,得到每個原始圖像的哈希編碼,其中,哈希層是模型最后的全連接層.

驗證實驗在2 個基準數據集——NUSWIDE,FLICKR25K 上進行.在每個數據集上,都與一些效果好的深度學習方法和傳統的淺層方法進行了對比分析.使用常見的評價準則來衡量本方法的效果:平均精度均值.

平均精度均值為每個詢問數據(query)的精度均值(AP)的平均:

其中,N表示為與詢問數據標簽相關的樣本數量,P(r)為前r個檢索樣本的準確率,δ(r)表示第r個檢索樣本是否與詢問數據相關.本文設置R為5 000,并且確定:若兩個樣本至少有一個標簽相同,則這兩個樣本相關.

3.1 數據集及實驗環境

本文實驗在一個服務器節點上運行,該服務器的操作系統為Linux version 4.4.0-116-generic (buildd@lgw01-amd64-021)(gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1～16.04.9)),處理器為Intel(R)Xeon(R)Silver 4210CPU@2.20GHz,內存64GB.

FLICKR25K 數據集包含從Flickr 網站收集到的25 000 個圖像,共分為24 類.隨機選擇2 000 個圖像作為測試集,剩余圖像作為檢索集,并從檢索集中隨機選擇10 000 個圖像作為訓練集.

NUSWIDE 數據集包含269 648 個圖像,共有81 種類別.本文使用的數據子集包含10 個最常見的標簽,隨機選擇5 000 個圖像作為測試集,剩余圖像作為檢索集,并從檢索集中隨機選擇5 000 個圖像作為訓練集.

3.2 FLICKR25K數據集上的實驗結果

本方法與其他對比方法在FLICKR25K 數據集上的實驗結果見表2.表2 顯示了各算法在哈希編碼長度從16 位變化到128 位時獲得的平均精度均值.可以看出:本文提出的方法在不同哈希編碼長度的實驗中比其他對比方法表現更好,在16 位、32 位、64 位、128 位哈希編碼長度上,本方法比表現第二好的深度無監督哈希方法,SSDH 的MAP 分別高出5.17%,6.46%,6.70%,7.45%,從而證明了本文方法的優勢.對比方法中,ITQ[11],Spectral Hashing (SH)[29],Density Sensitive Hashing (DSH)[30],Spherical Hashing (SpH)[31],SGH[21]是傳統的淺層方法,而DeepBit[27]和SSDH[14]是基于深度模型的方法.通過對比發現,一些非深度哈希的方法比深度哈希方法DeepBit的MAP 更高.這可能是因為深度哈希方法在缺乏監督信息時,不能完全利用深度網絡的特征表達能力并且容易過擬合到局部最小點,從而影響效果.本方法使用了基于對比學習的自監督哈希編碼的方法,并且對哈希編碼進行正則化,從而完成了最好的MAP 結果.

Table 2 MAP of different code length in FLICKR25K表2 FLICKR25K 數據集上對不同哈希編碼長度的測試平均精度均值

3.3 NUSWIDE數據集上的實驗結果

本方法與其他對比方法在NUSWIDE 數據集上的實驗結果見表3.表3 顯示了各算法在哈希編碼長度從16位變化到128 位獲得的平均精度均值.

Table 3 MAP of different code length in NUSWIDE表3 NUSWIDE 數據集上對不同哈希編碼長度的測試平均精度均值

由表3 所示的結果可以看出:本文提出的方法在不同哈希編碼長度的實驗中,比其他對比方法表現更好.在16 位、32 位、64 位、128 位哈希編碼長度上,本方法比SSDH 的MAP 分別高出6.96%,6.29%,7.84%,10.37%,仍然證明了本文方法的優勢.哈希編碼長度越長,能夠編碼的信息越多,因此MAP 更高.此外,NUSWIDE 檢索集大小是FLICKR25K 檢索集大小的10 倍左右,因此檢索查找的難度急劇增加,因此,MAP 值較FLICKR25K 在相同哈希編碼長度時小.

3.4 消融實驗分析

本小節進行消融實驗比較,從而驗證提出算法每部分的有效性.首先,將本方法劃分出3 個實驗元素,見表4,分別為:是否加入局部語義結構信息、是否加入對比學習損失、是否加入正則項損失.組合不同的實驗元素,得到消融實驗結果,以此觀察每個實驗元素對結果的影響.

Table 4 Three main componets for ablation studies表4 消融實驗中的3 個元素

在 FLICKR25K 數據集、哈希編碼長度為 16 位的條件下,進行消融實驗.消融實驗結果見表 5.在FLICKR25K 數據集、哈希編碼長度為32 位的條件下,進行消融實驗.消融實驗結果見表6.

Table 5 MAP of our method’s variants on FLICKR25K,at code length 16bits表5 加入不同元素的FLICKR25K 數據集上,16 位哈希編碼的MAP 對比

Table 6 MAP of our method’s variants on FLICKR25K,at code length 32bits表6 加入不同元素的FLICKR25K 數據集上,32 位哈希編碼的MAP 對比

從表5 和表6 可以看出:加入正則項和對比學習損失項后,模型的精度均能得到提升.模型在加入語義結構信息的基礎上,加入對比學習損失,通過對哈希碼使用動量對比學習算法,進一步學習到更準確的哈希編碼表達,極大地提高了模型的精度.在加入語義結構信息和對比學習損失的基礎上,加入正則項損失,通過約束哈希碼盡量趨近于1 或?1,提升了哈希碼的辨識度.因此,在哈希空間中試圖保持數據的語義結構信息和提升哈希編碼的辨識力,對于提升模型性能起到了積極的作用,從而驗證了本文所提方法的有效性.

3.5 參數敏感性分析

本小節對所提方法中的超參數進行了敏感性分析.本文主要包含了3 個超參數α,β,τ.本文在FLICKR25K 數據集上哈希編碼長度為16 位的情況下進行了實驗.本文首先固定正則項損失參數β為0.01,在0.001～0.1 內變化α,結果如圖3(a)所示.固定對比學習損失參數α為0.01,在0.001～0.1 內變化β,結果如圖3(b)所示.

Fig.3 Loss hyper-parameters of code length 16bits on FLICKR25K dataset圖3 損失項參數對FLICKR25K 數據集16 位哈希編碼長度實驗的影響

從圖3 中可以看出:固定參數β,隨著α的增加,MAP 先增加后減少,并且在α為0.01 時表現最好;固定參數α為0.01,隨著β的增加,MAP 先增加后減少,并且在β為0.1 時表現最好.對比α和β對實驗結果MAP 的影響可以看到:對比學習損失的參數α對實驗結果影響更大,而正則項損失的參數β能在一定程度上提高實驗結果.本文在其他實驗中固定α=0.01 和β=0.01.

固定損失項參數α=0.01 和β=0.01,在0～0.5 內變化溫度參數τ,結果如圖4 所示.

Fig.4 Temporature hyper-parameter of code length 16bits on FLICKR25K dataset圖4 溫度參數對FLICKR25K 數據集16 位哈希編碼長度實驗的影響

τ是控制數據分布集中程度的溫度參數.從圖4 中可以看出:固定參數α和β,隨著τ的增加,MAP 整體趨勢先增加后減少,并且在τ為0.07 時表現最好.本文的實驗中,固定α=0.01,β=0.01 以及τ=0.07.

3.6 時間復雜度分析

時間復雜度即模型的運算次數,可用FLOP(floating-point operation)衡量,表示浮點運算次數.

所有卷積層的時間復雜度為

其中,l表示卷積層的下標,d表示卷積層的數量,nl表示第l層網絡卷積核的數量,nl?1表示第l層網絡的輸入通道數,sl表示卷積核的邊長,ml表示輸出特征圖的邊長.訓練過程和測試過程的時間復雜度不同,每個圖像的訓練用時大約是測試用時的3 倍(前向傳播一倍,反向傳播兩倍).本文計算了哈希編碼訓練過程中的VGG-F 網絡與哈希編碼層的時間復雜度共為31.0GFlops,其中,全連接層與池化層的時間開銷占總的時間復雜度的0.8%.

4 結論及展望

針對無監督的哈希學習問題,本文提出了一種基于語義結構保持和實例分辨力的深度無監督哈希學習的框架.為了能夠提升哈希編碼的辨識力,采用自監督學習策略,不僅對語義結構進行學習,同時也指導哈希編碼的學習.本文在兩個常用于評估哈希方法的數據集上進行了實驗,廣泛的實驗設計與分析驗證了提出方法的有效性.下一步研究工作的重點將是嘗試設計更加有效的自監督學習任務以及更加有效的自監督學習損失函數;同時,如何優化算法提升模型的訓練速度,也是下一步工作的重點.