Locality Sensitive Hashing.

在机器学习领域，经常会面临检索问题：比如给定一个特征向量，检索数据库中与其相似的特征向量。如果是在低维度的小数据集中，可以使用线性查找（Linear Search，如KNN）的方法；但是在高维度大数据集中，线性查找的效率很低，显然是不可行的。如何从高维度大数据集中找到与某个向量最相似的一个或多个向量，是检索任务中的一个难点。

在这种高维度大数据集中的检索，通常需要使用最近邻最相似查找（Approximate Nearest Neighbor, ANN）的方法。局部敏感哈希（Locality Sensitive Hashing, LSH）是一种最近邻最相似搜索算法，有比较可靠的理论根据且在高维数据中表现比较好，很适合应用在检索任务中。

与一般的哈希算法不同，局部敏感哈希具有位置敏感性，也就是散列前类似的点（距离近的点），在散列后仍然能够保证一定程度的相似，且有一定的概率保证。

1. 局部敏感哈希

LSH的主要思想是，设计一种LSH哈希函数，使得对于在原空间中很相似的两个点，对这两点进行哈希值计算，使得它们哈希值有很大的概率是一样的；同时若两点之间的距离较远，映射后它们哈希值相等的概率很小。

（1）$(R,cR,P1,P2)$-sensive哈希函数

一个哈希函数$h(\cdot)$满足以下性质时，被称为$(R,cR,P1,P2)$-sensive：对于高维空间的任意两点$x,y$，

如果$d(x,y)≤R$，则$h(x)=h(y)$的概率不小于$P1$；
如果$d(x,y)≥cR$，则$h(x)=h(y)$的概率不大于$P2$。

其中$d(x,y)$是两个点$x,y$之间的距离，$h$是哈希函数，$h(x)$和$h(y)$是对点$x,y$的哈希变换，并且需要满足$c>1,P1>P2$。

设计LSH的核心有两个：

两个高维向量的相似性度量$d(x,y)$
$(R,cR,P1,P2)$-sensive哈希函数的选择。

LSH的哈希函数的选择取决于其选择的相似性度量方法，当然并不是所有向量相似性度量的方法都能找到相应的LSH函数，比如LSH最初提出的时候基于欧式距离的度量方法就没有找到合适的LSH函数。

（2）设置哈希键长与哈希表个数

设计完合适的哈希函数$h(\cdot)$后，通过哈希变换使得相似的向量在变换后有很大的概率($P1$)哈希值是相同的；不相似的向量其哈希值只有很小的概率($P2$)是相同的。

在实践中可以通过增加哈希键长度$K$以及哈希表的个数$L$来实现不同哈希函数的组合，从而提高找到相似向量的概率。

增加哈希键长度$K$

设$h_i$是哈希函数簇$H$中的任意函数，对于任意向量$p,q$满足:

\[P(h_i(p) = h_i(q)) = P_1\]

从$H$中随机的挑选$K$个哈希函数将向量映射为$K$长度的串 $g(p)=[h_1(p),h_2(p),⋯,h_K(p)]$，则有：

\[P(g(p) = g(q)) = \prod_{i=1}^K P(h_i(p) = h_i(q)) = P_1^K\]

增加哈希表的个数$L$

设现在有$L$个哈希表(也就是$L$个哈希函数簇$H$)，每个哈希表都使用上面的方法产生一个组合的哈希函数$g$，这样可以得到$L$个哈希函数$g_1,g_2,⋯,g_L$，将这几个组合的哈希函数再组合到一起得到哈希函数$G=[g_1(p),g_2(p),…,g_L(p)]$。

由于使用一个哈希表找到最近邻的概率为$P^K_1$，找不到最相似的概率是$1−P^K_1$。那么使用$L$个哈希表找到最相似的概率：

\[P(G(p) = G(q)) = 1- \prod_{i=1}^L \left(1-P(g_i(p) = g_i(q))\right) = 1-(1-P_1^K)^L\]

下面举一个例子。假设单个哈希函数能够检测到最近邻的概率$P1=0.9$，设置$L=4$个哈希表，每个哈希表具有$K=4$个哈希键，则从中找到最相似点的概率为$1-(1-0.9^4)^4=0.986 > 0.9$。

