So far except for a few examples, we have
learned only about how to do LSH for
declared similarity using minhashing.
There are many other notions of
similarity or distance and which one
to use depends on what type of data we
have and what our notion of similar is.
We're going to begin by studying
distance measures in general, and
see the most useful measures.
Then we'll talk about locality
sensitive families of
hash functions as a general idea.
We'll see that it is possible to
combine hash functions from a family,
to get the s curve affect that we saw for
LSH applied to mid-hash matrices.
In fact, the construction is essentially
the same for any LSH family.
And we'll conclude this unit by seeing
some particular LSH families, and
how they work for the cosine distance and
Euclidean distance.
We'll begin by introducing
the distance measures we need.
And we start with the formal
notion of a distance measure.
A distance between points in some abstract
space is intended to measure closeness and
similarity to points.
The lower the distance, the closer
the points, and the more similar they are.
Notice that jaccard similarity is
the opposite of what we mean by distance.
Jaccard similarity is higher for
similar sets than for
dissimilar sets, while a distance measure
would have their distance be lower.
It turns out that 1 minus the Jaccard
similarity is a suitable distance measure.
To start, we see two different
kinds of distance measures,
Euclidean and non-Euclidean.
Euclidean spaces have dimensions, and
a real number locates each
point along each dimension.
The ordinary two or
three dimensional Euclidean spaces
are the most common examples.
But Euclidean spaces can have any
number of dimensions, for example,
a 1 dimension Euclidean space is a
straight line infinite in both directions.
An important property of Euclidean
space is that they are dense.
That is, given any two points,
you can find their average and, and
it will be a point in the space.
We'll see some examples shortly
where there is no reasonable notion
of the average of points in the space.
That can be a problem in certain,
cer, situations.
for, for example,
if you're trying to cluster points, and
you want to represent the cluster
by a single typical point,
it's nice to be able to take the average
of the points in the cluster, but
you can't always do that for
non-Euclidean spaces.
There are many notions of distance
between points in a Euclidean space.
The best known one is often referred
to as the Euclidean distance,
where you sum the squares of the distances
between the points along each dimension.
And then take the square root of the sum.
However, we shall see that there are many
different distance measures that
also work for an Euclidean space.
We shall often refer to any of
these as a Euclidean distance.
So what about other spaces and
other distance measures?
There are many of these as well, but
a non-Euclidean distanced is based on
something other than the location
of points in a space.
A distance measure is a function
from pairs of points to some space,
in some space to real numbers.
This, this function has to satisfy
four important properties.
First, it never has a negative
value although the value can be 0.
But the value of a distance measure
could be 0 under only one condition,
that the two points to which it is applied
are actually, actually the same point.
moreover, whenever applied
to the same point,
x as both arguments, the value must be 0.
The distance is symmetric.
That is, the distance from x to y is
the same as the distance from y to x.
And most importantly, the function
must satisfy the triangle inequality.
That is, the distance from x to y
cannot be greater than the sum of
the distance going first from
x to some other point z.
And then from z to y.
You often see this idea in
the observation that one side of
a triangle cannot be longer than the sum
of the lengths of the other two sides.
The most common Euclidean
distance is the L2 norm,
which is the square root of the sum of the
squares of the distances between the two
points x and y measured in each dimension.
Another common choice for
Euclidean distance is the L1 norm,
or Manhattan distance.
If you've ever visited
Manhattan in New York
you know that the streets
are laid out in a grid.
You can't walk directly between points,
you need to first walk in one direction or
dimension, say northsouth, and
then in the other direction, say eastwest.
As a result the L1 norm
between points x and y,
is the sum of the distances between x and
y, along each the, the dimension.
Here's an example of two points a and
b in the two dimensional Euclidean space.
A is the point (5,5) and b is (9,8).
The difference between a and b,
in the horizontal dimension is 4, and
in the vertical direction it is 3.
Thus the L1 norm and Manhattan distance
between a and b is 4 plus 3 which is 7.
On the other hand,
the L2 norm is computed as follows.
We take the square of the distances 4 and
3 in each dimension.
Square them and sum them.
It's that.
And finally we take the square root.
Since 4 square is 16,
3 square is 9, the sum is 25.
The square root of that is 5.
Here's another interesting
Euclidean distance measure,
called the L infinity norm.
Here are the distance between two points,
x and y, is the largest of
the distance between x and
y in any of the dimensions of this space.
In fact we can define the L sub r norm for
any real number r.
You compute this norm by
taking the sum of the rth
powers of the differences of the two
points along each of the dimensions.
And then taking the rth root of the sum.
Notice that this definition is consistent
with the definitions we gave for
r equals 1 and r equals 2 before.
And it's also consistent with the notion
of an L infinity norm, because as r
gets larger and larger, raising numbers
to the rth power causes the largest of
them to dominate the sum, and
all other rth powers become negligible.
Then, when you take
the rth root of the sum,
you essentially are taking the rth
root of the rth power of the largest,
which gives you back essentially
just the largest of differences.
Now lets introduce the cast of characters
for the non-Euclidean distances.
First the Jaccard distance as we mentioned
is just 1 minus the Jaccard similarity.
We have to use 1 minus so
identical sets have distance 0,
and sets with no intersection
have distance 1,
which in this case is
the greatest possible distance.
And in this corner, the cosine distance.
This distance requires points to
be vectors, if the vectors have
real numbers as components, then they are
essentially points in the Euclidean space.
But the vectors could say,
have integer components in which
case the space is not Euclidean.
But either way, the cosine distance
in between the vectors is called
the cosine distance
because as we shall see.
It is generally easiest to compute the
cosine of the angle between the vectors,
and then use the cosine to
figure out the actual angle.
The edit distance applies to
points that are character strings.
The edit distance between two strings
is the minimum number of inserts and
deletes needed to transform one
of the strings into the other.
There are some other notions
of edit distance as well.
For example,
sometimes we allow a mutation as one edit.
Where a mutation changes one
character to another for
example abc could become adc in one edit.
Without mutations, we would have to
make two edits to make this change.
First we would delete the old character b,
and then second insert the,
the new character d.
So it would go a to abc to ac, and
then finally to adc in two steps.
By the way we're only going to talk about
the insert delete version of edit
distance in, in this course.
Finally, consider the Hamming distance.
It's named after Richard Hamming,
who happens to be the third
winner of the Turing award,.
And it applies to points that
are bit vectors of the same length.
The Hamming distance between two
bit vectors is the number of
positions in which they differ.
Here's an example of Jaccard distance.
Consider these two sets, x and y.
Their intersection has two members,
1 and 3.
And the union has five numbers
members the numbers one
through five thus the Jaccard
similarity is, is two fifths.
But we don't want Jaccard similarity
anymore, now we want Jaccard distance.
That's 1 minus the two-fifths giving
us a Jaccard distance of three-fifths.
So let's check the four conditions for
a di, a distance measure.
Jaccard distance is never less than 0,
because the Jaccard similarity
can't be greater than 1.
The reason for that,
is the size of the intersection of
two sets is never greater than the,
the size of their union.
Now the distance between a set x and
itself is 0.
Why?
Well, x intersect x is the same as
x union x, and both are x itself.
So the Jaccard similarity of
the set with itself is 1.
Therefore the Jaccard
distance is 1 minus 1 is 0.
We also have to check that
if x is not equal to y,
then their Jaccard distance
is strictly greater than 0.
That is because if x and
y are different, then there is at
least one element in their union
that's not in their intersection, and
therefore their intersection is
strictly smaller than their union.
That means that Jaccard similarity
is strictly less than 1,
and that Jaccard distance
is strictly greater than 0.
The symmetry condition follows
from the fact that the union and
intersection are both symmetric.
That is, x intersect y,
equals y intersect x, so
both intersects should
surely have the same size.
And, likewise for the unions.
The last thing to prove is
the triangle inequality.
That's a bit of work, but
we'll show the proof on the next slide.
Here's the inequality that says
the Jaccard distance from x to z,
plus the Jaccard distance
from z to y is equal to or
greater than the Jaccard
distance from x to y.
That is,
this is the Jaccard similarity of x and z.
The size of their intersection
divided by the size of their union.
So this is the Jaccard
distance from x to z.
And similarly this is the Jaccard distance
from y to z, and
this is the car distance from x to y.
Remember, we proved that the jaccard
similarity between sets a and
b, is the probability that the minhash
values of a and b are the same.
Or put another way.
This is the probability that
the minhash of a and b are different.
But the probability that minhash of x and
y differ,
cannot be greater than the probability
that the minhash of x and z differ.
Plus the probability that minhash of y and
z differ.
By what we saw on the previous slide,
this claim is equivalent
to the triangle inequality.
But the reason is that
whenever minhash of x and
y are different, it is impossible for
both minhash of x to equal minhash of z.
And for minhash of z to equal minhash of
y, because then by transitivity of equals,
minhash of x would be
equal to minhash of y.
So, in terms of Venn diagrams,
let the plane represent triples of sets x,
y, and z.
Here, those triples where minhash
values of x and z differ.
And here are the triples where
minhashes of y and z differ.
And contained within their union,
must be the set of triples where x and
y have different minhash values.
Another important distance
measure is the cosine distance.
Okay, this distance is useful for
data that is in the form of a vector.
Often the vector is in
very high dimensions.
For example documents are often
viewed as the vector of
counts of each of the words appearing in
the document, so each word is a dimension.
Now to define the cosine
distance think of a data point as
a vector from the origin in some space,
to the point in question.
Any two points have an angle from that
their origin between their vectors.
So we have something like this.
We can compute the cosine of this angle
from the components of the two vectors.
To do so,
we take the dot product of the vectors.
The dot product is the sum of the products
of the corresponding components.
And then we divide by
the lengths of the two vectors.
The length of a vector from the origin is
actually the normal Euclidian distance,
what we call the L2 norm, of the point
at the head of the vector to the origin.
That is it is the square root
of the sum of the squares,
of the component of the vector.
For example,
here are two vectors, P1 and P2.
The docked product of the vectors is two.
The products of each of
the first three components is 0.
That is 0 times 1 is 0,
0 times 0 is 0, 1 times 0 is also a 0.
But in the last two components each
vector is 1 do the dot-product of
the sum of 1 times 1 plus 1 times 1 and
the's 2.
For the lengths of the vector.
P1 has three 1s, so we sum three 1s
squared, and then take the square root,
giving us the square root of 3.
P2 also has three 1s and
two 0s as components, so
its length is the same square root of 3.
Thus the cosine of the angle
between P1 and P2 is two.
The dot-product, that is divided by
the product of the two vector lanes.
Each of those lengths is the square
root of 3, so that product is 3, and
the cosine of the angle is two-thirds.
If you look that up in a table
of cosine you'll find that
this angle is about 48 degrees.
So here's a diagram with the two vectors,
P1 to P2 shown on the plane
that passes through them.
No matter how many dimensions the vectors
have, any two lines that intersect, and
and P1 and P2 do intersect at the origin,
they'll follow a plane.
I'm not going to do the math, but if you
project P1 onto P2 as we have done here,
the length of the projection is the dot
product, divided by the length of P2.
Then the cosine of the angle between them
is the ratio of adjacent over hypotenuse.
Which is the dot product divided by P2,
that's the adjacent.
And then divided by the length of P1,
that's of course the hypotenuse.
Let's see why the cosine distance
satisfies the axioms of the distance.
First, remember that vectors here
are really directions, not magnitudes.
So two vectors with the same direction and
different magnitudes
are really the same vector.
Even to vector and
its negation, the reverse of the vector,
ought to be thought of as the same vector.
first, the distance between a vector and
itself is 0.
The angle a vector makes
with itself is 0 degrees.
moreover, the angle of a vector with
any different vector is not 0 degrees.
So, no pair of different
vectors have a distance of 0.
Again, remember we think of
vectors as direction only,
otherwise you could have say a vector and
twice that vector being quote different,
and yet having a 0 angle between them.
To make sure that all
distances are non-negative,
we shall interpret all angles as in
the range 0 to 100 and 180 degrees.
Notice that any two vectors from
the origin will make angle between 0 and
180 degrees in the plane they define.
The rest of the argument
is by physical reasoning.
Symmetry simply says that the angle
of a vector to x rotating to y,
is the same as the angle
from y rotating to x.
And the triangle inequality is merely the
observation that if we rotate from x to z,
and then from z to y,
the total rotation can't be less than what
we get if we rotate from x to y directly.
Now consider the edit distance.
Recall this distance measure assumes
point or character strings, and
the edit distance from x to y,
is the minimum number of inserts and
deletes needed to turn x into y.
There is an equivalent formula for
edit distance based on
the notion of the longest common
subsequence of two strings x and y.
The LCS of x and y is the longest
string that is a subsequence of both.
We say one string is a sub-sequence
of another if we can get the first by
deleting 0 or
more positions from the second.
Note that the positions of the deleted
characters did not have to be consecutive.
We'll give an example on the next
slide to make these ideas clear.
The formula for
the edit distance in terms of the LCS
is this, it's the sum of
the lengths of the two strings.
Length of x, length of y minus
twice the length of the LCS.
Here's an example where we'll compute the
edit distance of these two strings x and
y in two different ways.
First, we can turn x into y by deleting a,
and then inserting u and v,
after the d, that uses three edits,
and it's easy to check that there's no
way to get from x to y using fewer edits.
Thus the edit distance is three.
Notice that we can get from y to x
by doing the same edits in reverse.
That is, we delete u and v,
and then we insert a to get x.
In general repair, strings can have
several different LCSs of the same length.
In this case, there's only one, BCDE.
It is obtained from x by deleting
the first position and obtaining a.
And it is obtained from y
by deleting the fourth and
fifth positions containing u and v.
And to verify that the formula relating
edit distance to the LCS holds in
this case, the sum of the lengths of
the two strings is 5 plus 6 or 11.
And the LCS has a length of 4.
But 11 minus twice 4 is 3,
which is indeed the edit distance.
We can check the edit distance
also satisfies the requirements to
be considered a distance measure.
First of all, the edit distance from the
string x to itself is surely 0 because 0
edits suffice.
Moreover, if x and y are different, at
least one edit is required to change one
to the other so that no distances,
no other distances, are 0.
And there's no way for
there to be a negative number of edits,
so surely there are no
negative edit distances.
Symmetry holds because given any sequence
of inserts and deletes, say taking string
x to string y, we can reverse that
sequence, and replace the deletion of
a character C, by the insertion of C and
replace the insertion of C by a deletion.
We saw an example of this
transformation on the previous slide.
And the triangle inequality holds for
the following reason.
One way to transform x to y, is first
to transform x to z and then z to y.
The minimum number of edits needed
to make those transformations is
the sum of the edit distances
from x to z and from z to y.
But this sequence of edits is one of
the possible ways to transform x to y, so
the total number of edits is at
least the edit distance from x to y.
And next on our list is
the Hamming Distance.
And recall the Hamming distance
is the number of positions in
which two bit-vectors of
the same length differ.
So for example the Hamming
distance between P1 and
P2, is 2 because they differ
in the 3rd and 4th positions.
Here there's 1 0.
There there's 0 1.
Other than that they're,
they are the same.
The argument about why Hamming distance
is also a distance measure quite
the same as before, the Hamming distance
between a string and it's self is 0.
Because surely the string
differs in 0 positions.
On the other hand Hamming distance
between different strains cannot be 0,
because they differ in
at least one position.
There can't be a negative Hamming
distance because you can't talk about
strings differing in a negative
number of positions.
Symmetry of Hamming distance follow from
notion that the relationship different
from on bits is symmetric.
That is a is different from b,
if and only if b is different from a.
And the triangle in the equality argument
is very much like what we saw for, for
edit distance.
One way to change bit string
x to y by flipping bits,
is to first to flip bits to turn x to z,
and then flip bits to turn z to y.
The sum of these two numbers of flips
cannot be less than the number of
bits you have to flip to
turn x to y directly.