如何平衡向量检索速度和精度?深度解读HNSW算法

8c9f913622e0e0c46566d818a65f7bb5.png

1202c82f19d1b3d02626d6f56520f91b.png

向量检索(向量相似性搜索)是AI时代最重要的技术之一。其典型应用场景包括:推荐系统、检索增强生成(RAG)等高级GenAI应用。

向量检索最突出的优势是准确性和速度。

过去,向量搜索通常是用暴力扫描的方式来找到和查询向量最近的K个邻居(kNN)。它的核心思想是比对查询向量和库内所有向量的距离,简单直观但计算量大。也就是说,如果内存中有100个文档,kNN算法将计算查询向量与100个文档向量的相似度或距离。因此kNN的优势在于可以获得精确的搜索结果,但缺陷则是在检索时间与数据规模成正比。因此在处理数百万级以上数据规模时,成本、效率、速度都会遇到极大瓶颈。

4e2ec7163ff20cbb92b5162ed22df9c8.jpeg

图:kNN算法工作流程

在本文,我们将介绍一个基于Hierarchical Navigable Small World(HNSW)算法实现的HNSWlib的向量检索库。

01.

什么是向量检索

解读HNSWlib之前,我们需要对什么是向量检索先有一个基本的概念。

向量检索是信息检索中的一种常用方法,用于从大量非结构化数据集(图像、文档、音频等)中找到与给定查询最相似的信息。顾名思义,文档和查询都被表示为高维向量空间中具有特定维度的向量。向量的维度取决于用于转换文档和查询的Embedding模型。例如,如果我们使用“all-MiniLM-L6-v2”作为Embedding模型,每个查询或文档将获得384个维度的向量。

在查询时,Embedding模型会将查询内容,转化为文档中已有的语义维度,然后进行计算,相似含义的内容在向量空间中的位置更加靠近,然后返回其中最高相似性得分(或最短距离)的内容,这就是向量检索背后的逻辑。

6b6d7f0c7cffbe59d5d3102ec2e4dd03.png

图:2D向量空间中相似单词的向量嵌入

02.

什么是HNSW

近些年,为了优化kNN的检索性能,业内已经开发了各种索引算法,HNSW就是最有效的算法之一。

HNSW是一种基于图的高效向量检索算法。它依赖于两个关键概念:跳表(Skip List)和可导航小世界(NSW)图。

其中,跳表是一种概率数据结构,由多层链表组成,层次越高,链表中跳过的元素就越多。正如下面的可视化图,最低层包含了链表中的所有元素。随着我们向更高层移动,链表逐渐跳过越来越多的元素,所剩下的元素就越来越少。

b7a4dc9d4f8ad1d9ce1e74b2b34632f9.png

图:跳表工作流程

假设我们需要从有3层和8个元素的原始链表中查找元素7。首先,我们从最高层开始,检查第一个元素是否低于7。如果是,那么我们检查第二个元素。如果第二个元素高于7,那么我们将第一个元素用作较低层的起点。接下来,我们在较低层做完全相同的事情,并逐渐下降到最低层以找到所需的元素。在许多元素上的跳过过程使得跳表在执行搜索操作时非常快。

理解了跳表的基本概念之后,我们再来看看NSW图。

NSW图中,每个节点(或称为顶点)都会与相似的节点相连,组成一张完整的NSW图。其检索的底层逻辑是贪婪路由搜索,从任意节点开始,检索起相邻节点中与其更加相似的节点,然后转移到该节点,过程循环往复,直到找到局部最小值,即当前节点比之前访问的任何节点都更接近查询向量,此时停止搜索。

2ec487997eca0502676a013e7a81ee2d.png

图:NSW 图创建过程

HNSW算法,结合了跳表和NSW图的优势于一体。HNSW不仅仅是一个简单的二维图,而是由几层图所组成的多图层结构。与跳表概念类似,图的最低层包含所有元素,层越高,跳过的元素就越多。

在图创建过程中,HNSW首先为每个元素分配一个从0到 I 的随机数,其中 I 是一个元素在多层图中能存在的最大层。如果一个元素的 I 等于2,并且总层数为4,那么这个元素将从第0层一直存在到第2层,但不存在于第3层。

2140a7d9ee8d52bc32bd7fae584d1a44.png

图:使用HNSW算法的向量检索

在向量检索过程中,HNSW算法首先选择最高层的任意节点,然后通过NSW图检索到局部最小值,紧接着,相同的流程在下一层重复,逐步逼近目标节点,直到找到最接近查询向量的节点。

