Locality Sensitive Hashing

本文主要参考文献为 cs.DB] 17 Feb 2021 LSH系列3：p-stable LSH&E2LSH——原理介绍_什么是lsh sampling-CSDN博客

---

warm up

我上高中是2018年，那年的APIO有一道题。总之最后归结为需要使用 KD-tree 来寻找二维空间的最近邻。那年我们高中有一个很厉害的学长，我管他叫头哥哥，头哥哥用了随机向量排序的方法通过了这道题。

如何寻找二维平面最近点对？是x最小的吗？不一定是。是y最小的吗？不一定是。但是或许随机100个方向，有一个方向上相邻的两个点就是最近点对。

这就是平面最近点对的做法。高维映射到低维。

approximate nearest neighbor(ANN) problem

在高维空间中寻找近邻是一个显然很有用的东西，更别说是text-embedding 在基于GPT等技术无比陈述的现在。这个问题被成为 k-nearest neighbor problem。在维度较低的时候，我们常常会使用树形的检索结构，如 KD-tree，SR-tree，但是维度足够高的时候效果较差，甚至接近线性。众所周知传统 KD-tree 的是 $O(n^{1-1/k})$，$k$ 是维度。

与之相对的，一种称为 local sensitive hashing 的近似搜索方法，虽然不能提供 $100\%$ 的准确度（但往往可以通过多个哈希表实现），但能在非常快的速度找 close enough 的结果。

近似版本的 k-nearest neighbor problem ，也叫 c-approximate Nearest Neighbor search，结果是返回那些不超过 $c\times R$ 距离的查询。其中 $R$ 是查询节点到其最近节点的最近邻居。

def:c-ANN/c-k-ANN

假设 $\mathcal D$ 为数据集，有 $n$ 个点，$d$ 个维度，有一个询问的点 $q$，c-ANN search 的目的是返回一个点 $o \in \mathcal D$，使得 $dist(o,q) \le c\times dist(o^,q)$。同样的c-k-ANN是返回 top-k 满足 $dist(o_i,q) \le dist(o_i^,q) , 1\le i\le k$。

Solutions

KD-tree

• 任何一个算法竞赛选手都应该了解划分树。

HNSW, Hierarchical Navigable Small World

• 任何一个算法竞赛选手都应该了解三角剖分，至少是$n \log n$的分治Delaunay三角剖分。
• 让我们回顾一下它在做什么，
  • 任意三角形的外接圆范围内不会又其它点的存在
  • 在点集可能形成的三角剖分中，所形成的三角形的最小角最大。
• Delonay图最接近的三点形成三角形且各线段不相交，因此可以利用Delonay图解决最近邻查找问题。（直观上很对）
• 可导航小世界NSW Navigable Small World 利用贪心算法，每次从图中查找与查询点 $q$ 距离最近的 $k$ 各顶点，贪心算法是说每次找相邻的连接的点的最小值。

Locality Sensitive Hashing

IDEA：将高维数据通过随机哈希的方式映射到哈希桶中，相似的元素会高概率映射到相同的哈希桶。

最早1999年提出第一篇文章^[1]^ 此后又有许多变种。LSH 有两个主要优点，亚线性的查询效率，理论保障的查询准确度。state-of-art 的方法通过一些方法如 Collision Counting 和 Virtual Rehashing 的方法，使得 较小的索引大小，快速的索引维护。

def: sensitive

• 一个哈希函数 $H$ 被定义为 $(R,cR,p_1,p_2)$-sensitive 的，如果满足

• $$\Pr[H(x)=H(y)] \ge p_1 \quad |x-y|\le R\\ \Pr[H(x)=H(y)]\le p_2 \quad |x-y|>cR$$

接下来，我们会给出一些一些哈希函数的例子

Hamming metric: $H(x)=x_i$ 。两个点 $x,y$ 如果 Hamming distrance是 $r$，那么相同的概率就是 $\Pr[H(x)=H(y)]=1-r/d$。

从某种意义上来说，这是直接进行了一个维度的投影。

Minkowski metric: $H_{\vec a,b}(x)=\lfloor\frac{\vec a\cdot x+b}{w}\rfloor$ ，$a$ 是一个随机向量，从 p-stable-distribution，$b$ 是一个 $[0,w)$ 的随机实数 ，$w$ 是桶的大小。

这里牵扯到一个问题，什么是 p stable distribution。

若干个柯西分布 $c(x)=\frac{1}{\pi (1+x^2)}$ 的加权平均还是柯西分布。是 $p=1$ 的稳定分布

若干个高斯分布 $g(x)=\frac{1}{(2\pi)^{1/2}}e^{-x^2/2}$ 的平方的加权和的开方还是高斯分布（二维平面高斯分布）。是 $p=2$ 的高斯分布。

也就是 $\sum v_iX_i$ 和 $(\sum |v_i|^p)^{1/p} X$ 分布相同。则为稳定分布，对于任何 $p \in (0,2]$ 存在稳定分布。

注意，对 p-norm 而言，这就是一个随机投影。

我们这里对 2d 做一个简要的理解： $X\sim N(0,1)$

