深度學習在哈希算法的應用

亓海鳳　王永

摘 要：哈希，一種將任意長度的輸入二值化輸出的過程，被廣泛用于快速查找，如分類、檢索和拷貝檢測等。近年來受到卷積神經網絡強大學習能力的影響，很多學者嘗試用深度學習的工具進行哈希的探索，也就是所謂的深度哈希算法。深度學習模型是一種能夠層進學習的機器工具，它可以通過從低級特征中構建高級特征來學習特征的層次結構，從而使特征構建過程自動化。本文對深度哈希算法進行了總結。

關鍵詞：深度哈希 近似近鄰搜索 哈希性能

中圖分類號：TP393 文獻標識碼：A 文章編號：1672-3791（2018）11（b）-0139-04

對于最近鄰搜索[1]（Nearest Neighbor search， NNs）問題而言，給定任意檢索條目（query），目的在于找到目標庫中與之最相近的個體，這里的“近”既可以理解為視覺上的相似（外觀），也可以是語義表達相似（同類）。實際應用中目標庫的規模往往比較大，需要相當的存儲空間，而且計算檢索條目與目標庫中每個個體之間的距離的計算成本昂貴。為了解決存儲成本和計算成本問題，近年來近似近鄰搜索[2]（Approximate Nearest Neighbor search， ANNs）技術發展迅猛，這種方法效率更高，而且被證明對許多實際問題足夠有用，因此成為了一種實用的替代方案。哈希（hashing）是一種代表性的近似近鄰搜索的解決方案，吸引了大量的研究工作，其目標是將數據項轉換為低維表示，或等效為由一系列比特組成的短代碼，稱為哈希碼。

1 基于哈希的近似近鄰搜索

如圖1所示基于哈希的近似近鄰搜索一般有3個關鍵步驟：哈希函數設計、哈希表生成和哈希檢索。

1.1 哈希函數設計

將原始數據二值化獲取哈希碼的過程稱之為哈希函

數，哈希函數的設計一般包括投影和量化兩個關鍵步驟。投影的過程是一個降維的過程，原始的數據一般為視頻、圖像等維度很大的數據，需要先降維；量化是二值化的過程，因為常見的哈希碼是二進制的。從計算的復雜度考慮，降維一般采用廣義線性函數，哈希函數可以統一表示為：

其中為預先設計好的投影函數，參數由斜率參數和截距參數組成。常用的哈希碼是二進制的，轉換公式為：

現有的哈希函數大致可以分為兩類：一種是與數據無關的，隨機或者人為規定二值化的方式；一種是依賴數據訓練，用學習的方式和算法獲取哈希函數的形式。在過去的十幾年里，深度學習又稱深度神經網絡，發展迅速，受到越來越多的關注和研究，被廣泛應用于語音識別、機器視覺、文本挖掘等領域。深度學習致力于魯棒性的學習，用于對復雜數據的強大表達，作為數據的一種二進制表達方式，哈希碼也肯定了深度學習的工具并開始對其進行研究。

1.2 哈希表生成

哈希函數設計完成之后，目標庫里所有的樣本就可以全部轉化為哈希碼表示。對于一個K比特的哈希函數而言，整個數據集的哈希碼所占的內存為NK/8個字節，假設原始數據以雙精度浮點格式存儲，原始存儲成本為8ND字節。實際應用中的數據集往往有成百數千的維度，因此用哈希算法可以成百乃至上千倍的節約存儲成本。

在實際應用中，目標庫所有的樣本的哈希碼組成哈希表，對于一個K比特的哈希函數，哈希表最多可容納2k個不同的樣本。實際情況是2k這個哈希碼有很多是空的，因此這些哈希碼組成反向查找表，如圖2所示這樣可以更有效地節省存儲空間。檢索的返回值是按照與檢索條目的相似度從大到小排列。

1.3 哈希檢索

