关于搜索:一文纵览向量检索

摘要： 本文针对向量检索要解决的问题，梳理了支流向量检索相干的技术，剖析了向量检索目前的一个趋势。

什么是向量检索

首先咱们理解下什么是向量，所谓向量就是由 n 个数字（二值向量由 n 个比特组成）组成的数组，咱们称之为 n 维向量。而向量检索就是在一个给定向量数据集中，依照某种度量形式，检索出与查问向量相近的 K 个向量（K-Nearest Neighbor，KNN），但因为 KNN 计算量过大，咱们通常只关注近似近邻（Approximate Nearest Neighbor，ANN）问题。

向量度量

常见的向量度量有四种：欧式间隔、余弦、内积、海明间隔

不同的度量形式对应不同的场景，通常欧式间隔用于图片检索，余弦用于人脸识别，内积多用于举荐，海明间隔因为向量比拟小，通常用于大规模视频检索场景。

有了度量当前，咱们通常会用召回率（也通常叫精度）来评估向量检索的成果，对于给定的向量 q，其在数据集上的 K 近邻为 N，通过检索召回的 K 个近邻汇合为 M，则

召回越靠近 100% 代表索引成果越好。

向量检索解决的问题

向量检索从实质上讲，其思维框架和传统的检索办法没有什么区别，前面在解说向量检索的索引构造部时，领会能更粗浅一些。

1. 缩小候选向量集

和传统的文本检索相似，向量检索也须要某种索引构造来防止在全量的数据上做匹配，传统文本检索是通过倒排索引来过滤掉无关文档，而向量检索是通过对向量建设索引构造来绕过不相干的向量，本文重点探讨相干的向量索引构造。

1. 升高单个向量计算的复杂度

传统文本检索在排序时通常会采纳漏斗模型，下层计算比拟轻量，越往下计算越精密，但随着过滤的进行，须要计算的文档数也逐级降落，对高维向量而言，单个向量的计算量还是比拟重，通常会对向量进行量化，对向量做近似计算，最初在一个很小的数据集上做原始向量的排序。

上面咱们围绕这两个问题来开展向量检索的相干探讨。

向量检索索引构造

为向量建设高效的索引构造是向量检索面对的头等问题，在开始开展前咱们看一个 Benchmark 我的项目，这个我的项目在多个公开的向量数据集比照了相干索引构造的召回性能指标，使咱们可能疾速对各种索引构造的性能体现有个直观的意识。

暴力计算

暴力计算是最简略但复杂度最高的一种形式，在计算召回的时候，暴力计算的后果是作为答案的基准数据，在人脸识别的场景中常常要求 100% 的召回率，这种状况下个别间接暴力计算。

基于树的办法

基于树的办法有很多种，比拟典型的有 KDTree、BallTree、VPTree，类比传统的二叉树，树结构无非是在建树的时候是决定往左还是往右扩大，不同的向量树索引在于依照什么规范去决策，KDTree（如下图所示）会选取向量中某个方差最大的维度取中值作为断定规范，也就是以超平面去划分空间，而 BallTree 则以球面去划分空间，VPTree 会先选取一个制高点，而后计算每个点和制高点的间隔，取间隔中值作为断定规范。通常这些办法在检索的时候都会利用三角形不等式来去除不必要的摸索。

基于树的办法还有很多其余类型，但万变不离其宗，无非就是依照某个断定规范，对向量空间进行划分，但不管怎么划分，因为须要回溯的，都决定了基于树的办法在性能上要稍逊一筹。

哈希办法

哈希对大家再相熟不过，向量也能够采纳哈希来减速查找，咱们这里说的哈希指的是部分敏感哈希（Locality Sensitive Hashing，LSH），不同于传统哈希尽量不产生碰撞，部分敏感哈希依赖碰撞来查找近邻。

满足如下两个条件的哈希函数称为（d1,d2,p1,p2）-sensitive：

1. 如果 d(x,y) <= d1，则 h(x) = h(y) 的概率至多为 p1；
2. 如果 d(x,y) >= d2，则 h(x) = h(y) 的概率至多为 p2；

下面的表达式用人话来说就是：高维空间的两点若间隔很近，那么设计一种哈希函数对这两点进行哈希值计算，使得他们哈希值有很大的概率是一样的，若两点之间的间隔较远，他们哈希值雷同的概率会很小。不同间隔度量的哈希函数不同，不是所有间隔度量（如内积）都能找到对应部分敏感哈希

