Text By the Bay 2015: Alex Minnaar, Scalable Online Learning of Topic Models with Spark
Recording: Text By the Bay 2015: Alex Minnaar, Scalable Online Learning of Topic Models with Spark
uh before i start i should say that this is a 20-minute presentation but we have a 40-minute slot so there'll be plenty of time for questions um right so my name is alex minar i'm a software engineer at vertical scope and my talk is on the online learning of scalable topic models with spark so before i get into topic modeling i'll talk a little bit about vertical scope which should hopefully give you some idea as to why topic model would be would be useful for us so vertical scope is an online community of forum based websites in many different verticals including automotive power sports technology health but most prominent is automotive which is what i'll be talking about today and just to give you some idea of our of our scale we have over a thousand uh sites 42 million registered members 84 million monthly visitors 1.2 billion posts and those numbers are growing so there are thousands of discussions and conversations happening every day on our forums and a fundamental question we want to answer is what are these topics of conversation so this is useful for us because we want to know what our com our community members are interested in if we're able to identify the the presence of a topic in a form thread then perhaps we could uh tag or classify uh threads by those topics and we could also use topics in combination with other nlp tasks such as question answering name dandy recognition and and trends and trend analysis so before we go any further we should probably um clearly define what topics are and how we can learn them so topic modeling is a branch of machine learning and natural language processing the most popular topic modeling algorithm is leighton dirichley allocation or lda so in lda given a corpus of documents topics are modeled as distributions over words and documents are modeled as distributions over topics so lda is a generative model which means that for each word position in a document a topic is sampled from that document's distributions over topics and then the actual word in that position is sampled from that sample topic so this this diagram tries to illustrate that um but the reason why topic modeling is very useful is that if you look at the high probability words in a topic they should have some sort of thematic coherence so here's a topic we learned from from our data which seems to be about the theme of batteries we know this because some of the high probability high probability words are words like battery charge voltage charger current etc and in a similar way if you look at the high probability topics in a documents topic distribution these topics should describe in some way what that document is about so i don't want to get too deep into the math behind the lda algorithm but uh basically given your corpus of documents lda tries to infer these probability distributions that we're interested in but these distributions are intractable so approximate inference techniques have to be used like variational inference which turns the inference problem into an optimization problem which can be done with a which can be solved with an em style coordinate ascent algorithm so here's the pseudo code for this algorithm uh basically it has an e step and an m-step in the e-step you're trying to update your local per document parameters while keeping the global parameters fixed in the m-step you're trying to update your global topic parameters while keeping the local ones fixed you iterate between the e and the m step until you converge but the thing to notice here is that in the e-step you have to make a full pass through all the documents in your corpus i'll come back to that later also from an implementation standpoint uh topics are generally stored in some kind of topic word matrix uh here for example the the columns are the topics the the rows are the words in your vocabulary and the entries are the probability of that word in that topic so this is sort of like the sufficient statistic for an lda model so it holds all the topics if you want to infer the the topic proportions in a document you would select the the rows corresponding to the words in that document run the e-step on it and and one of the results of the e-step is is the topic proportions um so there's advantages and disadvantages to lda the main advantage is that it's completely unsupervised it can learn these topics without the need for any annotated training data at all it's very intuitive particularly for our use case um threads in forums can be can be easily thought of as documents in in a corpus and it also has a really nice sort of built-in document tagging or classification system this is because documents are distributions over topics so you can tag or or classify a document by its high probability topic uh the disadvantage is that in its current form it's not very scalable and the reason for this is as i showed in the e-step it requires a full pass over all the documents in your corpus if your corpus is the size of ours this is not this is not feasible also there's no clear clear way to update your ld your lda model if new documents arrive in your corpus so obviously for us uh new threads are constantly being created we want a way to efficiently update our model once these new threads come in rather than re-running all of our our documents in batch uh so this led us to a new strategy which was the online lda algorithm so the way the online lda algorithm is instead of learning our topics from the full corpus we sequentially sample many batches of documents and we update our model based on these mini batches in an online fashion so the general procedure is you sample a mini batch of documents from your corpora you perform the e-step on that mini batch so this is the same the same e-step as before except now it's on the mini batch not the full corpus this creates a set of intermediate topics and then in the m-step you merge these intermediate topics with a set of overall topics so online lda solves a few problems uh for one it's now more scalable in terms of memory you only need to keep one mini batch of documents in memory at any given time rather than the whole corpus and also updating the model is easy once when new documents arrive you can simply update the model as you would any other mini batch but for our use case it's still not as scalable as we'd like for instance if you consider the case where you want to learn a topic model on all of your all of our historical data so this would be a lot of many batches to process and it would take a a very long time and also consider a case where you're prototyping your models you're tuning some model parameters you don't want to wait hours and hours and hours to wait for the result also new threads are coming in really fast so we'd like to update our model as quickly as possible too so we can speed things up if we process each mini batch in a distributed fashion um so uh we distributed uh online lda and the way we do this is we sample a mini batch of documents as we did before but now we apply the e-step to each document in the mini batch in parallel then we aggregate the results and then we perform the m-step as before so we needed to choose a distributed processing framework in order to implement this we chose spark i'll tell you the reason in the next slide but right now i'll just give you a very very basic overview of spark so with spark all all distributed computations are done on rdds rdds are data structures that are distributed throughout your cluster you can perform two main operations on them transformations and actions with transformations you perform a computation on your original rdd that results in a new rdd so these are operations like map filter flat map actions are computations you perform on your rdd that have a local result that's returned to the driver these are things like result count collect um but the real reason why we use spark is because it works really well with distributed iterative computations so the reason why it does this is is because um uh spark keeps rdds in memory as much as possible so if you were to uh try to implement a iterative computation on one of spark's predecessors then at each iteration you have to you'd have to read and write from hdfs um so with spark you don't have to waste time with this disc i o and it makes makes iterative algorithms much faster so really spark is the only option um right so now i'll get into how we implemented online lda with spark so we treated each mini batch as an rdd of documents we treated our global topic word matrix as an ml live index row matrix which is basically an rdd of of matrix rows and their indices we applied the e step to the minibatch rdd via a map transformation followed by a reduce and these are the intermediate topics then the m-step is performed by by joining the result of the e-step with the global topic word matrix and then another transformation is done to to actually merge the result so here i've i've included a diagram just to reiterate what i just said you begin with a mini batch rdd there are two pre-processing transformations you have to do so you have to put each rdd in a bag of words format then you have to extract the row of the topic word matrix corresponding to the word in in the bag of words so now it's in the format where you can apply the e-step in terms of a map then you aggregate the results by a reduced by key where the where the key is the word um this gives you your set of intermediate topics which you then uh join with your global topic word matrix again where the keys are the words um and then another transformation to actually merge them um right so so we implemented this in spark and then we applied it to one year's worth of our data in our automotive related websites and as you might expect we discovered a lot of auto related topics so generally these correspond to actual physical aspects of a car so things like lights batteries tires wiring but also sort of general auto related topics so things like mileage pricing dealerships things like that but uh our forums also have a lot of uh sort of off-topic conversations so we we also discovered um topics corresponding to those so things like sports politics law enforcement movies tvs food food drink things like that and also sort of unexpectedly we discovered some topics that seem to be related to spam so things like fake documents passports some health and pharmaceutical related spam and i'll get back to why this could be important later so i also wanted to give an example of topic detection for a thread in our forum so at this point assume we've learned we've learned our topic model uh now we want to sort of infer the proportions of topics in um our documents which are threads so you probably can't read that but um this is a typical threat from one of our forums so a user has um has a car that is experiencing problems with it specifically there's a squeaking noise coming from the belt and pulley system within the engine uh so he's sort of appealing to the other community members to help him troubleshoot the issue so we inferred the the high probability topics within this thread and their their topics like belt and pulley noise and sound repair and replacement so i think you can agree that these are very relevant topics for this thread and you can see how we would want to sort of classify or tag this thread by by these themes right but there's there's also some other use cases for topics uh number one if you remember um in the topic discovery section uh there were some topics that we discovered corresponding to spam so why this is useful is if if we uh infer the top proportions on a sample thread and it seems to have have a high probability of uh of spam topics then that means there's a there's a good chance there's some spam in that thread we could also do things like combine topic modeling and named entity recognition uh so we had previously trained the named entity recognition model to um identify mentions of automotive makes and models and then link them back to a knowledge base of automotive makes and models so what we can do now is not only know when an automotive maker model is mentioned but also the topical context in which it was mentioned which is pretty useful um we could also do things like combine topic modeling and named entity recognition and anomaly detection so so now we can detect sudden spikes in mentions of automotive makes and models in a particular topic and this could indicate the presence of some kind of event for example it could it could mean that an automotive recall would be happening in the near future so there's lots of use cases for this and we've got lots of time for questions yep um well i would say that there is there is a parameter that you can tune uh sort of in the m step that sort of uh determines the influence of new of new topics with respect to uh ones you've learned so far so so i'd say tuning that parameter might be a good idea um yeah i'm not sure i haven't even really explored that problem yet but yeah i'll get back to you yep is that hasn't shown up in a topic i've seen i mean there's topics with a lot of like derogatory words in them which obviously i haven't haven't shown you guys but uh yeah that particular one i haven't seen i'm not i'm actually not sure that word is in our vocabulary so we might not have been able to yeah yep uh you mean like over or sequentially i mean we haven't really benchmarked it or anything but um well i mean i could i can tell you that uh uh the talks that i showed you were learned over 2014 and was approximately 200 million posts and that was uh learned in under half an hour so i hope that answers your question you imagine the end out from scratch or you have a favorite implementation than what you were able to respond to uh yeah so the name to recognizer was we obtained training data from from crowdflower and we learned it with the stanford uh named any recognizer tool um but yeah they're completely independent with uh from top model right yeah i mean empirically i have done that uh they don't change that much i mean i i i suppose that's that's uh that has to do with a particular data set that you're working with um so we didn't have a particular method we just sort of had a human look at it but uh yeah i'm sure there's more work that could be done i guess before you release yeah that'd be a good idea um so we have operationalized it so we've learned our topic model all of our posts are in elasticsearch um so we we can we've included elasticsearch fields uh corresponding to high probability topics in that post so we learned our topic model then we re-ran it over all of our posts and and tagged them with the appropriate comments that's it you