前言
Locality Sensitive Hash 的主要功能是在海量高维向量中寻找一个向量的近似最临近点,常用于搜索引擎网页去重,相似图像检索,音乐检索等。
本文主要参考资料是:
[1] Slaney, M., and M. Casey. “Locality-Sensitive Hashing for Finding Nearest Neighbors.” IEEE Signal Processing Magazine 2008:128 - 131.
[2] Slaney, M., Y. Lifshits, and J. He. “Optimal Parameters for Locality-Sensitive Hashing.” Proceedings of the IEEE 100.9(2012):2604 - 2623.
参考项目
[1] https://github.com/kayzh/LSHash
[2] https://github.com/RSIA-LIESMARS-WHU/LSHBOX
基本思想
这里有一个不错的隐喻:假设有一个球面,如果球面上的A点和B点是邻近的,那么将球面投影到某个二维平面上,无论以哪个方向投影,A点和B点始终是邻近的;
另一方面,如果球面上的A点和B点不是邻近的,那么以某些特定的方向投影时,A点和B点可能是邻近的,而以大多数其他方向上投影时,A点和B点则不会邻近。
所以我们应该如何定义邻近的概念呢,假设$p$和$q$是$R^d$空间中的两个点,
$$ ||p-q|| \leq R_1 $$
随机投影 RANDOM PROJECTION
$$ h^{x,b}(\vec{v})=\biggl\lfloor\frac{\vec{x} \cdot \vec{v} + b }{w}\biggr\rfloor $$
其中
$\vec{v}$ 是待查询的向量
$\vec{x}$ 是一个随机的方向,其中每一维遵循高斯分布,比如 $N(0,1)$
$w$ hash bin width 哈希桶宽度
$b$ random variable 实际中可为0
补充定义
如果$p$与$q$邻近,那么它们有高于$P_1$的概率落入同一个哈希桶。
$$ P_H[h(p)=h(q)] \geq P_1 \qquad \qquad \qquad for \quad ||p-q|| \leq R_1 $$
如果$p$与$q$不邻近,那么它们有小于$P_2$的概率落入同一个哈希桶。
$$ P_H[h(p)=h(q)] \leq P_2 \qquad \qquad \qquad for \quad ||p-q|| \geq R_2 = cR_1 $$
这样投影有k次,k的经验取值为7-15;以k次随机投影为一组,要进行L组计算,一般L的取值会与以下公式相关。
$$ L= \frac{[ \; log \, \delta \; ]}{log(1-P^k_1)} $$
$\delta$ 为 LSH 未能成功发现真最邻近点的最大概率。
LSHash 中的实现
LSHash 中进一步简化了上述公式。 原本是按 w 划分 hash bin。
在 LSHash 中 简化为 大于0 和 小于0的情况, 分别是 1 和 0 。
感觉可以这样解释,存在一组法向量随机的超平面,相邻近的点更倾向落在这一组超平面的同一侧,而不相邻近的点则无法一直保持在超平面的同一侧。
数据结构则是使用 dict { key: value} 并且 value 是一个 list 。