Latent Factor Recommender Systems | Stanford Lecture 55

[00:00:00]so talking about latent factor Commander systems the the main idea of the latent factor Commander 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 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 recommend ations the way we talked about the goodness of recommendations was using the root means squared error right the idea is the smaller the RO the root mean squared error of our rec Commander 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 we want to predict in the future what people are going to like of course we cannot really do this because we are not profits we don't know the future so what we will kind of have to be satisfied with is this second point right it's 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 will be to predict those ratings well and hopefully by doing that if we then go and take this recommander system and release it let's say live on the on the Netflix website that that system would also work well for the truly unknown ratings right so the way we think about uh rating prediction for recommander systems is the following we have our rating Matrix r with users and uh 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 um uh 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 uh 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 predicting 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 uh P the 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 um 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 we can think of this K as maybe 100 200 300 right so something much smaller than what is the total um number of users in our data set and similarly Matrix P will be this kind of also very thin Matrix where it we have one column per user and it has K row where again K is this parameter that that we choose right so for now let's just assume that we can approximate our Matrix are simply as a product of two thin or narrow matrices q and P okay there is one slight 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 that okay so all we did is we we kind of mathematically assumed that we can take R and factorize it into this uh two as a product of these two matrices okay what is 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 a column of P simply as a as a three let's say threedimensional representation of a given user or of a given um 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 mapped them into this uh in as I showed in the previous slide in this kind of threedimensional space and this is why and this axis of this um lat and Subspace are called um factors right so kind of the idea is that now movies and also users get mapped into this uh into this space where basically this AIS 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 two main axis of variation there are movies that are geared towards females and there are kind of the guys 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 are movies are closer together than some other pairs of movies and users right so that's kind of what latent factor Commander 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 uh are close together with each other so now assuming that we can do this uh take the Matrix R 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 um that is very easy all we have to do is to say ahuh 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 colum from Matrix p and now what we do is basically we dot product these two vectors with each other right so basically we do a weighted combination or a inner product between these two vectors and if you would if we were to go and multiply these two vectors together the prediction we would get is 2.4 right so our prediction about user four liking um use movie number two what basically predicting the rating would be uh 2.4 so what this really does as I mentioned before is that that the whole method discovers this latent factors or these latent dimensions in which the movies can be mapped according to the Matrix q and also um uh people can be mapped into the same space according to the Matrix P right so what would happen under this uh this view is that users are points in this space movies are points in this space and then um the prediction basically means is what users are close uh to what movies of course this also very nicely relates to the sing 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 we 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 time V transpose and call and call this part our P transpose right so in some sense SVD is already kind of doing or it seems it's doing what we want right so that R equals um Q * P transposed and SD is able to compute this for us however even though it seems we are done we are not really done um 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 Rec construction 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 uh value of that entry in The Matrix right this is the AI J is the entry in the data Matrix and sigma U * Sigma * 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 root mean squared error right if the sum of squ 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 multiply it by some constant one over the number of data points right what this basically means is that SVD is already minimizing the root mean square error right actually um SVD is able to find the product the three matrices that give us the best possible root mean square error right which is great so it seems SVD is really the right thing to do in this case however there is one slight complication and this is this I write here right the complication is that SVD um assumes that the Matrix a has all the entries given right the summation here I J 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 you were just to ignore those parts basically what that would mean is that no rating is interpreted 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 think of the SVD but change it a bit so the way we change the SVD is is the following right what we 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 specialized me 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 a sense that we want to find matrices p and Q that minimize the sum of squared errors but now the errors right the the we only go over the end entries 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 mat p and Q that minimize this expression that are basically best able to predict known known ratings in my Matrix are and I hope that by being able to find such matrices p and Q I'll be also a able to predict well the M the ratings that I don't even know so the unknown ratings a few things to note here first is the difference between SVD is that here for p and Q are kind of completely arbitrary so we don't require that columns um are orthonormal meaning that vectors are unit length and they are orthogonal to each other um as I mentioned before we can think of matrices p and Q as mappings of users and mappings of uh 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 this latent factor Commander systems were the most widely used and also the most successful method in the whole uh in the whole competition so what we will do next now is we will learn how do we actually go and solve this latent factor optimization problem so the equation I have written uh here