相似性搜索,第五部分:局部敏感哈希(LSH)

探索如何将相似性信息融入哈希函数

相似性搜索是一个问题,给定一个查询,目标是在所有数据库文档中找到最相似的文档。

介绍

在数据科学中,相似性搜索经常出现在NLP领域、搜索引擎或推荐系统中,需要检索出最相关的文档或物品。存在许多不同的方法来提高大量数据的搜索性能。

在本文系列的之前部分,我们讨论了倒排文件索引、产品量化和HNSW以及它们如何结合使用来提高搜索质量。在本章中,我们将看一种基本不同的方法,它保持了高速和高质量的搜索。

相似性搜索,第3部分:混合倒排文件索引和产品量化

在本系列的前两个部分中,我们讨论了信息检索中的两个基本算法:倒排…

towardsdatascience.com

相似性搜索,第4部分:分层可导航小世界(HNSW)

分层可导航小世界(HNSW)是一种用于近似搜索最近邻的先进算法…

towardsdatascience.com

局部敏感哈希(LSH)是一组方法,用于将数据向量转换为哈希值,同时保留有关它们相似性的信息,从而缩小搜索范围。

我们将讨论传统方法,它包括三个步骤:

  1. Shingling:将原始文本编码为向量。
  2. MinHashing:将向量转换为称为签名的特殊表示形式,可以用于比较它们之间的相似性。
  3. LSH函数:将签名块哈希到不同的桶中。如果一对向量的签名至少在一个桶中相同,则认为它们是候选项。

我们将逐步深入文章中每个步骤的详细信息。

Shingling

Shingling是在给定文本上收集 k-gram 的过程。 k-gram是k个连续的标记组。根据上下文,标记可以是单词或符号。 shingling的最终目标是使用收集的k-gram对每个文档进行编码。我们将使用one-hot编码进行此操作。但是,也可以应用其他编码方法。

Collecting unique shringles of length k = 3 for the sentence “learning data science is fascinating”

首先,收集每个文档的唯一k-gram。其次,为了编码每个文档,需要一个词汇表,它表示所有文档中唯一k-gram的集合。然后,对于每个文档,创建一个长度等于词汇表大小的零向量。对于文档中出现的每个k-gram,确定其在词汇表中的位置,并在文档向量的相应位置放置“1”。即使同一个k-gram在文档中出现多次,也无所谓:向量中的值始终为1。

One-hot encoding

MinHashing

在这个阶段,初始文本已经被向量化。可以通过Jaccard系数比较向量之间的相似度。请记住,两个集合的Jaccard系数定义为两个集合中的共同元素数量除以所有元素的长度。

Jaccard系数定义为两个集合的交集除以并集

如果取一对编码向量,则在Jaccard系数公式中的交集是同时包含1的行数(即k-gram在两个向量中都出现),并集是至少有一个1的行数(k-gram至少在其中一个向量中出现)。

两个向量的Jaccard系数公式
使用上述公式计算两个向量的Jaccard系数的示例

当前的问题是编码向量的稀疏性。计算两个one-hot编码向量之间的相似度得到的将需要很长时间。将它们转换为密集格式将使后续操作更加高效。最终的目标是设计这样一个函数,它将把这些向量转换为较小的维度,并保留它们相似性的信息。构建这样一个函数的方法称为MinHashing。

MinHashing是一种哈希函数,它对输入向量的组成部分进行排列,然后返回排列后向量组成部分等于1的第一个索引。

计算给定向量和排列的minhash值的示例

为了得到由n个数字组成的向量的密集表示,可以使用n个minhash函数来获得n个minhash值,这些值形成一个签名

一开始可能不太明显,但是可以使用多个minHash值来近似两个向量之间的Jaccard相似度。事实上,使用的minHash值越多,近似度就越高。

计算签名矩阵及其用于计算向量间相似度的方式。使用Jaccard相似度和签名计算的相似度通常应该近似相等。

这仅仅是一个有用的观察结果。事实上,背后有一个整个定理。让我们理解为什么可以使用签名来计算Jaccard系数。

定理证明

假设给定的向量对仅包含01、10和11类型的行。然后对这些向量进行随机排列。由于所有行中至少存在一个1,因此在计算两个哈希值时,这两个哈希值计算过程中的至少一个将在具有相应哈希值等于1的向量的第一行停止。

第二个哈希值等于第一个哈希值的概率是多少?显然,只有当第二个哈希值也等于1时才会发生这种情况。这意味着第一行必须是11类型。由于置换是随机进行的,这种事件发生的概率等于P = count(11) / (count(01) + count(10) + count(11))。这个表达式与Jaccard指数公式完全相同。因此:

根据随机行置换获取两个二进制向量相同哈希值的概率等于Jaccard指数

然而,在证明上述语句时,我们假设初始向量不包含00类型的行。很明显,类型为00的行不会改变Jaccard指数的值。同样,包含类型为00的行得到相同哈希值的概率也不会受到影响。例如,如果第一个置换行是00,则MinHash算法会忽略它并切换到下一行,直到至少存在一行中有1。当然,类型为00的行可能会导致与没有它们不同的哈希值,但是获得相同哈希值的概率保持不变。

我们证明了一个重要的语句。但是如何估计获得相同MinHash值的概率?显然,可以生成向量的所有可能置换,然后计算所有MinHash值以找到所需的概率。由于明显的原因,这不是有效的,因为大小为n的向量的可能置换数等于n!。尽管如此,可以近似地评估概率:只需使用许多哈希函数来生成那么多哈希值。