檢索的最終目的是找到目標庫中與之最相近的樣本，因此在基于哈希算法的檢索中需要先將檢索條目按照已經設計好的轉換目標庫的哈希函數將之映射為哈希碼。最常見的計算相似度的算法是計算檢索條目與目標庫中各個樣本的海明距離，哈希算法中這兩者都已經二進制表示，因此兩者的異或值就是他們的海明距離，計算公式為：

（3）

哈希算法要求相似的樣本有相似的哈希碼，因此設置好相似度的閾值即可返回與檢索條目近似最相近的樣本。如圖2所示，檢索條目q映射成4比特的哈希碼0110，設置的相似度閾值為漢明距離為1，則返回的近似最近鄰樣本為。

2 哈希函數的發展歷程

最初的哈希算法中，研究者將原始數據做特征提取之后在特征空間分塊，每一塊派生一位哈希比特串聯成哈希碼。這種方法有嚴格的理論保證其效果，但在實際操作中需要很長的哈希碼去達到檢索要求。

在之后的工作中，研究者為了獲取哈希碼更短、檢索性能更高的哈希算法，進行了更多的嘗試。其中局部敏感哈希[3，4]（Locality-Sensitive Hashing， LSH）是最常見的一類哈希算法，核心思想是使相近的樣本投影到相同的哈希桶，使之相鄰的概率更高。但是LSH存在無可跨越的缺點，首先需要獲取更高的檢索性能往往需要更長的哈希碼；其次，LSH算法設計敏感函數，敏感函數只能在某些特定的指標下使用，當涉及檢索要求變復雜像是語義信息這樣的，單純的數據相似或距離相近已無法滿足檢索的要求，這就是所謂的語義鴻溝。

為了解決這些問題，學習的方法被應用到哈希碼的獲取方式中，，這種哈希算法成為學習型哈希[5，6]。學習型哈希旨在針對特定的數據和特殊的檢索任務學習哈希函數，已達到更優的哈希性能。哈希函數的形式、哈希表生成時間和檢索時間都是影響哈希性能的因素，隨著學習理論和學習算法的發展，更多的學習哈希函數的算法被探究學習，新的哈希函數的形式也在不斷探索中。

3 深度哈希

不管是局部敏感哈希還是基于學習的哈希算法，都需要先將樣本從原始空間轉換到特征空間，然后再將樣本特征映射為哈希碼。由于深度神經網絡的學習能力非常強大，神經網絡已經開始運用于哈希算法，代替傳統的人工設計圖像特征的方式，將圖片作為網絡的輸入，訓練獲取哈希碼。

2014年在美國人工智能協會年會（AAAI2014）上，一種名為卷積神經網絡哈希[7]（Convolutional Neural Network Hashing， CNNH）的哈希算法被提出將深度哈希推向前臺，該算法主要用卷積神經網絡（Convolutional Neural Network， CNN）對預算好的哈希編碼做擬合用交叉熵的方式達到多標簽預測的目的，然后相似矩陣分解得到預編碼。CNNH直接將圖片樣本作為網絡的輸入，不再是基于手工設計的圖片特征，在性能上有了很大的提升。但這個網絡并不是端對端的，得到的最后圖像的表示不能反作用于哈希碼的更新，不能完全發揮神經網絡的學習能力，因此不斷有學者改進算法以更好挖掘深度模型的潛力。

2015年計算機視覺與模式識別會議（CVPR 2015）中，有4篇基于深度學習的哈希算法，其中3篇都用了端對端的深度網絡模型，使哈希性能有了進一步的提升。深度神經網絡哈希[8]（Deep Neural Network Hashing， DNNH）基于三元組圖片訓練，針對哈希學習，該算法在網絡結構上做了相應的修改，舍棄了神經網絡常用的全連接層，每部分負責一個比特，各部分直接不連接，這種連接層稱為部分連接層。此外，DNNH引入分段量化函數，組成分塊編碼模塊，更好地保持特征空間和漢明空間的相似性。這種深度哈希算法的網絡是端到端的，學習獲得圖像表示可以反作用于哈希碼，因此與CNNH算法相比，哈希性能有了進一步提升。

