I'm David Thompson and this is the next
lecture in the series
from the, the JPL Caltech virtual summer
school on big data analytics.
We talked previously about different
strategies for
dimensionality reduction, including, basic
feature selection approaches.
Linear methods, like principle component
analysis.
And also, metric learning approaches,
which generalize linear dimensionality
reduction to the case where class
information is available.
Now we're going to depart from the realm
of, of linear projections all together.
And move into a topic known as Nonlinear
Dimensionality Reduction.
And in particular, we'll be describing
kernel principle component analysis.
Which is a kernelized version of PCA.
All right, the objectives of this talk are
to first, just to be able to
distinguish linear from nonlinear
dimensionality reduction, and
to know and understand the differences
between them.
Kernel PCA is just one of
many different nonlinear dimensionality
reduction strategies.
I think it's a particularly useful and
widespread
ones, so we're going to talk about that
and
focus on that in this talk, and you
should be comfortable with it and it's
derivation.
And also, know, have some familiarity with
the other methods that are out
there and available to you if you prefer
to use those for other applications.
More generally, there are advantages and
pitfalls to nonlinear, as opposed to
linear approaches, and we should
understand
them, try and understand those too.
All right, so why do we care about
nonlinear projections?
Well, there are some cases where linear
subspaces just aren't good enough.
I mentioned before that linear subspaces
are
almost always useful on any dataset, but
they
may not adequately represent the
underlying manifold,
which may have some other nonlinear
structure, right?
So, even if I start and am able to project
my data linearly down to, say,
20 or 40 dimensions, that still, I still
might be able to find a more efficient
representation.
That captures the, the models the data
even better using a lower dimensional
manifold.
And that's the idea behind nonlinear
dimensionality reduction.
So here's an example, here, portrayed in
these four image panes.
We have in the upper right, or I'm sorry,
the upper left, on this S
curve which is a curved manifold that's a
two-dimensional surface that's embedded in
a three-dimensional space.
Now if, if you're to do a linear
dimensionality reduction on this data set,
that would amount
to maybe slicing taking hyper-planes
somewhere through that, that
data and projecting all the points onto
that hyper-plane.
Now, it, try as you might, you're not
going to be able to find a
single hyper-plane that would let you
recover
the original points of that, of those
data.
No matter how you orient that hyper-plane,
you're
always going to lose quite a bit of
information.
And this is reflected by the, the PCA
projection result that
you see there in the, in the upper right,
where it tends
to mix a lot of unlike colors together
even though the, the
different colors are supposed to be on
different sides of the manifold.
So the PCA projection down to 2D is really
inadequate.
Even though the, the structure is
intrinsically two
dimensional, we can't capture that with
the linear projection.
The other two panels in the bottom show
different nonlinear dimensionality
reduction methods, and they, actually,
are capable of modeling and unfolding,
this manifold
to, in order to, represent the data
adequately.
And that's not what nonlinear dimensional
introduction strategies are all about.
So, some other examples of that.
Here is a case using image data.
We have just two axis of variation here.
We're looking at a face from different
angles.
So the left right pose is one axis of
variation.
And the up down pause is another.
Note that any two of these data points
that are close to each
other in this manifold are also going to
be similar to each other.
So the, this, it captures sort of a local
structure around all data points and
also captures the global structure that
they're, these two main axis of variation.
But it's a highly nonlinear relationship,
naturally.
And if you are to try and embed this in
the space of pixel attributes,
you'd get some highly folded structure
probably,
even though the manifold itself is
continuous, right?
because you could continuously move this
camera around and
get practically no change from between
neighboring data points.
So the local structure is smooth and
continuous.
But of course its a very complicated
manifold and this is from early work in
Isomap in order to identify structures
using nonlineal dimensionality reduction.
Here's another result from the same paper
this is looking at
handwritten digit recognition, so here we
have lots of examples of twos.
And you, you can imagine that these twos
live on a manifold
of, of different different manifestations
of
what a handwritten two should look like.
Right, so if you change any one of these
just a little bit, you move along the
manifold to its neighbors, right, you're
still on the
manifold as long as it's still a valid
two.
And this just emphasizes the fact that
these manifolds needn't fill the space.
They aren't always rectangular sheets.
You can have spikes and, and pseudopods
that jut out like you see
down there in the lower right, there's
sort of a spike in this distribution.
Representing this, the twos of the curly
cues on the top.
but, that said we can still sort of
arbitrarily, apply ascribe different
English titles to these axis.
Here they've been called bottom loop
articulation, and the top arch
articulation axis.
But really all we're trying to do is come
up with
some nonlinear structure to describe the
universe of possible twos, right?
Which is a highly non linear manifold in
the original space.
How do we represent this structure?
Well, this, one way we can do this, there
are lots of different
ways, a, a lot of different nonlinear
dimensionality reduction methods involve,
looking at graphs,
for instance, to find, local neighborhoods
on graphs, but, kernel principal component
analysis,
which is the one we're going to be
exploring most deeply in this talk.
Relies on the intuition, that many, data
sets which are not linearly separable in
their
original attributes, can be made linearly
separable
by projecting them into a higher
dimensional space.
That is, we can add attributes, which are
simple arithmetic operations of the
original attribute space.
Which caused the data to become linearly
separable in that it, new feature space.
So here's an example where we have two,
data points.
This bullseye, data cloud has two classes.
The red and the green, which are not
linearly separable.
Try as you might, you cannot draw a
separating discriminate line,
through that, or separating decision
boundary, through that data point cloud.
However when you add a third feature to
the dataset which is the sum of
squared attributes, then, the results
become linearly separable
as you see here in the three-dimensional
portrayals.
So, we're mapping this into a high
dimensional space where linear
relationships are sufficient.
If you were to map that decision boundary
that you make in this hard
dimensional space back into the lower
dimensional
space, you get a nonlinear decision
boundary.
So, we can actually use all the tools from
our linear analysis toolkit
in the high dimensional space and get non
linear results in the original space.
This is an, an important an important
insight, an important intuition,
it is really the foundation of our Kernel
principle component analysis.
So, what does this look like for KPCA.
Kernal PCA takes our training data, it
maps it into some
higher dimensional features based where
we perform principal component analysis,
right?
Which in the original data space, it
would represented as a nonlinear
projection, right?
A nonlinear transformation of the data.
If we get some new data point then we can
similarly
project it into our higher dimensional
feature space and find its
low D representation in that new high
dimensional feature space that's,
that's, with projections that have been
learned from our training data right?
So this is the intuition behind KPCA.
But you might say this is fine but it's
kind of contrary to the whole point of
dimensionality reduction right?
If we're creating these arbitrary new high
dimensional feature
spaces doesn't that actually increase
rather than reduce the dimensions.
It's true it would except we also have the
benefit that for
KPCA you don't actually have to do any
calculations in the high
dimensional feature space and I will
describe that in a moment.
The derivation of Kernel PCA follows our PCA.
So we now take some mapping of the
original data set which is Phi.
So Phi of X sub i is the, the mapped data
point in this high dimensional space.
And we envision some projection in this
high dimensional space.
That's here represented by the set of
orthonormal base inspectors in the matrix
U, right?
And the expression here U times U
transposed, it times Phi of, of
X sub i, gives us the reconstruction of
the data point, Phi of
XLi after, down projecting it through this
linear basis, right?
So we subtract the original data points,
in the high dimensional feature space from
its reconstruction in that high
dimensional feature
space and we get an error score, right?
So we're trying to minimize reconstruction
error in this high dimensional space.
Note that for this expression, it's
actually
important that the data set Phi be
centered.
Similarly to regular PCA, where we're
working with zero mean data.
We had to subtract the mean off first.
Here as well we're going to be working
with
data that is centered in the high
dimensional space.
All right, so, this is equivalent.
I mentioned the, previously the
relationship between singular value
decomposition and PCA, so the same thing
applies here.
We can actually do a singular value
decomposition, of the, high dimensional
features, or, the
high dimensional dataset, Phi sub X, and
that gives us our basis vector as U.
So, we define U to be the left singular
vectors of Phi sub
X, associated with the highest singular
values in this matrix of singular values,
sigma.
All right, so equivalently, right just as
in our previous PCA example where there is
an equivalence between SVD and calculating
the eigenvectors
of the covariance matrix, the sample
covariance matrix.
We can calculate the eigenvectors of the
sample covariance matrix of
Phi sub X, which is a bunch of dot
products essentially.
And again this has to be the, the
eigenvectors
of the, the centered matrix as in, in PCA.
Okay this, this brings me to the kernel
trick.
So as before we can work with this, as
before P, PCA
relies on the eigenvectors of the sample
covariance matrix X times X transpose.
And we can represent that in the projected
space by a matrix of dot products, right?
And the expression for that is given here.
So what this means is we can implicitly
model any nonlinear transformation, Phi
of, of X.
The only requirement is that have to be
able
to calculate dot products between those
data points efficiently.
We can, as long as we know the dot
products, we can figure out what the
projected representation is.
So we actually never have to calculate the
explicit
represent, high dimensional representation
of the new feature space.
So that, typically the way this is done
in kernel methods, this is known as the
kernel
trick, is to come up with a kernel matrix
of dot products between all the different
data points,
and, so we describe here the dot product
using the kernel function K, which
represents point similarity,
in this high dimensional space or
similarity in the
attribute space, which equates to their
dot product, right?
So this is different, this is slightly
different than PCA.
Where as PCA has a covariance matrix
that's
scaled with the number of input dimensions
n.
Here we're working in KPCA with this
kernel matrix
that, is, has, dimensions similar, it's
dimension according to the
size of our dataset, right, because we're
calculating the
dot product of all data points against all
the others.
So this scales with D, the number of data
points in our training set.
What kernel function should we use?
How do we calculate these dot products?
Well a common method is just to look at a
local, some
sort of decreasing function of distance in
the original feature space, right?
A typical choice a typical choice is the
Gaussian kernel.
We introduced this way back in the first
lecture,
right, as, as a way to describe locality
between
data points that has a width parameter h
that
we can set using cross validation, if we
like.
And this falls off rapidly, as distance
increases.
So we can apply this to every, to
para-wise to all of the different data
points
and figure out what their, it what their
dot products are, in this high dimensional
space.
So we're describing a functional form to
their
dot products which let's us calculate this
nonlinear projection.
Okay so, there's a catch.
I mentioned before that our data set has
to be centered in this high-dimensional
feature representation.
That it has to be zero mean.
And this won't be the case for a general
kernel matrix that we derive.
What this really means is that we want to
come up
with some feature, I'm sorry, some data
point, some projected data point.
We'll call this Phi tilde of X sub i.
Which is the original Phi of X sub i minus
the mean of all of the fees.
And you can actually push this through
some algebra, to figure out
what its implementation, implications will
be for the kernel matrix as a whole.
So, with the kernel matrix elements
defined as the dot products.
So our Phi, of X sub i and X
sub j, we then perform that substitution
from the top
line and it actually works out to some
simple arithmetic
operations on the kernel matrix that
perform this centering operation.
So sparing, I, I won't walk you through
the gory details
but it basically amounts to this, this
operation that we have to
perform on the kernel matrix after
calculating the kernel function of all
data points in order to center it before
we can do STD.
All
right, so here's the from beginning to
end,
the, the recipe for Kernel Principle
Component Analysis.
First thing to do is pick a kernel
function.
I hardly recommend that we start with the
Gaussian.
There are lots of other kernel functions
and a
whole literature devoted to defining
different kernel functions for different
kinds of input spaces so I encourage you
to look
into that if, if it's a topic that
interests you.
After you have a kernel function, you can
calculate the kernel matrix.
And then center it according to that
expression that I showed you before.
Here I have written down the matrix
notation with, the ones indicating just a
matrix with entries of one over d where d
is the number of data points.
All right, so that's it, it fairly
straight forward.
Center an operation and then you solve the
eigenproblem, which is again this
eigensystem based on the kernel matrix,
which
gives us our projections alpha, and then
alpha is of course the size of all of our
data points in the
training set so in order to find the
projection of a new data point.
We multiply the alpha by its kernel
evaluation for all of
the data points in the training data with
respect to the
query point that we're trying to project
and that gives us
the location along some new dimension for
the projected data point.
Okay, so here's an example of what it
looks like in practice.
So we've taken the face dataset and
down-projected it with PCA first.
So this is a purely linear projection of
that, that face dataset before.
This is courtesy of go, Ghodsi, in 2006.
You'll note that there are lots of places
where, neighboring faces have
actually, neighboring points in this
dataset
have actually very different images right.
So this doesn't necessarily do a good job
of, of capturing the underlying structure.
We can do better with KPCA.
Now, this isn't a perfect unfolding of the
manifold, right?
It doesn't totally fill the space with a
beautiful rectangle, right?
But that's not, that rarely happens in
practice actually.
And this is actually pretty, a pretty good
result in that neighboring data points
also represent similar images, as you can
see from the examples that are plotted.
So this actually does a much better job.
For this, day, face dataset than, than a
purely linearly
projection would, as long as we're working
with just two dimensions.
So Kernel PCA, nonlinear dimensionality
reduction is a more
efficient method in this case of
representing the data.
Other methods for nonlinear dimensionality
reduction, and indeed there are a bunch.
Kernel PCA is a common one.
But there are lots of others based on
graph structure like I mentioned.
Laplacian Eigenmaps are an example of
that.
It's a sot of Local Liner Embedding is
another case.
Isomap is a, a famous algorithm that has
been around for a decade now.
Multidimensional Scaling is a classic
algorithm
that takes a, a matrix of affinities
which in some way similar to the kernel
matrix that I described before.
And creates a, a low dimensional
projection that
preserves those, those offendee values,
those distance values.
Feedforward Autoencoders are kind of an
exotic approach that's actually gained
a lot of attraction of late in the deep
learning community.
So, this is based on neural network
modeling.
And, again, that's something that I
encourage you to
investigate further if, If neural networks
are of interest.
Feedforward Autoencoders can be used to
perform Nonlinear Dimensionality Reduction
irrespective of the ultimate
classification
goal of the, the neural network.
All right, and of course there are, there
are many more strategies and a huge
literature
on nonlinear dimensionality reduction, but
I hope I've
given you a pretty good taste with this
lecture.
Okay, so one, note in closing, nonlinear
dimensionality
reduction doesn't always work better than
the linear case.
And it does work well when you have a lot
of data, when you
can fill the manifold and, you don't have
a lot of gaps or, or outliers.
It works pretty well and the intrinsic
dimensionality is relatively
low and your data is pretty evenly
distributed on the manifold.
If you don't have a lot of data then
some simpler structure is generally
going to give you better results.
Occasionally nonlinear dimensionality
reduction strategies can
give you degenerate solutions or they
can be unstable, and, and this is just
goes with the territory.
When you have a more flexible model right,
you
need more data in order to fit it
adequately.
So this is just a general caveat to keep
in mind.
I would always start with linear
dimensionality reduction strategies to
see if they're sufficient for your
classification or visualization task.
And only pull out nonlinear dimensionality
reduction
when it turns out to be absolutely
necessary.
It's particularly helpful in a lot of
cases like image data, where you have
smooth transitions, right, from one frame
to the next, or in pose estimation, where
you have like say an articulated body
that's moving and can define relatively
simple
low dimensional manifolds in that space
consisting
of different poses and joint limb
articulations.
So there are some sort of cottage
industries
where these nonlinear representations
which will become really
useful, but if you have some brand new
data set then start with the linear, okay.
So in summary methods like KPCA can find
non linear by projecting data into high
dimensional spaces.
And then applying the same linear tool kit
from PCA, in those in, those implicit
spaces.
And you can avoid the cost of this
calculation with the kernel trick.
That is computations based on dot products
which are
represented by a kernel function that you
can define.