LocalitySensitiveHashing总结.doc

Locality Sensitive Hashing 总结
一、 概述
最近邻搜索问题（Nearest Neighbor Search Problem， NNS）是：给定距离空间X中的点集P = { p1, p2 … pn }，以及q∈X，如何高效的找到P中距离近q最近的那个点。这里的距离空间X，我们一般只关注Rd空间。当d较小的时候，文献H. Edelsbrunner. Algorithms in Combinatorial Geometry. 1987 提出了一个有效的解决办法。但是，当空间的维度d较大的时候，无论是理论上还是实践中，还没有令人满意的解决方法，线性查找方法的效率也非常低这种由于维度d太大，而带来的求解困难的问题称为“维度灾难”。
除了最近邻问题之外，研究人员对近似最近邻问题也比较感兴趣，即，在P中找到点p，使得对所有的p’都满足 。此时，可以直观理解为，p是P中距离q的差不多最小的点。但是即使是ε-NNS问题，情况也不比NNS好到哪里去。
为了解决维度灾难问题，Indyk提出了局部敏感哈希算法，专门用于处理高维海量数据，尤其是用于数据间的相似度计算。在实际应用中，如果是低维少量数据，可以直接采用线性查找的方法。当数据量大，并且维度高时，LSH是一个不错的选择。
LSH从1998年开始，经历了多个版本。比较经典的是汉明空间上的LSH、p-stable LSH。P-stable LSH是汉明空间LSH的改进版本，它使得数据无需转化为01串，可以直接在欧氏空间上处理。下文分别介绍这两种LSH方案。
二、 原始LSH
LSH算法的思想是，利用hash函数，将原始数据点映射到一个新的空间中，并且使得，在原空间中距离相近的点，会以很大的概率产生hash碰撞。当进行最近邻查找时，只需要计算查询点的hash值，然后提取所有与查询点产生hash碰撞的数据点。这些数据点可以在一个较大的概率下保证是与查询点相似的。这样一来，我们只需要在这些相似的点中寻找那个最近邻，无需遍历整个数据库。因此，LSH算法能够帮助我们从整个数据库中找到一个子集，这个子集种的数据点会以很大的概率与查询点相接近。LSH算法中采用的hash函数并不同于传统的用于密码学中的hash函数。在密码学中，我们期望尽量避免hash碰撞。而在LSH算法中的hash函数，我们却希望最大化碰撞概率。
那么什么样的函数才算是局部敏感哈希函数呢？从上述描述来看，可以看出LSH函数有如下性质：
距离较远的点，产生哈希碰撞的概率较小
距离较近的点，产生哈希碰撞的概率较高。
从LSH函数的性质，我们可以这么定义LSH函数：
在距离空间X（d）中，d为距离，函数簇H是从X到U到映射，对任意X中的点p,q，f都满足：
1）如果d(x,y) ≤ d1， 则h(x) = h(y)的概率至少为p1；
2）如果d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；
满足上述条件的函数称之为是（d1, d2 , p1 , p2）-sensitive的。 《Mining of Massive Datasets》一书中，给出了寻找这样的函数的方法。一般来说，我们只需要几个常用的：
下面我们介绍一些满足不同距离度量方式下的locality-sensitive的hash functions：
1. Jaccard distance
Jaccard distance： (1 - Jaccard similarity)，而Jaccard similarity = (A intersection B) / (A union B)，Jaccard similarity通常用来判断两个集合的相似性。
Jaccard distance对应的LSH hash function为：minhash，其是(d1,d2,1-d1,1-d2)-sensitive的。

2. Hamming distance
Hamming distance： 两个具有相同长度的向量中对应位置处值不同的次数。
Hamming distance对应的LSH hash function为：H(V) = 向量V的第i位上的值，其是(d1,d2,1-d1/d,1-d2/d)-sensitive的。

3. Cosine distance
Cosine distance：cos(theta) = A·B / |A||B| ，常用来判断两个向量之间的夹角，夹角越小，表示它们越相似。
Cosine distance对应的LSH hash function为：H(V) = sign(V·R)，R是一个随机向量。V·R可以看做是将V向R上进行投影操作。其是(d1,d2,(180-d1)180,(180-d2)/180)-sensitive的。
理解：利用随机的超平面（random hyperplane）将原始数据空间进行划分，每一个数据被投影后会落入超平面的某一侧，经过多个随机的超平面划分后，原始空间被划分为了很多cell，而位于每个cell内的数据被认为具有很大可能是相邻的（即原始数据之间的cosine distance很小）。

