共计 2529 个字符，预计需要花费 7 分钟才能阅读完成。
1. 向量检索问题随着神经网络的倒退，embedding 的思维被宽泛的利用在搜推广、图像、自然语言解决等畛域，在理论的工业场景中，咱们经常会遇到基于 embedding 进行文本、图像、视频等物料的相干内容检索问题，这类问题通常要求在几毫秒的工夫内实现百万甚至亿级别候选物料上的检索。在这类问题中，次要须要思考的三个问题是速度、内存以及准确性，其中速度是必须要解决的问题，同时咱们心愿能在保障速度的根底上，尽可能的晋升准确率，升高内存占用。因而能够想到，咱们是不是能够通过肯定的办法，利用内存和准确率来换取查问速度的晋升。Faiss 是由 FacebookAI 团队开发的向量检索库，提供了多种向量查问计划，能够实现在亿级别候选物料上的毫秒级查问，是目前最支流的向量检索库。在 Faiss 中，把具体的查问算法实现称为索引，因为 faiss 中提供了多种类型的索引，因而理解其中不同索引索引的实现形式对于咱们的利用就尤为要害。
2.faiss 索引类型
)faiss 索引类型次要能够分为暴力检索、乘积量化、部分敏感哈希、基于图的办法。向量检索问题通常须要思考召回率、耗时以及内存占用三个问题，而理论的工业场景中，个别存在候选物料量级较大，耗时要求高的状况。比照 faiss 的索引类型，暴力检索类索引尽管召回率百分百，但耗时无奈承受。而罕用的索引类型次要是乘积量化和图两类标签。其中，基于图的办法召回率能够迫近暴力检索且耗时也略优于乘积量化类索引，然而在构建索引过程中须要占用的内存很大，如果能保障足够的资源，图办法能够在耗时和召回率上做到最优。乘积量化召回率低于图办法，然而能保障较好的耗时和空间占用，是在候选物料集较大时的最优抉择。索引召回率耗时暴力检索最优最差基于图的索引优优乘积量化次优优
3. 乘积量化
3.1 向量量化在介绍乘积量化前，首先须要介绍向量量化的基本概念。向量量化和信号编码的概念根本相似，就是将由间断值形成的向量 xx 从欧式空间映射到一个由无限离散值形成的汇合 C ={c_i, i \in [1,l]}C=ci,i∈[1,l] 中, 定义该映射为 qq, 则 q(x) \in Cq(x)∈C, 这里 CC 也成为 codebook。
如上图所示，定义映射函数 qq 为 kmeans，向量量化流程如下:1. 训练 kmeans 聚类，失去每个点所属的聚类编号 2. 将每个向量所属的聚类编号作为量化后果 faiss 中对应该类办法的索引类型为 IndexIVFFlat。
3.2 乘积量化
乘积量化的思路就是将向量宰割成多段后，对每一段别离进行向量量化。假如将向量维度为 DD, 切分成 mm 段，则每段的维度大小为 D^=D/mD∗=D/m，对于第 ii 个分段，向量示意为 x^i_1,x^i_1,…,x^i_{D^*}, 对应的 codebook 为 C_iCi。在索引训练实现后，全局的 codebook 示意为各个分段量化后果的乘积 C =C_1C_2…C_mC=C1∗C2∗…∗Cm，这也是乘积量化的命名起因。
3.3 空间占用比照假如向量维度为 D, 向量量化的 codebook 大小为 kk, 存储 codebook 须要 kDkD 的空间; 乘积量化每个分段只须要 k^k∗的 codebook 大小, 存储 codebook 须要 k^Dk∗D 的空间。能够发现，分段量化后能够在空间占用更小的状况下达到一样大的 codebook 规模。
3.4 faiss 中乘积量化的利用
在 faiss 的乘积量化的实现中，还引入了层次化量化的思维，在乘积量化前引入了一层毛糙量化，造成毛糙量化 + 细粒度量化的两层构造。引入毛糙量化的次要目标在于优化查问速度，因为候选向量的数量级个别较大，如果间接遍历所有候选，效率还是很难达到要求。退出毛糙量化后，通过计算查问向量到毛糙量化类簇核心的聚类就能够选出几个最有可能蕴含正确后果的类簇，而后再在这些类簇上进行第二级的查问，就能够大大缩减查问工夫，同时保障查问效率 索引构建:
- 构建第一层的量化器 q_cqc,codebook C_cCc, 失去每个向量 X 的向量量化后果 x_c=q_c(x)xc=qc(x) 2. 计算每个向量毛糙量化后的残差 x_r=x-x_cxr=x−xc, 对 x_rxr进行乘积量化毛糙量化 + 细粒度量化的模式能够进一步放慢查问速度，然而也会造成肯定的召回率损失，理论利用时须要通过调参较低这一影响。在毛糙聚类后，各个类簇内的向量散布可能差别较大，如果间接用原始向量进行细粒度量化，可能在检索时会放大误差，应用残差进行细粒度量化能缓解这个问题。向量查问 在两层量化构建索引后，查问能够改写为如下模式 d(x,y) = d(y, x_c+x_r) = ||y-x_c||^2+||x_r||^2+2x_cx_r-2yx_rd(x,y)=d(y,xc+xr)=∣∣y−xc∣∣2+∣∣xr∣∣2+2xcxr−2yxr其中,||x_r||^2+2x_cx_r∣∣xr∣∣2+2xcxr和 y 无关，能够事后计算缓存，||y-x_c||^2∣∣y−xc∣∣2 局部须要计算查问向量 yy 到毛糙聚类核心的间隔，这部分的计算量取决于训练时设定的毛糙聚类核心个数，2yx_r2yxr局部须要计算查问向量和簇内残差向量，这部分计算量和设定的查问类簇数量相干，最坏状况下须要遍历所有类簇。3.5 超参构建 PQ 索引时，超参数的抉择会在很大水平上影响线上成果，须要多调参找到召回率和耗时之间的 trader-off。次要影响成果的参数包含毛糙量化类簇个数、分块数量、分块字节等影响索引训练的参数，查问的类簇数量这种影响查问阶段的参数，除此之外 PQ 索引类型对查问成果也有很大影响，能够尝试 PQ，OPQ，PQ with PCA 等不同索引。4. 参考资料 Huang J T , Sharma A , Sun S , et al. Embedding-based Retrieval in Facebook Search[C]// 2020.faiss wiki:github.com/facebookres…语义向量召回之 ANN 检索:mp.weixin.qq.com/s/YOnzPcQia…Faiss 基于 PQ 的倒排索引实现:zhuanlan.zhihu.com/p/34363377