深度語義排序哈希[9]（Deep Semantic Ranking Hashing， DSRH）對網絡結構沒有很大的變化，哈希碼的學習對損失函數有了更高的要求。圖片檢索的過程是將圖片按照與檢索條目的相似性從大到小排序并按順序返回，DSRH直接用網絡學習排序順序，對最終的評測指標進行優化，優化難度要高很多，因此該算法加入一個凸上界優化。

深度學習二進制哈希[10]（Deep Learning of Binary Hash Codes， DLBHC）采用了一種比較直接的方式學習哈希碼，整合網絡可以分為預訓練和微調兩個部分，現在ImageNet上做預訓練，然后在預訓練好的網絡的倒數第二層和最終的任務層之間用新的全連接層連接，這個新的全連接層鑲嵌語義信息在自己的數據庫上做端對端的微調，同時用sigmoid函數約束，節點數即為哈希碼長。

上述3種算法都是在CVPR 2015中提出的，同年一種深度正則化相似比較哈希[11]（Deep Regularized Similarity Comparison Hashing， DRSCH）被提出，其參數的更新用加權的漢明距離代替標準漢明距離，這樣可以以更高的效率獲取更高的準確度，同時這樣可以用權值選擇比特，從而可以在不重新訓練模型的情況下獲取不同長度的哈希碼，有效性更強。

以上4篇文章的大致可以歸納出深度哈希算法的基本結構包括：深度網絡模型、正則項和損失函數，這三項也是現在深度哈希領域的重點研究對象，特別是正則項。現有的激活函數大都是由sigmoid或者tanh實現，這類激活函數有明顯的飽和性質，當輸出接近期望值時，梯度越小，訓練的難度就會越大，很多學者開始探索sigmoid/tanh的替代品。

在CVPR 2016中，深度監督哈希[12]（Deep Supervised Hashing， DSH）提出了一種新的如圖3所示的約束函數做正則項，當輸出值和期望值的偏差越大時，損失越大，但梯度穩定在-1或+1以保證網絡的穩定性，使網絡的輸出更趨于二值化更符合哈希碼的要求。和一般神經網絡的概率層比，這種正則化思想更像傳統哈希算法的思想，將重點放在量化的部分，這樣網絡的輸出更接近二值化，更趨于二進制的哈希碼。在同年[13]和[14]兩篇論文中也用了相似的函數約束系統輸出。

深度神經網絡通常需要大量的標注樣本，上述的深度哈希算法基本都是有監督的哈希算法，在實際應用中有時這種標注的樣本難以獲得，因此很多學者開始探索非監督的學習方式獲取哈希碼。CVPR 2017中有4篇介紹深度哈希的文章，其中3篇都涉及非監督的學習方式。多量化深度二值特征學習[15]（Learning Deep Binary Descriptor with Multi-Quantization， DBD-MQ）將二值化過程看作是非監督多量化的過程，提出了基于K-自編碼網絡的深度多量化算法，并將其應用于深度二值特征學習，提出了多量化深度二值特征學習，降低了二值化造成的量化損失。

4 其他應用

以上的哈希算法基本是應用于圖片檢索的，除此之外，哈希算法在其他領域也有很大的優勢，并得到了很多學者的關注。

深度視頻哈希[16]（Deep Video Hashing， DVH）是一種典型的視頻哈希，使用深度學習框架學習整個視頻的二進制哈希碼，以便能夠很好地利用時間信息和鑒別信息。作者將每個視頻中不同幀之間的時間信息融合在一起，以學習兩種標準下的特征表示：來自同一類的特征對之間的距離較小，來自不同類的特征對之間的距離較大；同時最小化了實值特征與二進制碼之間的量化損失。

還有一種典型的應用就是跨模態檢索，所謂的跨模態檢索就是系統的輸入和輸出是不同模態的數據，常見的就是輸入關鍵字輸出相應的圖片[17]。介紹了一種跨模態深度哈希算法（Deep CrossModal Hashing， DCMH），意在建立一個公共空間，要求相似的樣本在同一個空間里，且相似的相本必須相鄰，同時，通過對圖像和圖像、圖像和文本、文本和文本這幾種樣本加以約束，以保證兩模態樣本達到對齊的目的。筆者利用一個兩路的深度模型，將文字和圖像兩種模態投影到這個公共空間，即可實現在這個公共空間完成跨模態檢索。

