跳过导航

Vector向量检索学习

前提-向量是怎么判断相似的

向量是一串数字 [2,3,5] .

  1. 向量的“长相”与“含义”

• 几何视角：一个包含 N 个数字的向量，可以看作是在一个 N 维空间 中的一个点。

• 例如，一个二维向量 [3, 4] 就是在平面坐标系中，X坐标为3，Y坐标为4的一个点。

• 一个三维向量 [1, 2, 3] 就是在三维空间中的一个点。

• 虽然我们无法直观想象768维、1024维的空间，但数学上它们是完全一样的概念。

• 物理意义：在现代机器学习中，这串数字（这个高维空间的点）代表了一个对象的“特征”。

• 一张图片 → 通过神经网络模型 → 输出一个 512 维的向量。这个向量编码了图片的视觉特征。

• 一段文本 → 通过文本模型 → 输出一个 768 维的向量。这个向量编码了文本的语义信息。

核心思想：我们希望，含义/内容相近的物体，在向量空间里的“点”也离得近。

  1. 如何衡量“离得近”？—— 距离度量

既然把物体变成了空间中的点，那么判断“是否相似”就变成了计算空间中两个点之间的距离。距离越小，越相似。

主要有以下几种距离（或相似度）度量方法：

2.1 欧几里得距离

• 最直观的距离，就是两点之间的直线距离。

• 公式：d = sqrt( (x1-y1)² + (x2-y2)² + … + (xn-yn)² )

• 几何意义：我们在中学学的平面和三维空间中的距离，在高维空间的直接推广。

• 适用场景：非常通用。在向量各维度含义明确，且数值大小有直接可比性时常用。

例子： 向量 A = [1, 2, 3] 向量 B = [4, 5, 6] 欧氏距离 = sqrt((1-4)² + (2-5)² + (3-6)²) = sqrt(27) ≈ 5.2

2.2 余弦相似度

• 这衡量的是两个向量在方向上的差异，而不是它们在空间中的绝对位置差异。

• 公式：cos(θ) = (A·B) / (|A| * |B|)

• 其中 A·B 是点积：(A1B1 + A2B2 + … + An*Bn)

• |A| 是向量 A 的模长：sqrt(A1² + A2² + … + An²)

• 结果范围：-1 到 1。

• 1：方向完全相同（夹角0度），最相似。

• 0：相互垂直，无关。

• -1：方向完全相反，最不相似。

• 关键特性：对向量的绝对大小不敏感，只关心方向。

• 比如，一篇长文章和一篇短文章，如果主题相同，它们的向量方向可能很接近，但模长（反映文本长度）相差很大。余弦相似度依然能判断它们主题相似。

例子： 向量 A = [1, 2, 3] 向量 B = [2, 4, 6] // B 是 A 的两倍 余弦相似度 = (12+24+3*6) / (sqrt(1+4+9) * sqrt(4+16+36)) = 28 / (sqrt(14)*sqrt(56)) ≈ 0.999 几乎为1，表明方向几乎一致。但它们的欧氏距离其实很大。

2.3 内积

• 就是点积：A·B = A1B1 + A2B2 + … + An*Bn

• 在向量经过归一化（模长变为1）后，内积 = 余弦相似度。

归一化 特指将向量的模长（长度）变为1，但方向保持不变。这个过程也称为“单位化”或“L2归一化”。

• 很多向量数据库（如 Facebook 的 Faiss）的默认相似度度量是内积，因为它计算速度快。

2.4 曼哈顿距离

• 也叫“L1距离”。

• 公式：d = |x1-y1| + |x2-y2| + … + |xn-yn|

• 想象在曼哈顿街区，你不能斜着穿楼，只能沿方格走。它是各维度坐标差绝对值之和。

  1. 向量相似性搜索要解决的核心问题

现在我们把场景具体化：

  1. 你有 1亿张图片，每张图片都被编码成了一个 512 维的向量。
  2. 用户上传一张新图片，也得到一个 512 维的向量。
  3. 问题：从1亿个向量中，找出最相似（比如欧氏距离最近或余弦相似度最高）的 10个向量。

暴力破解法： • 将新向量与1亿个向量逐个计算相似度。

• 时间复杂度：O(1亿 * 512次运算)。

• 结果：虽然准确，但慢到无法接受（可能需要数秒甚至更久）。

近似最近邻搜索的目标： • 用 HNSW、IVF、LSH 这类算法，建立索引。

• 不再追求100%精确找到最近的点，而是用极短的时间（比如几毫秒）找到99%可能是最近的那些点。

• 牺牲一点点精度，换来百倍、千倍的速度提升。

总结与类比

• 向量：对象的“数学指纹”。

• 向量空间：所有“指纹”构成的抽象空间。

• 相似度：两个“指纹”在空间中的距离（欧氏距离）或朝向的接近程度（余弦相似度）。

