高维空间中检索LSH

局部敏感哈希（LSH）在高维空间检索中的应用

小象实战讲义 · 基于深度学习的计算机视觉

在海量高维数据中快速找到相似项，是图像检索、推荐系统等领域的核心挑战。传统的精确最近邻搜索在高维空间中效率低下，而局部敏感哈希（Locality Sensitive Hashing, LSH）提供了一种高效的近似解决方案。本节将深入讲解LSH的原理，特别是基于p-稳定分布的LSH如何将高维空间中的相似性保留到低维哈希值中，并构建高效的索引结构。

💡 核心导读

• LSH的核心思想：设计一种哈希函数，使得相似的数据点以高概率映射到相同的哈希桶（bucket），而不相似的数据点以低概率发生碰撞。
• p-稳定分布：理解高斯分布（p=2）和柯西分布（p=1）如何将高维向量的距离信息“携带”到一维投影中，这是LSH能够保持局部敏感性的数学基础。
• 哈希函数构造：学习如何利用随机投影和分段函数，将高维向量映射为一个整型哈希值。
• 索引构建与查询：掌握通过串联多个哈希函数（g函数）和构建多个哈希表来降低漏报率，并理解查询时“或”逻辑（一个桶命中即候选）的意义。
• 工程实现细节：了解如何将映射后的整型向量进一步转换为哈希表索引和指纹，以平衡检索速度与精度。

从普通哈希到局部敏感哈希

哈希是一种将数据映射到固定长度值（哈希值）的技术，常用于快速查找。普通哈希函数（如MD5、SHA）的设计目标是避免冲突，即希望不同的输入尽可能映射到不同的输出，从而确保数据检索的唯一性和快速定位。

然而，在图像检索等相似性搜索任务中，我们的目标恰恰相反：我们希望相似的图像能够发生冲突，即被映射到同一个哈希桶中。这就是局部敏感哈希（LSH）的设计初衷。

局部敏感哈希被定义为：对于一组哈希函数族，如果满足以下两个条件，则称其为(R1, R2, P1, P2)敏感的：

1. 如果两个数据点O1和O2在原始空间中的距离d(O1, O2) < R1，那么它们哈希值相等的概率Pr[h(O1)=h(O2)] ≥ P1。
2. 如果d(O1, O2) > R2，那么Pr[h(O1)=h(O2)] ≤ P2。

其中R1 < R2, P1 > P2。直白地说，足够相似的数据点，映射后相等的概率要足够大；足够不相似的数据点，映射后相等的概率要足够小。LSH支持多种距离度量，如汉明距离、Lp范数（曼哈顿距离L1、欧氏距离L2）、Jaccard相似系数、余弦相似度等。

p-稳定分布：LSH的数学基石

为了实现上述目标，我们需要一种能够“保持”距离信息的映射方法。p-稳定分布（p-stable distribution）为此提供了关键工具。

p-稳定分布的定义：对于一个实数集R上的分布D，如果存在p ≥ 0，使得对于任意n个实数v1, …, vn和n个服从分布D的独立随机变量X1, …, Xn，随机变量S = Σ_i v_i * X_i（一个点积结果）与随机变量(Σ_i |v_i|^p)^(1/p) * X具有相同的分布（其中X也服从分布D），则称D是一个p-稳定分布。

这个定义比较抽象，我们来看两个最重要的特例：

• 当 p=2 时，p-稳定分布就是高斯分布（正态分布）。
• 当 p=1 时，p-稳定分布就是柯西分布。

p-稳定分布的实用价值在于，它允许我们通过一个简单的点积运算来估计一个向量的p范数长度。具体来说：

• 取一个服从p-稳定分布D的随机向量a（例如，从高斯分布中采样得到的向量）。
• 对于一个高维特征向量v，计算点积a · v，得到一个标量投影值。
• 根据p-稳定分布的性质，这个投影值a · v，与向量v的p范数 ||v||_p = (Σ|v_i|^p)^(1/p) 再乘以一个来自同一分布D的随机变量X，两者是同分布的。

更关键的是，这个性质可以推广到两个向量的距离估计上。假设有两个向量v和u，考虑它们的差向量(v-u)。那么点积a · (v-u)的分布，与差向量的p范数 ||v-u||_p 乘以一个随机变量X是同分布的。这意味着，两个向量在一维投影a·v和a·u上的距离，与它们在高维原始空间中的p范数距离||v-u||_p，在分布上是相关的。距离近的向量，其投影值也倾向于接近。

基于p-稳定分布的LSH函数构造

基于上述原理，我们可以构造一个具体的LSH原子哈希函数h(v)，用于将d维向量v映射到一个整数哈希值。函数定义如下：

h_{a, b}(v) = floor((a · v + b) / r)

其中：

• a：一个d维随机向量，其每一维分量独立地采样自p-稳定分布（例如，对于欧氏距离LSH，使用高斯分布）。
• b：一个在区间[0, r)内均匀分布的随机实数，作为偏移量。
• r：一个正实数，称为“桶宽”（bucket width），用于将连续的投影值离散化到不同的整数桶中。
• floor(·)：向下取整函数。

这个函数的几何解释非常直观：

