图像检索 Deep Hashing_quantization loss

在检索任务中，Metric Learing是为了得到具有很好表征能力的特征向量， Deep Hashing则是为了得到具有很好表征能力的二值向量。 那么二值向量相比于一般的特征向量，优势在哪里呢？ 主要有两点：

1. 更少的存储空间： 二值向量只有0和1, 可以节约大量的存储空间。以1024维的特征为例，如果是二值特征， 只需要1024 / 8 = 128byte. 如果是浮点特征， 需要的空间大小为1024 * 4 = 4KB。 相比之下，二值向量的存储空间为浮点特征的1/32.
2. 更高的检索效率： 二值向量，通常采用Hamming Distance来衡量二者之间的距离；浮点向量，通常采用inner product、L2 Distance、cosine similarity来计算向量距离。 对于计算机来说， 计算Hamming Distance实际是在做bit的异或，可以非常高效的并行执行，相比于其他三种距离计算方式来说，具有天然的计算速度优势。

Deep Hashing也是随着深度学习的兴起发展起来的。自从2014年首篇论文问世之后， 每年均有3~5篇不错的工作，本文以时间为主轴，记录该领域一些有代表性的工作：

2014年：

Supervised Hashing for Image Retrieval via Image Representation Learning

简称CNNH, 由中山大学的潘炎老师组和新加坡国立的颜水成老师组合作完成，发表于当年的AAAI上。这是一个two stage的方法：

stage one: 通过对相似度矩阵（矩阵中的每个元素指示对应的两个样本是否相似）进行分解，得到样本的二值编码。

stage two: 利用CNN对得到的二值编码进行拟合。 拟合的过程相当于一个多标签预测问题，作者使用了交叉熵损失来达到这个目的，这一步对应图中最右侧红色节点（文中称该方案为CNNH) 。此外，作者还提出加入分类的损失函数来进一步提升性能（对应图中最右侧黑色节点, 文中称该改进方案为CNNH+）。

尽管实验中CNNH相比传统的基于手工设计特征的方法取得了显著的性能提升，但该方法也有明显的缺陷：1） 它不是一种端到端的方法； 2） 学到的图像表示不能反作用于二值编码的更新，因此并不能完全发挥出深度学习的能力。

Supervised Hashing for Image Retrieval via Image Representation Learning_南有乔木NTU的博客-CSDN博客

2015年：这一年随着深度学习的进一步发展，很多当时优秀的方法也被用在Hash coding上。总体来讲，已经统一是one stage的处理方式。

DNNH: Simultaneous Feature Learning and Hash Coding with Deep Neural Networks

深度学习入门:Simultaneous Feature Learning and Hash Coding with Deep Neural Networks_liyaohhh的博客-CSDN博客

方法主要的新颖点包括如下3处：

1） 采用triplet loss： hashing问题都会采用某种metric learning的loss, 比如constrstive loss or triplet loss, 不过会在此基础上再加一些正则项

2） 离散约束方面，采用sigmoid激活函数，将feature值约束在（0，1); 另外，为了模拟二值操作，加入了piece_wise threshold模块

Piece Wise threshold

3） divide-and-encode结构， 其实就是用部分连接代替了全连接（可以减小码值的冗余性）

 缺陷： 1） 采用了sigmoid激活， 事实上2015年之后的激活函数研究表明relu比sigmoid效果要好，慢慢得更多的网络中采用relu； 2）只引入了triplet loss，起到了metric learning的作用，但却忽视了对于feature二值化效果的约束

DLBHC: deep learning of binary hash codes for fast image retrieval

图像检索系列一：Deep Learning of Binary Hash Codes for Fast Image Retrieval_眼观的博客-CSDN博客

方法很好理解： 在预训练好的网络倒数第二层和最终的任务层中间，插入一个新的全连接层，这个层使用sigmoid激活函数来提供范围约束，节点数即为目标二值码的码长

缺陷：（1）sigmoid的作用，只是对最终输出的feature进行了限幅， 限制到（0，1），但是并不能够保证其能够很好得被二值化；没有正则项 （2）没有引入Metric Learning相关的loss；特征的表征能力有限。 DeepHash = Metric Learning + Binary Code

2015还有一些其他的工作，但印象比较深的就是以上两篇。 概括得讲，这时候的套路可以总结为： 深度模型学习图像表示 + sigmoid/tanh函数限制输出范围 + 不同的损失函数（Metric Learning) + 针对性的网络结构。 此框架中，最大的问题在于sigmoid/tanh的使用。这类激活函数具有饱和特性， 当输出接近于0或者是1时， 梯度很小，网络训练变得困难。后续的工作，基本都会舍弃sigmoid/tanh操作，而是直接在feature上，加正则项进行约束。

