$$
\newcommand{\cond}{{\mkern+2mu} \vert {\mkern+2mu}}
\newcommand{\SetDiff}{\mathrel{\backslash}}
\DeclareMathOperator{\BetaFunc}{Β}
\DeclareMathOperator{\GammaFunc}{Γ}
\DeclareMathOperator{\prob}{p}
\DeclareMathOperator{\dcategorical}{Categorical}
\DeclareMathOperator{\dcategorical}{Categorical}
\DeclareMathOperator{\ddirichlet}{Dirichlet}
$$

# Collapsed Gibbs Sampling for LDA

## Notation

* $\ddirichlet_N(\alpha)$ is the symmetric $N$–dimensional Dirichlet distribution, all of whose $N$ parameters are $\alpha$

* $\dcategorical_N(\alpha)$ is the (asymmetric) $N$–dimensional categorical distribution whose $N$ parameters are given by the vector $\alpha$

* $\BetaFunc_N(\alpha)$, with a vector argument, is the (asymmetric) $N$–dimensional beta function defined by

$$\BetaFunc_N(\alpha) = \frac{\prod_n \GammaFunc(\alpha_n)}{\GammaFunc(\sum_n \alpha_n)}$$

* $\BetaFunc_N(\alpha)$, with a scalar argument, is the symmetric $N$–dimensional beta function defined by

$$\BetaFunc_N(\alpha) = \frac{\prod_n \GammaFunc(\alpha)}{\GammaFunc(\sum_n \alpha)} = \frac{\GammaFunc^N(\alpha)}{\GammaFunc(N\alpha)}$$

## Glossary

* $D$ documents

* $K$ topics

* $W$ words in the vocabulary

* $\theta_d$ is a per document $K$–vector of probabilities over the topics

* $\phi_k$ is a per topic $W$–vector of probabilities over the words in the vocabulary

* $z_{id}$ are per document word unobserved latent variables giving the topic assignments

* $x_{id}$ are per document word observed variables giving the vocabulary choices

* $Z$ is the collection of all the latent topic assignment variables

* $X$ is the collection of all the observed vocabulary assignment variables

* $\Theta$ is the collection of per document topic distributions

* $\Phi$ is the collection of per topic word distributions

* $Z^{\SetDiff id}$ is the collection of all the latent topic assignment variables excepting that for topic assignment $z_{id}$

* $\Theta^{\SetDiff d}$ is the collection of per document topic distributions excepting that for document $d$

* $\Phi^{\SetDiff k}$ is the collection of per topic word distributions excepting that for topic $k$

## Statistics

* $N_d$, the number of instances of words in document $d$

* $A_{dk}$, the number of $z_{id}$ variables assigned to topic $k$ in document $d$

$$
A_{dk} = \sum_{i=1}^{N_d} \delta(z_{id} = k)
$$

* $B_{kw}$, the number of times an instance of word $w$ is assigned to topic $k$

$$
B_{kw} = \sum_{d=1}^D \sum_{i=1}^{N_d} \delta(x_{id} = w) \delta(z_{id} = k)
$$

* $A_{dk}^{\SetDiff id}$, the $A_{dk}$ statistic taken over all variables except $z_{id}$

$$
\begin{align}
A_{dk}^{\SetDiff id}
    &= \sum_{i\prime \ne i} \delta(z_{i\prime d} = k) \\
    &= A_{dk} - \delta(z_{id} = k)
\end{align}
$$

* $B_{kw}^{\SetDiff id}$, the $B_{kw}$ statistic taken over all variables except $z_{id}$

$$
\begin{align}
B_{kw}^{\SetDiff id}
    &= B_{kw} - \delta(x_{id} = w) \delta(z_{id} = k)
\end{align}
$$

* $M_k$, the total number of instances of words assigned to topic k, and the matching statistic, $M_k^{\SetDiff id}$

$$
\begin{align}
M_k &= \sum_{w=1}^W B_{kw} \\
M_k^{\SetDiff id} &= \sum_{w=1}^W B_{kw}^{\SetDiff id}
\end{align}
$$

## Probabilities

The LDA model is then given by

$$
\begin{align}
\theta_d \cond \alpha &\sim \ddirichlet_K(\alpha) \\
\phi_k \cond \beta &\sim \ddirichlet_W(\beta) \\
z_{id} \cond \theta_d &\sim \dcategorical_K(\theta_d) \\
x_{id} \cond z_{id}, \phi_{z_{id}} &\sim \dcategorical_W(\phi_{z_{id}})
\end{align}
$$

Assuming that the only dependencies are those given above, the joint probability of
the latent and observed variables along with the parameters is given by

$$
\prob(Z, X, \Theta, \Phi) = \frac{1}{\BetaFunc_K^D(\alpha)} \prod_{d=1}^D \prod_{k=1}^K \theta_{dk}^{A_{dk} + \alpha - 1} \cdot \frac{1}{\BetaFunc_W^K(\beta)} \prod_{k=1}^K \prod_{w=1}^W \phi_{kw}^{B_{kw}+ \beta - 1}.
$$

### Probabilities required for Gibbs sampling

The required conditional probabilites for this model are

$$
\begin{align}
\prob(z_{id} \cond Z^{\SetDiff id}, X, \Theta, \Phi) &= \frac{\theta_{d,z_{id}} \phi_{z_{id}, x_{id}}}{\sum_{k=1}^K \theta_{dk} \phi_{k,x_{id}}} \\
\theta_d \cond Z, X, \Theta^{\SetDiff d}, \Phi &\sim \ddirichlet_K(A_d + \alpha) \\
\phi_k \cond Z, X, \Theta, \Phi^{\SetDiff k} &\sim \ddirichlet_W(B_k + \beta)
\end{align}
$$

where $A_d = (A_{d1}, \dotsc, A_{dK})$ and $B_k = (B_{k1}, \dotsc, B_{kW})$.

## Probabilities required for collapsed Gibbs sampling

We need to integrate out the $\theta_d$'s and the $\phi_k$'s from the model's joint probability.
This gives us

$$
\prob(Z, X) = \prod_{d=1}^D \frac{\BetaFunc_K(A_d + \alpha)}{\BetaFunc_K(\alpha)} \cdot \prod_{k=1}^K \frac{\BetaFunc_W(B_k + \beta)}{\BetaFunc_W(\beta)}
$$

Then the conditional probability from which we need to sample is

$$
\prob(z_{id} \cond Z^{\SetDiff id}, X)
    \propto \frac{
        \left( A_{d,z_{id}}^{\SetDiff id} + \alpha \right)
        \left( B_{z_{id},x_{id}}^{\SetDiff id} + \beta \right)
    }{
        M_{z_{id}}^{\SetDiff id} + W\beta
    }
$$

Since this is a discrete distribution over $k = 1, \dotsc, K$ it is easy to normalise as required, either explicitly or implicitly.

23f063cf9e8d5277736b9982afb24be4f8f2c21a
ipynb
Jupyter Notebook
TopicModels/LDA.ipynb
ConradScott/IJuliaSamples
0f5d212dcf63bc795e79ac790aa3f1c9b010c89e
Apache-2.0
TopicModels/LDA.ipynb
ConradScott/IJuliaSamples
0f5d212dcf63bc795e79ac790aa3f1c9b010c89e
Apache-2.0
TopicModels/LDA.ipynb
ConradScott/IJuliaSamples
0f5d212dcf63bc795e79ac790aa3f1c9b010c89e
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES