Sparse Implementation of LSH

Locality Sensitive Hashing (LSH) can be implemented for both sparse and dense vectors. In this notebook we will implement the algorithm for searching sparse vectors. We will be using k-shingling and minhashing to create our sparse vectors before applying them for search with LSH.

We start by defining a few sentences.

The first thing we do is create our shingles, we will use k-shingles where k == 2. For longer text it is recommended to create shingles where it is unlikely to produce matching shingles between non-matching text, k values of 7 to 11 would likely produce this outcome.

These are our shingles, however, we must remove duplicate values as we are producing a set. We do this using the Python type set. To apply shingling to each of our sentences we will define a shingle function:

Now that we have our three shingles we create a shingle vocabulary by create a union between all three sets.

Using this vocab we can create one-hot encoded sparse vectors to represent our shingles.

So we now have one-hot encoded sparse vectors we can move onto minhashing.

Minhashing

Minhashing is the next step in our process. After creating our shingle sets we use minhashing to create signatures from those sets.

To create our minhashing function we build several hash functions, each will randomly count from 1 to len(vocab) + 1 - creating a random vector:

We now have a randomized list of integers which we can use in creating our hashed signatures. What we do now is begin counting from 1 through to len(vocab) + 1, extracting the position of this number in our new hash_ex list, like so (for the first few integers):

What we do with this is count up from 1 to len(vocab) + 1 and find if the resultant hash_ex.index(i) position in our one-hot encoded vectors contains a positive value (1) in that position, like so:

That gives us a first signature value of 98. But this is just a single value, and it takes many values to create a signature (100 for example).

So, how to we generate these other values? By using more hash functions! Let's generate a set of hash functions to create a signature vector of length 20.

hash_funcs = []

for _ in range(20)

We're only showing the first three hash functions here - we have 20 in total. To create our signatures we simply process each one-hot vector through each hash function, appending the output value to our signature for that vector.

And there we have our minhash produced signature for a. Let's clean up the code and formalize the process a little.

We now have our three minhashed signatures! These signatures, despite being seemingly randomized, will on average have the very similar Jaccard similarity values as our previous sparse vectors. We have reduced the dimensionality of our vectors significantly - but maintained the same information!

a should have lower similarity with b and c:

And b and c should share much greater simliarity:

We're now ready to move onto the LSH process.

Locality Sensitive Hashing

The approach we will be taking in this notebook is break our signature vector into multiple bands, creating several sub-vectors.

We then hash each of these sub-vectors into a set of buckets, if we find that two sub-vectors from two signature vectors collide (end up in the same hash bucket) we take the two full signature vectors as candidate pairs - which we then compare in full with a similarity metric (like Jaccard similarity, cosine similarity, etc).

There is no 'set' way to hash our signature vectors, and in-fact the simplest approach is to check for equivalence across sub-vectors, which will be our approach.

First, we must define the number of buckets b we would like to create. It's important to note that each bucket must contain an equal number of rows r - and so our signature length must be divisible by b.

We'll start by splitting into 10 bands, creating rows of 2 - on the small side to be used in a genuine LSH function but good for our example (we'll explore different r and b values soon).

Let's start with our b and c vectors, which should hopefully match in at least one band.

Check if they match (we'll rewrite some of this into Numpy soon).

And let's do the same for a.

Okay great, so even with this very simple implementation - we manage to identify sentences b and c and candidate pairs, and identify a as a non-candidate.

Tuning LSH

We can visualize the probability of returning a candidate pair vs the similarity of the pair for different values of r and b (rows and bands respectively) like so: