亓海鳳　王永

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

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

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

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

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

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

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

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

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

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

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

1.2 哈希表生成

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

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

1.3 哈希檢索

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

（3）

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

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

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

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

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

3 深度哈希

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

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

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

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

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

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

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

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

深度神經(jīng)網(wǎng)絡(luò)通常需要大量的標(biāo)注樣本，上述的深度哈希算法基本都是有監(jiān)督的哈希算法，在實(shí)際應(yīng)用中有時(shí)這種標(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)勢(shì)，并得到了很多學(xué)者的關(guān)注。

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

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

5 結(jié)語

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

參考文獻(xiàn)

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