学界 | Facebook AI实验室开源相似性搜索库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)开源,使大家能进行比较和重复利用。

概括的说,该论文的主要突破有:

  • 给出一个可在GPU上运行的k-selection算法。它可在快速寄存奇储器中运行,并且其灵活性能使它能与其他内核一起使用。对此我们给出了复杂性分析;
  • 在GPU上实现的为精确和近似的k最近邻搜索的近最优算法布局;
  • 通过一系列实验表明,在单一或多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 和/或点积向量比较的函数,以使该函数能够在向量集中进行搜索。有些索引类型是简单的基线,如精确搜索。大多数可用的索引结构都对应以下几点权衡:

  • 搜索时间
  • 搜索质量
  • 每个索引向量使用的内存大小
  • 训练时间
  • 无监督训练对外部数据的需求

获取Faiss 完整版文档

  • 完整文档(包括一个指南)可以参阅 GitHub 的 wiki 页: http://github.com/facebookresearch/faiss/wiki
  • doxygen 文档提供了每个类的信息:

http://rawgithub.com/facebookresearch/faiss/master/docs/html/annotated.html

  • 重现本研究论文的结果,可以参考基准 README

https://github.com/facebookresearch/faiss/blob/master/benchs/README.md

相似性搜索延伸阅读

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

相似性搜索的分类:

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

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

相似性搜索的工作原理:

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

相似性搜索的应用

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

  • 人力资源经理可能想要证明其公司薪资水平的合理性。找出在城市规模、生活成本和便利设施方面相似的城市后,她便可以查看这些城市的薪资水平,从而确定它们是否与本公司的薪资水平一致。
  • 犯罪分析师希望搜索数据库以查看某罪行是否属于较重犯罪形式或有重罪趋势。
  • 课外健身计划在 A 城极其成功。计划提倡者期望找到与其计划推广的候选城市具有相似特征的其他城市。
  • 执法机构用此方法揭露毒品种植地或生产地。标识具有相似特征的地方可能有助于制定未来的搜索目标。
  • 大型零售商不仅拥有数个成功店铺,也有少数业绩不佳的店铺。找到一些具有相似人口特征和环境特征(交通便利性、知名度以及商业互补性等等)的地方有助于标识新店的最佳位置。

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-03-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯移动品质中心TMQ的专栏

快给你的用例做减法吧

前言 生活的智慧,有时不在于多,而在于少。 同理适用于测试用例的管理中。 一. 热身:数一数你的用例数 随着互联网时代节奏的日益加快,许多产品都会在版本迭代中对...

18710
来自专栏月色的自留地

从锅炉工到AI专家(2)

1484
来自专栏鸿的学习笔记

八个方法干掉不平衡集

I have a binary classification problem and one class ispresent with 60:1 ratio i...

862
来自专栏python开发者

基于python语言的tensorflow的‘端到端’的字符型验证码识别源码整理(github源码分享)

基于python语言的tensorflow的‘端到端’的字符型验证码识别 1   Abstract 验证码(CAPTCHA)的诞生本身是为了自动区分 自然人 和...

3656
来自专栏机器之心

学界 | 一篇新的Capsule论文:优于基准CNN(ICLR 2018盲审中)

35315
来自专栏AI研习社

只需连接电脑摄像头,就能用深度学习进行实时对象检测

实时对象检测是一个非常有趣的话题。 我们应如何可靠地检测视频输入中的人和其他现实生活中的物体? 最近我设法构建了一个非常简单的应用程序,只需连接到用户的电脑网络...

702
来自专栏大数据挖掘DT机器学习

关联规则挖掘综述

本文介绍了关联规则挖掘的研究情况,提出了关联规则的分类方法,对一些典型算法进行了分析和评价,指出传统关联规则衡量标准的不足,归纳出关联规则的价值衡量方法,展望了...

3449
来自专栏ATYUN订阅号

【盘点】最适合AI开发的六种编程语言

? 自从AlphaGo战胜柯洁,AI风头就一直无人能及。而对于开发者来说,AI是一个十分广阔的领域,很多编程语言都可以利用AI进行开发。下面是整理出的几种典型...

29412
来自专栏深度学习之tensorflow实战篇

机器学习人群扩散(LPA算法) R实现

1、 业务场景说明: 2、 从业务映射到机器学习: 3、 友商应用资料: 4、 LPA方法原理:[1][3] 5、 特征过滤的解决方案:[4] 6、 R语言试验...

3927
来自专栏机器之心

深度 | 基于TensorFlow打造强化学习API:TensorForce是怎样炼成的?

选自reinforce.io 机器之心编译 作者:Michael Schaarschmidt、Alexander Kuhnle、Kai Fricke 参与:Pa...

4459

扫描关注云+社区