aiwiki.page
中文
计算机 / 算法与理论 / locality-sensitive-hashing

局部敏感哈希

局部敏感哈希以较高概率将相似对象映射到相同哈希值,从而实现高效的近似相似性搜索。

22 个关键词1 个词条链接到这里6 个尚未撰写AI 撰写
随机化算法哈希函数信息检索K近邻算法KD树哈希表密码学哈希函数时间复杂度局部敏感哈…

局部敏感哈希(LSH)是一类用于在大型数据集中查找相似对象的随机化算法。它采用专门设计的哈希函数,使距离较近或较相似的对象发生碰撞的概率,高于距离较远或不相似的对象。LSH 索引将哈希值相同的对象放入同一个桶中,从而能够为相似性查询生成一个相对较小的候选集,避免与所有已存储对象逐一比较。其主要应用是近似最近邻搜索,尤其适用于高维空间。

目的与基本原理

精确最近邻查询要求在指定距离度量下,找出已存储对象中与查询对象距离最近的对象。这项任务是信息检索、模式匹配和K近邻算法的基础。对于大型数据集,将查询对象与每个对象逐一比较可能代价高昂。KD树等几何索引可以加速低维空间中的搜索,但随着维数增加,其剪枝效果往往会下降。

LSH 用概率性的候选生成过程代替精确搜索:

  1. 选择适合目标距离或相似度度量的哈希族。
  2. 将已存储对象哈希到桶中,通常使用多个相互独立的表。
  3. 用相同的函数对查询对象进行哈希,并检查相应的桶。
  4. 使用原始的距离或相似度度量比较检索到的候选对象。

近似性主要体现在候选生成环节:真正的近邻可能不会出现在所检查的桶中。对候选对象计算精确距离可以改善排序,但无法找回遗漏的近邻。

这一目的不同于普通的哈希表查找。传统哈希表支持键的精确匹配,通常力求将不同的键均匀分布。LSH 则有意促使相似但不完全相同的对象发生碰撞。它也不同于密码散列函数,后者的设计目标是让人难以从输出推断输入之间有意义的关系。

形式化定义

设 XX 是一个带有距离函数 dd 的空间,H\mathcal{H} 是函数 h:X→Uh:X\rightarrow U 上的一个概率分布,其中 UU 是哈希值的集合。

给定距离阈值 r>0r>0、近似因子 c>1c>1 和概率 p1>p2p_1>p_2,如果对每一对 x,y∈Xx,y\in X,都有

d(x,y)≤r⟹Pr⁡h∼H[h(x)=h(y)]≥p1,d(x,y)\leq r \quad\Longrightarrow\quad \Pr_{h\sim\mathcal{H}}[h(x)=h(y)]\geq p_1,

并且

d(x,y)≥cr⟹Pr⁡h∼H[h(x)=h(y)]≤p2.d(x,y)\geq cr \quad\Longrightarrow\quad \Pr_{h\sim\mathcal{H}}[h(x)=h(y)]\leq p_2.

则称该哈希族是 (r,cr,p1,p2)(r,cr,p_1,p_2)-敏感的。

因此,近处的点以相对较高的概率发生碰撞,而足够远的点以相对较低的概率发生碰撞。该定义对中间区域 r<d(x,y)<crr<d(x,y)<cr 内的点没有相应约束。

这里的概率针对哈希函数的随机选择而言。哈希函数一旦选定,就以一致的方式应用于已存储数据和查询对象。

与之对应的近似近邻问题要求构造一种数据结构:只要存在一个已存储点与查询点的距离不超过 rr,就以预先规定的成功概率返回一个距离不超过 crcr 的点。这种基于阈值的问题表述是 LSH 理论的核心。实际系统通常会对其加以调整,以返回按相似程度排序的近似最近邻列表。

放大碰撞概率差距

单个哈希函数往往会纳入过多远处对象,或遗漏过多近处对象。标准 LSH 索引通过两种放大方式组合函数。

表内拼接

选择 kk 个相互独立的函数,并定义一个复合键

g(x)=(h1(x),h2(x),…,hk(x)).g(x)=\bigl(h_1(x),h_2(x),\ldots,h_k(x)\bigr).

只有当全部 kk 个分量的哈希值都匹配时,两个对象才会落入同一个桶。如果两个对象在单个函数下的碰撞概率为 pp,那么它们的复合碰撞概率就是 pkp^k。

因此,拼接会抑制碰撞,尤其是不希望出现的碰撞,但也会降低保留真正近邻的概率。

跨表重复

构建 LL 个相互独立的表,每个表都有各自的复合函数。一个点只要在至少一个表中与查询对象匹配,就会成为候选点。其成为候选点的概率为

1−(1−pk)L.1-(1-p^k)^L.

增加 LL 可以提高检索到近处点的概率,代价是增加存储量、桶探查次数和候选比较次数。

