学界 | 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 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

TF-IDF与余弦相似性的应用-自动提取关键词

TF-IDF与余弦相似性应用之自动提取关键词 引言 这个标题看上去好像很复杂,其实我要谈的是一个很简单的问题。有一篇很长的文章,要用计算机提取它的关键词(Aut...

35010
来自专栏新智元

【干货】怎样用深度学习做语音识别

【新智元导读】吴恩达曾经预测当语音识别的准确率从95%上升到99%时,语音识别将会成为人类与计算机交互的新方式。归功于深度学习,这4%的准确率的提升使得语音识别...

5258
来自专栏机器学习之旅

应用:推荐系统-威尔逊区间法

理论上讲,p越大应该越好,但是n的不同,导致p的可信性有差异。100个人投票,50个人投喜欢;10个人投票,6个人喜欢,我们不能说后者比前者要好。

874
来自专栏机器之心

前沿 | 将逆向课程生成用于强化学习:伯克利新研究让智能体掌握全新任务

35410
来自专栏人工智能LeadAI

伪标签半监督学习

之前在训练YoutubeNet和DCN的时候,我都发现平台用户中基础用户的信息数据缺失率特别高,比如性别一栏准确填写的不足60%,所以我一直想调研一下有没有什么...

822
来自专栏深度学习入门与实践

机器学习基础与实践(一)----数据清洗

本博客所有内容以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,并且是非商业用途,谢谢!   想写这个系列很久了,最近刚好项目结束了闲下来有点时间,...

2806
来自专栏张俊红

数学之美(一)

总第73篇 本篇为书籍《数学之美》的一部分读书笔记,分两篇来完成,只摘录了书中我个人认为重要的、典型的部分章节的部分内容分享出来,有兴趣的可以自己买来看看。 0...

2865
来自专栏大数据风控

评分卡模型开发-定量指标筛选

模型开发的前三步主要讲的是数据处理的方法,从第四步开始我们将逐步讲述模型开发的方法。在进行模型开发时,并非我们收集的每个指标都会用作模型开发,而是需要从收集的所...

2066
来自专栏人工智能LeadAI

推荐系统 | 威尔逊区间法

我推荐一种之前在惠普做过一种排序方法:威尔逊区间法 我们先做如下设定: (1)每个用户的打分都是独立事件。 (2)用户只有两个选择,要么投喜欢'1',要么投不喜...

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

如何通过评论、点赞等行为信息进行数据挖掘?

用户对产品有很多行为,如何进行用户行为分析来量化用户对产品的喜好程度呢? 比如豆瓣FM,用户可以点击“喜好”和"扔进垃圾箱"等;比如优酷视频,用户可以顶,踩,分...

3266

扫码关注云+社区