大数据近似最近邻搜索哈希方法综述

简介

朋友介绍的一篇哈希检索的综述，作下转载：

• Yuan Cao, Heng Qi, Wenrui Zhou, Kato Jien, Keqiu Li, Xiulong Liu, and Jie Gui. “Binary hashing for
  approximate nearest neighbor search on big data: A survey.” IEEE Access 6 (2018): 2039-2054.

背景

最近邻搜索(Nearest Neighbor Search)也称作最近点搜索， 是指在一个尺度空间中搜索与查询点最近点的优化问题。 具体定义如下： 在尺度空间 $M$ 中给定一个数据库点集 $S$ 和一个查询点 $q∈M$， 在 $S$ 中找到距离 $q$ 最近的点。 其中 $M$ 为多维的欧几里得空间，距离由欧几里得距离决定。 最近邻搜索在很多领域中都有广泛应用， 如： 计算机视觉、信息检索、 数据挖掘、 机器学习， 大规模学习等。 其中在计算机视觉领域中应用最广，如： 计算机图形学、 图像检索、 复本检索、 物体识别、 场景识别、 场景分类、 姿势评估，特征匹配等。

随着互联网和电子技术的高速发展， 网络上信息量的增长异常迅速， 每秒钟都会上传大量的文本， 图像等信息。 这给很多需要进行高效最近邻搜索的领域带来了极大的挑战。 当数据库中的信息量较少的时候， 我们可以使用最简单有效的穷尽搜索方式， 即：将数据库中的点与查询点一一比较欧式距离， 最终根据距离的大小排序。 时间复杂度为线性复杂度 $O(dn)$， $d$ 和 $n$ 分别是数据的维度和样本数。 但当数据库的规模庞大， 如有上百万到上亿个点时， 线性搜索的方式已不适用。 另外， 如在计算机视觉领域， 已越来越倾向使用高维度数据或结构化数据来更加精确地表达图像信息， 并使用复杂的相似度公式计算图像间距离， 在这些情况下， 穷尽搜索的方式无法高效完成最近邻搜索。

因此， 人们开始使用近似最近邻搜索(Approximate Nearest Neighbor Search)方法快速搜索有效解， 其定义为： $d(r,q)\le (1+\varepsilon)·d(r^\ast,q),\varepsilon \ge 0$。 其中， $q$ 为查询点，$r^\ast$ 为精确解，$\varepsilon$ 为近似误差， $d$ 为某种距离函数。 早期被大量使用的是通过各种树形结构对特征空间分割的方式， 最经典的以 K-D 树为代表。 不过， 虽然这些利用树形结构做近似最近邻搜索的方法在处理低维数据的时候有较好的性能， 但随着数据维度的增长， 该类方法的时间性能显著降低， 有时甚至比线性搜索还差。

后来就不断有人提出各种基于哈希编码的近似最近邻搜索方法。 哈希编码即将数据库中的点（高维向量） 通过编码的方式转化为二进制向量， 同时尽可能保持原始空间中点之间的距离关系。 查询过程一般分为三步：

1. 计算查询点的二进制编码；
2. 找到与查询点具有相同二进制码的哈希篮子；
3. 将该哈希篮子中的所有点导入内存并根据要求对它们重新排序。

哈希编码主要有两大优点：

1. 空间复杂度低。 原始空间中的点一般为几百到几千维， 每一维都是实数值（占多位二进制） ， 而哈希码为二进制向量， 维度大概只有几十到几百维；
2. 时间复杂度低。 哈希码之间的距离用汉明距离计算， 在计算机中仅仅为一个异或操作的时间复杂度。 同时， 由于哈希码占有较少的空间， 可以更多地存入内存， 因而在计算时减少 CPU 访问外存的次数， 从而减少时间复杂度。

当然， 哈希编码的最大缺点就是损失了大量原始信息从而降低检索精度。 因此， 自哈希编码提出以来， 人们不断探寻可以提高哈希编码精度的方法。 但 Antonio Torralba 等人早在 2008 年就提出： 以图像压缩为例， 我们可以使用少量位数表示图像信息而不影响图像识别的准确率（如图 1.1） 。 因此， 哈希方法是可以在保证正确率的前提下减少检索时间的， 如今哈希编码被广泛应用在各个领域。