两个二进制向量的Jaccard指数大约等于它们签名中相应值的数量。

数学符号

很容易注意到,采用更长的签名会得到更准确的计算结果。

LSH函数

当前,我们可以将原始文本转换为相等长度的密集签名,保留了有关相似性的信息。尽管如此,在实践中,这些密集签名仍然通常具有高维度,直接比较它们会效率低下。

考虑n = 10⁶个文档及其长度为100的签名。假设一个签名的单个数字需要4个字节来存储,则整个签名将需要400个字节。存储n = 10⁶个文档需要400 MB的空间,这在现实中可行。但是,以暴力方式将每个文档与每个其他文档进行比较将需要大约5 * 10¹¹次比较,这太多了,特别是当n更大时。

为避免这个问题,可以构建哈希表以加速搜索性能,但即使两个签名非常相似并且仅在1个位置上不同,它们仍然可能具有不同的哈希(因为向量余数可能不同)。但是,我们通常希望它们落入相同的桶中。这就是LSH的用处。

LSH机制构建了一个哈希表,其中包含几个部分,如果一对签名具有至少一个相应部分,则将其放入同一个桶中。

LSH将签名矩阵水平分成相等的b部分,称为,每个部分包含r。签名不是将整个签名插入单个哈希函数中,而是将签名分成b个部分,并且每个子签名都由哈希函数独立处理。因此,每个子签名都落入单独的桶中。

使用LSH的示例。将长度为9的两个签名划分为包含r = 3行的b = 3个带。每个子向量都被哈希到k个可能的桶之一。由于第二个带中存在匹配项(两个子向量具有相同的哈希值),因此我们将这些签名对视为最近的邻居候选。

如果两个不同签名的对应子向量之间至少有一个碰撞,那么这些签名就被认为是候选的。正如我们所看到的,这个条件更加灵活,因为为了将向量视为候选,它们不需要完全相等。然而,这会增加误报的数量:一对不同的签名可以有一个对应的部分,但整体上却完全不同。根据问题的不同,优化参数b、r和k总是更好的选择。

错误率

使用LSH,可以估计在每个带中具有b个带和r行的情况下,给定相似度s的两个签名被视为候选的概率。让我们分几步找到公式。

随机行等于两个签名中的一个随机行的概率
随机带与r行相等的概率
随机带与r行不同的概率
表中所有b个带都不同的概率
至少有一个b带相等,因此两个签名是候选者的概率

请注意,该公式不考虑不同子向量意外哈希到同一个存储桶中的碰撞。因此,签名成为候选的实际概率可能微不足道地不同。

例子

为了更好地理解刚刚获得的公式,让我们考虑一个简单的例子。考虑长度为35个符号的两个签名,它们被平均分成5个带,每个带有7行。这里是代表基于它们的Jaccard相似度具有至少一个相等带的概率的表:

概率P,基于相似度s,获得两个签名至少有一个相应带的概率

我们注意到,如果两个相似的签名具有80%的Jaccard相似度,则它们在93.8%的情况下具有相应的带(真正的正例)。在其余的6.2%的情况下,这样一对签名是假负结果。

现在让我们考虑两个不同的签名。例如,它们只有20%的相似度。因此,它们在0.224%的情况下是假阳性的候选者。在其他99.776%的情况下,它们没有相似的带,所以它们是真阴性。

可视化

现在让我们将相似度s和签名成为候选者的概率P之间的联系进行可视化。通常情况下,具有更高签名相似度的签名应具有更高成为候选者的概率。理想情况下,它应该如下所示:

理想情况。仅当相似度大于某个阈值t时,一对签名才被视为候选

基于上面得到的概率公式,典型的线条将如下图所示:

典型的线条在开始和结束时缓慢上升,并在阈值t处具有陡峭的斜率,该阈值由图中的近似概率公式给出

可以通过改变带数b的数量来将图中的线条向左或向右移动。增加b将向左移动线条并导致更多的FP,减少b将向右移动线条并导致更多的FN。根据问题找到一个良好的平衡非常重要。

带数越多,线条向左移动,带数越少,线条向右移动
将阈值向左移动会增加FP,将其向右移动会增加FN

使用不同的带数和行数进行实验

下面构建了几个不同b和r值的线图。根据具体任务调整这些参数以成功检索所有相似文档并忽略具有不同特征的文档,这始终是更好的选择。

调整带数
调整行数

结论

我们已经介绍了LSH方法的经典实现。通过使用较低维度的特征表示和快速的哈希机制来减少候选搜索范围,LSH显著优化了搜索速度。同时,这也会牺牲搜索准确性,但实际上,这种差异通常是微不足道的。

然而,LSH对高维数据很敏感:更多的维度需要更长的特征长度和更多的计算来保持良好的搜索质量。在这种情况下,建议使用另一种索引。

实际上,存在不同的LSH实现,但它们都基于相同的范式,即将输入向量转换为哈希值,同时保留关于它们相似性的信息。基本上,其他算法只是定义了获得这些哈希值的其他方式。

随机投影是另一种LSH方法,它将在下一章中介绍,并且已作为Faiss库中的LSH索引实现。

资源

  • 局部敏感哈希| Andrew Wylie| 2013年12月2日
  • 数据挖掘|局部敏感哈希| Szeged大学
  • Faiss存储库

除非另有说明,否则所有图片均为作者所拍。