通过这一方法,HNSW算法不必检索那些离查询点较远的相关度较低的元素,进而增加了检索的效率。这也导致了HNSW并不适用于精确匹配,因为HNSW在搜索过程中跳过了一些元素,当然,其他的近似最近邻(ANN)方法,如FAISS或ScaNN也是一样。

那么如何在不需要精确匹配结果,但仍然希望获得相对高效的召回时,我们要怎么办?我们可以调整HNSW的超参数:

  • M:NSW图中每个元素的边数。较高的M值通常会对应更好的搜索精度,但代价是更慢的索引构建时间。

  • efConstruction:构建索引时的动态候选列表大小。一般来说,候选队列越长,索引质量越好,索引构建时间也就会越长。

  • efSearch:搜索阶段的动态候选列表的大小。一般来说,efSearch越高,召回率越高,但是搜索过程会比较慢。

除了速度与精度的权衡之外,我们还需要注意图创建过程中的内存消耗。这是因为HNSW要求将整个数据集加载到RAM中,如果您的数据集太大而无法放入内存中,就会导致比较尴尬的情况发生。比如,M值越高,我们就需要分配越多存储资源用于每个元素相邻信息的存储。此外,随着元素和其相邻信息被添加到图中,内存需求会呈线性增长。因此,在图创建过程中,微调M和efConstruction至关重要,特别是在大规模应用中。

整体来说,HNSW具有对数复杂度O(log N)和高召回率,并支持动态更新,无需重建索引即可添加新数据。然而,与其他ANN算法相比,HNSWlib也具有更高的内存消耗,索引构建时间较慢,缺乏对元素删除的原生支持。

72912d000a9629306659f2afc03fb26c.png

但与其他ANN方法相比,HNSW在大型数据集上的表现依然非常具有竞争力。

参考下面的GIST1M数据集(具有960维的1M向量)上的ANN基准测试,HNSW效果整体好于FAISS,Annoy,pgector等,特别是当需要高召回率时。排名上,其表现只在Milvus的Knowhere和Zilliz Cloud的Glass算法之后,获得了前三名的成绩。

426b2fe7c7d83c9a6f501cf3c0c2ae70.png

图:GIST1M数据集的ANN基准测试结果

HNSWlib 是一个基于 C++ 的开源 HNSW 算法实现。用途上,HNSWlib 非常适合为向量检索用例构建简单场景,并不适合如1亿甚至数十亿数据点这样的复杂场景检索。

因为HNSWlib是一个功能有限的轻量级ANN库,会随着数据点的增长,因为内存消耗问题,导致出现扩展性瓶颈。

因此,在大规模应用中,使用像Milvus这样的向量数据库将是更好的选择。向量数据库作为一种成熟的解决方案,能够高效地存储大量数据并执行有效的向量检索。例如,Milvus支持云原生和多租户服务,允许用户从云上的多个用户存储、索引和检索数百万甚至数十亿个数据点。

当然,HNSWlib也可以被集成到Milvus这为代表的向量数据库中,接下来我们将展示这一过程。

03.

如何将HNSWlib与Milvus的集成

第一步,通过pip install安装HNSWlib:

pip install hnswlib

接下来,让我们创建100个虚拟数据点,每个数据点的维度为128。接下来,我们构建M为8,efConstruction为25的HNSW图。最后,我们计算查询数据点的最近邻。

import hnswlib
import numpy as np
import pickledim = 128
num_elements = 100# Generating sample data
data = np.float32(np.random.random((num_elements, dim)))
ids = np.arange(num_elements)# Generating query point
query = np.float32(np.random.random((1, dim)))# Declaring index
p = hnswlib.Index(space = 'l2', dim = dim) # possible options are l2, cosine or ip# Initializing index - the maximum number of elements should be known beforehand
p.init_index(max_elements = num_elements, ef_construction = 25, M = 8)# Element insertion (can be called several times):
p.add_items(data, ids)# Controlling the recall by setting ef:
p.set_ef(50) # ef should always be > k# Query dataset, k - number of the closest elements (returns 2 numpy arrays)
labels, distances = p.knn_query(query, k = 1)

这就是我们实现原生HNSWlib所要做的一切。

接下来,让我们看看如何在Milvus中使用HNSW集成。

使用Milvus的最简单方法是通过Milvus Lite(Milvus的轻量级版本,可以导入到您的Python应用程序中),我们可以使用pip install安装它。

!pip install -U pymilvus
!pip install pymilvus[model]

现在我们可以从创建集合并定义索引方法开始。首先,我们定义一个集合模式,指定HNSW作为索引方法,Milvus将自动在幕后使用HNSW。然后,我们可以开始将数据插入到集合中进行索引构建。