基于倒排办法

传统倒排索引是依据文档蕴含某个词，而后将以后文档放入改词的倒排索引中来建设索引构造，那向量是如何建设起倒排索引呢？通过聚类把整个向量空间划分为 K 个区域，每个区域用一个中心点 C 代替，这样每个向量和所有中心点比照，将本身纳入到间隔本人最近的中心点对应的倒排，整个索引构造就建设起来了

另一种基于倒排的索引是 BOW，原理大体雷同，例如一张图片会抽取出几百个部分特色，先对所有的特色聚类，造成中心点，这些中心点作为倒排的根底，建设索引时，把图片的每个部分特色归类到其最近的中心点，建设倒排，检索时会依据命中的次数来过滤后果。

基于图的办法

后面介绍的索引构造都能够归类为基于空间划分的办法，每个向量只会属于某个划分好的一个区域，这些办法最大的的问题是为了进步召回须要考查很大一块区域的向量，导致计算量激增，那有没有更好的办法来解决这个问题呢？基于图的办法就能够比拟好的实现这一指标，图办法最奢侈的想法是街坊的街坊也可能是街坊，这样把最近邻的查找转化为图的遍历，因为其连通性，能够针对性的考查局部向量而不是按区域来考查，因而能够大幅升高向量的考查范畴。

最近几年图办法是向量检索钻研的一个热点，呈现了如 KGraph、NSG、HNSW、NGT 等一批图索引办法，但实际上这些图办法的次要区别在构建过程，不同图办法采纳不同的伎俩来晋升图的品质，但图检索的步骤根本是统一的：a. 选好入口点；b. 遍历图；c. 收敛。在一直实际中咱们察看到一些个性来评判图索引品质，指引咱们在图办法改良的方向：

1. 街坊点靠近 K 近邻
2. 街坊点数量尽可能少，即缩小出度
3. 尽可能保障图的连通性，减少入度

上面咱们以 HNSW 为例介绍一下图办法的原理，之所以选取 HNSW 在于该办法易于了解，比拟容易实现流式索引构建和更新，属于传统办法在向量上的完满体现。

HNSW 背地其实是跳表在图上的利用，跳表作为一种简略高效的索引构造在 Redis、LevelDB 等零碎中取得广泛应用，如下图所示：

第一层上有全量的数据，在下层依据随机投币决定，越往上投到的概率越小，投到高层的节点往下都有一条记录，作为检索的高速公路疾速后退。

HNSW 的原理也相似，不同于传统跳表在每层用链表来串联节点，HNSW 在每层都是一个 NSW（Navigable Small World Graph），通过图数据结构组织，下层节点也是通过投币决定在哪一层，并且它们在上层图中都有记录，下层图能够看做上层图的一个缩影，检索时，从上到下，一直指引检索过程逐渐凑近想要探寻的向量空间。另外在构图过程中 HNSW 通过边的裁剪来保障图的连通性，这里顺便提一下，纵观多篇图办法的论文，都从本人的视角表述了边裁剪办法，但不论各种办法对裁边形容的有多酷炫，其办法实质都是截然不同的，只是视角不一样而已。

向量量化

后面把支流的向量检索的索引技术根本都概述了一遍，通过索引构造对考查的向量做了裁剪当前，对高维向量而言，单个的计算量还是很大，有没有办法来缩小计算量呢？量化正是基于这个目标技术，所谓量化是指把一个很大的值空间量化到一个较小的值范畴，举个简略的例子，全世界有 60 多亿人口，也就是地球人的表征有 60 多亿种，咱们能够把人量化为男人和女人两种类型，这样就把一个 60 多亿的空间量化成只有两个值的范畴。

罕用的量化个别包含 PQ（及其优化 OPQ、LOPQ）和二值两种。

PQ 原理如图，PQ 中的 P 是乘积的意思，那怎么就冒出个乘积呢？在下图中一个 128 维的向量空间在通过 PQ 解决后，向量空间切分成了 4 段，每段内由 256 个中心点来量化表白，因而原始的 128 维空间当初能够用每段里的中心点组合，也即 256 256 256 * 256 种组合来表白，这就是所谓的乘积。

对于二值向量，因为古代 CPU 都提供了专门的指令，计算海明间隔十分疾速，在海量的向量检索中通常会间接生成二值向量，生成二值向量办法常见的有 ITQ（Iterative Quantization）、DeepHash 等办法。

其余技术

