??????? 位姿檢索使用了LSH方法，而不使用PNP方法，是有一定的來由的。主要的工作會(huì)轉(zhuǎn)移到特征提取和檢索的算法上面來，有得必有失。因此，放棄了解析的方法之后，又放棄了優(yōu)化的方法，最后陷入了檢索的汪洋大海。

0：轉(zhuǎn)自wiki：http://en.wikipedia.org/wiki/Locality_sensitive_hashing

以下參考資料僅供參考：LSH理解及相關(guān)資料：http://s99f.blog.163.com/blog/static/35118365201262691335382/

有一篇代碼的實(shí)現(xiàn)：http://blog.sina.com.cn/s/blog_ad9597a30101o0ix.html

一：局部敏感哈希—原始分解

???????? 原文鏈接：http://www.jiahenglu.net/NSFC/LSH.html

LSH(Location Sensitive Hash),即位置敏感哈希函數(shù)。為保序哈希，也就是散列前的相似點(diǎn)經(jīng)過哈希之后，也能夠在一定程度上相似，并且具有一定的概率保證。

形式化定義：

??????? 對(duì)于任意q,p屬于S，若從集合S到U的函數(shù)族H={h1,h2...hn}對(duì)距離函數(shù)D(,)，如歐式距離、曼哈頓距離等等，滿足條件：

???? 則稱D(,)是位置敏感的。

如下圖，空間上的點(diǎn)經(jīng)位置敏感哈希函數(shù)散列之后，對(duì)于q，其rNN有可能散列到同一個(gè)桶（如第一個(gè)桶）,即散列到第一個(gè)桶的概率較大，會(huì)大于某一個(gè)概率閾值p1;而其(1+emxilong)rNN之外的對(duì)象則不太可能散列到第一個(gè)桶，即散列到第一個(gè)桶的概率很小，會(huì)小于某個(gè)閾值p2.

????

LSH的作用

◆高維下近似查詢

??????? 相似性檢索在各種領(lǐng)域特別是在視頻、音頻、圖像、文本等含有豐富特征信息領(lǐng)域中的應(yīng)用變得越來越重要。豐富的特征信息一般用高維向量表示，由此相似性檢索一般通過K近鄰或近似近鄰查詢來實(shí)現(xiàn)。一個(gè)理想的相似性檢索一般需要滿足以下四個(gè)條件：

1. 高準(zhǔn)確性。即返回的結(jié)果和線性查找的結(jié)果接近。

2. 空間復(fù)雜度低。即占用內(nèi)存空間少。理想狀態(tài)下，空間復(fù)雜度隨數(shù)據(jù)集呈線性增長(zhǎng)，但不會(huì)遠(yuǎn)大于數(shù)據(jù)集的大小。

3. 時(shí)間復(fù)雜度低。檢索的時(shí)間復(fù)雜度最好為O（1）或O（logN)。

4. 支持高維度。能夠較靈活地支持高維數(shù)據(jù)的檢索。

?????? 傳統(tǒng)主要方法是基于空間劃分的算法——tree類似算法，如R-tree，Kd-tree，SR-tree。這種算法返回的結(jié)果是精確的，但是這種算法在高維數(shù)據(jù)集上的時(shí)間效率并不高。實(shí)驗(yàn)[1]指出維度高于10之后，基于空間劃分的算法時(shí)間復(fù)雜度反而不如線性查找。LSH方法能夠在保證一定程度上的準(zhǔn)確性的前提下，時(shí)間和空間復(fù)雜度得到降低，并且能夠很好地支持高維數(shù)據(jù)的檢索。

◆分類和聚類

?????? 根據(jù)LSH的特性，即可將相近（相似）的對(duì)象散列到同一個(gè)桶之中，則可以對(duì)圖像、音視頻、文本等豐富的高維數(shù)據(jù)進(jìn)行分類或聚類。

◆數(shù)據(jù)壓縮。如廣泛地應(yīng)用于信號(hào)處理及數(shù)據(jù)壓縮等領(lǐng)域的Vector Quantization量子化技術(shù)。

總而言之，哪兒需要近似kNN查詢，哪兒都能用上LSH.

[1] Weber R, Schek H, Blott S. A quantitative analysis and performance study for similarity search methods in high dimensional spaces Proc.of the 24th Intl.Conf.on Very Large Data Bases (VLDB).1998:194-205

LSH的經(jīng)典論文作者：http://www.informatik.uni-trier.de/~ley/pers/hd/m/Ma:Yi

http://research.microsoft.com/en-us/people/mayi/publications.aspx

32.Segmentation of Natural Images by Texture and Boundary Compression,

Hossein Mobahi, Shankar Rao, Allen Yang, Shankar Sastry, andYi Ma, submitted to the International Journal of Computer Vision (IJCV), March 2010.

X: Compact Projection: Simple and Efficient Near Neighbor Search with Practical Memory Requirements

二：方法：Methods

