Recommender Systems: Collaborative Filtering & Matrix Factorization

[00:00:00]in this next set of videos I'd like to tell you about recommender systems there are two reasons I had two motivations but why I wanted to talk about recommender systems the first is just that is an important application of machine learning over the last videos occasionally I visit different technology companies here in Silicon Valley and I often talk to people working on machine learning applications there it's all about people what are your most important applications of machine learning or what are the machine learning applications that you would most like to get and improve in a whole new book and one of the most frequent answer I heard was that many groups out in Silicon Valley now trying to build better recommender systems so if you think about what of the website of the Amazon or what Netflix or what's eBay or what iTunes Genius made by Apple does there are many websites or systems that try to recommend new promise view so Amazon recommends ebooks video Netflix try to recommend movies do and so on and these sorts of recommender systems that look at what books you may have purchased in the past or what movies you rate them in the past but these are the systems that are responsible for today a substantial fraction of Amazon's revenue and for confident Netflix the recommendations that they make do they use it is also the transport of a substantial fraction of the movies watch sighted users and so an improvement in performance of a recommender system or another substantial and immediate impact on the bottom line of many of your companies um recommender systems is kind of a funny problem within academic machine learning so let me to go to an academic machine or any conference the problem of recommender systems actually Metheny relatively little attention or at least it solves a smallest fraction of what goes on within academia but if you look at what's happening when the technology companies are the ability to build these systems seems to be a high priority for many companies and that's one of the reasons why I want to talk about being responsible the second reason that I want to talk about recommender system that as we approach the last few sets of videos of this clause I wanted to talk about a few of the big ideas of machine learning and share of you know the big ideas in machine learning and we've already seen in this class that features are important for machine learning the features you choose will have a big effect on the performance of the learning algorithm so this is Big Idea machine learning which is that for some problems maybe not all problems with some problems there are algorithms that can try to automatically learn a good set of features for you so rather than trying to hand design your hand code the agent which is most important to you so far there are a few settings where you might be able to have an algorithm just learn what they should be used and the recommender systems is just one example that sort of thing there are many others but in going through recommender systems will be able to go a little bit into this idea of learning the features and you will see at least one example of this I think Big Idea machine learning as well so without further ado let's get started and talk about the recommender system problem formulation as my running example I'm going to use the modem problem of predicting movie ratings so here's the problem imagine that you're a website or a company that sells or rents on movies and what have you and so you know Amazon and Netflix and I think I choose are all examples of company I do our examples and company to do this and let's say you let these users rate different movies using a one to five star rating so you know something one two three four or five stars in order to make this example just a little bit nicer I'm going to allow zero to five stars as well because that just makes some of the nap come on later although most of most of these websites use a one to five Smart View so here I have five movies you love the lasts remains forever a few projects of love not subconsciousness sources the karate and we have four users which calling your Alice Bob Carol Dave with the initials ABC and D cauldron uses one two three and four so let's say Alice really likes melted last at least at five stars really likes romance forever rated 5 stars she did not watch two puppies a lot but did not rated so we don't have her anything for that and Alice really did not like non-stop consciousness or soldiers karate and different user Bob user to maybe raise a different set of movies maybe she likes weather laws did not to watch romance forever just elevating the poor zero zero and maybe our third user raise the zero did not watch that one zero five five and notice the sort of some of the numbers okay and so just to introduce a bit of notation this notation be using throughout I'm going to use nu to denote the number of users so in this example and you will be equal to four so the new subscript sensor uses and nm I'm going to use to denote the number of movies so here I have five movies so in M equals five and you know for this example I have for this example have usually Lee may be romantic or romantic comedies and meet two action movies and you know if you look at a small example it looks like Alice and Bob are giving high ratings to these romantic comedies or movies about love and giving very low ratings about the action movies and so Carol and Dave is the opposite right Carol or day if you use a student or really like the action movies and doing high ratings but don't like the romance and love type movies as much specifically in the recommender system problem we are given the following data of data comprises falling where these values are IJ and RJ is one if user J has rated movie I so I do this debate only some of the movies and you know has we don't have ratings for those wings and whenever our IJ is equal to 1 whenever user J has rated we di we also get the num get this number of yr J which is the rating given by user J to Gujarat and so why IJ will be a number you know from zero up to five depending on the star rating 0 to 5 stars that the user gave that with karubian so the recommender system problem is given this data set that is given these them are our GS and the yr J's to look through your data and look at all the movie ratings were missing and to try to predict what these values of a question mark should of in this specific example have a very small number of movies in a very small number of users and so most users have rates in most movies but in the realistic setting your users with each of your users may have rated only a minuscule fraction of the movies but look in this data I was involved both like the romantic movies maybe we think that Alice would have given this a 5 maybe with the involvement of Japan deserve 4.5 or some high value whereas we think maybe Carol and Dave live during these very low ratings and Dave well if Dave really like action movies maybe he would have given swords internality for rating or mediafire region okay and so the job in developing a recommender system is to come up with a learning algorithm that can automatically fill in these missing values for us so that we can look at say the movies that the user has not yet watched and recommend new movies to that user to watch you try to predict what else might be interesting to a user so that's the formalism of the recommender system problems in the next video we'll start to develop a learning algorithm to address installment in the last video we talked about the recommender system problem where for example you may have a set of movies and you may have a set of users we should prove has rated some subset of the movies that rated the movies one to five thousand zero to five stars and what we would like to do is locally its users and predict how they would have written other movies that have not yet rated in this video I'd like to talk about our first approach to building a recommender system this approach is called content-based recommendations here's our data set from before and just to remind you of a bit of notation I was using and you to denote the number of users and so that's equal to 4 and nm to denote the number of movies I have five movies so how do I predict what these missing values would be let's suppose that for each of these movies I have a set of features for them in particular let's say that which the movies I have two features which on which I'm going to denote X 1 and X 2 where X 1 measures the degree to which a movie is a romantic movie and X 2 measures the degree to which a movie is an action movie so if you take movie love that laughs you know it's 0.9 of rating on the romance skills of highly romantic movies a 0 on the action skill so almost no action in that movie romance forever so one point a lot of romance and 0.01 action well maybe there's a minor contraction that movie a little bit of action skipping one let's do a vs. karate maybe that is a zero romance rating no romance of all on that the plenty of action and you know start consciousness maybe again there's a tiny bit of romance in that movie but many action and then you have two puppies of love again maybe a romance movie with no astronaut so if we have teachers like these then each movie can be represented with a feature vectors let's take movie one so it's call these movies movies one two three four and five but my first movie love at last I have my two features 0.9 and zero and so these are features x1 and x2 and let's add an extra feature as usual which is Maria intercept term feature x0 is equal to 1 and so putting these together I would then have a feature x1 the superscript 1 denotes is the feature vector for my first movie and the spatial vector is equal to 1 the first one they're resistant to set term and then my two features 0.90 like so so the love and last I would have a feature vector x1 for the movie romance forever or may have a sub procedure back to x2 and so on and for social security I would have you know a different feature vector X superscript 9 also consistent with our urging of notation that we were using we're going to set n to be the number of features not counting this x0 deceptor until n is equal to 2 because we have two features x1 and x2 capturing the degree of romance and degree of action in each movie now in order to make predictions just one thing to do which is that we could treat predicting the ratings of each user as a separate linear regression problem so specifically let's say that for each user J we're going to learn your parameter vector theta J which would be an ass to be in this case more generally theta J would be our n plus 1 or n the number of features not confusing cetera and we're going to predict user J as rating movie I with just the inner product between yield parameter vector theta and the features X I so let's take a specific example let's take a user one so that was the Alice and Associates in what Alice will be some parameter vector theta one and our second user Bob will be associated with a different parameter vector theta two Carol reassociate to a different parameter vector theta three and gave a different printer nectar data form so let's say you want to make a prediction so what Alice will think of the movie two copies of love well that movie is going to have some parameter vector X 3 where we have that x3 is going to be equal to 1 which is fine intercept term and then 0.99 and then 0 and let's say for this example let's say that you know was somehow already gotten it parameter vector theta 1 so Alice will say later exactly how we come up with this parameter vector but let's just say for now that you know some unspecified learning algorithm has learned the parameter vector theta 1 and is equal to the 0 5 0 so our prediction for this entry is going to be equal to theta 1 that is Alice's parameter vector transpose X 3 that is the feature vector for the two puppies of love movie number 3 and so the inner product between the two vectors is going to be you know 5 times 0.99 which is equal to equal to 0.95 and so my prediction for this value over here is going to be four point nine five maybe that seems like a reasonable value if indeed this is my parameter vector theta one so all we're doing here is we're applying a different copy of essentially linear regression for an issued user and we're saying that what Alice does is Alice has some parameter vector theta one that she uses you know that we use to predict hook ratings as a function of how romantic and how action-packed it really is and evolving Karen gave each of them have a different linear function of the romantic nodes and action asorio romance and the degree of action in movie and that that's how we're going to predict their star ratings more formally here's how we can write down the problem our notation is that RJ is equal to 1 the usage as resolute VI and y IJ is the rating of that movie if that if that rating exists that is that that user has estimated that movie and on the previous slide we also defined these theta J which is a parameter whose user X I which is a feature vector for specific movie method each user and each movie we predict that rating as follows so let me introduce just temporarily introduce one extraverted notation MJ will use MJ to denote the number of users rated by movie J don't need this notation only for the slides now in order to learn the parameter vector for theta J well how can we do so this is basically a linear regression problem so what we can do is just choose a parameter vector theta J so that the predictive values here are as close as possible to the values that we observed in our training set and the values we observed in our data so let's write that down in order to learn the parameter vector theta J let's minimize over my parameter vector theta J of song and I want to sum over all movies that user J has rated so the vector sum over all values of AI that's a : r I J equals 1 so the way to read this information indexes this is summation over all the values of I so there are i j is equal to 1 so 3 summing over all the movies that user J has rated and then I'm going to compute theta J transpose X I so that's the prediction of user J's rating on movie I minus y IJ so that's actually a rating squared and then then just divide by the movies that user J has actually rated as divided by one over two mg and so this is just like the least-squares regression this is just like you know linear regression where we want to choose the parameter vector theta J to minimize this type of squared error term and if once we can also add in the regularization term such a plus lambda over 2 m and this is really 2 MJ because of that we have MJ examples right because if user J has rated that many movies the sort of ID without that many data points with which to fit the parameters theta J and then let me add in my usual regularization term here of theta J K squared as usual this sum this room k equals 1 to N so here theta J is going to be an N plus 1 dimensional vector where in our earlier example n was equal to 2 the more broadly more generally and is the number of features we have per movie and so as usual we don't regularize over theta 0 we don't worry right over the bias terms and sums from K equals 1 to N so if you minimize this as a function of theta J you get a good solution you get a pretty good estimate of the parameter vector theta J with which to make predictions for user J's movie ratings for recommender systems I'm going to change this notation a little bit so to simplify the subsequent map I'm actually to get rid of this term mg so that's just the constants right so I can delete it without changing the value of theta J to get out of this optimization so if you imagine taking this whole equation taking this whole expression the x MJ get rid of that constant and whether minimizes I should still get the same doubt energy as before so just repeat what we wrote on previous light here's our optimization objective in order to learn theta J which is the parameter for user J we're going to minimize over theta J of this optimization objective so this is our usual squared error term and then distance our regularization term now of course in building a recommender system we don't just want to learn parameters for a single user we want to go parameters for all of the all of my users so I have n subscript new users so I want to learn all of these parameters and so what I'm going to do is take this we're going to take this optimization objective and just adds an extra summation there so you know this expression here with the 1/2 on top of yes it's exactly the same as what we have on top except that now instead of just doing this for a specific users theta J I'm going to sum my objectives over all my users and then minimize this overall optimization objective minimizes overall cost function and when I minimize this as a function of theta 1 theta 2 up to theta n you I will get a separate parameter vector for each user and I didn't then use that to make predictions for all of my users but all of my n subscript new users so putting everything together this was our optimization objective on top and to give this in the name I'm just called as J of theta 1 dot dot theta and user J as usual is my optimization objective approach I'm trying to minimize next in order to actually do the minimization if you were to derive the gradient descent update these are the equations that you would get so you take theta J K and subtract from an alpha which is the learning rate times these terms over here on the right so we're slightly different cases for when K equals 0 and one case north of 0 because our regularization term here recognizes only the values of theta JK for 10 zero so we don't regularize data 0 so the slightly different updates for T equals 0 T not equal to 0 and this term will be here for example is just a partial derivative with respect to your parameter that of your optimization objective right and so you know this is just gradient descent but some and I've already computed the derivatives and plug them into here and if this and of these gradient descent update is look a lot like what we had from linear regression is because these are essentially the same as linear regression the only minor difference is that for linear regression you know we have these 1 over n terms are is really one of would have been 1 over m J but because earlier when we are deriving the optimization objective we got rid of this that's why we don't have this 1 over m term but otherwise is really some of my training examples of you know Bo ever times XK plus that regularization term Plus that term that regularization sort of contributes to the derivative and so if you're using gradient descent here's how you can minimize the cost function J to learn all the parameters and using these formulas for the derivatives if you want you can also plug them in to a more advanced optimization algorithm like conjugate gradients or l-bfgs or what-have-you and use that to try to minimize the cost function J as well so hopefully you now know how you can apply essentially a variation on linear regression in order to predict different movie ratings by different users this particular algorithm is called content-based recommendations or a content-based approach because we assumed that we have available to us features for the different movies and so we're features that capture what is the content of these movies that's how romantic is this movie how much absolutely and we're using features of the content of the movies to make our predictions but for many movies we don't actually have such features or maybe very difficult to get such features for all of our movies well for all of whatever items we're trying to sell and so in the next video we'll start to talk about an approach to recommender system that isn't content-based and does not assume that we have someone else giving us always these features for all of the movies in our data set in this video we'll talk about an approach to building a recommender system that's called collaborative filtering the algorithm they were going to talk about it has a very interesting property that it does what is called feature learning and by that I mean that this would be an algorithm they can sponsor learn for itself what each's to use here was the data set that we had and we have assumed that for each movie someone had come and told us how romantic that movie was and how much action there was in that movie but as you can imagine it can be very difficult and time-consuming and expensive to actually try to get someone to you know watch each movie and tell you how romantic relation patent is movie and often you want even more features and than just these tools and so where do you get these features from so let's change the problem of it and suppose that we have a data set where we do not know the values of these features so we're given a data set of movies and how the users rated them but we have no idea how romantic each movie is and we have no idea how action-packed each movie is so it replace all of these things with question marks but now let's make a slightly different assumption let's say that we've gone to each of our users and each of our users has told us how much they like romantic movies and how much they like action-packed movies so Alice has associated a state parameter vector theta 1 both theta 2 Carroll theta 3 days later for and let's say that we also use this let's say Alice tells us that she really likes romantic movies and so this is five there which is the multiplier associated x1 and let's say Alex tells us she really doesn't like action movies it's a little zero there and Bob tells us something similar so we have theta 2 over here whereas Carol tells us that she really likes action movies which is why there's a 5 there that's the multiplier associated with X to remember that also exhibit equals 1 and let's say that Carol you know tells us she doesn't like romantic movies and so on similarly okay so let's assume that somehow we can go to our users and each user J just tells us what is the value of theta J for them and so it basically specifies to us how much the alot of different types of movies if we can get these parameters theta for my users then it turns out that it becomes possible to try to infer what are the values of x1 and x2 for each movie let's look at example let's look at movie let's look at review 1 so that would be 1 has associated with in a feature vector x1 and you know this movie is called love and last or less ignore that let's pretend we don't know what does review summary so say you know the title of this movie all we know is that Alice loved this movie Bob loved this movie Carol and Dave hated this movie so what can you infer well we know from the feature vectors then Alice and Bob love romantic movies because they told it that it resides here whereas Carol and Dave we know that they hate romantic movies and that they love action movies so because those are the parameter vectors that user 3 at for Carol and DA gave us and so based on the fact that movie 1 is loved by Alice and Bob and hated by carol days we might reasonably conclude that you know this is probably romantic movie and is probably not much of an action movies this example is the law that mathematically simplified but what we're really asking is what feature vectors should x1 be so that theta 1 transpose x1 is approximately equal to five that's Alice's rating and theta 2 transpose x1 is also approximately equal to 5 and theta 3 transpose x1 is plus 1 equals 0 so this will be a careless rating and theta 4 transpose x1 is approximately equal to 0 and from this it looks like you know x1 equals 1 destined set terminal 1.0 0.0 that makes sense given what we know of Alice Bob Carol and Dave's preferences the movies in the way they rated this movie and so more generally we can go down this list and try to figure out what might be reasonable features for these other movies as well let's formalize this problem of learning the features exercise let's say that our users have given us their preferences so let's say that our users have come and told us these values for theta 1 to theta nu and we want to learn the feature vector X I for movie number I what we can do is therefore pose the following optimization problem so we want to sum over all the indices J for which we have a rating for movie I because we're trying to learn the features for movie either this is feature vector X is so and then what we want to do is minimize this squared error so we want to choose features X I so that you know the predictive value of how user J Ray's movie I will be similar will be not too far in the squared error sense of the actual value y IJ that we actually observe in the rating of user J on movie I so just summarize what this term does is it tries to choose features X I so that for all the users James that have rated that movie the algorithm also predicts a value for how that user will rate to that movie that is not too far in the squared error sense from the actual value that the user had made to that movie so that's the squared error term and as usual we can also add this sort of regularization term to prevent the features from becoming too big so this is how we would learn the features so one specific movie but what we want to do is learn all the features for all the movies and so what I'm going to do is add this extra summation here so I'm going to sum over all nm movies and subscript M movies and minimize this objective on top that summed over our movie and if you do that you end up with the following optimization problem and if you minimize this you have hopefully a reasonable set of features for all of your movies so putting everything together what we do we talked about in the previous video and the algorithm that we just talked about in this video in the previous video where we show was that you know if you have a set of movie ratings that you have the data of the are on J's and if you have the Y IJA and so you have the movie ratings then given features for your different movies we can learn these parameters data so if you need the features you can learn the parameters theta for your different users and what we showed earlier in this video is that if your users are willing to give you parameters then you can estimate features for the different movies so this is kind of a chicken and egg problem right which comes first you know do you want to if we get the Thetas you know the exodus it can if we have the XS can learn the status and when you can do in and then this actually works what you can do is in fact randomly deaths some value of the status now based on your initial random guess for the Thetas you can then go ahead and use the procedure that we just talked about in order to learn features for your different movies now given some initial set of features your movies you can then use you know this first method that we talked about the previous video to try to get an even better estimate for your parameters theta now these have a better setting of the parameters theta so your users we can use that to maybe get an even better set of features and so on you can sort of keep iterating going back and forth and optimizing theta X theta X theta X and this actually works and if you do this this will actually cause your algorithm to converge to a reasonable set of features for your movies and these small sets of parameters for your different users so this is a basic collaborative filtering algorithm this doesn't actually define your algorithm that we will use in the next video we're going to be able to improve on this algorithm and make it quite a bit more computationally efficient but hopefully this gives you a sense of how you can formulate a problem where you can simultaneously either in the parameters and simultaneously wear these features from the different movies and for this problem for the recommender system problem this is possible only because these user base multiple movies and hopefully each movie is rated by multiple users and so you can do this back and forth process IMX so to summarize in this video was seen an initial collaborative filtering algorithm the term collaborative filtering refers to the observation that when you run this out room with a large set of users what all of these users are effectively doing the first collaborative you're collaborating to get better movie ratings for everyone because with every user rating some subset of the movies every user is helping the algorithm a little bit to learn better features and then by helping you know by rating a few movies myself I will be hoping the system learn that the features and then these features can be used by the system to make better movie predictions for everyone else and so there's a sense of collaboration where every user is helping the system learn at the features sort of for the common good this collaborative filtering and in the next video what we're going to do is take the ideas that we've worked out and trying to develop an even better algorithm between slightly better technique for collaborative filtering in the last couple videos we talked about the ideas of how first if you're given each of the movies you can use that to learn parameter status with users and second if you're given parameters for the users you can use that to learn features in the movies in this video we'll take those ideas and put them together to come up with a collaborative filtering algorithm so one of the things we worked on earlier is that if you have teachers for the movies then you can solve this minimization problem to find the parameters theta for your users and then we also worked out that if you are given the parameters theta you can also use that estimate the features X and can do that by solving this minimization problem so one thing you could do is actually go back and forth either maybe randomly initialize parameters and then solve for theta solve X also theta solve for X but it turns out that this is more efficient algorithms it doesn't need to go back and forth between the excellence and the state but that can solve for theta and X simultaneously and here this what we're going to do is basically take both of these optimization objectives and put them into the same objective so I'm going to define a new optimization objective J which is a cost function there's a function of my features X and a function of my practice data as basically the two optimization objectives I had on top that put together so in order to explain this first I want to point out that this term over here this grant error term is the same as this squared error term and the summations look a little bit different but let's see what the summations are really doing the first summation is sum over all users J and then sum over all movies rated by that user right so this is really something over all pairs IJ that corresponds to a movie that was rated by user to sum over james's for every user sum of all the movies rated by that user this summation down here just does things in the opposite order this is for every movie I sum over all the useless J that have rated that movie and so you know these summations both of these such as summations over all pairs IJ for which R of I J is equal to 1 is just summing over you know all the user movie pairs for which you have a rating and so those two terms up there it's just exactly this first term not just written summation here explicitly where I'm just saying you know the sum of all pairs IJ such that are on J is equal to 1 and so what we're going to do is define a combined optimization objective that we want to minimize in order to solve simultaneously for X and theta and then the other terms in the optimization objective is our this which is a regularization in terms of theta and so came down here and the final piece is this term which is my optimization objective for the exes and that between this and this optimization objective J actually is an interesting property that if you were to hold the XS constant and just minimize a respect to the Thetas then you'd be solving exactly this problem whereas able to do the opposite if you were to hold the Thetas constant and minimize J only with respect to the axis then it becomes equivalent to this because either this term or this term is constant if you're minimizing over your respective X's or the other speculations so just an optimization objective that puts together your my cost functions in terms of X and in terms of theta and in order to come up with what's just one optimization problem what we're going to do is treat this cost function as a function of my features X and of mine user produce the parameters theta and just minimize this whole thing as a function of both the X's and a function of the faces and really the only difference between this and the older algorithm is that instead of going back and forth you know previously we talked about minimizing respect to theta the minimizing respect to X rays minimizing this legislature minimizing research X and so on in this new version instead of sequentially going between the two sets of parameters X and theta what we're going to do is just minimize with respect to both sets of parameters simultaneously finally one more detail is that when we're learning the features this way previously we have been using this convention that we have a feature x0 equals 1 that corresponds to an intercept term when we are using this sort of formalism where we're actually learning the features we're actually going to do a way with this convention and so the features we're going to learn X will be in RN whereas previously we had features X in RN plus 1 including intercept term by getting rid of x0 we now have just X in RN and so similarly because the parameters theta is missing dimension we now also have state there in RN because if there's no H 0 then there's no need for update parameter theta 0 as well and the reason we do away with this convention is because we're now learning all the features right so that means that there's no need to hard-code of the features is always equal to 1 because if the algorithm really wants a feature there's always equal 1 it can choose to learn one for itself so if the algorithm chooses it can set the feature x1 equals to 1 and so there's no need to hard-coded features or 0 on the algorithm now has effects abilities is just learning for yourself so putting your getting together here's our collaborative filtering algorithm first we're going to initialize X and theta to small random values and this is a local line neural network training where there will also initializing all the parameters of a neural networks small random values mix were then going to minimize the cost function using gradient descent or one of the year or one of the advanced optimization algorithms so if you take derivatives you find that the gradient descent update so like this and so you know this term here is the partial derivative of the cost function you're not gonna write down with respect to the future value X IJ and similarly you know this term here is also a partial derivative value of the cost function with respect to the parameters data that women and just as a reminder in this formula zombie no longer have this zero equals one and so we have that X is an RN and theta is an RN and this new formulism we're regularizing every one of our parameter states every one of our parameters X and there's no longer does no longer this special case theta zero which was regular rise differently or which was not regularized compared to with the parameters theta one down to stage of everything so there's now no longer a theta zero which is why the DS updates I did not break up the special case with T equals zero so in then use gradient descent to minimize the cost function J with respect to the features X and respective parameters data and finally given a user if the user has some parameters theta and if there's a movie with some sort of learn features X we would then predict that that movie will be differently star rating by that user of theta transpose J or justice others in then we're saying that with if user J has not yet rated movie I then what we do is predict that user J is going to rate movie I according to this theta J transpose X I so that's the collaborative filtering algorithm and if you implement an algorithm you actually get a pretty decent algorithm that will simultaneously learn good features for hopefully all the movies as well as learn parameters all reduces and hopefully give pretty good predictions for how different users will rate different movies that they have not yet rated in the last few videos we talked about a collaborative filtering algorithm in this video I want to say a little bit about the vectorization implementation of this algorithm and also talk a little bit about other things you can do with this algorithm for example one of the things you do is given one product can you find other products that are related to this so that if for example a user has recently be looking at one product on there other related problems that you could recommend to this user so let's see what we do about that what I'd like to do is work out an alternative way of writing out the predictions of the collaborative filtering algorithm to start here's our dataset with our five movies and what I'm going to do is take all the ratings by all the users and group them into a matrix so here we have five movies and four users and so this matrix Y is going to be a five by four matrix just you know taking all the elements all of this data including question marks and grouping them into this matrix and accord the elements of this matrix or the IJ element of this matrix and really what we were previously writing as Y superscript I comma genes they're maintained given to the eyes by user J given this matrix Y of all the ratings that we have there's an alternative way of writing out all the predicted ratings of the algorithm and in particular if you look at what a certain user predicts on a certain movie what user J predicts on movie I is given by this formula and so if you have a matrix of the predicted ratings what you would have is the following matrix ready I comma J entry so this corresponds to the rating that we predict user J will give to movie I is exactly equal to that theater J transpose X I and so you know this is a matrix where right this first element the one one element is the predicted rating of user 1 on movie 1 and this element this is the 1 2 element is their predicted rating of user - on Ruby 1 and so on and this is the predicted rating of user 1 on the the last movie and if you want you know this rating is what would have predicted for this value and this rating is what were the predictors of that value and so on now given this matrix of predicted rating there is then a simpler or vectorized way of writing results in particular if I define a matrix X and this is going to be just like the matrix we had earlier for linear regression to me so X 1 transpose X 2 transpose down to X of M M transpose so I'm going to take all the features for like movies and stack them in rows so if you think of each movie as one in an apple and snack all of the features the different movies and rules and if we also define a matrix capital theta and what I'm going to do is take each of the per user parameter vectors and stack them in rows like those so that's theta one which is the parameter vector for the first user and yes theta 2 and so must at them in rows like this to define a matrix capital theta oh and so has n you parameter vectors are stacked in rows like this now given this definition for the matrix X and this definition for the matrix theta in order to have a vectorized way of computing the matrix of all those operations you can just compute x times the matrix theta transpose and that gives you a vectorized way of computing this matrix over here to give the collaborative filtering algorithm that you've been using another name the algorithm that we're using is also called low rank matrix factorization and so if you hear people talk about low rank matrix factorization that's essentially exactly the algorithm that we'll be talking about and this term comes from the property that this matrix x times theta transpose has a mathematical property in linear algebra called that this is a low rank matrix and so that's what gives rise to this being low rank matrix factorization Zanden algorithms because of this low-rent copy of there's a matrix X theta transpose in case you don't know what low rank means in case you don't know what a low rank matrix is don't worry about it you really don't need to know that in order to use this algorithm but if you're an expert in linear algebra that's what gives this algorithm this other name of low rank matrix factorization finally having run the collaborative filtering algorithm here's something else that you can do which is use D learn features in order to find related movies specifically for each problem I really finish Ruby I will learn a feature vector X I so you know when you learn the seller features you don't really know in advance what the different features are going to be but if you run the algorithm and probably the features will tend to capture what are the important aspects of these different movies or different problems or what-have-you one of the important aspects that cause some users or like certain movies and cause some users to like in a different set of movies and settle maybe end up learning teacher you know where x1 equals romance if two equals action similar to an earlier video and maybe you learn a different teacher x3 which is the degree to which this is a comedy learn some teacher x4 which is you know or some other things and you have n features all together and after you've learned features is actually often pretty difficult to go in to the learn features and come up with a human understandable interpretation of what these species really are but in practice the features you know even though these features can be hard to visualize can be hard to figure out just with these features are usually it will learn features that are very meaningful for capturing whatever are the most important or the most salient properties of a movie that causes uses the like or dislike it and so now let's say we want to address the following problem so you have some specific movie I and you want to find other movies J that are related to that movie and so well why would you want to do this right maybe you have a user this browsing movies and they're currently watching movie J then what's the reason of a movie to recommend to them to watch after the wgj or if someone's recently purchased movie J well what's a different movie that would be reasonable to recommend to them since for them to consider purchasing so now we have learned these P vectors this gives us a very convenient way to measure how similar two movies are in particular movie I has a feature vector X I and so if you can find a different movie J so that the distance between X I XJ is small then this is a pretty strong indication that in a movies Jay and I are somehow similar at least in the sense that some of their lives movie I am making more likely to like movie J as well so just a recap if you your user is looking at some movie I and if you want to find the five most similar movies to that movie in order to recommend five movies to them what you do is find five movies J what's the smallest distance between the features between them of these different movies and this could give you a few different movies to recommend to your user so with that hopefully you now know how to use a vectorized implementation to compute all the predicted ratings with all the users on all the movies and also how to do things when use those features define what might be movie is the war might be problems level a Tunisia but now you've seen all of the main pieces of the recommender system algorithm or D collaborative filtering algorithm in this video I want to just share one loss implementational detail namely mean normalization which can sometimes just make the algorithm work a little bit better to motivate the idea of mean normalization let's consider an example of where there's a user that has not read in any movies so in addition to our four users Alice Bob Carol and Dave as in a fifth user Eve who has invaded any let's see what's out clavata filtering algorithm will do on this user let's say that n is equal to two and so we're going to learn two features and we're going to have to learn a parameter vector theta five which is going to be an R to remember this now vectors in RN not are n plus 1 when learn prime factors they define for our user number five needs so if we look in the first term in this optimization objective well the user Eve hasn't raised in any movies and so you know there are no movies there are no movies for which R IJ is equal to one for the user Eve and so this first term plays no role at all in determining data fine because there are no movies that rated and so the only term that affects theta v is this term and so we're saying that we want to choose vector theta v so that the last regularization term is as small as possible in other words we want to minimize this sum lambda over 2 theta v subscript 1 squared plus theta v subscript 2 squared so that's the component of the regularization term that corresponds to user 5 and of course if your goal is to minimize this term then what you're going to end up with it is just say the size equals 0 0 because the regularization term is encouraging us to set parameters close to 0 and if there is no data to try to pull the parameters away from 0 because this first service it doesn't affect the state of our boost and that will stay with R equals the vector of all zeros and so when we go to predict how users file rate and movie we have that theta v transpose X I for any ID that's just going to be equal to 0 and so because theta v is 0 for any value of x the profit is going to equal zero and we're going to have therefore is that women predicts that Eve is going to rate every single movie with zero stars but this doesn't seem very useful does it I mean if you look at the different movies you know Buffett laws this first movie a couple people rated it five stars and four you know even the deer for Escalante some one way to the theis file so some people do like some movies it seems kind of not useful to just predict that Eve is going to bring everything zero stars and in fact if we're predicting that neither is going to rate everything zero stars we also don't have any good way of recommending in your movies to her because you know all of these movies are getting exactly the same predicted rating for you so that no one movie with a higher predicted rating that we could recommend oh so that's all very good the idea of mean normalization will let us fix this problem so here's how it works as before let me group all of my movie ratings into this matrix one just take all of these ratings and group them into this matrix wine and just call them over here of all question marks corresponds to these not having read to any movies now the phone in organization what I'm going to do is compute the average rating that each movie obtains I'm going to spoil that in a vector than calm you so the first movie got to five star and to zero star rating so the average of that is a two point five star rating your second movie and an average of two point five star sensor one then the final movie at zero zero five zero and the average of zero zero five zero that averages out to an average at one point two five rating and then what I'm going to do is look at all the movie ratings and I'm going to subtract off the mean rating so this first element five I'm going to subtract off the two point five and register two point five and the settlement element fives have had topic two point five two two point five and then be a zero zeros subtract off two point five we get minus two point five minus two point five in other words what I'm going to do is take my matrix that we be rating this wide matrix and subtract from each row the average rating for that movie so what I'm doing is I'm just normalizing each movie to have an average rating of zero and so just one last example if you look at this last row the zero zero five zero we're going to subtract one point two five and so I end up with these values of this year okay so now and of course the question marks say a question mark and so each movie in this new matrix Y has an average rating at zero what I'm going to do then is take this set of ratings and use it with my collaborative filtering algorithm so I'm going to pretend that this was the data that I had gotten for my users and pretend that these are the actual ratings I got them from the users and I'm going to use this as my dataset with which to learn my parameters theta J and my features X ein from these mean normalized movie ratings when I want to make predictions of movie ratings what I'm going to do is the following for a user J on Ruby I I'm going to predict theta J transpose X i where X and theta are the parameters of learn from this me normalize data set but because on the data set I had subtracted off the means in order to make prediction on Ruby I I'm going to need to add back in the mean and so the pad back in mu I and sewed asking to neural prediction where my training data are subtracted up all the means and so when I'm a prediction they need to add back in these means new eyes will be I and so specifically for user five which is Eve the same argument as the previous five score points in the sense that if has not greater any movies and so the learn parameter but user five is still going to be equal to zero zero and and so what we're going to get then is that on a particular movie I we're going to for eve theta v transpose x i plus add back in mu I and so this first component is to equal 0 if X is a theta v is equal to 0 and so on movie our we're going to end up predicting mu I and this is actually make sense and is it on Rudy one we're going to predict me free until 2.5 on Ruby 2 looking to predict of race and to point solace on movies reprobate is greater than 2 and so on and this actually makes sense because it says that if Eve hasn't rated any movies we just don't know anything about the New Jersey we've what we're going to do is just predict for you sugar movies well let the average rating that does really not find the Diaz and the sides in this video we talked about me normalization where we normalize each row of the matrix Y to be that mean 0 in case you have some movies with no rating so this analogous to a user who hasn't written anything but in case you have some movies with no ratings you can also play with their version to the algorithm where you are normalized to different columns to have u 0 instead of normalizing the rows that mean 0 although that's maybe less important because if you really have a movie with no ratings maybe you just shouldn't recommend that movie to anyone anyway and so no taking taking care of the kids of a user who has a great than anything might be more important at taking care of a case of a movie that hasn't gotten a single rating so to summarize that's how you can do mean normalization as a sort of pre-processing except for collaborative filtering depending on your data set this might sometimes nature implementation work just a little bit better