干货 | 一文读懂 ANN

最近研究ANN 检索召回的内容，于是把对于 ANN 的内容整理总结下。由于现在深度学习和神经网络的火爆，大家一听到ANN，首先想到的是Artificial Neural Network人工神经网络，不过这里的ANN并不是Artificial Neural Network，而是Approximate Nearest Neighbor搜索。

1、概述

2、Ann简介

3、Ann典型算法

        3.1 树方法：Kd-tree

        3.2 树方法：annoy

        3.3 哈希算法 

        3.4 量化方法

        3.5 近邻图方法

4、常见的开源检索

5、Ann算法比较

6、Ann 现状及未来

1、概述

新闻推荐系统从海量新闻中推荐出你感兴趣的新闻，百度从海量的搜索结果中找到最优的结果，短视频推荐出你每天都停不下来的视频流，这些里面都包含有今天要介绍的ANN方法。当然，在现在的检索系统中，往往是多分支并行触发的效果，虽然DNN 大行其道，但是 ANN 一直不可或缺。

通用理解上，ANN（Approximate Nearest Neighbor）是在向量空间中搜索向量最近邻的优化问题。目前业界常用nmslib、Annoy算法作为实现。在实际的工程应用中，ANN是作为一种向量检索技术应用，用于解决长尾Query召回问题。将一个资讯的ANN 召回系统抽象出来大概是下面的样子。

2、Ann简介

Ann（approximate nearest neighbor）是指一系列用于解决最近邻查找问题的近似算法。最近邻查找问题，即在给定的向量集合中查找出与目标向量距离最近的N个向量。

比较平凡的方法就是线性查找方法，也就是说每次检索都会遍历整个检索库，虽然准确率是100%，但是其效率是随着检索库的增加而线性增加的，当检索库的大小超过一定阈值之后，每次检索的时间开销将会变得巨大，不能忍受。在搜索集小的时候，还可以接受，但是实际中向量集合往往很大，线性查找方法的计算资源消耗较大且耗时较长，在工程上一般都不会采用这种方法。

在 NN 的搜索上，提出了一些树的方法，比如说 KD-tree，以及进化的 ball-tree，像kd-tree等一些优化方法并没有提高高维空间里的搜索效率，效率甚至比线性扫描还要低，导致准确最近邻搜索难以直接用于实际问题。顾名思义，近似最近邻搜索找到的向量不要求一定是准确的最近邻，只要求距离准确的最近邻很近就可以了，可以看到近似近邻实际上是效果与性能的折衷。

3、Ann典型算法

最近邻检索作为数据检索中使用最为广泛的技术一直以来都是研究热点，由于维度高、数据规模大，直接应用最近邻方法并不可行，因此，最佳实践是使用逼近方法搜索最近邻。目前，近似最近邻缩短搜索时间有两类基本方案：第一类是缩短距离计算的时间，例如降维，第二类是减少距离计算的次数。

在工业上，常用的索引方法主要以倒排、PQ及其变种、基于树的方法（比如KD树）和哈希（典型代表LSH和ITQ）为主流。如果需要更高的召回率的话，则可能需要基于图方法的ANN，比如HNSW。

主要分为：

1. 树方法，如 KD-tree，Ball-tree，Annoy

2. 哈希方法，如 Local Sensitive Hashing (LSH)

3. 矢量量化方法，如 Product Quantization (PQ)

4. 近邻图方法，如 Hierarchical Navigable Small World (HNSW)

3.1 树方法：Kd-tree

基于树的经典实现为kd-tree，通过将空间按维度进行划分，缩小检索范围来加速的方法。适用于空间维度较小的情况。Kd-tree 的方法是：找出数据集中方差最高的维度，利用这个维度的数值将数据划分为两个部分，对每个子集重复相同的过程。

Kd-tree 有一些变种，比如随机k-d树算法建立多棵随机k-d树，从具有最高方差的N_d维中随机选取若干维度，用来做划分。在对随机k-d森林进行搜索时候，所有的随机k-d树将共享一个优先队列。

