Latent Dirichlet Allocation (LDA)

2024/07/28    Last Update: 2024/08/09

Introduction

Latent Dirichlet allocation (LDA) is a type of unsupervised learning commonly used in text mining, the goal of LDA is to classify a large number of documents by generating topic distributions based on term frequency of use of words, which is an extended model of latent semantic analysis.

LSA assume

1. Each document is a multinomial distribution of topics, called a topic distribution.
2. Each topics is a multinomial distribution of words, called a words distribution.

where topic distribution and words distribution are unknown, only the term frequency is observed. LDA introduces Dirichlet distribution as the prior distribution of topic distribution and word distribution.

Distribution

Multinomial Distribution

Support there are number of $k$ possible outcome, the probability of $i$-th outcome is $p_i \geq 0$, with $\sum_{i = 1}^{k} p_i^i = 1$, the correspond occured number is $x_i$, then the random vector $\ut X = (\contia{X}{k})$ has the following pdf:

$$ \begin{align*} P (\ut X = \ut x | n, \ut p) & = \frac{n!}{\prod_{i = 1}^{k} (x_i)!} \prod_{i = 1}^{k} p_i^{x_i} \end{align*} $$

where $\sum_{i = 1}^{k} x_i = n$, and $x_i \in \bb N$ ($> 0$), write as $\ut X \sim \text{Mult} (n, \ut p)$; when $n = 1$, abbreviated as $\text{Mult} (\ut p)$.

Dirichlet Distribution

Dirichlet distribution is an extended of beta distribution, or called multivariate beta distribution. For a given parameter $\ut \alpha = (\contia{\alpha}{k})$, $\alpha_i > 0$ for $i = \conti{k}$, the random vector $\ut \theta = (\contia{\theta}{k})$ has the following pdf:

$$ \begin{align*} P (\ut \theta | \ut \alpha) & = \frac{\Gamma (\sum_{i = 1}^{k} \alpha_i)}{\prod_{i = 1}^{k} \Gamma (\alpha_i)} \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} \end{align*} $$

where $\sum_{i = 1}^{k} \theta_i = 1$, and $\theta_i \geq 0$ for $i = \conti{k}$, write as $\ut \theta \sim \text{Dir} (\ut \alpha)$.

Properties

$\Gamma (s)$ is gamma function, define multivariate beta function

$$ \begin{align*} B (\ut \alpha) & = \frac{\prod_{i = 1}^{k} \Gamma (\alpha_i)}{\Gamma (\sum_{i = 1}^{k} \alpha_i)} \end{align*} $$

such that, the pdf of Dirichlet distribution can be express as

$$ \begin{align*} P (\ut \theta | \ut \alpha) & = \frac{1}{B (\ut \alpha)} \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} \end{align*} $$

Since the property of pdf

$$ \begin{align*} 1 = \int P (\ut \theta | \ut \alpha) d \ut \theta = \frac{1}{B (\ut \alpha)} \int \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} d \ut \theta \end{align*} $$

Hence

$$ \begin{align*} B (\ut \alpha) = \int \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} d \ut \theta \end{align*} $$

Conjugate Prior

Based on Bayes' theorem

$$ \begin{align*} \underbrace{p (\theta | x)}_{\text{posterior}} & = \underbrace{p (\theta)}_{\text{prior}} \times \underbrace{p (x | \theta)}_{\text{likehood}} \div \underbrace{p (x)}_{\text{marginal}} \\ & = \frac{p (\theta) p (x | \theta)}{\int p (\theta) p (x | \theta) d \theta} \\ & \propto p (\theta) p (x | \theta) \end{align*} $$

If prior $p (\theta)$ and posterior $p (\theta | x)$ are the same type of distribution, called this prior is conjugate prior, and using conjugate distribution makes it easier to calculate posterior from poior.

Given $\ut X \sim \text{Mult} (n, \ut \theta)$, where the prior of parameter is $\ut \theta \sim \text{Dir} (\ut \alpha)$, then the posterior is

$$ \begin{align*} p (\ut \theta | \ut x, \ut \alpha) & \propto p (\ut \theta | \ut \alpha) p (\ut x | \ut \theta) \\ & = \left[ \frac{1}{B (\ut \alpha)} \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} \right] \left[ \frac{n!}{\prod_{i = 1}^{k} (x_i!)} \prod_{i = 1}^{k} \theta_i^{x_i} \right] \\ & \propto \prod_{i = 1}^{k} \theta_i^{\alpha_i + x_i - 1} \end{align*} $$

i.e. $\theta | \ut x, \ut \alpha \sim \text{Dir} (\ut x + \ut \alpha)$, so that, Dirichlet distribution is the conjugate prior of multinomial distribution.

Modeling

