Recommender Systems Overview | Stanford Lecture

[00:00:00]welcome back to mining of massive data sets today's topic is recommended systems we're going to start with an overview of recommendation systems and why they are necessary then we're going to look at the two most common types of recommended systems content based systems and collaborative filtering and finally we're going to look at how to evaluate recommended systems to make sure they're doing a good job let's start with an overview imagine any situation where a user interacts with a really large catalog of items now these items could be products at Amazon they could be movies at Netflix there could be music from Pandora's catalog or they could be you know news items on Google News what really matters is that there are tens of thousands or hundreds of thousands or millions of items a really large catalog and the user is interacting with this catalog and there's two ways in which a user can interact with a large catalog of items the first is search the user knows what they're looking for and they go and they search the catalog for the precise item that they're looking for now when you have a really large catalog of items very often the user doesn't know exactly what they're looking for and this is where recommendations come in the system recommends to the user certain items that they think the user will be interested in based on what they know about the user now why do we really need such recommendations the key that made recommendation so important and why recommendation system developed so much in the last 10 or 20 years is that we moved from an era of scarcity to an Era of abundance what do I mean by this imagine that you were out shopping 20 years ago go and You' go to a local retailer and you'll find a certain number of products on the shelves of the local retailer now even in a really large retailer like like a Walmart for instance shelf space is a key is a scarce commodity it limits the number of items that the retailer can carry shelf space is expensive because it involves real estate costs and therefore a retailer can carry only a certain number of products now similar situation applies in the case for example of TV networks a TV network can carry only so many shows because there's only so many number of hours in a day and there are only so many movie theaters so they can only screen a certain number of movies now once the Internet was developed things changed the web enables zero cost dissemination of information about products and what this means is that we can have many more products than ever before there is no shelf space limitation on the number of products that's why the number of products on Amazon is much much more than the number of products available at any physical retailer the number of you know movies available on Netflix is more than the number of movies that were ever available at a blockbuster and so on this near zero cost dissemination of information gives rise to a phenomenon that's called the longtail phenomenon let's examine what this is now imagine a graph where on the x-axis we've taken the items in the catalog remember items might be books or music or video or news articles and you've ranked these items by popularity so the most popular items are on the left and as you move towards the right the items become less and less popular what do I mean by popular well I mean the number of times the uh item is purchased in a week or it could be the number of times a movie is viewed in a week or a month or some some fixed time period now on the y- AIS we have the actual popularity which in this case I've shown as number of purchases per week it could be number of views per week or it could be number of you know plays per month for for music and so on so in general you have items ranked by popularity along the x-axis and the popularity itself along the y- axis now when you take items uh you know in a large catalog um and you rank them uh and you plot them on this curve um you you get a curve that looks like this you can see that this curve you know has a very steep fall initially uh the the you know you have a really really a few really really popular items uh and then as you move towards the right uh as the you know as the item rank becomes greater the popularity falls off very steeply but at a certain point you can see that the popularity stops you know you know falls off less and less steeply and you know it never quite reaches the x-axis the interesting thing here is that there is a cutoff point be you know items that are less popular than this cutoff point you know might be purchased perhaps just once a week or maybe once a month if you're a physical retailer like a Walmart it's not economic to stock this item because the rent cost of stocking the item is more than you make by when you sell the item and therefore a retailer any right thinking retailer doesn't stock items that are unpopular they you know they only stock the the head of this distribution so there's this um cut off point that I show on this graph here um and items that are more popular than this the the more popular items are available at a retail store but the less popular items the items that are to the right of the cutoff Point are not available at any retail store they're only available online now this phenomenon applies to books to music to move to videos to news articles for example there are only so many news articles in newspaper but when you go online uh you can see the rest of the news articles the less popular news articles that are off to the right the piece of the curve that is to the the piece of the curve here that is to the uh right of this dividing line is called the long tail these are the items that are available only online the interesting thing is the is this area under the curve here and you can see the area under the curve here is quite significant in fact in some cases the area under the curve on the right is about as large or could be even larger than the area of the curve under the curve on the on the left so you have all these items that could never be found in a physical store but that can be only found online um but there are so many of them that it's very hard for any user to find all these items right so when you have this era of abundance and you have so many items um and many of them are only found online how you know how do you introduce a user to all these new items that they may not otherwise find when you have more Choice like this when you have these millions and millions of items that are only available online you need a better way for the user to find all these items the user doesn't even know where to start looking and that's where recommendations uh engines come in so recommendation engines both in the case of many many kinds of items books music movies news articles interestingly they even work in the case of people for example when you go to Facebook or LinkedIn or Twitter there are so many people that you don't know who to follow or who to friend and so Facebook or LinkedIn or Twitter makes recommendations to you on the people that you know that you could follow a friend I lent this point with an interesting anecdote that shows you the power of recommendation engines several years ago um a book was published called touching the void it's a book about mountaineering it's a very very good book uh the book came out it didn't make much of a Ripple uh you know a few people bought the book it got some decent reviews but it never became a bestseller and then a few years after touching the void a new book was published on mountaineering called Into Thin Air now Into Thin Air picked up traction and lots of people started buying Into Thin Air Amazon noticed that a few of the people who bought Into Thin Air had also bought touching the void so they started recommending touching the void to people who bought Into Thin Air and lo and behold those people started buying touching the void as well the interesting point is this made touching the void a bestseller in fact it became a bigger bestseller even than Into Thin Air even though a few years ago it had sank Without a Trace so this example should show you the power of recommendation systems there are these items these sort of gems like touching the void um you know that people don't know because they don't know to look for them but a good recommendation system can expose people to these hidden gems that they wouldn't have known about otherwise so let's look at types of recommendation systems the simplest uh and the oldest kind of recommendation is editorial or hand curated you might find a list of favorite for example when you go into your favorite neighborhood bookstore you might find staff picks certain books are marked off as staff picks right and these are editorial or hand curated um and on certain websites you'll see a list of Staff favorites or you'll see a list of essential items these are essentially built by hand um and another place where you'll see these editorial recommendations is often on the homepages of websites for example uh if you go to the uh the homepage of uh most popular uh websites including uh uh product websites you'll see uh editorial picks these are products that have been picked by the editorial staff to feature on the homepage the drawback with uh editorial or hand curated recommendations is that it's done entirely by uh you know by the staff of the website and there's no input from the users of the site so when you go beyond editorial recommendations the next simple thing that you can do is simple Aggregates on many websites you'll see uh list of top 10 or most popular or most recent uh for example if you go to YouTube uh you can see the most popular videos for instance right uh so these are simple Aggregates uh which sort of take into account user activity to make recommendations to other users but these recommendations don't uh depend on the user uh they only depend on you know the the aggregate activity of a lot of other users the third and most interesting kind of recommendation to us is uh recommendations that are tailored to individual users right uh for example book recommendations tailored to your taste or movie recommendation based on the movies that you watched previously or music recommendation based on your music interest and this is our Focus here uh recommendations that are tailored to individual users so let's look at a formal model let C be a set of customers and S a set of items we're going to create a function called the utility function or a utility Matrix the utility function uh is a function uh that looks at every pair of customer and item and Maps it to a rating okay uh R in this case is a set of ratings uh and for example R could be a star rating from one star to five star or R could be a number between uh 0 and 10 um in general R is a totally ordered Set uh so that you know a lower value indicates that the user like the product less and a higher value indicate so the user like the product more let's look at an example of utility Matrix now on the top we have four movies here Avatar lot of the Rings Matrix and Pirates of the Caribbean and down here we have four users Alice Bob Carol and David uh and the utility Matrix gives you ratings for certain movies uh and certain users for example Alice has rated Avatar and Matrix but not lot of the Rings are Pirates of the Caribbean whereas Carol has rated uh you know has rated the same two movies uh Bob has rated a lot of the Rings and Pirates uh but has rated Avatar you know or or Matrix now it could be that these users have not seen these movies um or it could be that they've seen the movies but not bother to rate them so in general a utility Matrix like this is going to be sparse uh you know most of the users haven't seen most of the movies and there are going to be values in some of the uh you know some of the locations the key problem in recommendation systems is to figure out these unknown values for example uh you you've seen that Alice has rated Avatar and Matrix but hasn't rated a lot of the ranks so the question is uh can we figure out what Alice's rating for a lot of the Rings will be based on her other ratings can you figure out whether she'd like Pirates or not right so this is the key problem for recommender systems once we find out for each user certain movies that they would have rated highly or which the system thinks they might have rated highly then we can recommend those movies to those users so there are three key problems in the space of recommended systems the first is gathering the known ratings in the uh ratings in The Matrix now in the previous slide uh when you looked at the utility Matrix uh it was already filled in with certain values but how do you GA gather those values in the first place so that's the key uh that's the first problem that you need to tackle the second problem is to extrapolate unknown ratings from known ratings but we're mainly interested in the high unknown ratings we're interested in those ratings where a user would have given a high rating to a movie We're not interested in the average or the low ratings because we're never going to recommend those movies to the user and finally the third key problem is evaluate extrapolation methods once you have a recommendation system that can extrapolate unknown ratings from known ratings how do you know that the recommended system is doing well this is where extra you know the valuation methodologies come in let's start with the first problem that of gathering datings the first and simplest way of gathering ratings is is what what I'll call explicit methods simply ask people to rate items now this method is good because the you know uh you're asking people to directly rate items and you're going to get uh you know for and you can decide on what scale people are going to rate item for example you can say you can ask for ratings on a one to five star scale or you can ask people to rate on a scale from 0 to 10 um or or you can just ask people to say whether they likeed an item or did not like it so the explicit method has the advantage of Simplicity um and of getting direct responses from users the problem though is that it doesn't scale only a small fraction of users who viewed a movie or listened to a you know piece of music or bought a product actually bother to leave a rating or review most users don't actually leave ratings or review use so while the data that's explicitly gathered is excellent data it uh it's not sufficient in most cases for recommendations because only a small fraction of users actually leave ratings and reviews since explicit ratings don't scale a lot of sites use implicit ratings now the idea behind implicit ratings is to learn ratings from other user action for example u u an online shopping website might uh have a rule that a purchase implies a high rating now the nice thing about implicit ratings is that they're much more scalable than uh explicit ratings because the user doesn't have to explicitly rate an item and there are way more other actions such as purchases than there are ratings the problem though is that it's very hard using implicit ratings to learn low ratings it's quite easy to learn high ratings because you might have a rule that purchase implies a high rating but you you can never learn a rating uh that a user disliked a product uh implicitly in practice most recommended systems and most websites use a combination of explicit and implicit ratings where explicit ratings are available they use them but they supplement them with implicit ratings when needed let's move on now to the central problem of extrapolating utilities uh or extrapolating unknown utilities from known utility values the key or Central problem that we have to sount to extrapolate utilities is that the Matrix U the utility Matrix is very very sparse most people have not rated most items and this introduces a slew of problems that we'll come across shortly the second problem we have is a cold start problem when you have a new item or a new user the new item doesn't have any ratings and new users have no no history so this is known as a cold start problem and and we'll have to tackle this problem as well in Du course there are three approaches to building recommendation systems the first is content based recommendations the second is collaborative filtering and the third is latent factor based models let's start with content based based approaches