导读：本文是“数据拾光者”专栏的第三十八篇文章，这个系列将介绍在广告行业中自然语言处理和推荐系统实践。本篇主要介绍实际广告搜索业务中经常使用的大规模检索利器faiss，希望对在海量高维向量空间进行大规模检索任务感兴趣的小伙伴有所帮助。
摘要：本篇主要介绍实际广告搜索业务中经常使用的大规模检索利器faiss。首先是背景介绍，主要讲了相似度匹配任务和大规模检索算法以及如何应用到我们的实际业务场景；然后重点介绍了faiss，包括什么是faiss、大规模检索任务流程、faiss索引类型介绍、各种索引优缺点对比以及线上构建索引经验分享；最后项目实践了faiss。希望对在海量高维向量空间进行大规模检索任务感兴趣的小伙伴有所帮助。
下面主要按照如下思维导图进行学习分享：
01
背景介绍
1.1 相似度匹配任务和大规模检索算法
机器学习领域中有很多相似度匹配任务。比如NLP场景中我们会根据一段文本，从海量文本数据集中去匹配相似文本。一个实际的业务就是根据用户搜索词来展示语义相似的广告，比如用户在浏览器搜索了”传奇XX”，终端会展示传奇游戏相关的广告；同样的CV场景中根据一张图片，从海量图片库去匹配相似图片。比如要获取某个人的信息，可以根据一张采集到的图片信息去图像库中匹配。按照这个逻辑下去，根据一条语音去匹配相似语音，根据一条视频去匹配相似视频等等。
这类任务就是相似度匹配任务，从表面上看是从文本数据集中去找相似的文本，但是对于计算机来说并不能理解文本，需要先将文本数据转化成计算机可以理解的特征向量embedding。这里针对不同模态的数据会使用不同的模型映射成特征向量，最后实际上去匹配相似的embedding向量。从海量的高维向量库进行向量匹配就需要用到大规模检索算法。
1.2 如何应用到我们的实际业务场景
我主要从事广告相关的NLP工作，对应到我们线上业务场景中，可以根据用户搜索词来匹配广告，渠道可以是浏览器、软件商店等等，广告可以是app、H5广告等；另一种业务场景是会根据语义相似度来匹配相似文本，扩展语料用于文本分类任务中。这是我们目前线上使用大规模检索算法的两种应用场景。
02
详解大规模检索利器faiss
上一节主要介绍了相似度匹配任务和我们实际业务场景中的应用，本节主要介绍实际项目中完成相似度匹配任务用到的技术，由Facebook维护开源的高效特征相似度匹配库faiss。
2.1 什么是faiss
Faiss全称是Facebook AISimilarity Search，是Facebook维护的一个针对海量高维向量库进行高效可靠检索的开源库。当我们需要从海量文本数据集中进行相似文本检索时，如果进行暴力检索，也就是去和向量库中的每一条样本进行相似度匹配，那么检索的时间非常长，很难满足线上实时性要求。针对这类问题，faiss提供了一整套大规模数据集检索解决方案，总的来说主要从两方面改善暴力检索存在的问题，第一方面是提升检索速度，第二方面是降低内存使用。
2.2 大规模检索任务流程
基于Faiss构建大规模检索任务主要包括以下几个流程：
(1) 获取候选集库和待检索数据
候选集库就是需要去检索的数据库，比如海量的文本数据集、图片库等。待检索数据就是需要去匹配的样本，比如用户搜索query或者图片等，这里可以是一条或者多条。通常情况下这里候选数据集库和待检索数据已经编码成了embedding特征向量。
(2) 构建并训练索引
这个流程就是根据候选数据集库去构建和训练索引index，通俗的理解就是如何把海量数据集组织起来用于后续检索。不同的索引方式会影响检索效率和内存使用。Faiss支持多种索引，比如最简单的暴力检索Flat，还有多种近似查找方式ANN(Approximate Nearest Neighbor)等等，下面是Faiss支持的部分索引类型：
图1 faiss支持的部分索引类型
这里需要说明的是很多索引在被检索之前需要进行一个“训练”操作，这个操作就是根据特征的分布进行聚类训练，从而提升检索速度。
(3) 根据索引检索数据
索引构建和训练完成之后就可以用于检索数据了。
2.3 faiss索引类型介绍
faiss支持多种索引，不同类型的索引对于检索速度和内存使用情况影响很大。下面会从简单到复杂分别介绍几种重要的索引类型。
2.3.1 最简单粗暴的索引FLAT
Faiss中最简单的索引就是暴力检索Flat，根据计算相似度方法的不同可以分为indexFlatL2和indexFlatIP。indexFlatL2是基于欧式距离计算相似度，indexFlatIP则是基于内积计算相似度。这两种索引都属于暴力检索，比较简单，也不需要训练流程，因为不需要根据特征的分布进行聚类操作。
Flat索引的优点在于准确率最高，因为需要和候选数据集中的所有数据进行相似度计算，所以是真正的精确检索。而Falt索引的缺点也很明显，Flat索引会将全部的候选数据集加载到内存中进行保存，所以当候选数据集很大的时候会占用很大的内存，同时需要和候选数据集中所有的数据计算相似度，所以检索速度是最慢的。
2.3.2 使用内存更少的索引PQ
因为Flat索引会将全部的候选数据集加载到内存中进行保存，所以当候选数据集很大的时候会占用很大的内存。如何降低内存使用？这里就需要用到PQ(Product Quantizer)索引。下面我们通过NLP的一个实际业务来讲解PQ索引是如何降低内存使用的。之前讲过我们会根据用户搜索来匹配对应广告，比如用户搜索“传奇XX”，我们则会返回传奇游戏广告，这里就是基于语义相似度来完成。下面详细说明如何通过PQ索引来减少内存：
- 首先我们会将文本通过BERT模型编码成768维度的向量。假如有1亿条广告，向量是float类型，如果使用Flat索引那么我们的候选数据集库就变成了1亿X768维的向量矩阵，需要占用286G内存；
- 然后使用PQ索引则会将每个样本拆分成6个子矩阵，也就是768=128X6。这里子矩阵的个数可灵活设置，子矩阵个数越少，压缩越大，内存降低越多，准确率也会越低；
- 接着在每个子矩阵上进行聚类算法，设置k=256，则每个子矩阵上会得到256个质心。设置k为256的原因是每个子矩阵可以通过256个质心代表，而256个质心可以通过一个字节表示，2的8次方等于256；
- 最后通过PQ索引操作之后内存使用则大大降低，相当于原来需要286G=(1亿X768X4)/(1024X1024X1024),现在仅需要0.56G=(1亿X6X1)/(1024X1024X1024)，内存占用仅为原来的1/512。从单条样本占用内存的角度来看就是原来一条样本需要768X4字节，现在把一条样本拆分到6个子矩阵中，并且每个子矩阵通过1个字节来表示，就变成了6X1字节。
下面是通过PQ减少内存使用的说明图：
图2 PQ减少内存使用说明
和Flat索引相比，PQ索引则属于近似查找方法，因为每个样本相当于被压缩了，所以内存使用大大降低。但是也正因为样本被压缩了，所以计算相似度时准确率有一定下降。需要注意的是因为需要进行聚类操作，所以构建索引的时候需要进行训练。
2.3.3 检索速度更快的索引IVF
上面PQ索引通过压缩样本使得内存占用大大降低，主要用于降低内存占用，虽然可以一定程度上提升检索速度，但还是需要和候选数据集库中的全部数据进行相似度计算。一个可行的提升检索速度的方法是缩小检索范围，只和候选数据集库中的部分数据集进行相似度计算。就拿hive表来举例，当有一张表数据量级非常大的时候，我们可以把它做成分区表，这样检索数据的时候可以根据一定的“线索”只查询部分分区的数据就可以达到提升检索速度的效果了。通过这种方式可以将检索全量数据变成检索部分数据了，可以大大提升检索效率。这种方式就是倒排索引IVF(Inverted File System)的核心思路。不管是Flat还是PQ都需要和候选数据集库中的所有样本进行相似度计算，如果可以减少搜索量，那么检索速度则会快速提升。IVF索引就是将候选数据集库进行聚类操作划分成多个分区，当需要检索数据时只需要检索部分分区数据就可以了。
IVF索引核心是通过减少搜索数据量级从而提升检索速度，和PQ一样都只能返回近似准确的结果。假如把候选数据集划分成100个“分区”，我们设置搜索的区域为top10分区，当正确的结果在第11分区的时候就会导致我们无法检索到正确的结果。这也是IVF只能返回近似准确结果的原因。IVF是可以和PQ组合使用的，相当于压缩了样本，同时还减少了搜索范围，不仅减少了内存时候，还提升了检索速度，这就是我们经常使用的IndexIVFPQ索引。
2.3.4 基于图索引HNSW
除了PQ索引和IVF索引，实际业务中比较常用的还有基于图的HNSW(Hierarchcal Navigable Small World graphs)索引。这块后续我会专门写一篇文章详细介绍HNSW图检索算法。
2.4 各种索引优缺点对比
这里分享一张组里小伙伴总结的faiss实验结论：
图3 faiss实验结果图
实验设置候选数据集为100W，检索top50个词。下面分别从检索的准确率、搜索时间、索引是否需要训练和是否支持GPU来对比不同索引：
- 从检索结果的准确率来看，FlatL2和FlatIP效果是最好的，因为是真正的精确检索，相当于无损检索了全量候选数据集。接下来是HNSW和PQ，PQ索引也会检索全量候选数据集，但是对样本有压缩，所以准确率略微下降。然后是IVFPQ索引，因为使用了倒排索引，只会检索部分候选数据集，所以准确率进一步下降。最后是LSH基于敏感哈希映射的方式；
- 从搜索时间来看，FlatL2、FlatIP和PQ应该是最慢的，因为需要检索全部候选数据集。区别在于FlatL2和FlatIP中样本没有压缩，PQ对样本进行了压缩。接下来是LSH索引，搜索时间有一定提升。搜索最快的是HNSW索引和IVFPQ索引。IVFPQ因为使用倒排索引，大大减少了搜索的数据量级，所以搜索速度有很大提升。HNSW是基于图的检索方式，检索速度也很快；
- 从索引是否需要训练来看，因为PQ和IVF需要进行聚类操作，所以这两类索引需要进行训练，其他索引则不需要；
- 从索引是否支持GPU来看，Flat、PQ和IVF均支持GPU训练和检索，可以大大提升索引构建和检索速度。有点遗憾的是HNSW不支持GPU。
2.5 线上构建索引经验分享
上面也介绍了各种索引的优缺点，其实主要是检索准确率和检索速度之间的博弈。如果你需要最好的搜索准确率，候选数据集不是很大，并且实时性要求不高，那么Flat索引搜索结果是最好的；如果你需要很高的实时性，那么最好使用近似检索算法，IVF、HNSW等都行；如果你的内存比较小，那么PQ索引则可以大大减少内存使用。整体来看检索准确率和检索速度都比较好的是HNSW和IVFPQ索引，如果有GPU加持那么IVFPQ可能更好。我们线上也主要使用这两种索引。实际业务中具体使用哪种索引取决于你的应用场景，分别从内存使用、检索速度、检索准确率、是否支持GPU、是否支持增量数据等各个方面来考虑选择最合适的索引类型。只要了解了各种索引的原理，那么选择哪种类型的索引则简单了很多。
03
项目实践faiss
上面主要从理论的角度学习了faiss，这里给出一个非常简单faiss代码实践，帮助小伙伴入门，下面是基于faiss构建大规模检索任务的代码实例：
图4 基于faiss构建大规模检索任务的代码实例
针对实际业务场景，比如根据用户搜索召回对应广告，主要是利用simbert模型将文本根据语义相似度编码成768维度向量，然后就可以利用上述faiss代码构建索引并检索数据了。
04
总结及反思
本篇主要介绍实际广告搜索业务中经常使用的大规模检索利器Faiss。首先是背景介绍，主要讲了相似度匹配任务和大规模检索算法以及如何应用到我们的实际业务场景；然后重点介绍了faiss，包括什么是faiss、大规模检索任务流程、faiss索引类型介绍、各种索引优缺点对比以及线上构建索引经验分享；最后项目实践了faiss。希望对在海量高维向量空间进行大规模检索任务感兴趣的小伙伴有所帮助。
