Facebook的开源Faiss（FacebookAISimilaritySearch）项目提供了一个相似度搜索库，可以从多媒体文档中快速搜索相似的项目。Facebook人工智能实验室(FAIR)构建了基于十亿规模数据集的最近邻搜索算法的实现，比已知最快的算法快约8.5倍，从而创造了新的记录，其中包括第一个基于K-最近邻的算法由数十亿个高维向量构建的图。Facebook于今年3月发布了FacebookAISimilaritySearch（简称Faiss）项目。本项目提供的类库可以从多媒体文档中快速搜索相似的项目——这个场景的挑战是传统的基于查询的搜索引擎无法修复。Facebook人工智能实验室（FAIR）构建了一个基于十亿级数据集的最近邻搜索算法的实现，比之前介绍的已知文献中在GPU上实现的最先进最快的k-selection算法快了约8.5倍，从而创造了新的记录，包括第一个由十亿个高维向量构建的k最近邻图。关于相似性搜索传统数据库由包含符号信息的结构化数据表组成。例如，一个图像集可以表示为一个数据表，每一行代表一个索引图像，包括图像标识符和描述文本等信息；每行还可以与其他数据表中的实体相关联，例如用户的照片可以与用户名表相关联。经过深度学习训练的AI工具，例如文本嵌入(word2vec)或卷积神经网络(CNN)描述符，可以生成高维向量。这种表示比固定的符号表示更强大、更灵活，稍后将对此进行解释。然而，使用SQL查询的传统数据库不适合这些新的表示形式。首先，海量多媒体信息的涌入产生了数十亿个向量；其次，更重要的是，找到相似的实体意味着找到相似的高维向量，如果只使用标准的查询语言，这将是非常低效和困难的。你如何使用矢量表示？假设您有一张建筑物的照片——比如某个您不记得名字的中等城市的市政厅——并且您想要在图像集中找到该建筑物的所有照片。由于记不住城市名，传统SQL常用的key/value查询这时候就帮不上忙了。这就是SimilaritySearch的用武之地。图片的向量化表示旨在为相似的图片生成相似的向量，其中相似的向量被定义为欧几里得距离最近的向量。矢量化表示的另一个应用是分类。假设您需要一个分类器来确定某个相册中的哪些图片属于菊花。分类器的训练过程众所周知：算法输入菊花图片和非菊花图片（如汽车、羊、玫瑰、矢车菊等）；如果分类器是线性的，则输出一个分类向量，其属性值为它与图像向量的点积，反映图像包含菊花的可能性；然后分类器可以计算相册中所有图像的点积，并返回具有最大点积的图像。此查询是“最大内积”搜索。因此，对于相似性搜索和分类，我们需要执行以下操作：给定一个查询向量，返回最接近该向量欧氏距离的数据库对象列表。给定一个查询向量，返回与该向量具有最大点积的数据库对象列表。另一个挑战是在非常大规模（例如数十亿个向量）上执行这些操作。软件包中现有的软件工具均不足以执行上述数据库检索操作。传统的SQL数据库系统也不太适合，因为它们针对基于哈希的检索或一维范围检索进行了优化；OpenCV等软件包中的相似性搜索功能在可扩展性方面受到严重限制；而其他的相似度搜索类库主要适用于小规模数据集（比如100万个向量大小）；其他包基本都是发表论文的学术研究输出，旨在展示一些特定设置的效果。Faiss类库解决了上述的局限性，其优点如下：提供多种相似度搜索方式，支持多种不同的用法和功能集。特别针对内存使用和速度进行了优化。为最相关的索引方法提供了最先进的GPU实现。相似性搜索评估一旦从学习系统（从图像、视频、文本文件和其他地方）中提取了向量，它们就可以在相似性搜索类库中使用了。我们有一个蛮力算法作为计算所有相似性的参考-非常精确和完整-并返回最相似元素的列表。这提供了参考结果的黄金标准列表。需要注意的是，暴力算法的高效实现并不简单，一般取决于其他组件的性能。如果牺牲一些精度，例如允许与参考结果有小的偏差，相似性搜索可以快几个数量级。例如，如果交换图像的第一个和第二个相似性结果，这可能没什么大不了的，因为它们可能都是给定查询的正确结果。加快搜索速度还涉及到数据集的预处理。我们通常将这种预处理操作称为索引。这样，我们重点关注以下三个指标：速度。找到与查询最相似的10个或更多向量需要多长时间？期望比蛮力算法更少的时间，否则索引有什么意义？内存消耗。此方法消耗多少RAM？比原始向量多还是少？Faiss仅支持在RAM上搜索，而磁盘数据库会慢几个数量级，即使使用SSD。准确性。返回的结果列表与暴力搜索结果的匹配度如何？可以通过计算查询结果第一个位置返回的真实最近邻结果的个数来评价准确率（这个指标一般称为1-recall@1），或者衡量返回结果在10之前的个数（即索引10-交集）)包含10个最近邻结果的平均比例。通常我们会在一定的内存资源下，在速度和准确率之间进行权衡。Faiss专注于压缩原始向量的方法，因为这是扩展到十亿向量数据集的明显选择：每个向量32字节，当必须索引十亿向量时会消耗大量内存。许多索引库适用于具有数百万向量的小规模数据集。例如，nmslib包含一些针对这种数据规模的非常有效的算法。它比Faiss快得多，但消耗更多存储空间。对10亿个向量的评估由于工程界没有针对这种规模的数据集的公认基准，因此我们的评估基于研究结果。估计精度基于Deep1B，这是一个包含10亿张图像的数据集。每张图像都经过CNN处理，其中一个CNN激活图用于图像描述。通过比较这些向量之间的欧氏距离，可以量化图片的相似度。Deep1B还附带了一组较小的查询图像，以及由蛮力算法产生的逼真的相似性搜索结果。因此，如果您运行搜索算法，则可以在结果中评估1-recall@1。选择Index进行评估，我们将内存限制为30G。这种内存约束是我们选择索引方式和参数的基础。Faiss中的索引方法表示为字符串，在本例中称为OPQ20_80,IMI2x14,PQ20。该字符串包含有关应用于向量(OPQ20_80)的预处理步骤的信息、指示数据库应如何分区的选择机制(IMI2x14)以及指示在以下情况下使用乘积量化器(PQ)的编码组件(PQ20)对向量进行编码以生成20字节的编码。因此，在内存使用上，包括其他开销，累计不到30G。这听起来很技术性，因此Faiss文档提供了有关如何选择最适合您需要的索引的使用指南。一旦选择了索引类型，索引过程就可以开始了。Faiss中的算法实现采用10亿个向量并将它们放入索引库中。索引可以存储在磁盘上或立即使用，并且可以穿插检索和添加/删除索引的操作。查询索引当索引准备就绪时，会设置一些搜索时间参数来调整算法。为了便于评估，这里使用单线程搜索。由于内存消耗是有界且固定的，因此需要在准确性和优化搜索时间之间进行权衡。这意味着，例如，为了获得40%的1-recall@1，可以将参数设置为花费尽可能少的搜索时间。幸运的是，Faiss自带了一个自动调整机制，可以扫描参数空间并收集提供最佳运行点的参数；即对于某个精度最可能的搜索时间，反之，最优精度度对应某个搜索时间。Deep1B中的操作点可视化如下图所示：这张图中我们可以看到，要达到40%的1-recall@1，要求每次查询时间小于2ms，或者如果可以优化到0.5ms，则可以实现30%的1-recall@1。一次查询耗时2ms代表单核500QPS的处理能力。这个结果基本可以媲美业界最新的研究成果，即Babenko和Lempitsky在CVPR2016发表的论文《EfficientIndexingofBillion-ScaleDatasetsofDeepDescriptors》。该论文介绍了Deep1B数据集，达到45%。1-recall@1需要20ms。在10亿级数据集的GPU计算GPU实现方面进行了大量投入，在原生多GPU的支持下，可以产生惊人的单机性能。GPU实现已经可以作为相应CPU设备的替代品，在不了解CUDAAPI的情况下也可以挖掘GPU的性能。Faiss支持Nvidia2012之后发布的所有GPU（Kepler，计算能力3.5+）。我们使用roofline模型作为指南，它指出您应该尝试最大化内存带宽或浮点单元。Faiss的GPU实现在单个GPU上的执行速度比CPU快5到10倍，而更新的Pascal架构硬件（如NvidiaP100）甚至可以快20倍以上。一些性能关键数据：对于近似索引，使用YFCC100M数据集中的9500万张图像，基于128DCNN描述符的强力k最近邻图(k=10)可以在35分钟内仅在4个MaxwellTitanXGPU上运行内部构建完成，包括索引构建时间。数十亿个向量的k最近邻图现在触手可及。基于Deep1B数据集，可以构建暴力k-NN图（k=10），实现10-交集0.65，使用4个MaxwellTitanXGPU耗时不到12小时，使用8个PascalP100-0.8PCIeGPU消耗不到12小时。TitanX配置可以在不到5小时内生成低质量的绘图。其他组件也表现出令人印象深刻的性能。例如，构建上述Deep1B索引需要使用k-means将6701万个1.20维向量聚类为262,144个簇，这在4个TitanXGPU（12.6tflop/s）上需要139分钟进行25次E-M迭代，或者在8个It上需要139分钟在P100GPU（40tflop/s）上耗时43.8分钟。请注意，集群训练数据集不需要位于GPU内存中，因为数据可以在需要时流式传输到GPU，而不会产生额外的性能影响。底层实现FacebookAI研究团队在2015年开始开发Faiss，基于大量的研究成果和大量的工程实践。对于Faiss类库，我们选择专注于一些基础性的技术优化，尤其是在CPU方面，我们大量使用：多线程以利用多核资源并在多个GPU上执行并行检索。使用BLAS类库，通过矩阵和矩阵乘法，高效准确地进行距离计算。不使用BLAS的蛮力实现几乎不是最佳的。BLAS/LAPACK是Faiss唯一强制依赖的软件。使用机器SIMD向量化和popcount加速独立向量的距离计算。关于GPU对于上述相似性搜索的GPU实现，k-selection（找到k个最小或最大的元素）存在性能问题，因为传统的CPU算法（如堆搜索算法）对GPU并不友好。对于FaissGPU，我们设计了文献中已知的最快的轻量级k-选择算法(k<=1024)。所有中间状态都存储在寄存器中，便于高速读写。k-select可以一次性完成输入数据，运行高达理论峰值性能的55%作为输出峰值GPU内存带宽。由于其状态单独保存在寄存器文件中，因此很容易与其他核集成，使其成为一种极快的精确和近似检索算法。大量的精力投入在为高效策略和近似搜索的内核实现做铺垫。可以通过数据分片或数据复制的方式提供对多核GPU的支持，不受单个GPU可用内存大小的限制；还提供了对半精度浮点数(float16)的支持，并且可以在支持的GPU操作上完成完整的float16，并在早期架构上提供中间float16存储。我们发现可以在不损失精度的情况下加速使用float16编码向量的技术。总之，关键因素的不断突破在实践中非常重要，Faiss在工程细节上确实下了不少功夫。开始使用以C++实现并支持Python的FaissFaiss。只需从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++代码。