Simplified model

Given $k$ topics, $V$ words, parameters $\ut \alpha \in \bb R^{K}$ and $\ut \beta \in \bb R^{V}$, LDA assume number of $N$ words document generated by

1. Generate word distribution under each topic $\ut {\varphi_k} \sim \text{Dir} (\ut \beta)$ for $k = \conti{K}$.
2. Generate topic distribution under documents $\ut {\theta} \sim \text{Dir} (\ut \alpha)$.
3. Generate word under documents
   1. Select topics under each position $z_n \sim \text{Mult} (\ut \theta)$ for $n = \conti{N}$。
   2. Select the word under each position $w_n \sim \text{Mult} (\ut {\varphi_{z_n}})$ for $n = \conti{N}$.

Example

Given 2 topics, 100 words, parameter $\alpha = (2, 1)$ express the topics (math, sport) and $\beta = (2, 2, 0.1, 2, 2, \cdots)$ express the words (number, function, conjugate, rate, sport), then a number of 10 words document generated by

1. Generate word distribution under each topic $\ut {\varphi_k} \sim \text{Dir} (\ut \beta)$ for $k = \conti{K}$.
   • Topic 1 $\ut {\varphi_1} = (0.4, 0.4, 0.08, 0.01, 0.01, \cdots)$, commonly used words are number, function, and conjugate
   • Topic 2 $\ut {\varphi_2} = (0.08, 0.01, 0.01, 0.4, 0.4, \cdots)$, commonly used words are rate and sport
2. Generate topic distribution under documents $\ut {\theta} \sim \text{Dir} (\ut \alpha)$.
   • Prefer math topics $\ut \theta = (0.9, 0.1)$
3. Generate word under documents
   • Because $\phi$ is partial to the first dimension, the sampling result of $\text{Mult} (\ut \theta)$ is likely to be 1, but not 2; assuming $z_1 = z_2 = \cdots = z_9 = 1$, $ z_{10} = 2$.
   • Generate the 1-th word, $w_1 \sim \text{Mult} (\ut {\varphi_{z_1}}) = \text{Mult} (\ut {\varphi_1})$, words such as number, function, and conjugate are prone to appear
   • Generate the 2-th word, $w_2 \sim \text{Mult} (\ut {\varphi_{z_2}}) = \text{Mult} (\ut {\varphi_1})$, words such as number, function, and conjugate are prone to appear
   • $\vdots$
   • Generate the 10-th word, $w_{10} \sim \text{Mult} (\ut {\varphi_{z_{10}}}) = \text{Mult} (\ut {\varphi_2})$, words such as rate and sport prone to appear

As can be seen in this example, $\ut{\varphi_1}$ and $\ut{\varphi_2}$ determine the common words under each topic.

Full Model

LDA assumes that $K$ is known and is selected through experiments in practice. Some experimental results show that 20 topics are enough; If $\ut \alpha$ and $\ut \beta$ do not have prior knowledge, it is recommended to set all components of $\ut \alpha$ and $\ut \beta$ to 1. Now consider $K$ topics, $V$ words, and $M$ documents. The number of words in the documents is $(\contia{N}{M})$. Then the LDA generation sequence is

1. Generate word distribution under each topic $\ut {\varphi_k} \sim \text{Dir} (\ut \beta)$ for $k = \conti{K}$.
2. Generate topic distribution under each documents $\ut {\theta_m} \sim \text{Dir} (\ut \alpha)$ for $m = \conti{M}$
3. Generate word under documents
   1. Select topics under each position $z_{mn} \sim \text{Mult} (\ut {\theta_m})$ for $m = \conti{M}$ and $n = \contia{N}{m}$
   2. Select the word under each position $w_{mn} \sim \text{Mult} (\ut {\varphi_{z_{mn}}})$ for $m = \conti{M}$ and $n = \contia{N}{m}$

wher $\ut {\varphi_k}$ determine the distribution of words under each topic, $\ut {\theta_m}$ determine the topic distribution for each document.

Simplified notation

1. Use $\bs \varphi = \{\ut {\varphi_k}\}_{k = 1}^{K} \in \bb R^{K \times V}$ represents word distribution matrix
2. Use $\bs \theta = \{\ut {\theta_m}\}_{m = 1}^{M} \in \bb R^{M \times K}$ represents topic distribution matrix
3. Use $\bs z = \{\ut {z_m}\}_{m = 1}^{M}$ represents topics matrix
4. Use $\bs w = \{\ut {w_m}\}_{m = 1}^{M}$ represents words matrix

Then given the parameters $\alpha$ and $\beta$, the complete probability model can be expressed as the multiplication of the probabilities of $m$ documents

