So far, we saw our singular value
decomposition on this small users to
movies example, where what we saw was
basically we took this regional matrix and
we were able to represent it as
a product of three matrices.
And there, we talked about the sci-fi
concept, the romance concept, and
then there was this, also,
the third column that we kind of
had very low strength, right, the third
concept that had very small strength.
That we kind of brushed under the rug and
didn't really talk about.
So what I want to do now is actually
talk about, how do we really do di,
dimensionality reduction?
In a sense, how do we discover that our,
movie data, really had only two real kind
of strong concept and the, the, the last
third concept, was more like noise.
And it was okay to, to kind of remove
it from our analysis and discussion.
So the idea is, how do we,
what is SVD really doing and
how do we think about it in terms
of dimensionality reduction?
And, what SVD is really trying to do,
it basically, in some sense it gives us,
the best axis to project on.
So what do we mean by this is that the,
the best means that,
the sum of the squared
projection errors is minimized.
Okay.
So in some sense, we want,
we want small set of xs such that we,
if we represent our data in terms of that,
of that axis we get the minimum
reconstruction error.
And a simple example how see this, would
be in this two-dimensional example, where
imagine every different axis is a separate
movie, and we have users ranking movies.
And every point is now a user.
And the x position of this mark is how
much they, they rated use Movie 1 and
y position is how much they rated Movie 2.
And assume that our data lies in
this kind of, in this kind of shape.
So then if you think of of it and say,
okay, we are only given one coordinate
to be able to represent this data.
So not two coordinates, but
I only give you one coordinate.
What is the best, axis, along which
you want to represent this data.
So for example in this case,
this would be the best axis.
And now every data point, we can represent
as a single number, which is simply,
the position or the projection of
a given data point on, on this slide.
So for example, the, the,
the data point that I'm just drawing the,
the red data point here would project to
this line to this particular, location.
And now, my goal is that when
I now represent these two
dimensional points simply by the,
by their position on,
along my red line, the sum of
the squared errors of the locations.
So basically the dis, the distance
between, its true position in the,
in the position a,
along the line should be minimal, and
this is exactly what SVD does.
So, what SVD does is finds
the best vectors, or axis,
on which to project the data, such that
the reconstruction error is minimized.
So let me give you an example
of what do I mean by this.
And now for example, also the question is,
given this two-dimensional data,
how do I discover the best,
the best axis on which to project?
And how do I really do
dimensionality reduction?
How do I discover the position
of the point on this given line?
So the idea is the following.
We are given our matrix A.
And we want to,
we represent it as a product of three
matrices, u sigma and v transpose.
Where we think of V, as a movie-to-concept
matrix and U as a user-to-concept matrix.
So what this means
immediately that we see that,
V is a movie-to-concept matrix which means
that for example if you want to ask,
what is this vector V1 along which it
is the best to represent the data,
that is simply the first straw
of our matrix V transpose.
All right, so
this is exactly the, the vector,
That represents the the,
the 's of the highest variation.
So, I, I have still my,
our old example of users to [INAUDIBLE]
represented And SVD of this thing.
And now the question is,
how do we do the dimensionality reduction?
So for example the way, we do
dimensionality reduction is that we can
think of the whole system the,
the following that our first right
singular vector, gives us the, location
the axis on which we want to project.
And then the, the corresponding singular
value, tells us the variance along that
given dimension or the spread of
the values along that given dimension.
So in our two dimensional case here,
the va,
the values are really spread
around the first singular vector.
They are spread around the bit,
the second singular vector a bit less.
And they are not really spread
around the first singular vector.
So the, strength of the import,
importance of that vector, is very small.
So now what we can think of, we can
think of the locations as the following.
So, so far I talk to you,
what defines the axis?
Now, the next question is,
what defines the positions, or
coordinates of the points in
this new then, new space?
And the way we can, think of that is
that we simply take the matrix U,
and multiply it with si, with sigma.
Right.
And this gives us
the coordinates of the points in,
on this projection axis.
Right.
So, basically, how do they map down,
to our length.
Right.
So, for example, if I compute,
given my matrix A,
I compute the product of U times sigma.
Here is the, here is now the position
of every, of every user in this new,
new space where, for example,
the first vector simply tells us what is
the location of every user, along,
along the first right singular vector.
And for example here you see that,
the values vary quite
a lot along the first one.
The vary quite a lot along the second one,
right?
The range is very high.
But for example the third one,
everything is kind of around 0 or
the, the variation on the,
along the third column is much smaller.
Which is why the, the third concept had a,
had a very small weight.
So now, given that we have our matrix
A and again the singular value
decomposition of it, the question is, how
do we really do dimensionality reduction?
All right, so so far I just
showed you how we can represent,
the regional data points in this
new in this new projected space.
But the question is, how do we
really do dimensionality reduction.
And that turns out to be very simple.
All basically we need to do,
is we need to go, and
set a given set of singular values to 0.
And basically we take the smallest,
if we want to preserve,
preserve K dimensions,
then basically we take R minus K singular,
smallest singular values,
and set them to 0.
So for example in our case here,
if we want to do dimensionality reduction
from this three dimensional space,
to a two dimensional space,
all we need to do is take the small,
the small singular value, set it to 0.
Which in some sense means, we that now
we also take the third column of U and
third row of V transpose and
set them to 0.
So, the way we can do dimensionality
reduction is to now take U, then
you sigma and then you retranspose where
we took the last singular value, the last
singular vector, and the last right
singular vector, we set all of those to 0.
So if we would now, for example go, and
take, take the three new matrices that,
that are now smaller right,
they only have two columns and two rows.
And multiply this thing together.
Here is the matrix we would obtain.
Right, so here is our ori,
original matrix A.
Here is our, new matrix A.
Call it A prime or let's give it a name B.
And what you notice is that, A and
B are very similar to each other.
So what do I mean by similar to each
other is that if I take a given element.
For example this number 5 here, and
I compare it to this value here,
to the same axis in to
the same cell in matrix B.
We see that the difference is very small.
Right?
Or, for example, I can take this 0 here,
correspond it compare it to
the corresponding element in B,
and again I see
the difference is very small.
So what we basically did is we took in the
previous slide we took our original matrix
A representative, did SVD and we were
able now to exactly reconstruct it.
Now we actually took removed
a few col last column from U and
the last column from V, and
we removed the singular value.
Now we represent everything as a,
as a, as a smaller set of matrices.
So these matrices are now smaller.
If we multiply the three matrices
together now the new matrix we obtained,
was very similar to the original matrix A.
And when I say very similar,
we can quantify the similarity of
two matrices using what is called
the Frobenius norm, right.
And the Frobenius norm of
two matrices is simply the,
the sum of the differences
of their entries, right?
So if I say I have matrix A,
I have matrix B.
So their distance, their Frobenius norm,
is simply,
I take a summation over all the entries.
I take the difference of the entry
values sum them square the top
sum those entries together and
take a square root and that's my distance.