So in this lecture, we'll be discussing non-negative matrix factorization and how this can be applied
to topic modeling will begin this lecture with a quick outline.
This lecture essentially has two distinct parts.
The first part is to discuss recommender systems, which is what matrix factorization is best known
for.
The second part is to connect this to topic modeling to understand why something built for recommender
systems can also be applied to this seemingly unrelated task.
So let's talk about recommenders, suppose you are Netflix, you have a whole bunch of movies and a
whole bunch of users, and your job is to recommend movies to users, which they have not yet seen.
If you can do this successfully, your users will be happy and entertained and more likely to use your
service in the future.
Now there's a lot of almost philosophical discussion that could be had about how to recommend, for
example, YouTube, in my opinion, as a bad recommender system because it keeps showing me the same
things, which is very boring.
However, for the purpose of this lecture, we'll need to simplify what it means to make a good recommendation
for us.
A good recommendation is simply a movie that a user will rate highly.
Once we have predictions for a user's movie ratings, we can simply show the user those movies in order
with the highest predicted rating first.
So if I think you're going to read something five stars, I'd probably show you that first.
Therefore, our task has been simplified predict the ratings for movies that users have not yet seen.
Now, this type of recommender system requires that we already have a set of ratings to learn from.
So imagine that we have a set of users numbered from one up to em and a set of movies numbered from
one up to end.
If you have experience with databases, this should make complete sense since these numbers would just
be used radios and movie IDs in your database tables.
Now, imagine that we have a table of ratings with three columns User ID, Movie ID and rating every
time a user writes a movie.
We add a new row to this table with that rating, which can then be used in our machine learning system.
Now, database tables are nice, but we need to think a bit more abstractly in order to solve this problem,
in particular, how we would like to store our ratings.
Is it a ratings matrix?
In this matrix, users go along the rows and movies go along the columns.
Therefore, this is a matrix of size m by N.
However, note that this is no ordinary matrix in particular.
This is a matrix where we do not know most of the values.
That is to say, most of the values are simply missing.
Of course, this makes complete sense.
Think about why this would be if you haven't yet done so.
Suppose Netflix has 100000 movies in their database.
Now, consider how many movies you have personally seen.
Now, consider how many movies you have personally rated probably a tiny percentage of those 100000
movies.
Now, assume that you are an average user and that pretty much all other users have the same proportion
of ratings.
It should be easy to see that this ratings matrix mostly contains missing values.
We call this a sparse matrix.
Now, note that this meaning of sparse is different from what we encounter in NLP, such as when we're
using TFI Taf with a tier free of metrics.
This is called sparse because many of the values are zero.
This is different from the ratings matrix, which is called sparse because many of the values are simply
not there.
Now let's remind ourselves of what our goal is.
As you recall, our goal is to make predictions from movie ratings that users have not yet made.
In other words, our goal is to fill in the missing values of this ratings matrix.
So now we have a concrete task.
So what is matrix factorization, the basic concept behind matrix factorization is that we are going
to imagine that a ratings matrix is really just the result of multiplying two smaller matrices, as
you recall, the ratings matrix as Ambrose and and the columns.
We're going to break this up into two factors which are also matrices, which by convention we call
W and H W has the shape m by K and H has the shape K by N.
As you know, from the rules of matrix multiplication, the results of multiplying these two matrices
is a new matrix of size m by N, which matches our ratings matrix.
Of course, the trick here is that when you multiply these two matrices together, there won't be any
missing values.
Thus, in makes predictions for values which didn't appear in the given ratings matrix.
Now, for those of you with some familiarity with machine learning, if you want to think about how
we actually find these unique matrices, let's discuss that briefly.
As you recall, for many machine learning models, the way we train them is by defining some lost function
and then finding the parameters in this case, W and H, which minimize that loss.
So, for example, we might want to minimize the squared error between the true ratings and the predicted
ratings.
Another possible option is the cail divergence, which is the one we will use and corresponds to probabilistic
lean semantic analysis.
So there's a connection to other topics we've studied in this course.
Note that the facts I've just presented are optional, but may be useful and intuitive.
If you have some experience.
Another optional topic I want to discuss in this lecture is why it works.
Why does factor rising our matrix into two smaller matrices results in an accurate predictive model?
I consider this topic to be intermediate to advanced.
So if you'd like to skip this, please feel free to do so.
So as you recall, the main idea behind machine learning is to create a model with a small number of
parameters that essentially compresses the information in the training set.
If we wanted perfect accuracy, all we would have to do is simply memorize the training set in the dictionary.
Of course, that's not helpful, since it doesn't help us predict a new data.
So, for example, to train a linear model, we might have an input matrix of size 1000 by 10.
But the model itself only has 10 weights.
So we compress all that information from the training set into just 10 numbers.
This is much smaller than our input data, which had 10000 numbers.
So the same idea applies to our ratings matrix.
Our ratings matrix technically could have rank em or rank in whichever is smaller and perhaps even less.
As you recall, the rank of a matrix is the number of linearly independent rows of columns, whichever
is smaller.
For all intents and purposes, just think of it as the smallest dimension.
But if you look at our model, which consists of W and H.
We choose to be much smaller than both men, which means that they both have rank typically values of
care between ten and a few hundred.
And in total, the number of parameters would be m times K plus K times N.
So by approximating a very large matrix with two very small matrices which have much lower rank, we
are compressing the information in the training set, which allows us to predict unknown data points
just as we do with models like linear regression.
Also important to note is that by doing this, we are making a modeling assumption that the true rank
of the ratings matrix is actually just K, and this is because when you multiply W and H together,
which both have ranked K, this gives us the predicted R matrix, which still has rank K.
You can think of K is the true number of hidden factors or in relation to this lecture.
The true number of hidden topics.
Now we've just described regular matrix factorization.
But what makes it non-negative matrix factorization for the purpose of this lecture?
The idea is very simple.
It just means that both W and H only contain at non-negative values.
Of course, this should be the case, since we know that these values will end up being some representation
of topics.
Documents only contain non-negative amounts of topics, and topics only contain non-negative amounts
of words.
That is, the values we see are always greater than or equal to zero.
We can ensure that these values remain not negative, by the way we do our updates, but this is not
a relevant topic for this course.
Now, I alluded to this on the previous slide, but let's address this question explicitly.
We just discussed matrix factorization in terms of recommender systems.
But why is it related to topic modeling?
Well, it helps to recall LDA.
The output of LDA, as you recall, is essentially two matrices, one with documents by topics and another
with topics by words.
But this is exactly what an AMF gives us.
If the input to our matrix factorization model is a tier of RDF matrix, it will be documents by terms.
The topics are hidden variables.
So as usual, we choose this value in our recommenders analogy.
This would be K when we perform matrix factorization, we get the two matrices W and H, which will
be documents by topics and topics by words.
Therefore, this is exactly the same as what we get with LDA.
And therefore applying an AMF to topic modeling is simply a matter of plugging in our documents by terms
matrix.