局部敏感哈希

在一个由海量数据集定义的时代，寻找一个相似项——无论是一份文档、一张图片，还是一条基因序列——这个简单的行为已经成为一项巨大的挑战。传统的暴力搜索方法，即将查询项与数据库中的每一个项进行比较，在处理数十亿甚至数万亿数据点时，计算上是不可行的。这种“维度灾难”要求我们采用一种更智能的方法，一种能够在不进行详尽扫描的情况下找到近似最近邻的方法。这正是局部敏感哈希（LSH）所优雅解决的问题。LSH 是一种革命性的概率技术，它颠覆了传统哈希的概念。它并非避免碰撞，而是巧妙地设计碰撞，创建了一个系统，使得相似项比不相似项更有可能被哈希到同一个桶中。

本文对这一强大的方法进行了全面的探讨。在第一章 ​​“原理与机制”​​ 中，我们将深入研究使 LSH 发挥作用的核心概念。您将学习到如何利用简单的几何和概率思想，例如随机超平面和排列，来构建对相似度敏感的哈希函数。我们还将揭示使 LSH 变得实用和有效的放大技术背后的工程巧思。随后的 ​​“应用与跨学科联系”​​ 章节将展示 LSH 巨大的现实世界影响力。我们将遍览其在驯服网络、驱动现代人工智能和推荐系统、以及为计算生物学和医学等领域的科学发现提供新工具中的应用，揭示一个单一的计算机科学概念如何为解决不同领域的相似性搜索问题提供一个统一的框架。

任何搜索算法的核心都有一个基本的比较问题：这个项是我正在寻找的那个吗？几个世纪以来，这意味着直接、逐一地检查。要在一个拥有一百万卷藏书的图书馆中找到与 Moby Dick 最相似的书，原则上，你必须将它与每一本其他的书进行比较。这是一种​​暴力搜索​​，即线性扫描，虽然它保证结果正确，但其成本与数据库的大小 $N$ 呈线性关系。对于现代的海量数据集，其中 $N$ 可能达到数十亿或数万亿，这不仅缓慢，而且是不可能的。

局部敏感哈希为我们提供了一种极其巧妙的方法来摆脱这种线性时间的束缚。它通过颠覆传统哈希函数的核心思想来实现这一点。在计算机科学中，我们被教导一个“好”的哈希函数，比如在字典或哈希表中使用的那种，应该不惜一切代价避免碰撞。它应该尽可能随机和均匀地散列数据。LSH 提出了相反的观点：如果我们设计的哈希函数有意地引起碰撞呢？如果我们能将其设计成使得相似项比不相似项更有可能发生碰撞呢？如果能做到这一点，我们就不需要将查询项与每个项进行比较了。我们只需要将它与恰好落入同一个哈希桶中的项进行比较。这个小的项集合就是我们的​​候选集​​。因此，搜索问题就从扫描整个图书馆简化为只检查一个小小书架。

让我们不要从令人眼花缭乱的高维空间开始我们的旅程，而是在一条简单的一维数轴上开始。假设我们的数据由这条线上的点组成，两点 $x$ 和 $y$ 之间的距离就是它们的间隔，$d = |x - y|$。我们如何设计一个能让邻近点发生碰撞的哈希函数呢？

想象我们有一堆尺子，每把尺子都有整数间隔的刻度：$0, 1, 2, 3, \dots$。现在，我们拿起这样一把尺子，不是将其起始的“0”刻度放在原点，而是将其随机平移一个量 $b$，这个 $b$是从区间 $[0, w)$ 中均匀选择的，其中 $w$ 是我们尺子分段的宽度。对于线上的任意点 $x$，我们现在可以将其哈希值定义为它所落入的分段编号。在数学上，这由函数 $h_{b,w}(x) = \lfloor \frac{x + b}{w} \rfloor$ 给出。

