So talking about
Latent Factor Recommender Systems.
The, the main idea of
the Latent Factor Recommender Systems,
is that we will think of recommendations
as an optimization problem.
And the way we think of this
as an optimization problem,
is that we think of recommendations
as a rating prediction.
And then the optimization is that we
want to find the method that gives us
best rating predictions.
So here's, here's the global idea.
The global idea, or the goal is that
we want to make good recommendations.
The way we talked about
the goodness of recommendations,
was using the root mean square data.
Right, the idea is the smaller the root,
the root mean square data of recommender
systems the better the recommendations.
Of course, what we would really
want is that we would want to
make good recommendations on items
that people haven't yet seen.
Right, basically want to predict in
the future what people are going to like.
Of course, we cannot really do
this because we are not prophets.
We don't know that future.
So what we will kind of have to be
satisfied with is the second point, right?
We, we want to build
a system that is able to
predict the ratings that
we already have well.
In a sense, what do I mean by this,
is that we have our rating matrix.
We will hide a few entries from it, and
our goal would be to
predict those ratings well.
And hopefully, by doing that,
if we then go and
take this recommender system and release
it, let's say live on the Netflix website,
that, that system would also work well for
the truly unknown ratings.
Right?
So the way we
think about rating prediction for
recommender systems is the following.
We have our rating matrix R with users and
movies.
And our goal is that we want to make
a system that predicts well the,
the hidden ratings.
What do I mean by this, is that we
will take some of the ratings from,
from our rate utility matrix and
we will hide them.
And our goal will be to build a system
that for each of these cells,
kind of exactly predicts
the value that is in that cell.
Right?
So we want to
kind of hide the known things and
then predict it.
And the idea is that the, the system
that is able to make the smaller root
mean square error between
the true ratings and
the predicted one,
that's the best system we have.
Now, how do we approach the rating
predict, prediction problem?
The way we will approach this
is through matrix factorization.
And this is why these models
are called latent factor models,
because we basically go and
factorize the matrix.
In some sense, we will be applying
singular value decomposition, or
a version of singular value decomposition
to the Netflix utility matrix.
And the way we will do
this is the following.
So, we are given our matrix,
R, and we will try to represent our
matrix R as a product of two matrices.
Matrix Q and matrix P, right?
So, we will say that matrix R
equals matrix Q times matrix P.
The difference here is the following,
right?
So if you think of the matrix R as items
to users or movies to users, then we can
think of matrices P and Q as kind of
thin and very long matrices, right.
So for example, we will think of
matrix Q to have the one row per item.
And it will have k columns, or k factors,
where k is some value that we will decide.
And usually you can think of this
K as maybe 100, 200, 300, right?
So something much smaller than what is
the total number of users in our data set.
And similarly, matrix B will be this
kin d of also very thin matrix,
where we have one column per user, and
it has KUO, where again K is this
parameter that, that we choose.
Right, so for now let's just assume
that we can approximate our matrix R
simply as a product of two theme,
or narrow matrices, Q and P, okay?
And there is only issue that R really
has missing or unknown entries.
Right, that there are these regions
of matrix R that are all unknown.
But for now, let's ignore them, okay.
So what we did is we, we kind of
automatically assumed that we can take R
and factorize it into this two as
a product of these two matrices.
Okay, what this really does to,
to to the data is the following.
The way we can think of every
row of our matrix Q, or
every column of our matrix P,
is that basically every item and
every user gets mapped into
this three dimensional space.
Right?
So we can think of every row or
our column of P simply as a,
as a three, let's say,
three-dimensional representation of
a given user or of a given movie, right?
So what this really means is that we
took this big utility matrix R, and
now we took all the movies and
all the users and map them into this.
In as, I showed in the previous slide in
this kind of three dimensional space.
And this is why in this axis of this
latent subspace are called factors.
Right, so
kind of the idea is that now movies and
also users get mapped
into this into this space
where basically this axis that we
find here are the axis of variation.
Right?
So maybe just hypothetically,
imagine that what our factorization
would discover is that we have,
our space has too many axis of variation.
There are movies that
are geared towards females.
And there are kind of the guy's movies.
And then there are you know,
the serious movies.
And then there are funny movies.
Right and now every user is is a data
point somewhere in this space, and
also every movie is a data
point in this space, right?
And some users and
movies are closer together than some
other pairs of movies and users.
Right, so that's kind of what latent
factor recommender system is doing.
In some sense, it's finding this low
dimensional representation of users and
movies, such that kind of
people that like those
movies are are close
together with each other.
So now, assuming that we can do
this take the matrix out and,
and represent it as matrix, matrix P and
Q, the question is, how do we estimate
the missing rating of the matrix R?
Right, so for example,
what is our prediction for
a given cell of the matrix R.
That is very easy.
All we have to do is to say a-ha!
We are making a prediction for
user number four and item number two.
So all this means is we have to take
the corresponding row from the matrix Q,
and the corresponding
column from matrix P.
And now what we do, is basically we dot
product these two vectors with each other.
Right?
So basically we do weighted combination or
inner product between these two vectors.
And if we would, if we were to go and
multiply these two vectors together,
the prediction we will get is 2.4.
Right, and so
the prediction about user four liking
movie number two, basically,
predicting the rating, would be 2.4.
So, what this really does,
as I mentioned before, is that,
that the whole method discovers these
latent factors or these latent dimensions.
In which the movies can be mapped
according to the matrix Q and
also people can be mapped into the same
space according to the matrix B.
Right?
So what would happen under this this view
is that users are pointing this space,
movies are pointing this space, and
then the prediction basically means is
that what users are close to what movies.
Of course, this also very nicely relates
to the singular value decomposition that
we already know about.
So let me remind you about the SVD.
What SVD does right, in that lecture we
said let's assume we have some matrix A,
and we want to represent this matrix as
a product of three matrices U, Sigma, and
V transpose, right?
And we, we called the matrix U to be
the matrix of left singular vectors.
Matrix Sigma,
is the diagonal matrix of singular values.
And the matrix V, is the matrix
of right singular vectors, right.
And we showed in that lecture that this
can be done for any matrix, and so
on and so forth, right?
So in some sense,
SVD is already doing what we want, right?
So, if we take our matrix R and
perform SVD of it,
then we could simply take the matrix U and
call it as matrix Q.
And we would, we could take the product
of sigma times V transposed and call, and
call this part our P transposed.
Right?
So, in some sense,
SVD is already kind of doing what it
seems it's doing what you want, right?
So that R equals Q times P transposed.
And SVD is able to compute this for us.
However, even though it seems we are done,
we are not really done.
Before I tell you why we are not
really done, let me tell you kind of
one more good thing that kind
of comes from SVD for free.
So one thing that we
know about SVD is that,
SVD gives us minimum reconstruction error,
right?
SVD gives us the,
the minimum sum of squared errors between
the true value of the, of in an entry
of the matrix versus the approximated
value of that entering the matrix, right?
This is the Aij is the entering the data
matrix, and sigma U times sigma
times V transposed is basically the, the
value the approximation coming from SVD.
And we already know that SVD gives us,
in some sense, is the solution to
this minimization problem, right?
Finding the three matrices such that
the approximation is as good as possible.
What is there to note?
First thing to note is that
this sum of squared errors,
is basically the same as
the root mean squared error, or
is related to the moo,
root mean squared error, right?
If the sum of square,
squared errors is small, the root
mean square error will also be small.
Why?
Because the two
are monotonically related, right?
Root mean square error is nothing
else than sum of squared errors,
the square root of that, and
then multiplied by some constant,
1 over the number of data points, right?
What this basically means is that,
SVD is already minimizing the root
mean square error, right?
Actually SVD is able to find the product
that the three matrices that
give us the best possible root
mean square error, right?
Which is great.
So, it seems SVD that I
think to do in this case.
However, there is one slight complication,
and this is, this I write here.
Right?
The complication is that SVD assumes that
the matrix A, has all the entries given.
Right?
The summation here, ij over A,
goes over all the entries of matrix A.
Right?
The matrix A is kind of
completely filled in.
But our matrix R, is not filled in.
Right?
Most of the matrix is empty.
Meaning for most of, for
most part of that matrix,
we don't know how much does
a given user like a given movie.
So if we were just to ignore those parts,
basically what that mean is that no
rating is integrated as zero rating.
Which is clearly wrong in our case.
Right?
So this me,
really means that R has missing entries,
and
SVD is not able to accurately account for
the missing entries.
So, we have to kind of be a bit smarter.
We have to take, think of the SVD,
but change it a bit.
So, the way we change the SVD is,
is the following, right?
What, what we know is that
SVD isn't defined when for
the entries that are missing.
So, what we need to do,
is we need to basically,
we will have to use special meth,
specialized methods to find P and Q.
In particular, we will, we will do,
we will solve the following
optimization problem.
Right?
Recommendations as optimizations,
in the sense that we want
to find matrices P and
Q that minimize the sum of squared errors,
but now the errors, right?
The, the, they only go over
the entities of matrix r.
Meaning, we only go over
the yellow entries of matrix R,
and not all the cells of the matrix.
Right?
And what, what this is saying
is the following, right?
So, I want to find matrices P and
Q, such that, when I sum over all
the known ratings, the, the value of
that rating minus my predicted rating,
that difference,
squared is as small as possible, right?
So, now, the game is kind of,
it's very clear.
I want to find matrices P and
Q that minimize this expression,
that are basically best able to predict
known, known ratings in my matrix R.
And I hope that by being able
to find such matrices P and Q,
I'll be also able to predict well the may,
the ratings that I don't even know.
So the unknown ratings.
A few things to note here.
First is the difference with SVD,
is that here, for P and
Q are kind of completely arbitrary.
So we don't require that
columns are orthonormal meaning
that vectors are unit length, and
they are orthogonal to each other.
As I mentioned before, we can think of
matrices P and Q as mappings of users,
ma, mappings of movies into
this low dimensional space.
And what is interesting is that this was,
if there was kind of one big
breakthrough in the Netflix challenge,
then these latent factor recommander
systems were the most widely used.
And also the most successful
method in the whole competition.
So what we will do next now, is we will
learn how to actually go and solve
this latent factor optimization problem,
so the equation I have written here