CHRISTOPHER POTTS: Welcome back, everyone.
This is part 3 in our series on distributed word
representations.
We're going to be talking about vector comparison methods.
To try to make this discussion pretty intuitive,
I'm going to ground things in this running example.
On the left, I have a very small vector space model.
We have three words, A, B, and C.
And you can imagine that we've measured two dimensions, dx
and dy.
You could think of them as documents if you wanted.
There are two perspectives that you might take
on this vector space model.
The first is just at the level of raw frequency,
B and C seem to be united.
They are frequent in both the x and the y dimension.
Whereas A is comparatively infrequent along both
those dimensions.
That's the first perspective.
The second perspective, though, is more subtle.
You might just observe that if we kind of correct
for the overall frequency of the individual words,
then it's actually A and B that are united.
Because they both have a bias in some sense for the dy
dimension.
Whereas by comparison, C has a bias for the x dimension,
again, thinking proportionally.
Both of those are perspectives that we might want to capture
and different notions of distance
will key into one or the other of them.
One more preliminary, I think it's very intuitive
to depict these vector spaces.
And in only two dimensions, that's pretty easy.
You can imagine that this is the dx dimension along the x-axis.
And this is the dy dimension along the y-axis.
And then I have placed these individual points
in that plane.
And then you can see graphically that B and C are pretty close
together.
And A is kind of lonely down here
in the corner, the infrequent one.
Let's start with Euclidean distance,
very common notion of distance in these spaces
and quite intuitive.
We can measure the Euclidean distance between vectors u
and v if they share the same dimension n by just calculating
the sum of the squared element wide differences,
absolute differences, and then taking the square root of that.
That's the math here.
Let's look at that in terms of this space.
So here we have our vector space depicted graphically,
A, B, and C, and Euclidean distances measuring
the length of these lines.
I've annotated with the full calculations.
But the intuition is just that we
are measuring the length of these lines, the most
direct path between these points in our high dimensional space.
And you can see that Euclidean distance is capturing
the first perspective that we took on the vector space, which
unites the frequent items B and C as against the infrequent one
A. As a stepping stone toward cosine distance, which
will behave quite differently, let's
talk about length normalization.
Given the vector u of dimension n, the L2 length of u
is the sum of the squared values in that matrix.
And then we take the square root.
That's our normalization quantity there.
And then the actual normalization
of that original vector u involves
taking each one of its elements and dividing it
by that fixed quantity, the L2 ranks.
Let's look at what happens to our little illustrative
example.
On the left here, I have the original count matrix.
And in this column here, I've given the L2 length
as a quantity.
And then when we take in that quantity
and divide each one of the values in that vector
to get its L2 norm, you can see that we've done something
significant to the space.
So they're all kind of united on the same scale here.
And A and B are now close together.
Whereas B and C are comparatively far apart.
So that is capturing the second perspective
that we took on the matrix, where A and B have something
in common as against C. And that has come entirely
from the normalization step.
And if we measured Euclidean distance
in this space, just the length of the lines
between these points, we would again
be capturing that A and B are alike
and B and C are comparatively different.
Cosine kind of does that all in one step.
So the cosine distance or approximately the distance,
as you'll see, between two vectors
u and v of shared dimension n.
This calculation has two parts.
This is the similarity calculation, cosine similarity.
And it is the dot product of the two
vectors divided by the product of their L2 lengths.
And then to get something like the distance, we just take 1
and subtract out that similarity.
Again, let's ground this in our example.
Here we have the original count vector space model.
And what we do with cosine distance
is essentially measure the angles between these lines
that I've drawn from this origin point.
And so you can see that cosine distance is capturing the fact
that A and and B are close together
as measured by this angle.
Whereas B and C are comparatively far apart.
So again with cosine, we're abstracting away
from frequency information and keying
into that abstract notion of similarity that
connects A and B as against C.
Another perspective that you could take
is just observe that if we first normalize
the vectors via the L2 norm and then apply
the cosine calculation, we changed the space
as I showed you before.
So they're all up here kind of on the units here.
And notice that the actual values that we get out
are the same whether or not we did that L2 norming step.
And that is because cosine is building
the effects of L2 norming directly
into this normalization here in the denominator.
There are a few other methods that we could think about
or classes of methods.
I think we don't need to get distracted by the details.
But I thought I would mention them
in case they come up in your reading or research.
The first class are what I called matching based methods.
They're all kind of based on this matching coefficient.
And then Jaccard, Dice, and Overlap
are terms that you might see in the literature.
These are often defined only for binary vectors.
Here, I've given their generalizations
to the real valued vectors that we're talking about.
And the other class of methods that you might see come up
are probabilistic methods which tend
to be grounded in this notion of KL divergence.
KL divergence is essentially a way
of measuring the distance between two probability
distributions.
To be more precise, from a reference distribution p
to some other probability distribution q.
And it has symmetric notions, symmetric KL,
and Jensen-Shannon distance, which
is another symmetric notion that's based in KL divergence.
Again, these are probably appropriate measures
to choose if the quantities that you're thinking of
are appropriately thought of as probability values.
Now I've alluded to the fact that the cosine distance
measure that I gave you before is not quite what's called
the proper distance metric.
Let me expand on that a little bit.
To qualify as a proper distance metric,
a vector comparison method has to have three properties.
It needs to be symmetric.
That is, it needs to give the same value for xy
as it does to yx.
KL divergence actually fails that first rule.
It needs to assign 0 to identical vectors.
And crucially, it needs to satisfy
what's called the triangle inequality, which
says that the distance between x and z is less than
or equal to the distance between x and y and then y to z.
Cosine distance, as I showed it to you before,
fails to satisfy the triangle inequality.
And this is just a simple example
that makes it intuitive.
It just happens that this distance here
is actually greater than these two values
here, which is a failure of the statement of the triangle
inequality.
Now this is relatively easily corrected.
But this is also kind of a useful framework.
Of all the different choices that we could make,
of all the options for vector comparison,
suppose we decided to favor the ones that counted
as true distance metrics.
Then that would at least push us to favor Euclidean distance,
Jaccard for binary vectors only, and Jensen-Shannon distance
if we were talking about probabilistic spaces.
And we would further amend the definition of cosine distance
to the more careful one that I've given here,
which satisfies the triangle inequality as well
as the other two criteria.
And by this kind of way of dividing the world,
we would also reject matching Jaccard, Dice, Overlap, KL
divergence, and symmetrical KL divergence
as ones that fail to be proper distance metrics.
And so that might be a useful framework for thinking
about choices in this space.
One other point in relation to this.
This is obviously a more involved calculation
than the one that I gave you before.
And in truth, it is probably not worth the effort.
Here's an example of just a bunch of vectors
that I sampled from one of our vector space models.
And I've compared the improper cosine distance
that I showed you before on the x-axis
with the proper cosine distance metric that I just showed you.
And the correlation between the two is almost perfect.
So there is essentially no difference
between these two different ways of measuring cosine.
And I think that they are probably
essentially identical up to ranking, which is often
the quantity that we care about when
we're doing these comparisons.
So probably stick with the simpler and less involved
calculation would be my advice.
Let's close with some generalizations
and relationships first.
Euclidean, as well as Jaccard and Dice with raw count vectors
will tend to favor raw frequency over other distributional
patterns, like that more abstract one that I showed you
with our illustrative example.
Euclidean with L2 norm vectors is
equivalent to cosine when it comes to ranking, which is just
to say that if you want to use Euclidean
and you first L2 norm your vectors,
you're probably just doing something that might as well
just be the cosine calculation.
Jaccard and Dice are equivalent with regard to ranking.
That's something to keep in mind.
And then this is maybe a more fundamental point
that you'll see recurring throughout this unit.
Both L2 norming and also a related calculation
which will just create probability distributions out
of the rows.
They can be useful steps, as we've seen.
But they can obscure differences in the amount or strength
of evidence that you have, which can in turn have
an effect on the reliability of, for example,
cosine, non-Euclidean, or KL divergence.
Right, these shortcomings might be addressed through weighting
schemes though.
But here's the bottom line.
There is valuable information in raw frequency.
If we abstract away from it, some other information
might come to the surface.
But we also might lose that important frequency information
in distorting the space in that way.
And it can be difficult to balance these competing
pressures.
Finally, I'll just close with some code snippets.
Our course repository has lots of hand utilities
for doing these distance calculations and also
length norming your vectors and so forth.
And it also has this function called
Neighbors in the VSM module.
It allows you to pick a target word
and supply a vector space model.
And then it will give you a full ranking
of the entire vocabulary in that vector space with respect
to your target work, starting with the ones that are closest.
So here the results for "bad" using cosine distance
in cell 12 and Jaccard distance in cell 13.
And I would just like to say that these neighbors don't look
especially intuitive to me.
It does not look like this analysis
is revealing really interesting semantic information.
But don't worry, we're going to correct this.
We're going to start to massage and stretch
and bend our vector space models.
And we will see much better results for these neighbor
functions and everything else as we go through that material.