p-stable LSH

背景

LSH 方法是处理海量高维数据 Approximate Nearest Neighbor（ANN）查询的有效的方法。

在处理欧氏空间中 ANN 问题时，原始的 LSH（Original LSH）方法将原始空间中的点嵌入到 Hamming 空间中，即将欧氏空间中点的表示形式转换成 Hamming 空间中点的表示形式，原始空间中的距离度量转换成 Hamming 空间中的距离度量，即 Hamming距离（其定义为两个等长序列各位进行异或运算，结果为 1 的个数）。

对应该汉明距离的 Origin LSH 的为位采样运算（bit sampling）。但是一般距离都是用欧式距离进行度量的，将欧式距离映射到 Hamming 空间再比较其的 Hamming 距离比较麻烦，于是研究者提出了基于 p-stable distribution 的位置敏感哈希算法，不需要将原始空间嵌入到 Hamming 空间中而是可以直接处理欧式距离，并解决 (R,c)-近邻问题。

p-stable LSH应用在d维 lp-norm 下的欧几里得空间中， p ∈ ( 0 , 2 ] p∈(0,2] p∈(0,2]。

p-stable distribution

p-stable LSH 之所以会叫这个名字，是因为该算法应用到 p-stable distribution（p-稳定分布）的概念。下面给出的就是p-稳定分布的概念：

对于一个实数集 R 上的分布 D，如果存在 p > = 0 p>=0 p>=0 ，对任何 n 个实数 v 1 , … , v n v_1,…,v_n v1,…,vn和 n 个满足 D 分布的变量 X 1 , … , X n X_1,…,X_n X1,…,Xn，随机变量 ∑ i v i X i \sum_iv_iX_i ∑iviXi 和 ( ∑ i ∣ v i ∣ p ) 1 / p X (\sum_i|v_i|^p)^{1/p}X (∑i∣vi∣p)1/pX 有相同的分布，其中 X X X 是服从D分布的一个随机变量，则称 D 为一个p稳定分布。

对任何 p ∈ ( 0 , 2 ] p∈(0,2] p∈(0,2] 存在稳定分布：

p = 1 p=1 p=1 是柯西分布，概率密度函数为 c ( x ) = 1 π ( 1 + x 2 ) c(x)=\frac{1}{π(1+x^2)} c(x)=π(1+x2)1；

p = 2 p=2 p=2 是高斯分布，概率密度函数为 g ( x ) = 1 ( 2 π ) 1 2 e − x 2 2 g(x)=\frac{1}{(2π)^{\frac{1}{2}}}e^{-\frac{x^2}{2}} g(x)=(2π)211e−2x2。

LSH系列3：p-stable LSH&E2LSH——原理介绍

利用 p-stable distribution 可以有效的近似高维特征向量，并在保证度量距离的同时，对高维特征向量进行降维，其关键思想是：

产生一个 d 维的随机向量 a a a，随机向量 a a a 中的每一维随机的、独立的从 p-stable distribution中产生。
对于一个 d 维的特征向量 v v v，因为 a ⋅ v = ∑ i v i X i a \cdot v =\sum_iv_iX_i a⋅v=∑iviXi，如 p-stable distribution 的定义，随机变量 a ⋅ v a \cdot v a⋅v 具有和 ( ∑ i ∣ v i ∣ p ) 1 / p X (\sum_i|v_i|^p)^{1/p}X (∑i∣vi∣p)1/pX 一样的分布，即和 ∣ ∣ v ∣ ∣ p X ||v||_pX ∣∣v∣∣pX 是同分布的，因此可以用 a ⋅ v a \cdot v a⋅v 表示向量 v v v 来估算 ∣ ∣ v ∣ ∣ p ||v||_p ∣∣v∣∣p ，其中 ∣ ∣ v ∣ ∣ p ||v||_p ∣∣v∣∣p 表示向量 v v v 在欧几里得空间 p-norm 下的长度（原始空间中的长度）。

如果用于欧氏距离度量方式的 LSH 的话，那么就 p = 2 p=2 p=2，此时 ( ∑ i ∣ v i ∣ p ) 1 / p (\sum_i|v_i|^p)^{1/p} (∑i∣vi∣p)1/p 对应的就是欧氏距离的计算公式，下面所有的都可以换为 p = 2 p=2 p=2。

p-stable LSH 的哈希函数

在 p-stable LSH 中，点积 a ⋅ v a \cdot v a⋅v 不用来估计 ∣ ∣ v ∣ ∣ p ||v||_p ∣∣v∣∣p 的值，而是用来生成哈希函数，且该哈希函数是局部敏感的（即空间中距离较近的点映射后发生冲突的概率高，空间中距离较远的点映射后发生冲突的概率低），使用它对每一个特征向量 v v v 赋予一个哈希值。

