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.