Facebook开源相似性搜索类库Faiss，超越已知最快算法8.5倍

Facebook 开源的开源库 Faiss(Facebook AI Similarity Search) 的项目，提供了一个相似性搜索的相似性搜类库，能够快速从多媒体文档中搜索出相似的索类算法条目。Facebook 人工智能实验室(FAIR)基于十亿级别的已知数据集构建了最近邻搜索算法的实现，这比已知的最快最快算法还快大约 8.5 倍，因此创造了新的开源库记录，包括第一个基于十亿高维向量构建的相似性搜 k 最近邻图。

Facebook 在今年 3 月份发布了 Facebook AI 相似性搜索(简称 Faiss)项目，索类算法该项目提供的已知类库可以从多媒体文档中快速搜索出相似的条目——这个场景下的挑战是基于查询的传统搜索引擎无法解决的。Facebook 人工智能实验室(FAIR)基于十亿级别的最快数据集构建了最近邻搜索算法的实现，这比之前介绍的开源库已知文献中在 GPU 上实现的最先进且最快的 k-selection 算法还要快大约 8.5 倍，因此创造了新的相似性搜记录，包括第一个基于十亿高维向量构建的网站模板索类算法 k 最近邻图。

关于相似性搜索

传统的已知数据库是由包含符号信息的结构化数据表组成。比如，最快一个图片集可以表示为一个数据表，每行代表一个被索引的图片，包含图片标识符和描述文字之类的信息;每一行也可以与其他数据表中的实体关联起来，比如某个用户的一张图片可以与用户姓名表建立关联。

像文本嵌入(word2vec)或者卷积神经网络(CNN)描述符这样通过深度学习训练出的 AI 工具，都可以生成高维向量。这种表示远比一个固定的符号表示更加强大和灵活，正如后文将解释的那样。然而使用 SQL 查询的传统数据库并不适用这些新的表示方式。首先，海量多媒体信息的涌入产生了数十亿的向量;其次，且更重要的是，查找相似实体意味着查找相似的高维向量，云南idc服务商如果只是使用标准查询语言这将非常低效和困难。

如何使用向量表示?

假设有一张建筑物的图片——比如某个你不记得名字的中等规模城市的市政大厅——然后你想在图片集中查找所有该建筑物的图片。由于不记得城市的名字，此时传统 SQL 中常用的 key/value 查询就帮不上忙了。

这就是相似性搜索的用武之地了。图片的向量化表示旨在为相似的图片生成相似向量，这里相似向量定义为欧氏距离最近的向量。

向量化表示的另一个应用是分类。假设需要一个分类器，来判定某个相册中的哪些图片属于菊花。分类器的训练过程众所周知：给算法分别输入菊花的图片和非菊花的图片(比如汽车、羊、玫瑰、矢车菊等);如果分类器是线性的亿华云，那么就输出一个分类向量，其属性值是它与图片向量的点积，反映了该图片包含菊花的可能性;然后分类器可以与相册中所有图片计算点积，并返回点积最大的图片。这种查询就是“最大内积”搜索。

所以，对于相似性搜索和分类，我们需要做下列处理：

给定一个查询向量，返回与该向量的欧式距离最近的数据库对象列表。 给定一个查询向量，返回与该向量点积最大的数据库对象列表。

一个额外的挑战是，要在一个超大规模比如数十亿向量上做这些运算。

软件包

现有软件工具都不足以完成上述数据库检索操作。传统的 SQL 数据库系统也不太适合，因为它们是为基于哈希的检索或 1 维区间检索而优化的;像 OpenCV 等软件包中的相似性搜索功能在扩展性方面则严重受限;同时其他的相似性搜索类库主要适用于小规模数据集(比如，1 百万大小的向量);另外的软件包基本是为发表论文而输出的学术研究产物，旨在展示某些特定设置下的效果。

Faiss 类库则解决了以上提到的种种局限，其优点如下：

提供了多种相似性搜索方法，支持各种各样的不同用法和功能集。 特别优化了内存使用和速度。 为最相关索引方法提供了最先进的 GPU 实现。

相似性搜索评估

一旦从学习系统(从图片、视频、文本文件以及其他地方)抽取出向量，就能准备将其用于相似性搜索类库。

我们有一个暴力算法作为参考对比，该算法计算出了所有的相似度——非常精确和齐全——然后返回最相似的元素列表。这就提供了一个黄金标准的参考结果列表。需要注意的是，暴力算法的高效实现并不简单，一般依赖于其他组件的性能。

如果牺牲一些精度的话，比如允许与参考结果有一点点偏差，那么相似性搜索能快几个数量级。举个例子，如果一张图片的相似性搜索结果中的第一个和第二个交换了，可能并没有太大问题，因为对于一个给定的查询，它们可能都是正确结果。加快搜索速度还涉及到数据集的预处理，我们通常把这个预处理操作称作索引。