from pymilvus import MilvusClient, DataType
from pymilvus import modelclient = MilvusClient("demo.db")# 1. Create schema
schema = MilvusClient.create_schema(auto_id=False,enable_dynamic_field=False,
)# 2. Add fields to schema
schema.add_field(field_name="id", datatype=DataType.INT64, is_primary=True)
schema.add_field(field_name="vector", datatype=DataType.FLOAT_VECTOR, dim=768)
schema.add_field(field_name="text", datatype=DataType.VARCHAR, max_length=200)# 3. Prepare index parameters
index_params = client.prepare_index_params()# 4. Add indexes
index_params.add_index(field_name="vector", index_type="HNSW",metric_type="L2"
)# Create collection
if client.has_collection(collection_name="demo_collection"):client.drop_collection(collection_name="demo_collection")client.create_collection(collection_name="demo_collection",schema=schema,index_params=index_params
)# Define embedding model
embedding_fn = model.DefaultEmbeddingFunction()# Text data to search from.
docs = ["Artificial intelligence was founded as an academic discipline in 1956.","Alan Turing was the first person to conduct substantial research in AI.","Born in Maida Vale, London, Turing was raised in southern England.",
]# Transform text data into embeddings
vectors = embedding_fn.encode_documents(docs)data = [{"id": i, "vector": vectors[i], "text": docs[i]}for i in range(len(vectors))
]# Insert embeddings into Milvus
res = client.insert(collection_name="demo_collection", data=data)Finally, if we want to perform vector search, we can do the following:SAMPLE_QUESTION = "What's Alan Turing achievement?"
query_vectors = embedding_fn.encode_queries([SAMPLE_QUESTION])res = client.search(collection_name="demo_collection",  data=query_vectors,  limit=1,  output_fields=["text"],)context = res[0][0]["entity"]["text"]

04.

结论

向量检索在需要准确度和速度的现代AI应用中非常重要。虽然kNN暴力搜索通过穷举搜索提供高度准确的结果,但其线性时间复杂度使其在大规模数据集上不切实际。

HNSW算法通过使用多层次图结构,在速度和准确性之间提供了创新的解决方案。通过结合跳表和NSW图,HNSW实现了快速、近似的搜索,可以有效处理海量数据集此外,通过微调超参数(如M、efConstruction和efSearch),我们可以根据每个应用所需的搜索速度、准确性和内存消耗这三者之间进行权衡优化。实际使用中,我们可以将HNSWlib集成到Milvus向量数据库优化我们的使用体验。

本文作者:Ruben Winastwan

推荐阅读

8ff36120693192956ee29d6fa9bda443.png

6cb525845a72b74133ad5c70aca90bbf.png

2c96afd18840d684ef4802a51b74c57e.png

01e608f6684bb675a5a743d7f29e8690.png

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/490789.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python的3D可视化库【vedo】2-2 (plotter模块) 访问绘制器信息、操作渲染器

文章目录 4 Plotter类的方法4.1 访问Plotter信息4.1.1 实例信息4.1.2 演员对象列表 4.2 渲染器操作4.2.1 选择渲染器4.2.2 更新渲染场景 4.3 控制渲染效果4.3.1 渲染窗格的背景色4.3.2 深度剥离效果4.3.3 隐藏线框的线条4.3.4 改为平行投影模式4.3.5 添加阴影4.3.6 环境光遮蔽4…

强化学习的学习笔记

什么是强化学习? 强化学习(Reinforcement Learning, RL),又称再励学习、评价学习或增强学习,是机器学习的范式和方法论之一,用于描述和解决智能体(agent)在与环境的交互过程中通过学…

Leetcode42-环形链表

题目 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使…

ElasticSearch 简介

一、什么是 ElastcSearch? ElasticSearch 是基于 Lucene 的 Restful 的分布式实时全文搜索引擎。 1.1 ElasticSearh 的基本术语概念 index 索引 索引类似与 mysql 中的数据库,ES 中的索引是存储数据的地方,包含了一堆有相似结构的文档数据…

【学习笔记】桌面浏览器的视口

概念:设备像素和CSS像素 设备像素:设备物理屏幕的像素分辨率,使用screen.width/height获取 这里有四个像素100%缩放,CSS像素完全覆盖设备像素 缩小后,CSS像素开始缩小,意味着一个设备像素覆盖多个CSS像素…

嵌入式软考学习笔记(1)超详细!!!

目录 第一章计算机系统基础知识 1、逻辑运算 2、数的表示 3、总线系统 5、流水线 6、存储器 7、可靠性、校验码 第一章计算机系统基础知识 1、逻辑运算 与:有0则0,全1才1 或:有1则1,全0才0 异或:相同为0…

FFmpeg功能使用

