SBTB 2015, SF Scala @Nitro: Alex Minnaar, Introduction to Topic Modeling and Evaluation Techniques
okay so yeah my name is Alex manorama research engineer here at nitro and my talk is an introduction to topic modeling and also some associated evaluation techniques so just an outline I'm first going to talk a little bit about what topic models are in general and what they're used for and then I'm going to talk about how topic models are trained and then how they can be trained in a scalable way and then finally how do we evaluate our trained topic model and then and then a short demonstration of a skylit implementation so what our topic models topic models refer to a collection of unsupervised learning algorithms that try to uncover the hidden latent structure within large document collections so this this hidden layton structure is encoded in what are known as topics so at a high level topics are our clusters of semantically coherent words so here's an example from our own nitro corpus of documents so this topic contains words like financial capital investment bank so clearly these are all semantically coherent words and you could say this is a topic about say finance or something so the reason why why these topics are so useful is because they're often human interpretable like this one so all you have to do is look at this topic and you can know sort of the the themes and ideas that are present in your large document collection without actually having to go through and read read every document within it so essentially topic models create a low dimensional representation of your document collection so the most popular topic modeling algorithm is Layton Deerslayer allocation or Lda so that's what I'm going to be talking about so lda was initially proposed in a paper in 2003 by David blah Andrew Inge and Michael Jordan so an Lda topics are defined as distributions over words so in this distribution the high probability words should be human interpretable so they should like those those financial aid words I mentioned earlier and then the documents are defined as distributions over topics so here's a good a good illustration of lda so on the left you can see the the corpus level topic distributions over words and then and then for each document you have a a per document distribution over topics this is called the the topic proportions and it's assumed that that each word in the document is generated by first sampling a topic from the documents topper proportions and then sampling that word from that topic which is again a distribution over words so what are topic models actually use for in practice so they can be very helpful for searching and browsing and summarizing your document collection so so consider you have your document collection you run lda on it you get your topics back what you then can do is is go back over your documents and infer the top of proportions within them and then look at the high probability topics within those proportions and then give give your documents informative labels based on on those topics so then what you can do is you can you can browse your topics in an intelligent way so think of the way gmail sort of categorizes your email in there their primary social and promotions tabs you can do the same thing with with your your topics as tabs you could also insert your documents and their their corresponding topic labels into a searchable database like elastic search and then perform faceted search based on topic so say you have a user that wants to search for a keyword but only within say documents with a financial topic so potentially the the results would be much more relevant if you could facet by that topic and it's also a powerful way to measure the similarity between two documents so you can do this by comparing the topic proportions between each of those documents and this is very useful because you can you can potentially have two documents that don't share any words in common but if their words sort of belong to the same topic then their topic proportions would still be similar and you can you can you could discover that there are actually similar documents in that way so that so there's lots of different applications the list goes on excuse me so an important question is is how to actually train your topic models so here's the the graphical model for lda so so so you have your observed words w which which is the the shaded node so all these nodes are our random variables and then you also have the per document topic proportions which are theta so there's there's assumed to be M documents in your in your corpus and you also have k k topic distributions which are parameterised by a fee they're so so when we say training a topic model we mean we want to compute the posterior distribution of the per document topic proportions as well as the global topic distributions given your observed documents so this is an intractable distribution so you have to use approximation techniques like variational inference so the way a variational inference works is you have your an intractable posterior distribution and you try to approximate it with a flexible distribution that you can sample from called called the variational distribution and this variational distribution has free parameters corresponding to your hidden variables so your per document topic proportions and your global topic distributions and basically you optimize these by by minimizing the KL divergence between the variational distribution and the posterior and you end up with some update equations for each of these two variables and they both depend on each other so you can solve this with a am style coordinate descent algorithm which shown here so basically you start off with some randomly initialized topics then in the east step you iterate through all the documents in your corpus and you update the the the local per document top of proportions of each of the documents and then in the m-step you update the global topic distributions based on those updates and you basically iterate between the e step and the m-step until you converge so there's a problem here in terms of scalability so you see in the east step you have to iterate through all the documents in your corpus between before you can have a global topic update so obviously you need all of your documents in memory in order to do this so if you have a very large collection of documents this is impossible so you can solve this problem by transforming this into an online learning problem so this was done in 2010 paper called online learning for Layton Deerslayer allocation so basically in the east step instead of iterating over your entire corpus you could actually just take a mini batch a sample a mini batch of documents from your corpus and perform the east step on that and then you get a set of intermediate topics which you can then merge with your overall topics in the m-step so again you iterate between the e step and the m-step and sequentially sampling mini batches so so now you only need to have a mini batch of documents in main memory at any given time rather than the full corpus so this sort of solves the the memory issue but still if you have a very large document collection that could mean a lot of mini batches to process so it could be prohibitive in terms of time so you can mitigate this by using distributed computing like like spark for instance so you could distribute your mini batch of documents within an RDD and perform the east step on each document of the mini batch in parallel and then aggregate the results so this way you can process larger mini batches so you can get through a large document collection much faster than then if you were to do it on a local machine right so once you've you've learned your topic model you want to know how to evaluate it so this is an important question because the LDA algorithm has a input variable called K which determines the number of topics that you will learn so a coma a common question is how do you know what to set K to for your particular corpus so if you can evaluate it a topic model then you can do a simple line search to find the optimal k value so there's basically two different ways to do this one way is using a statistical evaluation technique called perplexity so what this is is you initially divided your your document collection into a training set and a test set you trained your topic model on your training set and with with those parameters that you learn you can compute the predictive likelihood of the test set so this is basically how how like surprised your topic model is of these new documents and and basically if the predicted likelihood is high then this should correspond to a high quality model and vice versa so however there was a paper written in in 2009 called reading tea leaves how humans interpret topic models and in this paper they carried out a large-scale human Mechanical Turk Amazon Mechanical Turk experiment where basically they showed people learn topics and they asked them to sort of evaluate the human interpretability of those topics and the results actually said that topics that were highly human interpretable were actually not correlated well with with topics with high perplexity and in some cases they were actually anti-correlated so this sort of threw into doubt this evaluation technique so then people began to to use other evaluation techniques that try to model human interpretability directly so the idea is if if you look at the high probability words with of a learned topic if they are semantically similar to one another then then that should mean that they are human interpretable so so in order to yes sorry of the previous point well yeah I mean I'll give examples later thumb so so so one way to evaluate sort of the semantic similarity between two words is to use word vectors so so I'm not going to get too deep into what word vectors are but they can be learned via unsupervised neural network models so these neural network models compute vector representations of words that seem to encode their semantic information so there's a couple algorithms that do this so word tyvek and also glove from stanford so basically we we know that these word vectors encode some sort of semantic information because if you look at a word like France and its corresponding word vector and then and then look at what what words are similar to to France in terms of their cosine similarity to their respective word vectors you see words like Spain and Belgium and Netherlands in Italy so clearly there's some sort of semantic information being being encoded there right so we use this we can use this to sort of evaluate the coherence of the words within a topic or the human interpretability so basically the general formula is you take the high probability words within the topic and then you compute the average pairwise cosine similarity between those words corresponding word vectors so basically topics with high coherence should be highly human interpretable so for example we we did this on our own topics that we learned from our own nitro nitro corpus so we ran a 100 topic LD a model on our nitro corpus and then we computed the word vector coherence of each of the learned topics so on the left you can see the top 5 topics by word vector coherence and on the the right you can see the bottom five topics so I think you'd agree that the topics on the left are much more human interpretable than those on the right so now I'm going to give a short demo so in this demo I'm going to learn a small topic model on a small sort of test corpus so this corpus is is 1740 papers from the the nips journal which is a neuroscience and machine learning journal so our learned topics should reflect this so we're going to learn 20 topics from from this corpus and using online lda of course and using a mini batch size of 30 documents so and then also once we've learned these topics we're going to try to infer the top proportions of a particular paper called learning by state recurrence detection and I'll just show you that paper well I don't expect you to actually read this but but basically I chose this as an example because this paper sort of combines reinforcement learning and also neural networks so the top proportions should reflect this that it sort of has two high probability topics in its proportions so okay so try to run this right so it should be relatively fast but just so we're not looking at it load I have a pre pre ran version here so it's can you see that okay right so so here is sorry it's not that that pretty but here are the 20 topics learned so as you can see they're somewhat coherent so this one corresponds to two models and data and handwriting like handwriting recognition which is a machine learning problem just like speech speech signal auditory recognition proteins amino acids which is like a neurone a neuroscience topic but anyways and here's also the the topic proportions learn for the the paper I showed you and as you can see the most the most likely topic for this for this document is topic 16 with seventy eight percent so this is a topic that is sort of seems like it's it's it's about neural networks and then the second most probable topic is topic 14 which has words corresponding to two reinforcement learning if you're familiar with that area so yeah that's my demo yeah so the so it's pretty fast right and I'm actually going to be open sourcing this implementation sometime in the future so it's it it's going to have implementations in scale of online lda and also online HD p which is a nonparametric counterpart of lda and it should also have the option to run it locally or or in spark or in a purely streaming application with spark streaming and it should have the the two word association measures for sorry that this is the statistical and word association topic model evaluation measures a smart vocabulary builder ap is for topic proportion inference some pre-trained models so for example if you if you don't want to train your own model for whatever reason it can come with some pre-trained models say on Wikipedia so just just general topics if you just want to infer the proportion of those topics in your in your documents you can do that and also a topic proportion based document simula similarity calculator alright that's it ok question question right so HTTP is the hierarchical garishly process so so basically like I said a parameter in lda is is K the number of topics learned so an HTTP it's assumed that there are sort of an infinite number of topics that that could be present in your in your collection so it's maybe not as useful as lda but it's sort of like a more flexible model so it some people think that it's it's better for say like a purely streaming application where you want to see how your topic sort of change over time yeah yeah tizen topics what do you mean tie you mean like similar words within within like like duplicate topics I mean I I mean I've never experienced that but I suppose that I would have a lot to do with your data set I mean I mean like a el día generally works better with with larger data sets i mean i just showed a small data set for demo purposes but I mean that should be pretty unlikely to happen I mean unless there's a lot of sort of duplications within your data set that your your training right so um I mean I mean I'm not even i'm not sure if i've never experienced that I said I guess the model itself prevents that from happening right right right right right well I mean this is sort of like a neuroscience data set that I'm running it on so it's not that surprising that they would sort of be duplicates I mean they're not they're not exact duplicates in terms of like the probabilities but yeah I mean I mean that that tends to happen in in el día perhaps if you had a larger dataset I mean this is a very small data set so these these topics aren't of great quality yeah thanks yeah go ahead I mean okay so how is sort of my implementation invitation different from sparks implementation well I mean I haven't done any any benchmarking tests or anything like that I mean I'm sure both of our implementations are quite different I mean I think I mean I haven't looked at in a while but I think sparks implementation uses like graphics and things like that so but but yeah I mean once I open source it i think i should do some benchmarking that would be a good idea right right so I mean right so how are we using topics here at nitro right well just sort of the other thing you said I mean so sort of whenever you run topic modeling algorithms like this about ten percent of them will be sort of incoherent topics or like duplicate topics or things like that so that's that's sort of inevitable but but topics are independent with respect to each other so once you're doing you or your your topic proportion inference which is sort of what's most important for us here at nitro you can you can actually sort of prune and pick and choose the topics that you want to that you want to use for the proportion inference so you can sort of cheat that way but so so to your point though so we're using top modeling here at nitro generally speaking for things like smart search so some of the examples I mentioned earlier yep sorry I was actually gonna ask you to repeat the question so in practice when I've done this I haven't actually been I haven't actually been literally sampling from from the document collection so so what I've been doing is is sort of creating a mini batch iterator so sort of like an iterator of our dd's so for example if your if your documents were just in some directory on your system you can create and you knew the size of your mini batch you can create sort of like an iterator through those text files and then parallel lies them as our DD so I've never actually done it with with pure sampling as I said here