Pairwise Relationship Guided Deep Hashing for Cross-Modal Retrieval（PRDH）论文阅读笔记。
AAAI 2017
本文提出了基于数据对关系的深度哈希方法，能同时学习每个模态的特征以及哈希码，并且将其整合到一个端到端的框架之中，还加入了模态间和模态内的基于关系对的约束，此外，本文还引入了去关联约束（decorrelation constraints），来提高每个哈希bit的辨别能力。
模型
- 训练集：\[\mathcal{O} = \{o_i\}_{i=1}^N\]，\[\mathbf{X}\] 和 \[\mathbf{Y}\] 分别表示图像和文本数据
- 相似矩阵：\[\mathbf{S}_{N\times N}\]，\[S_{ij}=1\] 表示 \[o_i\] 和 \[o_j\] 相似，\[S_{ij}=0\] 表示不相似
- 为两个模态数据分别学习一个哈希函数 \[h^x(\cdot)\] 和 \[h^y(\cdot)\]，生成长度为 \[c\] 的哈希码
深度框架
对于图像模态，本文使用 VGG-F 网络，并将其 fc8 层用一个有 \[c\] 个结点的 fch 哈希层代替。
对于文本模态，使用由 3 个全连接层构成的多层感知机，并将最后一层做与图像模态一样的处理。
哈希码学习
为了更好地保留训练样本的语义相似度，本文的目标函数包含 4 个部分：
- 不同模态间基于对的损失
- 相同模态内基于对的损失
- 去相关损失
- 正则项损失
基于对的损失使得相似对的相似关联更强，而不相似对的关联更弱，本文使用负对数似然来度量这样的联系。
假设图像网络的输出的哈希码为 \[\mathbf{U}^x = \{U_i^x\}_{i=1}^N\]，文本网络的哈希码输出为 \[\mathbf{U}^y = \{U_i^y\}_{i=1}^N\]，相似标签 \[\mathbf{S} = \{S_{ij}\}\]，似然函数定义如下：
\[ p(S_{ij}|{\mathbf{U}_{*i}^x}^T\mathbf{U}_{*j}^y) = \begin{cases} \sigma(\Omega_{ij}^{xy}) & S_{ij} = 1\\ 1 - \sigma(\Omega_{ij}^{xy}) & S_{ij} = 0 \end{cases} \]
其中 \[\Omega_{ij}^{xy} = \frac12 {\mathbf{U}_{*i}^x}^T\mathbf{U}_{*j}^y\]，\[\sigma(\Omega_{ij}^{xy}) = \frac{1}{1 + e^{-\Omega_{ij}^{xy}}}\]。\[\mathbf{U}_{*i}^x = f^x(x_i, \theta_x)\]，\[\mathbf{U}_{*j}^y= f^y(y_j,\theta_y)\]。因此，不同模态间基于对的损失定义如下：
\[ \begin{align} \mathcal{J}_1 &= -\log p(\mathbf{S}|\mathbf{U}^{xy}) = -\sum_{S_{ij}\in \mathbf{S}} \log p(S_{ij}|\mathbf{U}^{xy}) \\ & = -\sum_{S_{ij}\in\mathbf{S}}(S_{ij}\Omega_{ij}^{xy} - \log(1 + e^{\Omega_{ij}^{xy}})) \end{align} \]
很容易看出，优化上述的损失函数，可以使得两个相似的实例之间的Hamming距离减小，不相似的实例之间的距离增大，所以，这样可以很好的保留不同模态数据的语义相似度。
此外，还需要每种数据在自己的模态中有很好的判别能力，来保留模态内的语义信息，所以，有必要给每个模态加一个模态内基于对的损失。
图像模态内基于对的损失如下：
\[ \begin{align} \mathcal{J}_2 &= -\log p(\mathbf{S}|\mathbf{U}^x) = -\sum_{S_{ij}\in \mathbf{S}} \log p(S_{ij}|\mathbf{U}^x) \\ &= -\sum_{S_{ij}\in\mathbf{S}} (S_{ij}\Omega_{ij}^x- \log (1 + e^{\Omega_{ij}^x})) \end{align} \]
其中 \[\Omega_{ij}^x = \frac12 {\mathbf{U}_{*i}^x}^T\mathbf{U}_{*j}^y\]。
同样的，文本模态内基于对的损失如下：
\[ \mathcal{J}_3 = -\sum_{S_{ij}\in\mathbf{S}}(S_{ij}\Omega_{ij}^y - \log(1+e^{\Omega_{ij}^y})) \]
其中 \[\Omega_{ij}^y = \frac12 {\mathbf{U}_{*i}^y}^T\mathbf{U}_{*j}^y\]。
值得注意的是，如果哈希码中一些不同的位（bit）有着很高的关联度，举例来说，\[\mathbf{U}_{i*}^x\] 和 \[\mathbf{U}_{j*}^x\] 在所有实例上同时变化，则这些位就有着重复的信息。为了让哈希码的每一位提供的信息最大，本文为每个模态的不同哈希位之间都加入了去关联约束：
\[ \begin{align} \mathcal{J}_4 &= \frac 12(\|\mathbf{C}^x\|_F^2 - \|diag(\mathbf{C}^x)\|_F^2) \\ &+ \frac 12 (\|\mathbf{C}^y\|_F^2-\|\mathbf{C}^y\|_F^2) \end{align} \]
其中
- \[\mathbf{C}^x = \frac 1T \sum_{n=1}^T(U_{in}^x - \mu_i)(U_{jn}^x - \mu_j)\] 是位 \[i\] 和 位 \[j\] 在图像数据的 batch 上的协方差矩阵，\[i,j\in\lbrace 1, 2,\cdots,c \rbrace\]
- \[\mu_i = \frac1T\sum_{n=1}^T U_{in}^x\] 是 batch 上实例的第 \[i\] 个特征（位）的均值
- \[T\] 是 batch size
- \[\mathbf{C}^y\] 的定义类似
为了能够在网络上进行梯度下降，将两个模态的 \[\mathbf{U}^x\] 和 \[\mathbf{U}^y\] 放松到实值。
为了更好地理解去关联约束，考虑图像模态下对一个样本 \[m\] 的一个特定的哈希位 \[a\] 的梯度：
\[ \begin{align} \frac{\partial \mathcal{J}_4}{\partial U_{am}^x} = &\frac 1T \sum_{j\neq a}[\frac1T\sum_{n=1}^T (U_{an}^x - \mu_a)(U_{jn}^x - \mu_j)] \\ & \cdot (U_{jm}^x - \mu_j) \end{align} \]
将上式右边的项记为 \[I^x(j,m) = (U_{jm}^x - \mu_j)\]，当第 \[j\] 位对样本 \[m\] 有着很高的判别性时，该项值（绝对值）就会较大，否则就会接近 \[\mu_j\]，所以 \[I\] 可以看做是“重要度”因子。左边的项就是哈希位 a 和哈希位 \[j\] 的协方差，上述梯度可以重写为：
\[ \frac{\partial \mathcal{J}_4}{\partial U_{am}^x} = \frac 1T \sum_{j\neq a}(C_{aj}^x\cdot I^x(j,m)) \]
当 \[j\] 对样本 \[m\] 很重要并且与 \[a\] 关联度高时，上述梯度的值就会变大，哈希位 \[a\] 的激活就会受到抑制。
文本还加入了正则项约束，能够减少量化损失，保持哈希码的平衡：
\[ \begin{align} R = &\|\mathbf{B} - \mathbf{U}^x\|_F^2 + \|\mathbf{B} - \mathbf{U}^y\|_F^2 \\ &+ \|\mathbf{U}^x\cdot \mathbf{1}\|_F^2 + \|\mathbf{U}^y\cdot \mathbf{1}\|_F^2 \end{align} \]
其中 \[\mathbf{B}\] 是两个模态的联合哈希码。
总的目标函数如下：
\[ \mathcal{J} = (\mathcal{J}_1 + \mathcal{J}_2 + \mathcal{J}_3) + \lambda \mathcal{J}_4 + \gamma R \\ s.t. \quad \mathbf{B} \in \{-1,+1\}^{c\times N} \]
优化算法
固定 \(\theta_x\) 和 \(\theta_y\) 优化 \(\mathbf{B}\)
当 \[\theta_x\] 和 \[\theta_y\] 固定时，目标函数可以写为：
\[ \max_\mathbf{B}{\rm tr}(\mathbf{B}^T(\gamma(\mathbf{U}^x+\mathbf{U}^y))) = {\rm tr}(\mathbf{B}^T\mathbf{V}) = \sum_{ij}B_{ij}V_{ij}\\ s.t. \quad \mathbf{B} \in \{-1, +1\}^{c\times N} \]
其中 \[\mathbf{V} = \gamma(\mathbf{U}^x + \mathbf{U}^y)\] ，可以得到上式的最优解为：
\[ \mathbf{B} = {\rm sign}(\mathbf{V}) = {\rm sign}(\gamma(\mathbf{U}^x + \mathbf{U}^y)) \]
优化 \(\theta_x\) 和 \(\theta_y\)
固定其他参数的情况下，分别使用SGD，通过BP算法优化。
在训练数据对的采样中，传统的方法是在一个 batch 中采样数据对，这样一个迭代得到的数据对最多有 \[\frac{T(T-1)}{2}\]，文本中训练集数据的选择保存在一个矩阵中，每次选择的数据是 batch 和整个数据集的结合，每个迭代可以得到 \[(TN - \frac{T(T+1)}{2})\] 个数据对。由于 \[N \gg T\]，相同的 batch size，更多的数据对被用来训练，所以可以更有效地进行优化，使得模型对噪声和离群点更加鲁棒。
最终的算法如下：
实验
详见论文。