基于哈希的近似最近邻搜索框架

图 1.2 描述了一种典型的基于阈值哈希的近似最近邻搜索框架。 如图所示， 原始空间 $D$ 中有 $n$ 个 $m$ 维的向量， 这些向量可来自于各种应用领域， 如图像、 文本、 生物医学等。 当 $n$ 与 $m$ 的数值较大时（ $n$ 达到百万至亿数量级， $m$ 达到几千维以上） ， 我们使用哈希方法可以有效解决大规模近似最近邻搜索问题。 由于基于阈值的哈希方法是最常用的哈希编码方法， 因此我们以其为例阐述近似最近邻搜索的完整过程。

基于哈希的近似最近邻搜索过程主要分为两阶段： Offline 和 Online。 图中虚线上面为 Offline 阶段， 即对数据库中点进行与查询点无关的哈希编码。 该过程可分为两步：首先使用 $k$ 个哈希函数将原始空间 $D$ 中 $n$ 个 $m$ 维的点映射到 $k$ 维的投影空间 P中， 该映射要尽可能保持原始空间中点间的相似度关系。 然后再使用 $k$ 个阈值将投影空间中的点映射到二进制空间 $B$ 中， 即将其每一维度映射为“0” 或“1” ， 阈值的选择要满足哈希特性（如平衡性） ； 图中虚线下面为 Online 阶段， 即对查询点哈希编码。 对于查询点，我们使用与 Offline 阶段中同样的哈希函数与阈值， 将 $m$ 维查询点编码为 $k$ 维二进制。最后， 通过比较查询点二进制码和数据库中点二进制码之间的汉明距离即可将数据库中的点按照汉明距离由小到大排序。

下面我们从不同的角度将哈希方法分类。 首先哈希方法可以分为两大类： 哈希编码和哈希排序。 哈希编码又可以从三个角度分类： 哈希机理特性， 数据自身特性，哈希平台。 哈希排序可以分为两类： 加权汉明距离和非对称距离。 具体分类细节如图 1.3 所示。

哈希编码方法简介

哈希编码即将数据库中的点（高维向量） 通过编码的方式转化为二进制向量， 同时尽可能保持原始空间中点之间的距离关系。 将其符号化为： 数据库矩阵 $D=R^{n\ast m}$ ， 其中每个行向量代表一个 $m$ 维的点， 共 $n$ 个点。 哈希编码就是采用某种映射的方式将矩阵 $D$ 映射为二进制矩阵 $H=B^{n\ast k}$ ， 矩阵中每个值为二进制 $0$ 或 $1$， $k$ 为二进制的码长。 对于查询点 $q \in R^m$， 采用同样的哈希编码方法将其映射为 $H_q \in B^k$ 。 $H_q$ 与 $H_i(i\in 1,…,n)$ 之间的汉明距离为： $\text{Hamm}(H_q,H_i) = H_q \oplus H_i,i\in 1,…,n$。在查询时， 对数据库 $D$ 中的 $n$ 个点按 $\text{Hamm}(H_q,H_i)$ 由小到大排序。

哈希编码必须满足的要求主要有以下三个：

1. 码长短。 因为我们要将大量的信息存入到内存中， 如： 普通的工作站有 16GB 的内存， 若存储 250 百万幅图像， 每幅图像最多可以用 64 位二进制表示；
2. 保距。 即原始空间中相似（任意相似度： 欧氏距离、 核距离、 语义相似度等）的点编码后二进制编码间的汉明距离要短；
3. 效率高。 即无论是在训练时学习哈希编码的参数， 还是对新的输入点编码， 速度都要快。

为了得到更加高效的哈希码， 哈希编码一般还需要满足以下两个特性： 平衡性和独立性。

1. 平衡性： 即编码后的所有点的每一维度都有一半编码为 0， 一半编码为 1。 当编码达到平衡时， 熵达到最大， 信息量最大， 哈希编码最好。 如图 1.4 所示， 左右两幅图的哈希方法都可以使带有标签的点对正确编码， 但很明显右侧图哈希的空间分割有较大的熵， 包含更大的信息量， 因此比左侧图哈希好。