（3）基于LSH的检索过程

综上，基于LSH的检索过程如下：

离线建立索引
1. 选择满足$(R,cR,P1,P2)$-sensive的哈希函数
2. 根据对查找结果的准确率（即相邻的数据被查找到的概率）确定哈希表的个数$L$和每个哈希表的键长$K$
3. 利用上面的哈希函数组，将集合中的所有数据映射到一个或多个哈希表中，完成索引的建立
在线查找
1. 将查询向量$q$通过哈希函数映射，得到相应哈希表中的编号
2. 将所有哈希表中相应的编号的向量取出来，为了保证查找速度，通常只需要取出来前$2L$个
3. 对这$2L$个向量进行线性查找，返回与查询向量最相似的向量

2. 基于汉明距离的LSH (Origin LSH)

最初设计的LSH对于欧式距离没有找到合适的LSH函数；但是在曼哈顿距离（L1距离）下找到了合适的LSH函数。但直接在L1度量下也不是很容易找到合适的LSH函数，而在汉明距离下有合适的LSH函数。所以Origin LSH使用一种方法将向量从L1准则下的欧式空间嵌入(Embedding)到汉明空间。

（1）汉明距离下的LSH

汉明距离指的是两个相同长度的二进制数据中相同位置处比特位值不同的个数。假如有两个二进制表示的向量$x,y$，向量的每个分量的值不是$0$就是$1$，则可使用汉明距离计算这两个向量的距离。

假设有一组哈希函数$H$，其定义为：每一个哈希函数$h$随机的选择向量特定位置的bit值返回。则$H$中包含了所有从$\{0,1\}^d$映射到$\{0,1\}$函数，其中$h_i(x)=x_i$。

从$H$中随机的选择哈希函数$h_i$应用到向量$x$上，则$h_i(x)=x_i$，返回向量$x$特定位置$i$的bit值。那么$h(x)=h(y)$的概率就为向量$x,y$中bit位相同的所占的比例，即有（$R,cR$为两个向量的汉明距离）：

\[P_1 = 1-\frac{R}{d}, P_2 = 1-\frac{cR}{d}\]

其中$d$为向量二进制的长度。则对于任意的$c>1$,都有$P1>P2$，满足以上提到的LSH函数的条件。

（2）曼哈顿距离(L1)转换为汉明距离

汉明距离只能应用于二进制表示的向量，Origin LSH提出了一种嵌入Embedding方法，将向量的表示从L1准则下的欧式空间嵌入到汉明空间，并且保证转换前后两个向量的距离是不变的。注意向量的各个分量要被正整数化，方便进行01编码。

Embedding算法的流程如下：

找到数据集中所有向量的所有分量的最大值$C$；
对于向量$x=(x_1,x_2,⋯,x_n)$，$n$是向量的维度。将向量每个分量$x_i$转换为长度为$C$的二进制序列，二进制序列为前$x_i$个$1$，剩余的为$0$；
这样一个向量就转变为$nC$长度的二进制串。

Embedding操作是保持距离的，转换后两个向量的距离是不变的。转变为汉明距离后，就可以利用汉明距离下的LSH函数了。设向量的二进制表示的长度为$nC$，如果向量$x,y$的汉明距离为$d$，则通过哈希函数的变换后：

\[P(h(x) = h(y)) = \frac{nC-d}{nC}\]

则有：

如果$d(x,y)≤R$，则$h(x)=h(y)$的概率不小于$P1=\frac{nC−R}{nC}=1−\frac{R}{nC}$；
如果$d(x,y)\geq cR$，则$h(x)=h(y)$的概率不大于$P2=\frac{nC−cR}{nC}=1−\frac{cR}{nC}$。

向量的汉明距离和其映射后相等的概率之间的关系如下图。当两个向量的汉明距离为$0$，映射后其相等的概率为$1$；两个向量的二进制完全不同，汉明距离为$nC$，则其映射后相同的概率为$0$。

（3）一个例子

假设有数据集合中有6个点：

首先进行Embedding操作，把点表示为二进制串，上述坐标的最大值为$4$，所以$C=4$，维度为$2$，则$n=2$，所以二进制串的长度为$8$。

