[数据结构与算法]论文研读（二）

Label Embedding Online Hashing for Cross-Modal Retrieval

2020 MM

YongXin Wang ShanDong University

online hashing的研究问题：

• 如何有效地利用语义信息
• 如何离散地解决二进制优化问题
• 如何高效地更新哈希码和哈希函数

概要

• 建立了一个包含标签相似性保持和标签重构的标签嵌入框架，可生成有区别的二进制码，降低了计算复杂度
• 该算法不仅保留了输入数据的两两相似度，而且通过块相似矩阵上的内积极小化建立了新输入数据与已有数据之间的联系。基于此，它可以利用更多的相似信息，使优化对传入数据不那么敏感，从而产生有效的二进制代码。
• 设计了一种离散优化算法来解决无松弛的二元优化问题。因此，量化误差可以减小。
• 它的计算复杂度只与传入数据的大小有关，这使得它非常高效。
• 保持现有数据的哈希码不变，有效地更新哈希函数，利于扩展到大规模数据集。

提出的问题

• 大多数在线哈希方法都是为单模态检索而设计的，很难直接扩展到跨模态检索。虽然已经提出了一些在线跨模态哈希模型，但它们的性能并不令人满意，因为异构模态之间的相关性很难捕捉。
• 它们只根据新到达的数据更新哈希函数，忽略了新到达数据与现有数据之间的关联，可能会丢失现有数据的信息，导致结果不稳定。
• 现有的在线哈希方法的更新方案效率低下。在这些方法中，哈希函数可以通过新到来的数据进行有效的再训练;然而，必须对所有累积的数据重新构建哈希码。因此，计算复杂度依赖于整个累积数据库的大小，使得在大规模数据集上的学习非常低效。
• 离散优化仍然是在线哈希的一个开放问题。大多数方法采用松弛策略，量化误差较大。而且在在线场景中，新数据和现有数据之间的相似性是不平衡的，即大多数对是不相似的，只有少数对是相似的。脱机哈希中的几种直接离散优化，即离散循环坐标下降(DCC)因为优化严重依赖于不同的对而不再适用。

具体原理

哈希码学习

定义：

将S(t)分块，有

即

基于批量的哈希目标：

变为在线哈希的目标 (B(old)不变）：

由于积累的数据逐渐增多，导致S(oc)和S(co) 稀疏和不平衡，即大多数元素都是-1。因为硬二叉矩阵分解可能会产生保留不同信息而丢失相似信息的偏差，采用直接离散优化方法可能会造成较大的信息损失，因此使用V(t)替换一个B(t)，和B(t)相似，V(t)保持V(old)不变，更新V(coming)。同时为了使V(t)无偏，进一步引入了正交约束和均衡约束。

优化过程

• 优化P
• 优化$V$
  原目标函数关于$V$的简化形式为
  
  
  令
  
  
  
  最终得到：
  
• 优化R
  经典正交procrustes问题，通过特征分解求解：
  
  *优化$B$
  
  

哈希函数的学习

• 目标函数
  

• 优化W(m)
  

• 生成哈希码：
  

实验

数据集描述：

• MIRFlicker
  包括25,000个实例，它们被24个类别中的至少一个加以注释。每个文本用一个1386维的词袋向量表示，每个图像用512维的GIST特征向量表示。删除了文本标记出现次数少于20次的实例后，使用了20015个实例。随机选择2,000个实例作为查询集。为了支持在线场景，其余的数据被划分为9个数据块，前8个数据块每个包含2,000个实例，最后一个数据块包含2,015个对。在每一轮，一个新的数据块被添加到数据库中。
• IAPR TC-12
  包含了来自世界各地255个类别的20000对图文组合。每个图像用512维GIST特征向量表示，每个文本用2912维bag-of-words向量表示。随机选择了2000个图像-文本对作为查询集。其余的被平均分成9个块，每个块包含2000对。
• NUS-WIDE
  包含81个类别的269648对图像-文本对，图像和文本分别用500维SIFT特征向量和1000维二进制标记向量表示。从原始数据集中选取了10个最常用的标签和对应的186,577个点。随机选择2000张图片及其相关文本作为查询。其余的被分成18块。其中，前17个块每个块包含10000点，最后一个块包含14577点。