Jac*_*ain 8 algorithm machine-learning locality-sensitive-hash
目前我正在研究如何使用局部敏感散列查找最近邻居.然而,当我在阅读论文和搜索网页时,我发现了两种算法:
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)!!!
你对第一个的理解有点偏.发生碰撞的概率与相似性不成比例,但是它是否小于预定半径.目标是半径范围内的任何东西都有很高的碰撞机会,半径*(1 + eps)以外的任何东西碰撞的几率都很低(而且两者之间的区域有点模糊).
第一种算法实际上很难很好地实现,但可以获得良好的结果.特别地,第一算法用于L1和L2(以及技术上更多)度量.
第二种算法实现起来非常简单,但是根据问题的大小,天真的实现可能会占用太多内存而无法使用.在这种情况下,碰撞概率与输入的相似性成比例.但是,它仅适用于余弦相似度(或基于相似度变换的距离度量).
那么您将使用哪一个主要基于您用于最近邻居(或任何其他应用程序)的距离度量.
第二个实际上比第一个更容易理解和实现,论文非常冗长.
短版本:采用随机向量V并给每个索引一个独立的随机单位正常值.根据需要创建任意数量的向量.当您执行Matrix Vector产品时,签名是每个索引的符号.现在任何两个签名之间的汉明距离与各个数据点之间的余弦相似性有关.
因为您可以将签名编码为int数组并使用带位计数指令的XOR来快速获得汉明距离,所以可以非常快速地获得近似余弦相似度分数.
LSH算法没有很多标准化,两篇论文(和其他论文)使用不同的定义,所以有时候它有点令人困惑.我最近才在JSAT中实现了这两种算法,并且我仍在努力完全理解它们.
编辑:回复您的编辑.维基百科的文章对LSH来说不是很好.如果您阅读原始论文,您所讨论的第一种方法仅适用于固定半径.然后基于该半径创建散列函数,并且连接以增加碰撞中的点附近的概率.然后,他们通过确定k的最大值来构建一个k-NN的系统,然后找到最大的合理距离,找到第k个最近邻居.这样,半径搜索很可能会返回一组k-NN.为了加快速度,它们还会产生一些额外的小半径,因为密度通常不均匀,使用的半径越小,结果越快.
您链接的维基百科部分取自"稳定分布"部分的纸质描述,该部分显示搜索半径r = 1的哈希函数.
对于第二篇论文,您描述的"排序"不是散列的一部分,而是用于更快地搜索汉明空间的单一方案的一部分.我正如我所提到的,我最近实现了这一点,你可以看到我使用强力搜索的快速基准测试仍然比NN的天真方法快得多.同样,如果您需要L2或L1距离上的余弦相似性,您也可以选择此方法.你会发现许多其他论文提出了不同的方案来搜索由签名创建的汉明空间.
如果你需要帮助说服你自己适合可以更快,即使你仍在做蛮力 - 只需这样看:让我们说平均稀疏文档有40个常用词与另一个文档(根据我的经验,这是一个非常保守的数字).您有n个要比较的文档.然后,强力余弦相似性将涉及大约40*n个浮点乘法(以及一些额外的工作).如果你有1024位签名,那只有32个整数.这意味着我们可以在32*n整数运算中进行强力LSH搜索,这比浮点运算快得多.
这里还有其他因素在起作用.对于稀疏数据集,我们必须保持双精度和整数索引来表示非零索引,因此稀疏点积产生了许多额外的整数运算,以查看它们共有哪些索引.LSH还允许我们节省内存,因为我们不需要为每个向量存储所有这些整数和双精度,而是我们可以保持其散列 - 这只是几个字节.减少内存使用可以帮助我们更好地利用CPU缓存.
你的O(n)是我在博文中使用的天真方式.它很快.但是,如果您事先对位进行排序,则可以在O(log(n))中进行二进制搜索.即使你有L个这样的列表,L << n,所以它应该更快.唯一的问题是它可以得到近似的汉明NN,它已经接近余弦相似度,因此结果可能会变得更糟.这取决于你需要什么.