[MUSIC]
So up to this point, we've described just the concept of partitioning our data,
just using these simple lines.
And I should have mentioned that in everything we're going to describe here,
we're just going to assume that there's no intercept term to the line, so
it's always just going to go through the origin.
So it's a very simple structure, a very simple way to think
about partitioning our data into two separate bins.
And then it’s a very simple way that we can just search along the points that
fall into each of these partitions.
But there are number of questions that we might be faced with.
So one of these questions is how do we think of defining a good line
to split the points?
And associated with that question is,
what's the resulting quality of this type of nearest neighbor search?
We said that it provides an approximate nearest neighbor search, but
what are the chances that we're actually going to find the nearest neighbor
to a given query point?
And then finally, what types of efficiencies are we actually going to get
from the simple partitioning of data points?
Well, let's start with the question on how are we going to define this line?
And for this, let's propose something that sounds really, really crazy.
What if we just draw the line randomly?
Just randomly throw down a line that goes through the 0, 0 point.
Well, how bad can this be?
It sounds that could actually be really, really bad, but
let's think through this a bit.
And remember that our objective is if two points are close together, and
here we're going to be focusing on cosine similarity when
we're talking about the distance between two different points.
Well, our goal is that if they're close together according to cosine similarity,
then we want those two points to fall into the same bin.
To formalize this a bit, let's just say that the angle, remember that cosine
similarity is defined in terms of the cosine of the angle between two points.
So let's say that there are two points, x and y.
And the angle between x and y is theta xy.
Okay, now let's just start drawing lines randomly.
So here's one line.
And this line happens to put both x and y into bin 0,
because the score of both of the points is less than 0.
Here's another line and another, and another, and another.
And here's a whole bunch of lines that all place x and y into the same bin, bin 0.
Well here's a line that places both x and
y into bin 1 since both of their scores are greater than 0.
And here's another one, another one, another one, another one, another one.
Whole bunch of lines that all place x and y into the same bin, bin 1.
But we can make mistakes, of course.
Here's one line that separates x and y, so that they will be put into different bins.
Because the y point has a negative score so that's going to be in bin 0,
the x point has a positive score, it's going to be in bin 1.
And here are some other lines that would do the same thing.
Okay, so what we're saying is that this whole range of points here
that I'm showing in blue place both x and y into the same bin, bin 1.
And all of these points, or all of these lines that would fall into this
orange region that I'm showing here, place both x and y into bin 0.
But then there's this green range where any line that falls
in that space is going to put x and y into separate bins.
But a question is, what's the chance of that happening?
Well, if theta x, y is really small,
then there's just a small chance that a random line placed, let's say,
uniformly at random from 0 to pi over 2,
there's just a small chance that it's going to fall within that theta range.
So what that means is that there's just a small probability that x and
y are going to be put in different bins, so if x were our query,
then we wouldn't find it's nearest neighbor y which was in some other bin.
So in summary,
this idea of just throwing down a random line, it's actually not that crazy.
We're saying that it provides good performance in terms of a probabilistic
statement of providing exact nearest neighbors for lots and lots of queries.
Okay, so far what we've done is we've talked about the first two points.
We showed how we can just very simply throw it out of line,
nothing challenging to how we have to think about defining that line.
And we also showed that we can get very good performance in terms of nearest
neighbor search with this very simple approach.
However, there's this really, really problematic last third point which is what
are the efficiencies that we get from this approach?
And if we think about just throwing down one line, then what happens is that
we often end up with bins that still have lots and lots of data points.
If we assume we have lots and lots and lots of data points to begin with, if we
just partition them into two sets, we're probably going to end up with two bins,
each of which have lots and lots of datapoints.
And a query is going to have to search over lots and lots of points.
Okay, so
it seems like we've gained something in terms of efficiency but not that much.
So let's think about how we can address this.
[MUSIC]