We shall now take up the essence of
what locality and sensitive hashing is
all about, by defining an abstract notion
of an LSH families of hash functions.
Using this abstract definition we show how
to build new families out of old families,
in such a way that the new family has a
steeper S-curve than the original family.
The construction we use are quite
analogous to the way we
work with minhash functions,
which are an example of an LSH family, and
use the combination into
bands to steepen the S-curve.
Before proceeding we need to explain
something about what a hash function in
the sense of an LSH family really is.
Technically a hash function h in
this sense takes two arguments x and
y, which are elements of similarity or
distance we are interested in,
and the hash function returns
a decision about this pair.
Yes means that they are a candidate pair
and we need to calculate their similarity.
We can think of yes as saying x and
y belong to the same bucket,
when hash function h is used.
But the answer no means that x and
y is not a candidate pair
according to this hash function.
For example, a minhash function can
be viewed as taking two sets x and y.
Computing the minhash values
according to some per
permutation associated
with that has function.
And saying yes, if and
only if the minhash values are the same.
In many cases, there will be a calculation
of values behind the scenes, and
the yes answers are made when
the values are the same.
However, the view we are taking
now is more general,
since there need not be a computation
of values that are then compared.
And as we shall see,
we really need this generality.
For example, we should look at LSH
families that render their decisions,
by looking at many values and saying yes,
if there is at least one equality.
However, to make things look more normal,
we shall often use
the expression h(x) equals h(y),
to mean that h of x and y is yes.
Okay, so here's the definition of
an LSH family of hash function.
First these families of hash functions,
each assume that it consists of a space of
points with a distance measure for
that space.
For example, the family of minhash
functions assumes the space of
points as sets, and
the distance is the Jaccard distance.
There is no notion of a family of
hash functions being sensitive in
some absolute sense,uh, but rather we
can make statements about a family H of
hash functions,
in terms of four parameters.
There are two distances, d1 and d2.
And there are two probabilities,
p1 and p2.
Of the two distance,
one is a small distance that's d1.
And the other is a large distance.
The probability p1 is associated with the
small distance, and it is a lower bound on
the probability of agreement, for
points at distance d1 or less.
The second probability, p2,
is associated with a large distance, and
it is an upper-bound,
on the probability of agreement for
points at distance d2 or more.
We expect p1 to be large and
p2 to be small.
'Kay, more formally, for any two
points x and y at distance up to d1,
the probability considering all
hash functions little h and
the family capital H, that little h
says yes about x and y is at least p1.
And if the distance between x and
y is at least d2,
then the probability that the little h
says yes for x and y, is at most p2.
Here's a picture of what we know about
the probability of h(x) equaling h(y).
For distances d1 and below,
we know the probability is at least p1.
And for distance is d2 and above,
we know the probability is at most p2.
Between d1 and
d2 we know nothing however we shall try
to make the difference between d1 and
d2 very small, and the distance
between p1 and p2 as large as we can.
'Kay,that will give us
the S-curve we want, although,
since we're now talking about distances
rather than similarities, the S-curve is
backwards, it drops down precipitously,
between the distances d1 and
d2, rather than rising precipitously so
it looks something like this.
Let's take as our example
the only example we know,
the underlying space consists of sets,
all sub-sets of some universal set.
And the distance measure
is Jaccard distance.
The LSH family is the family of
minhash functions, each based on one
of the possible permutations of the
members of the universal set of elements.
We claim the probability that a given
minhash function h gives the same
value for sets x and y, is 1 minus
the Jaccard distance from x to y.
That's just a restatement of the theorem,
about how the Jaccard similarity is
the probability that two sets agree
in a random minhash function.
Notice that 1 minus the Jaccard
distance is the Jaccard similarity.
We claim that the family of
minhash functions is a one-third,
two-thirds, two-thirds,
one-third sensitive family, for
the space S of sets and
the Jaccard distance d.
For example the first and third
parameters say that if the distance is at
most one-third, than the probability
of agreement is at least two-thirds.
But that makes sense,
because if the distance is at
most one-third than the Jaccard
similarity is at least two-thirds.
And we know that the probability of
agreement equals the similarity.
Okay?
Likewise, the second and fourth parameters
say that whenever the Jaccard distance is
at least two-thirds, that
the similarities is at most one-third.
The probability of agreement
is at most one-third.
We can make many statements like this
about the family of minhash functions.
There's nothing special about one-third or
two-thirds.
In fact, any distances d1 and d2,
as long as d1 is less than d2, the minhash
functions form a family with sensitivity,
d1, d2, 1 minus d1, 1 minus d2.
When we start with a simple LSH-family
such as the set of minhash functions,
we don't get the S-curve effect.
However, we're going to see that it is
possible to amplify the steepness of
the S-curve.
Using two constructions that produce
a new LSH family from a given LSH family.
These constructions are like,
are like what we've already seen for
the minhash functions.
In particular what we call the AND
construction,
is essentially the combination of
the effect of several rows in one band.
And the OR construction is
the combination of several bands.
So here is the AND construction.
We're given an LSH family H and we want to
construct from it a new family H prime,
each hash function from H prime,
is built from R functions from H.
A hash function little h
in the family h prime,
is constructed from a set of r hash
functions from family h, so h1 through hr.
Little h renders its decision
about a pair of elements x and
y by checking that each hash function
in the set, renders the decision yes.
Using our convention that h(x) equals
h(y) means that the answer for x and
y is yes, we can write the rule for
H as shown.
That is h(x) equals h(y) if, and only if,
hi(x) equals hi(y) for all i,
where i ranges now from 1 to r.
The family H prime amplifies the effect
of H, according to the rule given here.
The lower and upper distance d1 and
d2 don't change.
However, the two probabilities
are each raised to the rth power.
That is, in order to get
a yes from hash function H,
we have to get yes from each of the Hi's.
The family H prime consists of all
possible sets of r members of family H, so
the Hi's for a given H can be viewed as
randomly chosen and thus independent.
Remember that the rule for the probability
of independent events occurring
simultaneously, is the product of the
probabilities of the individual events.
The AND construction corresponds
to combining roles in the band.
We also have an OR construction that
corresponds to combining bands.
Again, we'll start with
an LSH family H and
constru, and
construct a new family H prime.
Each member of H prime will be constructed
from a set of b functions for H.
That little h be a typical member of
the family H prime, and that x and
y be elements to which we
want to apply little h.
And we say h(x) equals h(y) if and
only if hi(x) equals hi(y) for
at least one value of i and
the range of one to b.
Notice that the expression h(x) equals
h(y) really is shorthand for the way H
looks at both x and y and decides whether,
or not to make them a candidate pair.
We cannot explain what is going on by
supposing that H computes a value from x
and a value from y, and
simply asks if they are equal.
So here's the rule, for
the sensitivity of family H prime
in terms of the sensitivity of H.
As for the And Construction, the distance
components d1 and d2 do not change.
But the probabilities are altered
according to the rule, for
the probability of the or
of independent events.
To see how this combination works,
think of at least one of these events
occurs in its equivalent form, it is not
true that none of these events occurs.
If each event occurs
with probability of p1,
then the probability it
doesn't occur is 1 minus p1.
The probability that none of b events
occurs is that, raised to the bth power.
And 1 minus that, is the probability
that none of them occur it's false.
That is,
at least one of the b events occurs.
The same transformation
applies to the other,
the other probability p2, of course.
So here’s a summary of what happens when
we apply the AND and OR constructions.
AND makes both the high and
low probabilities shrink, because we’re
taking two probabilities which are less
than 1 and raising them to the rth power.
What we need to do is pick r big enough,
so
that the low probability
becomes close to 0.
Yet pick r small enough, that the high
probability stays significantly above 0.
It's a balancing act, but we'll see in
a moment, how it works in practice.
The analogous story implies to the OR
construction.
Both probabilities grow, but
we contrive the selective value of b
that makes the high probably
get very close to one,
while still keeping the low probability
significantly away from one.
Now we need to see how to compose the AND
and OR constructions in order to
wind up with an LSH family where the low
probability is essentially 0, and the high
probability is essentially one, that's
the ideal for the S-curve, remember.
In the case of signature matrices and
the AND construction, we did the AND
construction, combining rows in the band,
followed by the OR
construction combining bands.
But we could have actually done
these in the reverse order.
And it is also possible to use a sequence
of more than two of the AND and OR
constructions alternating, and we'll see
how to do, how that works in a moment.
Suppose we do the r way AND construction
followed by the b way OR construction.
The AND construction turns
a probability p, into p to the r.
Then, the OR construction turns
p to the r into this function.
Notice that what we have is exactly the S,
S-curve that we constructed when we
originally discussed LSH and
minhash functions.
We're going to do an example on the next
slide, where r and b are both 4.
That is, starting with some LSH family H,
we do a four-way AND
construction to get a family H prime.
And then use H prime to do a four-way, OR
construction to get a new
family H double prime.
So here's a table of what
happens to the probability p,
when you apply the four-way AND
followed by the four-way OR.
We could could pick the lower and
upper distances d1 and d2 as we like.
For example, here's what happens, if we
choose the lower distance d1 to be 0.2.
And the upper distance d2 to be 0.8, and
the underlining LSH family
is the midhash functions.
We start with a 0.2, 0.8, 0.8, 0.2 family.
The constructed family has
the same distances, 0.2 and 0.8.
But if you substitute p
equals 0.8 in this formula.
Well, you get this.
You get 0.8785, so, the upper
probability is raised that's good.
And if you substitute p equals 0.2,
in the same formula, you get 0.0064.
So the lower probability is lowered,
that's also good.
We also have the option of
starting with a b way, OR
construction and
then doing an r way AND construction.
The OR construction turns any
probability p, into this expression.
And then the AND
construction raises those probabilities
to the rth power, giving this formula.
The S-curve you get from this sequence of
constructions is related to what you get,
if you start with the r way AND
and then do the b way OR.
Starting with that curve,
you'd mirror it vertically and
then mirror it horizontally, or mirror it
first horizontally, then vertically it,
it doesn't matter.
The result will be the curve for
this expression.
We'll again do an example on
the next slide, it is a four-way OR
followed by a four-way AND.
So here's the table for
the OR-AND construction each using
four from the previous LSH family.
Let's see what you get when you
start with the minhash functions,
thought of as a (0.2, 0.8,
0.8, 0.2) sensitive family.
Looking up the values for probabilities
0.8 and 0.2 in the table, you see you get
a much higher probability for the low
the low distance pairs that's this.
And you also get a somewhat lower
probability, for the distant pairs.
And so again, both have been improved.
We are free to apply
construction after construction.
And if we pick the right values of r and
b, we'll keep improving both
probabilities, driving the low one
toward zero and the high one toward one.
For example, we could apply the OR
followed by AND
construction we just discussed.
And then apply the AND followed by OR
construction, discussed earlier.
That by the way would be the same as
applying a four-way OR then a 16-way,
AND and Finally another four-way OR.
Notice that each construction uses
16 of the original functions.
So by cascading these two constructions,
we use 256 minhash functions.
If you do the math, you'll find that
it transforms the minhash functions,
thought of as a 0.2, 0.8, 0.8,
0.2, a sensitive family into this.
The probability of saying yes for
sets at Jaccard distance 0.2 or
less is this, which is almost precisely 1.
That is there are very,
very few false negatives.
But the probability of saying yes for
sets of Jaccard distance 0.8 or
more, is this very small probability.
thus, at least among pairs
that are really far apart,
the number of false positives is tiny.
You might look at this analysis and
observe that we
don't know anything about what happens
between the similarities between 0.2 and
0.8 and that's a big range.
However, suppose our application
is shingled web documents.
If we take two random web pages and
we have used a large enough
shingle length, say nine or 10.
The two random documents will have
very small Jaccard similarity.
And this is Jaccard distance above 0.8.
Only if there is some special cause for
similarity, say a mirror page or
plagiarism, will the Jaccard
distance be low.
In those cases we expect it to
be very low, probably under 0.2.
That is to say there simply aren't many
pairs, at distance between 0.2 and
0.8 in this application.
The conclusion is that for the particular,
this particular application, we might
be happy with distances 0.2 and 0.8.
But we are free to make
the distances be whatever we want,
as long as the first is
less than the second.
For example,
we could start with a 0.49, 0.51,
0.51, 0.49 sensitive family.
And do constructions that would drive
the probabilities initially 0.51 and
0.49, close to one and zero respectively.
course, of course we would need many
more than 256 of the base functions to
get such a steep S-curve.
What I'd like to do now is explain how to
select the values of r and b, for AND and
OR constructions.
Let's look at the function that we've
called the S-curve, that's this.
This is a function of the probability p,
and it has two parameters r and b.
An interesting observation
is that this curve.
Okay, let's.
Draw something like that
here it has a fixed point t,
such that if p equals t then the result of
applying the function to t is t itself.
To see the t exists, look at where the
curve intersects the line with slope 1.
So that would be the value of t.
Above probability t, applying the S-curve
function increases the probability,
while below t, the probability decreases.
We can conclude that as long the two
probabilities are on opposite sides of t,
the construction where you do an r way and
followed by a b way OR,
will move both probabilities,
in the direction we want them to go.
We can then iterate this construction
as many times as we like, and
both probabilities will keep improving.
There is an analogous observation about
a construction where we do an, OR
followed by an AND.
The S-curve formula is a little different,
but the ideas are quite the same.
Here is a picture
suggesting what happens for
the S-curves that we get for both the AND
and OR, or OR-AND constructions.
The threshold is defined by
the place where the S-curve, and
the straight line cross.
'Kay, for probabilities p below t,
applying the S-curve function
lowers the probability.
While for probabilities above t, the
S-curve sends p to a higher probability.