Implementing Latent Dirichlet Allocation - notation confusion

I am trying to implement LDA using the collapsed Gibbs sampler from http://www.uoguelph.ca/~wdarling/research/papers/TM.pdf

the main algorithm is shown below

I'm a bit confused about the notation in the inner-most loop. n_dk refers to the count of the number of words assigned to topic k in document d, however I'm not sure which document d this is referring to. Is it the document that word (from the next outer loop) is in? Furthermore, the paper does not show how to get the hyperparameters alpha and beta. Should these be guessed and then tuned? Furthermore, I don't understand what the W refers to in the inner-most loop (or the beta without the subscript).

Could anyone enlighten me?

I would suggest you look at page 8 of "Probabilistic Topic Models" by Mark Steyvers and Tom Griffiths. I found their explanation of the Gibbs algorithm quite clear and easy to implement.

• i seems to range over (indexes for) all the words in all the documents, and d indeed seems to refer to the document of the word under consideration.
• There are some algorithms for estimating alpha and beta but I haven't really understood any of them myself. Just tuning the parameters manually should be ok in most cases.
• W seems to be the size of the vocabulary, i.e. the number of unique words.
• I'm confused about the beta with / without subscript as well. If they use a different beta per word, then maybe in the denominator it should say the sum of all beta_w, instead of beta * W?

I had this same problem and had to read a lot about the Dirichlet distribution to understand what was going on here. Stijn Vermeeren answers most of your questions, but I think there's a bit more to say.

Types and Tokens

One thing that is confusing about a number of descriptions of LDA available online is that they don't distinguish carefully between word types and word tokens. The vocabulary size is the number of word types; there is one type for "if", and one type for "the", and so on. But there will (almost always) be multiple tokens of that word type in the corpus.

So to answer your first question, yes, the d refers to the document containing the current word token under consideration. This is iterating over every word token in the corpus, and is storing the word type, the topic assignment, and the document for that particular token -- in word, topic, and d respectively. Only the topic will change in this process; the other two are constant for our purposes.

Hyperparameters

Answering your last three questions is more complicated, and requires that I talk for a moment about symmetric and asymmetric hyperparameters.

Basically, in many implementations of LDA, the values of a[k] are all different. They govern the shape of the Dirichlet distribution of topics over documents. Making the values different allows some topics to be much more prominent than others across many of the documents. So, for example, there might be a topic that makes up a solid 30% of almost every document. That, in turn, allows the algorithm to sequester common, uninteresting words into a few very common topics.

But in many implementations of LDA, the values of b[word] are all the same. They govern the shape of the Dirichlet distribution of words over topics. Because they are all the same, no one word appears more frequently in all topics than any other word. (Some words will appear much more frequently in a given topic, but those topics are outliers; the words will probably appear much less frequently in others.)

Now, in the pseudocode above, the numerator uses the notation b[w] to refer to the beta parameters. That's confusing, because if the beta value is the same for all words, then we don't need a subscript at all. But if the beta value differs for each word, then it really ought to be b[word], not b[w], since w has already been used to refer to the entire corpus of word tokens! Then, in the denominator, a different notation is used: b x W. There's no subscript, and a mysterious W appears. As Stijn says, the W is indeed the vocabulary size -- the number of word types (not tokens). So here, b is being treated as the same for all words, and we're just multiplying that value by the number of word types. You could just as easily use summation notation, and if the values of b[i] were indeed different, then you would have to.

So my interpretation of the above is that b[w] refers to the beta value for each word type -- which is always the same. And so the bottom ought to be b[w] x W, or else the top ought to be just b.

If you wanted to have different beta values for each word, you could use summation notation instead, and sum over the values of b[word] for each word. But most implementations I've seen follow the advice of this paper, which suggests that making beta values asymmetric is unnecessary -- and might even degrade performance slightly.

To answer your final question: yes, you can just guess. By default, MALLET uses symmetric alpha and beta, with defaults of 50 (as the sum of alpha values) and 1.0 (as the individual beta values -- for good reasons that I won't get into here).