9.3 Collaborative Filtering | Collaborative filtering algorithm-- [Machine Learning| Andrew Ng]
 In the last video, you saw how if you have features for each movie, such as features X1 and X2, they tell you how much is this a romance movie and how much is this an action movie. Then you could use basically linear regression to learn to predict movie ratings. But what if you don't have those features, X1 and X2? Let's take a look at how you can learn or come up with those features, X1 and X2, from the data. So here's the data that we had before. But what if instead of having these numbers for X1 and X2, we didn't know in advance what the values of the features X1 and X2 are. So I'm going to replace them with question marks over here. Now just for the purposes of illustration, let's say we had somehow already learned parameters for the four users. So let's say that we learned parameters W1 equals 5 and 0 and B1 equals 0 for user 1. W2 is also 5, 0. B2 is 0. W3 is 0, 5. B3 is 0. And for user 4, W4 is also 0, 5 and B4 is equal to 0. We'll worry later about how we might have come up with these parameters W and B, but let's say we have them already. And as a reminder, to predict user j's rating on movie i, we're going to use wj.product the features of x i plus bj. So to simplify this example, all the values of b are actually equal to 0. So just to reduce a little bit of writing, I'm going to ignore b for the rest of this example. Let's take a look at how we can try to guess what might be reasonable features for movie 1. If these are the parameters you have on the left, then given that Alice rated movie 1 5, we should have that W1.x1 should be about equal to 5. And W2.x2 should also be about equal to 5 because Bob rated it 5. W3.x1 should be close to 0 and W4.x1 should be close to 0 as well. So the question is, given these values for W that we have up here, what choice for x1 would cause these values to be right? Well one possible choice would be if the features for that first movie were 1 0, in which case W1.x1 would equal to 5, W2.x1 would equal to 5, and similarly W3 or W4.product with this feature vector x1 would be equal to 0. So what we have is that if you have the parameters for all four users here, and if you have four ratings in this example that you want to try to match, you can take a reasonable guess at what is the feature vector x1 for movie 1 that would make good predictions for these four ratings up on top. And similarly, if you have these parameter vectors, you can also try to come up with a feature vector x2 for the second movie, a feature vector x3 for the third movie, and so on to try to make the algorithms predictions on these additional movies close to what was actually the ratings given by the users. Let's come up with a cost function for actually learning the values of x1 and x2. And by the way, notice that this works only because we have parameters for four users. That's what allows us to try to guess appropriate features x1. This is why in a typical linear regression application, if you are just a single user, you don't actually have enough information to figure out what would be the features x1 and x2, which is why in the linear regression context that you saw in course 1, you can't come up with features x1 and x2 from scratch. But in collective filtering, it is because you have ratings from multiple users of the same item with the same movie. That's what makes it possible to try to guess what are possible values for these features. So given w1, b1, w2, b2, and so on through w, n, u, b, n, u for the n subscript u users, if you want to learn the features xi for a specific movie i, here's a cost function we could use, which is that I'm going to want to minimize squared error as usual. So if the predicted rating by user j on movie i is given by this, let's take the squared difference from the actual movie rating yij. And as before, let's sum over all the users j, but this will be a sum over all values of j where rij is equal to 1. And I'll add a one half there as usual. And so if I define this as a cost function for xi, then if we minimize this as a function of xi, you'd be choosing the features xi for movie i so that for all the users j that had rated movie i, we would try to minimize the squared difference between what your choice of features xi results in in terms of the predicted movie rating minus the actual movie rating that the user had given it. And finally, if we want to add a regularization term, we add the usual plus lambda over 2, k equals 1 through n, where n is usual as the number of features of xi k squared. Lastly, to learn all the features x1 through xnm because we have nm movies, we can take this cost function on top and sum it over all the movies, so sum from i equals 1 through the number of movies, and then just take this term from above and this becomes a cost function for learning the features for all of the movies in the data set. And so if you have parameters w and b for all the users, then minimizing this cost function as a function of x1 through xnm using gradient descent or some other algorithm, this will actually allow you to take a pretty good guess at learning good features for the movies. And this is pretty remarkable. For most machine learning applications, the features had to be externally given, but in this algorithm, we can actually learn the features for a given movie. But in what we've done so far in this video, we assume you had those parameters w and b for the different users. Where do you get those parameters from? Well let's put together the algorithm from the last video for learning w and b and what we just talked about in this video for learning x, and that will give us our collaborative filtering algorithm. This is the cost function for learning the features. This is what we had derived on the last slide. Now it turns out that if we put these two together, this term here is exactly the same as this term here. Notice that sum over j of all values of i is that rij equals 1 is the same as summing over all values of i with all j where rij is equal to 1. This summation is just summing over all user movie pairs where there is a rating. And so what I'm going to do is put these two cost functions together and have this where I'm just writing out the summation more explicitly as summing over all pairs i and j where we do have a rating of the usual squared cost function. And then let me take the regularization term from learning the parameters w and b and put that here and take the regularization term from learning the features x and put them here and this ends up being our overall cost function for learning w, b, and x. And it turns out that if you minimize this cost function as a function of w and b as well as x, then this algorithm actually works. Here's what I mean. If we had three users and two movies and if you have ratings for these four movies but not those two, over here it does is it sums over all the users and for user one, it has the term the cost function for this for user two, it has terms and cost function for these for user three, it has a term and cost function for this. So we're summing over users first and then having one term for each movie where there is a rating. But an alternative way to carry out this summation is to first look at movie one, that's what this summation here does, and then to include all the users that rated movie one and then look at movie two and have a term for all the users that had rated movie two. And you see that in both cases we're just summing over these four pairs where the user had rated the corresponding movie. So that's why this summation on top and this summation here, there are two ways of summing over all of the pairs where the user had rated the movie. So how do you minimize this cost function as a function of W, B and X? One thing you could do is to use gradient descent. So in course one when we learned about linear regression, this is the gradient descent algorithm you had seen where we had a cost function J which is a function of the parameters W and B and we'd apply gradient descent as follows. With collaborative filtering, the cost function isn't a function of just W and B, it's now a function of W, B and X. And I'm using W and B here to denote the parameters for all of the users and X here just informally to denote the features for all of the movies. But if you're able to take partial derivatives with respect to the different parameters, you can then continue to update the parameters as follows. So now we need to optimize this with respect to X as well. So we also will want to update each of these parameters X using gradient descent as follows. And it turns out that if you do this, then you actually find pretty good values of W and B as well as X. And in this formulation of the problem, the parameters are W and B and X is also a parameter. And then finally to learn the values of X, we also will update X as X minus the partial derivative with respect to X of the cost WBX. I'm using the notation here a little bit informally and not keeping very careful track of this superstrips and subscripts. But the key takeaway I hope you have from this is that the parameters of this model are W and B and X now is also a parameter, which is why we minimize the cost function as a function of all three of these sets of parameters W and B as well as X. So the algorithm we just arrived is called collaborative filtering. And the name collaborative filtering refers to the sense that because multiple users have rated the same movie kind of collaboratively, given your sense of what this movie may be like that allows you to guess what are appropriate features for that movie. And this in turn allows you to predict how other users that haven't yet rated that same movie may decide to rate it in the future. So this collaborative filtering is this gathering of data from multiple users, this collaboration between users to help you predict ratings for even other users in the future. So far, our problem formulation has used movie ratings from one to five stars or from zero to five stars. A very common use case of recommender systems is when you have binary labels such as the user favorites or like or interact with an item. In the next video, let's take a look at the generalization of the model you've seen so far to binary labels. Let's go see that in the next video.
