亓海鳳　王永

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

關(guān)鍵詞：深度哈希 近似近鄰搜索 哈希性能

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

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

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

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

1.1 哈希函數(shù)設(shè)計

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

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

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

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

1.2 哈希表生成

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

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

1.3 哈希檢索

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

（3）

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

2 哈希函數(shù)的發(fā)展歷程

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

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

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

3 深度哈希

不管是局部敏感哈希還是基于學(xué)習(xí)的哈希算法，都需要先將樣本從原始空間轉(zhuǎn)換到特征空間，然后再將樣本特征映射為哈希碼。由于深度神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)能力非常強大，神經(jīng)網(wǎng)絡(luò)已經(jīng)開始運用于哈希算法，代替?zhèn)鹘y(tǒng)的人工設(shè)計圖像特征的方式，將圖片作為網(wǎng)絡(luò)的輸入，訓(xùn)練獲取哈希碼。

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

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

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

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

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

以上4篇文章的大致可以歸納出深度哈希算法的基本結(jié)構(gòu)包括：深度網(wǎng)絡(luò)模型、正則項和損失函數(shù)，這三項也是現(xiàn)在深度哈希領(lǐng)域的重點研究對象，特別是正則項?，F(xiàn)有的激活函數(shù)大都是由sigmoid或者tanh實現(xiàn)，這類激活函數(shù)有明顯的飽和性質(zhì)，當(dāng)輸出接近期望值時，梯度越小，訓(xùn)練的難度就會越大，很多學(xué)者開始探索sigmoid/tanh的替代品。

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

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

4 其他應(yīng)用

以上的哈希算法基本是應(yīng)用于圖片檢索的，除此之外，哈希算法在其他領(lǐng)域也有很大的優(yōu)勢，并得到了很多學(xué)者的關(guān)注。

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

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

5 結(jié)語

哈希算法占用空間小，計算速度快，可以在帶寬和計算成本的雙重限制下，實現(xiàn)大規(guī)模數(shù)據(jù)檢索?；谏疃葘W(xué)習(xí)的哈希算法，以其強大的學(xué)習(xí)能力，一出現(xiàn)就快速超越傳統(tǒng)的哈希算法，得到快速的發(fā)展。但這才是開始，尋找更合適的網(wǎng)絡(luò)結(jié)構(gòu)、性能更好的正則項，用于更多的領(lǐng)域，這些問題還有待進一步探索。

參考文獻

[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.