漢明Bit重采樣：Bit sampling for Hamming distance（original hash ）

One of the easiest ways to construct an LSH family is by bit sampling.^[3] This approach works for the Hamming distance over d-dimensional vectors . Here, the family of hash functions is simply the family of all the projections of points on one of the coordinates, i.e.,? 必須把特征轉(zhuǎn)化到漢明空間，利用漢明距離；, where is theth coordinate of. A random function from simply selects a random bit from the input point. This family has the following parameters:,.

Min-wise independent permutations

Main article:MinHash?? ：最小hash！

Suppose is composed of subsets of some ground set of enumerable items and the similarity function of interest is theJaccard index. If is a permutation on the indices of, for let. Each possible choice of defines a single hash function mapping input sets to integers.

Define the function family to be the set of all such functions and let be the uniform distribution. Given two sets the event that corresponds exactly to the event that the minimizer of lies inside. As was chosen uniformly at random, and define an LSH scheme for the Jaccard index. ? 集合的 jaccard距離：一般用來判定文本相似度；

Because the symmetric group on n elements has size n!, choosing a truly random permutation from the full symmetric group is infeasible for even moderately sized n. Because of this fact, there has been significant work on finding a family of permutations that is "min-wise independent" - a permutation family for which each element of the domain has equal probability of being the minimum under a randomly chosen. It has been established that a min-wise independent family of permutations is at least of size.^[9] and that this boundary is tight^[10]

Because min-wise independent families are too big for practical applications, two variant notions of min-wise independence are introduced: restricted min-wise independent permutations families, and approximate min-wise independent families. Restricted min-wise independence is the min-wise independence property restricted to certain sets of cardinality at most k.^[11] Approximate min-wise independence differs from the property by at most a fixed .^[12]

Nilsimsa Hash

Main article:Nilsimsa Hash

Nilsimsa is ananti-spam focused locality-sensitive hashing algorithm.^[13] The goal of Nilsimsa is to generate a hash digest of an email message such that the digests of two similar messages are similar to each other. Nilsimsa satisfies three requirements outlined by the paper's authors:

The digest identifying each message should not vary signicantly (sic) for changes that can be produced automatically.

The encoding must be robust against intentional attacks.

The encoding should support an extremely low risk of false positives.

Random projection：

The random projection method of LSH^[4] (termed arccos by Andoni and Indyk ^[14]) is designed to approximate thecosine distance between vectors. The basic idea of this technique is to choose a randomhyperplane (defined by a normal unit vector) at the outset and use the hyperplane to hash input vectors.

Given an input vector and a hyperplane defined by, we let. That is, depending on which side of the hyperplane lies.

Each possible choice of defines a single function. Let be the set of all such functions and let be the uniform distribution once again. It is not difficult to prove that, for two vectors,, where is the angle between and. is closely related to.

In this instance hashing produces only a single bit. Two vectors' bits match with probability proportional to the cosine of the angle between them.

Stable distributions：基于p穩(wěn)定分布的hash.

????? The hash function^[15] maps ad dimensional vector onto a set of integers映射到一個(gè)數(shù)軸線段區(qū)間的整數(shù)上. Each hash function in the family is indexed by a choice of random and where is ad dimensional vector with entries chosen independently from a stable distribution and is a real number chosen uniformly from the range [0,r]. For a fixed the hash function is given by.

Other construction methods for hash functions have been proposed to better fit the data.^[16] In particular k-means hash functions are better in practice than projection-based hash functions, but without any theoretical guarantee.

三：基于p穩(wěn)定分布的LSH

原文鏈接：http://blog.sina.com.cn/s/blog_67914f2901019p3v.html

??????? LSH是用局部敏感的方法解決近似最近鄰搜索的問題。在原始的LSH方法中，通過將原始空間嵌入到Hamming空間中，將d維空間轉(zhuǎn)換成d＇=Cd維的Hamming空間（C是指原始空間中點(diǎn)的坐標(biāo)的最大值，具體情況參見上一部分中的第4節(jié)-算法步驟），使用(r,(1+e)r,1-r/d＇,1-(1+e)r/d＇)-敏感哈希函數(shù)來解決(r,e)-Neighbor問題。而后來提出的p-stableLSH算法中，不需要將原始空間嵌入到Hamming空間中，可以直接在歐幾里得空間下進(jìn)行局部敏感哈希運(yùn)算。

