My name's David Thompson and this is the
second lecture in a series on
dimensionality reduction.
In the first lecture I described some
local methods for pattern recognition
which include nearest neighbor approaches
and
locally linear regression among other
things.
This is where,this is the lecture where we
really start to get into dimensionality
reduction proper.
I'm going to talk about what happens as
we start going into higher dimensional
spaces.
From those simple examples that I showed
you before and in
particular I'll introduce a concept known
as the curse of dimensionality,
which is a perennial challenge for all
sorts of pattern recognition
problems so it's something that you all
should be aware of.
And know how to solve.
All right, so the objectives of this
lecture are
to, one, know how to find nearest
neighbors efficiently.
This is something that I really glossed
over in the last slides.
But as we start moving away from toy
examples this question will become more
and more important.
The notion of how to, how to perform these
calculation in an efficient manner.
At because in, in lotta cases the naive
approach really doesn't work very well.
The second objective is to understand the
curse of dimensionality.
What is it?
It sounds pretty ominous, and in fact it
is of, like I said, it's, it's
a real challenge for a lot of, for
scaling up these approaches to higher
dimensional spaces.
So you should know it's implications for
pattern recognition.
And I'll also start I'll wet your appetite
with some
idea of the general approaches that we'll
use in later lectures.
To solve the curse of dimensionality.
Okay, as a review local pattern
recognition involves
inferring something about the process that
generated the data
or some underlying function of the data by
looking in the local vicinity of your
query point.
Examples are K-nearest neighbor
classification local
linear regression, and Kernel density
estimation.
These all rely on the ability to find
these nearest neighbors fairly quickly.
Or maybe, beyond nearest neighbors, the
notion of a range query, that is, finding
points within a certain radius of your,
your query point, which is a related
problem.
But in general, we're going to have to
find a lot of nearest neighbors in data
sets that could be as large as hundreds of
thousands or even millions of data points.
All right, so this is the case where we're
looking for nearest neighbors with a one
dimensional data site.
Here I've shown you the entire data set X.
Right, which contains just a single
attribute.
Right so a single numerical input
attribute.
And we have a new data point which is here
four.
And we're trying to find its nearest
neighbor in this data set.
So the question is how do I do that
efficiently?
And the standard sort of naive approach to
doing this would simply be to take the
four, and march down this list of data
points and compare it to each one in turn.
Keeping track of the closest neighbor that
I found so far.
So when I reach the end of the list then
I'll
absolutely know with certainty the closest
neighbor in the data set.
Unfortunately this this sequential search
actually takes linear time to accomplish
which means it's not that tractable
computationally for very large data sets.
The, the time required, the number of
comparisons grows proportionally with the
number of data
points, so if you get up to data sets
containing say a million data points.
This will be pretty onerous to perform.
It'll be particularly challenging if we
have to do this as an inside loop in some
of the larger pattern recognition process,
like say
cross validation or a change in chrono
hits.
We may have to try this once for every
data point, in which case
the total complexity of the algodon would
scale polynomially with the number of data
points.
So that would be you know, a million times
a million, and that's
a, that's a lot of, of calculations that
you might have to do.
So this quickly becomes untractable and we
need to find some
more efficient way in order to generalize
nearest neighbor to higher dimensions.
Or to, or rather to larger numbers of, of
data points.
So in the 1D case there's a straight
forward approach which is to sort the
list, right?
So, you can presume that we have some sort
of strategy, some sorting algorithm, that
will, in sub-linear time, let us sort the
list into an ordered set of data points.
And indeed these algorithms exist.
So, after we've sorted the list into our
new
representation in our, in the computer
memory, X prime,.
Then we can actually search this space
more efficiently.
In, in fact the, the standard way of doing
this is called a, a binary search.
So we take our, our query point and look
at the, the midpoint in the sorted list.
And ask, is it greater than or smaller
than this?
And, how close are we to that, to that
nearest neighbor?
so, or, to that, to that point in the
dataset.
And based on the answer to our query, we
can go left or right up and descend
down this, this what amounts to a
branching tree
of, of decisions, bifurcating the list at
each time.
Until we arrive at a neighborhood of
points that are more or
less, in this case, they're more or less
equidistant from our, our query.
Note that in just three comparisons here,
we've,
we've already established the nearest
neighbors of this point.
There are, that is equidistant from
between points three and five.
Whereas before we would've potentially had
to make you know, ten
or, or 20 different comparisons, to arrive
at that same decision.
The, the real advantage is the, the
scaling property.
Because we can eliminate half of the data
set.
With every query that we perform, it
scales with Lawburn
Neck time which makes it tractable for
large data sets.
So it's a more efficient way of, of doing
the same, the same operation.
So this is the Wendy case.
So, how would we perform nearest neighbors
efficiently in higher dimensional spaces?
Well, it's not immediately obvious what
the higher
dimensional analog to the sorted list
would be.
But fortunately researchers in the
computer [UNKNOWN] literature
have dealt with this problem for a long
time.
They've come up with a wide range of data
structures that
will help us do efficient nearest neighbor
queries in high dimensional cases.
And I'll show you one of the most common
ones on the next slide.
All right, so this is the, the, K-D Tree
which works pretty
well from anywhere two to eight dimensions
of the, of the inputs space.
And the idea is to take your data, to take
your data set, and arrange it such that
it's lies in a tree structure, here at
left,
where each node splits the space with a
hyperplane, right?
And half of the, and the points on one
side of the
hyperplane constitute half the data set,
and the remaining half of the data
set goes on the other side of the
hyperplane, which lets us eliminate
at each step, at each query point, about
half of the data set.
now, which hyperplane do you use?
Well, the most common choice to this, is
to cycle through the attributes one at a
time.
So you start, and just split the data set
along the first attribute just like a
regular sorted list.
And then, in the second level of the tree,
the
second tier of the hierarchy, you'd split
on the next attribute.
And simply continue cycling through until
you reach the
end of the attributes and then start
cycling again.
And this it can be depicted graphically
here, at
right, we have a data set of 6 points.
And I've shown them, plotted them in
two dimensional space together with the
different splits.
So our first split is along that point A,
that
bifurcates the data neatly into two halves
along the X-axis.
And then the next stage of the tree is
the, the B points, right, which
bifurcate the data their respective data
sets along the Y-axis and it continues on.
And using the strategy we can perform
queries efficiently by eliminating
half the data sets at each stage of, of
the tree.
So, exactly the same computation benefits
that we get from the sorted list.
But here in, in two dimensions.
So, our typical search is order and log
in.
the, the computational properties tend to
degrade at around six to eight
dimensions when it starts to look less
efficient for newest neighbor queries.
And for that, we'll need more
sophisticated algorithms.
But typically, the K-D Trees are the first
tool that, in a toolbox that I reach for.
For nearest neighbor queries, in the range
of two to eight dimensions.
They can also be used for things like
range
queries, if you want to find all of the
points in
a data set that are within a certain range
of target points, then they can do that as
well.
And there exists lots of good efficient
implementations available
that I hardly encourage you to avail
yourself of.
All right, so for higher dimensions it,
it, one
typically uses an approximate nearest
neighbor strategy so this,
this works for as many as a dozen or
more dimensions they base, the basic idea
is to leverage
the fact that, well for, for many of these
data sets we're most interested in an
approximate nearest
neighbor is almost as good as the actual
nearest
neighbor so if we're willing to sacrifice
those hard guarantees.
That will find the exact response to our
query but are, are okay
with a little bit of error within some
epsilon value that we define.
Then an approximate nearest neighbor
calculation
can, can get some more results.
And so this, this tends to work better
above eight to ten dimensions.
And again many refined implementations
exist
in lots of different programming
languages.
All right so now I want to go on to to
talk about
when some of these methods even failed be,
beyond 15 or 20 dimensions.
There are lots of cases where nearest
neighbor methods just don't work
for other reasons and that involves
something known as the cursive
dimensionality.
A more fundamental problem is, is, when,
when is the nearest neighbor meaningful at
all?
Right?
And you can quite easily construct cases
where, or data sets, that
are sort of pathological, where nearest
neighbor queries really don't make much
sense.
And this is, this is one.
So we have a, a query point X in the
center of our data cloud.
Not that the, our training data, which are
here represented as Os,
are all more or less equidistant from our
query point X right.
So the fact that we go with one
nearest neighbor or another is really sort
of arbitrary.
That the structure, whatever structure is
present in the
data, really won't be captured by nearest
neighbor query.
It will be very sensitive to the precise
location of X in the input space.
And you can say, well, this is a strange,
crazy example, right?
This would never happen in practice.
But in the next couple of slides, I'm
going to
show that for actually, for very high
dimensional spaces
that is above a couple of dozen
dimensions, every
pattern recognition problems starts to
look exactly like this example.
Right.
Which means that the entire toolbox of the
local pattern recognition
methods that we've established, won't work
for these higher dimensional spaces.
One way to show this is to look at the
volume of an N-Ball.
So an N-Ball is just the, the higher
dimension generalization of a circle or a
sphere
and it describes all of the, the points
that are a certain distance from our
target.
Right, so this would be, so if we were
performing a nearest
neighbor based classification or some sort
of local pattern recognition strategy,
we'd
want a couple of data points in the local
N-Ball, right, in
order to decide what the, the, the
appropriate inferences at the query point.
So this is an expression for the volume of
an N-ball with a number of dimensions, N.
And note in particular the gamma function
in the denominator.
This is the, the real value generalization
of the factorial function, right?
And we all know the factorial function
goes up, starts
to go up very highly, very quickly for
higher values, right?
Beyond about five or six, it really starts
to explode.
So, we're getting here is an exploding
denominator, right?
So that the volume of the N-ball relative
to the
volume of the hypercube that encloses it,
is actually decreasing.
Right, so here is the, here's the plot
actually of the ratio.
So I plotted here the ratio of the volume
of the N-ball that's
described within a hypercube as the number
of dimensions of our input space
increases.
You can see just look at the, the Y-axis
here.
We're already for say eight or nine
dimensions, we're already up in the
hundreds.
All right.
So what does this mean?
This means that our inscribed N-Ball,
which I've shown here in two dimensions
at, at right co, comprise the much smaller
portion of the input space.
Right?
Most of the volume of these high
dimensional spaces
is very far from the, the center of the
N-Ball.
Right?
So, if we were to evenly distribute a
bunch of points in this high dimensional
space, it'd be very rare that any of them
actually fall in the, in the N-Ball.
They almost, all be more or less
equidistant from the N-Ball, outside it in
these corners which start to look
extremely
long and spiky in high dimensional spaces.
But this, this is kind of non-intuitive,
right?
Because we're used to thinking about these
well behaved
two and three dimensional volumes, it's
what we can visualize.
But in fact, the properties of
these high dimensional spaces, the
geometric properties.
are, are not at all amenable to the
sort of nearest neighbor approaches for
just this reason.
We've got all of our volume in these long,
spiky structures that, that are far from,
from the query.
All right, so everything starts to look
like that pathological case that I
showed you before where all of the data is
more or less equidistant.
And it's very susceptible to noise in, in
the input space and the, the training
data, right.
So evenly distributed data points and high
dimensional
spaces are generally a bad thing for
pattern recognition.
So, in summary, as dimensions increase,
these Euclidean distances, that
is these, these, end balls beco, become
less and less meaningful.
You can't interpret Euclidean distances
easily.
Uniform di, distributions become harder to
sample.
and, it, in a fashion it grows, really
explodes as, as the number of, of
dimensions increases.
Many parameters become polynomially harder
to
estimate as the number of dimensions
increases.
But most importantly perhaps and something
that
is often overlooked in the pattern
recognition literature.
It's just a lot more difficult to
interpret your data
and understand it and visualize it in
higher dimensional spaces.
We're restricted to seeing just the tiny
subspace slices.
In two or three dimensions of data
sets that actually have much grander
structure potentially.
So this, these are all challenges as
the dimensions in the number of data
increases.
So are their any real life problems where
you have high dimensional input spaces
like this?
Well actually the rule rather than the
exception.
So here's one great example so face
recognition.
Or any sort of object recognition can
be formulated as pattern recognition where
you're
trying to classify images or image frames
that could have many hundreds of pixels,
right?
So, here we're looking at templates to try
and
decide which one contains a face and which
one doesn't.
The most obvious way to formulate this
would be
as a 20 pixel by 20 pixel input space
right.
That's 400 dimensions in your input space.
So we're well into the range of super high
dimensional spaces,
for which local pattern recognition
strategies won't work as well right.
And, and face recognition, it's obvious
that we, that it works right.
We've got cameras that can do this but in
order to actually get Pattern
Recognition to operate, we're going to
need some
sophisticated pre-processing strategies
to, to reduce the dimensionality.
Another domain where these sorts of higher
dimensional input points are
common is in in the science that's more in
the, the Earth.
And space sciences realm is in
spectroscopy.
Often in spectro, we're describing
individual data points by many
wavelengths.
So here we have reflective spectra.
Which are measurements at many wavelengths
of
light here from 350 to about 950
nanometers.
these, relfectant spectra can easily be
tens or
even hundreds of, of dimensions in, in
size.
Right, and yet we need to find a way
to perform pattern recognition on these
data sets too
in order to distinguish spectra or
classify them and
we're going to need more sophisticated
methods to do that.
All right, so I want to close with a
couple
of by wetting your appetite with a couple
of solutions.
So one solution to the curse of
dimensionality would be to rely only
on those pattern recognition methods that
are intrinsically robust to higher
dimensional space.
That's right, so we've talked in previous
lectures about random force,
for example, which tend to do pretty well
in higher dimensional spaces.
So, you could limit yourself to those
pattern recognition strategies.
now, that's kind of limiting and there
are, there are other ways we can
tackle the problem, and in particular we
can try to represent the data differently.
So we can use hand crafted features.
We can use a sub set of the futures and in
the next
lecture I'm going to talk about feature
sub selections strategies that will let
us reduce the dimensionality by, by
choosing just selecting particular
features that are
more informative than the rest, and,
and performing our pattern recognition on
those.
We can also come up with linear
projections of the, of the input data set.
That will reduce the dimensionality so
that it's
more amenable to our, our local pattern
recognition approaches.
And then in the, the final lectures I'll
describe some nonlinear
projection strategies that will allow us
to reduce dimensionality in non-linear
ways.
All right, so in summary I described some
ways to find nearest neighbors
in data sets, sorted lists for 1D, K-D
Tree for two to eight dimensions.
And above that, you'll want to use
approximate nearest neighbors.
But far above that, most of these
local pattern recognition methods will
fail because of
the curse of dimensionality and so the,
the
coming lectures will provide some
solutions to that.