深度優先局部聚合哈希

龍顯忠，程成，李云

（1.南京郵電大學 計算機學院，江蘇 南京 210023；2.江蘇省大數據安全與智能處理重點實驗室，江蘇 南京 210023）

隨著信息檢索技術的不斷發展和完善，如今人們可以利用互聯網輕易獲取感興趣的數據內容，然而，信息技術的發展同時導致了數據規模的迅猛增長.面對海量的數據以及超大規模的數據集，利用最近鄰搜索[1]（Nearest Neighbor Search，NN）的檢索技術已經無法獲得理想的檢索效果與可接受的檢索時間.因此，近年來，近似最近鄰搜索[2]（Approximate Nearest Neighbor Search，ANN）變得越來越流行，它通過搜索可能相似的幾個數據而不再局限于返回最相似的數據，在犧牲可接受范圍的精度下提高了檢索效率.作為一種廣泛使用的ANN 搜索技術，哈希方法（Hashing）[3]將數據轉換為緊湊的二進制編碼（哈希編碼）表示，同時保證相似的數據對生成相似的二進制編碼.利用哈希編碼來表示原始數據，顯著減少了數據的存儲和查詢開銷，從而可以應對大規模數據中的檢索問題.因此，哈希方法吸引了越來越多學者的關注.

當前哈希方法主要分為兩類：數據獨立的哈希方法和數據依賴的哈希方法，這兩類哈希方法的區別在于哈希函數是否需要訓練數據來定義.局部敏感哈希（Locality Sensitive Hashing，LSH）[4]作為數據獨立的哈希代表，它利用獨立于訓練數據的隨機投影作為哈希函數.相反，數據依賴哈希的哈希函數需要通過訓練數據學習出來，因此，數據依賴的哈希也被稱為哈希學習，數據依賴的哈希通常具有更好的性能.近年來，哈希方法的研究主要側重于哈希學習方面.

根據哈希學習過程中是否使用標簽，哈希學習方法可以進一步分為：監督哈希學習和無監督哈希學習.典型的無監督哈希學習包括：譜哈希[5]（Spectral Hashing，SH）；迭代量化哈希[6]（Iterative Quantization，ITQ）；離散圖哈希[7]（Discrete Graph Hashing，DGH）；有序嵌入哈希[8]（Ordinal Embedding Hashing，OEH）等.無監督哈希學習方法僅使用無標簽的數據來學習哈希函數，將輸入的數據映射為哈希編碼的形式.相反，監督哈希學習方法通過利用監督信息來學習哈希函數，由于利用了帶有標簽的數據，監督哈希方法往往比無監督哈希方法具有更好的準確性，本文的研究主要針對監督哈希學習方法.

傳統的監督哈希方法包括：核監督哈希[9]（Supervised Hashing with Kernels，KSH）；潛在因子哈希[10]（Latent Factor Hashing，LFH）；快速監督哈希[11]（Fast Supervised Hashing，FastH）；監督離散哈希[12]（Supervised Discrete Hashing，SDH）等.隨著深度學習技術的發展[13]，利用神經網絡提取的特征已經逐漸替代手工特征，推動了深度監督哈希的進步.具有代表性的深度監督哈希方法包括：卷積神經網絡哈希[14]（Convolutional Neural Networks Hashing，CNNH）；深度語義排序哈希[15]（Deep Semantic Ranking Based Hashing，DSRH）；深度成對監督哈希[16]（Deep Pairwise-Supervised Hashing，DPSH）；深度監督離散哈希[17]（Deep Supervised Discrete Hashing，DSDH）；深度優先哈希[18]（Deep Priority Hashing，DPH）等.通過將特征學習和哈希編碼學習（或哈希函數學習）集成到一個端到端網絡中，深度監督哈希方法可以顯著優于非深度監督哈希方法.

到目前為止，大多數現有的深度哈希方法都采用對稱策略來學習查詢數據和數據集的哈希編碼以及深度哈希函數.相反，非對稱深度監督哈希[19]（Asymmetric Deep Supervised Hashing，ADSH）以非對稱的方式處理查詢數據和整個數據庫數據，解決了對稱方式中訓練開銷較大的問題，僅僅通過查詢數據就可以對神經網絡進行訓練來學習哈希函數，整個數據庫的哈希編碼可以通過優化直接得到.本文的模型同樣利用了ADSH 的非對稱訓練策略.

