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.