Now we're ready to learn and apply
the idea of locality-sensitive hashing.
We're going to do this first for
the special case of minhash signatures and
later see the general LSH idea.
First, let's remember
where we've gotten so far.
We converted documents to sets of shingles
and then we converted the presumably large
sets of shingles to short signatures,
consistently a vectors of integers.
We can compare two signatures
as they make quite close to
the Jaccard similarity of
their underlying sets.
Since the signatures are relatively short,
we can fit many of them into main memory
at once and thus compare many different
pairs of these signatures without having
to spend the time needed to read
each signature from disk many times.
The idea behind LSH is to look at
the collection of elements, that is,
signatures in our example here,
whose similar pairs we want to find and
without constructing all pairs of
those elements, create a short list of
candidate pairs whose similarity
actually must be measured.
When constructing candidate pairs,
you look only at individual elements,
not at the pairs themselves.
All pairs that are not candidates are
assumed not to be similar even though in
rare cases,
there will indeed be false negative.
That is, pairs that are similar but
never checked for similarity.
For the cases of signature matrices,
we perform LSH by creating some
large number of hash functions.
These are ordinary hash functions,
not minhash functions.
For each selected hash function,
we hash columns to buckets.
For each bucket, we make all pairs
within that bucket a candidate pair.
A pair becomes a candidate
pair if any one or
more of the hash functions puts
both signatures in the same bucket.
Okay.
We need to tune the number of hash
functions and the number of buckets for
each hash function so that the buckets
have relatively few signatures in them.
That way, there are not too
many candidate pairs generated.
But we can't use too many buckets, or
else, pairs that are truly similar
will not wind up in the same bucket for
even one of the hash functions we use.
To start, we have to agree
on how similar is similar.
We pick the threshold t that is the
minimum value of Jaccard similarity for
us to regard a pair of
signatures as similar.
That is, in the ideal world, columns c and
d of the signature matrix M would be
a candidate pair if and
only if their similarity was at least t.
Remember that the similarity of signatures
is the fraction of components or
rows of the signature matrix
M on which they agree.
So we want columns c and d to be
a candidate pair if the fraction of rows
i for which m of i and c and m of i and
d are the same to be at least t.
So we need to create some
number of hash functions and
use each to hash the columns of
signature matrix M into buckets.
And we need a trick to make sure
that similar signatures, or
columns, are much more likely
to hash to the same bucket for
one of these hash functions than
if the signatures are dissimilar.
As we mentioned before, we're going
to regard a pair of signatures as
a candidate pair if even one of the hash
functions puts them in the same bucket.
So, here's the picture of how
the hash functions are created.
The yellow area is the signature matrix M.
Each column corresponds
to one signature and
each row is one of the components
of all signatures.
That is, each row was created by
applying to each of the underlying sets
one of the minhash functions we use to
create the signatures in the first place.
We divide the rows into b bands for
some number b.
As a result, there are r rows per band,
where b times r is the total
length of the signatures.
That is, the number of main hash functions
we use to create the signatures.
We're going to create one
hash function from each band.
Remember, we divided the signature
matrix M into b bands of r rows each.
From each band, we create a hash function.
This hash function hashes the values that
a given column has in that band only.
Ideally, we would make one bucket for
each possible vector of b values that
a column could have in that band.
That is, we'd like to have so
many buckets that the hash function is
really the identity function, but
that is probably too many buckets.
For example, if b equals 5 and
the components of a signature
are 32-bit integers,
then they would be 2 to the 5 times 32,
or 2 to the 160th power of buckets.
We can't even look at all these buckets
to see what is in them at the end.
So we'll probably want to pick
a number of buckets that is smaller,
say, a million or a billion.
As we said, we consider a pair of columns
and signatures to be a candidate pair if
they are in the same bucket according to
the hash function for any of the bands.
Put another way,
the only way we can be sure a pair of
signatures will become a candidate pair
is if they, if they have exactly the same
components in at least one of the bands.
Notice that if most of the components
of two signatures agree,
then there's a good chance that they
will have 100% agreement in some band.
But if they have few components in common,
then they are unlikely to
agree 100% in any band.
We'll make the mathematics more precise
shortly, but that's the intuition.
Given t, the threshold
Jaccard similarity needed for
pairs to be considered similar,
we need to tune b and r so
that most of the similar pairs
are 100% similar in at least one band.
But few of the pairs with
the Jaccard similarity less than t
are 100% similar in any band.
The only constraint we have is that
b times r has to equal the length of
the signatures.
That is, equal to the number
of minhash functions we
used to create the signatures
in the first place.
In, intuitively, if we make b large and
r small, then there are lots of bands and
therefore lots of opportunities for
a pair to wind up in the same bucket.
And since r, the width of the band,
is small, it's not hard for
a pair to hash to the same bucket for
one of the bands.
Thus making b large is
good at the similari,
if the similarity threshold
is relatively low.
conversely, if you make b small and
r large, then it would be very hard for
two signatures to hash
to the same bucket for
a given band and there a few bands that
give them the opportunity to do so.
Thus a small number of bands is best if
we have a high threshold of similarity.
Again, we'll make
the math precise shortly.
Before we go on, here's a picture of
what one of the hash functions for
LSH on signature matrices looks like.
We see one of the b bands,
the band consisting of r rows, of course.
Oh, we also show the matrix
that's consisting of several,
of seven columns or signatures.
And each of the purple rep,
rectangles represents the portion of its
column within the one band we focus on.
Now, columns six and
seven hash to different buckets.
Thus, they surely differ within this band,
so
we are not motivated to compare them for
similarity.
That is, the pair sex and
seven is not made a candidate
pair by this LSH hash function.
Perhaps column six and seven will hash
in the same bucket for some other hash
function and will then therefore
become a candidate pair from whoa.
But from what we can tell,
looking only at this one hashing,
they do not form a candidate pair.
On the other hand, columns two and
six do hash to the same bucket.
So two and
six is a candidate pair regardless
of what happens in the other bands.
There's a good chance that columns two and
six are identical within the band shown.
That is these pieces of their columns.
Are identical.
There's a small chance that these segments
of these columns are not identical, but
they just happen to hash
to the same bucket.
We will generally neglect that
probability as it can be made tiny,
like 1 in 4 billion,
if we use 2 to the 32nd power buckets.
Let's look at a particular
example to get a feel for
how the probabilities of false positives
and negatives work out in practice.
We'll assume there are 100,000 columns.
That is, we're looking for
similar documents among
a set of 100,000 documents.
We'll assume signatures are of length 100.
That is, we use the 100 minhash
functions to create the signatures.
The signature matrix M is thus
100 rows by 100,000 columns.
Notice that the signatures fit
very nicely in main memory.
Assuming the components of
a signature are 4-byte integers,
each signature takes 400 bytes and the
total space requirement is 40 megabytes.
Now, let the similarity threshold be 80%.
That is, we consider a pair
of signatures similar if and
only if they agree in at least
80 of their 100 components.
There are approximately 5
billion pairs to compare so
we'd like to use LSH to avoid
having to compare them all.
Incidentally, if you don't see why 5
billion is the approximate count of pairs,
the exact number of pairs of items
chosen from a 100,000 items is
a 100,000 choose two.
Which is a 100,000 times
99,999 divided by 2.
And if we approximate the five 9s by
a 100,000, we get exactly 5 billion.
In our example, we're going to divide
the 100 rows of signatures ma,
of the signature matrix into
20 bands with five rows each.
First, let's consider two columns,
C1 and C2,
that represent sets with
Jaccard similarity 0.8.
Notice that because of the randomness
involved in minhashing, the columns C1 and
C2 may agree in more or
fewer than 80 of their rows,
but they'll most likely have
approximately 80 equal rows.
Now, what is the probability that
these columns are 100% similar in
one given band?
Well, the probability that they
agree in any one row is exactly 0.8.
Remember that the probability
that a minhash function agrees on
two sets equals the Jaccard
similarity of the underlying sets.
So the probability that the two columns
agree in all five of the rows of
a band is 0.8 raised to the fifth power,
or approximately 0.328.
That's not very high probability, but
we have 20 chances to make the pair
of columns a candidate pair.
The probability that they do
not hash to the same bucket
in one band is 1 minus 0.328 or 0.672.
Okay.
But the probability that the columns
failed to hash to the same bucket for
any of the 20 bands is that value
0.672 raised to the twentieth power,
which is a tiny number.
It's actually this 0.00035.
The chance that pair C1 and C2 will
be a candidate pair is 1 minus that,
or 0.99965.
Put another way,
the probability of a false negative,
a pair of sets that have
Jaccard similarity 80%, but
whose signatures do not become a candidate
pair is 0.00035, or about 1 in 3,000.
Now look at a pair of sets that
have Jaccard similarity 0.4.
The probability their signatures
are identical in a given band is
0.4 to the fifth power, or about 1%.
The probability that their signatures hash
to the same bucket in at least one of
the 20 bands is surely no more
than 20 times that, or 20%.
that's, that's not great.
It means that among 40%
similar underlying sets,
there are 20% false positives, pairs of
signatures we will have to compare and
yet will find that they're not
at least 80% silar, similar.
But 20% false positives is bad,
but the false
positive rate falls rapidly as the
similarity of underlying sets decreases.
For example, for 20% Jaccard similarity,
we get less than 1% false positives.
We cannot determine the exact number
of false positives because that
depends on the distribution of Jaccard
Similarities among the underlying sets.
For example,
if most pairs of sets were 79% similar,
almost all would be false positives.
But if the typical pair of sets has
a Jaccard similarity of a few percent,
then there would be almost
no false positives.
A way to look at the problem of
designing an LSH scheme from
a minhash matrix is this.
We want the probability of two
columns sharing a bucket to be
a step function with threshold t
equal to the value at which we
regard the underlying sets similar.
That is, if the Jaccard similarity s
of the underlying sets is less than t,
we want there to be zero chance
the signatures will share a bucket for
one of the hashings and
thus become a candidate pair.
However, if the underlying
Jaccard similarity exceeds 2,
we want the pair of signatures
surely to become a candidate pair.
On the other hand, what does a single
row of a signature matrix gives us?
It gives us a straight line.
The justification is the theorem
about the probability of
two minhash values equaling the Jaccard
similarity of the underlying set.
That's not too bad.
At least the probability goes
in the right direction, but
it does leave a lot of false positives and
negatives.
That is, for a given threshold t,
all of these are false positives and
all of these are all false negatives.
But when we combine many minhash functions
into b bands of r rows each, we begin to
get an s curve shape with greatly reduced
false positive and negative regions.
We're going to derive the function that
relates the probability of two sets having
the signatures become a candidate
pair to the similarity s of the sets.
First, if the underlying sets
have Jaccard similarity s,
then the probability that their
signatures will be identical in all
r rows of one particular
band is s to the r.
So the probability that their signatures
will not be equal in this band is
1 minus s to the r.
And the probability that their signatures
will be unequal in each of the b
bands is that raised to the bth power.
Finally, the probability that
their signatures will agree in at
least one band is one minus that, or
one minus the quantity, one minus s
to the r all raised to the bth power.
Okay?
As b and r get large, this function
increasingly resembles a step function.
And the threshold at which the rise
occurs is approximately 1 over b
raised to the power of 1 over r.
For example,
in the case of b equals 20 and r equals 5,
the threshold will be approximately the
fifth root of 120th, which is about 0.55.
Here are some sample
values of this s curve for
the case we have been examining,
20 bands of five rows each.
It's not exactly a step function, but
it does get rather steep in the middle.
For example,
looks at the values between 0.4 and 0.6.
The rise from 0.4 to 0.6 is more than 0.6,
so
the average slope in
this region is over 3.
On the other hand, in the region 0 to 0.4,
the rise is less than 0.2 and
the same can be said for
the region from 0.6 to 1.
That is, the slope is less than
one-half in both these regions.
So a rough approximation to this
curve looks like, like this.
Okay, it's not exactly a step function,
but
much better than the linear
function we got from a single row.
So here's a summary of what we
need to do to find sets with
a given threshold t of Jaccard similarity.
First, we need to decide
on our values of b and r.
As we mentioned, the threshold t
will be approximately 1 over b
to the power of 1 over r.
But there are many suitable values
of b and r for a given threshold.
The larger we make b and r, that is,
the longer the signatures we use,
the closer the s curve will
be to a step function.
And therefore, the fewer false
positives and negatives we can have.
But the longer we make the signatures,
the more space they will take and
the more work it will be to
perform all the minhashing.
Then we must run the LSH
to get the candidate pairs.
For each candidate pair,
we examine their signatures and
count the number of components
in which they agree.
That way, we can determine whether
the similarity of the signatures really
does reach or exceed the threshold t.
We can rely on the similarity of
the signatures truly measuring the Jaccard
similarity of the underlying sets.
however, if we want to spend
the resources, we can go to
the sets themselves after determining that
their signatures are sufficiently similar.
In some cases, the similarity
of the soon con nutrids will
overestimate the similarities of
the sets that they represent, so
it is possible that the two sets
are not really similar enough.
By computing the Jaccard
similarity of the underlying sets,
we can eliminate the false positives.
Unfortunately, we cannot eliminate
false negatives this way.
If two sets have Jaccard
similarity above threshold, but
by bad luck, their signatures
never become a candidate pair,
then we'll never look at this pair of
signatures or their underlying sets.