然而，現有的非對稱深度監督哈希方法并沒有考慮到數據之間的相似性分布對于哈希網絡的影響，可能導致結果是：容易在漢明空間中保持相似關系的數據對，往往會被訓練得越來越好；相反，那些難以在漢明空間中保持相似關系的數據對，往往在訓練后得到的提升并不顯著.同時大部分現有的深度監督哈希方法在哈希網絡中沒有充分有效利用提取到的卷積特征.

本文提出了一種新的深度監督哈希方法，稱為深度優先局部聚合哈希（Deep Priority Local Aggregated Hashing，DPLAH）.DPLAH 的貢獻主要有三個方面：

1）DPLAH 采用非對稱的方式處理查詢數據和數據庫數據，同時DPLAH 網絡會優先學習查詢數據和數據庫數據之間困難的數據對，從而減輕相似性分布傾斜對哈希網絡的影響.

2）DPLAH 設計了全新的深度哈希網絡，具體來說，DPLAH 將局部聚合表示融入到哈希網絡中，提高了哈希網絡對同類數據的表達能力.同時考慮到數據的局部聚合表示對于分類任務的有效性.

3）在兩個大型數據集上的實驗結果表明，DPLAH 在實際應用中性能優越.

1 相關工作

本節分別對哈希學習[3]、NetVLAD[20]和Focal Loss[21]進行介紹.DPLAH 分別利用NetVLAD 和Focal Loss 提高哈希網絡對同類數據的表達能力及減輕數據之間相似性分布傾斜對于哈希網絡的影響.

1.1 哈希學習

哈希學習[3]的任務是學習查詢數據和數據庫數據的哈希編碼表示，同時要滿足原始數據之間的近鄰關系與數據哈希編碼之間的近鄰關系相一致的條件.具體來說，利用機器學習方法將所有數據映射成{0，1}r形式的二進制編碼（r 表示哈希編碼長度），在原空間中不相似的數據點將被映射成不相似（即漢明距離較大）的兩個二進制編碼，而原空間中相似的兩個數據點將被映射成相似（即漢明距離較小）的兩個二進制編碼.

為了便于計算，大部分哈希方法學習{-1，1}r形式的哈希編碼，這是因為{-1，1}r形式的哈希編碼對之間的內積等于哈希編碼的長度減去漢明距離的兩倍，同時{-1，1}r形式的哈希編碼可以容易轉化為{0，1}r形式的二進制編碼.

圖1 是哈希學習的示意圖.經過特征提取后的高維向量被用來表示原始圖像，哈希函數h 將每張圖像映射成8 bits 的哈希編碼，使原來相似的數據對（圖中老虎1 和老虎2）之間的哈希編碼漢明距離盡可能小，原來不相似的數據對（圖中大象和老虎1）之間的哈希編碼漢明距離盡可能大.

圖1 哈希學習示意圖Fig.1 Hashing learning diagram

1.2 NetVLAD

NetVLAD 的提出是用于解決端到端的場景識別問題[20]（場景識別被當作一個實例檢索任務），它將傳統的局部聚合描述子向量（Vector of Locally Aggregated Descriptors，VLAD[22]）結構嵌入到CNN 網絡中，得到了一個新的VLAD 層.可以容易地將NetVLAD使用在任意CNN 結構中，利用反向傳播算法進行優化，它能夠有效地提高對同類別圖像的表達能力，并提高分類的性能.

NetVLAD 的編碼步驟為：利用卷積神經網絡提取圖像的卷積特征；利用NetVLAD 層對卷積特征進行聚合操作.圖2 為NetVLAD 層的示意圖.在特征提取階段，NetVLAD 會在最后一個卷積層上裁剪卷積特征，并將其視為密集的描述符提取器，最后一個卷積層的輸出是H×W×D 映射，可以將其視為在H×W 空間位置提取的一組D 維特征，該方法在實例檢索和紋理識別任務[23-24]中都表現出了很好的效果.

圖2 NetVLAD 層示意圖[20]Fig.2 NetVLAD layer diagram[20]

NetVLAD 在特征聚合階段，利用一個新的池化層對裁剪的CNN 特征進行聚合，這個新的池化層被稱為NetVLAD 層.NetVLAD 的聚合操作公式如下：

式中：xi（j）和ck（j）分別表示第i 個特征的第j 維和第k 個聚類中心的第j 維；ak（xi）表示特征xi與第k 個視覺單詞之間的權.NetVLAD 特征聚合的輸入為：NetVLAD 裁剪得到的N 個D 維的卷積特征，K 個聚類中心.

