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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.