Locality Sensitive Hash浅析

大智若愚，大巧若拙。—— 《道德经》

总述

Locality sensitive hash中文可以译成位置敏感哈希，是一种特殊的hash算法，简称LSH。与一般的hash算法类似，LSH也是将一个数值映射成另一个数值，但是LSH有一个位置敏感特性，即多维空间中相似的数值会被映射成相同的结果值或映射到相同的空间，而该空间中不相似的数值则会被映射成不同的结果值或映射到不同的空间。

原理

既然需要体现数据在空间中的位置特性，那么LSH所采用的哈希函数就要能够在具有一般哈希函数性质的同时（单向性、分散性）考量两个数据的相似性，并将这种相似性体现在映射结果上。

相似性度量

如果把两个数据看成是多维空间中的点，用向量来表征这些点，那么这两个数据的相似性就可以用多维空间中点的距离来衡量。典型的衡量多维空间中两个点之间的距离的算法有如下几种：

Jaccard距离：
$$sim(U, V) = \frac{U \cap V}{U \cup V}$$

余弦距离：
$$sim(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x} \cdot \mathbf{y}}{||\mathbf{x}|| \cdot ||\mathbf{y}||}$$

闵可夫斯基距离：
$$sim(v_1, v_2) = \sqrt[p]{|v_{11} - v_{21}|^p + |v_{12} - v_{22}|^p + … + |v_{1n} - v_{2n}|^p}$$

特别的，当p=1时，闵可夫斯基距离即为曼哈顿距离；当p=2时，闵可夫斯基距离即为欧几里得距离；当p趋于无穷大时，闵可夫斯基距离即为切比雪夫距离。

上述相似度计算方法从距离角度来看均满足距离度量函数的普遍特征（相似度需要转换成距离），即
$$d(x, y) \geq 0$$
$$d(x, y) = 0 \quad 当且仅当x=y时成立$$
$$d(x, y) = d(y, x) \quad 对称性$$
$$d(x, y) \leq d(x, z) + d(y, z) \quad 三角不等式$$

位置敏感哈希

有了距离度量方法之后，就可以设计一个哈希函数，将空间上相邻的点映射到相同的值或空间中去。如何设计这种函数呢？先来看几个重要的数学概念和结论。

p稳定分布

$$若\exists p \geq 0, 有n个服从实数集\Bbb{R}上的分布\mathbf{D}的变量X_i(n>0, 1 \leq i \leq n), v \in \Bbb{R}$$
$$如果随机变量\sum_{i=1}^n{v_iX_i}与(\sum_{i=1}^n{|v_i|^p)^\frac{1}{p}X}同分布，则\mathbf{D}为一个p稳定分布$$

因此，针对两个特征向量v1和v2，如果有一个n维的随机向量X，X中的每一维均独立地从相同的p稳定分布中随机产生，那么就有

$$(\vec{v_1} - \vec{v_2})\vec{a} 与 ||\vec{v_1} - \vec{v_2}||_pX \quad 同分布(\vec{a}是随机向量X中的一个向量)$$

两个向量同分布意味着二者是线性相关的，因此这里就可以用av来近似表示v的p阶范数，从而能够使用点乘运算av将特征向量v从高维空间映射到实数集空间（一维），实现降维。

已知并且常用的p稳定分布包括：
$$柯西分布(p=1): \quad f(x; x_0, \gamma) = \frac{1}{\pi}[\frac{\gamma}{(x-x_0)^2+\gamma^2}]$$
$$高斯分布(p=2): \quad f(x) = \frac{1}{\sqrt{2 \pi}\sigma}exp(-\frac{(x-\mu)^2}{2\sigma^2})$$

如果我们取p=2，就可以用一个每一维数值均满足高斯分布的向量与特征向量之差的点积来近似模拟特征向量之间在高维空间的欧几里得距离。

设计哈希函数

在上述结论的基础上，我们将实数轴做等分处理，每段长为r，并对每一段进行标号，av落到哪个区间，我们就把这个区间号作为映射结果进行返回。于是，LSH可以表示为如下形式：
$$h_{\vec{a}, b}(\vec{v}): \Bbb{R^d} \to \Bbb{N}$$
$$h_{\vec{a}, b}(\vec{v}) = \lfloor \frac{\vec{a} \cdot \vec{v} + b}{r} \rfloor, \quad b \in [0, r]$$

上式中a是一个确定的d维向量，每一维数据均从p稳定分布中产生，b为一个随机噪音，r为分段后每段的长度。
那么，两个点被映射成同一个哈希值的概率可以借助p稳定分布的概率密度函数来表示成：
$$Pr_{\vec{a},b}[h_{\vec{a}, b}(\vec{v_1}) = h_{\vec{a}, b}(\vec{v_2})] = \int_0^r{\frac{1}{c}f_p(\frac{t}{c})(1-\frac{t}{r})}{\rm d}t$$
$$其中 \quad c = ||\vec{v_1} - \vec{v_2}||_p, \ f_p(x)为p稳定分布的概率密度函数$$

由此可见，随着v1与v2之间距离的增大，哈希结果的相似概率随之减小，因此我们说上述函数h是距离敏感的，即h满足如下条件：
$$如果d(\vec{v_1}, \vec{v_2}) < d_1, \quad Pr[h(\vec{v_1})=h(\vec{v_2})] \geq p_1$$
$$如果d(\vec{v_1}, \vec{v_2}) > d_2, \quad Pr[h(\vec{v_1})=h(\vec{v_2})] \leq p_2$$

也就是说，当两个点足够相近时，使用上述函数映射得到相同的结果的概率足够大；当两个点足够相异时，使用上述函数映射得到相同结果的概率足够小。

概率调节

既然是概率保证，也就意味着仍然有一定的可能使得两个不相似的点被映射成相同的值（伪正例），或者相似的点被哈希成不同的哈希值（伪反例）。

为解决伪正例问题，可以构建一个LSH与函数组，每个函数之间相互独立，计算同一个特征的多个哈希值，只有当这些哈希值均相同时才认为特征相似。

为解决伪反例问题，可以构建一个LSH或函数组，每个函数之间相互独立，计算同一个特征的多个哈希值，该组函数中若有一个返回相同的哈希值，则认为特征相似。

结合上面两个方案，可以得到一个综合方案，同时满足与函数组之间的或判断的才认为特征相似。假设与函数组中有x个LSH函数，或函数组中有y个LSH与函数组，且一组特征的相似概率为p，则该组判断中共有xy个LSH函数，那么对该组特征进行组合哈希后的相似概率为
$$1 - (1 - p^x)^y, \quad 0 \leq p \leq 1$$
由此可见，当x越大时，相似概率越小；当y越大时，相似概率越大。x与y作为LSH函数组合的超参数，可以根据实际情况进行调节。

优势

LSH在进行高维数据之间的相似性检查时具有如下的优势：

• 哈希效率高于线性对比
• 通过多个独立LSH函数的组合，可以提升查准率

LSH具有上述的理论优势，但是在实际使用过程中，还需要与合适的索引结构进行配合才能借助计算机的力量实现快速匹配。

应用

LSH算法目前主要应用在各种相似性检索问题中，往往用来解决海量数据间的相似性比对问题，具体应用比如相似图片查找、相似文本检索等。

链接

LSH作者：http://people.csail.mit.edu/indyk/

一种实现：http://www.mit.edu/~andoni/LSH/