I'm David Thompson and this is the
next lecture in the series on
Dimensionality Reduction.
It's part of the JPL-Caltech Virtual
Summer School in Big Data Analytics.
This is a fun lecture.
This is where we actually start to get
into real dimensionality reduction proper.
So we've kind of danced around it a bit in
previous lectures, I've described
the cursive dimensionality, why high
dimensional data
sets can be problematic for pattern
recognition.
Then I described some feature selection
strategies, where you
can reduce dimensionality by selecting
subsets of those attributes.
Here we're going to get into the preview
of what, what most folks think of, when,
when they think of dimensionality
reduction, which is
actually coming up with interesting
projections of the
data that utilize all of the attributes
but
represent the data in some lower
dimensional space
that we can more easily visualize and its
easier for our pattern recognition
algorithms to use.
So we're going to be discussing linear
methods here.
All right.
The objectives of this talk you should
become
familiar with dimensionality reduction and
its relationship with
feature selection and understand Linear
Dimensionality Reduction your
principal analysis and it's relation to
singular value decomposition.
And then finally we'll be talking about
eigenface's too.
[BLANK_AUDIO]
All right.
So, di, dimensionality reduction relies on
the intuition.
That even though this high dimensional
spaces are very difficult to deal with.
It's almost never the case that our
data actually fills the high dimensional
space completely.
Real processes aren't like that.
It's very rare that you find a process
that, that
actually has a thousand of intrinsic
parameters along which it varies.
Right.
More commonly the process that generates
our data is some
lower dimensional structure, that's
embedded in this high dimensional space.
Right.
So, this is commonly represented as some
sort of a manifold
or a subspace that lives in our high
dimensional attribute space.
The point of dimensionality reduction is
to
revile or uncover, that manifold or that
subspace.
Here, we see an example.
So you may recall from earlier lectures
where I talked about image analysis
as one area where we have to deal commonly
with high dimensional data.
Right?
If you have say, a thumbnail image that's
20 pixels on a side.
That's 20 times 20, 400 different
attributes of potential variation.
Right?
It's a very high dimensional space.
But, in practice, many of these data
sets have a much smaller intrinsic
dimensionality.
That is they lie in a low dimensional
manifold of that 400 dimensional space.
Here's an example from a famous
dimensionality reduction paper showing
images of hands.
So we've got probably couple hundred data
points here.
These are the blue points that I've
plotted in just two dimensions.
And we've come up, we've projected these
data points down onto this two-dimensional
plane in such a way that neighboring
points are similar to each other.
And distant points are dissimilar.
And you can see that there are actually
only
two dimensions of intrinsic variation in
these hand images.
Right.
If you know the coordinates in the space,
right?
In this 2D space, you can specify exactly
what the hand image is going to look like.
The two dimensions that we've labeled are
the
wrist, wrist rotation and the extension of
the fingers.
Right?
And with those two parameters, you can
adequately describe any one of these
images.
So this is a case where there's some lower
dimensional manifold we've uncovered.
Here its non linear manifold, right?
We'll get to this in later talks.
But you can imagine that there are linear
subspaces that
would describe this, this data set more
efficiently as well.
And it's almost always the case, that you
can come up with some lower dimensional
projection that preserves all of the data
in your data set, while reducing redundant
dimensions.
So, let's start off with some formal
definitions before we go any further.
Again, we will be looking at data points
which are column vectors.
So here a column vector x has n
attributes,
so we're listing these attributes from one
to n.
As a column, and you can stack them
together in a matrix, row-wise.
So, we have an n by d matrix, where d is
the total number
of data points in our, in the data set
that we're trying to project.
And what we're aiming to do with
dimensionality reduction, is project these
onto new
data points, which I'll here represent as
y, that have some lower dimensional
representation.
So here we just have m attributes, where m
is considerably less than n.
Right?
So we want to, this is some lower
dimensional subspace.
And dimensionality reduction is just this
mapping.
[BLANK_AUDIO]
Okay.
So linear, for Linear Dimensionality
Reduction,
which is probably the most common form
of this algorithm, we'll define the
mapping from x to y to be linear.
That is, you can think of it as just pre
multiplication.
A new basis for representing the data that
has a smaller dimensionality than our
original basis, right?
So we can represent that as an m by n
projection matrix and if we pre
multiply it with the x matrix, then this
gives us the desired projected data matrix
y.
So we're finding a subspace that best
represents the data.
And the most common approach to doing
this, to
finding this subspace, is called Principal
Component Analysis, or PCA.
Now PCA is quite common, so you may have
come across it in your own disciplines.
Right?
It goes by a variety of different names.
In the earth sciences, it could be the
empirical error function, or the empirical
orthogonal function.
in, a lot of times in remote sensing,
it's known as the minimum noise fraction
transform.
There are other, it may have other names
in other disciplines.
So it's highly likely that you've
encountered this before.
But it's, it's good to review, because
it's just so darn useful.
And even for a data set that isn't truly
on a linear manifold often, sort of a
coarse
PCA reduction of the initial dimensions on
some smaller,
linear subspace of the data will still
yield benefits.
Even if the, you then go on to
subsequently apply some other
sort of analysis, some other nonlinear
mapping or pattern recognition after that.
Principal Component Analysis is almost
always a good thing to do.
It's a, it's a really fundamental tool in
the toolbox.
The goal of Principal Component Analysis
or how does it, how it identifies this
basis, is to find the orthogonal
directions
that maximize the variance of the data
set.
So here's an example of a, a data set in
two
dimensions, and you could imagine
projecting
this onto a one dimensional subspace.
Right?
So we want to project this onto a line, we
want to draw a line somewhere in this data
cloud.
That allows us to optimally reconstruct
the dataset
or maximize, equivalently maximize the
variance along that projection.
So, how would we do it?
Which, which line would you choose?
If you were to, to analyze this data site
and you had to come up
with a single linear direction on to which
all of your data would be projected.
Well obviously, you want to follow the,
the
direction of, of variation that is this
main access.
So, the, and the first principle component
is
indeed, aligned with the main access of
variation.
So, if you project all of your data points
onto that, that red line
or that red direction then that will
maximize the variance of the resulting
projection.
And equivalently, if you wanted to
reconstruct
a data point from its position along that
line, you'd get pretty close to the
original point if using that direction of
variation.
So, one thing to notice about this data
set that I'll get
back to in a couple slides is that it's
centered at zero.
So this is an important feature of the
Principal Component
Analysis is that the data cloud really has
to be centered.
Now it's easy to center any data cloud,
right?
Before applying PCA, simply subtract of
the mean.
Right?
But that's an important step.
And one that will be important as we start
looking at nonlinear analogs of PCA.
Okay.
So there's our first principal component
it's pretty obvious.
Our second principal component of our data
set
would have to be orthogonal to that one,
right?
Because again, PCA dimensions are, its an
orthogonal basis its an orthanormal basis.
So the second principal component would
come out perpendicular to the first.
So note also that these vectors have heavy
unit length, our goal here
is to provide a true basis that is a
rotation of the data.
In which every thing is, is
orthornormalized and sort of independent.
Okay.
So this will require a new a new
construction.
Which is that the covariance matrix, that
I want
to introduce here, if you're not familiar
with it already.
So, covariance matrix it's simply the
matrix of all the
covariances between all of the different
attributes in your data.
So this is the, the formal definition.
Where you have, the, the covariance
matrix,
that we're representing here as sigma sub
X.
The sigma sub X for attributes i and j is
the expectation of, the, attribute X.
Minus its mean times the attribute j minus
its mean.
I'm sorry.
The attribute y minus its mean times the
attribute j
minus its mean and you can put all these
together
element wise into an m by m matrix, where
m
is the total number of attributes in your
data set.
You can estimate that using what we call
the, the sample covariance matrix.
Which is represented by this expression
here and
that the center of the slide take the,
the,
essentially the, the data sites cross
product and divide
by the total number of data points minus
1.
Okay.
So, the properties of this, this
covariance matrix.
Well the diagonal terms have the variance
of the different attributes of x.
And the off-diagonal terms, like I said,
represent the covariances of x.
The matrix, the matrix itself has some
unique and important properties.
In particular, well, it's square,
obviously, and it's symmetric.
But it's also a special class of matrixes
known as positive semi-definite.
And, every positive semi-definite matrix
is
a valid covariance matrix and, and
vice-versa.
And it will be important to maintain this
property of positive semi-definiteness,
in, in the future.
Particularly, as we look at the nonlinear
analogs.
Okay.
So how would this, this work in practice?
How do we, we maximize the variance of a
projection?
How do we identify the appropriate
projection to use?
Well here on the, the left side you can
see.
it, we can rewrite the, the variance of
our projection as the, the expectation of
the projection.
Here I've noted the projection itself.
The projection vector as a vector v which
I'm multiplying.
I'm basically taken the dot product of
that with x.
And that gives me the projected location.
So the projected location data point minus
its expectation that quantity squared or
the expectation of that quantity squared
is
the, the formal definition of the
variance.
And you can through some algebra expand
this and get the expression in the center
which is the expression v times the
covariance matrix times v.
And then it's basically, it's known for
zero-mean covariance matrix, the unit
vector that minimizes this quantity is the
top eigenvector of the covariance matrix.
So you it's simply the solution to the
Eigen
system that starts with the sample
covariance matrix and
then gives you the eigenvectors of that
sample covariance
matrix, which is the expression in the
lower right.
So it's basically, a straight forward
Eigen system.
And there exist lots of numerical packages
that will solve this sufficiently mat
lab has a bunch of them that the eye'ds
function is particularly useful here.
And another useful property of this whole
procedure is that you only need
to calculate as many eigenvectors and
eigenvalues as you want to have
components.
Right?
So if you are projecting the data onto the
top six principal components,
then you only need to calculate the top
six eigenvectors and that that's enough.
So there are efficient, iterative
strategies for doing this
and it makes it a pretty straight forward
calculation.
So in summary, what's the PCA recipe?
You convert the data to have zero mean.
That is, you subtract off the mean from
the dataset.
And then you form the sample covariance
matrix or you, I'm sorry.
You form your projection matrix, which in
this case is
A, using the top n eigenvectors of the
sample covariance matrix.
Or equivalently, and I'll, get into this
in greater length later, you, there's a
similar formulation that uses the sim, the
singular value decomposition of the matrix
x.
Okay.
So this gives you a matrix A, which is
your orthonormal basis.
And then in order to project the data to a
lower
dimensional space, you subtract off the
mean of a new data point.
And then apply, pre-multiply that, that
orthonormal basis
x which gives you the projected data point
y.
To reconstruct the original data point
from it's projection, you multiply by
the, the transpose of your projection
matrix, and add back the mean.
And that gives you a reconstruction which
I've here noted X hat.
All right.
So it's, it's a fairly straightforward
procedure.
And it's useful for a wide range of
different pattern recognition problems.
I'm going to talk now about one canonical
example
of Principal Components Analysis, which is
called eigenfaces.
And they've been doing this for, for many
decades.
Here's an example from Moghaddam et al.
Where they apply this to a, a fairly
well-known dataset called a FERET frontal
view image database.
here, we're projecting these data points,
where each data points is a face
onto the, the set of basis factors
which best represent variance among
different faces.
So, you can use this for face recognition,
for detection of faces and new images.
Eigenfaces are sort of universally useful
for,
for all sorts of, of face recognition
problems.
Here is here are the first top eight
principal components of the face data set.
And these are, it's interesting that
these have their own distinctive
interpretations.
So starting with the first principal
component there in the upper
left, you can see that there's a lot that,
that bright patch
on the forehead suggests that maybe this
principal component is concerned
mostly with say, features of the hairline
or illumination on the forehead.
Perhaps the second principal component
right next to it moving right.
It looks like there's some shading there,
so perhaps the second axis of
a variation has to do with
say, illumination differences from left to
right.
You can see in the third principal
component that there's
definitely something to do with the
hairline there and the forehead.
And so on and so forth.
You can see different features pop out in
the
principal components, such as structure
and the face and cheeks.
The position of the eyes and eye sockets.
There's even a, an obvious expression
change in the principal components, and
all
of these are sort of distinct axes along
which the data can vary.
So that the principal components
interestingly enough, are themselves
interpretable as as direction of variances
in the data set.
All right.
So they can be informed of in their own
right.
You can also interpret the eigenvalues.
So the eigenvalues associated with that
eigen system that I showed you before.
In tell you a bit about how many principal
components you need to use.
And in particular, here's the, the chart
of all n eigenvalues.
There's a dramatic fall off initially
after the
first, well, few eigen values of, of the
system.
Right?
And what that means is that
the, the intrinsic dimensionality of this
eigenfaces
data set is actually much lower than the
full number of attributes n.
Right?
That we can capture the ma, majority of
the variance just by using a
much smaller set, m, and in fact that's
typically what people do, they could use
the top, say, ten or 20 dimensions, which
would be much better than using all,
like, hundreds or thousands of dimensions
in
the, in the original phase state data set.
Right.
So and the, the eigenvalue plot here gives
you some
indication of just, by the, where that
fall off starts to
asymptote exactly, how many eigen vectors
you need to include in
your orthonormal bases to adequately
capture the variants of the data.
All right.
I want to close with a few notes on how to
implement
this efficiently for very large dimensions
or very large numbers of data points.
So obviously even these calculations
onerous for a
very large d or a very large n.
Things like computing the sample
covariance
matrix can be challenging for large
numbers
of data points computing as inverse can be
challenging for very large dimensionality.
There are efficient ways to, to handle
this.
One of the common ways is to use singular
value decomposition.
So it turns out, that the, solving that
eigen system that I showed
you before, is equivalent to performing
singular value decomposition on the data
matrix.
And you can simply use the left singular
vectors, or the, the left-
Yeah.
The left vector is U, here, which are
column
vectors of that, that singular value
decomposition matrix, together with
the top singular values in the diagonal
matrix D instead
of your eigenvalues and that amounts to
the same thing.
Actually.
And so this is, and because there are
efficient singular value decompositions
and incremental singular value
decompositions, you can use these to
improve the,
the compositional performance on, on very
large data sets.
Another approach is to just calculate one
principal component at a time.
I alluded before to intertive solutions to
the eigan system.
Roweis et al in NIPS provided a method
for calculating one principal component at
a time.
Another method would be to use an online
learning strategy, where
you train principal components analysis on
a subset of the data,
and then iteratively update that or
improve it sequentially in sort
of an online fashion so you can use a
sequential estimation approach.
There's other literature about how to do
that.
So it's not so important that you know,
offhand how to do this,
but simply that, you know, where, that
these methods exist in the literature
and if you get stuck with a problem that's
too large for, naive
principal compare and analysis, that there
are
alternatives other for computing solutions
more efficiently.
All right.
So to summarize Principal Component
Analysis is a
terribly useful tool to have in your
toolbox.
It's a reliable, standard method
for dimensionality reduction and
visualization.
The objective is to find an orthonormal
basis that maximizes the
variance of the projected data in the
resulting new feature space.
The basis vectors and eigenvalues can also
be
interpreted to provide insight about the
data set.
In particular, what the principle axes of
variation are.
And also what the intrinsic dimensionality
of your
dataset is, which is what the eigenvalue
analysis provides.