So the last way in which we're
going to use KD-trees for nearest neighbor search is for
approximate nearest neighbor search. And this is something that we're going to
spend a lot of time talking about in the next section. But this idea,
it's really important because so far, everything we've been
talking about assumes that out of all the articles out there,
you want to find the nearest neighbor. But that assumption relies so heavily on
first assuming that it's important to find the nearest neighbor and
not just a good alternative. But also the fact that you really believe
in your representation of your data, as well as the distance measure that you're
using to compute these similarities. because if you don't really have
100% faith in those to begin with, then what's the difference of finding
the nearest neighbor versus one that's, pretty, pretty, pretty close to that. So a question is,
can we do things even more efficiently if we don't care about finding according
to our setup, the nearest neighbor but just a pretty good approximation? So within the context of KD-trees, the way we can do our approximate
nearest neighbor search is as follows. Remember before, we maintained the distance to
the nearest neighbor found so far. So this, I'm going to call r = distance to nearest neighbor so far. But now, what we're going to do,
is we're going to, instead of pruning based on the distance
to the nearest neighbor so far, we're going to prune more aggressively. That's what's going to give
us the added efficiency, but at the cost of an approximation. And to prune more aggressively,
instead of pruning based on distance r, we're going to prune based on a distance,
r over alpha where alpha is some number greater than 1. And so this is going to be
a smaller radius that we're using. So it means it's more likely that
the distance to the bounding box exceeds r over alpha than it does just r. Okay, so what are the properties of
performing nearest neighbor search with this more aggressive pruning? Well, we know that if we return
a neighbor at some distance r, then there's no neighbor
within r over alpha. So, what we're saying here is, let's say this is our query point Xq. This is our distance r, this is the nearest neighbor
that we're going to return. If we look at, let me draw in a different
color, I think it'll help make this clear. So if this is r over alpha, Then we know that there
could be points here. So, these would all be, Data points that were actually closer than
the nearest neighbor that we returned. But we know,
That there's no points within this box. Otherwise we would have found them and that would have been our
distance to the nearest neighbor. And we're pruning all other things
that fall further from that. Okay, so by doing this,
we get a fairly good approximation, and actually this bound that we're
stating here is rather loose, and in practice, we're often much
closer to the optimal solution. And importantly, it just saves
a ton of searching you have to do, of course if alpha is reasonably large. If alpha becomes 1, then it defaults back
to our exact nearest neighbor search. Okay, so in a lot of cases, doing
approximate nearest neighbor search is pretty much just as good as what you would
do with brute force, because there's so much noise in how you're thinking about
computing distances to begin with. And whether that's really relevant to, let's say I'm sitting
here reading an article, whatever you're going to present me as
a pretty good approximation to the nearest neighbor is probably going to satisfy my
needs for exploring other literature. Okay, so we're going to talk a lot more
about alternative ways to do approximate nearest neighbor search, but in ways that
also scale better with higher dimensions. But within the context of KD-trees, this is a very effective way of performing
approximate nearest neighbor search. So to wrap up on KD-trees, first I want to say that they really are
a very cool and efficient data structure. But I also want to discuss
a few other things. One is the fact that there are lots and
lots of variants. We talked about some of these in terms of
heuristics for how to choose the splitting dimension and the splitting value,
and all sorts of other things. And, in addition, instead of just
making these axis-aligned cuts, there are other ways of
performing a KD-tree. Well, it's really these ball-trees and
different shapes you can plop down. And what were going to talk about next is, you can think of it as one of these
alternatives to these axis-aligned cuts. And the other thing that we've seen so far is the fact that in performing
nearest-neighbor search, things rely very, very heavily on how you're
representing your data, and how you're computing the distance
between two different data points. And for both of these, KD-trees and
nearest neighbor search, things become much, much more challenging
when you're in high dimensional spaces. So for KD-trees, we talked about
the fact that the number of inspections you have to do can be exponential
in the dimensionality. So just as a rule of thumb, typically KD-trees are only useful if the
number of observations you have is much, much larger than 2 to the d,
2 to the number of dimensions you have. So in high dimensional cases,
often you don't have enough observations to really make a KD-tree worthwhile. And in terms of thinking about
nearest neighbor search for getting the challenges just of KD-trees,
in high dimensional spaces, things are really hard, because from
a really high dimensional feature vector, a lot of those features are going to
be basically just noise. And those can be swamping
your distance calculations. And so, what happens is in
a high dimensional spaces, basically everything is far
away from itself or each other. And so, you really need techniques to
learn which features are important or how do you think about wading
across the different features. And like we mentioned before, that's
a really, really challenging task that requires a lot of domain knowledge or
a lot of thought and exploration. And lastly, I really want to thank Andrew
Moore for the outline of these slides. The slides on KD-trees were built
very heavily from a really nice presentation that he put
together on KD-trees. So thanks for the permission to use that. [MUSIC]