译：相似性搜索，第 5 部分：局部敏感哈希 (LSH)

探索如何将相似性信息合并到哈希函数中

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。

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

局部敏感哈希（LSH）是一组方法，用于通过将数据向量转换为哈希值来缩小搜索范围，同时保留有关其相似性的信息。

我们将讨论传统方法，该方法包括三个步骤：

1. Shingling：将原始文本编码为向量。
2. MinHashing ：将向量转换为称为签名的特殊表示，可用于比较它们之间的相似性。
3. LSH函数：将签名块散列到不同的桶中。如果一对向量的签名至少一次落入同一个桶中，则它们被视为候选向量。

我们将在整篇文章中逐步深入探讨每个步骤的细节。

Shingling

Shingling 是收集给定文本的k元模型的过程。k-gram是一组k个连续标记(token)。根据上下文，标记(token)可以是单词或符号。shingling 的最终目标是使用收集的k元模型对每个文档进行编码。我们将为此使用 one-hot 编码。然而，也可以应用其他编码方法。

为“学习数据科学令人着迷(learning data science is fascinating)”这句话收集长度为 k = 3 的独特碎片(shingles)

首先，收集每个文档的唯一k元组。其次，为了对每个文档进行编码，需要一个词汇表来表示所有文档中一组唯一的k元组。然后，对于每个文档，创建一个长度等于词汇表大小的零向量。对于文档中出现的每个 k-gram，都会识别其在词汇表中的位置，并在文档向量的相应位置放置“1” 。即使相同的k元模型在文档中出现多次，也没关系：向量中的值将始终为 1。

​ one-hot编码

最小散列法(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指数。

证明(Statement proof)

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

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

基于随机行排列的两个二进制向量获得相等哈希值的概率等于 Jaccard 系数。

然而，通过证明上面的陈述，我们假设初始向量不包含类型00的行。很明显，类型00的行不会更改 Jaccard 索引的值。同样，获得包含类型00的行的相同哈希值的概率也不会对其产生影响。例如，如果第一个排列行是00，那么 minhash 算法会忽略它并切换到下一行，直到一行中至少存在一个 1。当然，类型 00 的行可能会产生与没有类型 00 的行不同的哈希值，但获得相同哈希值的概率保持不变。

我们已经证明了一个重要的说法。但是如何估计获得相同 minhash 值的概率呢？当然，可以生成向量的所有可能排列，然后计算所有最小哈希值以找到所需的概率。出于显而易见的原因，这效率不高，因为大小为n的向量的可能排列数量等于n!。不过，可以近似地评估概率：让我们使用许多哈希函数来生成那么多哈希值。

两个二进制向量的 Jaccard 系数大约等于其签名中对应值的数量。

很容易注意到，采用更长的签名会导致计算更准确。

LSH 函数

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

考虑n = 10⁶文档，其签名长度为 100。假设单个签名需要 4 个字节来存储，那么整个签名将需要 400 个字节。为了存储n = 10⁶文档，需要 400 MB 的空间，这在现实中是可行的。但是以强力方式比较每个文档将需要大约 5 * 10^1 比较，这太多了，尤其是当n更大时。

为了避免这个问题，可以构建一个哈希表来加速搜索性能，但即使两个签名非常相似并且仅在 1 个位置上不同，它们仍然可能具有不同的哈希值（因为向量余数可能不同）。然而，我们通常希望它们落入同一个桶中。这正是LSH能够发挥作用的地方。

LSH机制构建了一个由多个部分组成的哈希表，如果一对签名至少有一个对应的部分，则将它们放入同一个桶中。

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

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

如果两个不同签名的相应子向量之间至少存在一次冲突，则这些签名被视为候选。正如我们所看到的，这个条件更加灵活，因为将向量视为候选向量不需要绝对相等。然而，这增加了误报的数量：一对不同的签名可以具有单个对应部分，但总体上完全不同。根据问题的不同，优化参数b、r和 k。

错误率(Error rate)

使用 LSH，可以估计具有相似性s的两个签名将被视为候选的概率，给定多个频带b和每个频带中的行数r。让我们分几步找到它的公式。

​ 两个签名的随机行相等的概率

​ 具有 r 行的一个随机带相等的概率

​ 具有 r 行的一个随机带不同的概率

​ 表中所有b波段不同的概率

​ b 个波段中至少有一个相等的概率，因此两个签名是候选者

请注意，该公式没有考虑不同子向量意外散列到同一存储桶中时的冲突。因此，签名成为候选人的真实概率可能差别不大。

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

​ 根据两个签名的相似度 s 获得至少一个相应频带的概率 P

我们注意到，如果两个相似的签名的 Jaccard 相似度为 80%，那么它们在 93.8% 的情况下具有相应的band（真阳性 true positives TP）。在其余 6.2% 的场景中，这样的一对签名是漏报的。

现在让我们采取两个不同的签名。例如，它们的相似度只有 20%。因此，在 0.224% 的情况下，它们是假阳性 false positive FP候选者。在其他 99.776% 的情况下，它们没有类似的band，因此它们是真阴性 true negatives TN。

可视化(Visualisation)

现在让我们可视化相似性s和两个签名成为候选者的概率P之间的联系。通常，签名相似度越高*，*签名成为候选的概率就越高。理想情况下，它看起来像下面这样：

​ 理想的场景。仅当一对签名的相似度大于某个阈值 t 时，才将其视为候选签名

根据上面获得的概率公式，一条典型的线路如下图所示：

​ 一条典型的线，在开始和结束时缓慢增加，并在图中近似概率公式给出的阈值 t 处具有陡峭的斜率

可以改变band b的数量来将图中的线向左或向右移动。增加b将线向左移动并导致更多FP，减少 - 将其向右移动并导致更多FN。根据问题的不同，找到良好的平衡点很重要。

band数量较多时，该线向左移动，band数量较少时，则向右移动

向左移动阈值会增加 FP，向右移动会增加 FN

不同数量的band和行的实验

下面针对b和r的不同值构建了几个线图。最好根据特定任务调整这些参数，以成功检索所有相似文档对并忽略具有不同签名的文档。

​ 调整频段数量

​ 调整行数

（注：testing_lsh.ipynb 实操笔记）

我们已经完成了 LSH 方法的经典实现。LSH 通过使用较低维的签名表示和快速哈希机制来缩小候选者的搜索范围，从而显着优化搜索速度。同时，这是以搜索准确性为代价的，但在实践中，差异通常是微不足道的。

然而，LSH 容易受到高维数据的影响：更多维度需要更长的签名长度和更多的计算才能保持良好的搜索质量。在这种情况下，建议使用其他索引。

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

随机投影是另一种 LSH 方法，将在下一章中介绍，它在Faiss库中作为 LSH 索引实现，用于相似性搜索。

Reference

除非另有说明，所有图片均由作者提供。

原文地址： https://medium.com/towards-data-science/similarity-search-part-5-locality-sensitive-hashing-lsh-76ae4b388203

附操作笔记:

testing_traditional_lsh.ipynb

faiss_lsh.ipynb 学习笔记