FB开源相似性搜索库Faiss：性能高于理论峰值55%，提速8.5倍

　　在用户日常搜索过程中，一个经常出现的问题即大多数返回的网站结果拥有完全相同或者几乎一样的信息。而应用了相似性搜索的相似引擎即可为用户返回最恰当、最合适的结果，同时隐藏或者丢弃那些重复的数据。

　　但是，目前相似性搜索领域需要克服的难题即它的规模和运行速度。雷锋网近日了解到，Facebook 的人工智能研究团队就称已在该问题上取得了重要进展。Facebook 在新发布的论文《Billion-scale similarity search with GPUs》中表示，可在 GPU 上实现十亿规模级的相似性搜索，并且已开源该方法。

　　在处理图像或视频等复杂数据时会涉及专用数据库系统，而相似性搜索（similarity search）则可以在专用数据库系统中找寻应用。但问题是，这些复杂数据通常用高维特征表示，而且需要特定的索引结构。

　　因此，Facebook 的研究人员就通过更好地利用 GPU 的优势解决了这个问题 。尽管 GPU 擅长数据并行任务，但之前的方法要么会在并行性不高的算法（如 k-min selection）上遭遇瓶颈，要么不能有效利用内存的层次结构。

　　为此雷锋网了解到，他们提出一种可用于k-selection 的新设计，使其能以高达性能理论峰值 55% 的速度进行运算，并实现了比之前最佳的 GPU 方法快 8.5 倍的最近邻搜索。他们为以积量化（product quantization）为基础的暴力计算、近似和压缩域搜索提出优化设计，从而将其应用到不同的相似性搜索场景中。在所有这些场景中，该方法比之前的方法的最佳表现还要好，它可在 35 分钟内从 Yfcc100M 数据集的 9500 万张图像上构建一个高准确度的 k-NN 图，也可以在 12 个小时内在 4 个 Maxwell Titan X GPU 上构建一个连接了 10 亿个向量的图。

　　现在 Facebook 已将该方法（Faiss）开源，使大家能进行比较和重复利用。

　　概括的说，该论文的主要突破有：

1. 给出一个可在 GPU 上运行的k-selection 算法。它可在快速寄存奇储器中运行，并且其灵活性能使它能与其他内核一起使用。对此我们给出了复杂性分析；

2. 在 GPU 上实现的为精确和近似的k最近邻搜索的近最优算法布局;

3. 通过一系列实验表明，在单一或多 GPU 配置中运行的中到大规模的最近邻搜索任务上，我们的方法大幅度优于先前技术。

图片选自论文（图片6）：从 Yfcc100M 数据集的 9500 万张图像上构建的高准确度 k-NN 图。第一张和最后一张图片为给定图片，算法通过计算得出两张图片之间最“和谐”的演变路径。

　　开源库 Faiss 简介

　　Faiss 是用于有效的相似性搜索（similarity search）和稠密矢量聚类（clustering of dense vectors）的库。它包含了可在任何大小向量集合里进行搜索的算法，向量集合的大小甚至可达到 RAM 容纳不下的地步。另外，它还包含了用于评估和参数调优的支持代码。Faiss 用 C ++ 编写，有 Python / numpy 的完整包装。其中最有用的一些算法则在 GPU 上实现。

　　Faiss 包含几种相似性搜索的方法。它假定示例可以被表示为向量，并可以通过整数识别。除此之外，这些向量可以与 L2 位距或点积进行比较。与一个查询向量（query vector）相似的向量是具有最低 L2 位距或最高点积的查询向量。Faiss 还支持余弦相似性（cosine similarity），因为它属于标准化向量上的点积。

　　大多数方法，例如基于二元向量和紧凑量化代码的方法，仅使用向量的压缩表征，并不需要保留原始向量。这通常会降低搜索的准确性，但这些方法可在单个服务器上的主存储器中扩展到数十亿个向量。

　　该 GPU 实现可接受来自 CPU 或 GPU 内存的输入。在一个带有 GPU 的服务器上，其 GPU 索引可以被用作其 CPU 索引的插入替换（比如用 GpuIndexFlatL2 替代 IndexFlatL2），而且来自或发往 GPU 内存的副本可以被自动处理。

　　Faiss 的构建

　　该库基本上通过 C++ 实现。它带有可选择的 GPU （该 GPU 通过 CUDA 支持）以及一个可选的 Python 接口。编译采用的是 Makefile。详细信息可参见 INSTALL：

　　https://github.com/facebookresearch/faiss/blob/master/INSTALL

　　Faiss 的工作原理

　　Faiss 是围绕存储一个向量集的索引类型（index type）构建的，并且索引类型提供了一个利用 L2 和/或点积向量比较的函数，以使该函数能够在向量集中进行搜索。有些索引类型是简单的基线，如精确搜索。大多数可用的索引结构都对应以下几点权衡：

1. 搜索时间

2. 搜索质量

3. 每个索引向量使用的内存大小

4. 训练时间

5. 无监督训练对外部数据的需求

　　获取 Faiss 完整版文档

• 完整文档（包括一个指南）可以参阅 GitHub 的 wiki 页：http://github.com/facebookresearch/faiss/wiki

• doxygen 文档提供了每个类的信息：http://rawgithub.com/facebookresearch/faiss/master/docs/html/annotated.html

• 重现本研究论文的结果，可以参考基准 READMEhttps://github.com/facebookresearch/faiss/blob/master/benchs/README.md

　　相似性搜索延伸阅读

　　对相似性搜索不甚了解的同学，可以参看以下由雷锋网整理的相似性搜索的延伸阅读。

　　相似性搜索的分类：

　　最邻近搜索（nearest neighbor search）和范围查询（range queries）是相似搜索的重要子分类，研究人员已针对这两种分类开发出多种解决方案。

　　相似性搜索中存在的问题也是搜索复杂对象时的固有问题。复杂对象会导致大多数技术对大范围集合的抓取能力等问题。而在相似性搜索时，大部分情况下对象都是复杂的。

　　相似性搜索的工作原理：

　　相似性搜索工具可用于识别哪些候选要素与要匹配的一个或多个输入要素最相似（或最相异）。相似性的基础是数值属性（感兴趣属性）的指定列表。如果指定了一个以上的要匹配的输入要素，相似性将基于每个感兴趣属性的平均值。输出要素类（输出要素）将包含要匹配的输入要素以及找到的所有匹配的候选要素，这些要素以相似程度排序（由最相似或最不相似参数指定）。返回的匹配数基于结果数参数的值。

　　相似性搜索的应用

　　相似性搜索在很多场景下都可以发挥它的优势，比如：

• 人力资源经理可能想要证明其公司薪资水平的合理性。找出在城市规模、生活成本和便利设施方面相似的城市后，她便可以查看这些城市的薪资水平，从而确定它们是否与本公司的薪资水平一致。

• 犯罪分析师希望搜索数据库以查看某罪行是否属于较重犯罪形式或有重罪趋势。

• 课外健身计划在 A 城极其成功。计划提倡者期望找到与其计划推广的候选城市具有相似特征的其他城市。

• 执法机构用此方法揭露毒品种植地或生产地。标识具有相似特征的地方可能有助于制定未来的搜索目标。

• 大型零售商不仅拥有数个成功店铺，也有少数业绩不佳的店铺。找到一些具有相似人口特征和环境特征（交通便利性、知名度以及商业互补性等等）的地方有助于标识新店的最佳位置。

　　来源：Facebook 研究院，雷锋网编译。