ANN Search及一些方法

简介

综合转载以下文章：

• 图像检索：再叙ANN Search
• 图像检索：OPQ索引与HNSW索引

在具体到不同类的索引方法分类前，从宏观上对ANN有下面的认知显得很有必要：brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。可以看到，正是因为缩减了遍历的空间大小范围，从而使得ANN能够处理大规模数据的索引。

可以将ANN的方法分为三大类：基于树的方法、哈希方法、矢量量化方法、基于图的方法。

关于索引结构，有千千万万，而在图像检索领域，索引主要是为特征索引而设计的一种数据结构。关于ANN搜索领域的学术研究，Rasmus Pagh发起的大规模相似搜索项目ANN-Benchmarks、Faiss以及ann-benchmarks都有对一些主流的方法做过对比。虽然三个对比的框架对不同方法的性能均有出入，但一些主流方法的性能差异是可以达成共识的，比如基于图方法的ANN其召回率均要优于其他方法。在工业上，常用的索引方法主要以倒排、PQ及其变种、基于树的方法（比如KD树）和哈希（典型代表LSH和ITQ）为主流。

首先从检索的召回率上来评估，基于图的索引方法要优于目前其他一些主流ANN搜索方法，比如乘积量化方法（PQ、OPQ）、哈希方法等。虽然乘积量化方法的召回率不如HNSW（基于图的代表方法），但由于乘积量化方法具备内存耗用更小、数据动态增删更灵活等特性，使得在工业检索系统中，在对召回率要求不是特别高的场景下，乘积量化方法仍然是使用得较多的一种索引方法，淘宝（详见Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph）、蘑菇街等公司均有使用。乘积量化和HNSW特性对比如下：

特性	OPQ	HNSW
内存占用	小	大
召回率	较高	高
数据动态增删	灵活	不易

基于图ANN方法由于数据在插入索引的时候，需要计算（部分）数据间的近邻关系，因而需要实时获取到到数据的原始特征，几乎所有基于图ANN的方法在处理该问题的时候，都是直接将原始特征加载在内存（索引）里，从而造成对内存使用过大，至于召回率图ANN方法要比基于量化的方法要高，这个理解起来比较直观。

基于树的方法