1、背景介紹 ? ? p-stableLSH應(yīng)用在d維lp-norm下的歐幾里得空間中，0<p<=2。p-stableLSH是LSH的進(jìn)化版本，要解決的問題相同，而使用的方法和應(yīng)用環(huán)境不同。因此，下面重點(diǎn)介紹p-stableLSH的應(yīng)用環(huán)境，對(duì)于LSH的細(xì)節(jié)參見第一部分。 ? ? p-stableLSH使用的(R,cR,p1,p2)-敏感哈希中，c=1+e，并且不失一般性，設(shè)R=1。下面的工作主要是確定在1（即R）和c（即cR）下的p1與p2。 2、v概念解釋 ? ? p-stableLSH之所以會(huì)叫這個(gè)名字，是因?yàn)樵撍惴☉?yīng)用到p-stabledistribution（p-穩(wěn)定分布）的概念。下面給出的就是p-穩(wěn)定分布的概念： ? ? Def 1 :一個(gè)分布D稱為p-穩(wěn)定分布，如果對(duì)于任意n個(gè)實(shí)數(shù)v1,v2,…,vn和符合D分布的n個(gè)獨(dú)立同分布隨機(jī)變量X1,X2,…,Xn，都存在一個(gè)p>=0，使得變量Vi和? 其映射 具有相同的分布，此處X是一個(gè)符合D分布的隨機(jī)變量。 ??? p-穩(wěn)定分布不是具體的分布，而是滿足某條件的分布族。當(dāng)p=1時(shí)，代表是標(biāo)準(zhǔn)柯西分布，密度函數(shù)為?p(x) =(1/3.14)*(1/(1+x*x))????；當(dāng)p=2時(shí)，代表是標(biāo)準(zhǔn)正態(tài)分布（高斯分布）。 ???? 重點(diǎn)：近鄰特性
?? ? p-stable分布有一個(gè)重要的應(yīng)用，就是可以估計(jì)給定向量v在歐幾里得空間p-norm下長(zhǎng)度，記為||v||p。方法是對(duì)于取定的d維向量v，從p-穩(wěn)定分布中抽取d個(gè)隨機(jī)變量組成d維向量a，計(jì)算a與v的點(diǎn)積a.v（點(diǎn)積的概念是將向量對(duì)應(yīng)位置的元素相乘后所有乘積之和），根據(jù)p-stable的定義，由于a.v=Add（Vi*Xi）,因此a.v與||v||pX是同分布的（X是p-stable分布的一個(gè)隨機(jī)變量）。選取若干個(gè)向量a，計(jì)算多個(gè)a.v的值，稱為向量v的“概略（sketch）”，利用v的“sketch”可以用來估算||v||p的值。
3、局部敏感哈希函數(shù) ? ???在p-stableLSH中，a與v的點(diǎn)積a.v不用來估計(jì)||v||p的值，而是用來生成哈希函數(shù)族，且該哈希函數(shù)族是局部敏感的（即空間中距離較近的點(diǎn)映射后發(fā)生沖突的概率高，空間中距離較遠(yuǎn)的點(diǎn)映射后發(fā)生沖突的概率低）。大體方法是將一條直線分成等長(zhǎng)且長(zhǎng)度為r的若干段，給映射到同一段的點(diǎn)賦予相同的hash值，映射到不同段的點(diǎn)賦予不同的hash值。(a.v1-a.v2)是映射后的距離，而其值與||v1-v2||pX同分布，因此，原始距離（||v1-v2||p）較小時(shí)，映射后的距離也小，因此使用點(diǎn)積來生成哈希函數(shù)族可以保持局部敏感性。 ? ? 哈希函數(shù)族的形式為：，其中b是(0,r)里的隨機(jī)數(shù)，r為直線上分段的段長(zhǎng)。哈希族中的函數(shù)根據(jù)a和b的不同建立函數(shù)索引。 ? ?從哈希函數(shù)族中隨機(jī)選取一個(gè)哈希函數(shù)，現(xiàn)在估計(jì)兩個(gè)向量v1和v2在該哈希函數(shù)下映射后發(fā)生沖突的概率。定義符合p-stable分布的隨機(jī)變量絕對(duì)值的概率密度函數(shù)為fp(t)，設(shè)c=||v1-v2||p，則a.v1-a.v2與cX同分布，X為p-stable分布下的隨機(jī)變量。給出概率的計(jì)算公式如下，之后會(huì)有詳細(xì)分析。 ? ? ??
Ｐ（Ｃ）＝Ｐ（ａ，ｂ）［ Ha,b（V1）= Ha,b（V2）］=積分（1/c *fp(t/c)(1/t/r)）t

