Latent Dirichlet Allocation - Part.1

In this post, we will explore Latent Dirichlet Allocation (LDA).

It's interesting that LDA is used as an acronym for two different concepts, but fortunately, both are related to 'dimension reduction'.

1. Latent Dirichlet Allocation

2. Linear Discriminant Analysis (To avoid confusion, I will refer to this as LDAs)

LDAs' main function, like PCA, is dimension reduction. This function, of course, means that it can be used in other situations, but its inherent purpose is dimension reduction. On the other hand, LDA's main function is not dimension reduction but Topic Modeling, and the definition of Topic Modeling, borrowing from the expression in the paper, is as follows:

"To find short descriptions of the members of a collection that enable efficient processing of large collections while preserving the essential statistical relationships that are useful."

In other words, it's about representing vast and numerous documents with simple descriptions, and finding the 'Topic' that can represent those documents. Therefore, it can also serve the role of dimension reduction.

By using LDA, you can explore the following:

• What topics are the documents talking about?

• What topic is a single document talking about?

• What words are included in a specific topic?

• In which topic are specific words used?

We will unravel these one by one as the explanation progresses. LDA has made significant efforts to semantically reflect these in their formula.

LDA's objective is very simple. However, the formulas used and their background principles are quite complex, and if you fully understand LDA, it means you have a solid foundation in Bayesian statistics or probability. Therefore, materials explaining LDA often try to deliver the overall framework while leaving out difficult concepts. But in this post, we will look at the original paper,

"Latent Dirichlet allocation - David M. Blei, Andrew Y. Ng, Michael I.Jordan,"

and aim to explore its background and deeper principles. However, I can't explain everything about LDA from A to Z due to the complexity of the technique. While studying, I felt that some crucial concepts in the paper disappeared in explanatory materials, and as these were adopted by others, the basic background began to fade away. Therefore, I will try to reflect these points as much as I read through the paper. For this purpose, I will follow the order of the paper as much as possible, but I will add explanations where necessary.

Then, let's first look at the background of LDA's birth.

Introduction

LDA's Origin, Information Retrieval

LDA's purpose, as explained in the introduction, is to "simply" represent a multitude of documents. This attempt was not first started in the machine learning field but in the Information Retrieval (IR) field. What IR aimed for was to represent numerous documents on the internet as simple numbers based on "frequency". To this end, they used the concept of TF-IDF, which goes beyond the simple frequency of words appearing in a document to reflect the frequency of words in the entire document collection.

$tf_{i,j}=$ number of occurrences of $i$ in $j$

$df_i =$ number of documents containing $i$

$N =$ total number of documents

However, the dimension reduction capability of TF-IDF was not very significant. To show better performance than this, Latent Semantic Indexing (LSI) appeared. LSI applies Singular Value Decomposition (SVD) to a Matrix that represents word frequencies and documents, aiming to find a Subspace that maintains as much variance as possible. When using LSI, it is said that it represents linear combinations of TF-IDF, and it has the advantage of being able to capture the relationship of synonyms and polysemes.

But LSI also could not satisfy researchers, and Hofmann (1999) proposed pLSI. The concept closest to the principle of LDA is pLSI. pLSI assumes that each word in the document comes from a Mixture Model (Multinomial) of topics. Thus, the words that make up a document will consist of words from various topics (Mixture Components), and if the distribution of these topics is expressed, it becomes the topic distribution of the document. If you have studied LDA even a little, you will feel that this concept is very similar to LDA. However, pLSI is different from LDA, and the part pointed out as a limitation of pLSI is that direct topic assignment is possible for words, but the document derives topics from these words, which is an indirect method.

Then, is there a way to build a probability model for both words and documents? This is where LDA, which overcomes the limitations of pLSI, was born.

1. Notation and Terminology Now that we have looked at the techniques before LDA, we will soon need to look at the procedure of the LDA technique

. But before that, let's organize the notation once as done in the paper.

• Word: Represented as an index of words contained in a document. If there are V words, it is expressed as $1,…,V$. However, since the words are Discrete Data, they will be expressed in the form of One-Hot-Encoding. The paper explains it in a different expression, but eventually, it is an expression of one-hot encoding. We will express this as w.

• Document: A document is a sequence of N words. Therefore, it is expressed as $w = w_1, w_2, w_3 … w_N$. w and w are very confusing, but the paper distinguishes them simply as italic and bold.

• Corpus: A corpus is a collection of M documents. Therefore, it is expressed as $D = w_1, w_2 … w_M$. w has changed to w to use subscripts, but the w in D is a document.