2016年：

2016年有4篇比较有代表性的工作，分别简写为DSH、DPSH、DTSH、DHN; 对应的全称为：

DSH: Deep Supervised Hashing for Fast Image Retrieval

Deep Supervised Hashing for Fast Image Retrieval_与图像检索的爱恨情仇的博客-CSDN博客

DPSH: Feature Learning based Deep Supervised Hashing with Pairwise Labels

DTSH: Deep Supervised Hashing with Triplet Labels

DHN: deep hashing network for efficient similarity retrieval

于该领域的文章通常用简写表示，而简写之间的差异又比较小，所以最好能够依据自己的理解，分辨出不同简写对应的文章的主体差异。

2016年的工作相较于2015年，几乎清一色丢弃了sigmoid/tanh这样的激活函数， 而是聚焦在正则项的设计上，差异更多体现在Loss和正则式的不同。并且，在期望二值的选取上，不再是{0，1}； 而是变成了{-1，1}。在此只比较各种算法之间的差异，具体内容以阅读论文原文为准：

共性的部分： 1）均采用了样本对， 无论是pair 或者是 triplet; 2) 均做了relaxtion, 如果不做的话，网络不可导，无法训练； 网络能训练、能收敛是头等大事； 3) 均加了正则项， 无论是L1 norm或者是L2 norm.

2017年：

HashNet: 1) 提出用一组连续的激活函数去逼近sgn函数，并且可以在训练的过程中去不断增大beta; 2) 解决data imbalanced的问题，提出了wml: weighted maximum likelihood;

DSDH(deep surpervised discrete network)：1）h 与 b 相分离，且训练时不具有显式的相互关系； 2） Metric Learning 相关的loss之外，引入了classification分支，且以b作为输入； h通过pairwise label进行学习； b通过classification label进行学习； 3） h和b之间的量化误差作为整体loss的一部分； 4）新的优化学习方法，区别于sgd, 使得整个优化过程能够持续下去

DAPH(deep asymmetric pairwise hashing)： 核心贡献在于提出了pairwise feature计算，采用两个同结构、不同参数的网络，分别进行学习； 并提出了二值特征的独立性(independence)和平衡性(balance)，以此作为约束

LCDSH(locality constrained deep surpervised hashing)： 1）研究了量化误差对feature的影响，提出引入量化误差， 会影响feature的表征性； 2）pairwise similarity中，首次将相似样本标记为1，不相似样本标记为-1； 3）不再用常见的|||x| - 1|| 或者是|u - sgn(u)|来引入量化误差，而是使用P(U|B)

1. HashNet:

HashNet: Deep Learning to Hash by Continuation​arxiv.org/abs/1702.00758

HashNet的网络结构示意

Loss设计：

Weighted Maximum Likelihood(WML)

权值的计算方式

最大似然估计的公式

sgn近似：

离散不可导的sgn(z)，转化为连续可导的tanh(k * z)

相比于2016年的DHN算法，MAP提升明显

2. DSDH:

Deep Supervised Discrete Hashing​papers.nips.cc/paper/2017/file/e94f63f579e05cb49c05c2d050ead9c0-Paper.pdf

Loss设计：

其中： 第一项是常见的pairwise similarity maximum likelihood. 后面两项为classification分支的loss约束。 这里没有采用一般分类所用cross-entropy分支，而是采用了L2 loss，可能是考虑到这儿的label有可能是多标签。

Relaxtion:

1. 引入auxiliary variable h：

2. 依据Lagrange公式，进一步变换：

3. 进一步relax, h与b解耦：

至此，完成了整体loss的设计。 可以看到：h仅作用于pairwise similarity loss; b作用于classfication分支的loss. 两者通过L2距离进行相互约束

Optimization:

由于loss中引入了离散变量b, 使得整体的loss反向传播变得不怎么顺畅。作者重新设计了一种迭代更新机制，使得整个网络的训练能够持续迭代下去，但公式比较繁琐，在此不再赘述。

3. LCDSH：

Locality constrained deep surpervised hashing​www.ijcai.org/proceedings/2017/0499.pdf

LCDSH的网络结构

贡献点1： 指出常见的两种quantization loss会影响feature的性能

Quantization Loss format(1)

Quantization Loss format(2)

LCDSH算法相比于其他方法，在特征直方图上的差异

贡献点2： 新的loss设计

整体Loss设计

第一项P(S|U)的优化

值得一提的是，这儿的negative log-likelihood相较于之前的形式有差异，是因为在LCDSH中，相似样本标记为1，不相似样本标记为-1. 而之前的工作，基本上都是把相似样本标记为1， 不相似样本标记为0.