? ?因?yàn)閨a.v1-a.v2|=||v1-v2||p|X|=c|X|，X為p-stable分布下的隨機(jī)變量，|X|的概率密度函數(shù)為fp(t)。若要向量v1和v2映射后發(fā)生沖突，需要滿足如下條件：v1和v2通過與a進(jìn)行點(diǎn)積運(yùn)算分別映射到一段長(zhǎng)度為r線段后，再通過加b運(yùn)算，能使映射后的點(diǎn)在同一條線段上。
? ?以下是對(duì)該概率公式正確性的證明： ? ?設(shè)點(diǎn)a.v1在點(diǎn)M處，點(diǎn)a.v2在點(diǎn)N處，此處設(shè)N點(diǎn)在靠近Q的位置。 （一）b對(duì)映射后點(diǎn)的影響 ? ? 在加b后，因?yàn)閎>0，因此加b后點(diǎn)會(huì)后移。不失一般性，設(shè)r=1，則有以下兩種情況： ? ?（1）若映射到同一條線段上，不妨設(shè)為線段PQ（P為前端點(diǎn)，Q為后端點(diǎn)），設(shè)|MN|=t，|NQ|=m，則若要保證加b后點(diǎn)M和點(diǎn)N仍在同一條線段中，則要滿足0<b<=m（此時(shí)加b后M,N仍在線段PQ中），或者t+m<=b<r（此時(shí)加b后點(diǎn)M,N落入下一條線段中）。 ? ?? （2）若映射到不同線段上，但|MN|<r（此時(shí)必在相鄰線段中），不妨設(shè)相鄰兩條線段為PQ和QR，設(shè)|MQ|=m，則|QN|=t-m，則若要保證加b后點(diǎn)M和點(diǎn)N仍在同一條線段中，則要滿足m<b<r-(t-m)。 ? ??可以看到，不管是那種情況，b的取值范圍都是r-t，而b是(0,r)內(nèi)的隨機(jī)數(shù)，因此取得滿足條件b的概率是(r-t)/r=1-t/r。現(xiàn)在只需討論向量v1和v2經(jīng)過a的點(diǎn)積映射后的距離為t的概率（因?yàn)橛懻揵是設(shè)|MN|=t，即b是在向量映射后距離為t的情況下討論的），即求|a.v1-a.v2|=||v1-v2||p|X|=c|X|=t的概率。

（二）點(diǎn)積對(duì)映射后點(diǎn)的影響： ? ???? ? 因?yàn)殡S機(jī)變量|X|的概率密度函數(shù)為fp(x)，而這里要求的是c|X|=t的概率。在這里有一個(gè)誤區(qū)，要注意的是，c|X|=t的概率并不是Pr(|X|=t/c)=fp(t/c)，這是因?yàn)閨X|是連續(xù)隨機(jī)變量， 不能通過某點(diǎn)的概率來生成其密度函數(shù)，雖然密度函數(shù)的意義是fp(x)=Pr(|X|=x)，但反過來是不成立的。因此，要求c|X|=t的概率，只能通過密度函數(shù)的定義來解決。 ? ? ? ?? 密度函數(shù)的大致定義是：對(duì)于隨機(jī)變量X的分布函數(shù)F(x)，如果存在函數(shù)f(x)，使得F(x)是f(x)在全部定義域內(nèi)（一般就可取負(fù)無窮到正無窮，隨機(jī)變量取不到的地方概率為0）的積分，那么f(x)就稱為X的概率密度函數(shù)。F(x)=Pr(X<x)，f(x)=Pr(X=x)。這里再強(qiáng)調(diào)一遍，對(duì)于連續(xù)型隨機(jī)變量，第二個(gè)式子的反過來沒有意義，因?yàn)檫B續(xù)型隨機(jī)變量在某點(diǎn)的概率恒為0。而分布函數(shù)代表的是某段區(qū)域內(nèi)概率之和，因此，第二個(gè)式子反過來推導(dǎo)是有意義的。 ? ? ? ? ?因此，要求c|X|=t的概率，可用如下方法：設(shè)隨機(jī)變量Y=c|X|，則原始問題轉(zhuǎn)化成求Y=t的概率。設(shè)|X|的分布函數(shù)為Fp(t)，Y的分布函數(shù)為Gp(t)，則Gp(t)=Pr(Y<t)=Pr(c|X|<t)=Pr(|X|<t/c)=Fp(t/c)，因此，c|X|=t的概率為Gp'(t)=Fp'(t/c)=1/c*fp(t/c)，這樣，經(jīng)過點(diǎn)積映射后，兩向量在線上點(diǎn)的距離等于t的概率便求出來了。
? ?至此，我們得到了原始空間中的兩個(gè)向量經(jīng)過點(diǎn)積運(yùn)算后映射到線段上的距離為t的概率以及在距離為t的前提下加b后能落在同一線段上的概率。因?yàn)槿绻麅蓚€(gè)向量經(jīng)過點(diǎn)積后映射到線段上的距離大于r，且b是(0,r)上的隨機(jī)數(shù)，因此這種情況下不論b取多少，兩點(diǎn)都不可能落入同一條線段上。因此，t的取值范圍是(0,r)。綜上所述，該概率公式得證。
在上概率公式中，對(duì)于給定的r，概率p(c)是關(guān)于c的單調(diào)遞減函數(shù)。即，c=||v1-v2||越大，映射后發(fā)生沖突的概率就越小，這符合局部敏感哈希函數(shù)的要求。因此，所選取的哈希函數(shù)族是局部敏感哈希函數(shù)族，并且是(r1,r2,p1,p2)-敏感的，其中p1=p(1),p2=p(c),r2/r1=c。c>1時(shí)，滿足p1>p2，r1<r2。
以上就是對(duì)p-stableLSH的討論，它通過涉入穩(wěn)定分布和點(diǎn)積的概念，實(shí)現(xiàn)了LSH算法在歐幾里得空間下的直接應(yīng)用，而不需要嵌入Hamming空間。p-stableLSH中，度量是歐幾里得空間下的lp準(zhǔn)則，即向量v1與v2的距離定義為||v1-v2||p，然后通過設(shè)定的哈希函數(shù)將原始點(diǎn)映射到直線的等長(zhǎng)線段上，每條線段便相當(dāng)于一個(gè)哈希桶，與LSH方法類似，距離較近的點(diǎn)映射到同一哈希桶（線段）中的概率大，距離較遠(yuǎn)的點(diǎn)映射到同一哈希桶中的概率小，正好符合局部敏感的定義。