VLAD 的特征分配方式是硬分配，即每個特征只和對應的最近鄰聚類中心相關聯，這種分配方式會造成較大的量化誤差，并且，這種分配方式嵌入到卷積神經網絡中無法進行反向傳播更新參數.因此，NetVLAD 采用軟分配的方式進行特征分配，軟分配對應的公式如下：

如果α→+∞，那么對于最接近的聚類中心，ak（xi）的值為1，其他為0.ak（xi）可以進一步重寫為：

式中：wk=2αck；bk=-α‖ck‖2.最終的NetVLAD 的聚合表示可以寫為：

1.3 Focal Loss

對于目標檢測方法，一般可以分為兩種類型：單階段目標檢測和兩階段目標檢測，通常情況下，兩階段的目標檢測效果要優于單階段的目標檢測.Lin 等人[21]揭示了前景和背景的極度不平衡導致了單階段目標檢測的效果無法令人滿意，具體而言，容易被分類的背景雖然對應的損失很低，但由于圖像中背景的比重很大，對于損失依舊有很大的貢獻，從而導致收斂到不夠好的一個結果.Lin 等人[21]提出了Focal Loss 應對這一問題，圖3 是對應的示意圖.使用交叉熵作為目標檢測中的分類損失，對于易分類的樣本，它的損失雖然很低，但數據的不平衡導致大量易分類的損失之和壓倒了難分類的樣本損失，最終難分類的樣本不能在神經網絡中得到有效的訓練.Focal Loss 的本質是一種加權思想，權重可根據分類正確的概率pt得到，利用γ 可以對該權重的強度進行調整.

圖3 Focal Loss 示意圖[21]Fig.3 Focal Loss diagram[21]

針對非對稱深度哈希方法，希望難以在漢明空間中保持相似關系的數據對優先訓練，具體來說，對于DPLAH 的整體訓練損失，通過施加權重的方式，相對提高難以在漢明空間中保持相似關系的數據對之間的訓練損失.然而深度哈希學習并不是一個分類任務，因此無法像Focal Loss 一樣根據分類正確的概率設計權重，哈希學習的目的是學到保相似性的哈希編碼，本文最終利用數據對哈希編碼的相似度作為權重的設計依據，具體的權重形式將在模型部分詳細介紹.

2 深度優先局部聚合哈希

2.1 基本定義

對于DPLAH 模型，它在特征提取部分采用預訓練好的Resnet18 網絡[25].圖4 為DPLAH 網絡的結構示意圖，利用NetVLAD 層聚合Resnet18 網絡提取到的卷積特征，哈希編碼通過VLAD 編碼得到，由于VLAD 編碼在分類任務中被廣泛使用，于是本文將NetVLAD 層的輸出作為分類任務的輸入，利用圖像的標簽信息監督NetVLAD 層對卷積特征的利用.事實上，任何一種CNN 模型都能實現圖像特征提取的功能，所以對于選用哪種網絡進行特征學習并不是本文的重點.

圖4 DPLAH 結構Fig.4 DPLAH structure

2.2 DPLAH 模型的目標函數

為了學習可以保留查詢圖像與數據庫圖像之間相似性的哈希編碼，一種常見的方法是利用相似性的監督信息S∈{-1，1}n×m、生成的哈希編碼長度r，以及查詢圖像的哈希編碼ui和數據庫中圖像的哈希編碼bj三者之間的關系[9]，即最小化相似性的監督信息與哈希編碼對（ui，bj）內積之間的L2損失.考慮到相似性分布的傾斜問題，本文通過施加權重來調節查詢圖像和數據庫圖像之間的損失，其公式可以表示為：

受Focal Loss 啟發，希望深度哈希網絡優先訓練相似性不容易保留圖像對，然而Focal Loss 利用圖像的分類結果對損失進行調整，因此，需要重新進行設計，由于哈希學習的目的是為了保留圖像在漢明空間中的相似性關系，本文利用哈希編碼的余弦相似度來設計權重，其表達式為：

式中：ui和bj分別表示查詢圖像i 和數據庫圖像j 的哈希編碼；sij=1 表示圖像i 和j 語義相似，sij=-1 表示圖像i 和j 語義不相似.從公式（6）中可以發現，若ui和bj越相似，且圖像i 和j 語義相似，則wij的值接近1，這就表示哈希編碼ui和bj相似的難度低；反之ui和bj不相似，而圖像i 和j 語義相似，則wij的值接近0，這就表示哈希編碼ui和bj相似的難度高.本文希望深度哈希網絡優先關注相似難度高的圖像對，因此對查詢圖像和數據庫圖像之間施加權重（1-wij）α，α是一個超參數.

