- 为什么速度如此之快？
- 什么是向量搜索？
- kNN
- ANN
- Weaviate的HNSW
- 概括
每当我谈到向量搜索时，我都喜欢用一个语义搜索的例子来演示它。为了增加令人惊叹的因素，我喜欢在 Wikipedia 数据集上运行我的查询，该数据集包含来自 Wikipedia 的超过 2800 万段。
例如，我可以问：“柏林最高的建筑是什么？”，而向量搜索引擎（在我的演示中 - Weaviate的例子中）会用“Fernsehturm Berlin”来响应。
事情是这样的，在一个巨大的非结构化数据存储库中找到正确的答案并不是这个演示最令人印象深刻的部分（我的意思是，它非常令人印象深刻），但它是这一切发生的速度。UI 显示结果需要几分之一秒。
我们谈论的是语义搜索查询，它需要几毫秒才能在包含2800 万段的数据集中找到答案。有趣的是，呈现结果的时间比向量搜索引擎找到答案的时间要长。
请注意，语义搜索与常规关键字搜索不同（它匹配类似关键字），而是根据查询和数据的语义含义来搜索答案。
跟随这个演示不可避免的问题总是：
为什么速度如此之快？
要回答这个问题，我们需要看看向量搜索引擎是如何工作的。
与其他数据库不同，向量搜索引擎基于数据向量（或向量嵌入）对数据进行索引。向量嵌入捕获数据的含义和上下文，通常由机器学习模型预测。
在输入/导入（或对数据对象进行任何重大更改）时，对于每个新的/更新的数据对象，向量搜索引擎使用机器学习模型来预测和计算向量嵌入，然后将其与对象一起存储。
数据集中的每个数据对象都有一个向量
简而言之，向量嵌入是一个数字数组，可以用作高维空间中的坐标。虽然很难想象超过 3 维空间 (x, y, z) 的坐标，但我们仍然可以使用向量来计算向量之间的距离，这可以用来表示对象之间的相似性。
有许多不同的距离度量，例如余弦相似度和欧几里得距离（L2 距离）。
以类似的方式，每当我们运行查询（例如：“柏林最高的建筑是什么？”）时，向量搜索引擎也可以将其转换为“查询”向量。矢量搜索引擎的任务是使用距离度量和搜索算法识别和检索最接近查询的给定矢量的矢量列表。
这有点像滚球游戏——小标记（杰克）是我们查询向量的位置，球（滚球）是我们的数据向量——我们需要找到离标记最近的滚球。
找到相似向量的一种方法是使用简单的k 近邻 (kNN) 算法，该算法通过将数据库中的每个数据向量与查询向量进行比较，返回 k 个最近的向量。
在我们的滚球示例（如下图所示）中，有 6 个滚球，kNN 算法将测量千斤顶与地面上 6 个滚球中的每一个之间的距离。这将导致 6 次单独的计算。
仅在两个维度上将搜索向量与 10、100 或 1000 个数据向量进行比较是一项简单的工作。但当然，在现实世界中，我们更有可能处理数百万（如维基百科数据集）甚至数十亿的数据项。此外，大多数 ML 模型在语义搜索中使用的维度数量高达数百或数千个维度！
kNN 搜索的蛮力在计算上非常昂贵- 并且根据数据库的大小，单个查询可能需要几秒钟甚至几小时的时间。如果将 300 维向量与 10M 向量进行比较，搜索引擎将需要进行 300 x 10M = 3B 计算！所需计算的数量随着数据点的数量 (O(n)) 线性增加（图 2）。
总之，kNN 搜索不能很好地扩展，并且很难在生产中使用它与大型数据集进行图像处理。
向量搜索引擎不是逐个比较向量，而是使用近似最近邻 (ANN) 算法，该算法牺牲了一点准确性（因此名称中的 A）以大幅提高速度。
ANN 算法可能不会返回真正的 k 最近向量，但它们非常有效。ANN 算法在非常大规模的数据集上保持良好的性能（亚线性时间，例如（多）对数复杂度，参见图 2）。
请注意，大多数矢量搜索引擎都允许您配置 ANN 算法的行为方式。这使您可以在召回权衡（真正的 top-k 最近邻居的结果比例）、延迟、吞吐量（每秒查询数）和导入时间之间找到适当的平衡。举个很好的例子，检查Weaviate benchmarks，看看efConstruction、maxConnections 和 ef这三个参数如何影响召回、延迟、吞吐量和导入时间。
ANN 方法的例子有：
- 树——例如ANNOY（图 3），
- 邻近 图- 例如HNSW（图 4），
- 聚类- 例如FAISS，
- 散列- 例如LSH，
- 矢量压缩- 例如PQ或SCANN。
哪种算法效果最好取决于您的项目。性能可以通过延迟、吞吐量（每秒查询数）、构建时间和准确性（召回）来衡量。这四个组件通常需要权衡取舍，因此取决于用例哪种方法效果最好。
因此，ANN 并不是一种总能在数据集中找到真正的 k 个最近邻居的神奇方法，它可以找到真正的 k 个邻居的一个非常好的近似值。但它可以在很短的时间内做到这一点！
Weaviate是向量搜索引擎的一个很好的例子，它使用 ANN 算法提供超快速查询。引入 Weaviate 的第一个 ANN 算法是分层可导航小世界图 (HNSW)的自定义实现。
查看Weaviate ANN 基准，了解 HNSW 在现实大规模数据集上的表现。您可以使用它来比较召回、QPS、延迟和导入时间之间的权衡。您会发现有趣的是，Weaviate 可以保持非常高的召回率（>95%），同时保持高吞吐量和低延迟（均以毫秒为单位）。这正是您进行快速但可靠的矢量搜索所需要的！
快速回顾：
- 向量搜索引擎使用机器学习模型来计算矢量嵌入并将其附加到所有数据对象
- 向量嵌入捕获数据的含义和上下文
- 借助 ANN 算法，矢量搜索引擎提供超快速查询
- 人工神经网络算法以少量的准确度换取性能的巨大提升