四：hash方法的使用過程：

Amplification：詳細(xì)描述

Given a -sensitive family, we can construct new families by either the AND-construction or OR-construction of.^[1]

To create an AND-construction, we define a new family of hash functions, where each function is constructed from random functions from. We then say that for a hash function, if and only if all for. Since the members of are independently chosen for any, is a-sensitive family.

To create an OR-construction, we define a new family of hash functions, where each function is constructed from random functions from. We then say that for a hash function, if and only if for one or more values of. Since the members of are independently chosen for any, is a-sensitive family.? 重點(diǎn)是：如何構(gòu)建hash函數(shù)族...

LSH algorithm for nearest neighbor search:算法步驟

One of the main applications of LSH is to provide a method for efficient approximatenearest neighbor search algorithms. Consider an LSH family . The algorithm has two main parameters: the width parameter and the number of hash tables.

In the first step, we define a new family of hash functions, where each function is obtained by concatenating functions from, i.e.,. In other words, a random hash function is obtained by concatenating randomly chosen hash functions from. The algorithm then constructs hash tables, each corresponding to a different randomly chosen hash function.

In the preprocessing step we hash all points from the data set into each of the hash tables. Given that the resulting hash tables have only non-zero entries, one can reduce the amount of memory used per each hash table to using standardhash functions.

Given a query point , the algorithm iterates over the hash functions. For each considered, it retrieves the data points that are hashed into the same bucket as. The process is stopped as soon as a point within distance from is found.

Given the parameters and, the algorithm has the following performance guarantees:

• preprocessing time:, where is the time to evaluate a function on an input point;
• space: , plus the space for storing data points;
• query time: ;
• the algorithm succeeds in finding a point within distance from (if there exists a point within distance) with probability at least;

For a fixed approximation ratio and probabilities and, one can set and, where. Then one obtains the following performance guarantees:

• preprocessing time:;
• space: , plus the space for storing data points;
• query time: ;

五：Locality Sensitive Hashing(LSH)之隨機(jī)投影法

原文鏈接：http://www.strongczq.com/2012/04/locality-sensitive-hashinglsh%E4%B9%8B%E9%9A%8F%E6%9C%BA%E6%8A%95%E5%BD%B1%E6%B3%95.html

?為什么隨即投影法是可行的？應(yīng)該怎么去函數(shù)族的參數(shù)？以及正確率表現(xiàn)？

1. 概述

???????? LSH是由文獻(xiàn)[1]提出的一種用于高效求解最近鄰搜索問題的Hash算法。LSH算法的基本思想是利用一個(gè)hash函數(shù)把集合中的元素映射成hash值，使得相似度越高的元素hash值相等的概率也越高。LSH算法使用的關(guān)鍵是針對(duì)某一種相似度計(jì)算方法，找到一個(gè)具有以上描述特性的hash函數(shù)。LSH所要求的hash函數(shù)的準(zhǔn)確數(shù)學(xué)定義比較復(fù)雜，以下給出一種通俗的定義方式：

對(duì)于集合S，集合內(nèi)元素間相似度的計(jì)算公式為sim(*,*)。如果存在一個(gè)hash函數(shù)h(*)滿足以下條件：存在一個(gè)相似度s到概率p的單調(diào)遞增映射關(guān)系，使得S中的任意兩個(gè)滿足sim(a,b)>=s的元素a和b，h(a)=h(b)的概率大于等于p。那么h(*)就是該集合的一個(gè)LSH算法hash函數(shù)。

一般來說在最近鄰搜索中，元素間的關(guān)系可以用相似度或者距離來衡量。如果用距離來衡量，那么距離一般與相似度之間存在單調(diào)遞減的關(guān)系。以上描述如果使用距離來替代相似度需要在單調(diào)關(guān)系上做適當(dāng)修改。

根據(jù)元素相似度計(jì)算方式的不同，LSH有許多不同的hash算法。兩種比較常見的hash算法是隨機(jī)投影法和min-hash算法。本文即將介紹的隨機(jī)投影法適用于集合元素可以表示成向量的形式，并且相似度計(jì)算是基于向量之間夾角的應(yīng)用場(chǎng)景，如余弦相似度。min-hash法在參考文獻(xiàn)[2]中有相關(guān)介紹。

