【度量学习 · 三】度量学习的典型应用：图像检索

原文刊发于：https://zhuanlan.zhihu.com/p/21396173，经原作者修改后转载

一、简介

最近邻搜索（nearest neighbor search）问题的定义是：给定一个查询（query），目标是要找到空间中离它最近的点。例如在图像特征空间中进行最近邻搜索，目标就是要找到特征最相似的点；在语义空间中进行最近邻搜索，就是要找到语义最相似的点。

    实现最近邻搜索最简单的方法就是提取query的某种特征后，在特征空间中与所有数据库样本对的特征计算相似度，然后按照相似度从大到小的顺序返回结果。这种做法虽然能够达到目的，但是在数据规模大、特征维度高的情况下，会遇到计算时间长、存储空间消耗大的问题，不能满足实际业务中对实时性的要求，因此在实际业务中无法应用。

为了解决上面的问题，近年来近似最近邻搜索（approximate nearest neighbor search）技术发展迅猛，因为在检索时间和消耗的存储空间上都更低，因此成为了一种实用的替代方案。在这其中的代表性方法是哈希（hashing）。

哈希算法的目标是将样本表示成一串固定长度的二值编码，使得相似的样本具有相似的二值码（使用Hamming距离度量二值码之间的相似性）。不难看出，哈希的目标与度量学习的目标非常相似。

早期的哈希算法主要是通过在特征空间中随机选择一些超平面对空间进行划分，根据样本点落在超平面的哪一侧来决定每个bit的取值。这类方法虽然有严格的理论证明保证其效果，但是在实际操作中通常需要比较多的bit才能得到令人满意的检索效果。在之后的工作中，为了得到编码长度更短、检索效果更好的二值码，逐渐引入了度量学习的算法，通过学习而不是随机生成的方式来得到超平面，即所谓的哈希函数。

与标准的度量学习算法相比，哈希方法的目标是得到二值编码，所以优化过程中经常会遇到离散取值的约束，因此通常来说无法使用基于梯度的方法对目标函数进行优化。为了简化问题，通常的做法是改用一个更宽松的约束，比如不再要求“二值码”是二值的，而是只要在一个规定的范围中即可。优化结束后，再对松弛过的“二值码”进行量化，得到最终的真二值码，深度哈希算法通常也采用这种做法。所以深度哈希学习算法的总体思路通常可以总结为“度量学习 + 量化损失”。

二、深度哈希算法

2.1 单模态哈希

    单模态哈希的query和数据库中样本都是来自同一种模态的数据，例如都是图像，或者都是文本。

最早的基于深度学习的单模态哈希算法应该是2009年由Hinton研究组提出的Semantic Hashing方法[1]。对于这个方法来说，深度模型只是提供了一定的非线性表示能力，而网络的输入仍是手工设计的特征，和现在通常意义上的深度学习算法还是有一定的区别，在此一笔带过。

2014年，受到CNN在ImageNet比赛中取得优异战绩的鼓舞，中山大学的潘炎老师研究组和颜水成老师合作，在美国人工智能协会年会（AAAI 2014）上发表的论文提出了一种名为CNNH（Convolutional Neural Network Hashing）的方法[2]，把基于CNN的深度哈希算法推到了前台。CNNH的做法如下图所示，首先通过对相似度矩阵（矩阵中的每个元素指示对应的两个样本是否相似）进行分解，得到样本的二值编码；然后，利用CNN对得到的二值编码进行拟合。拟合的过程相当于一个多标签预测问题，作者使用了交叉熵损失来达到这个目的，这一步对应图中最右侧红色节点。此外，作者还提出加入分类的损失函数来进一步提升性能（softmax，对应图中最右侧黑色节点）。

尽管实验中CNNH相比传统的基于手工设计特征的方法取得了显著的性能提升，但是这个方法仍然不是端到端的方法，学到的图像表示不能反作用于二值编码的更新，因此并不能完全发挥出深度学习的能力。为了更好地挖掘深度模型的潜力，在这之后，出现了不少改进方法。

2015年计算机视觉与模式识别会议（CVPR 2015）中，一下子出现了四篇基于深度学习的哈希算法。在这四篇文章之中，其中一篇文章（在此不对这篇文章做详细介绍，有兴趣的同学可以参考[3]）使用手工设计特征作为输入之外，其余的三篇均为完全的端到端模型。下面具体介绍一下这三篇文章。