4. normal Euclidean distance
Euclidean distance是衡量D维空间中两个点之间的距离的一种距离度量方式。
Euclidean distance对应的LSH hash function为：H(V) = |V·R + b| / a，R是一个随机向量，a是桶宽，b是一个在[0,a]之间均匀分布的随机变量。V·R可以看做是将V向R上进行投影操作。其是(a/2,2a,1/2,1/3)-sensitive的
本章介绍的是原始LSH算法，该算法采用的是汉明距离。其LSH函数的构造方法是：给定函数簇H = { h | hi(v) = vi}。即，取出向量V第i位上的值。这个H仅仅是hash函数，但不能算作是局部敏感哈希函数。因此，下一步就是构造具有sensitive性质的hash函数簇G。构造方法是，从H中随机的取k个h，将这k个h串联起来形成一个新的函数g。g = { h1, h2, … hk }。这个g是sensitive的。因为g是随机的取k个h，而h又是去向量V上的第i位。函数g的实际效果就是，随机的从向量V中取k位。由于V是经过汉明化的，因此，函数g的函数值，也即hash值，的排列组合就有2k个。我们把函数g产生的hash值称为hash桶。这样，每个函数g都能够生成2k个hash桶，这2k个hash桶摆成一行，就会形成一个表，称为hash table。每个hash桶对应的都是产生碰撞的向量。当数据量特别大的时候，每个hash桶中都会对应了大量向量，这些向量会以很大概率在原空间X中距离接近。依然提到了概率，就会有例外。也有可能本身距离较远的点，经过哈希之后落入了同一个hash桶，这种错误称之为false positive；反之，也有可能本身距离相近的点，落入了不同的hash桶中，这种错误称之为false negative。在实际应用中，我们希望尽量减小这两类错误。因此，采用的一搬方法就是把g函数进行级联。因为，我们仅仅是从H中选出了一个g，如果我们选出大量的g，够成一个簇G。把这些g函数进行级联，就能使得错误概率大大减小。级联方法有AND、OR方法。通过选取多个g函数，可以形成多个hash table。
当有了sensitive 哈希函数时，就可以把数据库中所有的点映射到这多张hash table中的桶中。距离相近的点，会议较大的概率落入同一个hash table中的同一个桶里，即同一个g函数输出相等的hash值。当我们进行查询的时候，将查询点也计算hash值。因为我们选择了多个g函数的级联，假设是L个g函数。因此我们有L个hash table。查询点也会计算出L个hash值，对应了L个hash桶。将这L个hash桶对应的数据库中的点都搜集起来，构成一个集合。这个集合就是查询点最接近的点。我们只需要在这个子集中进行线性查找，就能找到查询点的最近邻，而无需搜索整个数据库。

三、 P-stable LSH

四、 E2LSH
E2LSH与p-stable LSH相比，有少许的改动，但主要部分不变。E2LSH可以看做是p-stable LSH的概率版本，也就是说。P-stable LSH能够100%的返回所有满足要求的近邻。而E2LSH只能以一个概率值返回满足要求的近邻。
R-NN问题的定义是。给定集合P，和半径R。来回答下面的问题：给定查询点q，和所有的点p∈P，返回满足||p-q||<=R的所有的点。而p-stable LSH能够返回满足条件的所有的点。而E2LSH却是以某个概率来返回满足要求的点。就好像是从答案中挑选了一些答案，再呈现给我们看。而p-stable LSH是把所有的答案都呈现给我们看。这就是二者之间的区别。
这个概率在E2LSH中设定为1-δ。这个1-δ可以看作是E2LSH的衡量指标了，通过控制1-δ的大小，来动态控制E2LSH的灵敏度度。
参考描述如下：
The R-near neighbor problem is defined as follows. Given a set of points P ⊂ d and a radius R > 0, construct a data structure that answers the following queries: for a query point q, find all points p ∈ P such that ||q − p||2 ≤ R, where ||q − p||2 is the Euclidean distance between q and p. E2LSH solves a randomized version of this problem, which we call a (R, 1 − δ)-near neighbor problem. In this case, each point p satisfying ||q−p||2 ≤ R has to be reported with a probability at least 1−δ (thus, δ is the probability that a near neighbor p is not reported).
原p-stable LSH版本称为(R,c)-NNS；而E2LSH版本称为(R, 1-δ)-NNS。P-stable LSH会返回所有与q距离之多是cR的任何点。而E2LSH能够得到所有的近邻和近似最近邻，但是接下来会丢弃近似最近邻（原文没说some，所以，有可能是丢弃所有的近似最近邻）。
对E2LSH，其敏感hash函数的定义形式有所变化：

