Blei 2003 - Variational Inference and Parameter Estimation

Summary

The posterior $p(\theta ,\mathbf{z}\mid \mathbf{w},\alpha ,\beta )$ is intractable (coupling of $\theta$ and $\beta$). Dropping the $w$ edges gives a mean-field family $q(\theta ,\mathbf{z}\mid \gamma ,\varphi )=q(\theta \mid \gamma ){\prod }_{n}q(z_n\mid {\varphi }_n)$; minimising KL yields closed-form coordinate updates, and variational EM estimates $\alpha ,\beta$.

Main Content

Why exact inference fails (5.1). $p(\mathbf{w}\mid \alpha ,\beta )=\frac{\Gamma (\sum {\alpha }_i)}{\prod \Gamma ({\alpha }_i)}\int {\prod }_i{\theta }_i^{{\alpha }_i-1}{\prod }_n{\sum }_i{\prod }_j({\theta }_i{\beta }_{ij}{)}^{w_n^j}d\theta$ is intractable because of the coupling between $\theta$ and $\beta$ in the sum over topics (Dickey 1983, hypergeometric functions). Alternatives: Laplace, variational, MCMC.

Variational family (Eq. 4)

$q(\theta ,\mathbf{z}\mid \gamma ,\varphi )=q(\theta \mid \gamma ){\prod }_{n=1}^{N}q(z_n\mid {\varphi }_n)$, $\gamma$ a Dirichlet parameter, ${\varphi }_n$ multinomial parameters; chosen by $({\gamma }^{\ast },{\varphi }^{\ast })=\arg \min D_{KL}(q\Vert p(\theta ,\mathbf{z}\mid \mathbf{w},\alpha ,\beta ))$ (Eq. 5), equivalent to maximising the ELBO (Jensen lower bound).

Coordinate updates (Eqs. 6-8, Appendix A.3)

$${\varphi }_{ni}\propto {\beta }_{i{w}_n}\exp \{E_q[\log {\theta }_i\mid \gamma ]\},{\gamma }_i={\alpha }_i+\sum _{n=1}^N{\varphi }_{ni},E_q[\log {\theta }_i\mid \gamma ]=\Psi ({\gamma }_i)-\Psi \left(\sum _{j=1}^k{\gamma }_j\right).$$

Proof sketch: write the ELBO terms; the ${\varphi }_n$ term is ${\sum }_i{\varphi }_{ni}\{E_q\log {\theta }_i+\log {\beta }_{i{w}_n}-\log {\varphi }_{ni}\}$, maximised under ${\sum }_i{\varphi }_{ni}=1$ by the stated softmax; the $\theta$ term is a Dirichlet with natural parameter ${\alpha }_i+{\sum }_n{\varphi }_{ni}-1$; $E[\log {\theta }_i]=\Psi ({\alpha }_i)-\Psi (\sum {\alpha }_j)$ follows from the exponential-family form of the Dirichlet (A.1: derivative of the log normaliser equals the expected sufficient statistic).

Interpretation: $\gamma$ is a posterior Dirichlet given expected counts $E[z_n\mid {\varphi }_n]$; $\varphi$ is Bayes’ rule with $p(z_n)$ replaced by $\exp E_q\log \theta$. Algorithm (Fig. 6): initialise ${\varphi }_{ni}^0=1/k$, ${\gamma }_i={\alpha }_i+N/k$; repeat updating $\varphi$ then $\gamma$ until convergence. Cost per iteration $O((N+1)k)$; iterations needed are about $N$, so roughly $N^{2}k$ per document. ${\gamma }^{\ast }(\mathbf{w})$ is a document-specific representation on the topic simplex.

Variational EM (5.3, A.4)

E-step: compute $({\gamma }_d^{\ast },{\varphi }_d^{\ast })$ for every document. M-step: maximise the bound over $\alpha ,\beta$. The conditional multinomial has the closed form ${\beta }_{ij}\propto {\sum }_{d=1}^M{\sum }_{n=1}^{N_d}{\varphi }_{dni}^{\ast }{w}_{dn}^j$ (Eq. 9); $\alpha$ is updated by Newton-Raphson on a Hessian of the form $\text{diag}(h)+1z{1}^T$ whose inverse is obtained in linear time by the matrix inversion lemma (A.2): $(H^{-1}g{)}_i=(g_i-c)/h_i$ with $c={\sum }_j{g}_j/h_j/(z^{-1}+{\sum }_j{h}_j^{-1})$.

Examples

E-step on a toy document

Two topics over four words, $\beta =\left(\begin{array}{cccc}.5& .4& .05& .05\\ .05& .05& .45& .45\end{array}\right)$, $\alpha =(.5,.5)$, document $w=(0,1,0,1,2)$. The fixed point gives $\gamma \approx (4.83,1.17)$: almost all expected words are assigned to topic 1.

import numpy as np
from scipy.special import digamma
 
def estep(w, beta, alpha, iters=100):
    k, N = beta.shape[0], len(w)
    gamma = alpha + N / k
    for _ in range(iters):
        phi = beta[:, w].T * np.exp(digamma(gamma) - digamma(gamma.sum()))
        phi /= phi.sum(1, keepdims=True)
        gamma = alpha + phi.sum(0)
    return gamma, phi
 
beta = np.array([[.5, .4, .05, .05], [.05, .05, .45, .45]])
print(estep(np.array([0, 1, 0, 1, 2]), beta, np.array([.5, .5]))[0])   # [4.83 1.17]

Connections

General theory: The ELBO and KL Divergence Minimization, Mean-Field Family and Coordinate Ascent VI (CAVI), Stochastic and Black-Box Variational Inference (the route to large corpora). MCMC alternative mentioned in Sec. 8: collapsed Gibbs (Griffiths and Steyvers 2002).

See Also

Blei 2003 - Latent Dirichlet Allocation - Overview