第一篇文章[4]与上面介绍的CNNH一样，同样是来自中山大学的潘炎老师研究组和颜水成老师。因为这篇文章中使用了一个比CNNH中的网络深得多的Network in Network的网络结构，因此被简称为NINH（NIN Hashing）或DNNH（Deep Neural Network Hashing）。这篇文章的做法如下图所示。网络使用三张图像构成的三元组进行训练。在三元组中，其中的第一张图像和第二张图像是相似的，而第一张图像和第三张图像则是不相似的。基于三元组的损失函数的目标是：在得到的Hamming空间中，相似样本间的距离小于不相似样本间的距离（下图右上）。值得一提的是，这项工作为了适配哈希学习这个任务，在网络结构上做了一些有针对性的设计，包括：

（1）为了减小二值码不同bit之间的冗余性，作者提出使用部分连接层代替全连接层，每个部分负责学习一个bit，各部分之间无连接（下图左slice layers）；

（2）为了避免二值码学习中的离散取值约束，像大多数哈希方法一样，作者使用sigmoid激活函数将离散约束松弛为范围约束（{0,1}→(0,1)），同时为了保持学到的特征空间和Hamming空间相似，引入了分段量化函数（下图右下）。以上这两部分合在一起，构成了图中的divide-and-encode模块。该方法可以端到端的训练，学到的图像表示可以反作用于二值码，因此相比于CNNH，性能有所提升。

第二篇文章[5]来自中科院自动化研究所的谭铁牛老师的研究组，和DNNH相比没有在网络结构上下太大功夫，而是更多地关注了损失函数这一块。文章中使用了类似于DeepID2的网络结构，如下图所示。回头来看图像检索这个任务，任务的目的无非就是把数据库中的图像，按照和查询图像的相关性由大到小的顺序，依次返回。基于这个思想，这篇文章中提出直接让网络学习这个排序，因此该方法称为DSRH（Deep Semantic Ranking Hashing）。事实上，这种做法相当于直接对最终的评测指标进行优化，相当于开启了上帝模式。但是实际中上帝模式并不是那么容易开的，直接优化排序并不容易，因此作者使用了一个凸上界作为替代，进行优化。

第三篇文章[6]来自台北中央研究院的陈祝嵩研究组，出现在当年的CVPR workshop中，其中使用了一种比较直接的方法来学习二值编码，该方法名为DLBHC（Deep Learning of Binary Hash Codes），方法流程如下图所示。其核心点为：在预训练好的网络倒数第二层和最终的任务层中间，插入一个新的全连接层，这个层使用sigmoid激活函数来提供范围约束，节点数即为目标二值码的码长。通过端到端的finetune，可以将语义信息嵌入到这个新加入的全连接层输出之中。虽然这么做得到的二值码中包含语义信息，但是由于在训练过程中没有显式地考虑样本点之间的相对位置关系，并不能保证Hamming距离近的点在语义上也相近，因此和最终的检索任务还是有些偏离。

同年，由中山大学林倞老师、哈尔滨工业大学左旺孟老师和香港理工大学张磊老师等人合作的文章发表在当年的Transactions on Image Processing (TIP 2015)中[7]，作者提出了一种使用加权Hamming距离代替标准Hamming距离的哈希方法DRSCH（Deep Regularized Similarity Comparison Hashing），如下图所示。该方法同样使用基于三元组的损失，同时使用图像对（image pair）之间的相似性作为正则项，希望得到的网络能够同时保持三元组确定的关系和图像对确定的关系（实验表明这两者虽然看上去是在描述一样的东西，但是这种做法确实能取得一定的效果提升）。在网络学习的过程中，加权Hamming距离的权值也作为参数进行更新，从而得到与网络匹配的权值。虽然这篇文章中使用的加权Hamming距离的时间复杂度要略大于标准Hamming距离，但是也带来了额外的好处：一方面，可以以很高的效率计算更加精确的距离；另一方面，可以通过权值来选择bit，从而得到不同码长的二值码，而不必像之前的方法一样每换一个码长就重新训练一个模型。此外，和DNNH相似，这篇文章的作者也设计了一种操作来保证学到的空间接近于Hamming空间，其形式类似于双曲正切函数（tanh）。

以上四篇文章中的框架，可以代表大多数深度哈希文章的做法，可以总结为：深度模型学习图像表示 + sigmoid/tanh函数限制输出范围 + 不同的损失函数 + （可选）有针对性的网络结构。这四个部件合在一起，组合出了很多种不同的方法，在此就不再详细介绍这些衍生方法了。