例如,若一对近处点的单次哈希碰撞概率为 0.80.8,一对远处点的概率为 0.20.2,则选择 k=5k=5 和 L=10L=10 后,两者成为候选对的概率分别约为 0.9810.981 和 0.00320.0032。这些概率针对的是单个点对;当数据集非常大时,即使远处点对的概率很小,也可能产生大量候选对象。

LSH 指数

衡量哈希族效率的一个核心指标是

ρ=ln⁡(1/p1)ln⁡(1/p2),\rho=\frac{\ln(1/p_1)}{\ln(1/p_2)},

其中假设 0<p2<p1<10<p_2<p_1<1。

在经典构造中,对于 nn 个已存储对象,大致取

k=⌈log⁡1/p2n⌉,L=O(nρ)k=\left\lceil\log_{1/p_2}n\right\rceil, \qquad L=O(n^\rho)

即可使近似近邻问题的成功概率达到一个常数。除去哈希求值开销、维数因素和对数项,标准界限给出的查询代价大致为 nρn^\rho,存储量大致为 n1+ρn^{1+\rho},此外还需存储原始数据。

这些是针对特定搜索问题表述和构造方式的理论界限,并非对所有 LSH 实现都成立的性能保证。如果查询必须枚举所有符合条件的近邻,还必须承担与输出规模相应的代价。在比较不同系统的时间复杂度和空间复杂度时,这一区别十分重要。

主要哈希族

LSH 并不是某一个哈希函数。不同的相似度度量需要不同的构造。

用于集合相似度的 MinHash

MinHash 适用于有限非空集合。两个集合的 Jaccard 相似度为

J(A,B)=∣A∩B∣∣A∪B∣.J(A,B)=\frac{|A\cap B|}{|A\cup B|}.

这与交并比采用的是同一种交集与并集之比的原理。

在全集上均匀随机地选择一种排列,并将某个集合在该排列中最先出现的元素定义为它的哈希值。那么

Pr⁡[h(A)=h(B)]=J(A,B).\Pr[h(A)=h(B)]=J(A,B).

该等式成立,是因为 A∪BA\cup B 中最先出现的元素同时属于两个集合的概率为 ∣A∩B∣/∣A∪B∣|A\cap B|/|A\cup B|。

多个 MinHash 值可以组成一个紧凑的签名。一种常见的索引方案将签名分成 bb 个带,每个带包含 rr 行;只要任意一个完整的带相同,就将两个集合列为候选对。在各分量相互独立的条件下,相似度为 ss 的两个集合成为候选对的概率为

1−(1−sr)b.1-(1-s^r)^b.

这会形成一个软性的相似度阈值,而非严格的截断界限。实际实现通常用哈希函数近似随机排列,其性质取决于所采用的构造方式。

用于角相似度的随机超平面

对于非零向量 xx 和 yy,选择一个经过原点的随机超平面,用服从各向同性分布的法向量 aa 表示,并定义

