作者|Chilia
整理|NewBeeNLP
最近，进行了使用ColBERT双塔结构的文本召回，其中一定包含向量相似度查询，仅靠brute-force法过于复杂，无法接受。 所以必须在Faiss上制作mrdjz。 因此，今天我们将学习Faiss的原理和实用化。
在这个万物可以嵌入的时代，图像、文本、商品都表示为50-1000维的矢量。 在双塔结构中，我们离线保存着物品的embedding； query来了，必须在巨大的商品池中召回top k个商品。 这个过程必须马上完成，达到很大的查询密码(QPS )。 那么，如何快速召回相似向量呢？
双塔结构的Faiss是Facebook AI团队开源集群和相似性搜索库，为密集向量提供高效的相似性搜索和聚类，支持10亿级向量的搜索，是目前最成熟的近邻搜索库
它包括用于搜索由RAM内存决定的任意大小的向量集的算法，以及用于评估算法和调整参数的支持代码。 Faiss用c编写，提供了与Numpy完美连接的Python界面。 另外，为一些核心算法提供了GPU实现。
1 .暴力搜索1. Faiss个人资料的方法可以得到完全正确的“标准答案”，但其时间复杂度是o(Mn )，这是完全不能接受的。 如果牺牲一些精度，例如允许与参考结果稍微有偏差，相似性检索就会快几个数量级。 加速搜索还涉及数据集的预处理，通常将此预处理操作称为「mrdjz」。 我们主要关注三个评价指标：
「速度」查找与查询最相似的k个向量需要多长时间？ 我期望不会花比暴力算法更长的时间。 否则，mrdjz的意思是什么？
「内存消耗」这种方法消耗的RAM量是多少？ Faiss仅支持在RAM中进行搜索，但磁盘数据库会慢几个数量级。
「精确度」返回的结果列表与暴力搜索结果的一致程度如何？ 可以用Recall @ 10进行评价。
通常，我们在内存资源的限制下权衡速度和精度。 Faiss提供了几种实现数据压缩的方法，包括PCA、产品质量等矢量压缩方法。 当然，还有其他优化手段，但PCA和PQ是最核心的。 中描述的场景，使用以下步骤创建明细表，以便在概念设计中分析体量的体积。
2. Faiss原理首先介绍使用Faiss时的数据流。
使用Faiss时，必须首先基于原始向量build创建mrdjz文件，然后对mrdjz文件执行查询操作。 第一次创建buildmrdjz文件时，需要Train和Add两个过程； 然后，如果需要将新向量添加到mrdjz文件中，则必须在一次Add操作中实现增量buildmrdjz。 但是，如果增量数量级与原始mrdjz相同，则整个向量空间可能会稍有变化。 在这种情况下，必须重新构建整个mrdjz文件。 这意味着，所有向量都需要再去一次Train和Add。 具体来说，如何成为Train
Faiss的核心原理其实是两个部分：
Product Quantizer, 简称PQ.
Inverted File System, 简称IVF.
2.1产品量化方法，即vector quantization，具体被定义为：使用有限子集对向量空间中的点进行编码的过程。 典型的聚类算法是矢量量化方法。 同时，在强蛋饼(Approximate Nearest Neighbor，最近邻)搜索问题中，向量量化方法是最典型的。
2.1.1前向转移pq有一个前向转移过程，一般分为两个阶段的操作，第一阶段的步骤「Cluster」，第二阶段的步骤http://www.Sina.com
数据流的「Train」阶段，可以以一个128维的向量库为例：PQ乘积量化的核心思想还是聚类，K-Means就是PQ乘积量化子空间数目为1的特例。
在做PQ之前，首先需要指定一个参数M，这个M就是指定向量要被切分成多少段，在上图中M=4，所以向量库的每一个向量就被切分成了4段，然后把所有向量的第一段取出来做Clustering得到256个簇心（256是一个作者拍的经验值）；再把所有向量的第二段取出来做Clustering得到256个簇心，直至对所有向量的第N段做完Clustering，从而最终得到了256*M个簇心。
做完Cluster，就开始对所有向量做Assign操作。这里的Assign就是把原来的N维的向量映射到M个数字，以N=128，M=4为例，首先把向量切成四段，然后对于每一段向量，都可以找到对应的最近的簇心 ID，4段向量就对应了4个簇心 ID，一个128维的向量就变成了一个由4个ID组成的向量，这样就可以完成了Assign操作的过程 -- 现在，128维向量变成了4维，每个位置都只能取0~127，这就完成了向量的压缩。
2.1.2 查询完成了PQ的Pre-train，就可以看看如何基于PQ做向量检索了。查询过程如下图所示：
同样是以N=128，M=4为例，对于每一个查询向量，以相同的方法把128维分成4段32维向量，「然后计算每一段向量与之前预训练好的簇心的距离」，得到一个4*256的表。然后就可以开始计算查询向量与库里面的向量的距离。
此时，库的向量已经被量化成M个簇心 ID，而查询向量的M段子向量与各自的256个簇心距离已经预计算好了，所以在计算两个向量的时候只用查M次表，比如的库里的某个向量被量化成了[124, 56, 132, 222], 那么首先查表得到查询向量第一段子向量与其ID为124的簇心的距离，然后再查表得到查询向量第二段子向量与其ID为56的簇心的距离......最后就可以得到四个距离d1、d2、d3、d4，查询向量跟库里向量的距离d = d1+d2+d3+d4。
所以在提出的例子里面，使用PQ只用4×256次128/4维向量距离计算加上4xN次查表，而最原始的暴力计算则有N次128维向量距离计算，很显然随着向量个数N的增加，后者相较于前者会越来越耗时。
2.2 Inverted File SystemPQ优化了向量距离计算的过程，但是假如库里面的向量特别多，依然逃不了一个遍历整个库的过程，效率依旧还是不够高，所以这时就有了Faiss用到的另外一个关键技术——Inverted File System。
倒排乘积量化(IVFPQ)是乘积量化(PQ)的更进一步加速版。其加速的本质就是在前面强调的是加速原理：brute-force搜索的方式是在「全空间」进行搜索，为了加快查找的速度，几乎所有的大力的蛋挞方法都是通过「对全空间分割(聚类)」，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。
在上一小节可以看出，PQ乘积量化计算距离的时候，距离虽然已经预先算好了，但是对于每个样本到查询样本的距离，还是得老老实实挨个去求和相加计算距离。
但是，实际上我们感兴趣的是那些跟查询样本相近的样本(下面称之为“感兴趣区域”)，也就是说老老实实挨个相加其实做了很多的无用功，如果能够通过某种手段快速「将全局遍历锁定为感兴趣区域」，则可以舍去不必要的全局计算以及排序。
倒排PQ乘积量化的”倒排“，正是这样一种思想的体现，在具体实施手段上，采用的是通过聚类的方式实现感兴趣区域的快速定位，在倒排PQ乘积量化中，聚类可以说应用得淋漓尽致。
要想减少需要计算的目标向量的个数，做法就是直接对库里所有向量做KMeans Clustering，假设簇心个数为1024。那么每来一个query向量，首先计算其与1024个粗聚类簇心的距离，然后选择距离最近的top N个簇，只计算查询向量与这几个簇底下的向量的距离，计算距离的方法就是前面说的PQ。
Faiss具体实现有一个小细节，就是在计算查询向量和一个簇底下的向量的距离的时候，所有向量都会被转化成与簇心的残差，这应该就是类似于归一化的操作，使得后面用PQ计算距离更准确一点。使用了IVF过后，需要计算距离的向量个数就少了几个数量级，最终向量检索就变成一个很快的操作。
3. Faiss应用 3.1 IndexFlatL2这种mrdjz的方式是用暴力的(brute-force)精确搜索计算L2距离。
import faiss # make faiss availableindex = faiss.IndexFlatL2(d) # build the index, d = 128, 为dimensionindex.add(xb) # add vectors to the index, xb 为 (100000,128)大小的numpyprint(index.ntotal) # mrdjz中向量的数量, 输出100000k = 4 # we want to see 4 nearest neighborsD, I = index.search(xq, k) # xq为query embedding, 大小为(10000,128)## D为查询得到的物品embedding与query embedding的距离,大小(10000,4)## I为和query embedding最接近的k个物品id，大小(10000,4)print(I[:5]) # neighbors of the 5 first queries输出：
100000[[ 381 207 210 477] [ 526 911 142 72] [ 838 527 1290 425] [ 196 184 164 359] [ 526 377 120 425]]IndexFlatL2的结果精确，可以用来作为其他mrdjz测试中准确性程度的参考。当数据集比较大的时候，暴力搜索的时间复杂度很高，因此我们一般会使用其他方式的mrdjz。
3.2 IndexIVFFlat为了加快搜索的速度，我们可以将数据集分割为几部分，将其定义为Voronoi Cells，每个数据向量只能落在一个cell中。查询时只需要查询query向量落在cell中的数据了，降低了距离计算次数。这就是上文说的倒排mrdjz方法。
IndexIVFFlat需要一个训练的阶段，其与另外一个mrdjzquantizer有关，通过quantizer来判断属于哪个cell。IndexIVFFlat在搜索的时候，引入了nlist(cell的数量)与nprob(执行搜索的cell数)参数。增大nprobe可以得到与brute-force更为接近的结果，nprobe就是速度与精度的调节器。
import faiss # make faiss availablenlist = 100k = 4quantizer = faiss.IndexFlatL2(d) # d = 128, dimensionindex = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)index.train(xb) ## xb: (100000,128)index.add(xb) index.nprobe = 10 # 默认 nprobe 是1 ,可以设置的大一些试试D, I = index.search(xq, k)print(I[-5:]) # 最后五次查询的结果 3.3 IndexIVFPQIndexFlatL2 和 IndexIVFFlat都要存储所有的向量数据。对于超大规模数据集来说，可能会不大现实。因此IndexIVFPQmrdjz可以用来压缩向量，具体的压缩算法就是PQ。
import faissnlist = 100m = 8 ##每个向量分8段k = 4 ##求4-近邻quantizer = faiss.IndexFlatL2(d) # 内部的mrdjz方式依然不变index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8) # 每个向量都被编码为8个字节大小index.train(xb)index.add(xb)index.nprobe = 10 D, I = index.search(xq, k) # 检索print(I[-5:])一起交流
想和你一起学习进步！『NewBeeNLP』目前已经建立了多个不同方向交流群（机器学习 / 深度学习 / 自然语言处理 / 搜索推荐 / 图网络 / 面试交流 / 等），名额有限，赶紧添加下方微信加入一起讨论交流吧！（注意一定o要备注信息才能通过）
本文参考资料[1]
图像检索：再叙大力的蛋挞 Search: https://yongyuan.name/blog/ann-search.html
[2]Faiss | 哈喽哈咯: https://blog.razrlele.com/p/2594
[3]faiss: https://github.com/facebookresearch/faiss
[4]Faiss从入门到实战精通: https://blog.csdn.net/bitcarmanlee/article/details/106447629
- END -
从顶会论文看对比学习的应用！
2021-11-22
深度学习基础 | 超详细逐步图解 Transformer
2021-11-02
升级换代！Facebook全新电商搜索系统Que2Search
2021-10-28
2021最新 北京互联网公司
2021-10-24