相似性搜索(similarity-search)是给定一个查询，目标是在所有数据库文档中找到与其最相似的文档。本章介绍 kNN 的相似性搜索及其使用倒排文件的加速。

介绍

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。通常，文档或项目以文本或图像的形式表示。然而，机器学习算法不能直接处理原始文本或图像，这就是为什么文档和项目通常被预处理并存储为数字向量的原因。

有时向量的每个分量都可以存储语义。在这种情况下，这些表示也称为嵌入。这样的嵌入可以有数百个维度，数量可以达到数百万个！由于数量如此庞大，任何信息检索系统都必须能够快速检测相关文档。

在机器学习中，向量也称为对象或点。

指数

为了加速搜索性能，在数据集嵌入之上构建了特殊的数据结构。这样的数据结构称为索引。该领域已经进行了大量的研究，并演化出了多种类型的指标。在选择索引来应用特定任务之前，有必要了解它的幕后运作方式，因为每个索引都有不同的目的，并且都有自己的优点和缺点。

在本文中，我们将看看最简单的方法:kNN。基于 kNN，我们将切换到倒排文件:一种用于更具可扩展性的搜索的索引，可以将搜索过程加速数倍。

kNN

kNN是最简单、最朴素的相似性搜索算法。考虑向量数据集和新的查询向量Q。我们希望找到与Q最相似的前k 个数据集向量。首先要考虑的方面是如何测量两个向量之间的相似性（距离）。事实上，有几个相似性指标可以做到这一点。其中一些如下图所示。

img

相似度指标

训练

kNN 是机器学习中少数不需要训练阶段的算法之一。选择合适的指标后，我们可以直接进行预测。

推理

对于一个新对象，该算法会详尽地计算到所有其他对象的距离。之后，它找到距离最小的k个对象并将它们作为响应返回。

img

kNN工作流程

显然，通过检查到所有数据集向量的距离，kNN 保证了 100% 准确的结果。然而，这种蛮力方法在时间性能方面非常低效。如果数据集由m个维度的n个向量组成，则对于每个n个向量，需要O(m)时间来计算从查询Q到它的距离，这导致总时间复杂度为O(mn)。正如我们稍后将看到的，存在更有效的方法。

而且，原始向量没有压缩机制。想象一个包含数十亿个对象的数据集。将它们全部存储在 RAM 中是不可能的！

img

kNN 性能。具有 100% 的准确度且无需训练阶段，可在向量的推理和无内存压缩期间进行详尽的搜索。注：此类图显示了不同算法的相对比较。根据情况和选择的超参数，性能可能会有所不同。

应用

kNN 的应用范围有限，仅应在以下场景之一使用：

  • 数据集大小或嵌入维数相对较小。这方面确保了算法仍然能够快速执行。
  • 算法要求的准确度必须是100%。在准确性方面，没有其他最近邻算法可以超越 kNN。

根据指纹检测人员就是需要 100% 准确度的问题的一个例子。如果此人犯罪并留下了指纹，则仅检索正确的结果至关重要。否则，如果系统不是 100% 可靠，那么另一个人可能会被判有罪，这是一个非常严重的错误。

基本上，改进 kNN 的方法主要有两种（我们稍后会讨论）：

  • 缩小搜索范围。
  • 降低向量的维数。

当使用这两种方法之一时，我们将不会再次执行详尽的搜索。此类算法称为**近似最近邻 (ANN)，**因为它们不能保证 100% 准确的结果。

倒排文件索引

“倒排索引（也称为倒排列表postings list/file、倒排文件inverted file）是一种数据库索引，存储从内容（例如单词或数字）到其在表、文档或一组数据中的位置的映射”——维基百科

执行查询时，会计算查询的哈希函数并从哈希表中获取映射值。这些映射值中的每一个都包含其自己的一组潜在候选值，然后根据条件对其进行全面检查，使其成为查询的最近邻居。通过这样做，缩小了所有数据库向量的搜索范围。

img

倒排文件索引工作流程

根据哈希函数的计算方式，该索引有不同的实现方式。我们将要看到的实现是使用Voronoi 图（或Dirichlet tessellation）的实现。

训练

该算法的思想是创建每个数据集点所属的几个不相交的区域。每个区域都有自己的质心，指向该区域的中心。

有时Voronoi 区域被称为单元或分区。

img

Voronoi 图的示例。白点是包含一组候选的各个分区的中心。

Voronoi 图的主要属性是从一个质心到其区域内任意点的距离小于从该点到另一个质心的距离。

推理

当给定一个新对象时，将计算到所有 Voronoi 分区质心的距离。然后选择距离最小的质心，并将该分区中包含的向量作为候选向量。

