论文笔记： Deep Quantization Network for Efficient Image Retrieval

灵魂三问

论文提出的问题

由于quantization error， 哈希编码将不能准确地表达特征

论文做了什么？

1. 用多池化层卷积神经网络，来表达图片
2. 用全连接的哈希层来生成二进制哈希编码
3. 用相应的交叉熵层来学习相似性
4. 用配对的量化损失来控制哈希质量

论文达到了什么效果？

通过在标准的哈希检索数据集上的实验，文中的方法超过了最新的哈希方法。

深度哈希网络 Deep Hashing Network

相似检索通常是给一系列为N个点的的数据集$\left\{\boldsymbol{x}_{i}\right\}_{i=1}^{N}${xi​}i=1N​， 其中每一个点都是一个D维的特征向量$\boldsymbol{x} \in \mathbb{R}^{D}$x∈RD

所以我们的目标就是找一个非线性的哈希函数$f: \boldsymbol{x} \mapsto \boldsymbol{h} \in\{-1,1\}^{K}$f:x↦h∈{−1,1}K来编码，将每一个$x$x编码成一个K-比特的哈希码。其中 $\mathcal{S}=\left\{s_{i j}\right\}$S={sij​}通常由语义来构建。

所以整个结构以配对$\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}, s_{i j}\right)$(xi​,xj​,sij​)的形式作为输入。

模型

作者从Alexnet网络开始，作者将AlexNet网络中全连接层 fc8换成了 fch层，包括了K个隐形单元，也就是将fc7层转换为了一个K维的哈希编码。并把这一层的输出结果叫做$z_i^8$zi8​也就是第八层的输出，也就是哈希编码。

作者将输出挤压到$[-1,1]$[−1,1]上，通过hyperbolic tangent(tanh)函数。

这个文章中，作者使用了pairwise-relationship，以及在Bayesian框架下控制了量化差异。

我们用汉明距离（Hamming distance）表示两个二进制编码的距离$\operatorname{dist}_{H}\left(\boldsymbol{h}_{i}, \boldsymbol{h}_{j}\right)=\frac{1}{2}\left(K-\left\langle\boldsymbol{h}_{i}, \boldsymbol{h}_{j}\right\rangle\right)$distH​(hi​,hj​)=21​(K−⟨hi​,hj​⟩)

