string; “0” is appended to the bit string if we go up, and “1” is appended if we godown.
For example, in Figure 3.1,{trees, capacity, length}is encoded by “100”,{structure, data, tree, graph, separate, node} is encoded by “110”, {in, of} is encoded by “010”, {widely, hierarchical} is encoded by “1111”, and so on. Each word in a cluster is represented by its cluster’s bit string.
If we view a cluster as an abstraction of a word, we can choose the arbitrary level of abstraction of a word in a hierarchical clustering. Indeed, we can use a prefix of a bit string as a representation of higher abstraction level. For example, in Figure 3.1, if we choose the prefix “11”, both words “tree” (110) and “hierarchical” (1111) become the member of a cluster at higher level abstraction.
This multi-level of abstraction in word representation helps our model can capture the semantic similarity of words at many levels. This is helpful in previous researches [53, 94].
Model [100], which can be applied to the process of topic analysis. While still being able to capture rich relationships between topics in a collection, LDA is simpler than these models. For this reason, we choose LDA for the topic analysis step in our proposal. More details about LDA are given in the subsequent sections.
3.3.1 Latent Dirichlet Allocation
Latent Dirichlet Allocation (LDA) [13, 39, 44] is a generative graphical model as shown in Figure 3.2. It can be used to model and discover underlying topic structures of any kind of discrete data in which text is a typical example. LDA was developed based on an assumption of the document generation process depicted in both Figure 3.2 and Algorithm 3.1.
Figure 3.2: The generative graphical model of LDA.
We begin the presentation of LDA with some common notations:
• M: the total number of documents to generate (const scalar)
• K: the number of latent topics (const scalar)
• V: number of termst in vocabulary (const scalar)
• ⃗α: Dirichlet parameters
• ⃗θm: topic distribution for document m
• Θ = {⃗θm
}M m=1
: a M ×K matrix
• ϕ⃗k: word distribution for topick
• Φ = {ϕ⃗k
}K k=1
: a K ×V matrix
• Nm: the length of document m, here modeled with a Possion distribution with constant parameter ξ
• zm,n: topic index of n-th word in document m
Algorithm 3.1: Generation process of LDA
1 foreach document m ∈[1, M] do
2 sample mixture proportion ⃗θm ∼Dir(⃗α)
3 sample document length Nm ∼Poisson(ξ)
4 foreach word n∈[1, Nm]do
5 sample topic index zm,n ∼Mult(⃗θm)
6 sample term for word wm,n ∼Mult(φ⃗zm,n)
7 end
8 end
• wm,n: a particular word for word placeholder [m, n]
The generative process can be interpreted as follows. A document containing Nm
words w⃗m = {wm,n}Nn=1m is generated by first picking a distribution over topics θ⃗m from a Dirichlet distribution Dir(⃗α), which determines topic assignments for words in that document. Then the topic assignment for each word placeholder [m, n] is performed by sampling a particular topic zm,n from multinomial distribution Mult(⃗θm). Finally, a particular word wm,n is generated for the word placeholder [m, n] by sampling from multinomial distribution Mult(φ⃗zm,n). The topics φ⃗k are sampled once for the entire corpus.
From the generative graphical model depicted in Figure 3.2, we can write the joint distribution of all known and hidden variables given the Dirichlet parameters as follows.
p (
⃗
wm, ⃗zm, ⃗θm|⃗α,Φ )
=
∏M n=1
p (
wm,n|ϕ⃗zm,n )
p (
zm,n|⃗θm )
p (⃗θm|α⃗
)
(3.11) And the likelihood of a document w⃗m is obtained by integrating over⃗θm and summing over⃗zm as follows.
p(w⃗m|α,⃗ Φ) =
∫ p
(⃗θm|α⃗ )∏M
n=1
p (
wm,n|⃗θm,Φ )
d⃗θm (3.12)
Finally, the likelihood of the whole data collection W = {w⃗m}Mm=1 is the product of the likelihood of all documents:
p(W|⃗α,Φ) =
∏M m=1
p(w⃗m|⃗α,Φ) (3.13)
3.3.2 Gibbs Sampling
LDA Estimation
Parameter estimation for LDA by directly and exactly maximizing the likelihood of the whole data collection in Equation 3.13 is intractable. One solution is to use approximate estimation methods such as variational methods [13] or Gibbs sampling [39]. Gibbs sam-pling is a special case of Markov-Chain Monte Carlo (MCMC) and often yields relatively simple algorithms for approximate inference in high-dimensional models such as LDA.
Let w⃗ and ⃗z be the vectors of all words and their topic assignment of the whole data collection W. Gibbs sampling approach [39] is not explicitly representing Φ or Θ as parameters to be estimated, but instead considering the posterior distribution over the assignments of words to topics, p(⃗z|w). We then obtain estimates of Φ and Θ by using⃗ this posterior distribution. In order to estimate the posterior distribution, Griffiths et al.
[39] used the probability model for LDA with the addition of a Dirichlet prior on Φ. The complete probability model is as follows.
wi|zi,Φ(zi) ∼ Mult(Φ(zi)) Φ ∼ Dir(β) zi|Θ(di) ∼ Mult(Θ(di))
Θ(di) ∼ Dir(α)
Here, α and β are hyper-parameters, specifying the nature of the priors on Θ and Φ.
These hyper-parameters could be vector-valued or scalar. The joint distribution of all variables given these parameters is p(w, ⃗⃗ z,Θ,Φ|α, β. Because these priors are conjugate to the multinomial distributions Φ and Θ, we are able to compute the joint distribution p(w, ⃗⃗ z) by integrating out Φ and Θ.
Using this generative model, the topic assignment for a particular word can be cal-culated based on the current topic assignment of all the other word positions. More specifically, the topic assignment of a particular word t is sampled from the following multinomial distribution.
p(zi =k|⃗z¬i, ⃗w) = n(t)k,¬i+βt
∑V
v=1
(
n(v)k +βv
)−1· n(k)m,¬i+αk
∑K
j=1
(
n(j)m +αj )−1
(3.14) where
• n(t)k,¬i is the number of times the word t is assigned to topic k except the current assignment;
• ∑V
v=1n(v)k −1 is the total number of words assigned to topic k except the current assignment;
• n(k)m,¬i is the number of words in document m assigned to topic k except the current assignment;
• ∑K
j=1n(j)m −1 is the total number of words in document m except the current word t.
In normal cases, Dirichlet parameters ⃗α and β⃗ are symmetric, that is, all αk (k = 1. . . K) have the same value, and so doβv (v = 1. . . V).
After finishing Gibbs Sampling, two matrices Φ and Θ are computed as follows.
ϕk,t = n(t)k +βt
∑V
v=1n(v)k +βv (3.15)
θm,k = n(k)m +αk
∑K
j=1n(j)m +αj (3.16)
LDA Inference
Given an estimated LDA model, we can now perform topic inference for unknown docu-ments by a similar sampling procedure as previous [44]. A new document ˆm is a vector of words ˆw⃗m; our goal is to estimate the posteria distribution of topics ˆ⃗z given the word vector ˆw⃗ and the LDA modelL(Θ,Φ): p(⃗z|w, L) =⃗ p(ˆ⃗z,w, ⃗⃗ˆ z, ⃗w). Here,w⃗ and⃗z are vectors of all words and topic assignment of the data collection upon which we estimate the LDA model. The similar reasoning is made to get the Gibbs sampling update as follows.
p( ˆzi =k|⃗zˆ¬i,w;⃗ˆ ⃗z¬i, ⃗w) = n(t)k + ˆn(t)k,¬i+βt
∑V v=1
(
n(v)k + ˆn(v)k +βv
)−1 · n(k)m,ˆ ¬i+αk
∑K j=1
(
n(j)mˆ +αj )−1
(3.17)
where the new variable ˆn(t)k counts the observation of termtand topickin new documents.
This equation gives an illustrative example of how Gibbs sampling works: high estimated word-topic associationn(t)k will dominate the multinomial masses in comparison with the contributions of ˆn(t)k and n(t)mˆ , the masses of topic-word associations are propagated into document-topic associations [44].
After performing topic sampling, the topic distribution of new document ˆm is ⃗θmˆ = {θm,1ˆ , . . . , θm,kˆ , . . . , θm,Kˆ }where each component is calculated as follows.
θm,kˆ = n(k)mˆ +αk
∑K
z=1n(z)mˆ +αz
(3.18)