从running time的角度去考虑，我们希望扩大[0，R][R, ∞]之间的碰撞概率P1与P2的间隔。处于这种考虑，我们采用串联k个h函数，并定义G函数，使得每个g都是k个h的串联。然后，再构造L个具有这种形式的g函数。在预处理阶段，我们把P中的每一个点v放进哈希桶gi(v)中。由于哈希桶的数量很大，所以不可能在内存中存储所有的哈希桶，一搬的做法是只选择那些非空的哈希桶。
当我们处理一个查询点q的时候，会搜索所有的哈希桶g1(q), . . . , gL(q).。对于在哈希桶中发现的每一个与q碰撞的点v，都计算一个q与v之间的距离。然后返回所有那些满足||q - v||<=R的点。并称这些点是一个R-near neighbor。从这里来看。并非所有与q 产生碰撞的点都是近邻，而是近邻以很大的概率存在于能够与q产生碰撞的点。
在具体的实现中，我们一般选择半径R等于1。因为，如果R不等于1，那么我们可以对所有点的坐标都除以个R，使得R归一化到1.
另外，稳定分布没有通用的密度函数和分布函数公式。但是根据文献，要产生P-stable随机变量，我们只需要从两个独立切服从[0，1]上均匀分布的随机变量上生成即可。
生成Hash family。
定义一个hash函数或family很简单。凡是能够把任意向量映射为固定长度的bit串的函数，都可以成为hash函数。典型的hash函数可以是求余函数。而在p-stable里，作者给出的hash函数的原型是内积。由于内积映射可以把任意维度的向量映射到整数域，因此内积可以是一个hash函数。数学形式如下：
ha,b(v):RdàZ 。这里的a是一个坐标服从p-stable分布的随机变量，b是[0，W]的随机数。函数h通过a,b来index。这里的index很有内涵。这表表明，每一个a都对应了一个h函数。而a是什么？a是我们被投影的向量。所以，我们选择多个h，实际上就是构造了多条射线。P中的点都向这些射线投影，也就是向a投影。通过投影来构造hash函数。还有一点，从h的定义来看，R是d维的，而Z是一维的。这恰恰对应了内积值是一个数这个概念。所以，当我们选择k个h时，实际上就是选择了k条射线。如果把我们这些k个h函数串联起来，那么就构成了Zk。这个Zk恰恰对应了后文的h1和h2的构造。
当我们通过内积构造hash函数的时候，我们当然可以很简单的构造一个ha(v)=a*v，h由a来index。但是这样做有一定的缺陷，就是每一个h都是过原点的，换句话说就是，我们只能构造了那些过原点的h函数，而漏掉了平面上其他的不过原点的函数。为了改善这一点，我们加入一个偏移量b，使得ha,b(v)=av+b。当然，b绝对不能是一个定值。否则，如果b是定值的话，那函数的截距就是个常数，这样一来，就又漏掉了其他截距的h函数。因此，b应该是一个服从均匀分布的随机变量。每一种截距都有相同的概率出现。但是这么做还不够，但是目前也想不清楚哪里不够，哪里还缺点什么。不妨暂且放下，等遇到问题的时候，再去修正我们构造的h。
如果有两个向量v1和v2，还有一个坐标都服从P-stable分布的变量a。那么根据内积的性质有，a*v1-a*v2 = (v1-v2)*a。再根据p-stable分布的定义。(v1-v2)*a与||v1-v2||X有相同的分布，X是一个服从p-stable分布的随机变量。
注意，因为a = X1,,,Xn），所以||v1-v2||X中的X仅仅是a中的一个元素。X的取值范围是实数，而||v1-v2||也是一个数，因此||v1-v2||X还是个数。如果不是数的话，是不可能与内积值有相同的分布的。而a*v1-a*v2实际上是v1与v2在a上的投影的距离。这样一来，投影之间的距离就可以用分布来量化了。
还记得前面我们通过内积来定义hash函数。任意两个向量之间hash函数的距离是
ha,b(v1)- ha,b(v2) = a*v1-a*v2 与 ||v1-v2||X 同分布 。因此两个向量之间的hash值的差异也可以通过分布来量化了。可喜的是，分布恰好与v1与v2之间的距离有关当||v1-v2||小的时候，其hash值之间的差异也小。（这句话一直不太理解）
问题来了，上述方法构造的hash值，确实是更像传统的hash函数。两个向量即使有1bit的差异，算出来的内积值也可能不同，hash冲突率较小。但是，问题是我们想要的局部敏感hash函数不能像传统hash函数那样，我们希望hash冲突率高。即两个||v1-v2||小的时候，其hash值最好相同。如果仅仅是用到传统hash函数，那上述构造的ha,b(v)=av+b也就满足需求了。但是到了这里，我们要的是局部敏感哈希，那就不得不对hash函数再进一步改造。改造方法很简单，只要使得hash值差异不大的两个向量，映射为相同的hash值就可以了。比如，如果v1，v2两个向量的hash计算结果是1.2和1.3，那么，我们只需要做取整运算，就能够使得hash差异在1以内的向量输出相同的hash值。
有了这个思路，那么怎么来实现呢？作者是把上述ha,b(v)=av+b 又除以了一个w。w是数轴上划分的线段宽度。这里我也不太理解，为什么要把av+b再除以一个w。我猜想，由于av+b是一个数，也就是不同的v都能够输出不同的数。对于一列数而言，把他们除以w，就能够使得这些数按照w来归一化。
上述取整的思想很容易对应到数轴上。我们把数轴划分为宽度为w的线段，当两个向量投影在同一个线段内的时候，就认为他们输出相同的hash值。可以取线段上的端点的坐标作为这个hash值。例如，有一条线段在坐标轴上横跨3-4之间，同时有两个向量落在了3.6和3.7上，那么我们就取线段的一个端点坐标作为hash值，例如3或4。具体形式见下图：

