翻译自 Learning to Hash for Big Data: A Tutorial。

引子

大数据中的最近邻搜索

最近邻搜索（Nearest Neighbor Search）：给定查询点 q，返回数据库中距离 q 最近（最相似）的点集。

  • Facebook：7.5 亿用户
  • Flickr：6 千万照片
  • Wal-Mart: 每天 2.67 亿商品；4PB 数据仓库
  • Sloan Digital Sky Survery：新墨西哥州望远镜每天获取 200GB 图像数据

大数据中的最近邻搜索挑战：

  • 维数灾难
  • 存储
  • 查询速度

Similarity Preserving Hashing（相似保留哈希）

让无关图像对应的哈希编码尽可能不同，让相似图像的哈希编码尽可能相同。

存储空间需求减少。

使用哈希编码来建立索引，可以达到常数或次线性查询时间复杂度。

某些情况下线性时间的全搜索也可以接受，因为二进制表示下的距离计算消耗很低。

哈希函数学习的两个阶段

  • 第一类
    • 投影阶段（Projection Stage）（降维）
      • 用实值投影函数投影
      • 给定点 x，每个投影维度 i 都和一个实值投影函数相关联 fi(x)（比如 fi(x)=Wi^T*x
    • 量化阶段（Quantization Stage）
      • 将实数转化为二进制（Turn real into binary）
      • 度量学习（metric learning）和哈希学习（learning to hash）的本质区别
  • 第二类
    • 二进制编码学习阶段
    • 哈希函数学习阶段

数据无关方法

哈希函数的定义和训练数据集无关。

  • Locality-sensitive hashing (LSH) 位置敏感哈希 (Gionis et al., 1999; Andoni and Indyk, 2008)
    • 和它的扩展 (Datar et al., 2004; Kulis and Grauman, 2009; Kulis et al., 2009)
  • SIKH: 偏移不变核函数哈希（Shift invariant kernel hashing）(SIKH) (Raginsky and Lazebnik, 2009)
  • MinHash (Broder et al., 1998)
    • 和它的扩展 (Li and K ̈onig, 2011)

这些方法的哈希函数使用了随机投影或者是人工构造的，所以不属于哈希学习。

数据相关方法

哈希函数是从给定的训练数据集中学习得到。

和数据无关方法相比，数据相关方法（即哈希学习）可以在更短的二进制编码上获得相近甚至更好的精确度。

开创性论文：(Salakhutdinov and Hinton, 2007, 2009; Torralba et al., 2008; Weiss et al., 2008)

两个种类：

  • 单模态
    • 监督式方法：给定一些监督的（语义）信息，例如 pairwise 标签 s_ij, pointwise 标签 yi 或者 triplet 标签 (xi, xj, xk)
    • 非监督式方法
  • 多模态
    • 监督式方法
    • 非监督式方法

单模态非监督方法

没有指示训练点类别的标签。

单模态监督（半监督）方法

具有类标签或者配对（pairwise）约束。

  • SSH (SPLH)：半监督哈希，同时利用有标签和无标签数据 (Wang et al., 2010a,b)
  • MLH：基于隐式结构（latent structural）SVM 框架的最小化损失哈希 (Norouzi and Fleet, 2011)
  • LDAHash：基于线性区分分析（Linear discriminant analysis）的哈希 (Strecha et al., 2012)
  • KSH：基于核函数（Kernel）的监督式哈希 (Liu et al., 2012)
  • LFH：隐含因子模型的监督式哈希 (Zhang et al., 2014)
  • FastH：使用图割和决策树的监督式哈希 (Lin et al., 2014)
  • SDH：使用逐点（pointwise）标签的监督式离散哈希 (Shen et al., 2015)
  • COSDISH：使用 pairwise 监督的可扩展的离散哈希

基于排序的方法

监督信息是排序标签，例如三元组 (xi, xj, xk)。

  • HDML：汉明距离度量学习（metric learning）(Norouzi et al., 2012)
  • OPH：顺序保留哈希，近似最近邻搜索 (Wang et al., 2013b)
  • RSH：用 listwise 监督式学习哈希编码 (Wang et al., 2013a)
  • RPH：排序保留哈希，快速相似度搜索 (Wang et al., 2015)

多媒体方法

  • 多来源哈希（Multi-Source）
  • 跨媒体哈希（Cross-Modal Hashing）
多来源方法
  • 目标是利用辅助视图（auxiliary views）来学习比单模态哈希更好的编码
  • 假设查询提供了所有视图
  • MFH：多特征哈希 (Song et al., 2011)
  • CH：复合哈希 (Zhang et al., 2011)
跨媒体方法

给定包含图片或文字的查询，返回相关的图片或文字。

  • CVH：跨视图哈希 (Kumar and Udupa, 2011)
  • MLBE：多模态隐含二进制嵌入 (Zhen and Yeung, 2012a)
  • CRH：同时正则化（Co-regularized）哈希 (Zhen and Yeung, 2012b)
  • IMH：媒体间哈希（Inter-media hashing）(Song et al., 2013)
  • RaHH：关系感知异构（Relation-aware heterogeneous）哈希 (Ou et al., 2013)
  • SCM：语义相关最大化（Semantic correlation maximization）(Zhang and Li, 2014)
  • CMFH：集体矩阵分解（Collective matrix factorization）哈希 (Ding et al., 2014)
  • QCH：量化相关哈希（Quantized correlation hashing）(Wu et al., 2015)
  • SePH：语义保留哈希 (Lin et al., 2015b)

深度哈希

使用深度学习的哈希。

  • CNNH：通过图片表达学习的监督式哈希 (Xia et al., 2014)
  • NINH：用深度神经网络同时特征学习和哈希编码 (Lai et al., 2015)
  • DSRH：基于深度语义排序的哈希 (Zhao et al., 2015)
  • DRSCH：位可扩展（Bit-scalable）深度哈希 (Zhang et al., 2015)
  • DH：深度哈希，压缩二进制编码学习 (Liong et al., 2015)
  • 二进制编码学习深度哈希 (Lin et al., 2015a)
  • DPSH：基于特征学习的使用 pairwise 标签的深度监督哈希 (Li et al., 2015)

量化

量化阶段和投影阶段一样重要。

  • DBQ：双位（Double-bit）量化 (Kong and Li, 2012a)
  • MQ：曼哈顿（Manhattan）量化 (Kong et al., 2012)
  • VBQ：可变位（Variable bit quantization）量化 (Moran et al., 2013)