2 隨機(jī)投影法(Random projection)

?? 假設(shè)集合S中的每個(gè)元素都是一個(gè)n維的向量：

v??={v1,v2,…,vn} ，集合中兩個(gè)元素v??和u??之間的相似度定義為 sim(v??,u??)=v???u??|v??||u??| 。

對(duì)于以上元素集合S的隨機(jī)投影法hash函數(shù)h(*)可以定義為如下：

在n維空間中隨機(jī)選取一個(gè)非零向量x??={x1,x2,…,xn}。考慮以該向量為法向量且經(jīng)過坐標(biāo)系原點(diǎn)的超平面，該超平面把整個(gè)n維空間分成了兩部分，將法向量所在的空間稱為正空間，另一空間為負(fù)空間。那么集合S中位于正空間的向量元素hash值為1，位于負(fù)空間的向量元素hash值為0。判斷向量屬于哪部分空間的一種簡(jiǎn)單辦法是判斷向量與法向量之間的夾角為銳角還是鈍角，因此具體的定義公式可以寫為

h(v??)={1,0,v???x??>0v???x??<=0 。

根據(jù)以上定義，假設(shè)向量v??和u??之間的夾角為θ，由于法向量x??是隨機(jī)選取的，那么這兩個(gè)向量未被該超平面分割到兩側(cè)（即hash值相等）的概率應(yīng)該為：p(θ)=1?θπ。假設(shè)兩個(gè)向量的相似度值為s，那么根據(jù)θ=arccos(s),有

p(s)=1?arccos(s)π 。因此，存在相似度s到概率p的單調(diào)遞增映射關(guān)系，使得對(duì)于任意相似度大于等于s的兩個(gè)元素，它們hash值相等的概率大于等于p(s)。所以，以上定義的hash值計(jì)算方法符合LSH算法的要求。

以上所描述的h(*)函數(shù)雖然符合LSH算法的要求，但是實(shí)用性不高。因?yàn)樵揾ash函數(shù)只產(chǎn)生了兩個(gè)hash值，沒有達(dá)到hash函數(shù)將元素分散到多個(gè)分組的目的。為了增加不同hash值的個(gè)數(shù)，可以多次生成獨(dú)立的函數(shù)h(*)，只有當(dāng)兩個(gè)元素的多個(gè)h(*)值都相等時(shí)才算擁有相同的hash值。根據(jù)該思路可以定義如下的hash函數(shù)H(*)：

H(v??)=(hb(v??)hb?1(v??)…h1(v??))2 。其中每個(gè)hi(v??)表示一個(gè)獨(dú)立的h(*)函數(shù)，H(*)函數(shù)值的二進(jìn)制表現(xiàn)形式中每一位都是一個(gè)h(*)函數(shù)的結(jié)果。

以H(*)為hash函數(shù)的話，兩個(gè)相似度為s的元素具有相同hash值的概率公式為

p(s)=(1?arccos(s)π)b

。hash值的個(gè)數(shù)為2b。很容易看出H(*)函數(shù)同樣也是符合LSH算法要求的。一般隨機(jī)按投影算法選用的hash函數(shù)就是H(*)。其中參數(shù)b的取值會(huì)在后面小節(jié)中討論。

3 隨機(jī)投影法在最近鄰搜索中的應(yīng)用

3.1 最近鄰搜索

最近鄰搜索可以簡(jiǎn)單的定義為：對(duì)于m個(gè)元素的集合T，為一個(gè)待查詢?cè)豵找到集合中相似度最高的k個(gè)元素。

最近鄰搜索最簡(jiǎn)單的實(shí)現(xiàn)方法為：計(jì)算q與集合T中每一個(gè)元素的相似度，使用一個(gè)具有k個(gè)元素的大頂堆（優(yōu)先隊(duì)列）保存相似度計(jì)算結(jié)果（相似度值為key）。這種實(shí)現(xiàn)方法每一次查詢都要遍歷整個(gè)集合T來計(jì)算相似度，當(dāng)m很大并且查詢的頻率很高的時(shí)候這種暴力搜索的方法無法滿足性能要求。

當(dāng)最近鄰搜索的近鄰要求并不是那么嚴(yán)格的時(shí)候，即允許top k近鄰的召回率不一定為1（但是越高越好），那么可以考慮借助于LSH算法。

3.2 隨機(jī)投影法提高執(zhí)行速度

這里我們介紹當(dāng)集合T的元素和查詢?cè)豵為同維度向量(維度為n)，并且元素相似度計(jì)算方法為余弦相似度時(shí)，使用隨機(jī)投影法來提高最近鄰搜索的執(zhí)行速度。具體的實(shí)現(xiàn)方法為：