img

通过给定的查询，我们搜索最近的质心（位于绿色区域）

最终，通过计算到候选者的距离并选择其中最接近的前k个，返回最终答案。

img

查找所选区域中的最近邻居

正如您所看到的，这种方法比前一种方法快得多，因为我们不必查看所有数据集向量。

边缘问题

随着搜索速度的提高，倒排文件也有一个缺点：它不能保证找到的对象始终是最近的。

在下图中，我们可以看到这样的场景：实际的最近邻居位于红色区域，但我们仅从绿色区域中选择候选者。这种情况称为边缘问题。

img

边缘问题

当查询的对象位于与另一个区域的边界附近时，通常会发生这种情况。为了减少这种情况下的错误数量，我们可以扩大搜索范围，并根据与对象最接近的前m个质心选择几个区域来搜索候选区域。

img

搜索多个区域内的最近邻居 (m = 3)

探索的区域越多，结果就越准确，计算结果所需的时间也就越多。

注：这个类似geohash搜索中的边缘问题

应用

尽管存在边缘问题，基于训练的倒排文件在实践中仍显示出不错的结果。当我们想要以稍微降低精度来实现速度数倍增长的情况下，它是完美的选择。

用例示例之一是基于内容的推荐系统。想象一下，它根据用户过去看过的其他电影向他推荐一部电影。该数据库包含一百万部电影可供选择。

  • 通过使用 kNN，系统确实为用户选择了最相关的电影并推荐。然而，执行查询所需的时间非常长。
  • 让我们假设通过倒排文件索引，系统推荐第五个最相关的电影，这可能是现实生活中的情况。搜索时间比 kNN 快 20 倍。

从用户体验来看，很难区分这两个推荐的质量结果：第一个和第五个最相关的结果都是来自一百万个可能的电影的良好推荐。用户可能会对这些建议中的任何一个感到满意。从时间角度来看，倒排文件显然是赢家。这就是为什么在这种情况下最好使用后一种方法。

img

倒排文件索引性能。这里我们稍微降低精度以在推理过程中获得更高的速度。

FAISS实现

Faiss（Facebook AI Search Comparison）是一个用 C++ 编写, binding Python使用的faiss库, 提供c api 库方便FFI交互，用于优化相似性搜索。该库提供了不同类型的索引，这些索引是用于有效存储数据和执行查询的数据结构。

根据Faiss 文档中的信息，我们将了解索引是如何创建和参数化的。

kNN

实现 kNN 方法的索引在 Faiss 中被称为扁平索引(flat index)，因为它们不压缩任何信息。它们是保证正确搜索结果的唯一索引。实际上Faiss中存在两种类型的扁平索引：

  • IndexFlatL2。相似度计算为欧几里得距离。
  • IndexFlatIP。相似度计算为内积。

这两个索引在其构造函数中都需要一个参数d：数据维度。这些索引没有任何可调参数。

img

IndexFlatL2 和 IndexFlatIP 的 Faiss 实现

存储向量的单个分量需要 4 个字节。因此，要存储维度为 d 的单个向量，需要4 * d字节。

img

倒排文件索引

对于所描述的倒排文件，Faiss 实现了类IndexIVFFlat。与 kNN 的情况一样，“ Flat ”一词表示原始向量没有解压缩并且它们被完全存储。

要创建此索引，我们首先需要传递一个量化器 - 一个将确定如何存储和比较数据库向量的对象。

IndexIVFFlat有2个重要参数：

  • nlist：定义在训练期间创建的多个区域（Voronoi 单元）。
  • nprobe：确定要搜索候选区域的区域数。更改 nprobe 参数不需要重新训练。

img

IndexIVFFlat 的 Faiss 实现

与前面的情况一样，我们需要4 * d字节来存储单个向量。但现在我们还必须存储数据集向量所属的 Voronoi 区域的信息。在 Faiss 实现中，此信息每个向量占用 8 个字节(可调整)。因此，存储单个向量所需的内存为：

img

结论

我们已经了解了相似性搜索中的两种基本算法。实际上，朴素 kNN 几乎不应该用于机器学习应用，因为除了特定情况外，它的可扩展性很差。另一方面，倒排文件为加速搜索提供了良好的启发式方法，其质量可以通过调整其超参数来提高。搜索性能仍然可以从不同的角度来提高。在本系列文章的下一部分中，我们将了解一种旨在压缩数据集向量的方法。

Reference

注：除非另有说明，所有图片均由原作者提供。

原文：https://towardsdatascience.com/similarity-search-knn-inverted-file-index-7cab80cc0e79

附操作学习笔记:

faiss_tutorial.ipynb

faiss_vector_indexes.ipynb