\[\begin{aligned} A = (1,1) & \to v(A) = 10001000 \\ B = (2,1) & \to v(B) = 11001000 \\ C = (1,2) & \to v(C) = 10001100 \\ D = (2,2) & \to v(D) = 11001100 \\ E = (4,2) & \to v(E) = 11111100 \\ F = (4,3) & \to v(F) = 11111110 \\ \end{aligned}\]

采用$K=2,L=3$的哈希函数组合，$G=[g_1,g_2,g_3]$，其中$g_i=[h_1,h_2]$。

假设随机选择的哈希函数组合如下：

$g_1$分别取第$2$位、第$4$位，也就是$h_1(p)=p_2, h_2(p)=p_4$
$g_2$分别取第$1$位、第$6$位，也就是$h_1(p)=p_1, h_2(p)=p_6$
$g_3$分别取第$3$位、第$8$位，也就是$h_1(p)=p_3, h_2(p)=p_8$

利用上面的哈希函数将$6$个点映射到三个哈希表中，结果如下：

对一个待查询向量$q=(4,4)=(11111111)$，可以计算出：

\[g_1(q) = [11], g_2(q) = [11], g_3(q) = [11]\]

将上面$3$个哈希表中映射到$[11]$号的向量取出来为$(C,D,E,F)$，接下来将这四个向量分别与$q$计算距离，距离最近的向量即为最相似的向量，也就是向量$F=(4,3)$。

3. 基于余弦相似度的LSH

余弦相似度是向量方向的度量，计算两个向量之间夹角的余弦。两个方向完全相同的向量的余弦相似度为$1$，而两个方向截然相反的向量的相似度为$-1$。

\[d(x,y) = \cos(\theta) = \frac{x \cdot y}{||x|| \cdot ||y||}\]

当向量的相似性度量是余弦相似度时，哈希函数是通过随机投影（random projection）的方法构造的。对于任意向量$x \in R^d$，首先将其归一化到超球面上$x \to x/ \|x\|_2$，然后构造随机向量$r \in R^d$，则哈希函数定义为：

\[h(x) = \begin{cases} 1, & x \cdot r >0 \\ -1, & x \cdot r <0 \end{cases}\]

$x \cdot r$可以看作是将$x$向$r$上进行投影操作，而$r$是$d$维空间上的一个超平面，把空间分成了两个区域。因此该哈希函数的几何含义是判断向量$x$落入空间中的哪个区域。

该哈希函数$h(\cdot)$是$(R,cR,P1,P2)$-sensive的：

如果$d(x,y)\geq R$，则$h(x)=h(y)$的概率不小于$P1=\frac{\pi-\arccos R}{\pi}$；
如果$d(x,y)\leq cR$，则$h(x)=h(y)$的概率不大于$P2=\frac{\pi-\arccos cR}{\pi}$。

进一步构造随机矩阵$A \in R^{d\times \frac{n}{2}}$，把空间划分成$n$个区域，并判断向量$x$落入空间的哪个区域：

\[h(x) = \mathop{\arg \max}_{n} [-xA,xA]\]

上式中同时存在正负号的含义为两个相反方向的空间。举一个例子，比如设置$d=2,n=4$，则是把二维空间划分为四个区域，计算$x$落入哪个区域中。

如果设置哈希键$K >1$，则相当于同时构造$K$个随机矩阵，从而构造向量的哈希编码：

def LSH(x, n_hashes=4, chunk_size=1):
    N, d = x.size()
    
    # number of hash buckets/hash bits
    hash_buckets = min(N//chunk_size + (N//chunk_size)%2, 128) #保障hash_buckets是偶数
    
    # generate random rotation matrix
    rotations_shape = (1, d, n_hashes, hash_buckets//2)
    random_rotations = torch.randn(rotations_shape, dtype=x.dtype, device=x.device).expand(N, -1, -1, -1)
    
    # locality sensitive hashing
    rotated_vecs = torch.einsum('Nd,NdLK->LNK', x, random_rotations) #[n_hashes, N, hash_buckets//2]
    rotated_vecs = torch.cat([rotated_vecs, -rotated_vecs], dim=-1) #[n_hashes, N, hash_buckets]

    # get hash codes
    hash_codes = torch.argmax(rotated_vecs, dim=-1) #[n_hashes,N]

    return hash_codes