这样一来我们就关注到下面三个指标：

速度。找到与查询最相似的 10 个或更多个向量要耗时多久?期望比暴力算法耗时更少，不然索引的意义何在?

内存消耗。该方法需要消耗多少 RAM?比原始向量更多还是更少?Faiss 支持只在 RAM 上搜索，而磁盘数据库就会慢几个数量级，即便是 SSD 也是一样。

精确度。返回的结果列表与暴力搜索结果匹配程度如何?精确度可以这样评估，计算返回的真正最近邻结果在查询结果第一位(这个指标一般叫做 1-recall@1)的数量，或者衡量返回结果前 10 个(即指标 10-intersection)中包含 10 个最近邻结果的平均占比。

通常我们都会在确定的内存资源下在速度和精准度之间权衡。Faiss 专注于压缩原始向量的方法，因为这是扩展到数十亿向量数据集的不二之选：当必须索引十亿个向量的时候，每个向量 32 字节，就会消耗很大的内存。

许多索引类库适用于百万左右向量的小规模数据集，比如 nmslib 就包含了一些适于这种规模数据的非常高效的算法，这比 Faiss 快很多，但需要消耗更多的存储。

基于 10 亿向量的评估

由于工程界并没有针对这种大小数据集的公认基准，所以我们就基于研究结果来评估。

评估精度基于 Deep1B，这是一个包含 10 亿图片的数据集。每张图片已通过 CNN 处理，CNN 激活图之一用于图片描述。比较这些向量之间的欧氏距离，就能量化图片的相似程度。

Deep1B 还带有一个较小的查询图片集，以及由暴力算法产生的真实相似性搜索结果。因此，如果运行一个搜索算法，就能评估结果中的 1-recall@1。

选择索引

为了评估，我们把内存限制在 30G 以内。这个内存约束是我们选择索引方法和参数的依据。Faiss 中的索引方法表示为一个字符串，在本例中叫做 OPQ20_80,IMI2x14,PQ20。

该字符串包含的信息有，作用到向量上的预处理步骤(OPQ20_80)，一个选择机制(IMI2x14)表明数据库如何分区，以及一个编码组件(PQ20)表示向量编码时使用一个产品量化器(PQ)来生成一个 20 字节的编码。所以在内存使用上，包括其他开销，累计少于 30G。

这听起来技术性较强，所以 Faiss 文档提供了使用指南，来说明如何选择满足需求的最佳索引。

选好了索引类型，就可以开始执行索引过程了。Faiss 中的算法实现会处理 10 亿向量并把它们置于一个索引库中。索引会存在磁盘上或立即使用，检索和增加 / 移除索引的操作可以穿插进行。

查询索引

当索引准备好以后，一系列搜索时间参数就会被设置来调整算法。为方便评估，这里使用单线程搜索。由于内存消耗是受限并固定的，所以需要在精确度和搜索时间之间权衡优化。举例说来，这表示为了获取 40% 的 1-recall@1，可以设置参数以花费尽可能短的搜索时间。

幸运的是，Faiss 带有一个自动调优机制，能扫描参数空间并收集提供最佳操作点的参数;也就是说，最可能的搜索时间对应某个精确度，反之亦然，最优的精确度对应某个搜索时间。Deep1B 中操作点被可视化为如下图示：

本图中我们可以看到，达到 40% 的 1-recall@1，要求每次查询耗时必须小于 2ms，或者能优化到耗时 0.5ms 的话，就可以达到 30% 的 1-recall@1。一次查询耗时 2ms 表示单核 500 QPS 的处理能力。

这个结果基本上能媲美目前业内最新研究成果了，即 Babenko 和 Lempitsky 在 CVPR 2016 发表的论文“Efficient Indexing of Billion-Scale Datasets of Deep Descriptors”，这篇论文介绍了 Deep1B 数据集，他们达到 45% 的 1-recall@1 需要耗时 20ms。

10 亿级数据集的 GPU

计算GPU 实现方面也做了很大的投入，在原生多 GPU 的支持下能产出惊人的单机性能。GPU 实现已经可以作为对应 CPU 设备的替代，无需了解 CUDA API 就能挖掘出 GPU 的性能。Faiss 支持所有 Nvidia 2012 之后发布的 GPU(Kepler，计算能力 3.5+)。

我们把 roofline model 作为指南，它指出应当尽量让内存带宽或浮点运算单元满载。Faiss 的 GPU 实现在单 GPU 上的性能要比对应的 CPU 实现快 5 到 10 倍，像英伟达 P100 这样的新型 Pascal 架构硬件甚至会快 20 倍以上。