使用Ψ={1，2，…，m}表示數據庫中所有圖像的索引，隨機地從數據庫中選擇nΨΥ 張圖像創建查詢集，并用Υ={i1，i2，…，in}?Ψ 表示查詢集的索引.此時，公式（7）可以表示為：

創建的查詢集通過深度哈希網絡生成哈希編碼，同樣它們在整個數據集中的哈希編碼也可以通過優化直接得到，因此，還需要保證查詢集在哈希網絡中學習到的哈希編碼要與數據集中的哈希編碼盡可能相同.對應的優化問題可進一步表示為：

由于VLAD 對于圖像具有較好的表示性能，并且VLAD 同樣被廣泛運用于圖像分類任務中，因此，NetVLAD 層的輸出對于分類任務也依然有效，并將NetVLAD 層的輸出pi作為分類網絡的輸入.利用NetVLAD 在分類網絡中的預測標簽和圖像的真實標簽之間的損失更新網絡參數，希望圖像哈希網絡能夠提取到更具有判別力的特征.最終，DPLAH 的目標函數可寫為：

2.3 學習過程

本文采用迭代優化的方式來學習DPLAH 網絡的參數Θ 和數據庫圖像的哈希編碼B.算法1 是整個DPLAH 算法的學習過程.

固定B，學習參數Θ.當B 被固定，直接使用反向傳播算法（BP）來更新參數Θ，具體來說，從查詢集中采樣一個批次的圖像來更新深度哈希網絡的參數.

固定參數Θ，學習B.當深度哈希網絡的參數Θ被固定時，使用與非對稱深度哈希[19]相同的優化策略來更新數據庫中的哈希編碼B，公式如下所示：

式中：B*k表示B 的第k 列；是矩陣B 除了第k 列的矩陣；U*k表示U 的第k 列；是矩陣U 除了第k列的矩陣；S 為相似性矩陣.

3 實驗設計與分析

3.1 實驗設計

3.1.1 數據集

為了驗證DPLAH 算法的有效性，在CIFAR－10[26]和NUS－WIDE[27]數據集上進行實驗.

CIFAR－10 數據集由60 000 張32×32 的RGB彩色圖像構成，它是一個用于識別普適物體的數據集.這些圖像被手動標記為10 個類別，分別是飛機、汽車、鳥、貓、鹿、狗、青蛙、馬、船和卡車.

NUS－WIDE 是一個真實的網絡數據集，一共包含269 648 張圖像，每張圖像都與來自81 個語義類別中的一個或多個類別相關聯.本文遵循與ADSH類似的實驗方案，使用最常見的21 個類別中的圖像，其中每個類別中至少包含了5 000 張圖像，從而總共使用了195 834 張圖像.

3.1.2 實驗運行環境及超參數配置

所有關于DPLAH 的實驗都是利用Pytorch 深度框架完成的，利用預訓練好的Resnet18 網絡[25]提取圖像的特征，NetVLAD 層對Resnet18 模型輸出的卷積特征進行聚合，最后，利用聚合得到的特征進行哈希編碼的學習.

對CIFAR－10 和NUS－WIDE 數據集，NetVLAD的聚類中心個數設置為64.超參數β、μ 和Υ 分別設置為200、200 和2 000，DPLAH 網絡的學習率在10－7～10－3區間進行調整，tl和ts分別為60 和3，超參數α 為0.2.

在本文實驗中，使用到的NetVLAD 層去掉了規范化操作，由于整個數據集的哈希編碼是通過優化算法直接得到，因此在訓練初期并不使用權重.具體來說，當超參數tl的值小于10 時，都不施加優先權重；當tl的值大于10 時，施加權重進行訓練的同時，會對學習率進行調整.

3.1.3 實驗對比

按照現有的深度哈希方法中的評估指標，使用平均準確率均值（MAP）和Top－5K 精度來評估DPLAH 算法的性能.對于NUS－WIDE 數據集，計算前5 000 張返回圖像的MAP.對于CIFAR－10 數據集，在每個類別中選取100 張圖像作為測試圖像，對于NUS－WIDE 數據集，同樣在每個類別中選取100張圖像作為測試圖像，因此這兩個數據集的測試圖像數量分別為1 000 和2 100 張，剩余圖像作為數據庫圖像.遵循非對稱深度哈希等方法[19]在圖像相似性上的構造方法，利用圖像標簽構造用于深度哈希函數學習的相似性矩陣.具體來說：若兩張圖像共享至少一個標簽，則它們被視為語義相似對，否則，它們是語義不相似的圖像對.