步骤:1,安装FFmpeg Download FFmpeg 在这里点击->Windows builds from gyan.dev;如下图 会跳到另外的下载界面: 在里面下拉选择点击ffmpeg-7.1-essentials_build.zip: 即可下载到FFmpeg; 使用&#…

接口开发笔记-WebApi

一、基础概念与原理 1、WebAPI的基本概念。 WebAPI是一种基于HTTP协议的网络应用程序接口,它使用JSON或XML格式来传输数据。WebAPI是服务器端应用程序,允许客户端应用程序通过HTTP请求来访问服务器上的数据。WebAPI支持RESTful服务,是构建这…

文件转曲,限制PDF文件编辑的最佳方案!

随着数字化进程的推进,PDF文件凭借其多样化的功能和优越的兼容性已经被广泛使用,成为了现代文档交流和存储的重要工具,满足了不同用户和行业的需求。 虽然PDF格式文件的功能很多,常见的比如阅读、编辑、加密、转换、还可用于印刷…

数据仓库工具箱—读书笔记01(数据仓库、商业智能及维度建模初步)

数据仓库、商业智能及维度建模初步 记录一下读《数据仓库工具箱》时的思考,摘录一些书中关于维度建模比较重要的思想与大家分享🤣🤣🤣 博主在这里先把这本书"变薄"~有时间的小伙伴可以亲自再读一读,感受一下…

分布式 窗口算法 总结

前言 相关系列 《分布式 & 目录》《分布式 & 窗口算法 & 总结》《分布式 & 窗口算法 & 问题》 参考文献 《【算法】令牌桶算法》 固定窗口算法 简介 固定窗口算法是最简单的流量控制算法。固定窗口算法的核心原理是将系统的生命周期划分为一个个…

FireFox火狐浏览器企业策略禁止更新

一直在用火狐浏览器,但是经常提示更新,进入浏览器右上角就弹出提示,比较烦。多方寻找,一直没有找到合适的方案,毕竟官方没有给出禁用检查更新的选项,甚至about:config里都没有。 最终找到了通过企业策略控…

java+springboot+mysql高校社团网

项目介绍: 使用javaspringbootmysql开发的高校社团网,系统包含管理员、学生角色,功能如下: 管理员:登录系统;首页;用户管理;社团分类管理;社团信息管理(社团…

[Maven]构建项目与高级特性

有关于安装配置可以看我的另一篇文章:Maven下载安装配置与简介。 构建项目的生命周期和常用命令 这一节的内容熟记即可,要用了认得出来即可。 在Maven出现之前,项目构建的生命周期就已经存在。对项目进行清理、编译、测试、部署等一系列工作…

多分类交叉熵与稀疏分类交叉熵

总结: 标签为 One-hot 编码的多分类问题,用分类交叉熵对于标签为整数的多分类问题,用稀疏分类交叉熵稀疏分类交叉熵内部会将整数标签转换为 One-hot 编码,而如果标签已经是 One-hot 编码的形式,再使用稀疏分类交叉熵就会多此一举。 算例 假设我们有三个类别:A、B 和 C。…

【学一点儿前端】本地或jenkins打包报错:getaddrinfo ENOTFOUND registry.nlark.com

问题 今天jenkins打包一个项目,发现报错了 error An unexpected error occurred: “https://registry.nlark.com/xxxxxxxxxx.tgz: getaddrinfo ENOTFOUND registry.nlark.com”. 先写解决方案 把yarn.lock文件里面的registry.nlark.com替换为registry.npmmirror.…

前端(模块化)

未使用模块化 定义两个js文件simple1.js和simple2.js let a11; let a11; 两个js文件变量重名 在html测试 传统引入js文件 <script src"./simple1.js"></script> <script src"./simple2.js"></script> 浏览器报错 使用模块…

JAVA入门:文件管理

JAVA入门:文件管理 在学习java之前,首先学习一下java的文件管理,以便后续更好地学习。 创建一个空项目 点击右上角File->New->Module 创建新模块 配置工程环境 点击File->Project Structure 选择project&#

QT:Widgets中的事件

事件的处理 (1)重新实现部件的paintEvent()、mousePressEvent()等事件处理函数。这是最常用的一种方法&#xff0c;不过它只能用来处理特定部件的特定事件。 (2)重新实现notify()函数。这个函数功能强大&#xff0c;提供了完全的控制&#xff0c;可以在事件过滤器得到事件之前…

jvm结构介绍

Java虚拟机&#xff08;JVM&#xff09;是Java平台的核心组件&#xff0c;它负责将Java字节码转换为机器码 1. 类加载子系统&#xff08;Class Loading Subsystem&#xff09;&#xff1a; • 负责将Java类加载到JVM中。这包括从文件系统、网络或其他来源读取.class文件&#x…