Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍

由于篇幅太长,这篇文章的讲述了文章的Introduction和Related Work部分。而文章的主体部分在Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 实现与分析 这篇文章里面。


摘要

这篇论文讲的是在高维空间的最近点搜索问题(ANN)的一个实现算法,该算法继承自 乘积量化(Product Quantization) 算法。在该算法中,提出了如下几点:

  • 将原来的乘积量化算法进行分层,使用树形结构减少向量的比较次数
  • 提出了一个重排序算法,该算法有更好的并行度

简介

最近点搜索问题(NN)就是在D维空间中,对于一个向量y,找寻样本集合\mathcal{X}中,最近点的问题,形式化表达——

(1)   \begin{equation*} N(y) =\mathop{\arg\min}_{x \in \mathcal{X}} d(y,x) \end{equation*}

在视觉识别的领域的很多课题中,该问题的维数D变得非常大,引入了一种称之为 “维数灾难” 的现象。形象的解释这个问题,对于一个体积a^128的128维高维立方体,一个体积0.1 \times a^128的立方体,边长也是0.1^{\frac{1}{128}} = 0.982\times a。从这个例子可以看到,由于高维立方体体积增长速度过于迅速,我们基本不可能通过遍历区域的方式进行搜索。例如,在128维空间中,即使我们只要访问10%的体积,这些体积分配到单维度上也超过了98%。

给予上述瓶颈,大多数应用中,我们都是用了临近点搜索的方式(ANN),搜索一个相对较近的邻居。对于该问题,人们已经研究出了很多基于CPU的实现,从KD树(KD-tree),到随机KD森林(Randomized KD forest),和KD-mean Trees。这一系列算法都试图将搜索空间缩减到一个包含询问点的尽量小的邻域。

另一个截然不同的实现方式是局部敏感哈希算法(Local Sensitive Hashing),这个方法将整个数据库的向量的一系列随机投影使用哈希表储存,在询问中,对于和询问向量落在了同一个哈希项中的样本向量进行额外的距离检查。

上述基于CPU的ANN算法在像GPU迁移的时候都会遇到或多或少的问题,而基于GPU的算法则很多都是纯粹暴力算法。而在这篇文章中提出的算法,不仅高效利用了GPU,甚至其CPU版本都和上述算法匹敌。

在效率评估上,由于在实际生产中,存在一个“离线预处理”阶段计算所有询问无关的数据,以及一个“在线计算”阶段,实时处理询问相关的计算。因此,最科学的方式应该是将两个阶段的用时分别测量。

向量量化(Vector Quantization)是一个简单的ANN算法,它将样本集\mathcal{X}中所有的向量进行聚类。对于某个询问向量,距离其最近的聚类中心所对应的样本集子集\mathcal{X}_k \subset \mathcal{X}是最有可能存在最近点的。然而倘若询问点恰好位于两个聚类的边界上,则算法就不那么容易找到最近点了。另一方面,一个聚类簇在V图上的相邻聚类簇的个数随着维数的增加指数级增长。

乘积量化(Product Quantization)算法是当下很多最前沿ANN算法的核心,一般来说,基于PQ的算法都有如下几步

  1. 通过一个高效但是低精度的算法,选出一系列候选点集。
  2. 在重排序过程(re-ranking step)中,使用近似距离将候选点集进一步排序。
  3. 排序后的前面K个候选点重新计算实际距离并取最近者。

在PQ类算法的基础上,我们平行提出了一个称之为Product Quantization Tree的算法(PQT),这个算法的贡献点有

  1. 二级乘积和树形结构,减少计算量
  2. 引入Dijkstra算法的松弛操作
  3. 一个O(P)复杂度的近似排序算法,其中P为询问向量的分段数

背景

向量量化与乘积量化

由于我们的算法是基于PQ算法的,因此下面将介绍PQ算法。

首先,乘积算法(Product Quantization)的鼻祖是向量量化(Vector Quantization)算法。已知最初的样本集合\mathcal{X} = \{x_1,x_2,x_3,\dots,x_n\},以及一个码表(codebook)\mathcal{C} = \{c_1,c_2,\dots,c_k\},我们可以定义映射c(x) = \arg \min _{c \in \mathcal{C}} d(x,c),将每个样本点映射到最近的码字。同时,对于每个码字也控制了一系列样本点,令这些点集为C_kC_k =\ {x \in \mathbb{R}^D | c(x) = c_k\},这个点集也成为簇(cluster)或盒子(bin)。直接使用码字代表样本点,虽然引入了一些距离上的不精确,但是在后续寻找相似向量中很有用。在上述算法中,关键点集合可以通过一个叫Lloyd Iteration的算法得到。