1. 独立性： 即不同哈希函数之间相互独立。 各个哈希函数若不相互独立则会产生类似的哈希结果， 造成信息冗余， 因此相互独立的哈希函数才可以对数据空间进行最有效的分割。

常见哈希编码方法的分类如表 2.1 所示， 其中标号为[1]中参考文献。

哈希机理特性

数据依赖性

如图 1.2 所示， 哈希编码的第一步是学习 $k$ 个哈希函数将原始空间 $D$ 中 $n$ 个 $m$ 维的点映射到 $k$ 维的投影空间 $P$ 中。 早期哈希函数的学习是不依赖于数据分布的， 如Locality-Sensitive Hashing (LSH) ， 哈希函数是从符合高斯分布的数据中随机选取的若干个投影分布。 尽管随着投影分布数量的增加， LSH 搜索结果渐近逼近理论值， 但是为了获得满意的精度往往需要较长的码长和较多的哈希表。 由于时间空间的限制很难扩展到上百万的数据集上。 因此， 依赖于数据分布的哈希方法被不断提出。 早期经典的依赖于数据分布学习哈希函数的哈希方法以 Spectral Hashing (SH) 为代表， SH 在数据库数据集上构造了一个目标函数保持原始空间和汉明空间之间的相似度表示， 即原始空间中相似的数据点要投影到汉明空间中相似的二进制码上。 再加上上面提到的独立性和平衡性限制， 最小化 SH 目标函数得到的数据库二进制码的解即为： 其拉普拉斯矩阵的前 $k$ 个最小特征值（除了 0）所对应的 $k$ 个特征向量。

尽管 SH 与 LSH 相比由于利用到了数据分布信息往往可以表示出较高的精度， 但 SH 有以下三个缺点：

1. SH 由于没有学习明确的哈希函数使得无法将其直接应用到新输入的数据点上；
2. SH 没有明确的理论依据， 即随着码长的增加， 哈希码之间的汉明距离是否会收敛于原始空间的相似度表示是不明确的；
3. 在实际应用中， 投影后的数据点的信息往往只分布在前几个维度上， 导致 SH 只在较短码长的二进制码上性能较好。

在下一节的哈希过程中， 我们会详细描述 SH 的哈希函数和哈希码学习过程。

哈希过程

传统哈希方法

在 2014 年以前， 大多数哈希方法都依赖于传统的两步走哈希框架： 投影和量化。在投影阶段， 使用 $k$ 个哈希函数将原始空间 $D$ 中 $n$ 个 $m$ 维的点映射到 $k$ 维的投影空间 $P$ 中， 该映射要尽可能保持原始空间中点间的相似度关系。 在量化阶段， 使用 $k$ 个阈值将投影空间中的点映射到二进制空间 $B$ 中， 即将其每一维度映射为“0” 或“1” 。

下面我们用矩阵运算的形式表示投影量化两阶段过程。 假设原始空间中的数据点表示为 $\{x_1,x_2,…,x_n\},\forall x_i \in R^d$，组成的数据库矩阵为 $X\in R^{n\ast d}$ 。 哈希方法的目标即找到一个投影矩阵 $W\in R^{d\ast k}$ ，其中 $c$ 表示二进制码长度。对于 $j =1,…,k$ ，哈希函数定义为：

$$y_{ij}=x_iw_j\\ B_{ij}=Q(y_{ij})$$

其中 $w_j \in R^d$ 是矩阵 $P$ 的一列，$B \in R^{d\ast k}$ 是数据库点对应的二进制码矩阵， 同时

