Variational Inference for LDA

Fitting latent Dirichlet allocation by optimization instead of sampling. The expected logarithm of a Dirichlet, the factorized family and the evidence lower bound, the two coordinate updates each proved to be a maximum, the M-step for the topics, and the bound traced on the six documents, where it rises at every step and stays below the exact evidence.

On the six documents, the collapsed Gibbs sampler of latent Dirichlet allocation approximates the posterior by moving among assignments of topics to words, and it never comes to rest. Can the posterior be approximated instead by one fixed distribution, found by optimization? It can, and that is how Blei, Ng, and Jordan (2003) fitted the model when they introduced it.

Variational inference replaces the posterior with a simpler distribution, in which the latent variables are independent, and adjusts that distribution to be as close to the posterior as it can be made. The adjustment maximizes a lower bound on the probability of the documents.

First we derive the one fact about the Dirichlet distribution that the method needs, its expected logarithm. Then we state the two updates, and derive them from the lower bound, proving that each is a maximum. Next we run them on the one-word document $d_3$ and on all six documents, and compare the bound with the exact evidence. Finally we solve two problems by hand. The article assumes latent Dirichlet allocation, for the model, the Dirichlet integral and the collapsed Gibbs sampler, and the expectation-maximization algorithm of pLSA.

The expected logarithm of a Dirichlet

Latent Dirichlet allocation writes the Dirichlet density with parameters $a_1, \dots, a_K$ as $\prod_k \theta_k^{a_k - 1} / B(a)$, with $B(a) = \prod_k \Gamma(a_k) / \Gamma(\sum_k a_k)$, and proves that $\int \prod_k \theta_k^{a_k - 1}\, d\theta = B(a)$ over the simplex. One consequence of that integral is needed here.

The expected logarithm. Variational inference needs the mean of $\log \theta_k$ under a Dirichlet with parameters $a$. Differentiate both sides of $\int \prod_j \theta_j^{a_j - 1}\, d\theta = B(a)$ with respect to $a_k$. On the left, the derivative of $\theta_k^{a_k - 1}$ is $\theta_k^{a_k - 1} \log \theta_k$, so the derivative of the integral is $\int \log \theta_k \prod_j \theta_j^{a_j - 1}\, d\theta$. On the right, $\log B(a) = \sum_j \log \Gamma(a_j) - \log \Gamma(\sum_j a_j)$, so the derivative of $B(a)$ is $B(a) \left[ \Psi(a_k) - \Psi(\sum_j a_j) \right]$. Here $\Psi$ is the digamma function, the derivative of $\log \Gamma$. Dividing both sides by $B(a)$ turns the left side into an expectation:

$$\mathrm{E}[\log \theta_k] = \Psi(a_k) - \Psi\!\left(\textstyle\sum_j a_j\right).$$

Taking the derivative inside the integral is the one step not justified here. Blei, Ng, and Jordan (2003, appendix A.1) obtain the same identity from the general fact that, for an exponential family, the derivative of the log normalizer is the expected sufficient statistic. The script variational-inference-for-lda.py in tools/experiments/topics/ checks the identity three ways: by numerical integration for $K = 2$, by a finite difference of $\log B$, and by 400,000 sampled vectors for $K = 3$.

Variational inference

Blei, Ng, and Jordan (2003) approximated the posterior with a simpler distribution in which the latent variables are independent. They adjusted that distribution to be as close as possible to the true posterior, by maximizing a lower bound on the likelihood of the data. The procedure is the EM derived for pLSA, with one change: the exact posterior that made pLSA's bound tight is out of reach, so the E-step takes the best distribution within the simpler family. It alternates between updating each document's variational parameters and the topics.