• HNSW要解决的问题：在一个有海量指纹的庞大档案馆里，当拿到一个新指纹时，如何避免和档案馆里每一个指纹都比对，而是用巧妙的方法（多层导航图）快速锁定一小部分最可能相似的候选指纹，只和这一小部分进行精确比对。

所以，HNSW 的强大之处在于：它不需要理解向量每个维度的具体含义（比如第127维代表“猫耳朵的弧度”），它只需要一个数学规则（距离计算公式）和一种聪明的数据结构（层次化小世界图），就能在海量点中快速导航。

HNSW 算法

好的，我来为你详细解释 HNSW 算法。

HNSW 是一种用于高效近似最近邻搜索的图索引算法，其全称是 Hierarchical Navigable Small World graphs（可导航小世界层次图）。

  1. 核心思想与背景

要解决的问题：在海量高维数据中，如何快速找到与目标向量最相似的 K 个向量？传统的精确搜索计算量大，无法满足实时性要求。

核心思路：HNSW 结合了两个重要的思想： • 可导航小世界图：构建一种“小世界网络”，其中大部分节点是局部连接的，但包含少量“高速公路”式的长距离连接，使得从任意节点出发，都能快速“导航”到目标区域。

• 层次化结构：将图分层，顶层是稀疏的、包含“高速公路”的图，底层是稠密的、用于精确搜索的图。搜索时从顶层开始，快速锁定大致区域，然后逐层细化。

  1. 算法工作原理

2.1 图的结构

• 多层结构：HNSW 维护一个图的层级结构 L=0,1,2,…。

• 顶层稀疏，底层稠密：L=0 层是底层，包含所有节点，且连接最稠密。越往上层，节点越随机、越稀疏，连接也越少。

• 节点选择：一个节点出现在第 l 层的概率是 1 / M^l，其中 M 是参数。这意味着大部分节点只在底层，越往上越“精英化”。

2.2 插入新节点

插入一个新向量 q 的步骤：

  1. 确定最高层：用 floor(-ln(uniform(0,1)) * mL) 公式随机决定 q 出现的最高层 l_max。

  2. 逐层搜索入口点：从最高层开始，找到该层中距离 q 最近的节点 ep 作为入口点。

  3. 逐层插入： • 从当前层向下，到第 0 层为止：

    a. 执行贪婪搜索，找到当前层中离 q 最近的节点。 b. 以该节点为基础，在下层找到与 q 最近的若干个节点（比如 efConstruction 个）作为候选邻居。 c. 从候选邻居中，按某种启发式规则（如“最远优先”或“简单选择”）挑选出最多 M 个邻居，与 q 建立双向连接。

2.3 搜索（查找最近邻）

给定一个查询向量 q 和参数 efSearch：

  1. 从顶层开始：从顶层（最稀疏）的入口点开始搜索。
  2. 贪婪搜索：在当前层，从一个候选集（初始为入口点）出发，反复查找候选集中点的邻居，如果邻居比当前候选点更近，就将其加入候选集，并继续探索，直到无法找到更近的点。
  3. 进入下一层：将当前层找到的最优点作为下一层的入口点，重复上述过程。
  4. 在底层进行精细搜索：到达底层（L=0）后，使用同样的贪婪搜索，但这次会维护一个大小为 efSearch 的动态候选列表，最终返回列表中最近的 K 个点。

直观比喻：就像你要在全世界找一个地址： • 顶层：先看世界地图，确定大致是“亚洲-中国”。

• 中间层：看中国地图，确定是“北京市”。

• 底层：看北京市区地图，找到具体街道和门牌号。

  1. 关键参数

• M：每个节点在每层最多连接的邻居数。控制图的稠密度和搜索质量/速度的平衡。

• efConstruction：构建索引时，为每个节点考察的候选邻居数。值越大，构建的图质量越高，但构建时间越长。

• efSearch：搜索时动态维护的候选列表大小。值越大，搜索精度越高，但速度越慢。

• mL：控制节点被分配到更高层的概率的参数。

  1. 优缺点

优点： • 查询速度极快：在亿级高维数据集上能达到毫秒级响应。

• 高召回率：在合适的参数下，能找到与真实最近邻非常接近的结果。

• 支持增量插入：可以在已有索引上动态插入新数据，无需重建整个索引。

• 内存效率相对较高：相比其他基于树或哈希的方法，内存占用可控。

缺点： • 索引构建较慢：因为要构建多层图结构。

• 参数敏感：M, efConstruction, efSearch 等参数需要根据数据集调整以达到最佳效果。

• 内存占用：需要存储整个图和所有向量，对于极大数据集仍需较多内存。

  1. 典型应用场景

  2. 推荐系统：根据用户向量寻找相似商品/内容。

  3. 图像/视频检索：以图搜图、以文搜图。

  4. 自然语言处理：语义搜索、相似句查找。

  5. 异常检测：寻找与正常模式差异最大的点。