Since it will be uncomfortable to use the paper's expression when explaining, let's express Word as w, Document as d, and Corpus as c.

Latent Dirichlet Allocation

LDA: Generative probabilistic model of a corpus

LDA is a generative probability model of a corpus. The fact that it generates means that, assuming the corpus is all the words in the world, it uses these words to create documents. Alternatively, it can be expressed differently, meaning that documents are made through the distribution of latent topics, and each topic is made up of a distribution of words. Let's give a simple example.

Let's say a writer named Leo has to quickly write about any topic. Therefore, she will choose a topic of interest from the 'topic distribution', and when she sits down at her desk and starts writing, the words she will use will naturally reflect that topic. If Leo writes about the topic of 'diet', she will use many words like sweet potato, shake, salad, etc., to describe the diet.

Mixture model

Here, we need to stop and go over the concept of the Mixture Model. A representative example of the Mixture Model is the Gaussian Mixture Model (GMM), which is often used in Clustering. That is, the concept of the Mixture Model itself originally represents the problem of which distribution a certain data belongs to (Cluster). Mixture Model is often used interchangeably with Mixture Distribution, but these two are concepts with different "purposes".

• Mixture Distribution: Obtaining the characteristics of the entire population from subgroups.

• Mixture Model: Statistical inference about the characteristics of subgroups when a given group is observed.

Just as GMM tries to identify subgroups (Clusters) from the entire distribution, LDA assumes that there are latent topics (Latent Topics) and judges which subtopics the currently viewed document belongs to. And it means that we will view the distribution of Latent Topics as a Dirichlet distribution. If we follow the name LDA once again,

• Latent Dirichlet Allocation ⇒ Allocating Topics by setting Latent Topic Distribution as Dirichlet.

This is what it means.

Dirichlet Distribution

The Dirichlet distribution is the posterior probability distribution of the conjugate prior distribution. The conjugate prior distribution means that when the posterior probability distribution $p(\theta|x)$ and the prior distribution $p(\theta)$ are tied to the same family group. This concept is used in Bayesian statistics to update the posterior using the prior, and when the prior and posterior distributions are tied to the same family group, it is convenient to calculate, so the conjugate prior distribution is used. It can be expressed in a formula as $P(\theta|X) = P(X|\theta) * P(\theta)$

and the purpose of the formula is to find the left-hand term $P(\theta|X)$, which means the probability distribution of the parameters when data are given. $P(X|\theta)$ on the right-hand side represents the distribution of data when the probability distribution is given, and $P(\theta)$ represents the probability distribution of the parameters. If we organize this in words following the formula (starting from the right-hand term),

Multiplying the (probability distribution of parameters) and the (distribution of data when that probability distribution is given) yields the (distribution of parameters when data exist). In other words,

Multiplying the (Prior Distribution) and the (Likelihood) yields the (Posterior Distribution), and if we apply this tothe (kinetic) flow of LDA, it can be expressed as:

(The predefined Topic Distribution - [Prior] Dirichlet) * (Distribution of words when the Prior is set) = (Topic Distribution when the distribution of words exists - [Posterior] Multinomial).

Thus, there is a clear reason for using Conjugate Prior / Posterior in LDA.

LDA Procedure

LDA follows this procedure to create each Document $d$ from the entire Corpus $c$ :

1. Choose $N$ ~ Poisson($ξ$).

2. Choose $θ$ ~ Dir($α$).

3. For each of the N words $w_n$: (a) Choose a topic $z_n$ ~ Multinomial($θ$). (b) Choose a word $w_n$ from $p(w_n|z_n,β)$, a multinomial probability conditioned on the topic $z_n$.

This procedure has additional details:

• The dimension $k$ of the Dirichlet Distribution is known and fixed (as the Dirichlet distribution is a prior, it is naturally set by the user).

• $β$ is the word probability, composed as a $k * V$ matrix, representing the (Number of Topics * Number of Words) matrix.

• There are some questions about $β$ as described in the paper. Other materials often describe both $α$ and $β$ as parameters of the Dirichlet Distribution, with $α$ controlling the document-topic distribution and $β$ controlling the topic-word distribution. However, if the paper also used this meaning, $α$ and $β$ should be explained together, but it is specified as a matrix. Therefore, I think $β$ itself is a Dirichlet Distribution of $k * V$ dimensions, with $V$ - dimensional distributions for $k$ topics.