For one document, the approximation gives $\theta$ its own Dirichlet with parameters $\gamma$, and each word position $n$ its own distribution $\varphi_n$ over topics. A warning on notation: in this section, as in the paper, $\beta_{k,w}$ denotes the topics themselves, the probability of word $w$ in topic $k$ (written $\phi_{k,w}$ in latent Dirichlet allocation), and not the scalar prior $\beta$ of that article's Gibbs sections. The prior on the proportions is written $\alpha_k$, one value per topic, all equal to 0.1 in the examples. The paper writes $\phi$ for the distributions called $\varphi_n$ here. Minimizing the Kullback–Leibler divergence to the true posterior leads to two updates, repeated until they stop changing (Blei, Ng, and Jordan, 2003, §5.2, eqs. 6 to 8):

$$\varphi_{n,k} \propto \beta_{k, w_n} \exp\!\left( \Psi(\gamma_k) - \Psi\!\left(\textstyle\sum_j \gamma_j\right) \right), \qquad \gamma_k = \alpha_k + \sum_{n} \varphi_{n,k}.$$

Here $\beta_{k,w}$ is topic $k$'s probability for word $w$, and $\Psi$ is the digamma function, the derivative of $\log \Gamma$. The updates mirror the Gibbs update of the LDA article:

  • The first is Bayes' rule for one word's topic, with the document's topic weight replaced by the exponential of its expected logarithm.
  • The second is the conjugate update, the prior plus expected counts, with soft counts $\varphi$ in place of the sampler's hard assignments.

If the three words of the LDA article's conjugacy example had certain topics, two in topic 1 and one in topic 2, the second update would give $\gamma = (2.1, 1.1)$, its exact posterior. The approximation lies elsewhere, in treating $\theta$ and the words' topics as independent. The topics are then re-estimated from the expected counts of all documents, as in pLSA's M-step.

Deriving the two updates

Here is the plan of the derivation. We write a lower bound on the log-probability of one document that holds for every choice of $\gamma$ and $\varphi$, as pLSA's bound held for every $q$. We write it out term by term, using the expected logarithm of the first section. Then we maximize it over each $\varphi_n$ with $\gamma$ fixed, and over $\gamma$ with the $\varphi_n$ fixed, and find that the maximizers are the two updates. The derivation follows Blei, Ng, and Jordan (2003, §5 and appendix A.3). It differs in one respect: where the paper sets derivatives to zero, each maximum here is proved directly from Jensen's inequality.