3.2 树方法：annoy

Annoy是Erik Bernhardsson写的一个以树为数据结构的近似最近邻搜索库，并用在Spotify的推荐系统中。annoy 算法在工程上应用较广，annoy 算法的目标是建立一个数据结构能够在较短的时间内找到任何查询点的最近点，在精度允许的条件下通过牺牲准确率来换取比暴力搜索要快的多的搜索速度。

Annoy通过建立一个二叉树来使得每个点查找时间复杂度是O(logn)。随机选择两个点，以这两个节点为初始中心节点，执行聚类数为2的kmeans过程，最终产生收敛后两个聚类中心点。这两个聚类中心点之间连一条线段（灰色短线），建立一条垂直于这条灰线，并且通过灰线中心点的线（黑色粗线）。这条黑色粗线把数据空间分成两部分。在多维空间的话，这条黑色粗线可以看成等距垂直超平面。

在划分的子空间内进行不停的递归迭代继续划分，直到每个子空间最多只剩下K个数据节点。

通过多次递归迭代划分的话，最终原始数据会形成二叉树结构。二叉树底层是叶子节点记录原始数据节点，其他中间节点记录的是分割超平面的信息。Annoy建立这样的二叉树结构是希望满足这样的一个假设:相似的数据节点应该在二叉树上位置更接近，一个分割超平面不应该把相似的数据节点分在二叉树的不同分支上。

查找的过程就是不断看查询数据节点在分割超平面的哪一边。从二叉树索引结构来看，就是从根节点不停的往叶子节点遍历的过程。通过对二叉树每个中间节点（分割超平面相关信息）和查询数据节点进行相关计算来确定二叉树遍历过程是往这个中间节点左子节点走还是右子节点走。

3.3 哈希算法

哈希的方法是通过哈希函数把向量变换成0、1二值码，hash 算法的的主要工作在于 hash 算法的设计上，要求相似的样本经编码后距离尽可能的近，不相似的样本编码后则尽可能的远。工程中在要使用到哈希方法的场景下一般都会选用的局部敏感哈希（LSH）。

LSH的工作原理是通过hash函数首先将所有的样本点映射到不同的桶中，在查询样本的最近邻时，将其做相同的变换，查询样本的最近邻很大概率会在查询样本落入相同的桶中，只需要在桶中进行搜索即可，不用在所有数据集中遍历，进而加速了查找。

使用LSH对海量数据进行最近邻查找的过程如下：

离线建立索引

<1>选取LSH哈希函数；

<2>根据对查找结果的准确率（即相邻的数据被查找到的概率）确定hash table的个数L，每个table内的hash functions的个数K，以及跟LSH hash function自身有关的参数；

<3>将所有数据经过LSH hash function哈希到相应的桶内，构成了一个或多个hash table；

在线查找

<1>将查询数据经过LSH hash function哈希得到相应的桶号；

<2>将桶号中对应的数据取出；（为了保证查找速度，通常只需要取出前2L个数据即可）；

<3>计算查询数据与这2L个数据之间的相似度或距离，返回最近邻的数据；

3.4 量化方法

向量量化是通过聚类把向量集聚成若干类，每类里面的向量用对应的类中心来近似。这样子，每个向量只需要用其对应的聚类中心的索引ID来表示，其与查询向量间的距离用其对应的聚类中心与查询向量间的距离来近似。向量量化带来了两项优势：

（1）向量需要的存储空间变少了，只需保存对应的聚类中心的ID；

（2）计算时间减少了，只需要通过聚类中心的索引ID来查询预先计算好的聚类中心与查询向量的距离表格。

3.5 近邻图方法

最近的方法是建立一个图结构来解决最近邻问题。点是顶点，将每个点与其他点相连，边的权重为两点之间的距离。各种各样的启发式策略来找出他们最近的邻居。这里介绍使用最广泛的HNSW（Hierarchical Navigable Small World）。