$$ \begin{align*} p (\bs w, \bs z, \bs \theta, \bs \varphi | \ut \alpha, \ut \beta) & = \prod_{k = 1}^{K} p (\ut {\varphi_k} | \ut \beta) \prod_{m = 1}^{M} p (\ut {\theta_m} | \ut \alpha) \prod_{n = 1}^{N_m} p (z_{mn} | \ut {\theta_m}) p (w_{mn} | \ut {\varphi_{z_{mn}}}) \\ & = \prod_{m = 1}^{M} p (\ut {w_m}, \ut {z_m}, \ut {\theta_m}, \bs \varphi | \ut \alpha, \ut \beta) \end{align*} $$

the probability of $m$-th is

$$ \begin{align*} p (\ut {w_m}, \ut {z_m}, \ut {\theta_m}, \bs \varphi | \ut \alpha, \ut \beta) & = \prod_{k = 1}^{K} p (\ut {\varphi_k} | \ut \beta) p(\ut {\theta_m} | \ut \alpha) \prod_{n = 1}^{N_m} p (z_{mn} | \ut {\theta_m}) p (w_{mn} | \ut {\varphi_{z_{mn}}}) \end{align*} $$

first part $p (\ut {\varphi_k} | \ut \beta) p(\ut {\theta_m} | \ut \alpha)$ are two independent Dirichlet probability, the other part $p (z_{mn} | \ut {\theta_m}) p (w_{mn} | \ut {\varphi_{z_{mn}}})$ is a two step multinomial probability, but $\bs z$ is unobserved, only $\bs w$ observed, so instead calculate marginal PDF of $(\ut {w_m} | \ut {\theta_m}, \bs \varphi)$

$$ \begin{align*} p (\ut {w_m} | \ut {\theta_m}, \bs \varphi) & = \sum_{k = 1}^{K} \left[ \prod_{n = 1}^{N_m} p (z_{mn} | \ut {\theta_m}) p (w_{mn} | \ut {\varphi_{z_{mn}}}) \middle| z_{mn} = k \right] \\ & = \prod_{n = 1}^{N_m} \left[ \sum_{k = 1}^{K} p (z_{mn} = k| \ut {\theta_m}) p (w_{mn} | \ut {\varphi_k}) \right] \end{align*} $$

where $\bs \theta$ and $\bs \varphi$ are still unobserved, so we calculate marginal PDF again, each document appearing under the given prior parameters $\ut \alpha$ and $\ut \beta$ is

$$ \begin{align*} p (\ut {w_m} | \ut \alpha, \ut \beta) & = \prod_{k = 1}^{K} \int \int p (\ut {\varphi_k} | \ut \beta) p (\ut {\theta_m} | \ut \alpha) p (\ut {w_m} | \ut {\theta_m}, \bs \varphi) d \ut {\theta_m} d \ut {\varphi_k} \end{align*} $$

the joint PDf of all documents is

$$ \begin{align*} p (\bs w | \ut \alpha, \ut \beta) = \prod_{m = 1}^{M} p (\ut {w_m} | \ut \alpha, \ut \beta) \end{align*} $$

Parameter Estimation

The probability model contains three hidden parameters $\bs z$ (topic of each word), $\bs \theta$ (topic distribution) and $\bs \varphi$ (single word distribution), which are the estimation targets, from $\bs z$ starts. Consider the first document, let $w, z, \varphi, \theta$ represent the corresponding $\ut {w_1}, \ut {z_1}, \ut {\varphi_1}, \ut {\theta_1}$ of the first document, given the documents and parameters, the topic distribution probability of each word is as follows

$$ \begin{align*} p (z | w, \ut \alpha, \ut \beta) = \frac{p (w, z | \ut \alpha, \ut \beta)}{p (w | \ut \alpha, \ut \beta)} \end{align*} $$

The parts of the denominator are known and the numerator can be split into two parts

$$ \begin{align*} p (w, z | \ut \alpha, \ut \beta) & = p (w | z, \ut \alpha, \ut \beta) p (z | \ut \alpha, \ut \beta) \\ & = p (w | z, \ut \beta) p (z |\ut \alpha) \end{align*} $$

Process the first part first, let $\varphi_{kv}$ be the probability of the $v$th word under the $k$th topic, let $n_{kv}$ be the number of occurrences of the $v$th word under the $k$th topic, and let $n_k = \{ n_{k1}, n_{k2}, \cdots, n_{kV} \}$

