# Why LDA (Latent Dirichlet Allocation) works (i.e. why put co-occurring words together)?

I am studying LDA, but have very weak statistical knowledge. I have a question regarding Gibbs sampling, one of the methods for inferring the distribution of topics and words-topic given a document, which basically iterates and computes the probability of words from being assigned to each topic after removing the specific word from the counts. The question is, why it works ?

I found an explanation below, but I am not able to understand the parts in bold ...

Word probabilities are maximized by dividing the words among the topics. (More terms means more mass to be spread around.) In a mixture, this is enough to find clusters of co-occurring words. In LDA, the Dirichlet on the topic proportions can encourage sparsity, i.e., a document is penalized for using many topics. Loosely, this can be thought of as softening the strict definition of “co-occurrence” in a mixture model. This flexibility leads to sets of terms that more tightly co-occur.

Technically LDA Gibbs sampling works because we intentionally set up a Markov chain that converges into the posterior distribution of the model parameters, or word–topic assignments. See http://en.wikipedia.org/wiki/Gibbs_sampling#Mathematical_background.

But I guess you are seeking an intuitive answer on why the sampler tends to put similar words into the same topic? That's an interesting question. If you look at the equations for collapsed Gibbs sampling, there is a factor for words, another for documents. Probabilities are higher for assignments that "don't break document boundaries", that is, words appearing in the same document have a slightly higher odds of ending up in the same topic. The same holds for document assignments, they to a degree follow "word boundaries". These effects mix up and spread over clusters of documents and words, eventually.

By the way, LDA Gibbs samplers do not actually work properly, in the sense that they do not mix, or are not able to represent the posterior distribution well. If they did, the permutation symmetries of the model would make all solutions obtained by samplers useless, or at least non-interpretable. Instead the sampler sticks around a local mode (of the likelihood), and we get well-defined topics.

• I have a related question about LDA. I know something about MCMC but nothing about LDA. If there are convergence problems in some cases is it possible that some problems just don't admit recurrent Markov chains? – Michael R. Chernick May 9 '12 at 11:11
• I'm not an expert on MCMC, so I'm not sure what you mean. But with respect to LDA, my impression is that there is no theoretical problem with convergence, just a practical one. The chain simply mixes very slowly to be practically non-mixing. On the other hand, the "labeling" problem of components of a well-mixing chain is typical for all mixture models. It's more about correct use of the models than about the model itself. Predictions are fine even though one doesn't get out the interpretation from the model that one was after. – scellus May 9 '12 at 13:16
• Thanks for the reply, very nice and clear. Although all replies were useful, I mark this as the answer. – kanzen_master May 9 '12 at 13:20
• @scellus. i think your response answers my question. Akey part of MCMC is that the Markov chain that you sample from has its k steo transition matrix converge to a stationary distribution. It is the stationary distribution that is set up in the Bayesian problems to be the posterior distribution that is used for the inference in the problem. Not all Markov chains have a stationary distribution. One requirement I think is recurrence. – Michael R. Chernick May 9 '12 at 14:27
• Ok, thanks for the explanation. Yeah, recurrence is usually taken for granted. I guess for collapsed Gibbs estimation of basic LDA (with sensible prior parameters), recurrence is quite trivially true, because the state space is finite, and all transitions with non-zero probability are reversible with non-zero probability. – scellus May 9 '12 at 15:49

I am not familiar with this and can only give a partial answer but maybe its better than nothing since I am a statistician and understand statistical terminology. Clusters of coocurring words means words that appear frequently in sequence such as "of the" being a common pair in english. Languages tend to have patterns like this which can help you characterize them. Mixture models in statistics usually means that the probability distribution in the model can be represented as a mixture of two or more distributions. In the case of two variables say f(x) and g(x) are two distributions. A mixture would pick an x from f with some probability p and with probability 1-p from g. These models are useful as a way to construct bimodal or multimodal distributions. It makes sense that they could mean this since they speak about words occurring in clusters. So I think they may be saying that if we condition on the word "of" occurring the frequency with which the word "the" follows it is much higher than say "the" following a noun like say "missile". So these models I suspect are used to better represent the frequency with which words occur in the english language. In statistics word frequencies have been used in the past to identify authorship. For example Mosteller and Wallace looked at samples of writing from the authors of the Federalist papers to try to attribute authorship to papers where the author was not identified. The Federalist papers were writtne by Hamilton,Jay and Madison and there are many papers where each author is identified. So they constructed a classification rule based on the differences in word usage in their writing to identify who the author of disputed papers are. I recently discover that Glen Fung published a paper in the Journal of ACM identifying disputed papers in the Federalist papers using support vector machines.

• Thanks for your reply and for the statistical background – kanzen_master May 9 '12 at 6:53

I understand your question as asking about LDA, rather than about the mechanisms of Gibbs sampling. Thus, my answer to the question of why the Gibbs sampling algorithm works is that it is designed to do LDA: our goal is to fit the best possible LDA model given the data and our initial parameter settings.

How many topics (that is, how much clustering) LDA does depends on the choice of the Dirichlet concentration parameters. I'm not an expert on using LDA, but so far as I know these parameters are usually fixed beforehand or drawn from a fixed distribution which makes the Gibbs sampling algorithm more convenient to sample.

I read the quoted paragraph as saying, roughly, that if we decide to penalize models with many topics, we will force LDA to perform more clustering: it will have to find the best way to describe all the documents using the fewer topics.

• Thanks for your reply. I am sorry for my vague question -I am mainly asking for the Gibbs sampling. In each iteration of Gibbs sampling, we remove one word, compute a new topic for that word according to a posterior conditional probability distribution inferred from the LDA model through Dirichlet integration, (and assuming the topic allocation for all the other words) and update word counts. The reason why it works, is because at every iteration, simply more words are associated to topics that follow the LDA model dsitributions...right? – kanzen_master May 9 '12 at 7:22

Seems you are asking for intuition.

1. In a mixture, this is enough to find clusters of co-occurring words. This means that the distribution over vocabulary i.e. topics will sum to one. So it is sensible that the co-occuring words come in same topic and fewer words in same topic increases the probability of words occuring in the topic as it should sum to one.

2. In LDA, the Dirichlet on the topic proportions can encourage sparsity As topics are sampled from an exchangable dirichilet so all topics are sampled uniformly. But if alpha in dirichlet is less than 1 than by the definition of dirichilet distribution you can see that $\theta^{(\alpha - 1)}$ is $(fraction)^{(-ve)}$ which will be high so the peaks in the simplex will be high at the corners i.e. sparsity as the topics are sampled from that dirichilet.