多種哈希學習方法被用來與DPLAH 進行比較，如SH、ITQ 等無監督的哈希方法（包括SH+CNN、ITQ+CNN），SDH、FastH 和LFH 等有監督的哈希方法（包括SDH+CNN、FastH+CNN 和LFH+CNN），CNNH、DPSH 和ADSH 等深度哈希方法（其中CNNH 是兩階段的深度哈希學習方法，其他都是端到端的深度哈希學習方法）.

3.2 實驗結果和分析

在兩個數據集上的MAP 對比結果如表1 所示.由于ADSH 算法的優越性能，它成為本文重點比較的方法.為了進行公平的比較，此處利用Pytorch 版本的ADSH 來進行實驗對比，預訓練好的Resnet18模型同樣會被用來提取圖像的卷積特征，其他哈希算法的實驗結果來源于DPSH[16]和ADSH[19].

表1 中的非深度哈希學習算法使用圖像的手工特征，同時也比較了使用CNN 特征的非深度哈希學習算法，可以發現端到端的深度哈希方法優于傳統的哈希學習方法，非對稱的深度哈希方法優于對稱的深度哈希方法.與LFH+CNN 的最好結果0.814 相比，DPLAH 的平均準確率均值要高出11%，同時，DPLAH 的平均準確率均值最多比非對稱深度監督哈希方法ADSH 高出2%.

由于非對稱深度監督哈希方法（ADSH）的性能遠優于其他哈希學習方法，因此，比較DPLAH 和ADSH 在不同比特長度下的Top-5K 精度，結果如圖5 所示.由表1 和圖5 可知，DPLAH 無論在MAP 還是Top-5K 精度的衡量下，其性能都優于現有的深度監督哈希方法.

圖5 兩個數據集下的Top-5K 精度Fig.5 Top-5K precision under two data sets

表1 兩個基準數據集上的MAP 對比Tab.1 The MAP comparison on two benchmark datasets

根據實驗結果，發現DPLAH 方法在NUS-WIDE數據集上性能較好.這可能由于NUS-WIDE 數據集中的圖像來自于真實世界，圖像中包含的內容非常豐富；而NetVLAD 的提出就是為了解決現實中的場景識別問題，在面對圖像中的光線變化、視角變化等情況，具備一定的魯棒性，從而使得DPLAH 方法在NUS-WIDE 數據集上的性能較好.

為了驗證NetVLAD 層確實能學習到具有區分力的哈希編碼，本文在NUS-WIDE 數據集不使用優先權重的條件下，僅僅將NetVLAD 層加入哈希網絡中，對比不同比特長度下的MAP.實驗結果如圖6 所示.

圖6 在NUS-WIDE 數據集上的NetVLAD 實驗結果Fig.6 NetVLAD experiment result on NUS-WIDE dataset

圖7 為DPLAH 算法基于漢明距離排序的搜索結果.結果是基于32 bits 的哈希編碼長度給出的幾個示例.在圖7 中，每行圖片中的第1 張代表查詢圖像，后面10 張圖像表示與查詢圖像的漢明距離最近的10 張圖像.由圖7 可知，DPLAH 算法具有優越的性能，盡管還存在一些錯誤的搜索結果（示例中最后一行的查詢圖像是飛機，然而檢索出的圖像是輪船），但這在接受的范圍內.

圖7 在CIFAR-10 數據集上的檢索示例Fig.7 Retrieval example on CIFAR-10 dataset

4 結論

本文提出了一種基于局部聚合的深度優先哈希方法，在應對相似性分布傾斜方面，受到了Focal Loss 的啟發，利用查詢圖像在哈希網絡中學習的哈希編碼和整個數據庫圖像的哈希編碼之間的余弦相似度，設計了損失函數的優先權重，使得深度哈希網絡優先關注相似難度高的圖像，從而保證難以在漢明空間中保持相似關系的圖像對得到充分訓練.在哈希特征提取方面，由于NetVLAD 層能夠有效地提高對同類別圖像的表達能力，因此利用NetVLAD 層將卷積得到的特征進行聚合，從而使學到的哈希編碼更具有區分性.在CIFAR-10 和NUS-WIDE 兩個數據集下進行了實驗，將DPLAH 與多種哈希學習方法進行比較，通過實驗分析，表明了DPLAH 算法的優越性能.