HNSW是一种基于图的数据结构。使用贪婪搜索算法的变体进行ANN搜索，每次选择最接近查询的未访问的相邻元素时，它都会从元素到另一个元素地遍历整个图，直到达到停止条件。

要理解 Hierarchical NSW，要先理解 NSW。NSW算法，对于每个新的传入元素，我们从结构中找到其最近邻居的集合（近似的 Delaunay 图）。该集合连接到元素。随着越来越多的元素被插入到结构中，以前用作短距离边现在变成长距离边，形成可导航的小世界。

圆（顶点）是度量空间中的数据，黑边是近似的 Delaunay 图，红边是用于对数缩放的长距离边。箭头显示从入口点到查询的贪心算法的示例路径（显示为绿色）

图中的边有两个不同的目的：

1. Short-range edges，用作贪婪搜索算法所需的近似 Delaunay 图。

2. Long-range edges，用于贪婪搜索的对数缩放。负责构造图形的可导航小世界（NSW）属性。

NSW 中的贪婪搜索

1. 算法计算从查询q到当前顶点的朋友列表的每个顶点的距离，然后选择具有最小距离的顶点。

2. 如果查询与所选顶点之间的距离小于查询与当前元素之间的距离，则算法移动到所选顶点，并且它变为新的当前顶点。

3. 算法在达到局部最小值时停止：一个顶点，其朋友列表不包含比顶点本身更接近查询的顶点

Hierarchical Navigable Small World (HNSW)

• 该算法贪婪地遍历来自上层的元素，直到达到局部最小值。

• 之后，搜索切换到较低层（具有较短 link），从元素重新开始，该元素是前一层中的局部最小值，并且该过程重复。

• 通过采用层状结构，将边按特征半径进行分层，从而将 NSW 的计算复杂度由多重对数（Polylogarithmic）复杂度降到了对数（logarithmic）复杂度。

4、常见的开源检索

• Annoy Spotify自家的C++库（提供Python绑定）。Annoy最突出的特性是支持使用静态索引文件，这意味着不同进程可以共享索引。

  code：https://github.com/spotify/annoy

• FLANN 加拿大英属哥伦比亚大学出品的C++库，提供C、MATLAB、Python、Ruby绑定。flann库包含基于树的实现（KD-tree）及哈希方法的实现（LSH）。code：https://github.com/mariusmuja/flann

• scikit-learn 知名的Python机器学习库scikit-learn提供了LSHForest、KDTree、BallTree实现。

• PANNS 纯Python实现。已“退休”，作者建议使用MRPT。

• NearPy 纯Python实现。基于局部敏感哈希（Locality-sensitive hashing，简称LSH，一种降维方法）。

• KGraph C++库，提供Python绑定。基于图（graph）算法。 *NMSLIB (Non-Metric Space Library) C++库，提供Python绑定，并且支持通过Java或其他任何支持Apache Thrift协议的语言查询。提供了SWGraph、HNSW、BallTree、MPLSH实现。

• hnswlib（NMSLIB项目的一部分） 相比当前NMSLIB版本，hnswlib内存占用更少。主要支持HNSW（级联式图搜索）。HNSW索引会复制大量内存，不支持范围检索。

  code：https://github.com/searchivarius/nmslib

• RPForest 纯Python实现。主要特性是不需要在模型中储存所有索引的向量。

• FALCONN 是经过了极致优化的LSH。code：https://github.com/FALCONN-LIB/FALCONN