P(U|B)优化形式

设计成高斯分布的形式

等价的优化形式

最终的loss形式：

该loss可以通过标准的BP算法进行优化，在整体算法设计上显得比较简洁。

相比于2016年的明星算法DPSH和DSH, 指标上都有明显的提升。几处改进值得玩味，训练采用常见的sgd即可，看起来比较实用。

2018年：

stephon：图像检索_Deep Hashing(2)5 赞同 · 2 评论文章正在上传…重新上传取消

GreedyHash: 1) 将sgn函数，直接内嵌在训练过程中（带来的问题是sgn反向传播梯度为0，无法训练）； 2）设计了一种greedy的反向传播算法，具体实现上借助于一个定制的hash layer. 3) Loss设计上只有分类loss和penalty项. 抛弃了前人用的pair-wise 和 triplet-wise 这样的样本对的训练方式，简称point-wise

DCH: 1) 出发点为采用Hamming Space Retrieval来进行检索，其能够保持一个常量的搜索时间； 2）整体Loss设计上采用Bayesian Learning Framework; 3) 分析了前人采用的logistic分布的缺陷，提出了Cauchy distribution，使得相似样本的Hamming distance更加得紧凑

ISDH: 1) 首先，这是一篇探讨多标签Deep Hash的文章，多标签的引入带来了一个问题：如何度量两幅图像的相似度； 2）为了处理多标签相似度的问题，引入了Normalized Semantic Label; 3) 区分处理： 在相似度矩阵中，对于相似度为0/1的 pair对，采用cross-entropy loss来计算； 对于相似度介于0~1的pair对，采用L2 loss计算

ADSH: 1) 相比于主流的研究单标签、对称hash的方法，这篇文章采用的是非对称的处理思路：也就是query image的特征通过网络前向计算得到； database images的特征为网络学习的产物； 2）打破了symemetric 学习的固化思维： 即query和database是通过同一个网络得到的； 3）问题：这样的学习方式，对于新增的检索图像该如何去获取特征呢？ 其效果又如何得到保证？

1. GreedyHash

https://proceedings.neurips.cc/paper/2018/file/13f3cf8c531952d72e5847c4183e6910-Paper.pdf​proceedings.neurips.cc/paper/2018/file/13f3cf8c531952d72e5847c4183e6910-Paper.pdf

整篇文章讨论的是如果把sgn()函数加入到网络中，采用什么样的方法可以让基于sgd的学习策略继续生效。处理方案如下：

核心公式

其中，H为网络输出的浮点特征，B为二值特征。反向传播的时候，通过定义贪心策略人为将sgn()函数的导数设置为1（事实上，严格计算来说，其导数为0）。

2. Deep Cauchy Hashing

https://openaccess.thecvf.com/content_cvpr_2018/papers/Cao_Deep_Cauchy_Hashing_CVPR_2018_paper.pdf​openaccess.thecvf.com/content_cvpr_2018/papers/Cao_Deep_Cauchy_Hashing_CVPR_2018_paper.pdf

整体结构如下图所示：

Framework of DCH

可以看到，特征提取部分并没有什么新意，但Loss包含了两部分:

1). Cauchy cross-entropy loss

2). Cauchy quantization loss

整体上是一个基于贝叶斯学习的框架：

Bayesian Learning Framework

增加权重，解决正负样本不均衡的问题

Add weight to handle data imbalance

建立两个样本间距离和相似度之间的关系

Based on Bernoulli distribution

本文采用柯西分布代替常用的sigmoid激活函数（sigmoid激活函数，无法使得相似的instance汉明距离变得很小，比如说< 2; 这就限制了Hamming Space Retrieval发挥作用）

Cauchy distribution

对距离函数进行relaxation操作：

Distance Relaxation

柯西量化损失：

Cauchy Quantization Loss

因此，整体Loss如下：

DCH Loss formula

实验结果：

Results based on Re-ranking within Hamming Radius 2(MAP@H&amp;amp;amp;amp;amp;lt;=2)

Effect of each component

可以看到，Cauchy quantization loss和Cauchy cross-entropy loss均对最终的结果产生了较大的正向作用。

总结： 本文最核心的亮点是提出了Cauchy Distribution这样一个急剧变化的分布，来将距离转化为相似度；从而使得相似样本对不仅在相对距离上小于不相似的样本对，在绝对距离上也能够更加得紧凑。同时，通过这样一种方式学习到的特征，也需要合适的检索方式与之匹配：Re-ranking within Hamming Radius 2(MAP@H<=2)