菜菜的秘密花园Label Embedding Online Hashing for Cross-Modal Retrieval
本文为论文 Label Embedding Online Hashing for Cross-Modal 的阅读笔记。
论文下载：https://doi.org/10.1145/3394171.3413971
1 简介
学习散列，作为最著名的近似近邻搜索技术之一，近年来吸引了很多人的注意。它旨在将高维实值特征映射到紧凑的二进制编码，同时保留原始空间中的相似性。然后，可以用XOR操作在Hamming空间中进行搜索，效率高，存储成本低。
许多跨模态散列方法已经被提出并取得了很好的性能。但大多数现有的方法通过批处理学习二进制代码或哈希函数。即在学习过程前，所有的训练数据都可用。这将产生以下问题：
- 实际数据通常以流方式收集，有新数据到来时，批处理方法需要对所有数据重新训练 → 效率低
- 训练集随训练时间变大 → 计算成本高
为了解决这些问题，在线散列被提出，但仍存在问题：
- 大多数在线散列方法是为单模态检索设计的，很难直接扩展到跨模态检索。少数在线跨模态散列模型被提出，但性能较差，因为异质模态之间的关联性难以捕捉。
- 只根据新到达的数据更新散列函数，忽略了新旧数据间的相关性 → 丢失现有数据的信息 → 现有在线散列。
- 新数据到来时，哈希函数可以有效地重新训练，但哈希码必须对所有累积数据重构 → 更新方案低效。
- 离散优化大多采用松弛策略 → 量化误差大。
为了解决上述问题，这篇文章提出了一种新的监督下的跨模式检索的在线散列方法，即Label EMbedding ONline hashing，简称LEMON。本文的主要贡献总结如下：
- 提出了一种新的有监督的在线散列检索方法，即LEMON。
- 它通过一个标签嵌入框架来捕捉语义结构，其中包括标签相似性的保存和标签重构，从而得到更有辨识度的二进制码。
- 通过优化内积最小化问题将新旧数据的哈希码连接起来，解决了更新不平衡问题。
- 采用两步学习策略，有效地更新哈希函数和二进制码，同时保持旧数据库的哈希代码不可更改，使其计算复杂度仅与流数据的大小有关。
- 提出了一种迭代优化算法来离散地解决二进制优化问题，极大地减少 量化误差。
- 在三个基准数据集上的实验结果表明，LEMON在跨模式检索任务上优于一些先进的离线和在线散列方法，并且可以扩展到大规模数据集。
2 相关工作
现有工作存在的问题：
- 单模态：不能直接用于跨模态检索任务；必须在每一轮更新所有的二进制代码，效率非常低
- 多模态：不能跨模态检索
- 跨模态：不能充分利用原始特征、语义标签；不能很好地以流的方式来捕捉数据的相似性信息
单模态：查询和要检索的文档都只有一个模态（图像→图像）
多模态：查询和要检索的文档必须至少有一个模态相同（图像、文本→图像、文本）
跨模态：查询和要检索的文档模态不同（图像→文本）
3 方法
3.1 Notations
假设每个样本由 $l$ 个模态组成。在第 $t$ 轮，一个新的数据块 $\vec{X}^{(t)}$ 被添加到数据库中。常用变量的说明如下：
| 符号 | 意义 |
|---|---|
| $\vec{X}_m^{(t)}∈R^{d_m×n_t}$ | 表示新数据块的第 $m$ 个模态，其中 $n_t$ 是新数据块的大小， $d_m$ 是特征维度。$m∈{1，2，…，l}$ |
| $\vec{L}^{(t)}∈R^{c×n_t}$ | 新数据块的标签矩阵，其中 $c$ 是语义类别的数量 |
| $\tilde{X}^{(t)}$ | 现有数据 |
| $N_{t-1} = \sum_{k=1}^{t-1} n_k$ | 现有数据的大小，$N_t=N_{t-1} +n_t$ |
| $\tilde{L}^{(t)}∈R^{c×N_{t-1}}$ | 现有数据的相应标签矩阵 |
| $X^{(t)}_m=[\tilde{X}^{(t)}_m,\vec{X}_m^{(t)}]∈R^{d_m×N_t}$ | 代表当前整个数据库 |
| $L^{(t)}=[\tilde{L}^{(t)},\vec{L}^{(t)}]∈R^{c×N_t}$ | 代表整个标签矩阵 |
| $\tilde{B}^{(t)}$ | 现有数据的哈希码 |
| $\vec{B}^{(t)}$ | 新数据的哈希码 |
我们的目标是学习所有模态的 $r$ 位统一哈希码$B^{(t)}=[\tilde{B}^{(t)},\vec{B}^{(t)}]∈R^{r×N_t}$，和第$m$ 个模态的哈希函数 $H_m^{(t)}(·)$。
本文采用了一个两步学习方案：首先学习现有样本和新数据的哈希码，再基于学习到的哈希码，进一步学习哈希函数。
3.2 Hash Codes Learning
算法整体伪代码：
3.2.1 Label Embedding
根据检索任务的目标，二进制代码应该保留实例的语义相似性。为了实现这一点，任务可以定义为以下的内积最小化问题： $$ min_{B(t)} ∥B^{(t)⊤}B^{(t)} − rS^{(t)}∥^2, s.t. B^{(t)} ∈ {−1, 1}^{r×N_t}\tag{1} $$ $S_{(t)}$ 是语义相似度矩阵。如果第 $i$ 个实例和第 $j$ 个实例至少有一个共同的标签，则 $S^{(t)}_{ij} = 1$ ，否则 $S^{(t)}_{ij} = -1$ 。此方案存在的问题：
存储、计算成本大
不能表明细粒度的语义相似性，特别是对于多标签数据
为了解决上述问题，重新定义相似性矩阵，并通过二进制的哈希码保存。标签相似度矩阵如下： $$ S^{(t)} = 2U^{(t)⊤} U^{(t)} − 11^⊤\tag{2} $$ 其中 $U^{(t)⊤}$ 是2规范化的标签矩阵，定义为 $u^{(t)}_i =l^{(t)}_i/∥l^{(t)}_i ∥$ ，而 $l^{(t)}_i$ 是 $L^{(t)}$ 的第 $i$ 列。
为了使 $S^{(t)}$ 能够用于在线场景，进一步将其改写为一个块状矩阵。$S_{oo}^{(t)}$，$S_{oc}^{(t)}$，$S_{co}^{(t)}$，$S_{cc}^{(t)}$分别是旧数据的成对相似度矩阵、旧新数据的相似度矩阵、旧新数据的相似度矩阵、新数据的成对相似性矩阵。
我们试图将更多的标签信息嵌入待学习的二进制码中。假设所有样本标签都可以从学习到的二进制码中重构。可以进一步定义以下优化问题： $$ min_{{B,P}^{(t)}} ∥L^{(t)} −P^{(t)}B^{(t)}∥^2+γ ∥P^{(t)}∥^2, s.t. B^{(t)} ∈ {−1, 1}^{r×N_t} \tag{5} $$ 其中 $γ$ 是惩罚参数，$P^{(t)}∈R^{c×r}$ 是投影矩阵。合并(1)和(5)： $$ min_{{B,P}^{(t)}} α ∥B^{(t)⊤}B^{(t)} − rS^{(t)}∥^2+ β∥L^{(t)} −P^{(t)}B^{(t)}∥^2+βγ ∥P^{(t)}∥^2 \tag{6} $$
其中 $α$ 和 $β$ 是权衡参数。显然，上述方法通过保留标签的相似性、重建标签，可以将更多的语义信息嵌入二进制码中。此外，它通过最一致的语义标签来匹配异质性的模式，从而产生统一的二进制码，非常适用于在线学习。
3.2.2 Online Learning
理想情况下，我们希望保持 $\tilde{B}^{(t)}$ 不变，只更新 $\vec{B}^{(t)}$ 。将(3)代入(6)得： $$ min_{{B,P}^{(t)}} α ∥\vec{B}^{(t)⊤}\tilde{B}^{(t)} − rS_{co}^{(t)}∥^2+ α ∥\tilde{B}^{(t)⊤}\vec{B}^{(t)} − rS_{oc}^{(t)}∥^2 + α ∥\vec{B}^{(t)⊤}\vec{B}^{(t)} − rS_{cc}^{(t)}∥^2 + $$
$$ β∥\vec{L}^{(t)} −P^{(t)}\vec{B}^{(t)}∥^2+ β∥\tilde{L}^{(t)} −P^{(t)}\tilde{B}^{(t)}∥^2+βγ ∥P^{(t)}∥^2, \tag{7} $$
这个在线目标是由最初的批处理目标推导出来的，即公式(6)。包含 $S_{oo}^{(t)}$ 的项被切断，因为 $\tilde{B}^{(t)}$ 不变。因此，它对传入的数据不太敏感，能够产生更多的鉴别性哈希码。通过上述目标函数，新数据之间的成对相似性被保留。更重要的是，新旧数据之间的关联性也被 $S_{oc}^{(t)}$ 或 $S_{co}^{(t)}$ 捕获。因此，公式(7)能将更多的相似性信息嵌入到二进制码中。
然而随着时间的积累，旧数据库的样本数量比新数据块的大得多，导致相似性矩阵 $S_{co}^{(t)}$ 稀疏且不平衡，大多数元素是负的。使用直接的离散优化可能会带来巨大的信息损失，因为硬二进制矩阵分解可能会偏向于保持不相似的信息而丢失相似的信息。为了解决这个问题，我们用一个实值 $V^{(t)}$ 来代替一个 $B^{(t)}$。类似地，有 $V^{(t)}=[\tilde{V}^{(t)},\vec{V}^{(t)}]$ 。为了减少 $B^{(t)}$ 和 $V^{(t)}$ 间的信息损失，引入一个正交旋转矩阵的正则化项：$R^{(t)}∈R^{r×r}$ 。为了使 $V^{(t)}$ 无偏，引入正交和平衡约束。目标函数成为以下函数： $$ min_{{\vec{B},\vec{V},P,R}^{(t)}} ∥\vec{B}^{(t)}−R^{(t)}\vec{V}^{(t)}∥^2+∥\tilde{B}^{(t)}−R^{(t)}\tilde{V}^{(t)}∥^2 + α ∥\vec{V}^{(t)⊤}\tilde{B}^{(t)} − rS_{co}^{(t)}∥^2+ $$
$$ α ∥\tilde{V}^{(t)⊤}\vec{B}^{(t)} − rS_{oc}^{(t)}∥^2 + α ∥\vec{V}^{(t)⊤}\vec{B}^{(t)} − rS_{cc}^{(t)}∥^2 + β∥\vec{L}^{(t)} −P^{(t)}\vec{V}^{(t)}∥^2+ $$
$$ β∥\tilde{L}^{(t)} −P^{(t)}\tilde{V}^{(t)}∥^2+βγ ∥P^{(t)}∥^2, \tag{8} $$
这样一来，二元约束只强加在一个被分解的变量上，而且避免了二元矩阵分解。
此外，实值 $V^{(t)}$ 比 $B^{(t)}$ 能更准确地捕捉语义信息，确保在相似性保存过程中可接受的信息损失，从而解决更新不平衡问题。此外，它仍然保留了离散的约束条件，并通过sign(·)操作有效地生成二进制哈希码。$V^{(t)}$ 在相似性空间和标签空间之间架起了桥梁。
3.2.3 Efficient Discrete Optimization
为了解决公式 (8) 的问题，我们提出了四步迭代优化算法，该算法有效地、不连续地生成哈希码。在每个步骤中，一个变量被更新，而其他变量被固定。
更新 $P^{(t)}$ 。令公式 (8) 关于 $P^{(t)}$ 的导数为零，得出 $P^{(t)}$ ： $$ P^{(t)} = C^{(t)}_1 (C^{(t)}_2 + γ I)^{−1} \tag{9} $$
更新 $\vec{V}^{(t)}$ 。当Bfi(t)、P(t)、R(t)固定时，公式(8)可以被简化为： $$ max_{\vec{V}^{(t)}} tr(Z\vec{V}^{(t)}), s.t. \vec{V}^{(t)}\vec{V}^{(t)T} = n_tI, \vec{V}^{(t)}1 = 0. \tag{13} $$ 我们可以发现，方程(13)有一个封闭形式的最优解。记为 $J = I - \frac{1}{nt} 11^⊤$。注意 $J$ 是实时计算的。然后，该问题可以通过对 ${ZJZ}^⊤$ 进行奇异值分解来解决： $$ {ZJZ}^⊤=\left[\begin{matrix}G & \hat{G}\end{matrix}\right] \left[\begin{matrix}Ω & 0 \ 0 & 0\end{matrix}\right] \left[\begin{matrix}G & \hat{G}\end{matrix}\right]\tag{16} $$ 这里，$Ω∈R^{r^′×r^′}$ 是正特征值的对角矩阵，$G∈R^{r×r^′}$ 是相应的特征向量。$\hat{G}$ 是剩余的 $r - r^′$ 零特征值的特征向量。$r'$ 是 $ZJZ^⊤$ 的等级。通过对 $\hat{G}$ 进行Gram-Schmidt处理，可以得到一个正交矩阵 $\bar{G}∈R^{r×(r-r^′)}$。我们进一步表示 $Q = JZ^⊤GΩ^{-1/2}$，并生成一个随机的正交矩阵 $\bar{Q}∈R^{n_t×(r-r^′)}$ 。如果 r′=r，$\bar{G}$ 和 $\bar{Q}$ 为空。则公式(13)的最优解是： $$ \vec{V}^{(t)} = \sqrt{n_t} \left[\begin{matrix}G & \bar{G}\end{matrix}\right] \left[\begin{matrix}Q & \bar{Q}\end{matrix}\right]^T.\tag{17} $$
更新 $\vec{R}^{(t)}$ 。在除 $\vec{R}^{(t)}$ 之外的所有变量固定的情况下，公式(8)变成经典的正交普鲁斯特问题，可以通过重度分解来解决： $$ C^{(t)}_5 = AΣ\hat{A}^⊤,\tag{18} $$
$$ C^{(t)}_5 = C^{(t-1)}_5+\vec{B}^{(t)}\vec{V}^{(t)T}, C^{(t-1)}_5=\tilde{B}^{(t)}\tilde{V}^{(t)T} .\tag{19} $$
得到 $R^{(t)}$ 的最佳解为： $$ R^{(t)} = A\hat{A}^⊤.\tag{20} $$
更新 $\vec{B}^{(t)}$。当除 $\vec{B}^{(t)}$ 以外的所有变量都被固定时，公式(8)被推导为以下子问题： $$ max_{\vec{B}^{(t)}} tr(R^{(t)T}\vec{V}^{(t)} + αr\tilde{V}^{(t)}S^{(t)}_{oc} + αr\vec{V}^{(t)}S^{(t)}_{cc}\vec{B}^{(t)T}), \tag{21} $$ 根据 $S_{oc}^{(t)},S_{cc}^{(t)}$ 的定义，经过几次代数变换，公式 (21) 的最优解为： $$ \vec{B}^{(t)}=sign(R^{(t)T}\vec{V}^{(t)}+2αrC_6^{(t)}\vec{U}^{(t)}-αrC_7^{(t)}1^T),\tag{22} $$
重复上述四个步骤直到收敛，可以得到最终的二进制代码。
3.3 Hash Functions Learning
获得统一的二进制码后，需要学习哈希函数来适应多种模式。为了达到这个目的，可以采用不同的模型，如线性回归、支持向量机、深度神经网络。我们在学到的二进制码的监督下，为每种模式训练一个线性回归模型。具体来说，给定学习的二进制码 $B^{(t)}$ 和第 $m$ 个模态的特征矩阵 $X^{(t)}_m$，线性映射模型可以通过解决以下问题被学习：
$$ min_{W^{(t)}_m} ∥B^{(t)} − W^{(t)}_m X^{(t)}_m∥^2 + ξ ∥W^{(t)}_m∥^2,\tag{24} $$ 其中 $ξ$ 是一个惩罚参数，$W^{(t)}_m$ 是映射矩阵。通过将公式 (25) 关于 $W^{(t)}_m$ 的导数设为零,得到最佳解： $$ W^{(t)}_m = H^{(t)}_m(F^{(t)}_m + ξ I)^{−1},\tag{26} $$
$$ H^{(t)}_m = H^{(t-1)}_m+\vec{B}^{(t)}\vec{X}^{(t)T}_m, H^{(t-1)}_m=\tilde{B}^{(t)}\tilde{X}^{(t)T}_m, $$
$$ F^{(t)}_m = F^{(t-1)}_m+\vec{X}^{(t)}\vec{X}^{(t)T}_m, F^{(t-1)}_m=\tilde{X}^{(t)}\tilde{X}^{(t)T}_m .\tag{27} $$
此后，给定一个新的查询，我们可以取第 $m$ 个模态 $x_m∈R^{d_m}$，并通过以下哈希函数生成其哈希码： $$ H^{(t)}_m (x_m) = sign(W^{(t)}_mx_m).\tag{28} $$ 训练过程的整体计算复杂度与新数据的大小 $n_t$ 呈线性关系，而与旧数据库的大小无关。因此，LEMON可以扩展到大规模的在线检索任务。
4 实验
为了评估LEMON的性能，我们在三个基准数据集上进行了广泛实验。
4.1 实施细节
在实现LEMON的过程中，我们首先对MIRFlickr-25K数据集进行了参数敏感性分析，当α和β为 1e4 时，LEMON取得最佳效果。此外我们观察到，参数对性能的影响并不显著。因此，为了简单起见，所有的数据集上都设置了相同的参数，即α=β=1e4。根据经验，$γ$ 和 $ξ$ 分别被设定为0.1和1。每一轮的迭代次数为5。
在实验中，我们进行了两种类型的跨模式检索任务。图像→文本和文本→图像。利用平均精度（MAP）和训练时间，来评估所有方法的性能。
4.2 结果分析
4.2.1 平均精度分析
MIRFlickr-25K数据集的结果如表1所示，展示了不同长度样例的MAP值。
不同方法的性能如下图所示：
可以得出：
- LEMON在所有情况下都持续优于其他方法，表明其在处理跨模式检索任务方面的有效性。
- 一般来说，离线基线（如DLFH和SCRATCH），比在线基线（如OCMH和OLSH）表现更好。
- 从图1中可以看到，LEMON实现了持续的性能提高，证明了LEMON可以通过新旧数据库之间的相关性，将更多的语义信息嵌入二进制码。
- 随着轮次的增加，大多数离线方法的性能都在下降。最有可能的原因是它们在每轮中用所有累积的样本重新训练哈希函数和哈希代码。
- 大多数方法随着哈希码长度的增加而表现得更好，表明更长的比特可以携带更多的鉴别信息。
- 大多数方法在文本→图像的任务中比图像→文本的任务中表现得更好，可能的原因是，文本特征可以更好地描述。
其他两个数据集的结果与其类似。
4.2.2 时间成本分析
根据之前的分析知，LEMON的复杂性与新数据的大小呈线性关系。由图四可知，LEMON在所有情况下都是最快的。离线方法需要更长的训练时间，并且时间成本随着回合数的增加而显著增加，因为它们必须对所有累积的数据重新训练哈希函数，这使得它们在在线情况下效率很低；而在线方法的训练时间不会。因此LEMON的训练非常有效，并且可以扩展到大规模在线检索。
4.2.3 参数敏感度分析
我们进行了实验来分析包括α和β在内的参数的敏感性。由图5可以看到，这些参数确实对LEMON的性能有一些影响，但并不明显。