BDSBTB 2015: Leah McGuire, Un-collaborative Filtering: Recommendations when Users Aren’t Helping
so yes so today I'm going to be talking about a collaborative filtering or unclad word filtering as the little pun says just in case you guys are a little bit tired I'll go ahead and tell you the full talk before I actually start and so basically I'm just going to start off with a brief introduction about recommender systems Heather used Heather built then I'll talk about our use case in particular so using AWS and spark for what I'll call medium sized data at scale and building a recommender system explicitly for purchase data so we don't have ratings that we're trying to predict we're just trying to predict whether or not people will buy something and make appropriate recommendations based on that I'll talk about how to choose a model and run it on spark and in particular I'll go into debt detail about item-based nearest neighbourhood models and matrix factorization models and then I'll talk a lot actually about how to evaluate a model and particularly a model without any explicit negative feedback and so a model where you don't have ratings and then I'll touch briefly on just the importance of presentation in in recommender systems so most if not all of the people in this room are probably familiar with the netflix prize so netflix offered a million dollars to the team that can improve their recommender system by ten percent so a ten percent increase in root-mean-square air and this generated a lot of research on recommender systems and basically improve improve the field but not every recommender system is the same right so when Netflix was doing this they were primarily a male based system they had a long latency between when they would send something to person when they would rate it and this really affected the way their recommended recommendations were used now they're primarily sort of online and you can see there's a lot of online recommender systems just everywhere and so when you're building a recommender system the things to keep in mind are really sort of what do you know about the users and the items whether or not there are ratings and how is that rating system used by each user so even if you have ratings you need to scale it for users but if you don't and you're trying to recommend based on purchases or views what does it mean if someone didn't purchase an item right does that mean they hate it or do they just didn't see it and also just looking at an article mean that it's a good recommendation if someone flips to something and then flips right off probably not right and so even how you generate your positive data for training take some thought so there's a lot of ways that you can start out building a recommender system and this is just sort of a stolen slide off Wikimedia Commons showing the broad categories of recommender systems so there's collaborative filtering models which are sort of taking the wisdom of the crowd to try and make recommendations based on what others users did those can be broken down into sort of broadly neighborhood based approaches so similar items or similar users are used to make recommendations they're model-based approaches so things like matrix factorization basically you're trying to come up with some description of the features that are important and then of course you can combine those types of models there are also content based models so if you know things about the users if you know things about the items you can take that information and try and combine it to really make a good recommendation for this particular user will like this particular item based on what we know about them and of course you can combine those those types of models again to make recommendations so when you're building a recommender system you really do have to take into account not only the type of data but also sort of the scale of your data so not all recommender systems really scale particularly to very large data but also you need enough data to fit your model so if you're going to have run something like matrix factorization in the classical forms this actually was really difficult to do there have been some developments of more scalable algorithms for matrix factorization which make this possible but again you need to take into account sort of how many users how many items you have and deal with that appropriately in choosing your algorithm so our particular use case at Salesforce was basically that Salesforce is sort of a repository for other companies data and so this data comes in it's very siloed it doesn't touch other companies data both for legal reasons and in our case actually practical reasons it's much easier to deal with as a siloed bit of data that maybe you know medium-sized some of them are large but most of them aren't that big and so it's much more practical so sort of fit a model based on one company's data to make recommendations but we have a lot of companies and for each company we want to fit a model make some top K recommendations and this actually rapidly adds up to sort of a big data problem right so it has to be able to scale but I mean it's nice for us right we don't have to deal with this behemoth data set so what would you do if you did have to and there's sort of a couple of options that you can take for dealing with really big data one is the course just to make your algorithm better and if you want to do this fortunately there have a bunch of people who have already sort of worked on improving these algorithms there's a ton of papers out there and so you can implement what they've done already another good option is actually just to make your algorithms simpler and so you've all probably heard the adage that more data and better better data is better than better algorithms so if you're smart about your features you can get away with a much simpler algorithm and another another thing you can do is actually try and break your data down so we fortunately had companies that we could focus on but you can do things like try and break your data into business groups you can try and break it into a focus on items instead of users or even types of items if you have metadata about the items but one of the important things is to actually just build for scale so make sure that your infrastructure is going to be able to deal with the size of your data in whatever form the model is going to take and so the infrastructure that we chose was actually to go with AWS and spark and so this is this is nice for us because we needed something that would rapidly scale going from a couple of pilot users to basically as many people who wanted to sign up for the new terms of service and get this this particular product and AWS is really great for that and we didn't want to reinvent the wheel so spark has great machine learning libraries you don't want to go re-implement a commodity algorithm that's been implemented a thousand times and so we could really use that to build on top of so what we actually wanted to build was a top k recommendation list right and so these companies have very different data within them and some of them have things like product catalogs some of them have metadata that we could abused but the only thing we were really consistently sure was in every company was purchased data and so that was a place to start to really build something that would generalize across all these companies and once we've got that we can bring in other pieces of data to sort of improve the model so given that kind of data the question became well what models do we want to start with and if you look at the data so i have here just sort of an example of what it might look like with just purchase data you have something like a user ID a product ID and maybe a date of purchase and this is called you know you narrate binary implicit data but all of the all of these whatever you call it it basically does require some special consideration and how you model it so there's a number of good candidates for these these kinds of data the first is item based nearest neighbors and the sector is matrix factorization specifically for implicit data and so i'll i'll go into the details of what that difference is later on there might be some other models that you could try i'm going to argue that these are the best ones you don't really want to go into a restricted Boltzmann machine at your first pass and so this these are the two models I'm going to talk about here and I'm going just going to emphasize continually throughout the talk that evaluation of the models and getting the evaluation right for the type of data that you're using was really important um so to talk a little bit about what these models look like basically item-based nearest neighbors is a really nice model so it's simple to compute and explain it tends to be more stable and scalable than a user based recommendations and basically all you need to do to show it is do something to compute a similarity matrix between items and so in this case I used Jaccard similarity so basically the intersect of the users who bought item a with an item B divided by the union of the users who bought item a and item B and then in order to compute a rating based on that so you get your similarity you compute the most similar items and that's your neighborhood computer rating with that you basically take the similarity for all the items in the neighborhood for a particular item that you want to rate so rating for a particular user a particular item similarity for all the items in the neighborhood and basically multiply that by the ratings of the user or the whether or not the user purchased a particular item in the the set of items the users purchase divide that by the total items in the neighborhood and that will give you your recommendation so an example of what that looks like is basically if you have a user who is purchased a hat then you might recommend to them a coat scarf and gloves which you wouldn't recommend jeans on a table so I am going to show you just a little bit of Scala code now and basically this is to say so item based nearest neighbors is not implemented in spark but it's a really simple algorithm to compute and so I have two slides they don't have that much code and I'm just going to walk through it quickly basically so this is computing the jacquard on the top and you're passing in the sets of users who purchased item one or product one in product two and then you just take the intersect and you take the union of those sets and then divide them and so that's all very nice and simple in order to compute the similar map what you do is basically I'm assuming that you're passing in an RDD of ratings and ratings are actually a case class that's just part of the the spark recommendations package and so you go ahead and group buy the product and then get the sets of all the users who bought those products you take the cartesian of the products and the user set with itself this can be really expensive in there are ways that you can sort of limit this to only 0 products that have at least one user in common but let's just say for simplicity that you take the cartesian you filter out products that are the same as themselves you don't care about them then you go ahead and compute the Jaccard similarity for all of those users and then given those similarity maps again you group on product take those similarities and take the top most similar products to get your similarity math and so that's all you need to do to train the second slide is just what you need to do to actually produce a recommendation and again so you have a particular user that you're trying to predict for a particular product that you're trying to predict for an array of all of the products that a user has purchased an array of all of the similar items for the particular product that you're trying to recommend and then to compute the recommendation again you just some across the item neighbors map and that's your divisor to compute the similarity basically you look at the products that the user purchased go ahead and get the similarities for the items in the map for those particular purchase products and that's your numerator then you just divide the sum of the the neighbors for the purchase products by the total sum of the neighbors and that gives you your rating and it's pretty much it that's all you need to do to implement nearest neighbors in spark so not too bad matrix factorization is is sort of the model-based approach and the way to think about this is basically if you think of your total space is basically a matrix so users are the rows and products or items are the columns and basically each element within that is whether or not they purchased or what their rating was what you're trying to do is come up with two new matrices one for users and one for products that have less dimensions that still describe everything that's going on in this larger matrix so it's it's describing all of those interactions but with fewer dimensions so finding an underlying representation for what's going on fortunately implicit matrix factorization is already in spark which is very nice so all you have to do to use it is basically import the appropriate library and say all right ALS train implicit and then passing your parameters so very easy to use and then basically the the difference between implicit and explicit matrix factorization is is in this equation over here I guess on your right and if you don't want to look at that there's the text from from spark but basically what it's doing is in in most matrix factorization if you look at the first the terms in the first set of parentheses that's what you're trying to minimize in regular matrix factorization so you have a user preference so P for a particular item and you're trying to minimize the difference between the multiple of the user factorized row and the item column basically just minimize the sum square error within that for implicit data you're basically adding on the second term which is C or the confidence in that purchase so it's basically separating out whether or not something happened with actually how confident you are that that means the person liked it so it's putting in this additional term this wiggle room that really allows the model to fit implicit data much better and that confidence is 1 plus alpha which is a hyper parameter that you tune times the rating or the number of times that the person purchased the data and then the preference just becomes 0 1 based on whether or not they purchase the data and the second part of this term is just regularization so with matrix factorization there's a lot of empty spaces within that matrix that you're trying to fill in you want to make sure you're not over fitting to the data and so you put a penalty on the terms that you fill in with your with your matrices so great so those are our two models how are we actually going to select between them and you know there's a lot of metrics to choose from so with implicit data you probably want to pick something from this screen but basically some good options might be precision and recall so you have things like the number of true positives that you predict versus the total number of positives that you predict and that's your precision or you could have the recall which is the number of true positives you predict over the total number that you could have predicted that would actually be positive you can do the f1 metric which is the harmonic mean a precision and recall and then there's the classic sort of root mean square error which is used for a lot of things area under ROC is again related to true positive and false false positives in basically looking at how different from chance is your model and then there's also some ranking metrics so if you're presenting a list you can do things like see where in a list your items occur on with mean reciprocal rank you can use discounted cumulative gain if you have a true ranking to basically say ok so given the rankings that I gave how close is that to my true ranking and basically you have a metric of the difference between those two but none of those metrics actually solve a fundamental problem with implicit data and that's basically that there's no negatives right so if you look at this data and sort of work through the classic machine learning process if you have your original data and again that's like the user ID the item ID the data purchase and you divide that up into your training and validation and then your test sets and this can be a separate training and validation or cross validation on your training it doesn't matter the the problems remains that you basically only have ones if you think about the ratings right and so the the best fit to this would actually be a model that predicted the user would buy everything which is not at all useful and so you have to get around this you have to have some negative data somehow and there's a couple of ways that you can do this the first is actually to just generate some negative data and so you can basically say okay some unwritten assigned values that the person didn't buy i'm going to say those are negative and the reason this works is that if you think about the total space of users and products it's very large and the actual relative space of products the user will actually like is much smaller so just randomly assigning things from from that very large space as negative will probably be correct and so this actually does work it's a bit of a hack but it'll give you something you can work with another option is actually to generate a list and focus on the top K recommendations so do your does your holdout set actually appear in the list that you're recommending so there's just a couple things to consider when you're deciding between you know the sort of matrix of how am I generating negative data what are my metrics that I'm going to use and it is this kind of thing of actually considering what you're trying to do so all are your results going to be a short list or a long list this actually makes a big difference in what what kind of metric you choose are you predicting a rating are you trying to predict whether or not someone will purchase something so is it actually just a hit or a miss of whether or not they'll purchase I mean the other thing is actually just to be aware of the biases and offline training so if you're doing a top K recommendation this will sort of skew towards popular items which can lead towards less personalization and and then things like RSC precision and recall will actually not tell you anything about how good the ordering is and so if you need that information this might not be the right metric and finally it's just really important to remember that offline evaluation is not perfect and so you want to go ahead and test in the wild that's what this guy is doing he's testing in the wild and so remember that models have a lot of different levers that you have to tweak and so just an example of what that looks like this is one set of relatively modest you know grid search for hyper parameter tuning for implicit matrix factorization as you can see so the rank of the matrix that you're trying to fit your regularization parameters how many iterations until convergence and then your confidence value for for the fit you can see this rapidly adds up you could be running the model 250 times this takes a lot of time and it's time and resource intensive but you really can't get around it because it is a huge effect on model performance and it's really data set specific so you need to do it for every every data set but fortunately you know if you have flexible resources and spark you can paralyze this and actually make it happen much faster as long as you have the right evaluation metric so what is the right evaluation metric so I'm just going to start off by saying it's not root mean square knot knot with implicit data so what I've plotted here is basically the root mean square error on a number of runs for different models with different hyper parameters against the number of true positives actually predicted by the model so half done is the model correctly predicting that something something would appear and this is for a case where I just generated false negative data so one thing to keep in mind is of course that this depends on the amount number of false negatives that you generate but more importantly is actually that this just isn't very helpful for predicting it's not even correlated with a number of true positives that the model is predicting and it's not really showing good differences between the models so if you look at alternating least squares explicit so matrix factorization for explicit data which is inappropriate for this kind of data you can see that it actually covers the same range about of root mean square errors as alternating lace least squares implicit so matrix factorization specifically for this kind of data it's not showing you the differences very well between those those two models however if you look at the true mod true positives it's clear that the appropriate model is doing much better right so just don't use this magic if you're trying to trying to evaluate something that will work is is for example hits and misses so again this is with generating zeros for the data and what I've plotted here is the the recall on the y-axis versus the precision on the x-axis again I'm throwing three different types of models with different hyper parameters so basically you have the alternating least squares explicit the inappropriate model you have the alternating least clear squares implicit so the more appropriate model and you have item based nearest neighbors but you can see is there's actually a nice trade off so there's a trade-off between precision and recall which you expect and then it's showing differences between the models so the implicit matrix factorization is actually doing better on recall but slightly worse on precision and so if you're using the f1 you might choose item based nearest neighbors for this particular data set so one thing to keep in mind is that this will again depend on how much negative negative data you generate but as long as you keep it consistent across models you can sort of compare between them and really get a good idea of what's going on if instead of generating zeros you want to look at the top K results basically you can say given my hold out what percentage of those actually appear in my list that I'm generating and if you're if you're presenting a short list this is probably a good way to go and and what I've plotted here is just item based nearest neighbors versus alternating least squares implicit so the appropriate matrix factorization model and what you can see is there there's somewhat comparable in this particular case but there's a big difference in performance or recall based on how many items are in your list and so basically it if you're presenting a list of something like 50 different items this may not be a good metric because chances are users aren't going to look at the 50th item so giving the same amount of points for something at the end is at the beginning isn't really going to help you a couple more things to keep in mind with this is so you don't want to look at precision in this because it's entirely dependent on the length of the list and if you're if you're presenting a really long list again you have no way of knowing how good the other k minus whatever your holdout set is and those are the really interesting things right those are those are basically the novel recommendations and so that's where it becomes important again to follow up in the wild and make sure that you see how users are responding to those and really get evaluation after you present it but going back to what to do if you're if you're generating a really long list users may or may not look all the way down you may want to move to something like a rank metric so I'm going to argue that discounted cumulative gain is it going to be a little bit tricky to do here and that's basically because it's hard to get truth data for rankings for personalized recommendations for a large data set right and so using something like mean reciprocal rank will actually give you something where if your item is appearing at the end of a list of 50 items it'll be penalized much more than if it's peering you know fifth in that and you basically want to make sure that you're pairing as high up as possible in that really long list and so the way this works is say you have a list of three results and the one you're looking for is cats then basically you would give that list if it appears third it has a rank of three the reciprocal rank is one third and then you average that across all the queries or all the list that you generate so this will this will really give you a good metric for long lists so which do you want to use basically top-k or generating negatives and again this this depends on what you're trying to do right so fortunately the relates results are related so you can see that there actually is a nice correlation so what I've plotted here is the recall for generated zeros versus the recall for a top K list for the two models different hyper parameter runs item-based nearest neighbors versus alternating least squares implicit data and basically you can see that you'd be able to somewhat use the results from either one but you'll probably get better results when you actually go and implement your model if you just make it as close to what you're actually going to present as possible and so if you're showing a list you probably want to use top k if you're trying to predict whether or not a user will purchase something you may want to do just generating negatives it is important to keep in mind that actually taught k can be a lot more computationally expensive to generate so you know use at your own risk of spending a lot of time staring at jobs not running or not finished running all right um but anyways what's the best model right I spent a long time talking about how you evaluate models what's the winner and it depends on your data so again it's really sort of a theme here but basically I've run run the models on three different data sets here so these models or the data sets basically have so I think data one of the data sets data set to I can't remember one of the data sets is much bigger than the other two and one of the data sets is basically much sparser so it has a lot more items that are that are infrequently purchased and what you can see is that it actually makes a big difference in which item wins so this is the the best tuned model for hyper perimeter tuning for item based nearest neighbors you can see that it does the best on the first first data set whereas the alternating least squares matrix factorization does the best for data sets two and three unfortunately the inappropriate model the explicit matrix factorization does the worst on all three datasets so that's at least something you can you can narrow it down to two appropriate models if you're really hoping to do well this should really just goes to emphasize the exploration of the models combined with good evaluation is very important but the good news is that you can actually get decent answers across a wide range of data and so you don't have to be very very specialized and how you're doing it if you've got your evaluation correct one other consideration and so I mentioned this briefly is just sort of the processing time for models there's not much you can do about this except try and sort of work around it and keep in mind how often you can get away with not refitting your model and so again this will kind of depend on on how your data is structured more than size so in this case data set B actually was an order of magnitude bigger than data sets AAA or C but what you can see is that data set C actually took a lot longer to run for matrix factorization and that was just because it had a lot more items and in users so the size of the matrix was actually the determining factor rather than the number of purchases and so there's a number of things that you can do to sort of decrease the impact of fitting time basically for both of these models you can sort of pseudo update so use purchases that happen since the last time you ran your model and basically try and artificially fresh in your results that way and this can decrease the need for refitting your model make it grow stale less less quickly and the other thing to consider is actually serving time for your application so if you need results to appear very quickly and your model is taking a long time even just to compute a recommendation you may want to consider doing something like batch jobs but again this has the trade-off of making your data a little bit's Taylor right so if you're computing batch jobs once a day you're not going to be able to take into account what they just purchased so beyond beyond the purchase data which is of course what I've just spent this whole time talking about you may want to incorporate other kinds of information in in your model so if you have metadata and we do want to incorporate this basically the purchase data is a starting point for companies that have additional data we want to make our models better bring it in and so there's things like product catalogs that we want to use so information about the items information about the users I mean you can do a lot with even just IP address and a geo look up item popularity can actually be a huge thing to incorporate it into the model and so I'm not going to talk about it but I'm just going to basically say that the way you incorporate this information is is there's process called learning to rank so you have your first recommendation score and then you would have something like item popularity and basically those provide two scores you come up with weights for each of those scores and combine them to produce a new score through learning to rank so the the final point that i'm going to make is actually just around around presentation so the cold start problem is a big deal in terms of what you're going to show people so what happens when you get a new user what happens when you get a new item so with with new users it can actually just gain you a lot to show the most popular items so we saw better than a 20-percent lift just by showing the most popular item for new users but for new items you actually treat this differently right you don't want to get into this sort of loop where you have a new item so it's not in the recommendations so people don't buy it so it's not in the recommendations new new items sort of lifting those up can be really important so you may actually want to have sort of a special space for new items if you have metadata about the items you can use that to sort of boost them into recommended recommendations but basically the point is that you really have to take into account business logic make sure that the ultimate goal is coming into play with your recommendations so recommendations are a tool you want to make sure that it doesn't run rampant right so you have checks on it you make sure that it's really doing what you want in serving all the use cases and beyond the right model it's actually really important how you present these recommendations to users so just the phrasing so you know telling telling people you should really buy this versus you know people also bought will have it have an effect on what they think about it whether or not you include a picture is actually huge difference in whether or not people will actually click on your recommendations interact with them and so when you're when you're testing the model you also want to test the presentation and just make sure that the presentation is is doing the best job that it can to make your model effective and and it's not just the actual box that your recommendations appear in it's actually the context of the site right so basically when when users are coming to your site what do they expect are they looking for their friends on Facebook are they good we've really insulted if you pick if you recommend someone that they hate are they looking for a book recommendation what is their response going to be if you if you recommend them fifty Shades of Grey like is that is that going to be upsetting or not in so keeping that in mind you may have to have additional rules in place just because of the context of what you're doing right so in case anyone zoned out um basically I'll just summarize summarize what i was saying and basically the important thing is the tools are out there so don't reinvent the wheel like if you can use someone else's library use it you can always add more to it but it's it's silly to spend time rewriting things that have been written a million times machine learning algorithms are big in an iterative and spark is actually really good at these kind of processes much nicer than trying to do them in Hadoop in my experience and the the real key here is that you want to think about your use case so you want to let your data dictate your model not you know use your favorite model no matter what think about what you're trying to do think about what your data looks like and that into account when you choose your model consider your evaluation in terms of your goals so get as close to what you're actually trying to do as possible in your offline evaluation and then continue to test in the wild so continue to test after you put it into production to see how its performing reevaluate your model and continue to improve it once it goes live and then finally the the details of presentation are important important so the best algorithm in the world is not going to overcome a terrible you I if the user doesn't see it they don't like what they see it doesn't matter how good the underlying recommendations are all right thank you great so do we have any quick questions we're kind of running a little late but can you talk about the uncle ablative feature of your approach more specifically how do you define your neighborhood uh sorry in the in the nearest neighbors or just the pun on the title yeah the title oh the pun in the side of it was basically just um uncooperative in that the users aren't helping you out by giving you a rating basically you're having to infer based on on their actions on the website so based on whether or not they purchase something based on whether or not they viewed something without without anything explicit from the user um so not it not intentionally right they're not intentionally helping you you're just taking taking what they do rather than so that the by collaborative filtering is is generally applied to this whole rating so you go you watch a movie you tell explicitly Netflix how much you liked that movie which is very different from from the current model actually even at Netflix where they're basically saying so we want to know if a person like the TV show if we recommend it to them and they watch it once like one episode in that series does that mean it was a good recommendation probably not right if they watch if they watch a significant portion of the series then it's actually good and so you're having to infer that rather than the user telling you is what i mean by the collaborative partner awesome may be any more quick questions all right here's one the jacquard algorithm that you showed have you thought about pushing that back inside of spark um so I had looked and there was there was a ticket in four nearest neighbors algorithm it wasn't specifically for collaborative filtering item-based nourished neighbors but basically I decided that since since there was already already basically a bunch of people working on an eris naked neighbors algorithm it wasn't worth it to push you back in so then do you know if that'll be in 1.5 or I haven't kept up on the ticket so I just thought was there awesome well I think that's leaving us with no time but thank you so much Leah