两个向量 $v1,v_2$，投影后为 $v_1’,v_2’$ ，记 $r = ||v_1,v_2|| , r’ = ||v_1’,v_2’||$，记 $\rho_i$ 为投影空间两个点第 $i$ 维的差，$r’=(\sum{i=1}^k \rho_i^2)^{1/2}$，而 $\rho = a_i \cdot(v_1-v_2)$ 与 $r\cdot X$ 同分布，有 $\rho / r \sim N(0,1)$ 。

我们有 $r’^2 / r^2 =(\sum \rho_i^2)/r^2$ 。可以得到 $r’^2 / r^2 \sim \mathcal X^2(k)$。而对于卡方分布而言，给定一个概率 $\alpha$ 去寻找 $\mathcal X^2(k)$ 大于某个数的概率为 $\alpha$，也就是后面一段的积分为 $\alpha$。根据卡方分布的上下侧分位数定义，我们有

$$\Pr[r'<r \sqrt{\mathcal X_{1-\alpha}^2(k)} ] = a \\ \Pr[r'>r \sqrt{\mathcal X_{\alpha}^2(k)} ] = a$$

也就是说原始空间和投影空间的置信区间有一种强相关性。

最终结论为

$$\Pr[H(x)=H(y)] = \int_{0}^w f_p(t/r)(1-t/w)\dd t$$

Angular metric: 定义了 $H(x) = sgn(\vec a \cdot x)$，$\vec a$ 是一个随机正态分布向量。这里如果两个点的夹角 $\theta$，那么 $\Pr[H(x)=H(y)] = 1-\frac{\theta}{\pi} $

Jaccard metric: $H(x)=\min (\pi (x_i))$，$\pi $ 是一个随机的排列置换，$x_i \in x$。这里 $\Pr[H(x)=H(y)]=J$，$J$ 是两个点的 Jaccard similarity。

$$J(D_i,D_j) = \frac{|D_i \cap D_j|}{|D_i \cup D_j|}$$

Shingling: 利用sliding window得到的一些文本，例如 abcdabd 得到了 ab,bc,cd,da,bd。对集合中的每个元素进行哈希，转化为一个整数存储起来，得到的就是文档集合是一个整数的集合。随便找一个哈希函数映射到整数集合，对于两组集合，从两个哈希后的集合中各挑一个最小的整数出来，这两个整数相等的概率就是 Jaccard Similarity。

---

Techs

Hamming-based LSH Techniques

• 最早的文章用的是Hamming距离，作者使用了多个哈希函数和哈希表，也从理论上找到了以获得恒定哈希概率，哈希函数和哈希表的最优值。

• Boosted LSH BLSH方法^[2]^是通过自适应增强学习的方式训练线性分类器，减少LSH投影中的冗余。

Minkowski-based LSH Techniques

• 2004年，E2LSH^[3]^，解决的是欧几里得距离，依然是使用多个哈希函数和哈希表在做的事情。

新的技术：

• 2006年，hash-perturbation LSH ^[4]^ 759.pdf (princeton.edu)，通过扰动的方式减少哈希表大小。

• 2007年，Multi-probe LSH，提出近邻的点容易被哈希到比较相近的桶里，于是尝试检索周围的一些桶。此外，该方法为每个哈希桶分配了一个距离分数，并且随后按照这些分数的递增顺序访问这些桶。通过使用这种策略，Multi-probe在保持相同准确性的同时需要更少数量的哈希表。

  • 卧槽，竟然是做ImageNet的Kai Li老师

• 一种方法在查询处理阶段，使用期望的而准确度测量来选择最适合给定查询的最佳哈希函数。（？）

• 一种方法利用动态规划，基于数据集特征（如密度）分配哈希桶的大小。
• 一种方法利用主成分分析生成均匀数据集。
• 一个文章利用Hadamard变换来更好地估计欧式和角度空间距离，减少LSH的运行时间。

C2LSH

• C2LSH中只有一个哈希表，有m个随机哈希函数，提出了一种称为碰撞计数的方法，该方法计算哈希点被映射到与查询点相同桶的次数，一旦发生 I 次碰撞，则视为候选点。
• C2LSH有两种停止条件：1）找到 k + βn 个候选点，2）找到 k 个真正的正例。真正的正例通过计算候选点与查询的欧几里德距离，并检查距离是否小于 cR 来找到。如果未满足停止条件，该算法将在每次指数增加的投影搜索半径（例如，在两个桶而不是一个桶中查找碰撞）时增加投影搜索半径。

Bi-level LSH

• Bi-level LSH [84]旨在提高搜索的准确性和运行时效率。首先，它使用RP-tree将数据集分割成随机子组，然后为每个子组创建一个哈希表和基于空间填充曲线（Z-order曲线）的分层结构。

Boundary-expanding locality sensitive hashing [108]

• Boundary-expanding locality sensitive hashing [108]解决了最近点被散列到不同桶的边界的问题，它通过扩展每个桶的边界来克服这个问题，从而增加了相邻点的碰撞概率。

[1] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In Vldb, Vol. 99. 518–529.

[2] Sunwoo Kim, Haici Yang, and Minje Kim. 2020. Boosted Locality Sensitive Hashing: Discriminative Binary Codes for Source Separation. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 106–110.

[3] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry. 253–262.

[4] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. [n.d.]. A Time-Space Efficient Locality Sensitive Hashing Method for Similarity Search in High Dimensions. Technical Report.