两个点 $x$ 和 $y$ 发生碰撞，即 $h_{b,w}(x) = h_{b,w}(y)$ 的概率是多少？当且仅当在我们随机平移的尺子上，没有整数刻度落在 $x$ 和 $y$ 之间时，才会发生碰撞。想象一下：如果 $x$ 和 $y$ 非常接近，它们之间的间隔 $d = |x-y|$ 很小。尺子上的刻度落入这个微小间隔的几率很小。随着它们相距越来越远，间隔变宽，刻度就越来越有可能将它们分开，导致它们有不同的哈希值。

两点之间的间隔长度，用我们的桶宽进行缩放，是 $\frac{d}{w}$。如果这个长度大于或等于 1 (即 $d \ge w$)，那么无论我们如何平移尺子，这个区间都保证至少包含一个整数刻度。在这种情况下，碰撞是不可能的，概率为 0。但如果 $d w$，这个区间比一个单位短。它可能包含一个刻度，也可能不包含，完全取决于随机平移量 $b$。一点点几何学知识表明，在这种情况下发生碰撞的概率恰好是 $1 - \frac{d}{w}$。

综合这些情况，碰撞概率由下式给出：

$p(d) = \max(0, 1 - \frac{d}{w})$

这个简单的公式体现了 LSH 的灵魂。当距离为 $0$ 时（相同的点总是碰撞），碰撞概率为 $1$，然后线性下降，直到对于距离为 $w$ 或更大的点，概率降为 $0$。我们成功地创建了一个“局部敏感”的哈希函数。

数轴是一个很好的热身，但现实世界的数据很少如此简单。一幅数字图像可能是一个包含数百万像素值的向量。一份文本文档可以表示为一个拥有数万维度的空间中的向量，其中每个维度对应词汇表中的一个词。在这些高维空间中，我们对距离的直觉可能会完全失效。这就是臭名昭著的​​“维度灾难”​​。

我们究竟如何将我们简单的尺子思想扩展到这样一个复杂的领域？由 Moses Charikar 发现的答案是一个极其优雅和强大的思想，用于处理以向量间夹角（​​余弦相似度​​）来衡量相似度的向量。我们不再使用随机的尺子，而是使用一个随机的超平面。

想象一下我们的高维空间，所有的数据向量都从原点指出。现在，生成一个随机向量 $\mathbf{r}$，并画一个穿过原点且与 $\mathbf{r}$ 垂直的平面（一个超平面）。这一个超平面将整个无限空间干净利落地切成两半。我们现在可以定义一个非常简单的哈希函数：如果一个向量 $\mathbf{x}$ 位于平面的一侧（例如，它与 $\mathbf{r}$ 的点积为非负数），我们给它分配哈希位 $1$；如果它位于另一侧，我们给它分配哈希位 $0$。数学上表示为 $h_{\mathbf{r}}(\mathbf{x}) = \operatorname{sign}(\mathbf{r} \cdot \mathbf{x})$。

两个向量 $\mathbf{u}$ 和 $\mathbf{v}$ 碰撞的概率是多少？如果它们落在这个随机超平面的同一侧，它们就发生碰撞。思考一下它们之间的夹角 $\theta$。如果 $\mathbf{u}$ 和 $\mathbf{v}$ 非常相似，它们指向几乎相同的方向，夹角 $\theta$ 非常小。那么一个随机超平面恰好穿过它们之间狭窄空间楔子的可能性极小。它们几乎肯定会落在同一侧。随着夹角 $\theta$ 增大，它们指向的方向差异变大，一个随机超平面将它们分开的几率也随之增加。

一个随机超平面分隔两个夹角为 $\theta$ 的向量的概率就是 $\theta/\pi$。因此，它们不被分隔——即碰撞——的概率是：

$P(\text{collision}) = 1 - \frac{\theta}{\pi}$

这是一个惊人的结果。碰撞概率与夹角直接且简单地相关，而夹角是它们不相似度的几何度量。一个纯粹的概率过程让我们直接读出了一个几何属性。

现在让我们转向另一种数据类型：集合。你如何衡量社交网络上两个用户的关注者集合，或者两种不同细胞类型中表达的基因集合之间的相似度？一个极好的度量是​​杰卡德相似度​​，定义为两个集合交集的大小除以它们并集的大小：$J(A,B) = \frac{|A \cap B|}{|A \cup B|}$

