局部敏感哈希(LSH)是一类用于在大型数据集中查找相似对象的随机化算法。它采用专门设计的哈希函数,使距离较近或较相似的对象发生碰撞的概率,高于距离较远或不相似的对象。LSH 索引将哈希值相同的对象放入同一个桶中,从而能够为相似性查询生成一个相对较小的候选集,避免与所有已存储对象逐一比较。其主要应用是近似最近邻搜索,尤其适用于高维空间。
目的与基本原理
精确最近邻查询要求在指定距离度量下,找出已存储对象中与查询对象距离最近的对象。这项任务是信息检索、模式匹配和K近邻算法的基础。对于大型数据集,将查询对象与每个对象逐一比较可能代价高昂。KD树等几何索引可以加速低维空间中的搜索,但随着维数增加,其剪枝效果往往会下降。
LSH 用概率性的候选生成过程代替精确搜索:
- 选择适合目标距离或相似度度量的哈希族。
- 将已存储对象哈希到桶中,通常使用多个相互独立的表。
- 用相同的函数对查询对象进行哈希,并检查相应的桶。
- 使用原始的距离或相似度度量比较检索到的候选对象。
近似性主要体现在候选生成环节:真正的近邻可能不会出现在所检查的桶中。对候选对象计算精确距离可以改善排序,但无法找回遗漏的近邻。
这一目的不同于普通的哈希表查找。传统哈希表支持键的精确匹配,通常力求将不同的键均匀分布。LSH 则有意促使相似但不完全相同的对象发生碰撞。它也不同于密码散列函数,后者的设计目标是让人难以从输出推断输入之间有意义的关系。
形式化定义
设 是一个带有距离函数 的空间, 是函数 上的一个概率分布,其中 是哈希值的集合。
给定距离阈值 、近似因子 和概率 ,如果对每一对 ,都有
并且
则称该哈希族是 -敏感的。
因此,近处的点以相对较高的概率发生碰撞,而足够远的点以相对较低的概率发生碰撞。该定义对中间区域 内的点没有相应约束。
这里的概率针对哈希函数的随机选择而言。哈希函数一旦选定,就以一致的方式应用于已存储数据和查询对象。
与之对应的近似近邻问题要求构造一种数据结构:只要存在一个已存储点与查询点的距离不超过 ,就以预先规定的成功概率返回一个距离不超过 的点。这种基于阈值的问题表述是 LSH 理论的核心。实际系统通常会对其加以调整,以返回按相似程度排序的近似最近邻列表。
放大碰撞概率差距
单个哈希函数往往会纳入过多远处对象,或遗漏过多近处对象。标准 LSH 索引通过两种放大方式组合函数。
表内拼接
选择 个相互独立的函数,并定义一个复合键
只有当全部 个分量的哈希值都匹配时,两个对象才会落入同一个桶。如果两个对象在单个函数下的碰撞概率为 ,那么它们的复合碰撞概率就是 。
因此,拼接会抑制碰撞,尤其是不希望出现的碰撞,但也会降低保留真正近邻的概率。
跨表重复
构建 个相互独立的表,每个表都有各自的复合函数。一个点只要在至少一个表中与查询对象匹配,就会成为候选点。其成为候选点的概率为
增加 可以提高检索到近处点的概率,代价是增加存储量、桶探查次数和候选比较次数。
例如,若一对近处点的单次哈希碰撞概率为 ,一对远处点的概率为 ,则选择 和 后,两者成为候选对的概率分别约为 和 。这些概率针对的是单个点对;当数据集非常大时,即使远处点对的概率很小,也可能产生大量候选对象。
LSH 指数
衡量哈希族效率的一个核心指标是
其中假设 。
在经典构造中,对于 个已存储对象,大致取
即可使近似近邻问题的成功概率达到一个常数。除去哈希求值开销、维数因素和对数项,标准界限给出的查询代价大致为 ,存储量大致为 ,此外还需存储原始数据。
这些是针对特定搜索问题表述和构造方式的理论界限,并非对所有 LSH 实现都成立的性能保证。如果查询必须枚举所有符合条件的近邻,还必须承担与输出规模相应的代价。在比较不同系统的时间复杂度和空间复杂度时,这一区别十分重要。
主要哈希族
LSH 并不是某一个哈希函数。不同的相似度度量需要不同的构造。
用于集合相似度的 MinHash
MinHash 适用于有限非空集合。两个集合的 Jaccard 相似度为
这与交并比采用的是同一种交集与并集之比的原理。
在全集上均匀随机地选择一种排列,并将某个集合在该排列中最先出现的元素定义为它的哈希值。那么
该等式成立,是因为 中最先出现的元素同时属于两个集合的概率为 。
多个 MinHash 值可以组成一个紧凑的签名。一种常见的索引方案将签名分成 个带,每个带包含 行;只要任意一个完整的带相同,就将两个集合列为候选对。在各分量相互独立的条件下,相似度为 的两个集合成为候选对的概率为
这会形成一个软性的相似度阈值,而非严格的截断界限。实际实现通常用哈希函数近似随机排列,其性质取决于所采用的构造方式。
用于角相似度的随机超平面
对于非零向量 和 ,选择一个经过原点的随机超平面,用服从各向同性分布的法向量 表示,并定义
若 是两个向量之间的夹角,则
因此,指向相近方向的向量往往会得到相同的比特值。将这些比特拼接成签名后,签名之间的汉明距离可以用来估计向量的夹角大小。
这种构造与 SimHash 密切相关。它适合对文档特征以及词嵌入等向量进行方向上的比较。角相似度忽略向量的大小,因此不能与未经归一化的欧氏距离或最大内积互换使用。
用于向量距离的稳定分布哈希
对于满足 的 距离,可以利用 -稳定分布构造 LSH 族。一种标准形式为
其中, 的各坐标独立采样自适当的 -稳定分布, 在 上均匀分布, 为桶宽。
对于欧氏距离,,相应的稳定分布通过高斯投影实现。对于曼哈顿距离,,则使用柯西投影。当 时,相应的距离表达式不满足度量的条件,不过稳定分布哈希仍然适用。
该方法将点投影到一条直线上,再将其位置量化为不同区间。与远处点相比,近处点更有可能落在同一区间。宽度 决定了一种权衡:桶越宽,碰撞越多;桶越窄,不希望出现的碰撞和有用的匹配都会减少。
用于二进制数据的坐标采样
对于定长二进制串,均匀随机地选取一个坐标,有
其中 为字符串长度, 为汉明距离。将采样得到的坐标值拼接起来,就能构成一种用于二进制描述子的基本 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 既成为一种实用的索引技术,也成为高维相似性搜索理论研究中的核心框架。