So, given that these are the applications, let me now tell you
the first data dimensionality reduction technique we will talk about.
And this, this is called the SVD or the singular value decomposition.
And the way we think about this is that the input to our method is a matrix.
We will call this the input data matrix.
That has it's, is of size m by n, which means that it has m rows and n columns.
So the way I can think of this is, for example,
if I think of this matrix A as a document matrix, I can think of every row,
representing a document and every column, representing a different word.
So now every document is represented as a long, vector of zeros and
ones, when zero means, that the word does not appear in the document and
one means, that the given word appears in the document.
I could also think, for example, of this data matrix as a set of,
as we will talk about later of movies and users, right.
So I can think of every row as a different user and
I can think of every column as a different movie.
And I can have, a value of one in a give,
column row pair, if a given user watched a given movie.
So, this is my imput.
Data matrix and what I want to do is, I want to do the following, I want to
take this matrix and I want to represent it as a product of three matrices.
I will call them U, sigma, and V.
Okay? And
this is called the singular value decomposition.
So I take my regional matrix and
I represent it, using a product of three different matrices.
And these three different matrices have some constraints on them.
So let, so let me explain those to you.
So first, we say that our matrix A is a product of U Sigma V, where the column U,
the matrix U, is of size m times r, so it has m rows and r columns.
And this matrix, we will call it stores left singular vectors so,
its of size m times r right and and we can think of this r as concepts or
topics, I'll, I'll give examples later but for now the important thing is that r,
we can think of r as a very small number.
Okay?
Then, I have, so I have the matrix of left singular vectors.
Then I have a special matrix.
I call it sigma.
This is the vec matrix of singular values.
And this is a diagonal matrix, basically that ha, that is of size r times r.
And basically it has it has its zeros everywhere except on the diagonal.
Okay so only, basically this matrix is full of
zeros only on the diagonal that are non-zero elements.
And these non-zero elements I call, singular values.
And what we'll also assume is that these singular values are sorted in
the decreasing order.
So the, the largest singular value comes first and
then the second largest and so on.
And then, the last matrix that we have is the matrix V and
this is the matrix that we will call, that it stores the, the right singular vectors.
So the size of this matrix will n times r, where n is the number of columns in our
original matrix A and again r in this case is some small number we can think of this,
r as basically being the, the rank of the matrix A.
So, what we have so far is, we, we have a way, or atleast conceptually we have a way
to take our matrix A and represent it, as a product of three different matrices
where the matrix sigma has this special structure, that is dia, diagonal matrix.
So, what do I mean this diagonal matrix?
As I said it only has, the non-zero values, on the diagonal and
everything else is full of zeros.
So I just gave you the, a mathematical way of looking at how,
matrix A can be represented as a product of three matrices.
But now let's look at it kind of graphically.
So, the way this looks, works is the following,
I'm giving the input data matrix A, that has m rows and n columns.
And I want to represent this matrix, as a product of three matrices,
U sigma and V transpose.
Where I can think of the matrix U as very thin.
So, very few columns.
But m rows matrix.
So something that's, thin and long.
Then, I have this special matrix sigma,
that only has el, values on the diagonal elements and the rest is zero.
And then I have this other matrix V transpose,
that has a small number of rows r rows, but it has n columns.
So, basically, what we did in a sense, is we will take this big matrix A and
then represent it as a product of a theme.
And not all matrix, are diagonal matrix.
And a very long and of low height matrix V.
So, this is one way how to look at this in terms of the product of three matrices,
here is again a different way of looking at it.
So, now I can think of this as that matrix A is a sum of different matrices,
where basically I took the same thing as I had before, but
now I'm representing it as other products of different vectors, right?
So I'm, in some sense taking the left singular vector,
multiplying it with the singular value, value and
then the right singular vector and then I add to it the second left singular vector,
the singular value and the second right singular vector.
Right, and the colors between the two slides correspond to each other so
all, I basically did in this representation is I, took the red rows and
columns and put them, to the first product and then I took the green, but O and
column and the sin, singular value and I put it to the second outer product.
So, so, this is what we're trying to do graphically.
And that is the theorem the SVD theorem that says that it is always possible,
to decompose a real matrix A into this product of matrix, of matrices U,
sigma, and V transposed.
And when I say a real matrix I mean, a matrix where,
where its values are, are real numbers.
Right. So not complex numbers, but real numbers.
And what, what this theorem says is the following,
first it says, that this is always possible.
And by this we mean that it, it, for any possible matrix A we can find this
decomposition, more over this decomposition is unique.
Which means there is only one, set of values or
one matrix A that gets decomposed into exactly one matrix U,
a unique matrix sigma, a unique matrix V, so that's the first thing.
The second thing is that matrices U and V are what is called column orthogonal which
means the columns of U, and we have length one.
So the sum of the squared values of the,
in each column of these two matrixes equals one.
And then the other one is that these columns are orthogonal, which means that
if I take two columns of U, or if I take two columns of V and I multiplied them
with each other, if I [INAUDIBLE] with each other, I get a zero, right?
So, in, what this means is that both U and V,
for, in some sense, form a basis, which means that I have,
each each column has [INAUDIBLE] one, this is called, this is part the, the normal.
And orthogonal, orthogonality is that the unit product is
zero between different columns of a, of a given matrix.
So that's the first important thing about the structure of columns U and
V and the, important thing about the structure of the,
of the, of the matrix sigma is that it's diagonal, which means that the entries,
of matrix sigma, which we call singular values, are all positive and
they are sorted in the decreasing order, which means that sigma one, is
greater than equal to sigma two, to sigma three and they are all greater than zero.
So, what do we know is that, for any given matrix A,
there is a unique set of matrices U, V and sigma that, are in,
that we are able to compute in order to decompose A, that U and
V that are in the columns of it are orthonormal, which means, unit length and
orthogonal and matrix sigma, is diagonal matrix with
non non-zero elements when it's always giving the singular values on it.
Let me give you now an example of how we can think about this, so
let's think about the users to movies matrix right so,
let's think of our we have we are a Netflix or user review website or
we can think our set, of ourselves as a movie selling business.
And what we do is the following, we have a set of people and we have a set of movies.
Right and every, every person goes and watches some set of movies and
they tell us whether they like that movie or not.
So well, a value of one means that they didn't like the movie that much and
five means, they really enjoyed the movie.
Okay? So
every column in this matrix corresponds to a different movie.
And every row corresponds to a different user.
Right? So what this means is for
example there is this particular user.
Let's call it the user number three.
That watched only the movies matrix alien and sere, serenity.
They really liked those movies.
While they didn't like the Casablanca and Amelie for example.
Right?
And now with given this kind of matrix.
This is our matrix A.
Our goal is to decompose this matrix, using the singular value decomposition.
So we want to decompose it in terms of this long and, and narrow matrix U.
The diagonal matrix sigma and the, matrix width.
So, if we, if we do this, the way we can think of, of this different elements
of this matrix, is that basically in some sense we want to discover concepts.
Right in some sense we would like to discover that in, the matrix that I
gave you that basically we have this set of science fiction movies and
we have also a set of users who like science fiction movies and I, I have a,
we have a set of other users.
Right the, the bottom three users that all like romance movies.
And they don't really like the Sci-Fi movies, so
in some sense, movies break into group into two groups one group is about Sci-Fi,
the other one is about romance and also users break into the two
groups into the kind of Sci-Fi lovers and the romance movie lovers.
So now, basically, this is what SVD will allow us to figure out.
So, if you take this matrix, let's say type it into Matlab and
do the singular value decomposition, this is what we obtain.
So we obtain our matrix U.
We obtain our matrix Sigma.
And we obtain our matrix V transpose.
And here is how, how we can think about the,
the what we learned from the singular value decomposition.
So the first thing is, the columns of U.
We can think of this as concepts right so for
example the first column of U, corresponds to the, to the Sci-Fi concept and
the second column of U, corresponds to the romance concept.
So, what is, what we learn from here is that for
example the first five users readily strongly belong to the Sci-Fi concept and
the second five users second three users, correspond heavily to the romance concept.
In terms of, this we can think of in some sense that
of matrix U as a user to concept matrix right so every entry here,
tells us how much that a given user correspond to a given to a given concept?
So the first user corresponds heavily, to the first concept,
to the SciFi concept while for example the fifth user
corresponds heavily to the second concept to the romance concept.
So this in some sense matrix.
We can think of it as a, user to concept similarity matrix.
Then we have the singular values Sigma.
And here, what we think of this is that every, every value is non-zero.
And it's positive, right, non-negative.
So we can think of this as, the strength of every concept.
So in our case, we would see that, the strength of our Sci Fi-concept is
higher than the strength of our, romance concept, all right?
And then we need to also explain, the matrix V and the way we
can think of matrix V is we can think of it as a movie to concept matrix, right?
In a sense that it tells us that, that the first three movies heavily corresponds to
the, belongs to the first concept, while the last two movies heavily corresponds to
the, to the se, to the second concept, which we named, the romance concept.
Of cour, of course, in both cases, we also have this third concept that, that in some
sense, has very low strength, so we can kind of ignore it and it, it just okay?
So this is one way how we, basically we can already go and
learn something from, from the SVD, right?
We took some matrix of data points.
And we performed the SVD.
And very quickly we saw that basically we have two, two concepts of the,
of the main, of lots of strength.
The first one we, we, we were able to interpret as the concept of Sci-Fi movies.
The second one is the concept of romance movies and then for
every user, we know how much they belong to the, to each concept so for
example the first user heavily belongs to the,
Sci-Fi concept and relatively very little belongs to the, romance concept and
then also for every movie, we know what concept its belongs, it belongs to.
So for example the, the first movie, heavily belongs to the,
to the first concept and much less to the second concept.
It also belongs quite heavily to the third concept, but
as we see from our matrix sigma, the third concept has a very low overall strength,
so it's not so important in explaining the data.
So, in, what is the first interpretation of our SVD?
Basically, the first interpretation is that we can take this, let's say users,
users to movie matrix and we can interpret our, our data in terms of movies,users,
and the concepts or different genres, or topics right?
So, we can think of U as user tool.
Concept similarity Matrix, V as a movie to concept similarity matrix.
And then matrix sigma, or its diagonal matri entries, the singular values,
as the, as modeling the strength of each concept.