$$Q(y_{ij})=\left\{ \begin{aligned} 1, && y_{ij}\ge t_j \\ 0, && \text{otherwise} \end{aligned} \right.$$

其中，$t_j$ 是由哈希方法确定的第 $j$ 位阈值。 由此， 哈希编码的整个过程可以表示为：$B = Q(XW)$。从式中， 我们可以看出一个哈希函数可以将数据点投影为一位， 如果想要获得 $k$ 位哈希码， 我们需要 $k$ 个哈希函数。 各个传统哈希方法之间的区别主要在于投影矩阵 $W$ 的计算上。 下面我们举例分析哈希方法是如何学习投影矩阵以及如何量化投影空间中的数据点的。

1. 投影
   我们将投影过程定义为 $P = XW$ 。 目前大多数传统哈希方法通过构造目标函数学习哈希函数， 最大化或最小化目标函数可以保持原始空间和汉明空间中点之间的相似度表示。 同时为了进一步提高哈希函数的性能， 还需要满足一些限制， 如： 平衡性和独立性。

   下面我们以 SH 为例分析哈希方法的投影过程， 以下是 SH 的目标函数和限制条件：

   $$\text{minimize}: \sum_{lij}S_{i,j}(y(i,l)-y(j,l))^2\\ \text{subject to}: Y(i,j)\in \{-1,1\},\\ Y^T1=0,\\ Y^TY=I$$

   其中， $y(i,l)$ 和 $y(j,l)$ 分别表示点 $i$ 和点 $j$ 在投影空间中的第 $l$ 位。 $S_{ij}\in [0,1]$ 表示点 $i$ 和点 $j$ 在原始空间中的相似度。 观察发现， 在原始空间中如果两个点很相似， 则 $S_{ij}$ 值较大，那么 $(y(i,l) - y(j,l))^2$ 应当较小。 因此， SH 通过最小化目标函数同时满足平衡和独立两限制条件学习哈希函数。

2. 量化

   在量化阶段， 投影空间中的点通过阈值量化为二进制码 。 目前大多数哈希方法将每个投影维度用一个阈值量化， 被称作单位量化。 阈值通常由平衡性限制 $(Y^T1 = 0)​$求得。然而单位量化一个比较严重的缺点是其阈值往往分布在数据密度最高的区域， 这将导致很多邻近的数据点被量化为完全不同的二进制码。 因此， 双位量化被提出。 双位量化即对每个投影维度动态学习两个阈值并将其编码为两位二进制码(01,00,10)。 阈值的学习使其避免设置在数据点密集的区域。 除此之外， 由于一些哈希函数可能比另一些携带更多的信息， 变位量化被提出为每个哈希超平面分配变化位数的哈希码。 变位量化首先构造一个目标函数使得为那些更好保持数据在原始空间中相似度关系的维度分配更多的哈希位。 与单位量化和双位量化相比， 变位量化可以获得更高的精度。

基于深度学习的哈希方法

对于图像检索应用中的哈希方法， 输入的图像往往由人工视觉特征向量表示。 这些人工视觉特征向量并不能严格保持图像对之间的精确语义相似度信息， 这将导致学习的哈希函数性能较低。 因此， 基于深度学习的哈希方法被不断提出。 这类方法的不同主要体现在四个方面：

1. 监督性

   监督性即在使用深度神经网络框架学习哈希码的过程中是否利用到原始图像的标签或相似点对信息， 分为监督和非监督。 对于监督的基于深度学习的哈希方法， 除了传统的依赖于图像标签信息的监督哈希方法， 另一些利用相似对信息的监督哈希方法又可以分为两类， 一类依赖于成对相似度信息， 另一类依赖于三元组相似度信息。

2. 网络并行性

   即只使用单一的深度神经网络还是并行使用多个深度神经网络学习哈希码。

3. 网络层数
   即使用的深度神经网络的层数。

4. 独立性
   即从图像中学习特征表示和哈希编码两个过程是联合学习的还是独立学习的。

对当前几种经典的基于深度学习哈希方法的分类细节详见表2.2， 其中标号为[1]中参考文献。

数据自身特性

相似度度量

欧氏距离

通常情况下， 原始空间中的两个点 $x$ 和 $y$ 之间的相似度是由欧氏距离度量的：

$$E_d(x,y)=||x-y||_2=\sqrt{\sum_{i=1}^m(x_i-y_i)^2}$$

大多数哈希方法都基于此， 如上面提到的 LSH 和 SH。

核距离

上面提到的哈希方法有一定的局限性， 即假设原始空间中的点是由向量形式表示的。 然而在很多实际应用中， 如多媒体、 生物、 网络等， 数据点往往具有复杂的表现形式， 如图、 树、 序列， 集合等。 对于这些常见的数据类型， 大量复杂的核被用来定义数据点之间的相似度。 而且在图像检索等视觉应用中， 即使图像是由向量形式表示的， 核距离与欧氏距离相比可以更好地展现出图像之间的语义相似度。 除此之外， 对于很多机器学习应用， 无法知道原始空间的明确数据， 只可以计算点对的核函数相似度。 因此在这些情况下， 很多处理核函数相似度的哈希方法被提出， 它们既可以适用于向量输入也可以适用于非向量输入。

核函数包括线性核函数， 多项式核函数， 高斯核函数等。 其中，高斯核函数是最常见的， 也叫做径向基函数， 它是一种沿着径向对称的标量函数， 定义如下：

$$k(||x-xc||)=e^{-\frac{||x-xc||^2}{2\sigma^2}}$$

其中， $xc$ 是核函数的中心， $\sigma$ 是宽度系数。我们可以看出高斯核函数是欧氏距离的反依赖函数。 Optimized Kernel Hashing (OKH) 是典型的处理核相似度的哈希方法， 详见[1]。

语义距离

非监督哈希方法不需要利用带标签训练数据点的标签信息， 其目标函数的构造依赖于预先设定的相似度矩阵。 然而在图像检索等应用中， 图像之间相似度并不是由一个简单的度量标准定义的， 因为它并不能保证图像之间的语义相似度。 语义相似度往往由带标签的图像对给出， 也就是说， 原始空间中相似的图像对至少拥有一个共同的标签。 对于这样的成对标签数据， 监督哈希方法可以生成保持语义相似度的哈希码。 其中，Semi-Supervised Hashing (SSH) 是经典的处理语义相似度的哈希方法， 详见[1]。

数据模态

单模态

近年来， 大多数哈希方法都依赖于同质相似度， 即数据库中的数据本体都是同一种类型的， 这样的哈希方法称作单模态哈希方法。 但是随着因特网和多媒体设备的快速发展， 我们可以很容易获得大量数据， 如文本， 图像， 视频等。 随着数据规模的扩大， 数据本体的密度也不断扩大。 在实际应用中， 异质本体也是普遍存在的， 即一些数据库包含的同一种数据本体有多种视角。 因此， 多模态哈希方法被提出来解决从多种异构领域中搜索出相似数据本体的问题。

多模态

初始的多模态哈希方法一般通过将原始空间中的异质数据点映射到一个统一的汉明空间中再进行相似度搜索排序。 这种方法的关键问题是如何同时构造多种模态之间的潜在联系以及如何保持在每个模态下的相似度关系。 一种方法将多模态本体的每个模态翻译成其中的同一种模态， 然后进行单模态搜索。 然而这种类型方法有两大缺点：

1. 在翻译过程中有一定的近似误差而且很依赖于具体应用。
2. 翻译过程往往很慢， 导致无法适用于很多实际应用。

因此， 近期又产生了一些新的多模态哈希方法， 详见[1]。

数据流动性

固定数据库

目前大多数哈希方法处理数据库中的数据是固定的。 但在实际应用中， 数据往往连续生成。 比如， 百度的数据中心搜索机器每天都新增大量文本图像之类的网页。 对于这种流动性数据， 已有的哈希方法必须重新训练新的哈希函数， 这种效率根本无法适应数据库中数据数量的增长和多样性的变化。

在线数据库

因此， 近期出现了一些可以处理流动数据的在线哈希方法。 详见[1]。

哈希平台

单机

之前讨论的哈希方法处理的都是单一中心机器上的数据， 然而随着数据库规模的扩大， 数据常常是分布式存储的， 一种直观的方法是将所有的数据读取到同一个工作站中，然后像在单机上一样训练哈希函数。 但是这将导致计算， 时间和空间复杂度太高。

分布式

Hashing for Distributed Data (HDD) 是一种分布式哈希方法。 HDD 分布式地学习哈希函数。 由于在训练过程中没有节点之间训练数据的交换， 通信成本很小， 使得 HDD可以适用于任何大规模分布式应用。

哈希排序方法简介

哈希排序指的是在哈希过程的最后一步， 对数据库中所有点哈希得到的二进制码的排序问题。 汉明距离是最常用的二进制码排序标准， 但它无法对那些与查询点具有相同汉明距离的二进制码排序。 如图 3.1 所示， 假设数据库中的点都是二维的， 红色叉表示查询点并被编码为“11” ， 绿色圆点表示查询点的真实 $\varepsilon$-最近邻。 很显然， 所有编码为 “01” 和 “10” 的点都与查询点具有相同的汉明距离。 然而， 由于查询点的真实 $\varepsilon$-最近邻中包含了部分编码为 “01” 的点而并不包含任何编码为 “10” 的点， 因此编码 “01” 应该排在编码 “10” 的前面。 在这个例子中， 汉明距离无法给出一个合理的哈希排序。

因此从 2011 年开始不断有人研究哈希排序算法。 近年来的哈希排序成果主要基于两类距离： 加权汉明距离和非对称距离。 几种代表性的哈希排序方法分类详见表 3.1， 其中标号为[1]中参考文献。

加权汉明距离

加权汉明距离的权重一般由两部分组成： Offline 权重和 Online 权重。 Offline 权重不依赖于查询点， 根据数据库中点的分布计算得出。 该权重一般在投影空间中求解， 因为投影空间 $P$ 的信息量远远大于二进制空间 $B$；Online 权重依赖于查询点， 根据查询点与数据库中点的相对分布关系求解。 加权汉明距离的权重基本上有两种计算方法： 按位算权重和按类别算权重。

按位算距离

按位算权重即对哈希后的每一位计算一个权重 $w_k$ ，并满足 $\sum_{j=1}^kw_j=1$ 。则查询点 $q$ 和数据库中点 $x_i$ 的加权汉明距离 $\text{WHamm}(h(q),h(x_i))$ 计算如下：

$$\text{WHamm}(h(q),h(x_i))=\sum_{j=1}^k w_j·\text{Hamm}(h_j(q),h_j(x_i))$$

经典的代表算法有 QsRank， WhRank 等， 详见[1]。

按类别算距离

按类别算权重适用于将标签作为相似度表示的数据库， 如 CIFAR， NUS-WIDE 等。我们以 Lost in Binarization 为例阐述类别权重的计算方法。

1. Offline 权重学习阶段。 输入数据库点的二进制码以及类别间的相似度就可以迭代输出 $k$ 个类别的权重 $a_i,i=1,…,k$。其目标函数旨在最大化类间距离和最小化类内距离。

2. Online 权重学习阶段。 首先， 计算查询点 $q$ 与数据库中所有点哈希后的二进制码之间的汉明距离， 返回与查询点 $q$ 最相近的前 $k$ 个点， 并记录它们的标签集合为 $T$ 以及每个标签中含有点的个数（ $k$ 近邻中） 为 $m_i$ 。 则查询点 $q$ 的最终权重 $a_q$

   定义如下：

   $$a_q=\sum_{i\in T}(m_ia_i)/\sum_{i\in T}m_i$$

图 3.2 显示了以图像搜索为例， 应用上述权重对汉明距离进行重排序的完整过程。

非对称距离

哈希编码分为投影和量化为二进制两个过程。 非对称的意思是只对数据库中的点二进制化， 而对查询点只投影不量化。 因此， 将非二进制的查询点与二进制的数据库点之间的距离称作非对称距离， 详见[1]。 非对称距离可以提高检索精度主要有以下两点原因：

1. 由于没有对查询点二进制化， 因此可以获取查询点更精准的位置信息， 从而提高检索精度。 在存储上， 仅仅多额外存储一个查询点的非二进制化向量与检索过程的整个存储量级相比是可以忽略的。
2. 非对称距离的实数量级与汉明距离的整数量级相比， 可以对距离空间进行更浓密的划分。 也就是说， 非对称距离可以将汉明距离无法区分的二进制码重新排序， 从而提高检索精度。

总结

我们简述了哈希方法的发展历史， 并从一个新颖的角度对哈希方法进行清晰地分类。 该文很适合对哈希方向感兴趣的读者快速找到他们感兴趣的分支。