为了对集合进行哈希，Andrei Broder 和他的同事们发明了一种名为 ​​MinHash​​ 的方法，它和随机超平面技巧一样优雅。 想象一下所有可能项的宇宙（所有推特用户，所有人类基因）是一副巨大的牌。现在，对这个宇宙应用一个随机排列——也就是说，把这副牌彻底、随机地洗一遍。

对于任何集合 $S$（项的子集），它的“最小哈希值”就是集合 $S$ 中在洗过的牌堆里出现得最早的那个项。

这为什么有用？考虑两个集合 $A$ 和 $B$。让我们看看它们的并集 $A \cup B$。这个并集中的每个元素都有同等的机会成为我们洗过的牌堆中的第一个。现在，它们的最小哈希值相同的概率，即 $\min(A) = \min(B)$ 的概率是多少？这只有在洗过的牌堆中来自 $A \cup B$ 的第一个元素恰好同时属于 $A$ 和 $B$ 时才会发生。换句话说，它必须来自它们的交集 $A \cap B$。

由于 $A \cup B$ 中的每个元素成为最小值的可能性都相等，所以最小元素来自子集 $A \cap B$ 的概率就是它们大小的比率。这导出了一个惊人的结论：

$P(\min(A) = \min(B)) = \frac{|A \cap B|}{|A \cup B|} = J(A,B)$

这个哈希函数的碰撞概率就是杰卡德相似度！我们找到了一个哈希方案，它直接计算了我们感兴趣的那个相似度度量。通过用许多不同的随机洗牌（或在实践中，用模拟洗牌的不同哈希函数）重复这个过程，我们可以通过简单地计算最小哈希值碰撞的次数来得到对杰卡德相似度的一个非常准确的估计。当我们增加哈希函数的数量 $m$ 时，我们估计的方差与 $1/m$ 成比例减小，从而使我们能够调整准确度。

我们已经看到了这些优美的哈希方案，但存在一个实际问题。对于随机超平面哈希，“近”对的概率可能是 $0.9$，而“远”对的概率可能是 $0.6$。对于 MinHash，杰卡德相似度可能是 $0.8$ 和 $0.5$。虽然存在差异，但这并非鸿沟。远对仍然有相当大的碰撞几率。如果我们基于这单个哈希构建候选集，最终会得到太多不相似的项，我们的搜索仍然会很慢。

这正是 LSH 的工程巧思所在。目标是放大这个微小的概率差异——将“稍微更可能碰撞”的耳语，变成“对于近对几乎肯定碰撞，对于远对几乎肯定不碰撞”的呐喊。这是通过一个称为 ​​AND-OR 构造​​ 的两步技巧实现的。

1. ​​AND 构造（分带）：​​ 我们不使用单个哈希函数（一个超平面，一次洗牌），而是使用一个由 $\alpha$ 个独立哈希函数组成的“带”（band）。我们定义一次碰撞，仅当两个项在所有 $\alpha$ 个哈希函数上同时匹配。这使得碰撞的总体可能性大大降低。如果单次碰撞的概率是 $p$，那么在 $\alpha$ 个函数上发生 AND 碰撞的概率是 $p^{\alpha}$。这个新的概率函数要陡峭得多。一个高概率 $p_1$ 和一个低概率 $p_2$ 之间的小差异会被放大；例如，如果 $p_1=0.9$ 和 $p_2=0.6$，我们选择 $\alpha=10$，新的概率就变成了 $0.9^{10} \approx 0.35$ 和 $0.6^{10} \approx 0.006$。差距被极大地拉开了！

2. ​​OR 构造（多表）：​​ AND 技巧通常过于严格。我们现在可能会因为真正的最近邻恰好由于运气不好而未能在所有 $\alpha$ 个哈希函数上匹配而错过它们。为了解决这个问题，我们重复整个过程 $L$ 次，创建 $L$ 个独立的哈希表，每个表都有自己的一组 $\alpha$ 个哈希函数。现在，如果两个项在至少一个这样的 $L$ 个表中发生碰撞，我们就将它们声明为候选者。得到候选者的概率现在是 $1 - (1 - p^\alpha)^L$。

