Basic questions about Locally Sensitive Hashing(LSH)

Question

Hi, all

I implemented basics LSH algorithms, including 1) minhash for jaccard distance2) random projections for Euclidean and cosine distance. My aim is to understand the LSH algorithms and use it in my project hopefully.

Two parameters are included in the algorithms, k(length of signature for each data), L(# of hash tables). I suppose k is responsible for precision of retrieved results and L is responsible for recall of retrieved results. My first question is: is there any other parameter I need to consider in LSH implementation?

Take random projection method for example. I initialize k*L random vectors, and make k vectors a group. For each data, I compute signature of the data with each group of vectors(the sign the of the dot product is a bit of signature), i.e., I got L signature for each data, and each signature has a length of k bit. Then I compute a hash value of the k-bit vector and treat the value as a key in hash table. In this manner, I will have L hash table. I call this training phase. My question is: If the k-bit vector is compressed into a hash value, I can only retrieve data with exactly the same signature(100% matched k-bit vector). Is this what LSH does?

Another question is: how can I evaluate my implementation? In particular, if I am focused on accuracy, how can I make sure that I tuned the optimal parameters? My current approach is to make the exact KNN results as baseline, and compute the precision/recall of the retrieved data compared with KNN results. Any problem with my method?

Thanks for your notices.

Answer 1

1

Regarding your first question, you might want to consider how many things you will evaluate at search time as a parameter as well, but you might not.

What LSH is usually used for is not for getting things which hash exactly to your input's hash but for getting everything which hashes sufficiently close (in terms of number of differring bits) to your key. This allows you to look up a neighborhood of a point in time which theoretically depends sublinearly on the size of your training set. K and L allow you to control this time versus the size of the neighborhood you're finding.

You can be shallower than this if you want; for examply by computing how often your LSH implementation is able to find the K exact nearest neighbors.

answered Feb 03 '12 at 06:58

Alexandre Passos ♦
25541●54●278●421

Thanks very much. 1. you mean I need to consider the # of neighbors needed in setting k and L? 2. This means that I still need to compare all the signatures in a table. And get the similarity from the # of bits they match? I think that if there are a lot of buckets in a table, that is still a linear search time, even though the comparison is now different from KNN. 3. this sounds very simple, but what if I retrieved a lot of data that covers the K exact NN?

Btw, I still have a question. Take random projection method of Euclidean distance for example, I generally calculate k integers, what kind of hash function do I need to hash these k values into a fixed-length signature, say 32bits. I am not sure whether the hash function I choose will affect the comparison if I am computing the # of different bits.

Thanks

(Feb 03 '12 at 08:30) DDX

1

Maybe, but that's likely.
Instead of storing all signatures in the table and going over all 2^k entries (which can be expensive), you can store all signatures in a hash table as you mentioned and directly look up, given a key, all other keys which are one bit away (it's a simple for loop, flipping each bit and looking it up in the table). Then things become linear in the size of the bit representation, k.
Then you're fine! More realistically, then you might want to decrease the value of the other parameters to make sure that you don't waste too much computational time.

The random projections method for computing the euclidean distance works by multiplying a vector with a random vector of zeros and ones, and then squaring the result. You then do this many times, average, and get an estimate of the norm of the vector. To do locality sensitive hashing with random projections the procedure is the same, except instead of squaring the result from the projections you throw that information out and look only at its sign. Repeating this many times will give you a bit vector, which is your key. You can generate these random numbers using a hash function, by computing the hash of their index in the vector.

(Feb 03 '12 at 08:37) Alexandre Passos ♦

Thanks! Very useful. Actually, I am confused about the procedure of the search phase. I consider it the same for all kinds of LSH function. i.e, compare every hi in <h1, h2,="" ...,="" hk="">. But it seems not like this from your answer, right?

(Feb 03 '12 at 11:49) DDX

Answer 2

I am going to break out my results into a separate answer, even though they are related to Alexandre's.

First of all, you should sanity check your code as follows:

Pick two random items.
Compute their distance in the original space. (x-value)
Compute their hamming distance in the hash space. (y-value)
Do that for a lot of items.
Plot a graph and make sure it looks like there is a (noisy) line. Otherwise, there is a bug, because the hamming distance in the hash-space is supposed to be an unbiased estimate of the original distance. (I believe this is correct. Anyone who has more intuition about this, please jump in.)

Now that you know your code works correctly, figure out for the desired F-measure of your results. (You measure FMS of the k-best LSH results vs. the exact k-NN results.) Also figure out the desired time in milliseconds (or nanoseconds) for each retrieval.

Now, you can tune your hyperparameters h and L. (I'm using h, not k, for the length of the hash, so as not to confuse with the hyperhyperparameter k from k-NN.) There is also one more hyperparameter, d. d is the maximum hamming distance you will search.

The choice of d controls how much you search in the neighborhood of the hash code. So if d=2, you will look at items in the original hash, you will look at h bit-strings with hamming distance 1 from the hash, and you will look at h^2 bit-strings with hamming distance 2 from the hash.

I will give an example:

 Hash the item.
 Results = []
 For i in [0, d]:
   For all bit-strings that have i bits flipped from the item's hash:
     Add the items in that bit-string's bucket into Results.
 For r in results:
    Compute the distance between r and the item, IN THE ORIGINAL SPACE.
 Pick the k-nearest items from results (under the original distance).
 Measure your FMS and the time this took.

Does this make sense? So now you can optimize your hyperparamter h, L, and d so that the time and FMS are what you desire.

[I will ping Olivier Grisel to jump in, because he is writing LSH code for scikits.learn right now. He might have other insight]

Basic questions about Locally Sensitive Hashing(LSH)

Subscription:

Related questions