简单总结

HNSW 就像一个“有高速路的多层社交网络”： • 底层是所有人的朋友圈（连接密集，用于精确查找）。

• 顶层是“社会名人”组成的网络（连接稀疏，但能快速跳转到不同圈子）。

• 搜索时，先从名人网络问路，快速定位到大致圈子，然后逐层深入，最终在底层朋友圈里找到你要的人。

这种设计让它在大规模高维向量搜索任务中，性能显著优于传统的树结构（如KD-Tree）和早期的图方法（如NSW）。

rust 基础

基本算法导引

太棒了，这种“由点及面”的切入方式非常符合 AI Infra 的工程逻辑。

在开始编写 Rust 向量检索算法（HNSW）之前，我们先对 AI Infra 的资源消耗（Resource Utilization） 做一次深度扫描。在 Infra 领域，快只是基本要求，省和稳才是核心竞争力。

1. AI Infra 视角：向量检索中的资源消耗细节

在实现算法时，请时刻带上这三个“成本紧箍咒”：

  • 内存带宽与局部性 (Memory Bandwidth): 向量检索本质是大量的浮点数运算。如果数据在内存中散乱分布，CPU 会频繁等待数据从内存加载到缓存（Cache Miss）。
    • 观察点： 你的向量是连续存储（如 Vec<f32>）还是对象嵌套？
  • 计算密度 (Compute Density): 简单的 for 循环计算余弦相似度是非常低效的。
    • 观察点： 是否利用了 SIMD (单指令多数据流)？一次指令能否处理 4 个或 8 个浮点数？
  • 并发争抢 (Lock Contention): HNSW 在构建索引时是多线程的。
    • 观察点： 插入节点时，细粒度的读写锁（RwLock）是否会导致大量线程切换？

2. 第一步：Rust 实现向量检索（HNSW）的步骤拆解

HNSW（分层导航小世界）是目前最主流的向量索引算法。我们将其拆解为四个阶段：

第一阶段：基础数学与数据结构 (Day 1-2)

不要急着写图算法，先打好 Rust 的高性能基础。

  • 定义特征 (Trait): 定义一个 Distance trait，实现 L2 距离（欧氏距离）和 Cosine 距离。
  • SIMD 优化： 使用 Rust 的 std::arch 或者 ndarray 库，对比普通循环和 SIMD 优化后的距离计算性能差异。
  • 数据容器： 思考如何存储千万级向量？（先用 Vec，后续考虑 mmap）。
第二阶段：构建单层概率图 (NSW) (Day 3-5)

HNSW 的基础是 NSW（导航小世界）。

  • 查找最近邻： 实现简单的贪心搜索（Greedy Search），在图中寻找距离目标向量最近的点。
  • 插入逻辑： 当新向量进入时，如何选择它的“邻居”？这里涉及到一个重要的参数 M（每个节点的最大连接数）。
  • 启发式算法： 学习如何通过“启发式选择”来保证图的连通性，防止出现孤岛。
第三阶段：实现多层结构 (Hierarchical) (Day 6-10)

这是 HNSW 名字中 “H” 的来源。

  • 概率层级分配： 每个点以指数衰减的概率决定它最高能出现在哪一层。
  • 多层导航： 从最高层开始快速定位大致区域，逐层向下精细搜索。
  • 并发控制： 使用 parking_lot 库提供的更高效的锁，或者研究如何用无锁（Lock-free）跳表思路处理层级切换。
第四阶段：Go 侧对接准备 (Day 11+)
  • C 接口导出： 学习编写 extern "C" 函数。
  • 序列化： 实现索引的持久化（把图和向量存入文件），这样 Go 调用时直接加载文件。

3. 你的第一个代码作业：高性能距离计算

在实现 HNSW 之前，AI Infra 工程师的第一课是：如何把距离计算做到极致？

请尝试在 Rust 中实现以下逻辑，并观察性能：

// 目标：计算两个 f32 数组的欧氏距离平方
// 进阶要求：尝试使用 `rayon` 库进行并行计算，或者查看 `pulp` 库来实现 SIMD
pub fn euclidean_distance(a: &[f32], b: &[f32]) -> f32 {
    a.iter()
        .zip(b.iter())
        .map(|(x, y)| (x - y).powi(2))
        .sum()
}

细化思考题： 如果向量维度是 768（Llama 系列常用维度），上述代码在循环中会产生多少次内存寻址？如果使用 Rust 的 autovectorization（自动向量化），编译器能帮我们优化到什么程度？

建议下一步： 你可以先尝试写一个简单的向量结构体和这个距离函数，如果你准备好了，我们可以开始讨论 HNSW 的层级概率分配逻辑 该怎么写。

返回博客列表