Fast Supervised Discrete Hashing

2017 TPAMI

• 要点：
  FSDH使用非常简单但有效的回归训练示例的类标签到相应的哈希码，以加速算法；
  FSDH有一个封闭的解，只需要一个单一的而不是迭代的哈希码求解步骤，这是非常高效的。此外，FSDH求解最小二乘回归投影矩阵的速度通常比SDH快，这使得FSDH通常比SDH快。

• 传统算法回顾：

  • 数据无关的哈希
    不依赖于训练数据，而是在二值化之前使用随机投影将样本映射到特征空间
    LSH

  • 数据相关的哈希

    • 无监督哈希
      哈希学习时不需要训练样本标签
      SH ITQ AGH IMH t-SNE
    • 半监督哈希
      利用成对的标签数据进行哈希学习
      SSH BRE
    • 监督哈希
      利用样本标签进行哈希学习
      KSH dualview hashing FashHash LDAHash

• 问题的提出:
  为了充分利用标签信息，SDH被表述为一个最小二乘分类，将每个哈希码回归到其相应的标签。然而，普通的最小二乘回归可能不是分类的最佳方法。

• 本文的解决：
  FSDH有一个封闭的哈希学习解决方案，只需要一个单一的步骤，而不是迭代来解决哈希代码。在求解最小二乘回归(另一个子问题)的投影矩阵时，FSDH通常比SDH快。最后，在求解将非线性嵌入投影到低维空间的投影矩阵时，SDH和FSDH具有相似的时间复杂度。所以总体上FSDH比SDH快，性能也更优了。

目标函数：

SDH是将B回归到Y，而为了加速FSDH将Y回归到B。
目标函数中只有第一项使得每个类的二进制码相同，但是由于第三项的存在，使得每个类中的二进制码不同。

• 算法正确性证明：
  证明了为什么Y-BW可以被替换为B-YW
  证明了FSDH在求解B时比SDH更稳定

测评：

• 数据集：
  CIFAR 10个类别，每个类别6000个图像，共60000张图像。每张图像用512维的GIST特征向量表示
  MNIST 70000张784维的手写数字
  FRGC 面部数据集

• 特征：

• 测评指标：
  汉明排序（MAP）
  哈希查找（precision recall F-measure）
  Accuracy
  Training time
  Test time

• 实验内容：
  在CIFAR数据集上，FSDH在precision recall F-measure上取得最优，FastHash在MAP accuracy上取得最优
  在MNIST数据集上，FSDH在recall、F-measure上取得最优，SDH在precision上取得最后，FastHash在MAP和accuracy上取得最优
  在FRGC数据集上，哈希吗32位时，FSDH在precision recall F-measure取得最优；64位时FSDH最优，超过128位时KSH最优。FSDH提供了更好的搜索结果。