|
三月初，Facebook AI Research（FAIR）开源了一个名为 Faiss 的库，Faiss 主要用于有效的相似性搜索（Similarity Search）和稠密矢量聚类（Clustering of dense vectors），包含了在任何大小的矢量集合里进行搜索的算法。Faiss 上矢量集合的大小甚至可以大到装不进 RAM。这个库基本上是用 C++ 实现的，直播，带有可选的通过 CUDA 提供的 GPU 支持，以及一个可选的 Python 接口。 通过 Faiss 进行相似性搜索时，10 亿图像数据库上的一次查询仅耗时 17.7 微秒，速度较之前提升了 8.5 倍，且准确度也有所提升。 除图片检索外，相似性搜索还有更广阔的运用场景。例如，通过搜索数据库来判断某一罪行是否属于较严重的犯罪形式，或有重罪趋势；通过搜索和成功店铺所在地相似的人口特征和环境特征，来寻找零售商新店的最佳位置；通过相似城市的搜索，来衡量所在城市薪资水平是否合理等。 日前，Facebook 发布了一份关于 Faiss 原理的介绍，36氪对此进行了编译和整理，具体内容如下： 关于相似性搜索 传统的数据库由包含符号信息的结构化表格组成。举例来说，一个图片集合的呈现方式是一个列表，这个列表的每一行都有一张索引照片，同时包含图像标识、描述语句等信息。每一行的信息也可以连接其他表格，如一张包含人物的照片可以连接到姓名表上。 大部分 AI 工具都会生成高维矢量，如以 word2vec 为代表的文字嵌入工具，和用于深度学习训练的 CNN 描述符（Convolutional Neural Net）等。在这篇文章中，我们将阐述为什么高维矢量数据比固定符号数据更强大且灵活。不过，使用 SQL 查询的传统数据库并不适用这些新型表述方式：首先，海量的多媒体信息流创造了数十亿矢量；其次，更重要的一点是，找到类似的条目意味着要找到类似的高维矢量，这对标准的查询语言来说是极其低效甚至是不可能的。 如何应用矢量表述？ 让我们假设你现在有一张建筑的照片，这个建筑是某个中型城市的市政府，但你已经记不清名字了，然后你想在整个图片集合中找到这个建筑的其他所有照片。这种情况下使用传统的 SQL 语句来完成关键字查询是不可能的，因为你已经忘记了这个城市的名字。 相似性搜索此刻却能派上用场，图片的矢量描述是为了针对相似图片制造出相似的矢量，这些矢量被定义为临近欧几里得空间的向量。 矢量描述的另一个应用是分类。假设你需要一个分类器来判定一个图像集合中哪些图片代表的是小雏菊。分类器的训练是一个比较知名的过程：该算法会输入雏菊图像和非雏菊图像（如汽车、绵羊、玫瑰、向日葵等）。如果分类器是线性的，则会输出一个分类矢量， 所以，针对相似性搜索和分类，我们需要进行如下操作： 给定一个查询矢量，回到欧几里德空间中最接近这个矢量的数据库对象列表。 给定一个查询矢量，回到有最高向量点积德数据库对象列表。 有一个挑战是，我们希望这些操作可以以数十亿矢量的规模来运行。 软件包 目前投入应用的软件工具还不足以支持上述数据研究的进行。传统的 SQL 数据库系统不切实际，因为它们是针对 hash-based searches 或 1D interval searches 而优化的。相似性搜索功能在 OpenCV 这类工具包中受到的扩展性限制较大，一些针对“小”数据集（比如仅 100 万个矢量）的相似性搜索算法库也是如此。
Faiss 是一个打破了以上提到的所有限制的算法库，其优点有： Faiss 提供了多种相似性搜索方法，可以针对不同的使用方法，进行跨度较大的功能取舍。 Faiss 针对内存使用和速度进行了优化。 Faiss 为最相关的索引方法提供了先进的 GPU 实现方案。 评估相似性搜索一旦矢量被学习机器提取（从图像、视频、文档等），就可以被输入到相似性搜索库中。 我们拥有一个作为参考的暴力算法，能精确而详尽地计算出所有相似性，并且返回到最相似的元素列表中。这提供了一个“黄金标准”参考结果列表。但值得注意的是，高效实施暴力算法并不容易，并且暴力算法经常会影响到系统其他组件的效果。 如果我们愿意牺牲一部分精确度，相似性搜索的速度可以提高几个数量级，但是会偏离参考结果。例如，将图像相似性搜索的第一和第二个结果交换，可能没有什么太大影响，因为它们都是给定查询的正确结果。加速搜索涉及一些数据集合的预处理，我们将这项操作称之为“索引”。 这使我们确定了三个感兴趣的研究指标： 速度 在整个数据库中寻找 10 个（或其他数字）最相近的矢量需要花费多长时间？最好的情况是比暴力算法耗时短，否则索引就没有任何意义了。 内存用量 这个方法需要多少 RAM？比传统矢量多还是少？Faiss 仅支持在 RAM 搜索，因为磁盘数据库的数量级要慢一些，即使是 SSD。 准确度 (责任编辑：本港台直播) |