从上图可以看出，当两个向量的投影距离大于w的时候，是不可能落到同一个线段内的，也就是当a*v1-a*v2 > w时，P[h(v1) = h (v2)] = 0 。当c< w 时，他们投影在同一个线段内的概率是[w- (a*v1-a*v2)]/ w 。这个不难理解，可以想象成把一个火柴棍放在一个线段内，两端点同在一条线段内的概率是多少。此时，我们只需要考虑一侧端点即可。
这样一来，我们就成功的把一个普通的hash函数，转化成了一个具有高冲突率的hash函数。并且冲突率可以通过两个向量之间的距离来量化。这时，我们需要得知，这个hash函数冲突率有多高，即有多敏感，也就是算出，敏感性的4个参数：r1,r2,p1,p2，
前面说过，只有当a*v1-a*v2 所以，也就是等价于计算P（||v1-v2||X < w）= ? 也即， P（X < w/||v1-v2||）= ?其中X符合p-stable分布。
设X的分布函数时f(x)。我们通过分布函数f(x)可以得到||v1-v2||X有多大的可能性小于w。注意，仅仅这一步是不能算作v1与v2产生hash冲突的概率的。因为v1与v2要产生hash冲突，应该分为两步。
第一步是a*v1-a*v2h冲突的概率是 Y总体概率就是

Pra,b[ha,b(v1)= ha,b(v2)]=
至此就推导出了v1与v2产生hash冲突的概率。
l<=1,Pra,b[ha,b(v1)= ha,b(v2)]>=
l>1+ε=c, Pra,b[ha,b(v1)= ha,b(v2)]<
令r1=1,r2=c,则P1，P2由上述两式给出。

即使从直观上理解，也会发现w会影响hash冲突的概率。如果w无限长，那么冲突率是100%。如果w变小，那么冲突率也会降低。那么w取多少才能使得p1与P2之间的间隔最大化呢。原文给出的是w取决于数据点和查询点。设w=4。

五、 参考资料