預(yù)處理階段：使用hash函數(shù)H(*)計(jì)算集合T中所有元素的hash值，將集合T分成一個(gè)個(gè)分組，每個(gè)分組內(nèi)的元素hash值均相等。用合適的數(shù)據(jù)結(jié)構(gòu)保存這些hash值到分組的映射關(guān)系（如HashMap）。

查詢階段：計(jì)算查詢?cè)豵的hash值H(q)，取集合T中所有hash值為H(q)的分組，以該分組內(nèi)的所有元素作為候選集合，在候選該集合內(nèi)使用簡(jiǎn)單的最近鄰搜索方法尋找最相似的k個(gè)元素。

該方法的執(zhí)行效率取決于H(*)的hash值個(gè)數(shù)2b，也就是分組的個(gè)數(shù)。理想情況下，如果集合T中的向量元素在空間中分布的足夠均勻，那么每一個(gè)hash值對(duì)應(yīng)的元素集合大小大致為m2b。當(dāng)m遠(yuǎn)大于向量元素的維度時(shí)，每次查詢的速度可以提高到2b倍。

根據(jù)以上分析H(*)中b的取值越大算法的執(zhí)行速度的提升越多，并且是指數(shù)級(jí)別的提升。但是，在這種情況下H(*)函數(shù)下的概率公式p(s)，實(shí)際上表示與查詢?cè)豵的相似度為s的元素的召回率。當(dāng)b的取值越大時(shí)，top k元素的召回率必然會(huì)下降。因此算法執(zhí)行速度的提升需要召回率的下降作為代價(jià)。例如：當(dāng)b等于10時(shí)，如果要保證某個(gè)元素的召回率不小于0.9，那么該元素與查詢?cè)豵的相似度必須不小于0.9999998。

3.3 提高召回率改進(jìn)

為了在保證召回率的前提下盡可能提高算法的執(zhí)行效率，一般可以進(jìn)行如下改進(jìn)：

預(yù)處理階段：生成t個(gè)獨(dú)立的hash函數(shù)Hi(?)，根據(jù)這t個(gè)不同的hash函數(shù)，對(duì)集合T進(jìn)行t種不同的分組，每一種分組方式下，同一個(gè)分組的元素在對(duì)應(yīng)hash函數(shù)下具有相同的hash值。用合適的數(shù)據(jù)結(jié)構(gòu)保存這些映射關(guān)系（如使用t個(gè)HashMap來保存）。

查詢階段：對(duì)于每一個(gè)hash函數(shù)Hi(?)，計(jì)算查詢?cè)豵的hash值Hi(q)，將集合T中Hi(?)所對(duì)應(yīng)的分組方式下hash值為Hi(q)的分組添加到該次查詢的候選集合中。然后，在該候選集合內(nèi)使用簡(jiǎn)單的最近鄰搜索方法尋找最相似的k個(gè)元素。

以上改進(jìn)使得集合中元素與查詢?cè)豵的t個(gè)hash值中，只要任意一個(gè)相等，那么該集合元素就會(huì)被加入到候選集中。那么，相似度為s的元素的召回率為

p(s)=1?(1?(1?arccos(s)π)b)t

在執(zhí)行效率上，預(yù)處理階段由于需要計(jì)算t個(gè)hash函數(shù)的值，所以執(zhí)行時(shí)間上升為t倍。查詢階段，如果單純考慮候選集合大小對(duì)執(zhí)行效率的影響，在最壞的情況下，t個(gè)hash值獲得的列表均不相同，候選集集合大小的期望值為t?m2b，查詢速度下降至1t，與簡(jiǎn)單近鄰搜索相比查詢速度提升為2bt倍。

下圖是召回率公式p(s)=1?(1?(1?arccos(s)π)b)t在不同的b和t取值下的s-p曲線。我們通過這些曲線來分析這里引入?yún)?shù)t的意義。4條藍(lán)色的線以及最右邊紅色的線表示當(dāng)t取值為1（相當(dāng)于沒有引入t），而b的取值從1變化到5的過程，從圖中可以看出隨著b的增大，不同相似度下的召回率都下降的非常厲害，特別的，當(dāng)相似度接近1時(shí)曲線的斜率很大，也就說在高相似度的區(qū)域，召回率對(duì)相似度的變化非常敏感。10條紅色的線從右到左表示b的取值為5不變，t的取值從1到10的過程，從圖中可以看出，隨著t的增大，曲線的形狀發(fā)生了變化，高相似度區(qū)域的召回率變得下降的非常平緩，而最陡峭的地方漸漸的被移動(dòng)到相對(duì)較低的相似度區(qū)域。因此，從以上曲線的變化特點(diǎn)可以看出，引入適當(dāng)?shù)膮?shù)t使得高相似度區(qū)域在一段較大的范圍內(nèi)仍然能夠保持很高的召回率從而滿足實(shí)際應(yīng)用的需求。

3.4 參數(shù)選取

