data.bythebay.io: Mike Tamir, Marvin Bertin, and David Ott, Like2Vec with neural network embeddings
there we go all right uh so first I want to uh thank uh thank galvaniz and data by the bay Alexi for having us here to talk about this um what we're going to talk about today is uh we're dubbing it like Tove uh suggestively it's a new technique for uh recommender algorithms this is a project that has come out of the capstones um that galvaniz held with uh with skymine the uh the the company for dl4j um I have I'm Mike Tamir I'm formerly Chief science officer for Galvanize and now Chief data scientist for intertrust and uh I have with me uh Marvin and David two of our graduate students from galvaniz so with that let's get started all right right so quick run through the agenda we are going to just do a little bit of recap in the first two acts uh Matrix factorization as compression talking about stacked Auto encoders in order to motivate uh what led us to this idea for um for LC and then we will go into shallow neural uh neural word embeddings uh talk a little bit about word TC and what that is for those of us who are not as familiar with that and then move on to the uh the main results uh like Tove an application of word Toc type strategies but for recommender engines and we will go over some of the results and Marvin will help us with that all right so let's start just with a quick review of Matrix factorization thought of as compression so this is a a story an old story of how do you do say you want to do uh text classification on your documents you have Suite of documents document one through document n and you count up the terms those terms are kind of the frequen the term frequencies are kind of the properties of each document we're not worrying about structure right now um so you get this term frequency Matrix and you know documents go that way terms go that way it's very large your vocabulary so your dimensionality of the of of this space in which you're representing your documents is the order of 100,000 likely a million different terms it's the size of your whole vocabulary so we should be thinking curs of dimensionality sparsity and indeed most of those terms are going to be very sparse or sorry most most of the data is going to be empty there's going to be a lot of most of those rows are going to be sparse in that representation when we um so the problems with uh document uh text frequency representation is so we have high dimensionality we have sparse representation then we also have this thing uh which is more passive term instantial instantiation and passive term instantiation you might have chosen to use the word slacks instead of pants and there are some subtleties between these two words but um be there's not that much subtlety and in in this representation they are on completely different axes they're represented in completely different columns and so that puts more onus on your uh your machine learning to figure out the similarity on that and to combine that signal which likely have a shared signal in a lot of context for a lot of use cases what's the solution well we can use uh Matrix factorization in order to find the latent topic space how does that work we have our documents terms Matrix and then we use something like um you know ALS or nmf algorithm using an ALS to to to choose how to actually do gradient descent on that algorithm and we Factor it into a uh a a skinny but tall Matrix and a short but wide Matrix actually that's skinny butall too but you take the transpose when you're factoring and you have a representation of every document in your uh document term Matrix in terms of these latent factors you can choose the dimensions the K Dimensions that you want and you have a representation of every term in terms of those K Dimensions so um if you're if you're uh depending on how those different latent terms are represented you will have a different representation of the document and that document can be translated into the representation in the terms and you can make you can multiply Matrix multiply these two um these two matrices back and fill in the fill in the entire Blue Square the term the document term uh frequency square and you can get different representations in terms of those latent factors or sorry those latent topics something with uh we see this same this same results when we do uh user item Matrix and we do Matrix factorization for user item Matrix in recommenders so uh again you have high dimensionality again you have sparse representation even if you are the most um the the the the most aant user of of Netflix you you you probably aren't going to watch all the movies you probably aren't going to buy every item in on in the Amazon inventory and so there's going to be a very sparse representation for every user um and there's uh there's also one class uh CL one class representation just because you didn't buy a product yet doesn't mean it's not a product that you want to buy in fact a recommender that only uh recommends products that you've already bought is going to be a pretty crappy recommender and so um this is this is called one class uh classific one class representation and it's going to be when you're doing working with implicit purchase data it's going to be similar to that uh passive term instantiation solution Matrix factorization again you have your users you have your latent factors you uh you factor it using you know latest and greatest something like NF with ALS or more advanced versions of that and you can represent each user in terms of their latent features things like uh interested in sci-fi interested in action adventure interested in romantic comedies which by this algorithm will tend to um to Bubble up as columns uh when you look at the at the factorization so why am I bringing this up one way to think about what's going on when you do this factorization is what you're doing is you're you're actually compressing the information you're taking uh the the big uh the big insight to collaborative filtering and Matrix factorization is that um you know users can be represented in terms of the things they buy problem is curs of dimensionality so we have to compress that High dimensional representation into a dense Rich low dimensional representation that's what Matrix factors is doing the low dimensional repr low dimensional representation is the uh the latent feature space all right so that's one example that's a linear example or an example of a linear mapping for um compressing the high dimensional signal into a lower dimensional signal let's talk about another one just for contrast that's that's nonlinear it's stacked autoencoders this is a one of the first breakthroughs in um in in deep arbitrary deep uh learning uh neural Nets um so this is a nonstacked auto encoder this is just one Auto encoder what it the way it works is you have your input data your X data um you map it down with a matrix W that that is is um you know shorter than it is wide so it takes a long X vector and produces a shorter y vector and then you undo that um you to get a z vector and then you compare the between the input vector and the output vector and the idea in St in Auto encoding is that you want to minimize um the loss the information loss by squeezing it through that keyhole in the middle and and you you can pick your own loss function and what you do is you actually train based on that loss you do your gradient uh your gradient descent on that loss um and then you can repeat so you clamp the ends um and then you do another level of of Auto encoding and so you can continue this um a INF itm to 2 N plus one different layers and what you're doing is you're compressing by orders of magnitude the input Vector down to that middle y um y y uh nodes and what that does is that actually compresses the information it compresses the information can be effective in a lot of different contexts uh turns out that it's uh well um and then once you once you do the compression you can add your favorite classifier at the end often it's uh you know you do some uh some some fine tuning uh by supervised back prop and you get your answer whatever it is with that compressed representation that Y2 representation in this case um it doesn't work as well as you would like for text or for items um first of all why uh well it's fundamentally unsupervised what it's what it's doing is it's saying I want to preserve the information but I don't care how I preserve I just want to preserve it and um and it does that it does that with um non- Illuminating and nonlinear Transformations at each node each layer in the the neuron net it's is doing it's adding a layer of nonlinearity and what that does is um it it seems to or it suggests that what that does is it actually um eliminates some of the important structure that we want to keep that is represented in our in our language at least in this case that in the co the co-occurrences of different terms it doesn't um help as much as we would like because um you know something about moving or adding those nonlinearities in our compression um actually obfuscates the signal it doesn't preserve the signal or or make it even easier to detect all right so um so that's kind of like the the gun in act to um you nonlinearities can hurt maybe we should use linearities and um so we'll we'll see that in a little bit um so let's talk a little bit about word word has uh it was developed over a series of papers and it's really revolutionize how we work with text uh this now in 2016 it um it is a uh simple uh continuous Vector representation for individual terms so it's um just a quick a quick I'm going to go through the algorithm but a quick uh review of the highlights um so it's uh it's trained to specialize in sentence context completion so uh so you have a simple neural net of three layers and it's um trained the way that that compression is trained actually is for uh sentence completion like continuous bag of words Etc um it seems like what it's doing is it's actually um captur ing information about co-occurrence or um you know this recent results suggest that it's actually capturing information specifically about Mutual information pointwise Mutual information between the terms um and then uh it encodes conceptual relationships and we'll give a very um well Trot an example of that in a moment what I mean by that okay so I'm I am going to explain the algorithm real quick because it's important to understanding the next stage which is how we use the uh this sort of or this style of algorithm oh this style of algorithm for for like Toc um okay so so real quick we have our um what what we do is we we're Pretend We're trying to do a a sentence completion an engram um algorithm where we have uh the cat on the guess the next word so we take those words and we project them uh we give the projection the indicator Vector which basically is as long as our vocabulary say a million Dimensions long and uh it's all zeros except for a one for um for or whichever word represents that specific Dimension so if we have all our vocabulary alphabetically then a is the f is one and all zeros and so forth an is yeah an is a is is O is a two and all zeros oh yep uh and so um so we we project that for several words the cat on the and that's the context of the term and then we uh then then we send that through um into the projection layer we map that with a linear mapping and W is just a matrix so it's a matrix that is in this case say if we have a million dimensional uh vocabulary then it's 3 million wide um so we have a 3 million long Matrix to if we want to project down to say a 300 dimensional uh Vector Space by 300 dimensions and um that's how we get to this H layer this hidden layer then you do your nonlinearity with activation for function of your choice and you map into um into into predicting the most likely word you add a probability assignment to each of those words with something like a you know accent or um you choose your poison and so the word that is get the highest probability of coming next is um then trained and cross referenced by the um by the training data by the label data um compared to the word Matt do you if you have any questions please feel free to interrupt umuse Alm just try to figure you use um yeah so this isn't our algorithm this is the word Toc algorithm but but yeah back propop is or um you know backrop with uh with other optimizations would be the way that you would you would train this and and the parameters remember the parameters here are the um the W Matrix the the entries into that Millions by hundreds uh Matrix and then uh and I'm skipping a lot of details here I'm just trying to get us the Gestalt of what it is um then you would you notice that that you have a matrix that's 3 million um actually you want a matrix that's million if your vocabulary is 1 million by 300 so you would you you would you would find a way of aggregating each of those three projections that that represent each of the context terms um and you would probably do multiple passes with multiple ends so there's a lot of details here that we're skipping but the general idea is that you feed it in here you project it down linearly you do a nonlinear a nonlinear activation and then you use that to project the next word or continuous backwards is another common task and the cool thing here is that the the the word Toc Matrix is almost like a pleasant side effect that's incredibly valuable from just training it to do this task and the pleasant side effect is that now we have a method of mapping every single term based only on say its position in the vocabulary it's the nth word in our list of words in our vocabulary of words and um actually captures the semantics and so this is uh one of the most popular examples of that you have your uh King uh your king Vector your queen Vector your woman Vector your man Vector you find the difference between the uh woman the man vector and um and then you add that Vector to the king vector and lo and behold you end up being Epsilon close to the queen Vector which is a very cool um cool thing and and suggests that um that WC actually captured something about the semantics of the terms in compressing it doesn't just map to smaller number of Dimensions it also captures something about the meaning the geometry in that representation is is semantically significant um okay so and that also means and this is an important point for something we're going to be talking about later um Direction matters too there is a femininity Direction uh or there's a maybe a higher status quote uh direction that is also captured in the representation in this Vector space so you can use this also to um to represent documents for instance um so uh you take your documents you might remove the stop wordss you find the um the the aggregate of those words and now you have a way of representing the entire document in terms of the instances of the words themselves um and you can do this both in a supervised context or unsupervised context now you've uh you've what I've just done is is shown away with naive drve if you take the average or the l21 norm or L2 or L1 Norm of this Vector um you have a direction of the document and that direction of the document um has other words that are also embedded in that very same word toex space and so you you can do unsupervised um text classification you can do supervised text classification there's all sorts of different uh ways that you can really take advantage of this representation all right so I do want to um move on because I want to make sure that we have enough time for the for the juicy stuff um there is just as a as a uh a side for questions um there are more advanced versions than just naive drve we can talk about that in question answer if we want all right let's talk about like Tove so um like Toc what we want to do is we have our user item representation the the items that every person watched or read or listened to or purchased and we want to figure out a way to semantically embed that semantically with quotes um into the vector space into a lower dimensional Vector space in a way that captures the significance of these purchase patterns or watch patterns um so let's reflect on what what I very quickly went through number number one it's fundamentally linear um in the case of of of represent of of representing words and also suggest it's suggested that it's fundamentally linear um at least in co-frequency co- purchasing for uh purchase patterns that's part of the reason why um why maybe M Matrix factorization uh works so well this is just a suggestion uh it's suggested by the evidence it's not um it's not something that that is definitely true and there are certainly other um nonlinear uh you know ways that we can use deep learning for um for for text and for items but in this uh in this specific context it seems like it's fundamentally linear um it's reconstructing uh cooccurrences uh and the underlying model is actually um the mutual information graph so what do I mean by that um with the word Toc what we're doing is we're taking documents which are these um the these it's it's a random variable or a string of events that represent conditional random variables or random variables conditional on the uh result of the last the last term um the last random variable outcome and what happens there is that um you know the we can you can kind of think about that in terms of a graph structure where um each word is a node and what you're doing is you're randomly walking from one node to the next and there's a probability of going from one node to the next and you can actually wait those probabilities um by the mutual information of term to term in the graph and so um one thing that the deepwalk algorithm does this done by perosi and and his team over in Stonybrook is took that one step further instead of just restricting it to the um the representation of co-occurrences of words as a string of random variables um based on an underlying model like a graph model um and then treating each document as an instantiation of a pull from that graph model uh they just went straight from the graph model so they take an arbitrary graph um bidirectional they uh treat words as node and and here for the for the Deep walk words aren't actually don't actually need to be words they can be anything but um they the um each node represents something like a quote word in generating these strings and as it randomly walks we create a quote graph a qu a quote document which is just a string of T steps randomly walking this graph so we could do this with words and with actual documents we could do this with any graphical model that's symmetric and then everything's the same and you still run it through the um the say the the like the WC um three layer shallow neural Nets um you could do continuous back words skip gram or you or you make modifications as appropriate and what you end up is a end up with is an embedding of the graph structure in a much much lower dimensional representation so you get um so you input a sparse graph and you get a mapping of the nodes in that graph into a say two-dimensional space in this toy example all right so let's talk about um go back to the recommender case right the recommender case we also have sparcity issues just like in text so the natural inference that drove what we did here was thinking about that sparsity and um you could use code you know the user item Matrix is not a symmetric Matrix but if you take the coari Matrix of these so you multiply by the transpose you could get a symmetric Matrix that's item by item you can even get a symmetric Matrix that's user by user typically the user by user user user base if your company's doing well is going to be way too big to deal with it way too many dimensions even more than the number of items that you have but if we could compress it somehow we might be able to take deep advantage of that user symmetric Matrix um you don't have to use covariant you could use other cases like Mutual information uh log likelihood ratio which also scales with mutual information um and in our specific uh results that we're talking about today we're We Used Log likelihood ratio um so log likelihood ratio does a couple things it is the ratio of the likelihoods of two models it um it computes a score that analyzes the counts of the events as they Cur together it tells you how many times more likely the two items are to co-occur as as not so it um it it is a measure of the uh probability distribution in a sense of a randomly pulling from um from different say uh purchases as a distribution over um over the different items in this case and it um it does something you know there's a log in there and much like when we do tfidf that helps to control for commonly occurring items or commonly occurring words in this case commonly occurring items so it solves um what what the uh the quote banana problem that you might remember from uh from uh Market Basket analysis everybody buys bananas so if you don't conditionalize you end up recommending bananas to every purchase every basket um okay so uh let's talk about the like Toc recipe the like Toc recipe um is uh fairly straightforward you take your your your symmetric Matrix that symmetric Matrix could be uh represented in any of the similarities of item item user user um then you leverage that density um so you can look at uh for instance embed embed the users look at the other users that are close to that user in the dense representation space the like Toc mapping space and um and and then you can uh for instance see uh what other what other um ratings did they give for for a movie or an item that you uh that that you want to predict a rating for for this individual user and because they're so so close in this representation space you can get a uh a good sense of what they what the actual user in proximity to all these other users would assign for that particular space or what they might purchase Etc um and then you can do this not just for embedding the user you could also do for the items now saying this about the items doesn't isn't as intuitive but for a given item you could look at the other items that are similar to that and if you think of say star ratings or being purchased by as the relation with users now um then you can uh start to uh then you can start to fill in what the um what a particular user would write would rank that item as all right and now for the results which Marvin will talk about some of these results which are very cool thank you um okay so I'm I'm going to talk about some of the preliminary results we have so far and um some of the some of the new approaches we've been taking with the like Tove um so for any uh machine learning algorithm it's very crucial to pick the right evaluation metric that is in line with the task you you're you're going to perform form in in the field and so for recommend the system uh the most widely used metric is actually imsc the would means crate error um and it turns out that this is actually not a natural fit for evaluating tasks that try to optimize the top Ed recommendations just minimizing imsc doesn't necessarily uh translate into accuracy improvements um what MSC does it captures the average error between the true rating and your predicted rating and so what what's wrong here in practice when you're actually recommending movies you really only care about the best matches the most relevant the most valuable item you or movies you want to recommend to that user and so those items are the ones that are going to be red five stars maybe four stars but not lower uh so for example does it really matter if you predict a rating of 1.2 and the true rating is one then do you really want to optimize that it's never going to be this movie is never going to be used in your recommendation so with imsc you waste way too much training time trying to optimize to correctly predict readings for items that you're never going to be you're never going to use they're Irrelevant for that specific user so we actually need an evaluation matric that only concentrate on highly relevant highly viable um movies and only optimize and recommend on those movies and so what we use is a metric that's called record at end and so it's based on on ideas we have with accuracy recall and precision those are well-known metrics that is used uh in uh machine learning classification algorithms so we take the same intuition here and we refactor the the scores into um something that can work with recommended systems so in a nutshell the idea is to take your test set and only keep your highly weighted movies the movies that are red five stars and so here the Assumption here is that in your test set you're only going to have highly re relevant highly viable movies that you're going to try to force your recommender to predict to that specific user and for each of those highly rated movies you're going to pick a thousand random movies that the user hasn't seen yet and so here the idea is that those random movies are going to be on average of less interest to that user of course within that thousand there are probably going to be a couple movies that are in fact pretty relevant and pretty good recommendation for that user so it's good to keep in mind that Reco at end gives you a measure of recall but that is a lower bound to what you actually will find in practice when actually use the recommender system so you take those 10,1 movies that you bundle together and then you Fe read that through your recommender system and you try to rank them and retrieve as as best as possible your test set data and you do that by Computing some kind of similarity between that movie so just to backtrack a little bit we start it with a high dimensional graph that represents the interaction between your movies and we take that high dimensional sparse data and we squeeze it through the like to V algorithm to represent it into a dense representation of Rich latent features and with those features we can perform operations in the same way we perform the operation with lack to V what we do here is for similarity we do a cosine similarity which is a simple dot product between one vector to the other so what is the dot what is what do a represent the dot product it's a projection of one vector along all of its Dimension into the other dimension of the other vector and that gives you a much much richer um measure of the the similarity across all those dimension for that specific movie and then we rank those into a list and we see okay where in that rank list where we able to retrieve that specific test set data so the way to recall to calculate recall is at such um you simply count how many times you're able to retrieve that data for a specific range of n so N is a number of movies you allow yourself to recommend so usually it could be just one if you want to recommend only one movie at a time could be four five or 10 depending on your application but it's usually it's not a big number and so you count how many times you retrieve that movie divided by the total amount of data in your data set and you repeat that for different values of n Precision is is similar in a way that you take recall and you normalize that by that range value you have n and that normalizes your value by saying how precise how consistent are you at recalling a great movie a highly relevant item as we in decrease the space of the recommendation so here are some of the results we have uh this is a graph of Rec n on the left we've got uh the recall percentage and at the bottom we have rank n which is that um that that list will allow ourself for the recommendation so we've got two lines we've got in blue the L likelihood ratio so that's a simple recommender system that only is based on that uh normalized likelihood of cooccurrence between two items and in green we have that locked like to Vex algorithm that uses that embedding space to make the recommendation so what's striking about is that we do have a crossover at one points but we need to remind ourselves that the task of a recommander is to perform as well as possible for short number of N and that's really what we're looking for we're looking for an algorithm that is optimized for only U um predicting the best movies as early as possible in the recommendation and it doesn't matter if it recommends a movie Down the Line we really want it to recommend the good movie right at the beginning and that's exactly what we're seeing right here the the behavior of like Tove is that even at Rec if even if you can only recommend one movie then you're already getting twice the we or percentage uh compared to the log likelihood ratio so this graph is very similar um instead of having the rec or percentage we're having the rec frequency which is the number of hits we're able to get for that specific number of N and what you're looking for is you want a line that is as close as possible to the Y AIS and that means that you're able to recall a lot of very L relevant movies and great movies for for a small number of N and so we can see here that like is able to get more than twice the number of great movies for that for short number of n compared to the log likelihood ratio okay this graph may be a bit confusing at first but what we have here is we have Precision on the left and then we have recall percentage on the right and we have again that crossover that's happening here but what's important to note is that although the log ratio seems to perform better at at the bottom right it's actually um a region of the recommended that will not be used in practice because that basically means that at such low decision you're basically telling the user among a few hundred movies I'm 90% sure that there's at least one movie that's great right but that's not what we're trying to do we're trying to recommend a movie given a very small list and that's where like toet is performing well it's achieving high percentage High Precision scores while maintaining a good recall percentage um so here I'm going to talk briefly of scores we get using imsc uh of predicted ratings um I did say that armac is a bad metric for eving recommended system but nonetheless like toet performs relatively well even with that uh metric so here we're looking at a recommander without embeddings so using a onedimensional symmetric measure using like to V ratio and we're calculating the prediction using the topk most similar movies seen by that user and we see an interesting uh Behavior where as you increase K you actually get a decrease in performance when you just take a naive average of the closest movies and it's only when you take weighted average of that movie that you get a nicer behavior and you get a convergence of your of your results we like to v um it's it looks quite different so there's three things that we need to notice about this um first of all the error is much smaller compared to the other one secondly as you increase SC you're actually getting significant Improvement in the prediction error and then regardless of having the a naive average or voed average you actually get very similar score and that's come from the fact that we're calculating similarity not based on one dimension but based on that projection across all the dimension in that hyperspace given those uh highly Rich embedded vectors so this this is basically some of the prary results we have right now we're working on a lot of other things and we hope that we show show that later I think we just have two more sides left and uh Mike time is going to take over and finish up all right thank you [Music] [Applause] [Music] Marvin so um so as Marvin mentioned there there are a couple of directions that we are taking this uh going forward um one of the ones that that uh really stands out and that anyone who's worked in the uh in the recommender space probably has run into this is there is a lot of motivation for not just figuring out what um what somebody would want to purchase also what somebody would want to watch also what item a user would want to also get but also time ordering so understanding the order in which U you know get you know watching this movie and then watching that movie versus the other way around or purchasing apple and then banana versus banana then Apple um so in order to capture some of those asymmetric relationships that sometimes happen uh where you know if you think about the way that the Deep walk algorithm actually works there's nothing intrinsic about um the The Waiting from one way direction to the other um being the same so it doesn't in other words need to be a symmetric graph in that sense from items to items or from users to users it could be an asymmetric graph and so um we are working on some research search for generating uh generate generating recommendations generating results when you look at that a to try and get time um time correction something else that is uh is interesting is remember that there are um when we went to the word case we had directions in the in the actual geometry of the embedded space so there was a say femininity Direction uh or a masculinity Direction a a a class stature or wealth Direction um there is very likely going to be similar structure to the geometry of the embedding in the um in the like of X space and so taking advantage of that looking at um at subspaces or hyperspaces where we can actually um actually uh give context to the kind of recommendations we want to do um sub selecting for time for instance uh all of that is very rich way that we can start leveraging this uh this like Tove compression all right so let's uh wrap up here with the conclusions now you know uh starting with there there are powerful parallels in text and preference data uh it's very powerful with with data sparsity management um the taking advantage of the linear structure which seems to exist both for item user and for text uh and this goes back to in the text case back to distributional Structure Theory um for word embeddings um we have taken some of the the huge advances that we've seen with word TC and similar neural word embeddings and applied that to the user item representation um options our opportunities in particular recommenders and so uh we have represent or we have presented the like Toc algorithm and some results in initial results that we're getting with the like Toc algorithm and how that measures up to traditional methods of doing recommenders which is very promising so thank you very much and uh this is the team uh you know again uh uh Marvin Burton and uh David O have been able to join join us but we also have Mike Ulen who is ALS and Adam Gibson who are also part of this uh this project so thank you very [Applause] much