logo标签列表

如何理解局部敏感哈希？

cmachine-learninghashmapnearest-neighborlocality-sensitive-hash
159
6
阅读Ullman第3章 - “查找相似项”http://infolab.stanford.edu/~ullman/mmds.html - achini
1
我投票关闭此问题，因为机器学习（ML）理论问题不适合在Stack Overflow上讨论 - Cross-Validated的礼品包装候选人。 - Daniel F
6个回答
256
我看过的最好的 LSH 教程在《海量数据挖掘》一书中。请查看第 3 章 - 查找相似项。 http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf 此外，我推荐下面的幻灯片： http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf 。 幻灯片中的示例帮助我更好地理解余弦相似度的哈希。
我从 Benjamin Van Durme & Ashwin Lall, ACL2010 借用了两张幻灯片，并尝试解释余弦距离的 LSH Family 的直觉。 enter image description here
  • 在图中，有两个圆，分别用红色和黄色表示，代表两个二维数据点。我们正在使用 LSH 找到它们的余弦相似度。
  • 灰色线是一些均匀随机选择的平面。
  • 根据数据点在灰线上方或下方的位置，我们将此关系标记为 0/1。
  • 在左上角，有两行白色/黑色正方形，分别表示两个数据点的签名。每个正方形对应一个位 0(白色)或 1(黑色)。
  • 一旦您有了一个平面池，您就可以将数据点编码为相对于平面的位置。想象一下，当我们在池中拥有更多平面时，签名中编码的角度差距更接近实际差距。因为只有位于两个点之间的平面才会给两个数据不同的比特值。

enter image description here

  • 现在我们来看这两个数据点的签名。如示例所示，我们使用只有6个比特（方块）来表示每个数据。这是我们原始数据的LSH哈希。
  • 两个哈希值之间的海明距离为1，因为它们的签名只有1个比特不同。
  • 考虑到签名的长度，我们可以根据图表中显示的方式计算它们的角度相似度。

我在这里用Python写了一些示例代码(仅50行)，该代码使用余弦相似性。 https://gist.github.com/94a3d425009be0f94751

为什么它被称为局部敏感？因为每个位的分配取决于数据点相对于每个平面的局部性。 - nawara
22
本地敏感 -- 数据点彼此靠近时被映射到相似的哈希值（很可能在同一桶中）。 - greeness
2
抱歉我在这个话题上来晚了，但我有一个关于余弦的问题。演示文稿说，如果实际向量和平面向量之间的点积>=0，则位值为1，否则为0。平面向量的方向是什么，因为90度到180度之间的角度也会产生负余弦。我想每个平面都由两个向量组成，我们取与实际向量形成的较小角度。 - vkaul11
1
您提供的幻灯片非常整洁：http://www.cs.jhu.edu/~vandurme/papers/VanDurmeLallACL10-slides.pdf - 您能否解释一下“池化技巧”的数学逻辑，或者我应该查看哪些线性代数概念来理解它？ - user305883
@vkaul11: "我们可以通过先计算角度的余弦值，然后应用反余弦函数将其转换为0-180度范围内的角度来计算余弦距离" - Scott Weaver
显示剩余2条评论
35
21
为什么不直接使用minhash作为您的LSH函数呢？ - Thomas Ahle
1
我相信这是因为每个桶中非重复元素的数量仍然足够高，而如果我们使用m个独立的哈希函数，非近似重复元素映射到同一个桶的概率会大大降低。 - Shatu
10
  • 局部敏感哈希(LSH)是一种将文档/图像/对象集作为输入并输出哈希表的过程。
  • 该表的索引包含文档，使得在同一索引上的文档被认为是相似的，而在不同索引上的文档则被认为是"不相似"的。
  • 相似取决于度量系统以及阈值相似度s，它充当LSH的全局参数。
  • 对于您的问题，定义适当的阈值s由您自行决定。

enter image description here

需要强调的是，不同的相似性度量有不同的LSH实现方式。

在我的博客中，我尝试深入解释了针对minHashing（jaccard相似度度量）和simHashing（cosine距离度量）情况下的LSH。希望对您有所帮助： https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

2
我是一个视觉型人。以下是我的直觉工作方式。
假设您要搜索的每个东西大约都是物理对象，例如苹果、立方体、椅子。
我的对局部敏感哈希（LSH）的直觉是，它类似于获取这些对象的阴影。就像如果你取一个3D立方体的阴影，你会得到一个2D的正方形，在一张纸上，或者一个3D球体会给你一张圆形的阴影在一张纸上。
最终，在搜索问题中有比三个维度更多的维度（其中文本中的每个单词可能是一个维度），但是shadow类比对我仍然非常有用。
现在我们可以在软件中高效地比较位字符串。固定长度的位字符串有点像单个维度上的线。
因此，使用LSH，我最终将对象的阴影投射为单个固定长度的线/位字符串上的点（0或1）。
整个技巧是获取阴影，使其在较低的维度中仍然有意义，例如它们以足够好的方式类似于原始对象，可以被识别。
一份立体的立方体的二维图可以告诉我这是一个立方体。但是如果没有透视，我无法轻易地区分二维正方形和三维立方体的阴影：它们对我来说都像是一个正方形。
我如何将我的物体呈现给光线将决定我是否能得到一个好的可识别的阴影。因此，我认为“好”的局部敏感哈希（LSH）是那种能够将我的物体放在光线前面，以便它们的阴影最能代表我的物体。
所以，总结一下：我认为用局部敏感哈希（LSH）进行索引的东西是像立方体、桌子或椅子这样的实物，并且我将它们的阴影投射在二维平面上，最终沿着一条线（一个位串）。一个“好”的LSH“函数”是如何将我的物体放在光线前面，以便在二维平面和后来的位串中得到一个近似可区分的形状。
最后，当我想要搜索我拥有的某个对象是否与我索引的某些对象相似时，我使用同样的方式将这个“查询”对象的阴影呈现在光源前（最终也得到一个位串）。现在，我可以比较该位串与我所有其他索引位串的相似程度，这是一种代理方式来搜索我的整个对象，如果我找到了一种好的和可识别的方法来展示我的对象给光线。
0
作为一个非常简短的回答，局部敏感哈希的一个例子可以是首先在输入空间中随机设置平面（带有旋转和偏移），然后将要哈希的点放入空间中，并且对于每个平面，测量点是在其上方还是下方（例如：0或1），答案就是哈希值。因此，如果在余弦距离之前或之后测量，空间中相似的点将具有相似的哈希值。
您可以使用scikit-learn阅读这个例子: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接