My name is David Thompson, and this
presentation is Local Methods for Pattern
Recognition.
It's the first of several modules that
will involve, or talk about
dimensionality reduction in the context of
this Caltech Big Data Summer School.
And so, the first of these lectures is
intended to provide just
a common reference some basic skill set
that we'll refer to later.
I'm going to review some basic
pattern recognition strategies, such as
classification regression
that you will have been exposed to
previously, but I think it's, it's
worth talking about them again, because it
really is foundational for some of
the things that we'll describe later
as far as dimensionality reduction is
concerned.
So it's an important background to have.
Okay, so this first talk will, as I
said, review basic pattern recognition
problems, classification, and regression.
And in particular on the context of local
pattern recognition strategies.
These are non-parametric pattern
recognition strategies, as opposed
to say parametric methods that we have
seen earlier.
A lot of these fall into the general
category of nearest neighbor methods.
So I'll describe the nearest-neighbor
methodology, and why that might be a
good thing, and then a couple variants of
that, including local linear regression.
Which is a flexible regression strategy
that
is based on a local non-KerMetric
approach.
And then kernel density estimation, which
is a probabilistic method for pattern
recognition.
Okay, so let's start off with a simple
pattern recognition task.
Here I've got a, a data set with a couple
of
attributes on it, and is pattern
recognition folks I want to do.
I just plotted these giving each its own
coordinates.
So here, this is a two-dimensional
attribute space where
every data point may have associated with
it some
class value or some real valued ordinate
that we're
regressing against, some value that we'd
want to predict.
[INAUDIBLE] were just interesting in
intrinsic properties of the data set how
the data is distributed to try to infer
something about the process that
generated that data, so that is more akin
to say a density estimation
task where we are estimating probability
density in this two dimensional attribute
space.
So there are lots of different kinds of
pattern recognition questions that
we can ask of this data set even this very
simple one here.
So, I've plotted here on this, this slide
a red question mark to indicate
some query point where we'd like to
describe or predict behavior of this
process.
Again, this could be a, a prediction of
the
real valued function at that location in
the input
space, or it could be that we have a
new point there, who's class we're tying
to infer.
Regardless we've got a, a query point and
we want to be
able to infer something about what the
process is doing at that location.
All right, a little bit of notation
background.
So I'm going to treat these data points as
column vectors, so
we're going to say X is, er, X sub I is
our data point.
And it has from one to n attributes.
Again, that's example, a simple example
only has
two, but you can imagine having
arbitrarily many.
And because this is dimensionality
reduction, we're eventually going to be
talking
about data points that have hundreds or
even thousands of attributes.
And we can represent the entire data set
as
a matrix where we stack these column
vectors together
in rows so we have an N by d matrix, where
D is the number of data points.
For now without much loss of generality,
I'm just going
to assume that all of these attributes are
real valued.
Continuous attributes so, I'm not going to
deal much with, for example, categorical
attributes,
but many of the same principles that
I'll discuss apply to categorical
attributes as well.
And you may be familiar with encoding
strategies that
you can use to turn categorical attributes
into continuous.
So really we'll just focus on the, the the
continuous case here.
Okay, so, or one reasonable way to do
pattern recognition on this data set is to
just
look at the local behavior in the vicinity
of the query point that we're interested
in inferring.
So here we can, this goes under the
assumption that whatever
process generated the data is locally
smooth in the input space.
So maybe we can disregard a bunch of the
points that are really far away from our
query, right.
We don't have to look at the function
values.
it, it, at the extreme lower left side of
a plot.
We can just look at the, the values on
the upper right near the, the red question
mark.
Right?
So, maybe to look at its, its closest
neighbors
to see what the function is doing in that
vicinity.
And you can do this for each
of the pattern recognition strategies that
I mentioned.
All right.
So the canonical example is, of course,
nearest neighbor classification.
To infer the class of the query, just look
to its nearest neighbor in our
data set, and assume that it has the same
class as that one neighbor point.
So, in this case I've indicated, with a
red arrow, the nearest neighbor of the
query and so we just assume that that is
the class of our, of our query.
Now this amounts to a [UNKNOWN]
partitioning of
the input space so here in two dimensions
I've drawn, I've partitioned the space
drawing areas
for which every input point is responsible
right?
So you can see that the nearest neighbor
points
are actually responsible for a polygon,
within this input space.
And any query within that polygon is going
to get its class now this has kind of
nice property, because the data that is
where
we have denser data right in the center.
it, where we, it, have more information
that the Voronio partitions are smaller,
right?
And we permit the function to vary a
little bit more.
Far from the data cloud these, these
partitions get a lot larger and, again,
we,
we don't have as much to say about that
corner of, of the input space.
So our inference there is going to be
smoother.
Right, so this is a basic example of
nearest
neighbor classification, and the decision
boundary looks like this.
This is he resulting decision boundary.
I've applied here some, some labels to the
data set, red and, and blue.
And you can see that the decision boundary
here drawn in black is sort
of a wiggly shape through this input space
that bends around all of these inputs.
Now the, the query's actually been paired
with a blue point.
This is kind of interesting, though
because
if you look carefully you'll note that
the query is actually also fairly close to
a bunch of red points as well.
Right?
To it's immediate left there are clusters
of red points and it's almost as close
to those, but it's just sort of
happenstance
that it got paired with a blue point.
So another way of saying this is that the
one nearest neighbor approach to
classification is rather sensitive noise.
It has high variance, in the language of
pattern recognition.
Variance-bias tradeoff, is definitely well
it's definitely
more variance than bias in this case.
So this also manifests as a fairly wiggly
decision boundary.
So if you see in the center of the cloud
there, maybe our decision boundary wiggles
a little bit more than is appropriate
given,
given the, the amount of data that we
have.
So what this really needs is some way to
smooth that decision
boundary or regularize it so we're less
sensitive to those single point outliers.
And the way that's typically done is by
introducing more nearest neighbors.
So here I'm looking at the five nearest
neighbors and taking
a majority vote of which which class to
call the query.
And you can see the decision boundary
straighten out quite a bit as a result.
This has the effect of regularizing
or smoothing our classification, and we're
now
paired correctly with the, the red points
as opposed to that single blue outlier.
Alright, so this is just one example
of regularization in the context of
pattern recognition.
So, I alluded to other kinds of pattern
recognition tasks
that one might want to perform using this
sort of local estimation.
And another one is regression, right?
So, a really simple regression strategy
that sort of.
The regression analog to K's nearest
neighbor is kernel smoothing.
And that is to, if I have some real value
function that I want to estimate, I can
just perform a weighted average of the
local, of
that function where the weights are
weighted by local neighbors.
Right, so locality to the, the query
point.
Which amounts to convolving a kernel
function over the training data.
So here the kernel function, which I've
represented
as K can be any decreasing function of
distance.
So it's quite common to use a Gaussian
bump for that.
There you see on the lower right the, the
formula for a Gaussian kernel function.
Which is a perfectly good kernel, and it's
actually what I'd recommend you start
off with as sort of a first cut for all
your your kernel smoothing problems.
It's got a free parameter which is the
width which is here represented as H.
So if the width is wide it's sort of akin
to many nearest neighbor classification.
We're taking into account a large
neighborhood around our query point right.
And most of the the nearest neighbors in
that
point vicinity will get more or less equal
weighting.
Right, so that's a lot of smoothing.
If our width is very narrow, or then what
that means is that we're, just look, it's
a
very skinny Gaussian bump function, and
we're only looking
at the points very, very close to the
query points.
So it's akin to a one nearest neighbor
where
our variance is a little bit higher, which
might be
more appropriate if we have more data for
instance
or over a dense region of the, the input
space.
Note also that we're normalizing by all of
the kernel outputs over all of the data
points.
So we, we do this calculation over all the
training
data for any query whose value we want to
estimate.
So here's an example for just a 1D
classification
problem of what kernel smoothing looks
like in practice.
So we've got a process, which is green
here.
It's Y of X.
Which is a, just a simple periodic
function in this case.
And it generates a bunch of data points
that are here noted in blue.
And we're trying to infer what this, what
this function looks like.
And I've applied a, a kernel smoothing
algorithm to the data.
So you, we can see that for X sub naught.
There, where we've inferred a value, Y of
X
sub naught, or Y hat because it's an
estimate.
And you can see we're looking at, at
points in the, the
vicinity of X sub naught to determine what
that, what that real function
value would be; and that those points,
which are red in this diagram,
are weighted by a kernel function, which
is centered on X sub naught.
So points near X sub naught are going to
get high weighting.
In our local average and points far from,
from X sub naught are going to
get low weighting and that's what the,
what the yellow Gaussian function there
represents.
So you can see that this is without very
many assumptions at all, just using the
intrinsic properties
of the data, this method's already done a
pretty
good job of modeling the, the periodic
sine function.
Right, so this is quite a powerful method
for regression, simply
because it makes so few assumptions about
the intrinsic structure of
the data, the parametric form of the data
and can be
used, just out of the box on a wide range
of problems.
But it's not perfect.
And in particular you'll note challenges
at the
edges, right, where there's a little bit
of bias.
The function sags a little bit at the
edges instead of.
Modeling the data precisely there and
that's because we're
being unduly weighted by that data points
on one
side of that, that function of the very
extreme
side X values, on the extreme left and
extreme right.
So we aren't doing as good a job of
modeling our underlying function there.
And there are ways to address this one, a
common way to do that is
by adding a little bit of, of parametric
inference into this by, by building in.
Into our local, instead of using a
local average, actually using a local,
linear regression,
that takes into account the linear
structure
of the data set at those edge points.
And this is what local linear regression
looks like.
It's actually very similar to kernel
smoothing in a lot of ways.
But it builds off of standards lee's
square linear regression.
So you may be familiar with the hatmey
tricks and standard linear lee's squares.
Here's an example of a, a liner lee's
estimate of x sub not.
Where we've defined the data matrix B and
our predictor is Y.
Right.
So this projects the the data onto the
column space
of the design matrix B is the basic
premise here.
Now, if we add kernel weights to this,
right, so that we weight our nearest
neighbors more highly in this regression,
we
get an expression that looks something
like this.
So we've added matrices W of X sub note /
g which represents the kernel evaluation.
Of all of the data points to the location
X sub not.
Right?
So that's a diagonal matrix with all the
colonel weights on the diagonal.
So just by making this simple change,
we've actually created a local linear
regression
problem that will let us predict the value
of this function at X sub not.
And this is what it looks like.
And you can see it does a very good job of
modeling our, our sine function.
And in particular it's removed the bias at
the extremes the extreme left
and extreme right, so we're actually
modelling
the local linear structure there quite
accurately.
But otherwise it's very similar to, to
kernal smoothing.
Okay, there's one more local method for
pattern recognition that I'd like to talk
about.
And this is kernel density estimation.
So this is the, this is meant to address
the density estimation problem.
So if we want to estimate a probability
density
or a conditional probability density in
this input space.
One way to do that is simply assume that
each input point is responsible
for a local kernel, right, a local
probability density function in its
immediate neighborhood.
So we can take the density to be the sum
of all, or the density of
any new point to be the sum of
all the kernel evaluations of all our
training data.
So this, this image here right show an
example of that.
We got just one real valued input here on
the X-axis and we convulsed our kernel
across that and summed up the response of
the kernel over all those data points.
To provide some estimates of the density.
Here are the true density is given by the
grey curve and the estimated densities are
given bu the
various color curves as we change our
current bandwidth, you
can see that the density estimate becomes
smoother or more
wiggly right which is [UNKNOWN] to the
regularization that we
saw before both with the increase in the
number of
[INAUDIBLE] we can do exactly the same
thing here note
that the blue might even be a bit over
smooth.
Looks right, so we're doing a pretty good
job of modeling the underlying
galaxy influction, but we've started to
truncate its peak a little bit, right?
So maybe a width of point three is a
little bit too much.
One thing to note about this expression,
note that it's normalized to provide
a true probability density estimate, so
it's
a valid PDF so that the normalization.
Factor Z, zed normalizes our kernel
function so
that all the kernel evaluations have a
volume
one or area one and we're also dividing by
the total number of data points that
enter into this kernel density estimate
that's the
n score so our density you were to
evaluate the density everywhere in this
space and
integrate that we get an area of one.
Okay.
So, how would you go about setting all of
these these regularization terms?
Well, typically you'd simply use cross
validation.
You could use you can leave one point out
and look at your performance estimating at
that point
for either regression or classification
and you use that
to adjust the kernel bandwidths so the
number [UNKNOWN].
That's probably the most common way.
I guess the anag the the analogous method
for density estimation would
be look at the, the, likelihood of held
out data points, right?
So, the, the cross validation is the, the
typical way that one would estimate these,
these parameters.
But, fortunately there's really only one
parameter
to estimate which is the, in this case.
The kernel width.
So we get a wide range of very
flexible functions out of very few input
parameters.
We're letting the data speak for itself
unlike a parametric method.
And this is the, the real power of these
local methods for pattern recognition.
Okay.
So, in summary I've described some
local nonparametric methods for pattern
recognition.
This is in contrary to parametric methods
that imply some
global functional form for the process
that generates the data here.
We're just looking at local patches of
data to infer the
values of the underlying function or
process at some query point.
And there are 3 different examples of
this local pattern recognition that I
demonstrated.
K-nearest neighbor for classification.
Kernel smoothing and local linear
regression for regression problems
and then kernel density estimation for
probability density estimation tasks.
In order, the main parameter is
regularization and
you can set this using a cross validation
strategy.