聚类

向量聚类次要指的是 K -means 系列办法，如经典的 K -means、K-means++、K-means#、One pass K-means、YinYang k-means 等，在实践中咱们也应用过分层的办法来取得海量中心点。

内积转换

后面在哈希章节咱们曾经看到对内积是没有方法找到对应的部分敏感哈希函数，内积也不满足三角形不等式，因而导致很多索引构造无奈间接应用内积作为度量，大多数做法是先对向量做归一化再检索，但归一化会转换向量空间散布。钻研人员通过一个数学察看发现了一个办法，通过肯定规定变换，能够使得内积和欧式可能实现负相关，如下图所示：

对向量转换后，可间接用欧式间隔度量形式检索。

向量检索发展趋势

本文结尾咱们提到向量检索的思维框架和传统检索没有什么区别，到目前为止传统办法利用到向量检索的红利也根本吃完。这两年的一个发展趋势是各种办法的组合，通过排汇各种办法的短处，来取得更好的性能、承载更大规模的向量。

量化图

从 Benchmark 上咱们能够清晰的看到，处在劣势位置的办法根本被图办法霸屏，同时咱们晓得量化能够升高单个向量的计算量，因而很天然的一种想法是让两者强强联手，在图遍历过程中应用量化计算来减速，这种办法对于在高维度办法上劣势显著，减速比能达到三倍以上。

图 + 倒排

图的性能尽管卓越，但毛病也非常明显，为了保障检索成果，图上边的保留耗费大量的存储

尤其在向量自身很小的二值向量上，这是不能接受之重，另外图的街坊自身具备随机性，对硬件解决向量也十分不利。倒排形式则恰恰相反，索引构造根本不耗费太多空间，但毛病是空间划分办法容易导致召回率不高，但咱们从暴力计算的察看取得一些启发，暴力计算从空间划分角度有两种视角：能够将暴力计算看做成把所有向量聚类为一个；也能够将暴力计算看做聚类为 N（N 为向量数据集的大小）个核心，每个中心点是向量自身。这两种办法都能 100% 召回，但他们一个是因为中心点上面的向量太多，另一个因为聚类的中心点太多，而导致计算量不可承受，那咱们是否能够找到一个平衡点？适当的中心点数目使得召回和性能获得一个比拟好的均衡？图 + 倒排形式应运而生，用海量中心点去宰割向量空间，图办法来组织海量中心点。

华为云向量检索实际

向量检索的利用呈现了空前的凋敝，华为云搜寻服务（Cloud Search Service,CSS）目前曾经对外开放向量检索的能力，咱们针对高性能和海量数据两种典型的场景都提供了解决方案。

实现上咱们次要基于图办法，在裁边优化，连通性加强，指令减速，多线程解决等方面做了大量加强。比照测试中，咱们召回率远高于 Faiss，在高维度数据上差距更为显著，在同样召回下，咱们性能在 SIFT，GIST 等公开数据集上是 Faiss 2.3 倍以上。比照测试采纳的是雷同的机器，雷同的算法。

总结：

本文针对向量检索要解决的问题，梳理了支流向量检索相干的技术，剖析了向量检索目前的一个趋势。在向量检索的倒退历程中，还有很多相干的办法没有囊括进来，但万变不离其宗，这些办法要么还是传统办法的扩大或者利用三角不等式的优化或者利用档次办法等等。期盼本文能帮忙梳理向量检索的脉络。

参考文献：

1. J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18:509–517,1975
2. P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proc. of the 4th annual ACM-SIAM Symposium on Discrete Algorithms, pages 311–321, 1993
3. Liu, T.; Moore, A. & Gray, A. (2006). New Algorithms for Efficient High-Dimensional Nonparametric Classification. Journal of Machine Learning Research. 7: 1135–1158.
4. P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pages 604–613, Dallas, TX, 1998.
5. W. Dong, C. Moses, and K. Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web, pages 577–586. ACM, 2011.
6. Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR,abs/1603.09320, 2016.

7. https://arxiv.org/abs/1707.00143

8. https://yongyuan.name/blog/ve…

1. A. Shrivastava and P. Li. An improved scheme for asymmetric lsh. Technical report, arXiv:1410.5410, 2014.
2. H. Jegou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117{128, 2011.

11.https://arxiv.org/abs/1810.07355

注：本文局部索引构造示例图源自 https://yongyuan.name/blog/ve…

点击关注，第一工夫理解华为云陈腐技术~