对于两个向量 v 1 , v 2 v_1,v_2 v1,v2 ， ( a ⋅ v 1 − a ⋅ v 2 ) ，(a \cdot v_1-a \cdot v_2) ，(a⋅v1−a⋅v2)是映射后的距离，而其值与 ∣ ∣ v 1 − v 2 ∣ ∣ p X ||v_1-v_2||_pX ∣∣v1−v2∣∣pX 同分布，因此原始距离 ∣ ∣ v 1 − v 2 ∣ ∣ p ||v_1-v_2||_p ∣∣v1−v2∣∣p 较小时，映射后的距离也小，因此使用点积来生成哈希函数可以保持局部敏感性。如果 v 1 v_1 v1 和 v 2 v_2 v2 距离很近，它们的哈希值将相同，并被哈希到同一个桶中的概率会很大。

大体方法： a ⋅ v a \cdot v a⋅v将特征向量 v v v 映射到实数集R，如果将实轴以宽度 w w w 等分，并对每一段进行标号，则 a ⋅ v a \cdot v a⋅v 落到哪个区间，就将此区间标号作为哈希值赋给它。

哈希函数定义如下：

h a , b ( v ) : R d → N h_{a,b}(v):R^d→ N ha,b(v):Rd→N，映射一个 d 维特征向量 v v v 到一个整数集。哈希函数中有两个随机变量 a a a 和 b b b，其中 a a a 为一个 d 维向量，随机向量 a a a 中的每一维随机的、独立的从 p-stable distribution 中产生， b b b 为 [ 0 , w ] [0,w] [0,w] 范围内的随机数， w w w 是人为设定的一个参数。对于一个固定的 a , b a,b a,b，p-stable LSH 的哈希函数 h a b ( v ) h_{ab}(v) hab(v) 为:
h a b ( v ) = ⌊ a ⋅ v + b w ⌋ h_{ab}(v) = \lfloor \frac{a \cdot v + b}{w} \rfloor hab(v)=⌊wa⋅v+b⌋

这样的哈希函数构成的集合 { h a , b ( v ) : R d → N } \{h_{a,b}(v):R^d→ N\} {ha,b(v):Rd→N} 为 p-stable LSH 的哈希函数族。

两个向量在 p-stable LSH 的哈希函数映射下发生碰撞的概率分析

从 p-stable LSH 的哈希函数族中随机选取一个哈希函数，现在估计两个向量 v 1 , v 2 v_1,v_2 v1,v2 在该哈希函数下发生冲突（也就是落在一个桶中）的概率。若要向量 v 1 v_1 v1 和 v 2 v_2 v2 映射后发生冲突，需要满足如下条件： v 1 v_1 v1 和 v 2 v_2 v2 通过与 a a a 进行点积运算分别映射到一段长度为 w w w 线段后，再通过加 b b b 运算，能使映射后的点在同一条线段上。

首先定义 c = ∣ ∣ v 1 − v 2 ∣ ∣ p c=||v_1-v_2||_p c=∣∣v1−v2∣∣p（原始空间中的距离）， f p ( t ) f_p(t) fp(t)为 p-stable 的分布的概率密度函数，那么特征向量 v 1 v_1 v1 和 v 2 v_2 v2 映射到一个桶上的距离是 ∣ a ⋅ v 1 − a ⋅ v 2 ∣ < w |a·v_1-a·v_2|<w ∣a⋅v1−a⋅v2∣<w，即 ∣ ( v 1 − v 2 ) ⋅ a ∣ < w |(v_1-v_2)·a|<w ∣(v1−v2)⋅a∣<w，根据p-Stable分布的特性，即 ∣ ∣ v 1 − v 2 ∣ ∣ p X = ∣ c X ∣ < w ||v1-v2||_pX=|cX|<w ∣∣v1−v2∣∣pX=∣cX∣<w，其中随机变量 X X X 满足 p-stable distribution。

P ( c ) = P r [ h a b ( v 1 ) − h a b ( v 2 ) ] = ∫ 0 w 1 c f p ( t c ) ( 1 − t w ) d t P(c)=Pr[h_{ab}(v_1)-h_{ab}(v_2)] = \int_{0}^{w}\frac{1}{c}f_p(\frac{t}{c})(1-\frac{t}{w})dt P(c)=Pr[hab(v1)−hab(v2)]=∫0wc1fp(ct)(1−wt)dt

关于这个概率公式的证明，详见它的最后一部分。

根据该式，可以得出两个特征向量的冲突碰撞概率随着距离 c c c（指的是原始空间中的距离）的增加而减小，这符合局部敏感哈希函数的要求。