$$ \begin{align*} p (w | z, \ut \beta) & = \int p (w | z, \varphi) p (\varphi, \ut \beta) d \varphi \\ & = \int \left[ \prod_{k = 1}^{K} \prod_{v = 1}^{V} \varphi_{kv}^{n_{kv}} \right] \left[ \frac{1}{B (\ut \beta)} \prod_{v = 1}^{V} \varphi_{k_v}^{\beta_v - 1} \right] d \varphi \\ & = \prod_{k = 1}^{K} \frac{1}{B (\ut \beta)} \int \prod_{v = 1}^{V} \varphi_{kv}^{n_{kv} + \beta_v - 1} d \varphi \\ & = \prod_{k = 1}^{K} \frac{B (\ut {n_k} + \ut \beta)}{B (\ut \beta)} \end{align*} $$

Similarly, let $n_{mk}$ is the number of occurrences of the $k$th topic in the $m$th document, and $n_m = \{ n_{m1}, n_{m2}, \cdots, n_{mK} \}$

$$ \begin{align*} p (z | \ut \alpha) & = \int p (z | \theta) p (\theta, \ut \alpha) d \theta \\ & = \prod_{m = 1}^{M} \frac{B (\ut {n_m} + \ut \alpha)}{B (\ut \alpha)} \end{align*} $$

Combining the above formula, we can get

$$ \begin{align*} p (w, z | \ut \alpha, \ut \beta) = \prod_{k = 1}^{K} \frac{B (\ut {n_k} + \ut \beta)}{B (\ut \beta)} \prod_{m = 1}^{M} \frac{B (\ut {n_m} + \ut \alpha)}{B (\ut \alpha)} \end{align*} $$

such that

$$ \begin{align*} p (z | w, \ut \alpha, \ut \beta) = \frac{1}{p (w | \ut \alpha, \ut \beta)} \prod_{k = 1}^{K} \frac{B (\ut {n_k} + \ut \beta)}{B (\ut \beta)} \prod_{m = 1}^{M} \frac{B (\ut {n_m} + \ut \alpha)}{B (\ut \alpha)} \end{align*} $$

However, $\ut {n_k}$ and $\ut {n_m}$ are unknown and can be estimated through Gibbs sampling.

References

1. LI, Hang. Machine Learning Methods. Springer Nature, 2023.

Errata

This article contains a certain amount of errors. I will list the formulas with errors. Red are errors and green are corrections.

$$ \begin{align} \tag{20.2} p (\theta | \alpha) = \frac{\Gamma \left( \sum_{i = 1}^{k} \alpha_i \right)}{\prod_{i = 1}^{k} \Gamma (\alpha)^{\color{red}{k}}} \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} \\ \notag p (\theta | \alpha) = \frac{\Gamma \left( \sum_{i = 1}^{k} \alpha_i \right)}{\prod_{i = 1}^{k} \Gamma (\alpha)} \prod_{i = 1}^{k} \theta_i^{\alpha_i - 1} \end{align} $$$$ \begin{align} \tag{20.16} & p (\bs w_m, \bs z_m, \theta_m, \varphi | \alpha, \beta) \\ \notag = & \prod_{k = 1}^{K} p (\phi_k | \beta) p (\theta_m | \alpha) \prod_{\textcolor{red}{m} = 1}^{N_m} p (z_{mn} | \theta_m) p (w_{mn} | z_{mn}, \varphi) \\ \notag = & \prod_{k = 1}^{K} p (\phi_k | \beta) p (\theta_m | \alpha) \prod_{\textcolor{green}{n} = 1}^{N_m} p (z_{mn} | \theta_m) p (w_{mn} | z_{mn}, \varphi) \end{align} $$$$ \begin{align} \tag{20.18} p (\bs w_m, | \theta_m, \varphi) & = \prod_{\textcolor{red}{n} = 1}^{K} \int p (\varphi_k | \beta) \\ \notag & = \prod_{\textcolor{green}{k} = 1}^{K} \int p (\varphi_k | \beta) \end{align} $$$$ \begin{align} \tag{20.23} p (w | z, \beta) & = \int p (w | z, \textcolor{red}{\beta}) p (\varphi | \beta) d \varphi \\ \notag & = \int p (w | z, \textcolor{green}{\varphi}) p (\varphi | \beta) d \varphi \\ \end{align} $$$$ \begin{align} \tag{20.27} & p (z_i | \text{z}_{-i}, w, \alpha, \beta) \\ \notag \propto & \frac{n_{kv} + \beta_v}{\sum_{v \textcolor{red}{-} 1}^{V} (n_{kv} + \beta_v)} \cdot \frac{n_{mk} + \alpha_k}{\sum_{k = 1}^{K} (n_{mk} + \alpha_k)} \\ \notag \propto & \frac{n_{kv} + \beta_v}{\sum_{v \textcolor{green}{=} 1}^{V} (n_{kv} + \beta_v)} \cdot \frac{n_{mk} + \alpha_k}{\sum_{k = 1}^{K} (n_{mk} + \alpha_k)} \\ \end{align} $$