平台建站,网站制作过程合理的步骤,做网站每页面费用,价格查询作者#xff1a;来自 Elastic Valentin Crettaz 本文是三篇系列文章中的第一篇#xff0c;将深入探讨向量搜索#xff08;也称为语义搜索#xff09;的复杂性#xff0c;以及它在 Elasticsearch 中的实现方式。 本文是三篇系列文章中的第一篇#xff0c;将深入探讨向量搜…作者来自 Elastic Valentin Crettaz 本文是三篇系列文章中的第一篇将深入探讨向量搜索也称为语义搜索的复杂性以及它在 Elasticsearch 中的实现方式。 本文是三篇系列文章中的第一篇将深入探讨向量搜索也称为语义搜索的复杂性以及它在 Elasticsearch 中的实现方式。
第一部分重点介绍嵌入向量的基础知识以及向量搜索的底层工作原理。
借助第一篇文章中学到的所有知识第二部分将指导你了解如何在 Elasticsearch 中设置向量搜索。
在第三部分中我们将利用前两部分中学到的知识在此基础上深入研究如何在 Elasticsearch 中编写强大的混合搜索查询。
在深入探讨本文的真正内容之前让我们回顾一下向量的一些历史它是语义搜索中的关键概念。 向量搜索并不新鲜
可以肯定的是自 2022 年 11 月 ChatGPT 问世以来我们每天都会听到或读到有关 “向量搜索” 的信息。向量搜索无处不在而且非常普遍我们常常会觉得这是一项刚刚问世的尖端新技术但事实是这项技术已经存在了 60 多年该主题的研究始于 1960 年代中期第一篇研究论文于 1978 年由信息检索专家 Gerard Salton 及其康奈尔大学的同事发表。Salton 在密集和稀疏向量模型方面的工作构成了现代向量搜索技术的根基。
在过去的 20 年里许多基于他的研究的向量 DBMS 被创建并推向市场。其中包括由 Apache Lucene 项目提供支持的 Elasticsearch该项目于 2019 年开始研究向量搜索。
向量现在无处不在如此普遍因此在使用它们之前首先要很好地掌握它们的基本理论和内部工作原理。在深入研究之前让我们快速回顾一下词汇搜索和向量搜索之间的区别以便我们更好地理解它们的区别以及它们如何相互补充。 向量搜索与词汇搜索
介绍向量搜索的一个简单方法是将其与你可能习惯的更传统的词汇搜索进行比较。向量搜索通常也称为语义搜索和词汇搜索的工作方式截然不同。词汇搜索是我们在 Elasticsearch 中多年来一直使用的搜索类型。简而言之它不会尝试理解索引和查询内容的真正含义而是会尽力将用户在查询中输入的单词或其变体例如词干、同义词等的文字与之前已使用相似性算法例如 TF-IDF索引到数据库中的所有文字进行词汇匹配。 图 1词汇搜索的一个简单示例 我们可以看到左上角的三个文档被标记并分析。然后将生成的术语编入倒排索引该索引只是将分析的术语映射到包含它们的文档 ID。请注意所有术语都只出现一次并且没有一个与任何文档共享。搜索 “nice german teacher” 将匹配所有三个文档分数各不相同即使它们都没有真正抓住查询的真正含义。
如下图 2 所示在处理多义词或同形异义词时情况会变得更加棘手即拼写相同但含义不同的单词right、palm、bat、mean 等。让我们以 “right” 这个词为例它可以表示三种不同的含义看看会发生什么。 图 2搜索同形异义词 搜索 “I’m not right” 会返回一个与第一个返回结果含义完全相反的文档。如果你搜索完全相同的术语但以不同的顺序排列它们以产生不同的含义例如 “turn right” 和 “right turn”则会产生完全相同的结果即第三个文档 “Take a right turn”。诚然我们的查询过于简单没有使用短语匹配等更高级的查询但这有助于说明词汇搜索不了解索引和搜索内容背后的真正含义。如果这不清楚请不要担心我们将在第三篇文章中重新讨论这个例子看看向量搜索在这种情况下如何提供帮助。
公平地说当你可以控制如何索引结构化数据想想映射、文本分析、提取管道等以及如何编写查询想想巧妙编写的 DSL 查询、查询术语分析等时你就可以使用词汇搜索引擎创造奇迹这是毫无疑问的Elasticsearch 在词汇搜索功能方面的记录令人惊叹。它在过去几年中取得的成就以及它在多大程度上普及和改进了词汇搜索领域这确实令人惊叹。
但是当你负责为需要提出自由文本问题的用户提供查询非结构化数据想想图像、视频、音频、原始文本等的支持时词汇搜索就显得力不从心了。此外有时查询甚至不是文本它可能是图像我们很快就会看到。词汇搜索在这种情况下不足的主要原因是非结构化数据既不能像结构化数据那样被索引也不能被查询。处理非结构化数据时语义semantics就会发挥作用。语义是什么意思很简单就是含义
我们以图像搜索引擎例如 Google 图片搜索或 Lens为例。你拖放一张图片Google 语义搜索引擎就会找到并返回与你查询的图片最相似的图片。在下面的图 3 中我们可以在左侧看到德国牧羊犬的图片在右侧看到所有已检索到的类似图片第一个结果是与提供的图片相同的图片即最相似的图片。 图 3搜索图片。 来源Google 图片搜索 https://www.google.com/imghp 尽管这对于我们人类来说听起来简单而合乎逻辑但对于计算机来说情况就完全不同了。这就是向量搜索能够实现和帮助实现的。正如世界最近所见证的那样向量搜索释放的力量是巨大的。现在让我们揭开它的面纱看看下面隐藏着什么。 嵌入向量
正如我们之前所见使用词汇搜索引擎文本等结构化数据可以轻松标记为可在搜索时匹配的术语而不管这些术语的真实含义如何。然而非结构化数据可以采用不同的形式例如大型二进制对象图像、视频、音频等并且根本不适合相同的标记tokenizing过程。此外语义搜索的整个目的是以这样的方式索引数据以便可以根据其所代表的含义进行搜索。我们如何实现这一点答案就在两个词中机器学习或者更准确地说是深度学习
深度学习Deep Learning是机器学习的一个特定领域它依赖于基于人工神经网络的模型该模型由多层处理组成可以逐步提取数据的真正含义。这些神经网络模型的工作方式深受人脑的启发。下面的图 4 显示了神经网络的外观包括输入层和输出层以及多个隐藏层 图 4神经网络层。 来源IBMhttps://www.ibm.com/topics/neural-networks 神经网络的真正壮举是它们能够将单个非结构化数据转换为一系列浮点值这些浮点值被称为嵌入向量或简称为嵌入。作为人类只要我们在二维或三维空间中可视化它们我们就能很好地理解什么是向量。向量的每个分量表示二维 x-y 平面或三维 x-y-z 空间中的坐标。
但是神经网络模型工作的嵌入向量可以有几百甚至几千个维度并且仅表示多维空间中的一个点。每个向量维度代表非结构化数据的一个特征feature或特性。让我们用一个深度学习模型来说明这一点该模型将图像转换为 2048 维的嵌入向量。该模型会将我们在图 3 中使用的德国牧羊犬图片转换为下表所示的嵌入向量。请注意我们仅显示第一个和最后一个元素但表中还会有 2,042 个列/维度。
is_redis_dogblue_sky…no_grasgerman_shepherdis_treeGerman shepherd embeddings0.01210.95720.8735…0.11980.97120.0512
每一列都是模型的一个维度代表底层神经网络试图建模的特征或特性。提供给模型的每个输入都将根据该输入与 2048 个维度的相似程度进行表征。因此嵌入向量中每个元素的值表示该输入与特定维度的相似度。在这个例子中我们可以看到模型检测到狗和德国牧羊犬之间有很高的相似性并且还检测到了一些蓝天。 与词汇搜索其中术语可以匹配也可以不匹配相比使用向量搜索我们可以更好地了解一段非结构化数据与模型支持的每个维度的相似程度。因此嵌入向量可以作为非结构化数据的极好的语义表示。 秘诀
现在我们知道了深度学习神经网络如何将非结构化数据切分为嵌入向量从而捕捉大量维度上数据的相似性我们需要了解这些向量的匹配是如何进行的。答案其实很简单。彼此接近的嵌入向量表示语义上相似的数据片段。因此当我们查询向量数据库时搜索输入图像、文本等首先使用与索引所有非结构化数据相同的模型转换为嵌入向量最终目标是找到与该查询向量最近的相邻向量。因此我们需要做的就是弄清楚如何测量查询向量与数据库中索引的所有现有向量之间的 “距离” 或 “相似性”仅此而已。 距离和相似性
幸运的是借助向量算法测量两个向量之间的距离是一个很容易解决的问题。那么让我们来看看现代向量搜索数据库例如 Elasticsearch支持的最流行的距离和相似度函数。警告前方有数学知识 L1 距离
两个向量 x 和 y 的 L1 距离也称为曼哈顿距离是通过将它们所有元素的成对绝对差相加来测量的。显然距离 d 越小两个向量越接近。公式非常简单如下所示 从视觉上看L1 距离可以用下面的图 5 来表示 图 5可视化两个向量之间的 L1 距离 设两个向量 x 和 y例如 x (1, 2) 和 y (4, 3)则两个向量的 L1 距离为 | 1 - 4 | | 2 - 3 | 4。 L2 距离
L2 距离也称为欧几里得距离两个向量 x 和 y 的测量方法是先将它们所有元素的两两差值的平方相加然后对结果取平方根。它基本上是两点之间的最短路径也称为斜边。与 L1 类似距离 d 越小两个向量越接近 L2 距离如下图6所示 图 6可视化两个向量之间的 L2 距离 让我们重复使用与 L1 距离相同的两个样本向量 x 和 y现在我们可以计算 L2 距离为 。取 10 的平方根将得出 3.16。 Linf 距离
两个向量 x 和 y 的 Linf代表 L 无穷大距离也称为切比雪夫距离或棋盘距离简单定义为任意两个元素之间的最长距离或沿其中一个轴/维度测量的最长距离。公式非常简单如下所示 Linf 距离的表示如下图 7 所示 图 7可视化两个向量之间的 Linf 距离 同样取相同的两个样本向量 x 和 y我们可以计算 L 无穷距离为 max ( | 1 - 4 | , | 2 - 3 | ) max (3, 1) 3。 余弦相似度
与 L1、L2 和 Linf 不同余弦相似度不测量两个向量 x 和 y 之间的距离而是测量它们的相对角度即它们是否都指向大致相同的方向。相似度 s 越高两个向量越 “接近”。公式同样非常简单如下所示 两个向量之间余弦相似度的表示方法如下图 8 所示 图 8可视化两个向量之间的余弦相似度 此外由于余弦值始终在 [-1, 1] 区间内-1 表示相反的相似性即两个向量之间呈 180° 角0 表示不相关的相似性即呈 90° 角1 表示相同即呈 0° 角如下图 9 所示 图 9余弦相似度谱 再次让我们重复使用相同的样本向量 x 和 y并使用上述公式计算余弦相似度。首先我们可以计算两个向量的点积即 1x4)(2x3) 10。然后我们将两个向量的长度也称为幅度相乘。最后我们将点积除以乘积的长度 10 / 11.18034 0.894427即 26° 角该值非常接近 1因此两个向量可以被认为非常相似。 点积相似度
余弦相似度的一个缺点是它只考虑两个向量之间的角度而不考虑它们的大小即长度这意味着如果两个向量大致指向同一方向但其中一个比另一个长得多则两者仍将被视为相似。点积相似度也称为标量或内积通过同时考虑向量的角度和大小来改善这一点从而提供更准确的相似度度量。
两个等效公式用于计算点积相似度。第一个与我们之前在余弦相似度的分子中看到的相同 第二个公式只是将两个向量的长度乘以它们之间角度的余弦 点积相似度如下图 10 所示 图 10可视化两个向量之间的点积相似度 最后一次我们取样本 x 和 y 向量并使用第一个公式计算它们的点积相似度就像我们之前对余弦相似度所做的那样即 (1x4)(2x3) 10。
使用第二个公式我们将两个向量的长度相乘 并将其乘以两个向量之间 26° 角的余弦得到 11.18034 x cos(26°) 10。
值得注意的是如果先对所有向量进行归一化即它们的长度为 1那么点积相似度将与余弦相似度完全相同因为 |x| |y| 1即两个向量之间角度的余弦。正如我们稍后会看到的归一化向量是一种很好的做法它可以让向量的大小变得无关紧要从而使相似度只关注角度。它还可以加快索引和查询时的距离计算这在处理数十亿个向量时可能是一个大问题。 快速回顾
哇到目前为止我们已经了解了很多信息所以让我们暂停一下快速回顾一下我们所处的位置。我们已经了解到……
…语义搜索基于深度学习神经网络模型该模型擅长将非结构化数据转换为多维嵌入向量。…模型的每个维度都代表非结构化数据的特征或特性。…嵌入向量是一系列相似度值每个维度一个表示给定的非结构化数据与每个维度的相似程度。…两个向量越 “近”即最近邻居它们所代表的语义相似概念就越多。…距离函数L1、L2、Linf使我们能够测量两个向量的接近程度。…相似度函数余弦和点积使我们能够测量两个向量朝同一方向的距离。
现在我们需要深入研究的最后一部分是向量搜索引擎本身。当查询进入时查询首先被向量化然后向量搜索引擎找到与该查询向量最近的相邻向量。测量查询向量与数据库中所有向量之间的距离或相似度的蛮力brute-force方法可以适用于小型数据集但随着向量数量的增加它很快就会失效。换句话说我们如何索引数百万、数十亿甚至数万亿个向量并在合理的时间内找到查询向量的最近邻居这就是我们需要变得聪明并找出索引向量的最佳方法的地方这样我们就可以尽快锁定最近的邻居而不会过多地降低精度。
更多有关距离和相似性的知识请详细阅读 “Elasticsearch向量相似度技术和评分” 向量搜索算法和技术
多年来许多不同的研究团队投入了大量精力来开发非常巧妙的向量搜索算法。在这里我们将简要介绍主要的算法。根据用例有些算法比其他算法更适合。 线性搜索
我们之前简要介绍了线性搜索或平面索引当时我们提到了将查询向量与数据库中存在的所有向量进行比较的蛮力brute-force方法。虽然它可能在小型数据集上效果很好但随着向量数量和维度的增加On复杂度性能会迅速下降。
幸运的是有一种更有效的方法称为近似最近邻 (approximate nearest neighbor - ANN)其中嵌入向量之间的距离是预先计算的并且相似的向量以保持它们靠近的方式存储和组织例如使用集群、树、哈希或图形。这种方法被称为 “近似”因为它们通常不能保证 100% 的准确性。最终目标是尽可能快速地缩小搜索范围以便只关注最有可能包含相似向量的区域或者降低向量的维数。 K 维树 - K - Dimensional trees
K 维树或 KD 树是二叉搜索树的泛化它将点存储在 k 维空间中并通过将搜索空间连续二等分为较小的左树和右树来工作其中向量被索引。在搜索时算法只需访问查询向量周围的几个树枝图 11 中的红点即可找到最近的邻居图 11 中的绿点。如果请求的邻居超过 k 个则黄色区域会扩展直到算法找到更多邻居。 图11KD树算法。 Source: Kd-tree and Nearest neighbor (NN) search (2D case) | Alexey Abramov | Salzi | Blog KD 树算法的最大优点是它允许我们快速地只关注一些局部的树分支从而排除大部分向量的考虑。然而这种算法的效率会随着维数的增加而降低因为与低维空间相比需要访问的分支要多得多。 倒排索引
倒排索引 (inverted file index - IVF) 方法也是一种空间分区space-partitioning算法它将彼此接近的向量分配到它们的共享质心。在 2D 空间中最好使用 Voronoi 图来可视化如图 12 所示 图 12二维空间中倒排文件索引的 Voronoi 表示。 Source: AUTOINDEX Explained | Cloud | Zilliz Cloud Developer Hub 我们可以看到上面的二维空间被划分为 20 个簇每个簇的质心都用黑点表示。空间中的所有嵌入向量都被分配给质心最接近的簇。在搜索时算法首先通过找到最接近查询向量的质心来确定要关注的簇然后它可以简单地将焦点集中在该区域如果需要还可以将焦点集中在周围的区域以找到最近的邻居。
在高维空间中使用时此算法会遇到与 KD 树相同的问题。这称为维数灾难当空间体积增加太多以至于所有数据看起来都很稀疏并且获得更准确结果所需的数据量呈指数增长时就会发生这种情况。当数据稀疏时这些空间分区算法将数据组织成簇变得更加困难。幸运的是还有其他算法和技术可以缓解这个问题如下所述。 量化 - Quantization
量化是一种基于压缩的方法它允许我们通过降低嵌入向量的精度来减少数据库的总大小。这可以通过使用标量量化 (scalar quantization - SQ) 来实现即将浮点向量值转换为整数值。这不仅可以将数据库的大小减少 8 倍还可以减少内存消耗并加快搜索时向量之间的距离计算。
另一种技术称为乘积量化 (product quantization - PQ)它首先将空间划分为低维子空间然后使用聚类算法类似于 k 均值 - k-means将彼此接近的向量分组到每个子空间中。
请注意量化不同于降维降维是减少维数dimensionality reduction即向量只是变短了。 分层可导航小世界 (Hierarchical Navigable Small Worlds - HNSW)
如果仅从名称来看它看起来很复杂别担心其实它并不复杂简而言之分层可导航小世界是一种基于多层图形的算法非常流行且高效。它被许多不同的向量数据库使用包括 Apache Lucene。下图 13 中可以看到 HNSW 的概念表示。 图 13分层可导航小世界。 Source: Similarity Search, Part 4: Hierarchical Navigable Small World (HNSW) | Towards Data Science 在顶层我们可以看到一个由极少数向量组成的图这些向量之间的链接最长即相似度最低的连接向量图。我们越深入底层找到的向量就越多图就越密集向量之间的距离也越来越近。在最低层我们可以找到所有向量其中最相似的向量彼此距离最近。
在搜索时算法从顶层的任意入口点开始找到最接近查询向量的向量以灰色点表示。然后它移动到下一层并重复相同的过程从上一层留下的相同向量开始依此类推一层接一层直到到达最低层并找到查询向量的最近邻居。 局部敏感哈希 (Locality-sensitive hashing - LSH)
与迄今为止介绍的所有其他方法一样局部敏感哈希力求大幅减少搜索空间以提高检索速度。通过这种技术嵌入向量被转换为哈希值所有这些都通过保留相似性信息来实现这样搜索空间最终就变成了一个可以查找的简单哈希表而不是需要遍历的图或树。基于哈希的方法的主要优点是包含任意大维数的向量可以映射到固定大小的哈希这极大地加快了检索时间而不会牺牲太多的精度。
通常对数据进行哈希处理的方法有很多种特别是对嵌入向量进行哈希处理的方法但本文不会深入讨论每种方法的细节。传统的哈希方法通常会为看起来非常相似的数据产生非常不同的哈希。由于嵌入向量由浮点值组成我们取两个在向量算法中被认为非常接近的浮点值样本例如 0.73 和 0.74并将它们通过几个常见的哈希函数运行。从下面的结果可以看出常见的哈希函数显然无法保留输入之间的相似性。
Hashing function0.730.74MD51342129d04cd2924dd06cead4cf0a3ca0aec1b15371bd979cfa66b0a50ebecc5SHA149d2c3e0e44bff838e1db571a121be5ea874e8d9a534e76482ade9d9fe4bff3035a7f31f2f363d77SHA25699d03fc3771fe6848d675339fc49eeb1cb8d99a12e6358173336b99a2ec530ea5ecbc825ba5c16856edfdaf0abc5c6c41d0d8a9c508e34188239521dc7645663
虽然传统的哈希方法试图最小化相似数据片段之间的哈希冲突但局部敏感哈希的主要目标恰恰相反即最大化哈希冲突以便相似的数据以高概率落入同一个存储桶中。通过这样做在多维空间中彼此接近的嵌入向量将被哈希为落入同一个存储桶中的固定大小值。由于 LSH 允许这些哈希向量保持其接近度因此该技术对于数据聚类和最近邻搜索非常有用。
所有繁重的工作都发生在需要计算哈希值的索引时而在搜索时我们只需要对查询向量进行哈希处理以查找包含最近嵌入向量的存储桶。一旦找到候选存储桶通常会进行第二轮以确定与查询向量最近的相邻向量。 让我们总结一下
为了介绍向量搜索我们必须在本文中介绍相当多的内容。在比较了词汇搜索和向量搜索之间的差异之后我们了解了深度学习神经网络模型如何设法捕获非结构化数据的语义并将其含义转码为高维嵌入向量即表示数据沿模型每个维度的相似性的浮点数序列。还值得注意的是向量搜索和词汇搜索不是竞争关系而是互补的信息检索技术我们将在本系列的第三部分深入研究混合搜索时看到。
之后我们介绍了向量搜索的一个基本构建块即距离和相似度函数它使我们能够测量两个向量的接近度并评估它们所代表的概念的相似性。
最后我们回顾了最流行的向量搜索算法和技术的不同类型这些算法和技术可以基于树、图、集群或哈希其目标是快速缩小多维空间的特定区域以便找到最近的邻居而不必像线性蛮力搜索那样访问整个空间。 请继续关注本系列的其他部分
第 2 部分如何在 Elasticsearch 中设置向量搜索第 3 部分使用 Elasticsearch 进行混合搜索
使用此自定进度的 Search AI 动手学习亲自尝试向量搜索。您现在可以开始免费云试用或在本地机器上试用 Elastic。 原文A quick introduction to vector search - Elasticsearch Labs