[{"start": 0.0, "end": 7.44, "text": " In the last video, you saw how if you have features for each movie, such as features"}, {"start": 7.44, "end": 12.88, "text": " X1 and X2, they tell you how much is this a romance movie and how much is this an action"}, {"start": 12.88, "end": 13.88, "text": " movie."}, {"start": 13.88, "end": 18.92, "text": " Then you could use basically linear regression to learn to predict movie ratings."}, {"start": 18.92, "end": 22.32, "text": " But what if you don't have those features, X1 and X2?"}, {"start": 22.32, "end": 27.76, "text": " Let's take a look at how you can learn or come up with those features, X1 and X2, from"}, {"start": 27.76, "end": 28.76, "text": " the data."}, {"start": 28.76, "end": 31.880000000000003, "text": " So here's the data that we had before."}, {"start": 31.880000000000003, "end": 38.64, "text": " But what if instead of having these numbers for X1 and X2, we didn't know in advance what"}, {"start": 38.64, "end": 41.160000000000004, "text": " the values of the features X1 and X2 are."}, {"start": 41.160000000000004, "end": 45.0, "text": " So I'm going to replace them with question marks over here."}, {"start": 45.0, "end": 52.040000000000006, "text": " Now just for the purposes of illustration, let's say we had somehow already learned parameters"}, {"start": 52.040000000000006, "end": 53.96, "text": " for the four users."}, {"start": 53.96, "end": 61.120000000000005, "text": " So let's say that we learned parameters W1 equals 5 and 0 and B1 equals 0 for user 1."}, {"start": 61.120000000000005, "end": 64.24, "text": " W2 is also 5, 0."}, {"start": 64.24, "end": 66.52, "text": " B2 is 0."}, {"start": 66.52, "end": 69.76, "text": " W3 is 0, 5."}, {"start": 69.76, "end": 72.84, "text": " B3 is 0."}, {"start": 72.84, "end": 78.64, "text": " And for user 4, W4 is also 0, 5 and B4 is equal to 0."}, {"start": 78.64, "end": 83.32, "text": " We'll worry later about how we might have come up with these parameters W and B, but"}, {"start": 83.32, "end": 86.67999999999999, "text": " let's say we have them already."}, {"start": 86.67999999999999, "end": 96.83999999999999, "text": " And as a reminder, to predict user j's rating on movie i, we're going to use wj.product"}, {"start": 96.83999999999999, "end": 102.0, "text": " the features of x i plus bj."}, {"start": 102.0, "end": 106.82, "text": " So to simplify this example, all the values of b are actually equal to 0."}, {"start": 106.82, "end": 110.8, "text": " So just to reduce a little bit of writing, I'm going to ignore b for the rest of this"}, {"start": 110.8, "end": 111.8, "text": " example."}, {"start": 111.8, "end": 118.08, "text": " Let's take a look at how we can try to guess what might be reasonable features for movie"}, {"start": 118.08, "end": 119.36, "text": " 1."}, {"start": 119.36, "end": 125.32, "text": " If these are the parameters you have on the left, then given that Alice rated movie 1"}, {"start": 125.32, "end": 133.4, "text": " 5, we should have that W1.x1 should be about equal to 5."}, {"start": 133.4, "end": 140.56, "text": " And W2.x2 should also be about equal to 5 because Bob rated it 5."}, {"start": 140.56, "end": 149.28, "text": " W3.x1 should be close to 0 and W4.x1 should be close to 0 as well."}, {"start": 149.28, "end": 158.32, "text": " So the question is, given these values for W that we have up here, what choice for x1"}, {"start": 158.32, "end": 164.96, "text": " would cause these values to be right?"}, {"start": 164.96, "end": 171.24, "text": " Well one possible choice would be if the features for that first movie were 1 0, in which case"}, {"start": 171.24, "end": 184.32, "text": " W1.x1 would equal to 5, W2.x1 would equal to 5, and similarly W3 or W4.product with"}, {"start": 184.32, "end": 188.34, "text": " this feature vector x1 would be equal to 0."}, {"start": 188.34, "end": 194.92000000000002, "text": " So what we have is that if you have the parameters for all four users here, and if you have four"}, {"start": 194.92, "end": 200.55999999999997, "text": " ratings in this example that you want to try to match, you can take a reasonable guess"}, {"start": 200.55999999999997, "end": 207.88, "text": " at what is the feature vector x1 for movie 1 that would make good predictions for these"}, {"start": 207.88, "end": 210.39999999999998, "text": " four ratings up on top."}, {"start": 210.39999999999998, "end": 217.16, "text": " And similarly, if you have these parameter vectors, you can also try to come up with"}, {"start": 217.16, "end": 223.88, "text": " a feature vector x2 for the second movie, a feature vector x3 for the third movie, and"}, {"start": 223.88, "end": 233.84, "text": " so on to try to make the algorithms predictions on these additional movies close to what was"}, {"start": 233.84, "end": 237.24, "text": " actually the ratings given by the users."}, {"start": 237.24, "end": 244.88, "text": " Let's come up with a cost function for actually learning the values of x1 and x2."}, {"start": 244.88, "end": 251.78, "text": " And by the way, notice that this works only because we have parameters for four users."}, {"start": 251.78, "end": 257.08, "text": " That's what allows us to try to guess appropriate features x1."}, {"start": 257.08, "end": 262.1, "text": " This is why in a typical linear regression application, if you are just a single user,"}, {"start": 262.1, "end": 266.2, "text": " you don't actually have enough information to figure out what would be the features x1"}, {"start": 266.2, "end": 272.94, "text": " and x2, which is why in the linear regression context that you saw in course 1, you can't"}, {"start": 272.94, "end": 277.36, "text": " come up with features x1 and x2 from scratch."}, {"start": 277.36, "end": 282.32, "text": " But in collective filtering, it is because you have ratings from multiple users of the"}, {"start": 282.32, "end": 284.68, "text": " same item with the same movie."}, {"start": 284.68, "end": 290.04, "text": " That's what makes it possible to try to guess what are possible values for these features."}, {"start": 290.04, "end": 299.96000000000004, "text": " So given w1, b1, w2, b2, and so on through w, n, u, b, n, u for the n subscript u users,"}, {"start": 299.96000000000004, "end": 306.2, "text": " if you want to learn the features xi for a specific movie i, here's a cost function we"}, {"start": 306.2, "end": 314.46, "text": " could use, which is that I'm going to want to minimize squared error as usual."}, {"start": 314.46, "end": 324.18, "text": " So if the predicted rating by user j on movie i is given by this, let's take the squared"}, {"start": 324.18, "end": 329.8, "text": " difference from the actual movie rating yij."}, {"start": 329.8, "end": 337.2, "text": " And as before, let's sum over all the users j, but this will be a sum over all values"}, {"start": 337.2, "end": 342.44, "text": " of j where rij is equal to 1."}, {"start": 342.44, "end": 344.54, "text": " And I'll add a one half there as usual."}, {"start": 344.54, "end": 352.68, "text": " And so if I define this as a cost function for xi, then if we minimize this as a function"}, {"start": 352.68, "end": 361.32, "text": " of xi, you'd be choosing the features xi for movie i so that for all the users j that had"}, {"start": 361.32, "end": 368.40000000000003, "text": " rated movie i, we would try to minimize the squared difference between what your choice"}, {"start": 368.40000000000003, "end": 374.96000000000004, "text": " of features xi results in in terms of the predicted movie rating minus the actual movie"}, {"start": 374.96000000000004, "end": 377.2, "text": " rating that the user had given it."}, {"start": 377.2, "end": 384.0, "text": " And finally, if we want to add a regularization term, we add the usual plus lambda over 2,"}, {"start": 384.0, "end": 391.32, "text": " k equals 1 through n, where n is usual as the number of features of xi k squared."}, {"start": 391.32, "end": 400.15999999999997, "text": " Lastly, to learn all the features x1 through xnm because we have nm movies, we can take"}, {"start": 400.16, "end": 407.64000000000004, "text": " this cost function on top and sum it over all the movies, so sum from i equals 1 through"}, {"start": 407.64000000000004, "end": 416.76000000000005, "text": " the number of movies, and then just take this term from above and this becomes a cost function"}, {"start": 416.76000000000005, "end": 422.82000000000005, "text": " for learning the features for all of the movies in the data set."}, {"start": 422.82, "end": 431.0, "text": " And so if you have parameters w and b for all the users, then minimizing this cost function"}, {"start": 431.0, "end": 437.08, "text": " as a function of x1 through xnm using gradient descent or some other algorithm, this will"}, {"start": 437.08, "end": 442.92, "text": " actually allow you to take a pretty good guess at learning good features for the movies."}, {"start": 442.92, "end": 445.2, "text": " And this is pretty remarkable."}, {"start": 445.2, "end": 451.15999999999997, "text": " For most machine learning applications, the features had to be externally given, but in"}, {"start": 451.16, "end": 455.84000000000003, "text": " this algorithm, we can actually learn the features for a given movie."}, {"start": 455.84000000000003, "end": 460.92, "text": " But in what we've done so far in this video, we assume you had those parameters w and b"}, {"start": 460.92, "end": 462.68, "text": " for the different users."}, {"start": 462.68, "end": 465.24, "text": " Where do you get those parameters from?"}, {"start": 465.24, "end": 469.88, "text": " Well let's put together the algorithm from the last video for learning w and b and what"}, {"start": 469.88, "end": 475.28000000000003, "text": " we just talked about in this video for learning x, and that will give us our collaborative"}, {"start": 475.28000000000003, "end": 477.8, "text": " filtering algorithm."}, {"start": 477.8, "end": 481.44, "text": " This is the cost function for learning the features."}, {"start": 481.44, "end": 484.84000000000003, "text": " This is what we had derived on the last slide."}, {"start": 484.84000000000003, "end": 493.16, "text": " Now it turns out that if we put these two together, this term here is exactly the same"}, {"start": 493.16, "end": 495.46000000000004, "text": " as this term here."}, {"start": 495.46000000000004, "end": 502.14, "text": " Notice that sum over j of all values of i is that rij equals 1 is the same as summing"}, {"start": 502.14, "end": 508.08, "text": " over all values of i with all j where rij is equal to 1."}, {"start": 508.08, "end": 514.02, "text": " This summation is just summing over all user movie pairs where there is a rating."}, {"start": 514.02, "end": 522.92, "text": " And so what I'm going to do is put these two cost functions together and have this where"}, {"start": 522.92, "end": 530.2, "text": " I'm just writing out the summation more explicitly as summing over all pairs i and j where we"}, {"start": 530.2, "end": 535.1600000000001, "text": " do have a rating of the usual squared cost function."}, {"start": 535.1600000000001, "end": 543.08, "text": " And then let me take the regularization term from learning the parameters w and b and put"}, {"start": 543.08, "end": 549.2800000000001, "text": " that here and take the regularization term from learning the features x and put them"}, {"start": 549.2800000000001, "end": 559.0400000000001, "text": " here and this ends up being our overall cost function for learning w, b, and x."}, {"start": 559.04, "end": 564.48, "text": " And it turns out that if you minimize this cost function as a function of w and b as"}, {"start": 564.48, "end": 568.52, "text": " well as x, then this algorithm actually works."}, {"start": 568.52, "end": 569.52, "text": " Here's what I mean."}, {"start": 569.52, "end": 578.12, "text": " If we had three users and two movies and if you have ratings for these four movies but"}, {"start": 578.12, "end": 584.52, "text": " not those two, over here it does is it sums over all the users and for user one, it has"}, {"start": 584.52, "end": 589.04, "text": " the term the cost function for this for user two, it has terms and cost function for these"}, {"start": 589.04, "end": 591.36, "text": " for user three, it has a term and cost function for this."}, {"start": 591.36, "end": 599.16, "text": " So we're summing over users first and then having one term for each movie where there"}, {"start": 599.16, "end": 600.16, "text": " is a rating."}, {"start": 600.16, "end": 605.88, "text": " But an alternative way to carry out this summation is to first look at movie one, that's what"}, {"start": 605.88, "end": 612.24, "text": " this summation here does, and then to include all the users that rated movie one and then"}, {"start": 612.24, "end": 619.08, "text": " look at movie two and have a term for all the users that had rated movie two."}, {"start": 619.08, "end": 626.2, "text": " And you see that in both cases we're just summing over these four pairs where the user"}, {"start": 626.2, "end": 628.96, "text": " had rated the corresponding movie."}, {"start": 628.96, "end": 633.8, "text": " So that's why this summation on top and this summation here, there are two ways of summing"}, {"start": 633.8, "end": 638.5600000000001, "text": " over all of the pairs where the user had rated the movie."}, {"start": 638.56, "end": 643.8, "text": " So how do you minimize this cost function as a function of W, B and X?"}, {"start": 643.8, "end": 648.04, "text": " One thing you could do is to use gradient descent."}, {"start": 648.04, "end": 655.1999999999999, "text": " So in course one when we learned about linear regression, this is the gradient descent algorithm"}, {"start": 655.1999999999999, "end": 660.28, "text": " you had seen where we had a cost function J which is a function of the parameters W"}, {"start": 660.28, "end": 663.56, "text": " and B and we'd apply gradient descent as follows."}, {"start": 663.56, "end": 669.88, "text": " With collaborative filtering, the cost function isn't a function of just W and B, it's now"}, {"start": 669.88, "end": 673.64, "text": " a function of W, B and X."}, {"start": 673.64, "end": 679.4, "text": " And I'm using W and B here to denote the parameters for all of the users and X here just informally"}, {"start": 679.4, "end": 682.28, "text": " to denote the features for all of the movies."}, {"start": 682.28, "end": 687.5999999999999, "text": " But if you're able to take partial derivatives with respect to the different parameters,"}, {"start": 687.5999999999999, "end": 692.56, "text": " you can then continue to update the parameters as follows."}, {"start": 692.56, "end": 695.9599999999999, "text": " So now we need to optimize this with respect to X as well."}, {"start": 695.9599999999999, "end": 704.76, "text": " So we also will want to update each of these parameters X using gradient descent as follows."}, {"start": 704.76, "end": 712.0, "text": " And it turns out that if you do this, then you actually find pretty good values of W"}, {"start": 712.0, "end": 714.4799999999999, "text": " and B as well as X."}, {"start": 714.48, "end": 724.96, "text": " And in this formulation of the problem, the parameters are W and B and X is also a parameter."}, {"start": 724.96, "end": 733.2, "text": " And then finally to learn the values of X, we also will update X as X minus the partial"}, {"start": 733.2, "end": 739.64, "text": " derivative with respect to X of the cost WBX."}, {"start": 739.64, "end": 744.44, "text": " I'm using the notation here a little bit informally and not keeping very careful track of this"}, {"start": 744.44, "end": 746.48, "text": " superstrips and subscripts."}, {"start": 746.48, "end": 751.6400000000001, "text": " But the key takeaway I hope you have from this is that the parameters of this model"}, {"start": 751.6400000000001, "end": 759.32, "text": " are W and B and X now is also a parameter, which is why we minimize the cost function"}, {"start": 759.32, "end": 765.6400000000001, "text": " as a function of all three of these sets of parameters W and B as well as X."}, {"start": 765.6400000000001, "end": 770.44, "text": " So the algorithm we just arrived is called collaborative filtering."}, {"start": 770.44, "end": 776.12, "text": " And the name collaborative filtering refers to the sense that because multiple users have"}, {"start": 776.12, "end": 781.96, "text": " rated the same movie kind of collaboratively, given your sense of what this movie may be"}, {"start": 781.96, "end": 787.3000000000001, "text": " like that allows you to guess what are appropriate features for that movie."}, {"start": 787.3000000000001, "end": 792.5600000000001, "text": " And this in turn allows you to predict how other users that haven't yet rated that same"}, {"start": 792.5600000000001, "end": 796.22, "text": " movie may decide to rate it in the future."}, {"start": 796.22, "end": 803.02, "text": " So this collaborative filtering is this gathering of data from multiple users, this collaboration"}, {"start": 803.02, "end": 809.72, "text": " between users to help you predict ratings for even other users in the future."}, {"start": 809.72, "end": 815.52, "text": " So far, our problem formulation has used movie ratings from one to five stars or from zero"}, {"start": 815.52, "end": 817.32, "text": " to five stars."}, {"start": 817.32, "end": 823.0, "text": " A very common use case of recommender systems is when you have binary labels such as the"}, {"start": 823.0, "end": 827.36, "text": " user favorites or like or interact with an item."}, {"start": 827.36, "end": 831.32, "text": " In the next video, let's take a look at the generalization of the model you've seen so"}, {"start": 831.32, "end": 833.8, "text": " far to binary labels."}, {"start": 833.8, "end": 854.0, "text": " Let's go see that in the next video."}]