• The Poisson distribution does not have much impact on the procedure and can be omitted. This can be seen in various LDA-related materials online, where the Poisson distribution is often omitted. This is because $N$ represents the length of a document, and in reality, the length of words is not fixed.

Simplex

A $k$-dimensional Dirichlet random variable $θ$ can take values in the $(k-1)$ simplex.

The above sentence, taken directly from the paper, means that a random variable extracted from a $k$-dimensional Dirichlet distribution exists on a $k-1$ dimensional simplex. But what exactly is a simplex? While simplex has various definitions in different fields, in probability theory, it means "Space of all probabilities distributions with support N". Depending on $k$, you can define simplex as follows:

• 0-simplex is a point.

• 1-simplex is a line segment.

• 2-simplex is a triangle.

Although I don't fully grasp it yet, I will guide you on how to apply this to the Dirichlet Distribution.

A point I missed when mentioning the Dirichlet Distribution earlier is that Dirichlet is a 'distribution of distributions'. Specifically, it contains distributions of Multinomials, and we sample these distributions. The best example to visualize this is a Dirichlet distribution with $k = 3$, i.e., a 2-simplex, which we will look at.

$k = 3$ means that we are dealing with 3 Topics, and we obtain the probability Prior Distribution for these 3 Topics from the Dirichlet Distribution. At this time, you can contain a 3-dimensional probability distribution in the form of a triangle simplex.

And if you look closely, do you see numbers on the triangle? These numbers represent $α$ in "Choose $θ$ ~ Dir($α$)". In LDA, the Dirichlet Distribution used is symmetric. That is, one $α$ is used equally regardless of how many dimensions the distribution has. As $α$ increases, the 3-dimensional probability distribution gathers in the center, meaning that each probability has many points with equal values. Conversely, as $α$ decreases, they scatter, gathering at the vertices, which means that the probability of each Topic appearing is concentrated in one Topic. Depending on the form of your data, choosing $α$ is a smarter way to use LDA.

LDA, as Bayesian Network

When parameters $α$ and $β$ exist, the joint distribution formula for the mixture $θ$ of topics,

$N$ topics $z$, and $N$ words $w$ can be expressed as follows:

$p(θ, z, w|α, β) = p(θ|α) ∏_{i=1}^{N} p(z_n|θ) p(w_n|z_n, β)$

Reading the right-hand side of the formula, it surprisingly makes sense. However, there is doubt about whether such a joint distribution interpretation is appropriate or forced. Reading it:

• $p(θ|α)$: The probability of $θ$ given $α$ - Dirichlet distribution $θ$ when $α$ is given.

• $p(z_n|θ)$: The probability of $z_n$ given $θ$ - Topic $z_n$ of a word when the prior distribution $θ$ is given.

• $p(w_n|z_n, β)$: The probability of $w_n$ given $z_n, β$ - The word itself when the topic of the word is determined.

Therefore, the left-hand side joint distribution $p(θ, z, w|α, β)$ multiplies the Dirichlet distribution $θ$ given $α$ with the distribution of topics $z_n$ and words $w_n$ in the document. However, the usual factorization of joint distributions is done as follows:

$p(x_1, x_2, …, x_K) = p(x_K|x_1, …, x_{k-1}) … p(x_2|x_1) p(x_1)$

Thus, the joint distribution interpretation used in LDA is different from the standard form and can be explained as a Bayesian Network. However, the paper only examines Bayesian Statistical Modeling, i.e., prior/posterior distributions, so some parts were not clear.

Bayesian Network is well explained in Professor Moon Il-Chul's lectures at KAIST. I will briefly describe it.

Bayesian Network is a directional graph model where the links in the graph have direction and are represented with arrows. This indicates that the arrows represent conditional probabilities. Below is a Bayesian Network of my recent mood and state, and we will use it to solve the joint distribution.

Thus, even if a joint distribution contains numerous variables, if it is represented or representable as a Bayesian Network, it becomes easier to factorize the joint distribution. But the LDA representation equivalent to the above example of my mood exists.

Latent Dirichlet allocation - Wikipedia

If we consider the above Plate Notation as a Bayesian Network and extract elements to solve the joint distribution $p(θ, z, w|α, β)$, we can express:

• $p(θ|α)$

• $p(z_n|θ)$

• $p(w_n|z_n, β)$

Final Formula Summary with Luis Serrano

When I couldn't quite grasp the 'intuitive' understanding of LDA, I watched a YouTube video by Luis Serrano, who explained the Generative Model of LDA well through diagrams.

