There is an important intuition behind LSH and similar concepts called dimensionality
reduction. Now think of the space or the collection
of objects for example you can think of fingerprints.
It's D dimensional where you know D is thousand because every print can be
represented by D dimensional vector which has 1's and 0's.
1's where there are many [inaudible] 0's where there are not.
1000 because we had a 25 by 40 grid. There are lots and lots of possible
objects in this space, not all of which are fingerprints, but definitely the space
is very, very large. Two to the 1,000 is really, really huge.
What LSH does intuitively, is it reduces the dimension to just b hash values, and b
is small, 1,024 in this case. Further.
The fact that we use random hash functions.
Turns out to make them locality sensitive. Now, this is a very deep idea that random
choices and random functions actually work really well, and we won't delve into why
that happens right now, but that's another important intuition.
As a result, similar objects map to similar hash values.
It also turns out that, LS aged techniques are closely related to other kinds of
dimensionality reduction, methods, such as for discovering topics in large document
collections objects in videos and images, and many other.
A caveat though, implementing LS Age can be a bit tricky, especially in parallel,
and something we're going to look into during our discussion on big data
technology and map reduce. Let's return now to our hidden agenda.
We are trying to understand something about human memory from all the techniques
that we've been studying. One question we should think about is do
we actually store all the objects, such as images and experiences that we get at,
exposed to? Do we have a large disk space somewhere
and I had where, things are just kept in full fidelity, probably not.
Way back in the late'80s and early'90s, Pentti Kanerva then working at NASA.
Came up with a concept called sparse distributed memory.
Which tried to model how humans actually store data.
In particular, high dimensional data like images, experiences, and many of the
things that we are exposed to are high dimensional.
So this stuff pre-dates LSH, is also related to high dimensional spaces.
But rather than reducing the dimension, it also exploits the fact that the space is
high dimensional. Space distributed memory exploits some
rather peculiar features of high dimensional spaces.
An example of a high dimensional space that we've already seen is this space of
thousand bit vectors such as all possible grid cells of 25 by 40 with 1's and 0's
that we use for fingerprints. There are lots of these to a thousand
many, many hundred of 0's behind that. Now, think about any two random
thousand-bit vectors. What would be the average distance between
these in terms of the number of bits in which they might defer?
What do you think? Well, quiet obviously 500 because in on
the average, you would toss a coin to decide whether the two vectors differed
from each other, and half the time they wouldn't, half the time they wouldn't, so
in half the, the bits they would differ, in half they would be the same.
Now consider, a vector X shows in at random, could be anyone.
We start from this one vector x and ask these few interesting questions.
Clearly, half all of the other vectors are less than 500 bits away from this vector,
and half of them are more than 500 bits away from this vector.
That is, again, obvious by a choice, by, by tossing a coin.
The really interesting thing. It's when we ask the question how many of
all the other vectors defer from our chosen x?
While less than 450 bits. Now remember, half of the vectors deferred
by less than 500 bits. Well, how many differ by less than 450
bits? So we toss a coin, and if the coin comes
up heads we, assume the other vector differs, from x and otherwise it doesn't,
so we toss a 1000 coins and figure out, whats the chance, that we will have, less
than 450 heads. Actually, it's a quite, quite a small
chance that comes from probability theory. We use the binomial distribution, with a
mean of 500 and N equal to 1000 because we are tossing a 1000 fair coins.
The standard deviation of this is, square root of 250.
You can look this up in any probability text book.
We approximate the binomial distribution by a normal distribution.
And then we see that. Very interestingly, a very, very small
fraction of all the other vectors are less than 450 bits from x.
So what that means is that with a very, very high probability most of the other
vectors are. Within a band of 450 and 550 bits away.
Remember the normal distribution is symmetric, so what we did for, how many
other vectors differ from X by less than 450, can be repeated symmetrically for
asking the question, how many will differ from X by more than 550.
So we'll, we have this very interesting situation that, almost all vectors, in
this huge space. Are far away from x.
Somewhere around 500 bits away.