这个双参数 $(\alpha, L)$ 方案非常强大。通过调整这两个旋钮，我们可以将整体的概率曲线塑造成一个陡峭的“S”形。对于相似度高的项，这条曲线接近 $1$；对于相似度低的项，它骤降至接近 $0$。这使得 LSH 能够生成一个以高概率包含真正最近邻的小候选集，从而有效地节省了大量昂贵的距离计算。

我们已经探索了针对不同数据类型——线、向量、集合、二进制码——的不同 LSH 方案。每种方案都有其优雅的机制。但是否有一个宏大的、统一的理论来支配它们呢？确实有。

对于任何 LSH 族，我们可以定义两个关键参数：$p_1$，即“近”项（在某个距离 $r$ 内的项）的碰撞概率；以及 $p_2$，即“远”项（超出距离 $cr$ 的项，其中 $c>1$ 是近似因子）的碰撞概率。LSH 的整个游戏都依赖于 $p_1 p_2$ 这个事实。

任何基于 LSH 的搜索算法的理论性能都由一个单一的、神奇的数字，即指数 $\rho$ (rho) 决定，定义为：

$\rho = \frac{\ln p_1}{\ln p_2}$

由于概率小于 1，它们的对数是负数，所以 $\rho$ 是一个正数。并且因为 $p_1 > p_2$，我们有 $|\ln p_1| |\ln p_2|$，这保证了 $\rho 1$。

这个指数 $\rho$ 告诉了我们一切。基于 LSH 的搜索的查询时间大约是 $O(N^{\rho})$。由于 $\rho 1$，这代表了亚线性的查询时间，打破了维度灾难，并胜过了暴力搜索的 $O(N)$。$\rho$ 的值越小，搜索就越快。当 $p_1$ 高而 $p_2$ 非常低时——也就是说，当我们的哈希族非常擅长区分近和远时——就能实现一个小的 $\rho$。

但这种能力并非没有代价。这就引出了所有近似搜索方法的基本权衡。为了得到一个更小的 $\rho$（从而更快的搜索），我们需要 $p_1$ 和 $p_2$ 之间有更大的差距。对于大多数 LSH 族，创造一个大的概率差距需要接受一个大的近似因子 $c$。换句话说，为了让搜索更快，我们可能不得不放宽对“近”的定义。在另一个极端，如果我们要求一个近乎完美的近似（$c \to 1$），那么 $p_1$ 和 $p_2$ 变得几乎相等，$\rho$ 接近 $1$，查询时间就退化回 $O(N)$。天下没有免费的午餐。局部敏感哈希的精妙之处不在于消除了这种权衡，而在于提供了一种形式化的、可调节的、并且极其有效的方式来驾驭它。

既然我们已经摆弄过局部敏感哈希的引擎，并理解了其内部齿轮的运作，现在就让我们开着它去兜兜风。这台巧妙的机器能带我们去哪里？事实证明，答案是几乎所有有数据存在的地方。我们已经看到，LSH 的魔力不在于哈希本身，而在于一种非常特殊的类型的哈希。一个标准的哈希函数，我们可能称之为“通用”哈希，被设计成一个出色的搅乱器；它的目标是把任意两个项，无论它们多么相似，都扔到哈希表中随机、遥远的位置，以避免碰撞。这就像一个图书管理员纯粹随机地摆放书籍，以确保没有两本书会挨在一起。

但 LSH 恰恰相反。它是一位会阅读每本书精髓并将相似书籍放在一起的图书管理员。它的目的是为相似的项创造有意的碰撞。这种目标的简单逆转——从避免碰撞到拥抱碰撞——将哈希从一种简单的存储技巧转变为一种强大的发现工具。这把钥匙开启了广阔的应用前景，从在网络上发现抄袭行为到识别拯救生命的癌症治疗方法。