我们用MLP最大似然估计估计$H$H, 也就是MAP 估计
$\begin{aligned} \log p(\boldsymbol{H} \mid \mathcal{S}) & \propto \log p(\mathcal{S} \mid \boldsymbol{H}) p(\boldsymbol{H}) \\ &=\sum \log p\left(s_{i j} \mid \boldsymbol{h}_{i}, \boldsymbol{h}_{j}\right) p\left(\boldsymbol{h}_{i}\right) p\left(\boldsymbol{h}_{j}\right) \end{aligned}$logp(H∣S)​∝logp(S∣H)p(H)=∑logp(sij​∣hi​,hj​)p(hi​)p(hj​)​
这其中$p(\mathcal{S} \mid \boldsymbol{H})$p(S∣H) 是似然方程，对于每一个配对$p\left(s_{i j} \mid \boldsymbol{h}_{i}, \boldsymbol{h}_{j}\right)$p(sij​∣hi​,hj​)是一个条件概率，定义为
$\begin{aligned} p\left(s_{i j} \mid \boldsymbol{h}_{i}, \boldsymbol{h}_{j}\right) &=\left\{\begin{array}{ll} \sigma\left(\left\langle\boldsymbol{z}_{i}^{l}, \boldsymbol{z}_{j}^{l}\right\rangle\right), & s_{i j}=1 \\ 1-\sigma\left(\left\langle\boldsymbol{z}_{i}^{l}, \boldsymbol{z}_{j}^{l}\right\rangle\right), & s_{i j}=0 \end{array}\right.\\ &=\sigma\left(\left\langle\boldsymbol{z}_{i}^{l}, \boldsymbol{z}_{j}^{l}\right\rangle\right)^{s_{i j}}\left(1-\sigma\left(\left\langle\boldsymbol{z}_{i}^{l}, \boldsymbol{z}_{j}^{l}\right\rangle\right)\right)^{1-s_{i j}} \end{aligned}$p(sij​∣hi​,hj​)​={σ(⟨zil​,zjl​⟩),1−σ(⟨zil​,zjl​⟩),​sij​=1sij​=0​=σ(⟨zil​,zjl​⟩)sij​(1−σ(⟨zil​,zjl​⟩))1−sij​​

其中$\sigma(x)=\frac{1}{1+e^{-x}}$σ(x)=1+e−x1​

这样，如果两个式子相乘大于0，那么两个式子比较相似，相反，如果小于0，那么p接近0，说明两个输入不相似。那

直接使得$\boldsymbol{h}_{i} \in\{-1,1\}^{K}$hi​∈{−1,1}K的离散优化非常难，作者希望可以使用一个连续函数那放松对$h_i$hi​的限制。

过去的连续放松一直面对两个问题：

（1）uncontrollable quantization error by binarizing continuous embeddings to binary codes.

也就是最后将连续函数二进制化时导致的数量错误。

（2）) large approximation error by adopting inner product between continuous embeddings as the surrogate of Hamming distance between binary codes.

在用内积代替汉明距离的时候导致的估计误差。

作者为了控制quantization error 以及消除内积代替汉明距离导致的误差， 作者使用了bimodal Laplacian先验概率
$p\left(\boldsymbol{h}_{i}\right)=\frac{1}{2 \epsilon} \exp \left(-\frac{\left\|\boldsymbol{h}_{i} \mid-\mathbf{1}\right\|_{1}}{\epsilon}\right)$p(hi​)=2ϵ1​exp(−ϵ∥hi​∣−1∥1​​)
其中的$\epsilon$ϵ是一个分散超参数（diversity parameter）。这个先验分布可以在下图表示

代入MAP公式， 于是DHN优化问题就变成了
$\min _{\Theta} C=L+\lambda Q$Θmin​C=L+λQ
其中$\lambda=1 / \epsilon$λ=1/ϵ就是在配对交叉熵（pair-wise cross entropy）与量化损失（quantization loss）之间的权衡了。$\Theta \triangleq\left\{\boldsymbol{W}^{\ell}, \boldsymbol{b}^{\ell}\right\}$Θ≜{Wℓ,bℓ}表示网络参数。

其中配对交叉熵被定义为
$L=\sum_{s_{i j} \in \mathcal{S}}\left(\log \left(1+\exp \left(\left\langle\boldsymbol{z}_{i}^{l}, \boldsymbol{z}_{j}^{l}\right\rangle\right)\right)-s_{i j}\left\langle\boldsymbol{z}_{i}^{l}, \boldsymbol{z}_{j}^{l}\right\rangle\right)$L=sij​∈S∑​(log(1+exp(⟨zil​,zjl​⟩))−sij​⟨zil​,zjl​⟩)
同样，量化损失由以下定义而来
$Q=\sum_{s_{i j} \in \mathcal{S}}\left(\left\|\left|z_{i}^{l}\right|-1\right\|_{1}+\left\|\left|z_{j}^{l}\right|-1\right\|_{1}\right)$Q=sij​∈S∑​(∥∥​∣∣​zil​∣∣​−1∥∥​1​+∥∥​∣∣​zjl​∣∣​−1∥∥​1​)
但这是个非光滑函数，我们想变成光滑函数通过$|x| \approx \log \cosh x$∣x∣≈logcoshx，于是
$Q=\sum_{s_{i} \in \mathcal{S}} \sum_{k=1}^{K}\left(\log \cosh \left(\left|z_{i k}^{l}\right|-1\right)+\log \cosh \left(\left|z_{j k}^{l}\right|-1\right)\right)$Q=si​∈S∑​k=1∑K​(logcosh(∣∣​zikl​∣∣​−1)+logcosh(∣∣​zjkl​∣∣​−1))
在优化MAP估计之后哦，我们得到了统计上的最优解，只用让$h \leftarrow \operatorname{sgn}\left(z^{i}\right)$h←sgn(zi)就可以得到哈希编码了。

理论分析

ITQ中， point-wise quantization error是以文中的quantization loss 为上界的
$\left\|\boldsymbol{h}_{i}-\operatorname{sgn}\left(\boldsymbol{h}_{i}\right)\right\|_{2} \leq\left\|\boldsymbol{h}_{i} \mid-\mathbf{1}\right\|_{1}$∥hi​−sgn(hi​)∥2​≤∥hi​∣−1∥1​

总结

t(\boldsymbol{h}{i}\right)\right|{2} \leq\left|\boldsymbol{h}{i} \mid-\mathbf{1}\right|{1}
$$

总结

总的来说，作者使用了两部分损失函数，一部分是Pair-wise cross-entropy用来控制不同点之间的距离，使其根据相似性来判断。另一部分是pairwise quantization loss用来控制$h$h, 使其可以尽量靠近-1或者1.