We said the Generative Model's Joint Distribution of LDA could be expressed as:

$p(θ, z, w|α, β) = p(θ|α) ∏_{i=1}^{N} p(z_n|θ) p(w_n|z_n, β)$

However, in this video, $β$ is described as a parameter, and the $φ$ Dirichlet distribution using this parameter is clearly depicted (a formula not appearing in the original paper, and I guess it might have been included in subsequent research following the original). If we transform the formula to represent the entire Corpus $c$, it becomes:

Explaining the new formula:

$p(C|α, β) = ∏_{j=1}^{M} P(θ_j; α) ∏_{i=1}^{K} P(φ_i; β) ∏_{t=1}^{N} P(Z_{j, t}|θ_j) P(W_{j, k}|φ_{Z_{j, k}})$

• $∏_{j=1}^{M} P(θ_j; α)$: Obtain the topic distribution $θ$ from the Dirichlet distribution created by $α$.

• $∏_{t=1}^{N} P(Z_{j, t}|θ_j)$: Obtain the topic $Z$ from the acquired topic distribution $θ$.

• $∏_{i=1}^{K} P(φ_i; β)$: Obtain the word distribution $φ$ of the topic from the Dirichlet distribution created by $β$.

• $P(W_{j, t}|φ_{Z_{j, t}})$: Obtain the word $W$ using the acquired word distribution $φ$ of the topic.

LDA and Exchangeability

“What is the key to LDA's success?” “It’s Exchangeability…”

The theoretical background of LDA includes Bayesian Statistics, Mixture Models, and more. However, one of the most fundamental theories, which constitutes an entire chapter in the paper, is De Finetti's Exchangeability.

When random variables $z_1, z_2, …, z_N$ exist, if the probability remains the same even when their order is varied in different ways, and always remains the same regardless of the order, we can say that Exchangeability exists. This can be expressed as:

$p(z_1, …, z_N) = p(z_{π(1)}, …, z_{π(N)})$, where $π$ is a permutation.

And if every subsequence in an infinite sequence of random variables is exchangeable, then the entire sequence is exchangeable.

Initially, I didn't quite grasp this concept because in probabilities like $p(a, b, c) = p(b, a, c) = p(c, a, b)$, the order of elements in the joint distribution doesn't matter. However, the joint distribution of word sequences in a sentence $p(w_1, …, w_N)$ is a probability that should guarantee the order. For example:

$p("our, team's, jungle, is, trash") ≠ p("team's, our, is, trash, jungle")$.

This shows that the probability changes with the order.

De Finetti’s Theorem

De Finetti's theorem, using Exchangeability, provides the following theorem:

$p(X_1, X_2, …, X_N) = ∫(∏_{i=1}^{N} p(X_i|θ))dπ(θ)$

This theorem simplifies the joint distribution significantly, showing that when $θ$ is given, the random variables derived from the distribution $θ$ are independent and identically distributed.

Why is this included in LDA's assumptions?

LDA also ignores the order. In other words, it ignores the order of words. Unlike the previous sentence example where $p("our, team's, jungle, is, trash") ≠ p("team's, our, is, trash, jungle")$, in LDA, they are considered equal due to the Bag of Words assumption. Since all words in the entire Corpus are in one Bag, their order is ignored, enabling Exchangeability. This provides computational advantages in LDA’s model:

$p(θ, z, w|α, β) = p(θ|α) ∏_{i=1}^{N} p(z_n|θ) p(w_n|z_n, β)$

Here, $∏_{i=1}^{N}$ benefits from this. Even using Bayesian Network, there was no theoretical guarantee for $∏_{i=1}^{N}$. However, knowing that words and topics in a document are exchangeable, we can represent probabilities in the document not as a joint distribution but as numerous multiplications.

