开发者社区> 2G冲浪词条> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

FaissPQ索引简介

简介: FaissPQ索引简介
+关注继续查看

1.png

1.向量检索问题
随着神经网络的发展,embedding的思想被广泛的应用在搜推广、图像、自然语言处理等领域,在实际的工业场景中,我们常常会遇到基于embedding进行文本、图像、视频等物料的相关内容检索问题,这类问题通常要求在几毫秒的时间内完成百万甚至亿级别候选物料上的检索。
在这类问题中,主要需要考虑的三个问题是速度、内存以及准确性,其中速度是必须要解决的问题,同时我们希望能在保证速度的基础上,尽可能的提升准确率,降低内存占用。因此可以想到,我们是不是可以通过一定的方法,利用内存和准确率来换取查询速度的提升。
Faiss是由FacebookAI团队开发的向量检索库,提供了多种向量查询方案,可以实现在亿级别候选物料上的毫秒级查询,是目前最主流的向量检索库。在Faiss中,把具体的查询算法实现称为索引,由于faiss中提供了多种类型的索引,因此了解其中不同索引索引的实现方式对于我们的应用就尤为关键。

2.faiss索引类型

2.png

3.乘积量化

3.1 向量量化
在介绍乘积量化前,首先需要介绍向量量化的基本概念。
向量量化和信号编码的概念基本类似,就是将由连续值构成的向量xxx从欧式空间映射到一个由有限离散值构成的集合C=ci,i∈[1,l]C={c_i, i \in [1,l]}C=ci​,i∈[1,l]中,定义该映射为qqq,则q(x)∈Cq(x) \in Cq(x)∈C,这里CCC也成为codebook。

3.png

3.2 乘积量化

4.png

3.3 空间占用对比

假设向量维度为D,向量量化的codebook大小为kkk,存储codebook需要kDkDkD的空间;乘积量化每个分段只需要k∗k^k∗的codebook大小,存储codebook需要k∗Dk^Dk∗D的空间。可以发现,分段量化后可以在空间占用更小的情况下达到一样大的codebook规模。

3.4 faiss中乘积量化的应用

5.png

在faiss的乘积量化的实现中,还引入了层次化量化的思想,在乘积量化前引入了一层粗糙量化,形成粗糙量化+细粒度量化的两层结构。引入粗糙量化的主要目的在于优化查询速度,由于候选向量的数量级一般较大,如果直接遍历所有候选,效率还是很难达到要求。加入粗糙量化后,通过计算查询向量到粗糙量化类簇中心的聚类就可以选出几个最有可能包含正确结果的类簇,然后再在这些类簇上进行第二级的查询,就可以大大缩减查询时间,同时保证查询效率
索引构建:

  1. 构建第一层的量化器qcq_cqc​,codebook CcC_cCc​,得到每个向量X的向量量化结果xc=qc(x)x_c=q_c(x)xc​=qc​(x)
  2. 计算每个向量粗糙量化后的残差xr=x−xcx_r=x-x_cxr​=x−xc​,对xrx_rxr​进行乘积量化

粗糙量化+细粒度量化的形式可以进一步加快查询速度,但是也会造成一定的召回率损失,实际应用时需要通过调参较低这一影响。
在粗糙聚类后,各个类簇内的向量分布可能差异较大,如果直接用原始向量进行细粒度量化,可能在检索时会放大误差,使用残差进行细粒度量化能缓解这个问题。

向量查询
在两层量化构建索引后,查询可以改写为如下形式
d(x,y)=d(y,xc+xr)=∣∣y−xc∣∣2+∣∣xr∣∣2+2xcxr−2yxrd(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+2xc​xr​−2yxr​
其中,∣∣xr∣∣2+2xcxr||x_r||^2+2x_cx_r∣∣xr​∣∣2+2xc​xr​和y无关,可以预先计算缓存,∣∣y−xc∣∣2||y-x_c||^2∣∣y−xc​∣∣2部分需要计算查询向量yyy到粗糙聚类中心的距离,这部分的计算量取决于训练时设定的粗糙聚类中心个数,2yxr2yx_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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Git - 简介
Git - 简介
42 0
Protocol Buffers 简介
本文档的 Protocol Buffer 的中文文档使用的是 Asciidoctor 进行编排的 http://docs.ossez.com/protocol-buffers-docs/index.html(本 WIKI 中的内容将会与在线发布的版本同步) Google Protocol Buffer( 简称 Protobuf) 是 Google 公司内部的混合语言数据标准,目前已经正在使用的有超过 48,162 种报文格式定义和超过 12,183 个 .proto 文件。
1553 0
Lombok简介
最近发现了一个非常好用的库,叫做Lombok,它可以帮助我们简化一些Java代码的编写。我试用了一下感觉非常好用,所以来介绍一下。 下面对Lombok的简单使用方法做一下总结: val 这不是一个注解,用于局部变量声明,减少重复输入。
933 0
QC入门简介
      本篇博客简单介绍QC的基本知识,让大家对QC有一个初步的认识。在软件开发过程中,测试是一个重要环节,以下是缺陷管理流程图:              1、什么是QC? HP质量中心,测试管理工具,现在普遍被称为应用程序生命周期管理工具(ALM),因为它不再仅仅是一个测试管理工具,它支持的软件开发生命周期的各个阶段。
957 0
Git简介
1.Git历史 Git是由Linux之父Linus用2周时间用C语言写的分布式版本控制系统,之前由于linux源代码托管在BitKeeper,但是linux社区的成员破解BitKeeper的协议,BitKeep收回了Linux社区的使用权。
526 0
NBear简介与使用图解
NBear简介与使用图解 框架类型:ORM映射框架 简介:NBear是一个基于.Net 2.0、C#2.0开放全部源代码的的软件开发框架类库。NBear的设计目标是尽最大努力减少开发人员的工作量,最大程度提升开发效率,同时兼顾性能及可伸缩性。
1143 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Phoenix 全局索引原理与实践
立即下载
Phoenix 基本介绍及二级索引
立即下载
Cassandra CQL语法以及功能介绍
立即下载