也许 LSH 最直观的用途是整理互联网这个巨大而混乱的图书馆。想象一下，你的任务是在数十亿网页的语料库中找到所有近似重复的文档。对每一对文档进行暴力比较所需的时间将超过宇宙的年龄。这正是 LSH 凭借 MinHash 技术大放异彩的地方。

首先，我们必须教会计算机对于文档来说“相似性”意味着什么。一种极其简单而有效的方法是将每份文档分解为一组称为“shingles”的短小的、重叠的字符序列。如果两份文档共享很高比例的这些 shingles，那么它们就被认为是相似的，这种关系通过杰卡德相似度来衡量。然后，MinHash 算法为每个文档的 shingle 集合生成一个短小的、固定大小的“签名”。这个签名是压缩的杰作；它是一个微小的指纹，保留了杰卡德相似度的信息。其魔力在于，两个签名的相似度是对原始的、大得多的文档相似度的一个极好估计。有了这些紧凑的指纹，LSH 就可以通过确保它们的指纹在同一个哈希桶中碰撞来快速地将相似的文档分组，让我们能用比暴力方法少得多的时间找到近似重复项。

这种“感知指纹”的思想远不止于文本。考虑在大型照片数据库中查找重复或视觉上相似的图像的问题。我们不能简单地比较原始像素数据，因为一次简单的裁剪、缩放或颜色调整就会使两张视觉上相同的图像在像素层面上完全不同。取而代之的是，我们为每张图片计算一个“感知哈希”（pHash）——一个捕捉其基本视觉特征的签名。现在，如果两个图像的 pHash 比特串之间的汉明距离很小，它们就被认为是相似的。LSH 也可以适应这个领域。通过基于图像 pHash 的一部分进行哈希，我们可以建立一个系统，让视觉上相似的图像很可能发生碰撞。这就产生了一个根本性的权衡：一个更具选择性的哈希（使用 pHash 的更多位）会减少我们必须检查的随机候选者的数量，但也有错过真正重复项的风险。工程师必须仔细调整这些参数来平衡搜索速度和准确性，这是任何真实世界 LSH 部署中的核心挑战。

在设计这些指纹方面的创造力，在音频领域或许表现得最为淋漓尽致。像 Shazam 这样的应用是如何仅凭几秒钟的音频就在嘈杂的酒吧里识别出一首歌的？它使用了一种受 LSH 启发的绝妙方案。歌曲首先被转换成频谱图，这是一个其频率内容随时间变化的视觉地图。然后算法识别出“峰值强度”——就像夜空中的星座。关键的洞见不是对峰值本身进行哈希，而是对成对的峰值进行哈希：它们的频率和它们之间的时间差。这创建了一种对噪声具有鲁棒性的哈希，而且最重要的是，它与歌曲中的绝对时间无关。副歌中的一个片段会产生许多与你音乐库中相同副歌相同的哈希值，从而导致碰撞和成功匹配。

在现代人工智能的世界里，数据通常不是生活在三维空间中，而是生活在数百或数千维空间中。一个词、一个人对电影的品味，或一个用户的购物习惯，都可以表示为一个高维“嵌入空间”中的向量。在这些空间中，距离意味着相似性——不是外观上的，而是意义或功能上的。在这个广阔的空间中导航是一个核心挑战，而 LSH 提供了一个至关重要的指南针。

考虑一下理解语言的挑战。像 Word2Vec 这样的技术学习单词的向量表示，其中语义关系通过几何方式被捕捉；例如，king 和 queen 之间的向量关系与 man 和 woman 之间的几乎相同。要找到意义相近的词，我们必须找到在这个空间中“接近”的向量，通常通过它们之间的小夹角（高余弦相似度）来衡量。使用 LSH 的随机超平面方法，我们正能做到这一点。每个哈希函数都是一条穿过原点的随机直线（或平面、或超平面），将空间一分为二。一个向量的哈希码就是一串比特，告诉我们它落在了这些随机平面的哪一侧。两个夹角很小的向量很可能落在大多数平面的同一侧，从而产生相同的哈希码并发生碰撞。这使我们能够构建“语义搜索引擎”，根据意义而不仅仅是关键词来查找单词（或整个文档）。