The formal version.

  1. The model for one document. As in the paper's §5, the topics are held fixed while one document is treated: $\beta_{k,w}$ is the probability of word $w$ in topic $k$. The document has words $w_1, \dots, w_N$, and its latent variables are its proportions $\theta$ and its topic assignments $z_1, \dots, z_N$. Their joint probability is the document's factor of the product in the LDA article's plate-notation section: $$p(\theta, z, w \mid \alpha, \beta) = p(\theta \mid \alpha) \prod_{n=1}^{N} \theta_{z_n}\, \beta_{z_n, w_n}.$$ The probability of the words alone, the document's evidence, is $p(w \mid \alpha, \beta) = \int \sum_z p(\theta, z, w \mid \alpha, \beta)\, d\theta$.
  2. The approximating family. Let $q$ make $\theta$ and the $z_n$ independent, with $\theta$ Dirichlet and each $z_n$ a free distribution over topics (the paper's eq. 4): $$q(\theta, z \mid \gamma, \varphi) = \mathrm{Dirichlet}(\theta \mid \gamma) \prod_{n=1}^{N} \varphi_{n, z_n}.$$ Its parameters are $K$ positive numbers $\gamma_k$ and, for each word position, probabilities $\varphi_{n,1}, \dots, \varphi_{n,K}$ that sum to 1.
  3. The bound. Multiply and divide by $q$ inside the evidence and apply Jensen's inequality, exactly as in step 2 of the EM derivation for pLSA: $$\log p(w \mid \alpha, \beta) = \log \int \sum_z q\, \frac{p(\theta, z, w)}{q}\, d\theta \;\ge\; \int \sum_z q \log \frac{p(\theta, z, w)}{q}\, d\theta = \mathrm{E}_q[\log p(\theta, z, w)] - \mathrm{E}_q[\log q(\theta, z)].$$ Call the right side $L(\gamma, \varphi)$, the evidence lower bound. It holds for every $\gamma$ and $\varphi$. Its distance from the evidence has a name. Since $p(\theta, z, w) = p(\theta, z \mid w)\, p(w)$, $$L = \log p(w) - \mathrm{E}_q\!\left[ \log \frac{q(\theta, z)}{p(\theta, z \mid w)} \right] = \log p(w) - \mathrm{KL}\big(q \,\|\, p(\theta, z \mid w)\big),$$ where KL is the Kullback–Leibler divergence from $q$ to the true posterior. Raising $L$ and lowering that divergence are therefore the same thing, since $\log p(w)$ does not depend on $\gamma$ or $\varphi$.
  4. The bound, term by term. Taking logarithms, $\log p(\theta, z, w) = \log p(\theta \mid \alpha) + \sum_n \log \theta_{z_n} + \sum_n \log \beta_{z_n, w_n}$, and $\log q = \log \mathrm{Dirichlet}(\theta \mid \gamma) + \sum_n \log \varphi_{n, z_n}$. Under $q$, position $n$ has topic $k$ with probability $\varphi_{n,k}$, and by the expected logarithm of the first section, $$\ell_k = \mathrm{E}_q[\log \theta_k] = \Psi(\gamma_k) - \Psi(\gamma_0), \qquad \gamma_0 = \textstyle\sum_j \gamma_j.$$ Writing each Dirichlet density as $\prod_k \theta_k^{a_k - 1} / B(a)$ and taking expectations one term at a time gives five lines (the paper's eq. 15): $$\begin{aligned} L(\gamma, \varphi) = {} & -\log B(\alpha) + \sum_k (\alpha_k - 1)\, \ell_k \\ & + \sum_n \sum_k \varphi_{n,k}\, \ell_k \\ & + \sum_n \sum_k \varphi_{n,k} \log \beta_{k, w_n} \\ & + \log B(\gamma) - \sum_k (\gamma_k - 1)\, \ell_k \\ & - \sum_n \sum_k \varphi_{n,k} \log \varphi_{n,k}. \end{aligned}$$ Line 1 is the expectation of $\log p(\theta \mid \alpha)$, line 2 of $\sum_n \log \theta_{z_n}$, and line 3 of $\sum_n \log \beta_{z_n, w_n}$. Lines 4 and 5 are minus the expectations of $\log \mathrm{Dirichlet}(\theta \mid \gamma)$ and of $\sum_n \log \varphi_{n, z_n}$.
  5. The best $\varphi_n$ for a fixed $\gamma$. The terms that contain $\varphi_n$ are $\sum_k \varphi_{n,k} \left[ \ell_k + \log \beta_{k, w_n} - \log \varphi_{n,k} \right]$. Put $m_k = \beta_{k, w_n} e^{\ell_k}$ and $m = \sum_k m_k$. The terms are then $\sum_k \varphi_{n,k} \log (m_k / \varphi_{n,k})$, and by Jensen's inequality, over the $k$ with $\varphi_{n,k} > 0$, $$\sum_k \varphi_{n,k} \log \frac{m_k}{\varphi_{n,k}} \le \log \sum_k \varphi_{n,k}\, \frac{m_k}{\varphi_{n,k}} \le \log m.$$ The choice $\varphi_{n,k} = m_k / m$ makes every ratio equal to $m$ and so attains $\log m$. It is the maximum. Since $e^{\ell_k} = e^{\Psi(\gamma_k)} e^{-\Psi(\gamma_0)}$ and the second factor is the same for every $k$, this is the first update: $\varphi_{n,k} \propto \beta_{k, w_n} \exp \Psi(\gamma_k)$.
  6. The best $\gamma$ for fixed $\varphi$. Put $c_k = \alpha_k + \sum_n \varphi_{n,k}$. The terms of $L$ that contain $\gamma$ are in lines 1, 2 and 4, and together they are $$\sum_k (c_k - 1)\, \ell_k - \sum_k (\gamma_k - 1)\, \ell_k + \log B(\gamma).$$ Under $q$, the expected log-density of a Dirichlet with parameters $c$ is $-\log B(c) + \sum_k (c_k - 1)\ell_k$, and that of the Dirichlet with parameters $\gamma$ is $-\log B(\gamma) + \sum_k (\gamma_k - 1)\ell_k$. So the terms equal $$\log B(c) + \mathrm{E}_q\!\left[ \log \frac{\mathrm{Dirichlet}(\theta \mid c)}{\mathrm{Dirichlet}(\theta \mid \gamma)} \right] \le \log B(c) + \log \mathrm{E}_q\!\left[ \frac{\mathrm{Dirichlet}(\theta \mid c)}{\mathrm{Dirichlet}(\theta \mid \gamma)} \right] = \log B(c),$$ by Jensen's inequality again. The last expectation is the integral of the density $\mathrm{Dirichlet}(\theta \mid c)$, which is 1. With $\gamma = c$ the ratio is 1 and the bound $\log B(c)$ is attained. So $\gamma_k = \alpha_k + \sum_n \varphi_{n,k}$ is the maximum, the second update. The paper reaches the same $\gamma$ by setting the derivative to zero (appendix A.3.2).
  7. The bound never decreases. Each update replaces one block of parameters by the maximizer of $L$ over that block with the other block fixed, so $L$ cannot fall. $L$ is at most $\log p(w \mid \alpha, \beta)$, so its values converge. The two updates depend on each other, which is why they are repeated. As with EM, this shows that the values of $L$ converge. If the parameters settle, they settle at a point that neither update can improve, which need not be the best member of the family. The argument does not show that they must settle; in the runs below they do.
  8. The topics. For the whole collection, add the bounds of the documents. The topics appear only in the third line, which sums to $\sum_k \sum_w m_{k,w} \log \beta_{k,w}$, where $m_{k,w}$ is the expected number of occurrences of word $w$ assigned to topic $k$: the sum of $\varphi_{n,k}$ over all positions of all documents that hold $w$. By the weighted-log inequality of the pLSA article (step 4 of its derivation), the maximum over distributions $\beta_{k,\cdot}$ is $\beta_{k,w} = m_{k,w} / \sum_{w'} m_{k,w'}$ (the paper's eq. 9). Alternating the two updates for every document with this re-estimate is variational EM, and each of its steps leaves the total bound higher or unchanged. Here $\alpha$ is held fixed. Blei, Ng, and Jordan (2003, §5.3 and appendix A.4.2) also re-estimate it at each M-step, by Newton–Raphson. The derivation treats the topics as parameters, as the paper's §5 does. In the smoothed model of the generative story at the top of the LDA article (the paper's §5.4), each topic also receives a variational Dirichlet, and its update adds the prior's pseudo-counts to the expected counts $m_{k,w}$. The collapsed Gibbs sampler of that article is for the smoothed model, and scikit-learn, used on Reuters there, fits it too. On the six documents, the unsmoothed form is why the fitted topics below contain exact zeros.

The updates on the six documents

Take $d_3$, the one-word document ship, with $\alpha = 0.1$ for both topics. Fix the topics at the start of the pLSA trace, which give ship probability 0.30 in topic 1 and 0.15 in topic 2. Start, as the paper does, from $\varphi = (0.5, 0.5)$ and $\gamma_k = \alpha_k + N/K = 0.6$.

  • Round 1. The two $\gamma_k$ are equal, so $\varphi \propto (0.30, 0.15)$, which is $(0.667, 0.333)$. Then $\gamma = (0.1 + 0.667,\ 0.1 + 0.333) = (0.767, 0.433)$.
  • Round 2. Now $\exp \Psi(0.767) = 0.3520$ and $\exp \Psi(0.433) = 0.0968$. The weights are $0.30 \times 0.3520 = 0.1056$ and $0.15 \times 0.0968 = 0.0145$, so $\varphi = (0.879, 0.121)$ and $\gamma = (0.979, 0.221)$.
  • Rounds 3 and 4. $\varphi = (0.992, 0.008)$, then $(1.000, 0.000)$ to three decimals, and $\gamma$ settles at $(1.100, 0.100)$.

The bound after each update, starting from $-2.957$:

Round After the $\varphi$ update After the $\gamma$ update
1 −2.898 −2.794
2 −2.640 −2.384
3 −2.156 −1.931
4 −1.900 −1.897

It rises at every step, as step 7 says, and converges to $-1.897$. For so short a document the evidence can be computed exactly. A one-word document has $p(w) = \sum_k \mathrm{E}[\theta_k]\, \beta_{k,w} = 0.5 \times 0.30 + 0.5 \times 0.15 = 0.225$, and $\log 0.225 = -1.492$. The bound stops 0.405 below it.

The gap can be read exactly. The converged $q$ puts essentially all its weight on topic 1 and gives $\theta$ the distribution $\mathrm{Dirichlet}(1.1, 0.1)$, which is the true posterior of $\theta$ if the word's topic is 1. So $L$ is, to four decimals, $\log p(w, z = 1) = \log(0.5 \times 0.30) = \log 0.15 = -1.897$. By step 3 the gap is the divergence from the true posterior, here essentially $-\log P(z = 1 \mid w) = -\log(0.15 / 0.225) = \log 1.5 = 0.405$. The equality is not exact: the optimum keeps a probability of about $2 \times 10^{-5}$ on topic 2 and ends $2.3 \times 10^{-5}$ above $\log 0.15$, so the true gap is 0.40544, just under $\log 1.5 = 0.40547$. The true posterior gives topic 1 probability two-thirds, and its mean for $\theta_1$ is $\tfrac{2}{3} \times \tfrac{1.1}{1.2} + \tfrac{1}{3} \times \tfrac{0.1}{1.2} = 0.639$. The approximation's mean is $1.1 / 1.2 = 0.917$. The factorized family cannot represent "topic 1 with $\theta$ leaning one way, or topic 2 with $\theta$ leaning the other", so it commits to the likelier branch. The small $\alpha$ sharpens the choice: $\exp \Psi(0.1)$ is about $0.00003$, so a topic that holds little of a document is given almost no chance at its remaining words.

For the whole collection, the script runs variational EM from the same starting topics, with each document's updates run to convergence. The total bound and, for comparison, the exact log evidence of the six documents under the same topics (computed by summing over every assignment, with $\theta$ integrated out as in step 1 of the Gibbs derivation in the LDA article) were:

Round Total bound Exact log evidence
Start −20.295 −15.964
1 −16.228 −15.329
2 and after −15.217 −14.766

The bound never decreased over 40 rounds, and it stayed below the exact value throughout, as the derivation requires. The topics it settled on are (ship 1/3, boat 1/6, ocean 1/3, voyage 1/6) and (voyage 1/2, trip 1/2), with all of $d_1$ in the first: $\gamma_{d_1} = (3.1, 0.1)$. Its assignment of words to topics is the one called "all of $d_1$ with the sea words" in the LDA article's table of the exact posterior (a table for the collapsed model, with the topics integrated out), not pLSA's sea/travel split. The preference is the prior's, not an accident of the approximation. With pLSA's best topics, where every word's topic is forced and the bound is exact, the log evidence of the six documents is $-16.151$, lower than $-14.766$. A prior with $\alpha = 0.1$ charges $d_1$ for mixing two topics, and the charge outweighs the better fit to its words.

Online variational inference

Online variational inference (Hoffman, Blei, and Bach, 2010) updates the topics from small batches of documents at a time. It can therefore process collections too large to hold in memory, or streams of new documents. The scikit-learn implementation used on Reuters in the LDA article offers both batch and online variants.

Worked problems

The course had no assignment for this topic, and the course text has no exercises on LDA. These two problems are posed on the six documents with $K = 2$ and $\alpha = 0.1$, and every number in them is checked by variational-inference-for-lda.py.

Problem 1 (mean and expected logarithm of a Dirichlet). A two-topic document has prior $\alpha = 0.1$, two words assigned to topic 1 and one to topic 2. Find the posterior of $\theta$, its mean, and $\exp \mathrm{E}[\log \theta_k]$, the weight the variational update for $\varphi$ would use.

By conjugacy (the prior's parameters plus the counts, as in the LDA article) the posterior is $\mathrm{Dirichlet}(2.1, 1.1)$, with mean $(2.1/3.2,\ 1.1/3.2) = (0.656, 0.344)$. For the expected logarithms, $\Psi(2.1) = 0.4853$, $\Psi(1.1) = -0.4238$ and $\Psi(3.2) = 0.9988$, so

$$\mathrm{E}[\log \theta_1] = 0.4853 - 0.9988 = -0.5135, \qquad \mathrm{E}[\log \theta_2] = -0.4238 - 0.9988 = -1.4226.$$

Their exponentials are 0.598 and 0.241. Each is below the corresponding mean, as Jensen's inequality requires ($\mathrm{E}[\log \theta] \le \log \mathrm{E}[\theta]$), and they sum to 0.84, not 1. The shortfall is larger in proportion for the smaller component. Normalized, the two weights are 0.713 and 0.287, against the mean's 0.656 and 0.344. The variational update therefore leans toward the topic a document already favors, more than the posterior mean would. That is the same pull that sent $d_3$ to a single topic in the trace.

Problem 2 (the exact evidence of a one-word document, and the bound). For $d_3$ = ship, with the topics of the variational trace (ship has probability 0.30 in topic 1 and 0.15 in topic 2) and $\alpha = 0.1$, compute the evidence exactly, the exact posterior probability of each topic, and the largest value the bound can take when $q$ puts the word wholly in topic 1.

The evidence is 0.225, the posterior is two-thirds for topic 1, and the bound is $\log 0.15$. Summing the collapsed probability over the two possible assignments, as in step 1 of the Gibbs derivation in the LDA article, the assignment to topic $k$ contributes $\frac{B(\alpha + e_k)}{B(\alpha)}\, \beta_{k,\text{ship}} = \frac{0.1}{0.2}\, \beta_{k,\text{ship}}$:

$$p(w) = 0.5 \times 0.30 + 0.5 \times 0.15 = 0.150 + 0.075 = 0.225.$$

The posterior probability of topic 1 is $0.150 / 0.225 = 2/3$, and of topic 2 it is $1/3$.

If $q$ puts the word in topic 1 with certainty, the best it can do for $\theta$ is the posterior given that assignment, $\mathrm{Dirichlet}(1.1, 0.1)$, by step 6 of the derivation. Then $q$ equals the true posterior restricted to topic 1, and the bound of step 3 is $\log p(w) - (-\log \tfrac{2}{3}) = \log 0.225 + \log \tfrac{2}{3} = \log 0.15 = -1.897$. The trace converged to this value to four decimals, 0.405 below $\log 0.225 = -1.492$. A $q$ that kept the true two-to-one split between the topics would need $\theta$ to depend on the topic, which the factorized family does not allow.

What we have learned

Variational inference maximizes a lower bound on the evidence by two updates, each proved to be a maximum; on the six documents the bound rose at every step and stayed below the exact evidence. For the one-word document $d_3$ it stopped 0.405 below, because a family in which $\theta$ and the word's topic are independent has to commit to one topic. With $\alpha$ fixed at 0.1, variational EM put all of $d_1$ in one topic, and the exact evidence confirmed that the prior prefers it to pLSA's split.

A bound below the evidence has a consequence for measurement. Evaluating topic models computes perplexity from this bound and from the exact evidence on the six documents, and shows that the bound overstates perplexity.

References

  • Blei, D. M., Ng, A. Y., and Jordan, M. I. (2003). Latent Dirichlet allocation. Journal of Machine Learning Research, 3, 993–1022. record · 6 pages
  • Hoffman, M. D., Blei, D. M., and Bach, F. (2010). Online learning for latent Dirichlet allocation. In Advances in Neural Information Processing Systems 23 (NIPS 2010), 856–864. record