9.10 Advanced implementation | Recommending from a large catalogue -- [ML |Andrew Ng]
 Today's recommended systems will sometimes need to pick a handful of items to recommend from a catalog of thousands or millions or tens of millions or even more items. How do you do this efficiently computationally? Let's take a look. Here's the neural network we've been using to make predictions about how a user might rate an item. Today, a large movie streaming site may have thousands of movies or a system that is trying to decide what ad to show may have a catalog of millions of ads to choose from or a music streaming site may have tens of millions of songs to choose from and large online shopping sites can have millions or even tens of millions of products to choose from. When a user shows up on your website, they have some feature XU, but if you need to take thousands or millions of items to feed through this neural network in order to compute the inner product to figure out which products you should recommend, then having to run neural network inference thousands or millions of times every time a user shows up on your website becomes computationally infeasible. Many large scale recommender systems are implemented as two steps, which are called the retrieval and ranking steps. The idea is during the retrieval step will generate a large list of plausible item candidates that tries to cover a lot of possible things you might recommend to the user. And it's okay during the retrieval step if you include a lot of items that the user is not likely to like and then during the ranking step will fine tune and pick the best items to recommend to the user. So here's an example. During the retrieval step, we might do something like for each of the last 10 movies that the user has watched, find the 10 most similar movies. So this means for example, if a user has watched the movie I with vector v i m, you can find the movies Hey, with vector v k m that is similar to that. And as you saw in the last video, finding the similar movies to a given movie can be pre computed. So having pre computed the most similar movies to given movie, you can just pull up the results using a lookup table. This would give you an initial set of maybe somewhat plausible movies to recommend to a user that just showed up on your website. Additionally, you might decide to add to it for whatever are the most viewed three genres of the user. Say there's a user that's watched a lot of romance movies, and a lot of comedy movies and a lot of historical dramas. Then we would add to the list of plausible item candidates to top 10 movies in each of these three genres. And then maybe we would also add to this list, the top 20 movies in the country of the user. So this retrieval step can be done very quickly and you may end up with a list of 100 or maybe hundreds of plausible movies to recommend to the user. And hopefully this list will recommend some good options, but it's also okay if it includes some options that the user won't like at all. The goal of the retrieval step is to ensure broad coverage, to have enough movies to at least have many good ones in there. Finally, we would then take all the items we retrieve during the retrieval step and combine them into a list, removing duplicates and removing items that the user has already watched or that the user has already purchased and that you may not want to recommend to them again. The second step of this is then the ranking step. During the ranking step, you would take the list retrieved during the retrieval step, so this may be just hundreds of possible movies and rank them using the learned model. And what that means is you will feed the user feature vector and the movie feature vector into this neural network. And for each of the user movie pairs, compute the predicted rating. And based on this, you now have all of the say 100 plus movies, the ones that the user is most likely to give a high rating to. And then you can just display the rank list of items to the user depending on what you think the user will give the highest rating to. One additional optimization is that if you have computed Vm for all the movies in advance, then all you need to do is to do inference on this part of the neural network a single time to compute Vu and then take that Vu that you just computed for the user on your website right now and take the inner product between Vu and Vm for the movies that you have retrieved during the retrieval step. So this computation can be done relatively quickly if the retrieval step just brings up say hundreds of movies. One of the decisions you need to make for this algorithm is how many items do you want to retrieve during the retrieval step to feed into the more accurate ranking step. During the retrieval step, retrieving more items will tend to result in better performance, but the algorithm will end up being slower. To analyze or to optimize the trade-off between how many items to retrieve, do you retrieve a hundred or five hundred or a thousand items, I would recommend carrying out offline experiments to see how much retrieving additional items results in more relevant recommendations. And in particular, if the estimated probability that yij is equal to one, according to your neural network model, or if the estimated rating of y being high of the retrieved items according to your model's prediction ends up being much higher, if only you were to retrieve say five hundred items instead of only one hundred items, then that would argue for maybe retrieving more items even if it slows down the algorithm a bit. So with the separate retrieval step and the ranking step, this allows many recommender systems today to give both fast as well as accurate results because retrieval step tries to prune out a lot of items that are just not worth doing the more detailed inference and inner product on, and then the ranking step makes a more careful prediction for what are the items that the user is actually likely to enjoy. So that's it. This is how you would make your recommender system work efficiently, even on very large catalogs of movies or products or what have you. Now it turns out that as commercially important as our recommender systems, there are some significant ethical issues associated with them as well. And unfortunately, there have been recommender systems that have created harm. So as you build your own recommender system, I hope you take an ethical approach and use it to serve your users and society as large as well as yourself and the company that you might be working for. Let's take a look at the ethical issues associated with recommender systems in the next video.