一些性能关键数字：

对于近似的索引，使用 YFCC100M 数据集中的 9500 万张图片，一个基于 128D CNN 描述符的暴力 k 近邻图(k=10)，只需 4 个 Maxwell Titan X GPU 就能在 35 分钟内构建完成，包括索引构建时间。 十亿级向量的 k 近邻图现在触手可及。基于 Deep1B 数据集，可以构建一个暴力 k-NN 图(k=10)，达到 0.65 的 10-intersection，需要使用 4 个 Maxwell Titan X GPU 花费不到 12 小时，或者达到 0.8，使用 8 个 Pascal P100-PCIe GPU 消耗不到 12 小时。Titan X 配置可以在不到 5 小时生成低质量的图。 其他组件也表现出了骄人的性能。比如，构建上述 Deep1B 索引需要使用 k 均值聚类 6701 万个 120 维的向量到 262,144 个簇，对于 25 E-M 迭代需要在 4 个 Titan X GPU(12.6 tflop/s)上花 139 分钟，或者在 8 个 P100 GPU(40 tflop/s)上花 43.8 分钟。注意聚类的训练数据集并不需要放在 GPU 内存中，因为数据可以在需要时流到 GPU 而没有额外的性能影响。

底层实现

Facebook AI 研究团队 2015 年就开始开发 Faiss，这建立在许多研究成果和大量工程实践的基础之上。对于 Faiss 类库，我们选择聚焦在一些基础技术方面的优化，特别是在 CPU 方面，我们重度使用了：

采用多线程来利用多核资源，并在多个 GPU 上执行并行检索。 使用 BLAS 类库通过矩阵和矩阵乘法来高效精准地完成距离计算。一个不采用 BLAS 的暴力实现很难达到最优。BLAS/LAPACK 是 Faiss 唯一强制依赖的软件。 采用机器 SIMD 向量化和 popcount 加速独立向量的距离计算。

关于 GPU

对于前述相似性搜索的 GPU 实现，k-selection(查找 k 个最小或最大元素)有一个性能问题，因为传统 CPU 算法(比如堆查找算法)对 GPU 并不友好。针对 Faiss GPU，我们设计了文献中已知的最快轻量 k-selection 算法(k<=1024)。所有的中间状态全部保存在寄存器，方便高速读写。可以对输入数据一次性完成 k-select，运行至高达 55% 的理论峰值性能，作为输出的峰值 GPU 内存带宽。因为其状态单独保存在寄存器文件中，所以与其他内核很容易集成，使它成为极速的精准和近似检索算法。

大量的精力投在了为高效策略做铺垫，以及近似搜索的内核实现。通过数据分片或数据副本可以提供对多核 GPU 支持，而不会受限于单 GPU 的可用显存大小;还提供了对半精度浮点数的支持(float16)，可在支持的 GPU 上做完整 float16 运算，以及早期架构上提供的中间 float16 存储。我们发现以 float16 编码向量技术可以做到精度无损加速。

简而言之，对关键因素的不断突破在实践中非常重要，Faiss 确实在工程细节方面下了很大的功夫。

开始使用 Faiss

Faiss 使用 C++ 实现，并支持 Python。只要从 Github 下载源码并编译，然后在 Python 中导入 Faiss 模块即可开始使用。Faiss 还完整集成了 Numpy，并支持构造 numpy(使用 float32)数组的所有函数。

获取 Faiss:

https://github.com/facebookresearch/faiss

索引对象Faiss(包括 C++ 和 Python)提供了索引 Index 的实例。每个 Index 子类实现一个索引结构，以说明哪些向量可被加入和搜索。比如，IndexFlatL2 是一个能使用 L2 距离搜索的暴力索引。

这样会打印出索引向量的数量。增加到一个 IndexFlat 仅仅表示拷贝它们到索引的内部存储，因为后面没有其他操作会作用在该向量上。

执行一次搜索：

I 是一个整型矩阵，输出后是这样的：

对于 xq 的第一个向量，xb 中最相似向量的索引是 0(从 0 开始)，第二相似的是 #393，第三是 #363。对于 xq 的第二个向量，相似向量列表是 #1， #555 等等。本例中，xq 的前三个向量看起来与 xb 的前三个向量一样。

矩阵 D 是一个平方距离矩阵，与 I 的大小一致，表示对于每个结果向量查询的平方欧氏距离。

Faiss 实现了十多个由其他索引组合的索引类型。可选的 GPU 版本有完全相同的接口，并有通道在 CPU 和 CPU 索引之间互通。Python 接口主要由 C++ 生成以凸显 C++ 索引，所以可以很容易地将 Python 验证代码转换为集成的 C++ 代码。