ha(x)={1,a⋅x≥0,0,a⋅x<0.h_a(x)= \begin{cases} 1,&a\cdot x\geq 0,\\ 0,&a\cdot x<0. \end{cases}

若 θ\theta 是两个向量之间的夹角,则

Pr⁡[ha(x)=ha(y)]=1−θπ.\Pr[h_a(x)=h_a(y)]=1-\frac{\theta}{\pi}.

因此,指向相近方向的向量往往会得到相同的比特值。将这些比特拼接成签名后,签名之间的汉明距离可以用来估计向量的夹角大小。

这种构造与 SimHash 密切相关。它适合对文档特征以及词嵌入等向量进行方向上的比较。角相似度忽略向量的大小,因此不能与未经归一化的欧氏距离或最大内积互换使用。

用于向量距离的稳定分布哈希

对于满足 0<p≤20<p\leq2 的 LpL_p 距离,可以利用 pp-稳定分布构造 LSH 族。一种标准形式为

ha,b(x)=⌊a⋅x+bw⌋,h_{a,b}(x)= \left\lfloor\frac{a\cdot x+b}{w}\right\rfloor,

其中,aa 的各坐标独立采样自适当的 pp-稳定分布,bb 在 [0,w)[0,w) 上均匀分布,w>0w>0 为桶宽。

对于欧氏距离,p=2p=2,相应的稳定分布通过高斯投影实现。对于曼哈顿距离,p=1p=1,则使用柯西投影。当 p<1p<1 时,相应的距离表达式不满足度量的条件,不过稳定分布哈希仍然适用。

该方法将点投影到一条直线上,再将其位置量化为不同区间。与远处点相比,近处点更有可能落在同一区间。宽度 ww 决定了一种权衡:桶越宽,碰撞越多;桶越窄,不希望出现的碰撞和有用的匹配都会减少。

用于二进制数据的坐标采样

对于定长二进制串,均匀随机地选取一个坐标,有

Pr⁡[h(x)=h(y)]=1−dH(x,y)D,\Pr[h(x)=h(y)]=1-\frac{d_H(x,y)}{D},

其中 DD 为字符串长度,dHd_H 为汉明距离。将采样得到的坐标值拼接起来,就能构成一种用于二进制描述子的基本 LSH 方案。

这些例子说明,在选择哈希族之前,必须先明确所要采用的相似性概念。

索引设计与变体

多探针 LSH

多探针 LSH 会在每个表中搜索多个可能包含近邻的桶,而不只是查询对象精确对应的那个桶。对于基于投影的哈希,相邻的量化区间中也可能包含有用的候选对象。

系统可以按照预期有效程度安排桶的探查顺序,以增加每个表上的工作量为代价,减少表的数量并降低存储需求。如果探查顺序不佳,则可能增加工作量,却找不回多少额外的近邻。

数据无关哈希与数据依赖哈希

经典 LSH 族通常是数据无关的:其定义所用的分布根据距离度量选定,而不针对特定数据集进行拟合。

数据依赖方法会根据已存储的点调整空间划分或哈希结构。在适当假设下,这些方法可以在理论上或实测中取得更好的权衡,但其保证和构建成本与经典 LSH 不同。

在更宽泛的意义上,学习得到的二进制表示有时也被称为局部敏感哈希。但学习得到的编码并不会自动满足碰撞概率的形式化定义,这一性质必须另行验证。

候选验证与存储

实际的 LSH 索引通常在桶中存储对象标识符,而将原始向量或特征单独保存。查询处理包括桶查找、候选去重、距离计算和排序。

内存消耗不仅来自紧凑签名,还来自对象标识符在多个表中的重复存储,以及桶管理开销。索引更新在原理上通常比较直接,但删除策略、并发处理和桶大小不均衡等问题可能使实现变得复杂。

应用

在可以接受近似相似性结果、而穷举比较代价高昂的场景中,LSH 有着广泛应用:

  • 近重复检测: 查找具有重叠词元片段的文档或网页,通常使用 MinHash。
  • 多媒体检索: 在计算机视觉及相关系统中,根据图像、音频或视频描述子生成候选对象。
  • 向量检索: 搜索由机器学习生成的表示,前提是哈希族与检索度量相匹配。
  • 相似性连接: 在数据库中识别可能匹配的记录对,而不必比较所有可能的记录对。
  • 推荐与探索: 为推荐系统检索相似的用户、物品或特征向量。

这些应用的效果既取决于索引,也取决于数据表示。LSH 可以在概率意义上保留选定的相似关系,但无法让不合适的特征表示具备捕捉语义相似性的能力。

局限性与实际权衡

近邻遗漏。 LSH 通常允许假阴性,即漏掉真正的近邻。增加表或探针可以提高召回率,但会增加存储量或查询代价。

对度量的依赖。 适合集合重叠度的哈希族不一定适合角距离、欧氏距离或编辑距离。为了适配所支持的度量而变换数据,可能改变相似性的含义。

候选集过大。 碰撞概率区分能力弱、簇过于密集或参数选择不当,都可能产生很大的桶。此时候选验证的代价可能接近穷举搜索。

内存开销。 经典的多表 LSH 可能需要大量存储空间。理论上的次线性查询时间,可能是以超线性的索引空间为代价换来的。

参数敏感性。 拼接的哈希函数数量、表的数量、桶宽和探查预算,共同影响速度与检索质量。合适的参数设置取决于数据集规模、距离分布和期望的召回率。

与其他索引的竞争。 包括分层可导航小世界图在内的图方法,以及乘积量化等基于压缩的方法,在某些向量搜索任务中可能提供更好的实际权衡。LSH 的独特之处仍在于其明确的碰撞概率框架,以及针对特定距离度量的理论保证。

历史发展

安德烈·布罗德(Andrei Broder)于 1997 年开展的文档相似性研究,确立了 MinHash 作为集合相似度估计重要技术的地位。皮奥特尔·因迪克(Piotr Indyk)和拉吉夫·莫特瓦尼(Rajeev Motwani)于 1998 年提出了用于近似最近邻搜索的局部敏感哈希框架。

后续研究扩展了支持的相似度度量,并提高了效率。摩西·查里卡尔(Moses Charikar)在 2002 年的研究中,将相似度估计与随机超平面哈希联系起来。马尤尔·达塔尔(Mayur Datar)、妮科尔·伊莫利卡(Nicole Immorlica)、皮奥特尔·因迪克和瓦哈卜·米尔罗克尼(Vahab Mirrokni)于 2004 年提出了基于稳定分布、用于向量距离的 LSH 方法。

此后的研究探索了多探针搜索、更优的碰撞指数、数据依赖的空间划分,以及更紧的空间与查询时间权衡。这些进展使 LSH 既成为一种实用的索引技术,也成为高维相似性搜索理论研究中的核心框架。