[{"start": 0.0, "end": 6.44, "text": " Today's recommended systems will sometimes need to pick a handful of items to recommend"}, {"start": 6.44, "end": 11.6, "text": " from a catalog of thousands or millions or tens of millions or even more items."}, {"start": 11.6, "end": 13.72, "text": " How do you do this efficiently computationally?"}, {"start": 13.72, "end": 16.04, "text": " Let's take a look."}, {"start": 16.04, "end": 21.080000000000002, "text": " Here's the neural network we've been using to make predictions about how a user might"}, {"start": 21.080000000000002, "end": 22.84, "text": " rate an item."}, {"start": 22.84, "end": 32.24, "text": " Today, a large movie streaming site may have thousands of movies or a system that is trying"}, {"start": 32.24, "end": 40.72, "text": " to decide what ad to show may have a catalog of millions of ads to choose from or a music"}, {"start": 40.72, "end": 47.94, "text": " streaming site may have tens of millions of songs to choose from and large online shopping"}, {"start": 47.94, "end": 52.8, "text": " sites can have millions or even tens of millions of products to choose from."}, {"start": 52.8, "end": 59.559999999999995, "text": " When a user shows up on your website, they have some feature XU, but if you need to take"}, {"start": 59.559999999999995, "end": 66.5, "text": " thousands or millions of items to feed through this neural network in order to compute the"}, {"start": 66.5, "end": 71.56, "text": " inner product to figure out which products you should recommend, then having to run neural"}, {"start": 71.56, "end": 77.2, "text": " network inference thousands or millions of times every time a user shows up on your website"}, {"start": 77.2, "end": 80.6, "text": " becomes computationally infeasible."}, {"start": 80.6, "end": 86.75999999999999, "text": " Many large scale recommender systems are implemented as two steps, which are called the retrieval"}, {"start": 86.75999999999999, "end": 89.08, "text": " and ranking steps."}, {"start": 89.08, "end": 97.63999999999999, "text": " The idea is during the retrieval step will generate a large list of plausible item candidates"}, {"start": 97.63999999999999, "end": 103.19999999999999, "text": " that tries to cover a lot of possible things you might recommend to the user."}, {"start": 103.19999999999999, "end": 107.96, "text": " And it's okay during the retrieval step if you include a lot of items that the user is"}, {"start": 107.96, "end": 115.32, "text": " not likely to like and then during the ranking step will fine tune and pick the best items"}, {"start": 115.32, "end": 117.36, "text": " to recommend to the user."}, {"start": 117.36, "end": 119.19999999999999, "text": " So here's an example."}, {"start": 119.19999999999999, "end": 125.0, "text": " During the retrieval step, we might do something like for each of the last 10 movies that the"}, {"start": 125.0, "end": 130.44, "text": " user has watched, find the 10 most similar movies."}, {"start": 130.44, "end": 138.85999999999999, "text": " So this means for example, if a user has watched the movie I with vector v i m, you can find"}, {"start": 138.85999999999999, "end": 145.32, "text": " the movies Hey, with vector v k m that is similar to that."}, {"start": 145.32, "end": 150.36, "text": " And as you saw in the last video, finding the similar movies to a given movie can be"}, {"start": 150.36, "end": 152.16, "text": " pre computed."}, {"start": 152.16, "end": 156.96, "text": " So having pre computed the most similar movies to given movie, you can just pull up the results"}, {"start": 156.96, "end": 158.72, "text": " using a lookup table."}, {"start": 158.72, "end": 163.35999999999999, "text": " This would give you an initial set of maybe somewhat plausible movies to recommend to"}, {"start": 163.35999999999999, "end": 165.88, "text": " a user that just showed up on your website."}, {"start": 165.88, "end": 172.5, "text": " Additionally, you might decide to add to it for whatever are the most viewed three genres"}, {"start": 172.5, "end": 174.07999999999998, "text": " of the user."}, {"start": 174.07999999999998, "end": 179.04, "text": " Say there's a user that's watched a lot of romance movies, and a lot of comedy movies"}, {"start": 179.04, "end": 181.92, "text": " and a lot of historical dramas."}, {"start": 181.92, "end": 187.56, "text": " Then we would add to the list of plausible item candidates to top 10 movies in each of"}, {"start": 187.56, "end": 189.56, "text": " these three genres."}, {"start": 189.56, "end": 196.72, "text": " And then maybe we would also add to this list, the top 20 movies in the country of the user."}, {"start": 196.72, "end": 202.92000000000002, "text": " So this retrieval step can be done very quickly and you may end up with a list of 100 or maybe"}, {"start": 202.92000000000002, "end": 207.4, "text": " hundreds of plausible movies to recommend to the user."}, {"start": 207.4, "end": 214.2, "text": " And hopefully this list will recommend some good options, but it's also okay if it includes"}, {"start": 214.2, "end": 217.56, "text": " some options that the user won't like at all."}, {"start": 217.56, "end": 223.2, "text": " The goal of the retrieval step is to ensure broad coverage, to have enough movies to at"}, {"start": 223.2, "end": 226.28, "text": " least have many good ones in there."}, {"start": 226.28, "end": 232.12, "text": " Finally, we would then take all the items we retrieve during the retrieval step and"}, {"start": 232.12, "end": 237.35999999999999, "text": " combine them into a list, removing duplicates and removing items that the user has already"}, {"start": 237.35999999999999, "end": 241.16, "text": " watched or that the user has already purchased and that you may not want to recommend to"}, {"start": 241.16, "end": 243.04, "text": " them again."}, {"start": 243.04, "end": 246.32, "text": " The second step of this is then the ranking step."}, {"start": 246.32, "end": 251.51999999999998, "text": " During the ranking step, you would take the list retrieved during the retrieval step,"}, {"start": 251.51999999999998, "end": 259.12, "text": " so this may be just hundreds of possible movies and rank them using the learned model."}, {"start": 259.12, "end": 265.68, "text": " And what that means is you will feed the user feature vector and the movie feature vector"}, {"start": 265.68, "end": 267.56, "text": " into this neural network."}, {"start": 267.56, "end": 273.48, "text": " And for each of the user movie pairs, compute the predicted rating."}, {"start": 273.48, "end": 280.04, "text": " And based on this, you now have all of the say 100 plus movies, the ones that the user"}, {"start": 280.04, "end": 282.96, "text": " is most likely to give a high rating to."}, {"start": 282.96, "end": 287.96, "text": " And then you can just display the rank list of items to the user depending on what you"}, {"start": 287.96, "end": 291.1, "text": " think the user will give the highest rating to."}, {"start": 291.1, "end": 298.76000000000005, "text": " One additional optimization is that if you have computed Vm for all the movies in advance,"}, {"start": 298.76000000000005, "end": 304.32000000000005, "text": " then all you need to do is to do inference on this part of the neural network a single"}, {"start": 304.32000000000005, "end": 310.64000000000004, "text": " time to compute Vu and then take that Vu that you just computed for the user on your website"}, {"start": 310.64000000000004, "end": 316.76000000000005, "text": " right now and take the inner product between Vu and Vm for the movies that you have retrieved"}, {"start": 316.76000000000005, "end": 318.72, "text": " during the retrieval step."}, {"start": 318.72, "end": 324.3, "text": " So this computation can be done relatively quickly if the retrieval step just brings"}, {"start": 324.3, "end": 326.88000000000005, "text": " up say hundreds of movies."}, {"start": 326.88000000000005, "end": 331.84000000000003, "text": " One of the decisions you need to make for this algorithm is how many items do you want"}, {"start": 331.84000000000003, "end": 339.20000000000005, "text": " to retrieve during the retrieval step to feed into the more accurate ranking step."}, {"start": 339.20000000000005, "end": 345.14000000000004, "text": " During the retrieval step, retrieving more items will tend to result in better performance,"}, {"start": 345.14, "end": 349.59999999999997, "text": " but the algorithm will end up being slower."}, {"start": 349.59999999999997, "end": 355.12, "text": " To analyze or to optimize the trade-off between how many items to retrieve, do you retrieve"}, {"start": 355.12, "end": 361.76, "text": " a hundred or five hundred or a thousand items, I would recommend carrying out offline experiments"}, {"start": 361.76, "end": 367.71999999999997, "text": " to see how much retrieving additional items results in more relevant recommendations."}, {"start": 367.71999999999997, "end": 375.12, "text": " And in particular, if the estimated probability that yij is equal to one, according to your"}, {"start": 375.12, "end": 382.08, "text": " neural network model, or if the estimated rating of y being high of the retrieved items"}, {"start": 382.08, "end": 387.4, "text": " according to your model's prediction ends up being much higher, if only you were to"}, {"start": 387.4, "end": 393.16, "text": " retrieve say five hundred items instead of only one hundred items, then that would argue"}, {"start": 393.16, "end": 399.24, "text": " for maybe retrieving more items even if it slows down the algorithm a bit."}, {"start": 399.24, "end": 405.08, "text": " So with the separate retrieval step and the ranking step, this allows many recommender"}, {"start": 405.08, "end": 412.08, "text": " systems today to give both fast as well as accurate results because retrieval step tries"}, {"start": 412.08, "end": 418.38, "text": " to prune out a lot of items that are just not worth doing the more detailed inference"}, {"start": 418.38, "end": 424.08, "text": " and inner product on, and then the ranking step makes a more careful prediction for what"}, {"start": 424.08, "end": 428.36, "text": " are the items that the user is actually likely to enjoy."}, {"start": 428.36, "end": 429.36, "text": " So that's it."}, {"start": 429.36, "end": 434.52000000000004, "text": " This is how you would make your recommender system work efficiently, even on very large"}, {"start": 434.52000000000004, "end": 438.68, "text": " catalogs of movies or products or what have you."}, {"start": 438.68, "end": 445.92, "text": " Now it turns out that as commercially important as our recommender systems, there are some"}, {"start": 445.92, "end": 449.96000000000004, "text": " significant ethical issues associated with them as well."}, {"start": 449.96000000000004, "end": 455.42, "text": " And unfortunately, there have been recommender systems that have created harm."}, {"start": 455.42, "end": 460.28000000000003, "text": " So as you build your own recommender system, I hope you take an ethical approach and use"}, {"start": 460.28000000000003, "end": 466.36, "text": " it to serve your users and society as large as well as yourself and the company that you"}, {"start": 466.36, "end": 468.04, "text": " might be working for."}, {"start": 468.04, "end": 486.44, "text": " Let's take a look at the ethical issues associated with recommender systems in the next video."}]