根據(jù)以上分析，H(*)函數(shù)的參數(shù)b越大查詢效率越高，但是召回率越低；參數(shù)t越大查詢效率越低但是召回率越高。因此選擇適當(dāng)參數(shù)b和t來折中查詢效率與召回率之間的矛盾是應(yīng)用好隨機(jī)投影法的關(guān)鍵。下面提供一種在實(shí)際應(yīng)用中選取b和t的參考方法。

根據(jù)實(shí)際應(yīng)用的需要確定一對(duì)(s,p)，表示相似度大于等于s的元素，召回率的最低要求為p。然后將召回率公式表示成b-t之間的函數(shù)關(guān)系t=log1?(1?acos(s)pi)b(1?p)。根據(jù)(s,p)的取值，畫出b-t的關(guān)系曲線。如s=0.8,p=0.95時(shí)的b-t曲線如下圖所示。考慮具體應(yīng)用中的實(shí)際情況，在該曲線上選取一組使得執(zhí)行效率可以達(dá)到最優(yōu)的(b,t)組合。

3.5 關(guān)于最近鄰文本搜索

在最近鄰文本搜索中，一般待檢索的文本或查詢文本，都已被解析成一系列帶有權(quán)重的關(guān)鍵詞，然后通過余弦相似度公式計(jì)算兩個(gè)文本之間的相似度。這種應(yīng)用場(chǎng)景下的最近鄰搜索與以上所提到的最近鄰搜索問題相比存在以下兩個(gè)特點(diǎn)：

• 如果把每個(gè)文本的帶權(quán)重關(guān)鍵詞表都看作是一個(gè)向量元素的話，每個(gè)關(guān)鍵詞都是向量的一個(gè)維度，關(guān)鍵詞權(quán)重為該維度的值。理論上可能關(guān)鍵詞的個(gè)數(shù)并不確定（所有單詞的組合都可能是一個(gè)關(guān)鍵詞），因此該向量元素的維數(shù)實(shí)際上是不確定的。
• 由于關(guān)鍵詞權(quán)重肯定是大于零的，所以向量元素的每一個(gè)維度的值都是非負(fù)的。

對(duì)于第一個(gè)特點(diǎn)，我們需要選取一個(gè)包含n個(gè)關(guān)鍵詞的關(guān)鍵詞集合，在進(jìn)行文本相似度計(jì)算時(shí)只考慮屬于該集合的關(guān)鍵詞。也就是說，每一個(gè)文本都視為是一個(gè)n維度的向量，關(guān)鍵詞權(quán)重體現(xiàn)為對(duì)應(yīng)維度的值。該關(guān)鍵詞集合可以有很多種生成辦法，比如可以是網(wǎng)站上具有一定搜索頻率的關(guān)鍵詞集合，總的來說該關(guān)鍵詞集合應(yīng)當(dāng)能夠涵蓋所有有意義并且具有一定使用頻率的關(guān)鍵詞。通常n的取值會(huì)比較大，如幾十萬到幾百萬，由于在使用隨機(jī)投影算法時(shí)，每一個(gè)生成的隨機(jī)向量維度都為n，這種情況下需要特別考慮利用這些高維隨機(jī)向量對(duì)執(zhí)行效率造成的影響，在確定b、t參數(shù)時(shí)需要考慮到這方面的影響。

對(duì)于第二個(gè)特點(diǎn)，由于向量元素各維度值都非負(fù)，那么這些元素在高維空間中只會(huì)出現(xiàn)在特定的區(qū)域中。比如當(dāng)n為3時(shí)，只會(huì)出現(xiàn)在第一象限中。一個(gè)直觀的感覺是在生成隨機(jī)向量的時(shí)候，會(huì)不會(huì)生成大量的無用切割平面（與第一個(gè)象限空間不相交，使得所有元素都位于切割平面的同側(cè)）。這些切割平面對(duì)應(yīng)的H(*)函數(shù)hash值中的二進(jìn)制位恒定為1或者0，對(duì)于提高算法執(zhí)行速度沒有幫助。以下說明這種擔(dān)心是沒有必要的：

切割平面與第一象限空間不相交等價(jià)于其法向量的每一個(gè)維度值都有相同的符號(hào)（都為正或者負(fù)），否則總能在第一象限空間中找到兩個(gè)向量與法向量的乘積符號(hào)不同，也就是在切割平面的兩側(cè)。那么，隨機(jī)生成的n維向量所有維度值都同號(hào)的概率為12n?1，當(dāng)n的取值很大時(shí)，該概率可以忽略不計(jì)。

參考文獻(xiàn)

[1] P. Indyk and R. Motwani. Approximate Nearest Neighbor:Towards Removing the Curse of Dimensionality. In Proc. of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 604–613.

[2] Google News Personalization: Scalable Online Collaborative Filtering

后記：

??????? 然而最后，我使用了還是隨機(jī)投影的方法，這個(gè)是正確率和速度的權(quán)衡

總結(jié)

以上是生活随笔為你收集整理的位姿检索PoseRecognition：LSH算法.p稳定哈希的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。