正是这个相同的原理驱动着现代推荐系统。在协同过滤系统中，用户和物品（如电影或产品）都被嵌入到一个共享的高维空间中作为向量。用户的向量代表他们的偏好，物品的向量代表其特性。为了向你推荐一部电影，系统需要找到与你的用户向量相近的电影向量。对于数百万用户和数百万物品，详尽搜索是不可能的。LSH 是使这变得可行的关键技术之一，它能迅速识别出一小组有希望的候选者来进行推荐。它如此基础，以至于它被用作基准，来衡量更新、更复杂的近似最近邻（ANN）搜索算法，例如基于图的 HNSW。这些现代比较揭示了一个动态的领域，其中索引构建时间、内存使用和查询速度之间的权衡正在不断地被重新评估。

一个基础科学思想的真正美妙之处在于其跨越学科的力量。为一个领域开发的抽象概念可能突然成为另一个领域的完美工具，揭示了问题结构中潜在的统一性。

让我们回到我们用来寻找重复文档的 MinHash 技术。现在，考虑一位在蛋白质组学领域工作的生物学家。他们使用质谱仪分析蛋白质样本，产生复杂的光谱——其中肽段的“指纹”。为了识别蛋白质，他们必须将这个实验光谱与一个庞大的已知肽谱数据库进行匹配。如果我们将每个光谱表示为其最显著的质荷比峰值的集合，问题就变成了找到数据库中与查询集具有最高杰卡德相似度的集合。这与寻找重复文档的问题完全相同！同样的 MinHash 和 LSH 机制可以被部署，无需修改，来解决计算生物学中的一个问题，在数百万个光谱中筛选，几秒钟内找到一个潜在的匹配。

LSH 的影响也延伸到了临床领域。在计算医学中，研究人员可能会分析脑肿瘤的 MRI 扫描，提取如大小、形状和纹理等形态学特征，并将它们表示为三维特征空间中的一个点。医生可能希望找到过去具有结构相似肿瘤的患者，以帮助制定预后或治疗计划。在这里，相似性是通过简单的欧几里得距离来衡量的。为此，使用了一个不同的 LSH 函数族，它基于用随机平移的网格覆盖空间。在空间中彼此接近的点，对于给定的随机平移，有很高的概率落入同一个网格单元，从而发生碰撞。通过使用多个独立的、随机平移的网格，我们可以可靠地在这个特征空间中找到近邻，为数据驱动的医学提供了一个强大的工具。这是一个深刻的提醒，即使“特征”可能不同——单词、图像、基因或肿瘤——但按相似性搜索的根本挑战依然存在，而 LSH 为解决这一挑战提供了一个统一的框架。

为了结束我们的旅程，让我们看一个巧妙地颠覆 LSH 用途的前沿应用。在联邦学习领域，多方（例如医院）希望协同训练一个机器学习模型，而无需共享他们敏感的私有数据。每一方都在其本地数据上计算对模型的“更新”，表示为一个高维向量。中央服务器需要聚合这些更新，但如何在不看到它们的情况下智能地做到这一点呢？

在这里，LSH 不仅可以用于搜索，还可以作为一种增强隐私的聚合工具。每一方发送的不是他们的更新向量，而是它的 LSH 哈希值。服务器无法从哈希值中重建原始更新。然而，如果两方的更新相似，它们的哈希值很可能碰撞。服务器可以观察到这些碰撞，并决定将产生相同哈希值的客户端的更新分组，或许将它们平均以创建一个更稳健的聚合更新。在这里，碰撞是全部的重点——它们在不泄露原始数据本身的情况下揭示了相似性结构。这为平衡效用和隐私开辟了迷人的新途径，使得在以前不可能的敏感数据上进行协作成为可能。

从组织世界知识到开启隐私机器学习的下一个前沿，局部敏感哈希的应用与其操作的数据一样多种多样。这段旅程向我们展示了一个单一、优美思想的深远力量：通过巧妙地设计碰撞，我们可以教会计算机不仅从 0 和 1 的角度，而且从相似性的不同层次来感知世界。