上述框架中，问题比较大的一个地方在于sigmoid/tanh的使用。由于这类激活函数具有饱和的性质，越是当输出接近期望的值的时候（0/1或-1/+1），梯度就越小，网络训练也就越困难。因此，最近的一些工作开始关注sigmoid/tanh的替代品。例如，我们发表在CVPR 2016的工作DSH（Deep Supervised Hashing）[8]中，使用了如下图所示的一个正则项，来对网络的输出进行约束，使之接近二值编码。当网络的输出和期望得到的值偏差越大的时候，损失也越大，但是同时，梯度的值保持在-1或+1，来保证训练过程的稳定性。此外，类似的正则思想在清华大学的Haiyi Zhu博士等人发表在AAAI 2016和李武军老师研究团队发表在2016年国际人工智能联合会议（IJCAI 2016）的两篇工作中也有体现[9,10]。和侧重于设计损失函数的方法相比，这类方法的关注点在于量化部分，而这在传统哈希方法中也是一个重要的研究方向。

以上介绍的深度哈希方法在生成二值码的时候，只需要将图像送入训练好的网络，并将网络输出进行量化。值得一提的是，由于传统哈希方法需要同时使用多种特征才能达到和深度哈希方法可比的性能，提取特征的时间严重拖慢了传统方法在实际应用中的编码速度，因此深度哈希方法在编码速度上甚至有时会优于传统方法。

需要指出，目前很多深度哈希算法在对比同类方法的时候，用的都是对比方法原文中的网络结构，而自己却用更深、更复杂的结构。在我看来，这种对比并不能很好地反映方法本身的好坏，更合适地对比方法应该是大家使用基本一致的结构进行对比。

2.2 多模态哈希

上面介绍的方法解决的都是以图搜图的单模态检索问题，在跨模态检索中，哈希算法也有应用。例如：当我们在搜索引擎中输入一些关键词搜索相关的图像时，就可以用到跨模态哈希算法。

通常来说，关键词（文本）和图像并不在同一个特征空间中，因此无法直接比较。在2016年年初，李武军老师带领的研究团队在arXiv上发布了一篇文章，其中介绍了一种跨模态深度哈希算法DCMH（Deep Cross-Modal Hashing）[11]。这篇文章中，作者利用一个两路的深度模型将两种不同模态的数据（文章中是文本和图像）变换到一个公共空间，并要求相似的样本在这个公共空间中相互靠近，如下图所示。通过同时对图像和图像、图像和文本、文本和文本这几种不同类型的样本对施加这个约束，可以保证两种模态样本的对齐。如此一来，即可实现在公共空间中的跨模态检索。

三、总结

基于深度学习的哈希算法，凭借深度学习的强大特征学习能力，基于度量学习算法，目前已成为图像检索、跨模态检索等检索任务中的核心技术。但是目前深度度量学习算法中的难训练等问题仍然是深度哈希算法绕不过去的坎，未来深度哈希算法的提升，还高度依赖于深度度量学习算法的研究和发展。

四、参考文献

[1] Ruslan Salakhutdinov, Geoffrey Hinton. Semantic Hashing. IJAR 2009.

[2] Rongkai Xia, Yan Pan, Hanjiang Lai, Cong Liu, Shuicheng Yan. Supervised Hashing for Image Retrieval via Image Representation Learning. AAAI 2014.

[3] Venice Erin Liong, Jiwen Lu, Gang Wang, Pierre Moulin, Jie Zhou. Deep Hashing for Compact Binary Codes Learning. CVPR 2015.

[4] Hanjiang Lai, Yan Pan, Ye Liu, Shuicheng Yan. Simultaneous Feature Learning and Hash Coding with Deep Neural Networks. CVPR 2015.

[5] Fang Zhao, Yongzhen Huang, Liang Wang, Tieniu Tan. Deep Semantic Ranking Based Hashing for Multi-Label Image Retrieval. CVPR 2015.

[6] Kevin Lin, Huei-Fang Yang, Jen-Hao Hsiao, Chu-Song Chen. Deep Learning of Binary Hash Codes for Fast Image Retrieval. CVPR 2015 workshop.

[7] Ruimao Zhang, Liang Lin, Rui Zhang, Wangmeng Zuo, Lei Zhang. Bit-Scalable Deep Hashing with Regularized Similarity Learning for Image Retrieval and Person Re-identification. TIP 2015.

[8] Haomiao Liu, Ruiping Wang, Shiguang Shan, Xilin Chen. Deep Supervised Hashing for Fast Image Retrieval. CVPR 2016.

[9] Han Zhu, Mingsheng Long, JianminWang,Yue Cao. Deep Hashing Network for Efficient Similarity Retrieval. AAAI 2016.

[10] Wu-Jun Li, Sheng Wang, Wang-Cheng Kang. Feature Learning based Deep Supervised Hashing with Pairwise Labels. IJCAI 2016.

[11] Qing-Yuan Jiang, Wu-Jun Li. Deep Cross-Modal Hashing. arXiv:1602.02255.