$( p(θ, z, w|α, β) = p(θ|α) p(w_n, z_n, d)$ ⇒ $p(θ, z, w|α, β) = p(θ|α) ∏_{i=1}^{N} p(z_n|θ) p(w_n|z_n, β)$

Relationship with Other Latent Variable Models

This section compares LDA with simpler latent variable models, such as the Unigram Model and Mixture of Unigrams.

Unigram Model / Mixture of Unigrams, pLSI

Unigram Model

The Unigram model is the simplest model in language models. It assumes each word is independent and calculates the joint distribution as a product of probabilities.

$P(w_1, w_2, …, w_n) = ∏_{i=1}^{n} P(w_i)$ or $P(Words in Document) = ∏_{n=1}^{N} p(w_n)$.

This means that each word is drawn from a single Multinomial Distribution.

Mixture of Unigrams

The Mixture of Unigrams (Unigram + random topic variable $z$) is structured as

follows:

1. First, choose a Topic $z$,

2. Then, independently draw N words from the Conditional Multinomial $p(w|z)$.

Thus, the formula is structured as follows:

$p(d) = ∑_{z} p(z) ∏_{n=1}^{N} p(w_n|z).$

Here, $p(z)$ appears as a weight, and $∏_{n=1}^{N} p(w_n|z)$ acts as the sub-model. The Mixture of Unigrams assumes that only one Topic exists in a document, making the word distribution $p(d)$ effectively represent the Topic.

In the above figures, the left Topic Multinomial Distribution represents $p(z)$, and the chosen $z$'s $p(w|z)$ is represented by the right Multinomial Distribution. However, in the Mixture of Unigrams, since $∑_{z} p(z)$ aggregates each topic one by one, it represents a Single Topic, whereas LDA constructs the formula to include multiple Topics in one document.

Inference and Parameter Estimation

So far, we have learned about the Latent Topic Model, which is how a document or a corpus is created. However, this procedure is not yet Topic Modeling.

When we actually face the goal of Topic Modeling, what do we have in our hands? It's the documents. We only have the documents and the frequency of words contained in them. Therefore, $θ$ and $z$ are unknown to us, and we need to infer and update these parameters through Inference, finding out how the topics in our documents are composed. The word 'Latent' itself means 'hidden', so the process of finding these out is Latent Dirichlet Allocation.

$θ$ and $z$ are Hidden or Latent Variables. That is, except for $w$, nothing is visible. The formula for obtaining the Posterior Distribution to find these is

$p(θ, z|w, α, β) = \frac{p(θ, z, w|α, β)}{p(w|α, β)}$

However, according to the paper and various materials, calculating this formula for Estimation is Intractable, i.e., impossible. Therefore, we resort to approximation methods for calculation.

The approximation method mentioned in the paper is 'Variational Inference'. I still lack the ability to fully understand Variational Inference, but its goal seems to be setting a Lower Bound through Jenkin's Inequality. However, the formulas look quite complex and are filled with numerous complicated expressions.

An easier and simpler method for implementation is Gibbs Sampling, which I will explain.

(Collapsed) Gibbs Sampling

Once Gibbs Sampling starts, it no longer seems like solving a probability problem but rather continuously updating frequency calculations, simplifying the problem. It is widely used and the easiest and most certain method among various approximation techniques. The Python-implemented 'lda' also applies Gibbs Sampling.

I will start by explaining Gibbs Sampling.

Gibbs Sampling involves quite a bit of formula calculation, and it would be better to watch Professor Gang Pil-Seong's 'Topic Modeling - Part 3' rather than me explaining it line by line. Therefore, I will only cover the basic concept here, and we will look at the code implementation together.

The basic idea of Gibbs Sampling is, "By fixing other variables and changing only one variable and updating it, all variables are automatically updated." Based on this, the distribution we fundamentally want to calculate is:

$p(z_i = j|z_{(-i)}, w)$

This is the probability that the topic of the $i$-th word in a document is $j$ after erasing the topic information of the $i$-th word. To derive this, the most probable topic from the remaining topic distribution is inserted into the erased topic information after erasing the topic information. Repeating this process, similar to the EM algorithm, will converge to the optimal Topic Distribution.

But here's a question: Isn't Topic Modeling about calculating

• $θ$: Topic Distribution within a document,

• $φ$: Word Distribution within a Topic?

Why, then do we only iterate with $z$, the topic of words, as the subject of interest? Shouldn't there be direct calculations for the above two distributions?

This is because if you calculate $z$ through a process like Gibbs Sampling, the actual goal of the two distributions above is derived automatically. If we calculate $z$ for all words in the Corpus, we know the topics of each word. Then, we can determine the topic distribution of each document ($θ$) by aggregating the topics of words in each document. Similarly, by selecting a topic and examining the distribution of words contained in it, we can determine the word distribution within a topic ($φ$). The appearance of (Collapsed) in the title refers to the fact that $θ$ and $φ$ do not need to be inferred directly in the process of inference, as the calculations revolve around z.

Ultimately, after several complex formulas, the following final formula is derived:

$\propto$ Topic weight over document $\times$ Word weight over Topic

This formula guides how updates are carried out and how conclusions are reached.