algorithm - 使用 Locality-sensitive hashing 找到最近邻的两种算法，哪一种？

Question

目前我正在研究如何使用 Locality-sensitive hashing 找到最近的邻居。然而，当我阅读论文和搜索网络时，我发现了两种算法:

1- 使用 L 个哈希表和 L 个随机 LSH 函数，从而增加两个相似文档获得相同签名的机会。例如，如果两个文档有 80% 的相似度，那么它们有 80% 的机会从一个 LSH 函数中获得相同的签名。但是，如果我们使用多个 LSH 函数，则更有可能从其中一个 LSH 函数获得文档的相同签名。这种方法在维基百科中有解释，我希望我的理解是正确的:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- 另一种算法使用论文(第 5 节)中的方法:Moses S. Charikar 的舍入算法中的相似性估计技术。它基于使用一个 LSH 函数来生成签名，然后对其应用 P 排列，然后对列表进行排序。其实我不是很了解这个方法，我希望有人能澄清一下。

我的主要问题是:为什么有人会使用第二种方法而不是第一种方法？我发现它更容易和更快。

我真的希望有人能帮忙!!!

编辑:
实际上我不确定@Raff.Edward 是否在“第一个”和“第二个”之间混合。因为只有第二种方法使用半径，第一种方法只使用由散列族 F 组成的新散列族 g。请检查维基百科链接。他们只是使用了许多 g 函数来生成不同的签名，然后对于每个 g 函数它都有一个相应的哈希表。为了找到一个点的最近邻居，您只需让该点通过 g 函数并检查相应的哈希表是否存在冲突。因此，我如何将其理解为更多的功能......更多的碰撞机会。

我没有发现任何关于第一种方法的半径的提及。

对于第二种方法，他们只为每个特征向量生成一个签名，然后对它们应用 P 个排列。现在我们有 P 个排列列表，每个列表包含 n 个签名。现在，他们对 P 中的每个列表进行排序。在给定一个查询点 q 之后，他们为它生成签名，然后对其应用 P 排列，然后在每个排列和排序的 P 列表上使用二分搜索找到最相似的签名查询 q。我在阅读了很多关于它的论文后得出了这个结论，但我仍然不明白为什么有人会使用这样的方法，因为它在找到汉明距离方面似乎并不快!!!!

对我来说，我会简单地执行以下操作来找到查询点 q 的最近邻居。给定签名列表 N，我将为查询点 q 生成签名，然后扫描列表 N 并计算 N 中每个元素与 q 签名之间的汉明距离。因此，我最终会得到 q 的最近邻居。它需要 O(N) !!!

Answer 1

你对第一个的理解有点偏离。碰撞发生的概率与相似度不成正比，而与它是否小于预先定义的半径成正比。目标是半径内的任何东西都有很高的碰撞机会，而半径 * (1+eps) 之外的任何东西碰撞的机会都很少(中间的区域有点模糊)。

第一种算法实际上很难很好地实现，但可以得到很好的结果。特别是，第一个算法用于 L1 和 L2(技术上还有更多)指标。

第二种算法实现起来非常简单，尽管根据您的问题大小，一个简单的实现可能会占用太多内存而无法使用。在这种情况下，碰撞概率与输入的相似性成正比。但是，它仅适用于余弦相似度(或基于相似度变换的距离度量)。

因此，您将使用哪一个主要取决于您用于最近邻居(或任何其他应用程序)的距离度量。

第二个实际上比第一个更容易理解和实现，论文只是很罗嗦。

简短版本:取一个随机向量 V 并给每个索引一个独立的随机单位正态值。创建尽可能多的向量，只要你想要签名长度。签名是做矩阵向量乘积时每个索引的符号。现在，任意两个签名之间的汉明距离与各个数据点之间的余弦相似度有关。

因为您可以将签名编码到一个 int 数组中，并使用带有位计数指令的 XOR 来非常快速地获得汉明距离，所以您可以非常快速地获得近似的余弦相似度分数。

LSH 算法没有很多标准化，两篇论文(和其他论文)使用不同的定义，所以有时有点困惑。我最近才在 JSAT 中实现了这两种算法，并且我仍在努力充分理解它们。

编辑:回复您的编辑。维基百科文章对 LSH 来说不是很好。如果您阅读了 original paper ，您所说的第一种方法仅适用于固定半径。然后基于该半径创建散列函数，并将其连接起来以增加在碰撞中靠近点的可能性。然后，他们通过确定他们想要的 k 的最大值，然后找到他们将在其中找到第 k 个最近邻居的最大合理距离来构建一个在此之上进行 k-NN 的系统。这样，半径搜索很可能会返回 k-NN 的集合。为了加快速度，他们还创建了一些额外的小半径，因为密度通常不均匀，并且您使用的半径越小，结果越快。

您链接的维基百科部分取自“稳定分布”部分的论文描述，该部分提供了用于搜索半径 r=1 的哈希函数。

对于第二篇论文，您描述的“排序”不是散列的一部分，而是更快地搜索汉明空间的一种方案的一部分。正如我提到的，我最近实现了这个，你可以看到 a quick benchmark I使用蛮力搜索确实比 NN 的朴素方法快得多。同样，如果您需要 L2 或 L1 距离上的余弦相似度，您也可以选择此方法。您会发现许多其他论文提出了用于搜索由签名创建的汉明空间的不同方案。

如果您需要帮助说服自己适合，即使您仍在使用蛮力也可以更快 - 只需这样看:假设平均稀疏文档与另一个文档有 40 个常用词(根据我的经验，这是一个非常保守的数字)。您有 n 个文档要进行比较。蛮力余弦相似性将涉及大约 40*n 次浮点乘法(和一些额外的工作)。如果你有一个 1024 位的签名，那只有 32 个整数。这意味着我们可以在 32*n 整数运算中进行蛮力 LSH 搜索，这比浮点运算快得多。

这里还有其他因素在起作用。对于稀疏数据集，我们必须同时保留 double 和整数索引来表示非零索引，因此稀疏点积正在执行大量额外的整数运算以查看它们有哪些共同的索引。 LSH 还允许我们节省内存，因为我们不需要为每个向量存储所有这些整数和 double 数，相反，我们可以保留它的散列值——只有几个字节。
减少内存使用可以帮助我们更好地利用 CPU 缓存。

你的 O(n) 是我在我的博客文章中使用的天真方法。而且速度很快。但是，如果您事先对位进行排序，则可以在 O(log(n)) 中进行二分查找。即使你有 L 个这些列表，L << n，所以它应该更快。唯一的问题是它让你得到近似的汉明神经网络，它已经接近余弦相似度，所以结果可能会变得更糟。这取决于你需要什么。