深度学习在哈希算法的应用

亓海凤　王永

摘 要：哈希，一种将任意长度的输入二值化输出的过程，被广泛用于快速查找，如分类、检索和拷贝检测等。近年来受到卷积神经网络强大学习能力的影响，很多学者尝试用深度学习的工具进行哈希的探索，也就是所谓的深度哈希算法。深度学习模型是一种能够层进学习的机器工具，它可以通过从低级特征中构建高级特征来学习特征的层次结构，从而使特征构建过程自动化。本文对深度哈希算法进行了总结。

关键词：深度哈希 近似近邻搜索 哈希性能

中图分类号：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.