几乎所有的ANN方法都是对全空间的划分，所以基于树的方法也不例外。基于树的方法采用树这种数据结构的方法来表达对全空间的划分，其中又以KD树最为经典，而KD树之前写过了，下面对Annoy](https://github.com/spotify/annoy)进行简单介绍。

Annoy

Annoy是Erik Bernhardsson写的一个以树为数据结构的近似最近邻搜索库，并用在Spotify的推荐系统中。Annoy的核心是不断用选取的两个质心的法平面对空间进行分割，最终将每一个区分的子空间里面的样本数据限制在 $K$ 以内。对于待插入的样本 $x_i$，从根节点依次使用法向量跟 $x_i$ 做内积运算，从而判断使用法平面的哪一边（左子树or右子树）。对于查询向量 $q_i$，采用同样的方式（在树结构上体现为从根节点向叶子节点递归遍历），即可定位到跟 $q_i$ 在同一个子空间或者邻近的子空间的样本，这些样本即为 $q_i$ 近邻。

为了提高查询的召回，Annoy采用建立多棵树的方式，这种做法是一种非常常见的做法，比如NV-tree也采用这种方式，哈希方法采用多表的哈希方法。

值得注意的是，Annoy如果不保存原始特征，则Annoy只能返回查询的 $k$ 个近邻，至于这 $k$ 个里面的排序顺序是怎么样的，它是不知道的，如果需要知道，需要对这 $k$ 个返回的结果，获取原始特征，再计算各自的相似度，排序一下即可得到这 $k$ 个结果的排序。

根据Annoy的定义的节点数据结构，如下：

struct ANNOY_NODE_ATTRIBUTE Node {
S n_descendants;
union {
  S children[2]; // Will possibly store more than 2
  T norm;
};
T dot_factor;
T v[1]; // We let this one overflow intentionally. Need to allocate at least 1 to make GCC happy
};

其中T v[1]保存原始特征，保存原始的特征的坏处是造成占用内存过大，索引文件过大。

哈希方法

哈希，顾名思义，就是将连续的实值散列化为0、1的离散值。在散列化的过程中，对散列化函数(也就是哈希函数)有一定的要求。根据学习的策略，可以将哈希方法分为无监督、有监督和半监督三种类型。在评估某种哈希方法用于图像检索的检索精度时，可以使用knn得到的近邻作为ground truth，也可以使用样本自身的类别作为ground truth。所以在实际评估准确度的时候，根据ground truth的定义，这里面是有一点小的trick的。通常对于无监督的哈希图像检索方法，由于我们使用的都是未标记的数据样本，所以我们会很自然的采用knn得到的近邻作为ground truth，但是对于图像检索的这一任务时，在对哈希函数的构造过程中，通常会有“相似的样本经编码后距离尽可能的近，不相似的样本编码后则尽可能的远”这一基本要求，这里讲到的相似，指语义的相似，因而你会发现，编码的基本要求放在无监督哈希方法里，似乎与采用knn得到的近邻作为ground truth的评价方式有些南辕北辙。对无监督哈希方法的ground truth一点小的疑惑在原作者读书的时候就心存这样的困惑，一直悬而未解。当然，在做无监督的图像哈希方法，采用样本自身的类别作为ground truth是毋庸置疑的。

原作者读书那会儿，研究了很多的哈希图像检索方法（见hashing-baseline-for-image-retrieval），有时候总会给一些工程实践上的错觉（在今天看来是这样的），即新论文里的方法远远碾压经典的方法，那是不是在实际中这些方法就很work很好使。实践的经历告诉小白菜，还是经典的东西更靠谱，不是因为新的方法不好，而是新的事物需要经过时间的沉淀与优化。

局部敏感哈希 LSH

之前博客写过LSH了，这里主要是原作者的作为补充。

为什么要用多表哈希？

对于单表哈希，当我们的哈希函数数目 $K$ 取得太大，查询样本与其对应的最近邻落入同一个桶中的可能性会变得很微弱，针对这个问题，我们可以重复这个过程 $L$ 次，从而增加最近邻的召回率。这个重复 $L$ 次的过程，可以转化为构建 $L$ 个哈希表，这样在给定查询样本时，我们可以找到 $L$ 个哈希桶（每个表找到一个哈希桶），然后我们在这 $L$ 个哈希表中进行遍历。这个过程相当于构建了 $K\ast L$个哈希函数（注意是“相当”，不要做“等价”理解）。

多表哈希中哈希函数数目K和哈希表数目L如何选取？

哈希函数数目 $K$ 如果设置得过小，会导致每一个哈希桶中容纳了太多的数据点，从而增加了查询响应的时间；而当 $K$ 设置得过大时，会使得落入每个哈希桶中的数据点变小，而为了增加召回率，我们需要增加 $L$ 以便构建更多的哈希表，但是哈希表数目的增加会导致更多的内存消耗，并且也使得我们需要计算更多的哈希函数，同样会增加查询相应时间。这听起来非常的不妙，但是在 $K$ 过大或过小之间仍然可以找到一个比较合理的折中位置。通过选取合理的 $K$ 和 $L$，我们可以获得比线性扫描极大的性能提升。

Multiprobe LSH是为了解决什么问题？

多probe LSH主要是为了提高查找准确率而引入的一种策略。首先解释一下什么是Multiprobe。对于构建的 $L$ 个哈希表，我们在每一个哈希表中找到查询样本落入的哈希桶，然后再在这个哈希桶中做遍历，而Multiprobe指的是我们不止在查询样本所在的哈希桶中遍历，还会找到其他的一些哈希桶，然后这些找到的 $T$ 个哈希桶中进行遍历。这些其他哈希桶的选取准则是：跟查询样本所在的哈希桶邻近的哈希桶，“邻近”指的是汉明距离度量下的邻近。

通常，如果不使用Multiprobe，我们需要的哈希表数目 $L$ 在100到1000之间，在处理大数据集的时候，其空间的消耗会非常的高，幸运地是，因为有了上面的Multiprobe的策略，LSH在任意一个哈希表中查找到最近邻的概率变得更高，从而使得我们能到减少哈希表的构建数目。

综上，对于LSH，涉及到的主要的参数有三个：

• $K$，每一个哈希表的哈希函数（空间划分）数目
• $L$，哈希表（每一个哈希表有 $K$ 个哈希函数）的数目
• $T$，近邻哈希桶的数目，即the number of probes

这三个设置参数可以按照如下顺序进行：首先，根据可使用的内存大小选取 $L$，然后在 $K$ 和 $T$ 之间做出折中：哈希函数数目 $K$ 越大，相应地，近邻哈希桶的数目的数目 $T$ 也应该设置得比较大，反之 $K$ 越小，$L$ 也可以相应的减小。获取 $K$ 和 $L$ 最优值的方式可以按照如下方式进行：对于每个固定的 $K$，如果在查询样本集上获得了我们想要的精度，则此时 $T$ 的值即为合理的值。在对 $T$ 进行调参的时候，我们不需要重新构建哈希表，甚至我们还可以采用二分搜索的方式来加快 $T$ 参数的选取过程。

LSH开源工具包

关于LSH开源工具库，有很多，这里推荐两个LSH开源工具包：LSHash和FALCONN, 分别对应于学习和应用场景。

LSHash

LSHash非常适合用来学习，里面实现的是最经典的LSH方法，并且还是单表哈希。哈希函数的系数采用随机的方式生成，具体代码如下：

def _generate_uniform_planes(self):
    """ Generate uniformly distributed hyperplanes and return it as a 2D
    numpy array.
    """

    return np.random.randn(self.hash_size, self.input_dim)

hash_size为哈希函数的数目，即前面介绍的K。整个框架，不论是LSH的哈希函数的生成方式，还是LSH做查询，都极其的中规中矩，所以用来作为了解LSH的过程，再适合不过。如果要在实用中使用LSH，可以使用FALCONN。

FALCONN

FALCONN是经过了极致优化的LSH，其对应的论文为NIPS 2015 Practical and Optimal LSH for Angular Distance，Piotr Indyk系作者之一（Piotr Indyk不知道是谁？E2LSH这个页面对于看过LSH的应该非常眼熟吧），论文有些晦涩难懂，不过FALCONN工具包却是极其容易使用的，提供有C++使用的例子random_benchmark.cc以及Python的例子random_benchmark.py，另外文档非常的详实，具体可参阅falconn Namespace Reference和falconn module。下面将其Python例子和C++例子中初始化索引以及构建哈希表的部分提取出来，对其中的参数做一下简要的分析。

Python初始化与构建索引L127：

# Hyperplane hashing
params_hp = falconn.LSHConstructionParameters()
params_hp.dimension = d
params_hp.lsh_family = 'hyperplane'
params_hp.distance_function = 'negative_inner_product'
params_hp.storage_hash_table = 'flat_hash_table'
params_hp.k = 19
params_hp.l = 10
params_hp.num_setup_threads = 0
params_hp.seed = seed ^ 833840234

print('Hyperplane hash\n')

start = timeit.default_timer()
hp_table = falconn.LSHIndex(params_hp)
hp_table.setup(data)
hp_table.set_num_probes(2464)

C++初始化与构建索引L194:

// Hyperplane hashing
LSHConstructionParameters params_hp;
params_hp.dimension = d;
params_hp.lsh_family = LSHFamily::Hyperplane;
params_hp.distance_function = distance_function;
params_hp.storage_hash_table = storage_hash_table;
params_hp.k = 19;
params_hp.l = num_tables;
params_hp.num_setup_threads = num_setup_threads;
params_hp.seed = seed ^ 833840234;

cout << "Hyperplane hash" << endl << endl;

Timer hp_construction;

unique_ptr<LSHNearestNeighborTable<Vec>> hptable(
    std::move(construct_table<Vec>(data, params_hp)));
hptable->set_num_probes(2464);

可以看到，有3个很重要的参数，分别是k、l和set_num_probes，对应的具体意义前面已经解释，这里不再赘述。

FALCONN的索引构建过程非常快，百万量级的数据，维度如果是128维，其构建索引时间大概2-3min的样子，实时搜索可以做到几毫秒的响应时间。总之，这是原作者见过的构建索引时间最短查询响应时间也极快的ANN工具库。

另外谈一下数据规模问题。对于小数据集和中型规模的数据集(几个million-几十个million)， FALCONN和NMSLIB是一个非常不错的选择，如果对于大型规模数据集(几百个million以上)，基于矢量量化的Faiss是一个明智的选择。关于这方面的讨论，可以参阅原作者参阅的讨论benchmark。

当然，FALCONN还不是很完善，比如对于数据的动态增删目前还不支持，具体的讨论可以参见Add a dynamic LSH table。其实这不是FALCONN独有的问题，NMSLIB目前也不支持。一般而言，动态的增删在实际应用场合是一个基本的要求，但是我们应注意到，增删并不是毫无限制的，在增删频繁且持续了一段时间后，这是的数据分布已经不是我们原来建索引的数据分布形式了，我们应该重新构建索引。在这一点上，Faiss支持数据的动态增删。

矢量量化方法

矢量量化方法，即vector quantization，其具体定义为：将一个向量空间中的点用其中的一个有限子集来进行编码的过程。在矢量量化编码中，关键是码本的建立和码字搜索算法。比如常见的聚类算法，就是一种矢量量化方法。而在ANN近似最近邻搜索中，向量量化方法又以乘积量化（PQ, Product Quantization）最为典型。在之前的博文基于内容的图像检索技术的最后，对PQ乘积量化的方法做过简单的概要。在这一小节里，原作者结合自己阅读的论文和代码对倒排乘积量化（IVFPQ）和优化乘积量化（OPQ）做一种更加直观的解释。

倒排乘积量化

倒排PQ乘积量化（IVFPQ）是PQ乘积量化的更进一步加速版。其加速的本质逃不开原作者在最前面强调的是加速原理：brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。在上一小节可以看出，PQ乘积量化计算距离的时候，距离虽然已经预先算好了，但是对于每个样本到查询样本的距离，还是得老老实实挨个去求和相加计算距离。但是，实际上我们感兴趣的是那些跟查询样本相近的样本（原作者称这样的区域为感兴趣区域），也就是说老老实实挨个相加其实做了很多的无用功，如果能够通过某种手段快速将全局遍历锁定为感兴趣区域，则可以舍去不必要的全局计算以及排序。倒排PQ乘积量化的”倒排“，正是这样一种思想的体现，在具体实施手段上，采用的是通过聚类的方式实现感兴趣区域的快速定位，在倒排PQ乘积量化中，聚类可以说应用得淋漓尽致。

倒排PQ乘积量化整个过程如下图所示：

在PQ乘积量化之前，增加了一个粗量化过程。具体地，先对 $N$ 个训练样本采用K-Means进行聚类，这里聚类的数目一般设置得不应过大，一般设置为1024差不多，这种可以以比较快的速度完成聚类过程。得到了聚类中心后，针对每一个样本 $x_i$，找到其距离最近的类中心 $c_i$ 后，两者相减得到样本 $x_i$ 的残差向量 $(x_i-c_i)$，后面剩下的过程，就是针对 $(x_i-c_i)$ 的PQ乘积量化过程，此过程不再赘述。

在查询的时候，通过相同的粗量化，可以快速定位到查询向量属于哪个 $c_i$（即在哪一个感兴趣区域），然后在该感兴趣区域按上面所述的PQ乘积量化距离计算方式计算距离。

OPQ

OPQ是PQ的一种改进方法。

通常，用于检索的原始特征维度较高，所以实际在使用PQ等方法构建索引的时候，常会对高维的特征使用PCA等降维方法对特征先做降维处理，这样降维预处理，可以达到两个目的：一是降低特征维度；二是在对向量进行子段切分的时候要求特征各个维度是不相关的，做完PCA之后，可以一定程度缓解这个问题。但是这么做了后，在切分子段的时候，采用顺序切分子段仍然存在一定的问题，这个问题可以借用ITQ中的一个二维平面的例子加以说明：

如上面左图（a图）所示，对于PCA降维后的二维空间，假设在做PQ的时候，将子段数目设置为2段，即切分成 $x$ 和 $y$ 两个子向量，然后分别在 $x$ 和 $y$ 上做聚类（假设聚类中心设置为2）。对左图（a图）和右图（c图）聚类的结果进行比较，可以明显的发现，左图在y方向上聚类的效果明显差于右图，而PQ又是采用聚类中心来近似原始向量（这里指降维后的向量），也就是右图是我们需要的结果。这个问题可以转化为数据方差来描述：在做PQ编码时，对于切分的各个子空间，我们应尽可能使得各个子空间的方差比较接近，最理想的情况是各个子空间的方差都相等。上图左图中，xx和yy各个方向的方差明显是差得比较大的，而对于右图，xx和yy方向各个方向的方差差不多是比较接近的。

为了在切分子段的时候，使得各个子空间的方差尽可能的一致，Herve Jegou在Aggregating local descriptors into a compact image representation中提出使用一个正交矩阵来对PCA降维后的数据再做一次变换，使得各个子空间的方差尽可能的一致。其对应的待优化目标函数见论文的第5页，由于优化该目标函数极其困难，Herve Jegou使用了Householder矩阵来得到该正交矩阵，但是得到的该正交矩阵并不能很好的均衡子空间的方差。

OPQ致力于解决的问题正是对各个子空间方差的均衡。具体到方法上，OPQ借鉴了ITQ的思想，在聚类的时候对聚类中心寻找对应的最优旋转矩阵，使得所有子空间中各个数据点到对应子空间的类中心的L2损失的求和最小。

OPQ在具体求解的时候，分为非参求解方法和带参求解方法，具体为：

• 非参求解方法。跟ITQ的求解过程一样。
• 带参求解方法。带参求解方法假设数据服从高斯分布，在此条件下，最终可以将求解过程简化为数据经过PCA分解后，特征值如何分组的问题。在实际中，该解法更具备高实用性。

基于图的方法

HNSW

HNSW是Yury A. Malkov提出的一种基于图索引的方法，它是Yury A. Malkov在他本人之前工作NSW上一种改进，通过采用层状结构，将边按特征半径进行分层，使每个顶点在所有层中平均度数变为常数，从而将NSW的计算复杂度由多重对数（Polylogarithmic）复杂度降到了对数（logarithmic）复杂度。

贡献

• 图输入节点明确的选择
• 使用不同尺度划分链接
• 使用启发式方式来选择最近邻

近邻图技术

对于给定的近邻图，在开始搜索的时候，从若干输入点（随机选取或分割算法）开始迭代遍历整个近邻图。

在每一次横向迭代的时候，算法会检查链接或当前base节点之间的距离，然后选择下一个base节点作为相邻节点，使得能最好的最小化连接间的距离。

近邻图主要的缺陷：1. 在路由阶段，如果随机从一个或者固定的阶段开始，迭代的步数会随着库的大小增长呈现幂次增加；2. 当使用k-NN图的时候，一个全局连接可能的损失会导致很差的搜索结果。

算法描述

网络图以连续插入的方式构建。对于每一个要插入的元素，采用指数衰变概率分布函数来随机选取整数最大层。

• 图构建元素插入过程（Algorithm 1）：从顶层开始贪心遍历graph，以便在某层A中找到最近邻。当在A层找到局部最小值之后，再将A层中找到的最近邻作为输入点（entry point），继续在下一层中寻找最近邻，重复该过程；
• 层内最近邻查找（Algorithm 2）：贪心搜索的改进版本；
• 在搜索阶段，维护一个动态列表，用于保持 ef​ 个找到的最近邻元素

在搜索的初步阶段，ef​参数设置为1。搜索过程包括zoom out和zoom in两个阶段，zoom out是远程路由，zoom in顾名思义就是在定位的区域做精细的搜索过程。整个过程可以类比在地图上寻找某个位置的过程：我们可以地球当做最顶层，五大洲作为第二层，国家作为第三层，省份作为第四层……，现在如果要找海淀五道口，我们可以通过顶层以逐步递减的特性半径对其进行路由（第一层地球->第二层亚洲—>第三层中国->第四层北京->海淀区），到了第0层后，再在局部区域做更精细的搜索。

参数说明

• efConstruction​：设置得越大，构建图的质量越高，搜索的精度越高，但同时索引的时间变长，推荐范围100-2000
• efSearch​：设置得越大，召回率越高，但同时查询的响应时间变长，推荐范围100-2000，在HNSW，参数ef是​efSearch​的缩写
• M​：在一定访问内，设置得越大，召回率增加，查询响应时间变短，但同时M​增大会导致索引时间增加，推荐范围5-100

HNSW L2space返回的top@K，是距离最小的K个结果，但是在结果表示的时候，距离是从大到小排序的，所以top@K距离是最小的，top@K-1距离是次之，top@1是距离第K大的。只是结果在表示上逆序了而已，不影响最终的结果。如果要按正常的从小到大来排序，则对top@K的结果做个逆序即可。作者在python的接口里，实现了这种逆序，具体见bindings.cpp#L287，所以python的结果和c++的结果，是逆序的差异。

参数详细意义

• M：参数 M 定义了第0层以及其他层近邻数目，不过实际在处理的时候，第0层设置的近邻数目是 2M​。如果要更改第0层以及其他层层近邻数目，在HNSW的源码中进行更改即可。另外需要注意的是，第0层包含了所有的数据点，其他层数据数目由参数mult定义，详细的细节可以参考HNSW论文。
• delaunay_type：检索速度和索引速度可以通过该参数来均衡heuristic。HNSW默认delaunay_type为1，将delaunay_type设置为1可以提高更高的召回率(> 80%)，但同时会使得索引时间变长。因此，对于召回率要求不高的场景，推荐将delaunay_type设置为0。
• post：post定义了在构建图的时候，对数据所做预处理的数量（以及类型），默认参数设置为0，表示不对数据做预处理，该参数可以设置为1和2（2表示会做更多的后处理）。

更详细的参数说明，可以参考parameters说明。

原作者总结

以基于PQ的量化方法在工业界最为实用，基于图的ANN方法，在规模不是特别大但对召回要求非常高的检索场景下，是非常适用的。除此之外，图ANN方法可以和OPQ结合起来适用，来提高OPQ的召回能力，具体可以阅读Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors和Link and code: Fast indexing with graphs and compact regression codes这两篇文章。

总结

原作者总结了很多。

下面是自己的思考：基于图的方法的突出优点是召回率高，在一开始有三个缺点，分别为速度慢、数据动态增删困难、内存占用大。这几年，速度通过很多方法已经有很大提高。而数据动态增删困难主要是因为，插入删除数据后，需要重新构建近邻图。赵老师去年解决了该问题。

Zhao W L . k-NN Graph Construction: a Generic Online Approach[J]. 2018.

所以，目前基于图的方法主要在于内存占用大的缺点，其实问题主要在于为了高召回率，将原数据读到内存中，PQ利用的是聚类中心来粗表示数据点。如果能够利用类似倒排PQ的思想，先用 k-means 粗聚类之后再用爬山算法，可能能够减少内存占用大的问题。