1. 随机投影：a · v将高维向量v投影到随机向量a所决定的一维直线上。
2. 偏移与分段：加上随机偏移b后，再除以桶宽r并取整，相当于将这条一维直线划分成无数个长度为r的区间（桶），每个区间对应一个唯一的整数值（哈希值）。

由于a · v与||v||_p * X同分布，而||v-u||_p反映了v和u的距离，因此，如果v和u在高维空间中距离很近，那么它们的投影a·v和a·u也很可能落在同一个长度为r的区间内，从而被映射到同一个哈希值（整数桶）。反之，距离远的向量则大概率被映射到不同的桶。

降低漏报率：串联哈希函数与多表索引

单个LSH原子函数h(v)仍有概率将相似的点映射到不同桶（漏报）。为了降低漏报率，我们采用两种策略：

1. 串联（AND构造）形成复合函数g(v) 我们将k个独立的LSH原子函数h1(v), h2(v), …, hk(v)串联起来，形成一个复合函数： g(v) = (h1(v), h2(v), …, hk(v)) 这个g(v)输出一个k维的整型向量。只有当两个向量v和u在全部k个投影上都落入相同的桶时，它们的g(v)值才相等。这提高了判断的严格性，降低了误报（不相似的点被放入同桶）的概率，但可能增加漏报。

2. 并联（OR构造）使用多个g函数（多表索引） 为了补偿串联带来的漏报率增加，我们独立随机地选择L个这样的复合函数g1, g2, …, gL，并构建L个哈希表。

• 索引构建（离线）：对于数据集中的每个向量v，计算其L个g_i(v)值，并将v插入到第i个哈希表中g_i(v)对应的桶里。
• 查询过程（在线）：对于一个查询向量q，同样计算其L个g_i(q)值。然后，只要在任意一个哈希表i中，g_i(q)对应的桶非空，就将该桶内的所有向量都作为候选近邻。这种“或”的逻辑确保了：只要q和某个数据点v在至少一个g_i上哈希值相等，v就会被召回。

通过精心选择k和L，可以在检索精度（召回率）和效率（哈希表大小与查询时间）之间取得平衡。

索引构建的工程细节：从g(v)到哈希表

直接将g(v) = (x1, x2, …, xk)这个k维整型向量作为哈希表的键是不高效的。在实际工程中，通常采用两层哈希将其转换为两个值：index（桶索引）和fingerprint（指纹）。

假设我们有一个g(v)输出的整型向量(x1, x2, …, xk)。

1. 计算桶索引 (index)：目的是快速定位到哈希表中的某个桶（链表或容器）。 index = H1(x1, x2, …, xk) = (Σ_{i=1}^k r_i * x_i) mod C mod table_size 其中r_i是一组随机整数，C是一个大素数（例如在32位系统上可用 $2^{32} - 5$），table_size是哈希表长度。取模运算将结果约束到哈希表范围内。
2. 计算指纹 (fingerprint)：用于在同一个桶内快速判断两个 g(v) 是否真的相同（精确相等校验），避免不同数据产生相同的 index、实际却并不相同的情况。 fingerprint = H2(x1, x2, …, xk) = (Σ_{i=1}^k r‘_i * x_i) mod C 其中r‘_i是另一组随机整数。

在查询时，先通过index快速定位到候选桶，再只保留指纹与查询指纹完全相同的向量（指纹是压缩后的单个整数，做的是相等判断，不是逐位比较），然后进行最终的距离计算和排序。这进一步提升了检索效率。

📝 动手练一练

1. 概念辨析：普通哈希函数（如用于哈希表的哈希）与局部敏感哈希（LSH）的核心设计目标有何根本不同？为什么在图像检索中我们需要LSH而不是普通哈希？

2. 原理理解：在基于p-稳定分布（以p=2高斯分布为例）的LSH中，随机向量a是从高斯分布中采样得到的。假设我们有两个非常相似的128维特征向量v1和v2（例如，v2 = v1 + ε，ε是一个极小的随机噪声向量）。请定性描述，为什么h(v1) = floor((a·v1 + b)/r) 与 h(v2) = floor((a·v2 + b)/r) 相等的概率会很高？

本章小结

本节我们深入探讨了局部敏感哈希（LSH）这一用于高维空间近似最近邻搜索的强大工具。我们从其与普通哈希的本质区别讲起，明确了LSH“利用冲突”来保持数据相似性的核心思想。随后，我们引入了关键的数学概念——p-稳定分布，并揭示了高斯分布和柯西分布如何使得高维向量的距离信息能够通过随机投影得以保留。基于此，我们学习了具体的LSH原子函数构造方法，以及如何通过串联（AND）和并联（OR）构造来平衡检索的精度与召回率。最后，我们了解了工程实践中将哈希值转换为索引和指纹的细节，以构建高效的检索系统。

📋 行动清单

• 理解核心思想：能够清晰阐述LSH如何通过“高概率碰撞相似项”来解决高维近似检索问题，并与普通哈希进行对比。
• 掌握数学原理：理解p-稳定分布（特别是p=2的高斯分布）在LSH中的作用，即建立高维距离与一维投影值之间的概率联系。
• 复现关键步骤：尝试用代码实现基于随机投影的向量映射和简单的桶划分，直观感受相似向量被映射到同一区间的过程。

—— 小象教研组