介绍HNSW：分层导航小世界
探索HNSW：分层导航小世界
介绍
人工智能创新正在以极快的速度进行。其中创新的前沿之一是向量搜索引擎。你问这些搜索引擎是什么？简单来说，它们通过浏览大型数据集并挑选出相关内容来帮助训练大型语言模型（LLMs）。现在，向量数据库中的索引有许多不同的方法。其中，分层可浏览小世界（HNSW）因其高性能和可扩展性而脱颖而出。所有主要的向量存储提供HNSW作为索引方法。它快速、高效、强大且可靠。因此，在本文中，我们将研究HNSW的内部工作原理，了解它的快速之处。
学习目标
- 理解嵌入和向量数据库。
- 熟悉向量数据库中的不同索引方式。
- 了解HNSW及其工作原理。
- 理解仅包含头文件的HNSW实现HNSWlib。
本文是数据科学博览会的一部分。
什么是嵌入？
嵌入是数据（文本、图像）在高维向量空间中的向量表示。
在向量空间中，语义相关的数据会靠近，而不相似的数据则会远离。换句话说，梅西和足球的嵌入将在嵌入空间中紧密相连，而足球和乔·拜登的嵌入将在嵌入空间中相距较远。
向量的长度可以从几百到数千个以上。这导致存储、查询和搜索变得困难。但是，每个基于检索增强生成（RAG）的应用程序都需要对嵌入数据进行高速搜索和查询。这就是向量数据库的用武之地。
什么是向量数据库？
正如传统数据库旨在存储结构化和非结构化数据一样，向量数据库用于存储、搜索和查询高维向量嵌入。它们提供了与嵌入及其相关数据交互的用户友好界面。向量数据库与传统数据库在本质上并无不同。向量数据库使用传统数据库存储序列化嵌入。例如， Chroma 使用SQLite作为内存存储，而Pgvector使用Postgres数据库存储嵌入及其相关元数据。将传统数据库与向量数据库区分开的是底层的索引算法。
向量数据库中的索引
索引是指以提供最近邻向量高效查询的方式组织高维向量的过程。
这是构建任何向量数据库最关键的部分。这些索引使得高维嵌入的查询快速高效。创建向量索引有多种方法，例如：
- 线性搜索算法（平坦索引）：这是一种线性搜索算法，意味着它将将查询向量与数据库中的每个向量进行比较。这是目前最简单的方法，并且在小数据集上运行良好。
- 基于聚类的算法（IVF）：倒排文件是一种基于聚类的索引技术。它使用k-means聚类对所有向量进行聚类。当提供查询向量时，它计算查询向量与每个聚类的质心之间的距离，并开始在与查询向量最接近的质心聚类中搜索最近邻居。这显著减少了查询时间。
- 量化（标量量化和乘积量化）：量化技术通过减少大型嵌入的精度来减少其内存占用。
- 基于图的（HNSW）：最常见的索引方法。它使用分层图结构对向量进行索引。这是我们将要探索的内容。
理解HNSW
大型语言模型（LLMs）正变得越来越流行，许多组织希望在其产品堆栈中实现它们。然而，这样做存在一个挑战：LLMs具有有限的上下文窗口。上下文窗口是一个AI模型可以吸收的标记数量。例如，GPT 3.5 turbo的上下文长度为4096。这就是向量搜索数据库的优势所在。我们不是将整本书都投入LLM的上下文中，而是找出最相关的部分并将其提供给LLM以获得精确的结果。
现在，在上面所有讨论过的向量数据库索引方法中，HNSW是最稳健和可扩展的。这也使得它成为最广泛使用的索引方法。HNSW是通过组合两个算法而形成的：跳跃表和可导航小世界算法。为了理解HNSW，我们需要了解这些算法。那么，让我们深入探讨。
跳跃表
顾名思义，跳跃表是基于链表数据结构，或者我们可以说它是链表数据结构的扩展。它是由David Pugh在1990年发明的作为链表的更快替代品。
为什么我们需要一个跳跃表呢？链表的搜索时间复杂度是O(n)。这在实际应用场景中可能并不理想，速度至关重要。因此，我们可能需要一种更高效的链表算法。
跳跃表的预期时间复杂度是O(log n)。它在随机访问方面比链表表现更好。由于它具有具有多个节点的分层结构，最坏情况下的空间复杂度是O(n log n)，其中n是最底层节点的数量。
跳跃表如何工作？
跳跃表维护了一个分层的链接结构，其中顶层具有元素之间最长的链接。随着我们向下移动，链接的数量呈指数递减。
在上图中，最底层是一个完整的链表。随着我们向上移动，每个层级的节点数量减半。这个结构被称为跳跃表，因为较高的层级在遍历时允许我们跳过节点。
考虑以下示例。
在搜索k时：
- 如果k等于目标元素
- 如果k大于等于向右移动
- 如果k小于向下移动
我们从左上角开始向右移动，直到找到k或小于k的数字。然后我们下降到下一层并继续这个过程，直到找到k。搜索时间复杂度为O(log n)，因为我们在每个层级跳过了一半的项目。
尽管随机访问更快，但插入和删除的速度较慢，因为它们增加了在多个层级上更新和删除的额外开销。
在插入时，我们从底层链表开始，在适当的位置添加节点。由于跳跃表维护了一个分层结构，我们需要确定节点是否出现在更高的层级。这个过程是随机的，就像抛硬币一样。节点出现在其立即上层的概率是0.5。在理想的跳跃表中，第一层的节点数量约为n/2，在第二层中约为n/4，其中n是最底层的节点数或完整链表。
考虑以下示例。
我们找到插入的理想位置，并在底层插入节点。然后基于随机的二进制结果（正面或反面），决定节点是否出现在上层。在完美的跳跃表中，各个层级上的节点分布是平衡的。
删除类似地进行。找到目标数字并删除节点。如果元素在更高的层级上存在，则删除它并更新链表。
可导航小世界 (NSW)
可导航小世界是一种基于图的算法，用于寻找近似最近邻。图中的数据点称为节点。每个节点连接到一组靠近自己的固定连接。
这是一种贪婪算法。它从图中预定义的点开始，并选择靠近目标节点的节点。节点之间的距离可以用欧氏距离或余弦相似度来衡量。该过程重复进行，直到到达目标节点的最近邻。
可导航小世界算法非常高效且易于部署。它适用于数据集的规模从几百到几千。在那之后，其性能可能变差。它使用局部信息来寻找最近邻居时，可能由于过早终止而导致性能下降。
在插入期间，我们遍历图以找到最近的邻居并将它们连接到节点x。
由于向量数据库中需要处理数百万个嵌入数据，因此我们需要一种更好的算法，以便扩展性好且具有更好的搜索性能。尽管可导航小世界对于小型数据集表现良好，但我们需要一种更好的算法来处理数亿或十亿个数据点。这就是HNSW的作用。
分层可导航小世界（HNSW）
HNSW通过包含跳表的分层结构扩展了NSW。这解决了NSW的可扩展性瓶颈问题。与跳表一样，HNSW创建了NSW的多层结构，而不是链表。与跳表一样，最顶层会有较少的数据点和最长的连接。随着在层次结构中下降，元素的数量增加。在最底层，我们有所有的数据点。与跳表一样，随着在层次结构中上升，元素存在的概率呈指数级下降。
但是我们如何在HNSW中进行搜索呢？
在HNSW中进行搜索
现在回想一下跳表和NSW。在跳表中，我们从顶层开始，而在NSW中，我们从预定义的点开始。在HNSW中，我们从层次结构的最顶层的预定义点开始，并且贪婪地遍历图表，以找到该层中与目标数据点最接近的元素。一旦找到最近的节点，我们向下降到下一层，重复此过程，直到找到目标节点的“K”个最近邻节点。参见下图
在HNSW中的插入和删除
HNSW的插入遵循与跳表相同的原理。我们遍历各个层次，找到元素的最近邻节点。然后，我们向下移动并重复相同的过程，直到在底层找到所有最近邻节点。
下一个任务是确定对插入元素的双向连接。通常由预定义参数m来确定。我们将m个最近邻节点连接到插入节点。这是确定连接到插入节点的一种方式。也可以使用其他启发式算法。例如，我们不仅将其连接到相同区域的最近邻节点，还将插入节点连接到最近区域的最接近节点，以形成更好连接的图表。
与跳表一样，节点出现在较高层的概率是随机决定的。其函数为floor(-ln(rand(0, 1)))，其中rand(0, 1)是从均匀分布（0, 1]中抽取的随机数。
删除时采用类似的方法。我们从顶层开始，直到底层逐层删除目标。
HNSW中的复杂性
HNSW中的搜索、插入和删除的时间复杂度取决于多个因素，包括架构的高度、每个节点的邻居节点数和距离度量。但平均而言，搜索、插入和删除的时间复杂度是O(log n)。构建HNSW可能会很昂贵。我们需要以O(log n)的复杂度插入n个节点。因此，图构建的整体时间复杂度为O(n log n)。
向量数据库用于处理数亿维嵌入。索引这么多的数据需要高效、稳定和可扩展的算法。HNSW满足所有这些要求。
HNSW的缺点
尽管HNSW中的搜索、插入和删除速度更快，但在选择HNSW之前，您需要了解一些权衡。在实施HNSW之前，请牢记以下几点。
- 更高的内存占用：HNSW维护嵌入的分层结构，这会显著增加内存消耗，与NSW等算法相比。这可能会对资源受限设备造成问题。
- 参数调整：HNSW具有不同的可调参数。需要仔细调整参数以提高性能。
- 难度：从零开始实现HNSW可能会变得棘手。大多数向量数据库使用可信的预构建解决方案，如FAISS或HNSWlib。
HNSWlib：仅包含头文件的HNSW实现
HNSWlib是HNSW算法的仅包含头文件的C++实现，并带有Python绑定。它由HNSW论文的作者Yury Malkov编写。这是算法的简明实现。
那么，让我们开始吧。
您可以使用任何Python软件包管理器安装HNSWlib。
pip install hnswlib声明并初始化HNSW索引。
import hnswlib
import numpy as np
import pickle
dim = 16
num_elements = 100
hnsw_index = hnswlib.Index(space='l2', dim=dim) ＃声明索引
hnsw_index.init_index(max_elements=num_elements, ef_construction=200, M=16) - space参数是用于计算节点之间距离的距离度量。 Python实现支持平方L2、余弦和点积。
- dim参数是嵌入向量的维度
- init_index方法用于初始化索引。
- ef_construction定义了速度/准确性的构建时间/准确性的权衡。
- M是在插入节点期间创建的双向链接的数量。
现在我们已经创建了索引，让我们添加一些向量。
data1 = np.float32(np.random.random((num_elements, dim)))
ids1 = np.arange(num_elements)
data2 = np.float32(np.random.random((100, dim)))
ids2 = np.arange(100)
data3 = np.float32(np.random.random((100, dim)))
ids3 = np.arange(100)
hnsw_index.add_items(data1, ids1)
hnsw_index.add_items(data2, ids2)
hnsw_index.set_ef(50) ＃设置查询时间速度/准确性的权衡
hnsw_index.set_num_threads(4) ＃设置批处理构建期间的线程数 现在，让我们看看如何查询k个近似最近邻。
labels, distances = p.knn_query(data, k=1) 使用pickle对索引对象进行序列化。
p_cp = pickle.loads(pickle.dumps(hnsw_index)) 删除元素。
for id in ids2:
hnsw_index.mark_deleted(id) 这将从索引中释放最后100个元素。如果您愿意，您还可以重用删除元素的内存。
hnsw_index.add_items(data3, labels3, replace_deleted=True) 结论
HNSW是目前开发向量检索方法的最重要的算法之一。它是所有主要向量数据库中使用的主要索引算法。希望通过本文，您已经理解了HNSW的工作原理。随着人工智能的发展，我们将看到更大、更复杂的学习模型的发展，这将增加使用HNSW的需求，并增加其应用和重要性。
要点
- 向量数据库是针对存储高维向量嵌入的专门设计的数据存储。
- 嵌入的索引使得向量存储可以处理嵌入的查询、插入和删除。
- 有不同的向量索引方式，如IVF、Annoy、Quantization和HNSW。
- HNSW是两个算法的组合。跳表和可导航的小世界（NSW）。
常见问题
本文中显示的媒体不归Analytics Vidhya所有，仅基于作者的判断使用。
