1. 概述

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

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

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

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

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

2. ANN典型算法

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

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

主要分为：

树方法，如 KD-tree，Ball-tree，Annoy
哈希方法，如 Local Sensitive Hashing (LSH)
矢量量化方法，如 Product Quantization (PQ)
近邻图方法，如 Hierarchical Navigable Small World (HNSW)

3. 树方法

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建立这样的二叉树结构是希望满足这样的一个假设:相似的数据节点应该在二叉树上位置更接近，一个分割超平面不应该把相似的数据节点分在二叉树的不同分支上。

查找的过程: 对于待插入的样本 $x_i$，从根节点依次使用法向量跟 $x_i $做内积运算，从而判断使用法平面的哪一边（左子树or右子树）。对于查询向量 $q_i$，采用同样的方式（在树结构上体现为从根节点向叶子节点递归遍历），即可定位到跟 $q_i $在同一个子空间或者邻近的子空间的样本，这些样本即为 $q_i$ 近邻。

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

4. 哈希算法

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

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

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

离线建立索引
在线查找

5. 矢量量化方法

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

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

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

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

在ANN近似最近邻搜索中，向量量化方法以乘积量化（PQ, Product Quantization）最为典型。

乘积量化

动机：即，PQ量化，很多时候向量不同部分之间的分布不同的，比如下图(3段向量)，因此可以考虑对向量分段，并分别进行分块量化。这个只是直觉原因，本质原因下文讲。

乘积量化定义：将向量分成m个不同的部分，对每个部分进行向量量化,假设平均划分，则每个部分的维度大小为$D^⋆=D/m$

一个向量$[x_1,x_2,…,x_{D^⋆},…,x_{D−D^⋆+1},…,x_D]$，可以划分为$m$组向量，第i组向量形如：$[x_{i_1},x_{i_2},…,x_{i_D^*}]$，每组的codebook为$C_i$，对应的量化器记为$q_i$, $(∀q_i(x_i^⋆)∈C_i)$。则最终的全局codebook就是 $C=C_1*C_2*...*C_m$，乘积量化的名称也来源于此。

分块量化也可以采取聚类量化来实现，则分块聚类中心的个数即为分块codebook的大小。相当于在这个方法下，对每个向量，有【m个分块向量】来量化它，即：【m个分块聚类中心向量】。示意图如下：

如上图所示，将原始向量等分为m组分块向量，每组都进行聚类量化，那么每个向量就有m个分块聚类中心向量来表示，比如vec1用$C_{1−1}, …,C_{m−1}$共m个向量来量化。

乘积量化的好处：假设每个子codebook大小一样，记做$||C_i||=k^⋆$，排列组合一下，那么相当于能表达的向量空间容量是这么大，$||k^⋆||^m$，但是只需要$mk^⋆$的codebook空间，这也是乘积量化大幅度降低空间占用的本质原因。PQ量化原论文中给出的经验取值是$k^⋆=256，m=8$，即：分成8块，每个分块的codebook大小为256，对应的向量空间大小为约$256^8=2^{64}≈1.8×10^{19}$，能够表达的向量个数足够大了。

粗糙量化+残差量化

核心思想：层次化量化，这个也是Faiss中PQ索引的实现方式。其中粗糙量化使用聚类量化，用划分到的粗糙聚类簇的中心向量来粗粒度量化该向量，该结果存在较大的误差；接着对残差结果进行细粒度乘积量化。这样的话，误差就小了。

💡 1. 总体上，每个向量先进行粗糙量化划分到某个粗糙聚类簇里，1个向量对应1个粗糙聚类簇标识，通常称为粗糙量化ID；
2. 然后计算残差向量，即：向量-聚类簇中心向量，再对该残差向量进行分块，并进行细粒度分块残差量化。残差量化的时候，每一块对应一个细粒度聚类簇，1个向量M块，则对应M个细粒度聚类簇标识，通常称为残差量化code。
3. 为什么用残差量化？原始向量可能会有特别大的分布差异/不平衡，也就是说可能聚类后，不同聚类簇分布得非常分散，每个簇所拥有的样本数极度不平衡。但是通过残差化后，即：每个样本向量减去所属的聚类簇中心向量后，残差向量之间的差异就不太大了，然后再对残差向量进行量化，就能更精确的近似原向量。

过程：具体而言，向量库先构造一个小规模codebook $C_c$，量化器为$q_c$。这个就是所谓的粗糙量化，或者称为粗糙聚类。接着，每个向量y都会有一个残差$r(y)=y−q_c(y)$。具体而言：记残差量化步骤的量化器为$q_p$，则$y$可以通过$q_c(y)+q_p(y−q_c(y))$来表示。

\[ y=q_c(y)+q_p(y−q_c(y))=y_C+y_R \]

其中， $y_C$是粗糙量化结果，$y_R$是残差量化结果。

这样的话，【查询向量x】和y之间的距离：

\[ d(x,y)=||x-y||^2=||x-y_C-y_R||^2=\underbrace{||x-y_C||^2}_{term1}+\underbrace{||y_R||^2+2y_Cy_R}_{term2}-\underbrace{2xy_R}_{term3} \]

term 2与查询向量$x$无关，可以提前计算好；
term 1 求$x$和$y$的粗糙量化向量的欧式距离，最多计算$O(k)$次，$k$为粗糙聚类中心个数。
term 3 求$x$和$y$的残差量化向量的内积，遍历所有簇的时候，最多计算$O(mk^*)$次，$mk^*$为分块聚类中心向量。

QPQ

OPQ是PQ的一种改进方法。

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

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

6. 近邻图方法

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

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

Delaunay三角部分

Delaunay 三角剖分（Delaunay triangulation）是学习 HNSW 的预备知识，具体见Voronoi 图和 Delaunay 三角剖分。HNSW 的生成的索引在最后的形式将会是近似的 Delaunay 图，只是由于 HNSW 具有可导航（Navigable）的属性，最后生成的图在搜索时会具有一些长边（Long-range edges）来进行快速逼近目标点。

NSW 主要思想

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

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

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

Short-range edges，用作贪婪搜索算法所需的近似 Delaunay 图。
Long-range edges，用于贪婪搜索的对数缩放。负责构造图形的可导航小世界（NSW）属性。

NSW 中的贪婪搜索

算法计算从查询q到当前顶点的朋友列表的每个顶点的距离，然后选择具有最小距离的顶点。
如果查询与所选顶点之间的距离小于查询与当前元素之间的距离，则算法移动到所选顶点，并且它变为新的当前顶点。
算法在达到局部最小值时停止：一个顶点，其朋友列表不包含比顶点本身更接近查询的顶点

Hierarchical Navigable Small World (HNSW)

该算法贪婪地遍历来自上层的元素，直到达到局部最小值。
之后，搜索切换到较低层（具有较短 link），从元素重新开始，该元素是前一层中的局部最小值，并且该过程重复。
通过采用层状结构，将边按特征半径进行分层，从而将 NSW 的计算复杂度由多重对数（Polylogarithmic）复杂度降到了对数（logarithmic）复杂度。

Reference

干货 | 一文读懂 ANN