0
$\begingroup$

I was confused by how LDA (by the original variational inference) can be implemented in a way such that the number of operations for each document $j$ is $\mathcal{O}(N_j~K)$, where $N_j$ is the unique number of words in $j$ and $K$ is the number of topics. In the original paper by Blei, their inference is done by scanning through each individual word (not unique) for the variational parameter $\gamma_{jik}$ where $i$ is the $i$th word in document $j$.

In an email from the topic modeling mailing list, the authors (Prof. Blei) also said that

the complexity of mean-field variational inference is actually
O(NKV). the reason is that, in a document, we need not compute
posterior multinomials for each instance of each term but only once
for each unique term in that document. in the LDA paper, we did not
write things down that way to make the math simpler. (though, we
should have mentioned this speed-up.)

if you'll look at the LDA-C code, which is on my web-site, you'll see
that we only need to iterate through the unique terms of each document
for each iteration of variational inference.

For me, it will take up too much time to look at the C code. Can anyone provide an intuitive way on how to implement VB LDA by iterating thru each document's unique word?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Thanks to Prof. Dave Blei's reply, I now got it.

So it turns out that this simply comes from some algebra trick. There's indeed a variational multinomial distribution, with parameter $\phi_{jik}$, for the $i$th word and $j$th document, regarding the $k$th topic/component. When we are doing updates $\phi_{jik}$, it goes like this: $$\phi_{jik}\propto \beta_{kw_i}~exp\Big(E\big[log\theta_{jk}\big] + E\big[log\beta_{kw_i}\big]\Big)$$

where $w_i$ is the index of word $i$. Therefore, the update will be the same if two words are the same element in the vocabulary (say, word 1 and word 17 are both "bayes"). In this case, we can collapse them into one single term, namely "term", instead of word, variational factor. After we do so, we need to aggregate the effects of multiple terms when updating other parameters like $\gamma$ and $\lambda$. There's no need to re-derive the equations.

Reference: M. D. Hoffman, D. M. Blei, and F. Bach, “Online Learning for Latent Dirichlet Allocation,” Adv. Neural Inf. Process. Syst., vol. 23, pp. 1–9, 2010.

Improve this answer
$\endgroup$
1
$\begingroup$

The idea behind LDA is that you assign a topic $z_{d,n}$ to every word $w_{d,n}$ in document $d$. The topic assignment $z_{d,n}$ is done according to the variational distribution of $z_{d,n}$ (which takes $K$ possible values) and intuitively takes into account two influencing factors:

  1. The topic assignments of all other words in document $d$
  2. The word-topic distributions (i.e. topics) in which word $w_{d,n}$ (let's say this word is 'tree') plays a major role

Imagine that the word 'tree' occurs multiple times in the same document, e.g. $w_{d,1} = w_{d,15} = w_{d, 100} = $ 'tree'. The variational distribution of $z_{d,1}$ is equivalent to the distribution of $z_{d,15}$ and $z_{d, 100}$, because the two influencing factors are the same for all three occurrences of the word 'tree' in document $d$.

Instead of sampling a value $z$ for every single occurrence of 'tree', we can also sample once and then assign the result of that sampling as a value to $z_{d,1}$, $z_{d,15}$ and $z_{d, 100}$. This saves us two draws and thus reduces the computational complexity of the algorithm.

Instead of having to sample all $N$ words, we now only have to sample all $N_d$ unique words.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for the reply. I understand that the var. dist. of $z$ is a multinomial for each unique word across $K$. In this case, how do we take into account the word counts for each pair of $d$ and $w$, namely $n_{d,w}$ ? $\endgroup$
    – Zhiya
    Commented Mar 5, 2018 at 16:40
  • $\begingroup$ Instead of saving every document as a bag-of-words, like [1, 2, 3, 4, 5, 2, 5, 3, 4] for a document with 9 total words and 5 unique words, you save every word as a (word, frequency) tuple. The document then looks like [(1, 1), (2, 2), (3, 2), (4, 2), (5, 2)]. Every time you resample, you resample all occurrences of a word immediately. I'm sure there are other ways, though. This is the way I do it usually $\endgroup$
    – KenHBS
    Commented Mar 5, 2018 at 16:43
  • $\begingroup$ This is more about the input data format, which is the Blei LDA-C format. What I was wondering is more on the derivation side. Based on my current understanding, can I say something like this for each of the unique token $w$ in $d$, the sampling of it will be done one time, and its impact in terms of probability will be raised to the power of $n_{d,w}$? $\endgroup$
    – Zhiya
    Commented Mar 5, 2018 at 16:49
  • $\begingroup$ And for variational distribution of $z$, we will right it as $q(z)=\prod_d q(z_d \vert \phi) = \prod_d q(z_{d,w} \vert \phi_{w})^{n_{d,w}}$ and there is constraint on $phi_{w}$: $\sum_{k} \phi_{w,k} = 1$. Is this correct? $\endgroup$
    – Zhiya
    Commented Mar 5, 2018 at 16:52
  • $\begingroup$ If by 'impact in terms of probability' you mean the impact it has on e.g. the document-topic mixture (usually called $\theta_d$) and word-topic distribution (usually called $\phi_k$), then you multiple its effect by $n_{d,w}$, not take the power. $\endgroup$
    – KenHBS
    Commented Mar 5, 2018 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.