5 結語

哈希算法占用空間小，計算速度快，可以在帶寬和計算成本的雙重限制下，實現大規模數據檢索。基于深度學習的哈希算法，以其強大的學習能力，一出現就快速超越傳統的哈希算法，得到快速的發展。但這才是開始，尋找更合適的網絡結構、性能更好的正則項，用于更多的領域，這些問題還有待進一步探索。

參考文獻

[1] G. Shakhnarovich， T. Darrell，P. Indyk. Nearest-Neighbor Methods in Learning and Vision[J]. Pattern Analysis & Applications，2006，19（19）：377.

[2] T. Ge， K. He， Q. Ke，et al. Optimized Product Quantization for Approximate Nearest Neighbor Search [A].IEEE Conference on Computer Vision and Pattern Recognition[C].IEEE，2013：2946-2953.

[3] M. Datar， N. Immorlica，P. Indyk. Locality-sensitive hashing scheme based on p-stable distributions[A].Proc. Symposium on Computational Geometry[C].2004：253-262.

[4] A. Dasgupta， R. Kumar，T. Sarlos. Fast locality-sensitive hashing[A].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM，2011： 1073-1081.

[5] R. Salakhutdinov，G. E. Hinton. Semantic hashing [J]. International Journal of Approximate Reasoning，2009，50（7）：969-978.

[6] B. Kulis，K. Grauman. Kernelized. Locality Sensitive Hashing[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2012，34（6）：1092.

[7] R. Xia， Y. Pan， H. Lai，et al. Yan. Supervised hashing for image retrieval via image representation learning[A].The Association for the Advancement of Artificial Intelligence. AAAI Press[C].2014：2.

[8] H. Lai， Y. Pan， Y. Liu，et al. Simultaneous feature learning and hash coding with deep neural networks[A].Computer Vision and Pattern Recognition[C].IEEE，2015： 3270-3278.

[9] F. Zhao， Y. Huang， L. Wang， T. Tan. Deep semantic ranking based hashing for multi-label image retrieval [A].Computer Vision and Pattern Recognition[C].IEEE， 2015：1556-1564.

[10] K. Lin， H.F. Yang， J.H，et al. Deep learning of binary hash codes for fast image retrieval[A].Computer Vision and Pattern Recognition Workshops[C]. IEEE，2015：27-35.

[11] R. Zhang， L. Lin， R. Zhang，et al Bit-Scalable Deep Hashing With Regularized Similarity Learning for Image Retrieval and Person Re-Identification[J]. IEEE Transactions on Image Processing，2015，24（12）：4766-4779.

[12] H. Liu， R. Wang， S. Shan，et al. Deep Supervised Hashing for Fast Image Retrieval[A]. Computer Vision and Pattern Recognition[C]. IEEE，2016：2064-2072.

[13] H. Zhu， M. Long， J. Wang，et al. Deep Hashing Network for efficient similarity retrieval[A].The Association for the Advancement of Artificial Intelligence[C].AAAI Press，2016：2415-2421.

[14] W. Li， Sh. Wang， W. Kang. Feature Learning based Deep Supervised Hashing with Pairwise Labels[A]. International Joint Conference on Artificial Intelligence[C].IJCAI，2016：1711-1717.

[15] Y. Duan， J. Lu， Z. Wang，et al. Learning Deep Binary Descriptor with Multi-quantization[A]. Computer Vision and Pattern Recognition[C]. IEEE，2017：4857-4866.

[16] V.E. Liong，J. Lu，Y.P.Tan，et al.Deep Video Hashing[J].IEEE Transactions on Multimedia，2017，19（6）：1209-1219.

[17] Q. Jiang， W. Li. Deep Cross-Modal Hashing[A]. Computer Vision and Pattern Recognition[C].IEEE， 2017：3270-3278.