• FAISS Facebook出品的C++库，提供可选的GPU支持（基于CUDA）和Python绑定。包含支持搜寻任意大小向量的算法（甚至包括可能无法在RAM中容纳的向量）。faiss库包含线性检索方法（BLAS库优化）、哈希方法的实现（LSH）及矢量量化方法的实现（PQ、IVFPQ）。faiss库的一大优势是支持索引的动态增删。faiss库的线性检索方法利用blas库加速，个人测试在E5-2620处理器上128维向量可以达到每秒约1500万的检索速度。LSH算法及IVFPQ算法在随机生成（均匀分布）的数据集上除top1外的召回效果不好。ScalarQuantizer算法在速度较慢的cpu上表现比FlatL2好，在较快的cpu（E5 2620 2.1GHz）上不如FlatL2，平均每秒可以检索1000万数据，准确率可以达到95%以上。IndexPQ索引性能数据（E5-2680 v4 2.4GHz 28核）运行时程序并发会利用满cpu资源。code：https://github.com/facebookresearch/faiss/tree/master/demos

• DolphinnPy 纯Python实现。基于超平面局部敏感哈希算法。

• Datasketch 纯Python实现。基于MinHash局部敏感哈希算法。

• PyNNDescent 纯Python实现。基于k-近邻图构造（k-neighbor-graph construction）。

• MRPT C++库，提供Python绑定。基于稀疏随机投影（sparse random projection）和投票（voting）。

• NGT: C++库，提供了Python、Go绑定。提供了PANNG实现。

5、Ann算法比较

ann算法 benchmark

https://github.com/erikbern/ann-benchmarks

作者在AWS EC2（c5.4xlarge）上的测试结果，比较算法的性能

glove-100-angular：

sift-128-euclidean

fashion-mnist-784-euclidean

gist-960-euclidean

nytimes-256-angular

glove-25-angular

从以上评测可以看出（越靠上、靠右，成绩越好），几乎在所有数据集上，排名前五的实现为：

1. HNSW，比Annoy快10倍。

2. KGraph位于第二，和HNSW的差距不算很大。和HNSW一样，KGraph也是基于图（graph）的算法。

3. SW-graph，源自NWSLIB的另一个基于图的算法。

4. FAISS-IVF，源自Facebook的FAISS。

5. Annoy 我们看到，有不少使用局部敏感哈希（LSH）的库。这些库的表现都不是很好。

6、Ann 现状及未来

近些年，词向量技术（尤其是基于DeepLearning的词向量训练技术）取得了长足的进步，业界在检索、推荐等系统中都大量使用了词向量技术，词向量的思路，实质上是将文本映射到较高维度向量空间的向量上，通过向量间的关系来反映文本间的关系。这样做的一个很大的好处就是我们能够借此发现一些隐匿的、深藏在文本背后的某种语义关系，因为我们认为距离相近的向量具有相似的语义。比如，衡量两段文本的语义相似性，单纯从文本层面上想办法，我们可能通过两者重叠的term来衡量，但是如果两段文本分别用了不同的同义词，则这种方法效果不好（可能要引入同义词），但是词向量的方法天然不存在这个问题，如果两段文本语义相似，则两者的向量距离就会比较小。

所以，词向量特别适合解决字面上不相似但语义上相似的问题，举例：

（1）语义检索中，解决传统term倒排命中非0即1的问题，召回语义上相似但看起来命中不好的结果，对传统倒排召回结果进行补充；

（2）某些推荐应用中，需要将某些长尾的query转化为语义相近的热门表达，然后以热门表达query进行后续的处理。

对于词向量的匹配、查找类需求，最近邻查找问题是一个始终绕不过去的问题。

7、待续

这里给自己挖个坑，下次详细介绍在业界广泛应用的 hnsw 和 annoy 算法。

参考：

https://github.com/nmslib/hnswlib

https://arxiv.org/pdf/1603.09320.pdf

https://segmentfault.com/a/1190000013713357

https://msgi.github.io/2018/09/07/annoy-learn/

https://yongyuan.name/blog/ann-search.html?spm=a2c4e.11153940.blogcont697621.17.3ef936ddMFh7on

https://www.msra.cn/zh-cn/news/features/approximate-nearest-neighbor-search

https://www.ryanligod.com/2018/11/27/2018-11-27%20HNSW%20%E4%BB%8B%E7%BB%8D/