E2LSH 的相似性搜索算法

欧氏局部敏感哈希(E2LSH，Exact Euclidean locality sensitive Hashing)是 p-stable LSH在欧氏空间的一种随机化实现方法，其基本原理是：利用基于p-稳定分布的位置敏感函数对高维数据进行降维映射，使原始空间中距离很近的两个点经映射操作后依然很近。

一组哈希函数的情况

只有一个 g ( v ) g(v) g(v) 的情况，只有一个哈希表。

为拉大距离近的点与距离远的点经映射后碰撞概率之间的差距，E2LSH 常将 k 个 p-stable LSH 哈希函数联合使用。

从 p-stable LSH 哈希函数族 { h a , b ( v ) : R d → N } \{h_{a,b}(v):R^d→ N\} {ha,b(v):Rd→N} 选择 k 个哈希函数，组成一组哈希函数 g ( v ) = ( h 1 ( v ) , . . . , h k ( v ) ) g(v)=(h_1(v),...,h_k(v)) g(v)=(h1(v),...,hk(v))，对于每个数据点 v ∈ R d v \in R^d v∈Rd，经函数 g ( v ) g(v) g(v) 降维后可以得到一个 k 维向量 a = ( a 1 , a 2 , ⋅ ⋅ ⋅ , a k ) a = (a_1 , a_2 , ··· , a_k ) a=(a1,a2,⋅⋅⋅,ak)，这个 k k k 元组就代表一个桶。

但将 k 元组 a a a 直接作为该哈希表的桶标号，即占用内存，又不便于查找。为解决此问题，设计者又将其分层，使用数组+链表的方式，其中链表中的每一项都是一个哈希桶，即将原来的哈希表组织成下面的形式。

LSH系列3：p-stable LSH&E2LSH——原理介绍

对每个形式为 k 元组的桶标号 a a a，使用如下两个哈希函数 H1 和 H2 计算得到两个值：

其中 H1 的值是数组中的位置，数组的大小也就相当于是哈希表的大小。
其中 H2 的值作为 k 元组的代表，链接到对应 H1 数组位置的链表中。

H1 和H2 的具体形式如下：

H 1 ( a ) = [ ( ∑ i = 1 k r i a i ) m o d C ] m o d t a b l e S i z e H 2 ( a ) = ( ∑ i = 1 k r i ′ a i ) m o d C H_1(a) = [(\sum_{i=1}^{k}r_ia_i)\ mod\ C]\ mod\ tableSize \\ H_2(a) = (\sum_{i=1}^{k}r_i^{'}a_i)\ mod\ C H1(a)=[(i=1∑kriai) mod C] mod tableSizeH2(a)=(i=1∑kri′ai) mod C

其中:

r i r_i ri 和 r i ′ r_i^{'} ri′ 是随机整数;
C C C 是一个大素数，在 32 位机器上可以设置为 2 32 − 5 2^{32}-5 232−5;

索引构建过程：

对数据集中的所有点 v v v，使用 g ( v ) g(v) g(v) 函数对其进行降维，也就是确定其桶标号。
然后使用新定义的哈希函数 H 1 H_1 H1 和 H 2 H_2 H2，将其存在对应位置的哈希桶内
也就是根据 H 1 H_1 H1 的值找到在数组中的位置，然后根据 H 2 H_2 H2 的值在链表中寻找对应的哈希桶，在将原始数据点 v v v 存到对应的哈希桶中。

查询过程如下：

对于查询点 q；
使用这 k 个哈希函数构成的函数（即 g ( q ) g(q) g(q)）计算桶标号的 k 元组；
对 k 元组计算 H1 和 H2 的值；
获取哈希表 H1 位置的链表；
在链表中查找 H2 值对应的哈希桶；
计算 q 与桶中样本的精确的距离，并排序；
找到规定的点。

多组哈希函数的情况

定义 { g l ( v ) : g l ( v ) = ( h 1 ( v ) , . . . , h k ( v ) ) , 1 ≤ l ≤ L } \{g_l(v):g_l(v)=(h_1(v),...,h_k(v)),1 \leq l \leq L\} {gl(v):gl(v)=(h1(v),...,hk(v)),1≤l≤L}，也就是定义 L L L 个前面那样的 g ( v ) g(v) g(v) 函数，这对应着 L L L 个哈希表。每个 g l ( v ) g_l(v) gl(v) 函数由从哈希函数族 { h a , b ( v ) : R d → N } \{h_{a,b}(v):R^d→ N\} {ha,b(v):Rd→N} 中随机独立地选取 k 个哈希函数组成， g l ( v ) g_l(v) gl(v) 对向量 v v v 降维后的值，表示其在第 l l l 个哈希表中哈希桶标号。