在PQ算法中,高维的向量空间可以等价于若干低维向量空间的乘积,假设D = P \cdot m,那么对于所有的样本向量都可以进行分解,x \in ([x]_1,[x]_2,\dots,[x]_p)^T, [x]_i \in \mathbb{R}^m. 对于x \in \mathbb{R}^D,我们可以将该高维空间中的码表定义为C = C_1 \times C_2 \times \dots \times C_P,这个集合里面实际上包含了k^P个D维码字,但是却只需要k \cdot P个m维码字。由于码字变得非常非常多,我们可以对于高维向量进行更加精细的匹配。最终,一个向量的编码(Canonical Projection)定义为其P个独立组成部分的码字组合而成——

    \[c_p : \mathcal{X} \rightarrow \mathcal{C}_p, x\mapsto c_p(x) := \mathop{\arg \min}_{c \in C_p}  d([x]_p,c)\]

    \[c(x) = (c_1(x),c_2(x), c_3(x), \dots, c_p(x))^T\]

从上式可以发现,对于P个部分的量化操作使用了不同的码书,这些码书和VQ一样,都可以使用Lloyd Iteration生成。

诚然,查询任意一个向量处于哪一个簇是非常简单的。但是任意向量所归属的簇在大部分情况下都是空的,这是因为数据分布的稀疏性。不过,在实际使用中,查询向量通常和样本有相同分布,在这个条件下,我们确实可以成功的依照簇找到最近的向量。即使如此,我们还是需要考虑最坏的情况。

一些研究者为了实现更加精确的乘积量化方式,找到了一些解决方式,比如对于所有询问x,统一使用一个线性变换R修饰。及每次查询Rx。不过这个方法在GPU上并不怎么方便。

右图的四部分就分别介绍了“向量量化(Vector Quantization)”和“乘积量化(Product Quantization)”对应的中心点分布图。下层的两幅图则尝试按照不同的“粒度”实现树状查询,在之后会详细讨论。

 

倒排文件系统

对于一个询问y \in \mathbb{R}^D,有的文章使用了含“非对称距离计算”的倒排系统实现。在这个实现中,首先一次VQ,在规模k的码书中提取一系列候选码字(原文中是在8192个向量中,提取0.05%,即64个候选)。不过,即使是64个候选码字也廊括了524288个样本向量。

在这个实现中,选择一组合理的码字消耗了k个D维向量距离运算,在计算了k次距离之后,其中最近的w个码字对应的样本集合的并集\mathcal{L}_c \in \mathcal{X}就是“极有可能包含答案的向量集合”。这一系列向量进一步在基于PQ算法的重排序(re-ranking)。按照中心向量c_wy的距离r_w = y-c_w,从小到大排序,在之前文章中,由于询问向量y事先知道,所以这个距离被放在了查找表(lookup-table)中。

询问向量y和其最近的候选向量可以在集合\mathcal{L}_c中使用相似的方式查找到。只不过这一次,候选集合\mathcal{L}_c小了很多,而码书包含了更多(k_2个词).通过新的码书对应的距离函数,重排序得到更加靠谱的候选集合\mathcal{L}_s,最终,在\mathcal{L}_s中,选择前几个进行最精确的距离计算。

上述步骤意味着共有k_1 + w \cdot k_2次距离计算,在论文默认的规模中,意味着24576次高维向量距离计算每询问。

一个层次化的实现会将总共的距离计算次数将至200,不过,在NVIDIA Titan X架构下,16k的向量距离计算比256次计算慢62倍,因此,在这个问题上,就近多少次距离计算是运行效率的瓶颈。

多索引倒排

相比于之前,在整个数据及上使用VQ,多层次倒排索算法使用了PQ算法,减少了询问向量与中心向量的距离计算次数,而增加了Cluster的总数。

对于y的每一部分,都给定了其到k个中心向量的距离。这些距离经过排序生成如下表格——

(2)   \begin{align*} [y]_1 \rightarrow \{i_{10}, i_{11}, i_{12}, \dots, i_{1k-1}\} \\ [y]_2 \rightarrow \{i_{20}, i_{21}, i_{22}, \dots, i_{2k-1}\} \\ \vdots \\ [y]_P \rightarrow \{i_{P0}, i_{P1}, i_{P}, \dots, i_{Pk-1}\} \\ \end{align*}

上面式子中i_{23}指的是询问向量第二部分的第三近的向量。在此基础上的NN搜索,使用启发式算法,从i=(i_{10},i_{20},\dots,i_{P0})开始。可以使用优先队列,一次访问最近的一个簇中的向量,直到足够多的向量被访问。

讨论

上述的基于VQ和基于PQ的查询算法都能达到很好的精准度。基于VQ的算法需要很大的内含D维向量的码书,即使基于PQ算法的码书会小一些,但是从总量上也非常大。另一方面,两个算法都需要与询问相关的离线初始化操作。这在实时的查询中是不可行的。

对于之前提到的诸多问题,在接下来一章中,我们将使用乘积量化树(Product Quantization Tree)来解决上述的问题,并提出不同的Cluster选择算法,和基于投影的重排序算法。最后,我们将讨论该算法如何在GPU上面运算。

参考文章

理解 product quantization 算法

K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比

原创文章地址:【Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍】,转载时请注明出处mhy12345.xyz

《Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 背景介绍》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.