ANN Search及一些方法

简介

综合转载以下文章:

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

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

关于索引结构,有千千万万,而在图像检索领域,索引主要是为特征索引而设计的一种数据结构。关于ANN搜索领域的学术研究,Rasmus Pagh发起的大规模相似搜索项目ANN-BenchmarksFaiss以及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的定义的节点数据结构,如下:

1
2
3
4
5
6
7
8
9
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开源工具包:LSHashFALCONN, 分别对应于学习和应用场景。

LSHash

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

1
2
3
4
5
6
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 DistancePiotr Indyk系作者之一(Piotr Indyk不知道是谁?E2LSH这个页面对于看过LSH的应该非常眼熟吧),论文有些晦涩难懂,不过FALCONN工具包却是极其容易使用的,提供有C++使用的例子random_benchmark.cc以及Python的例子random_benchmark.py,另外文档非常的详实,具体可参阅falconn Namespace Referencefalconn module。下面将其Python例子和C++例子中初始化索引以及构建哈希表的部分提取出来,对其中的参数做一下简要的分析。

Python初始化与构建索引L127

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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个很重要的参数,分别是klset_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 JegouAggregating 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 NeighborsLink 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 粗聚类之后再用爬山算法,可能能够减少内存占用大的问题。

一分一毛也是心意