Topic Modeling with Document Relative Similarities

1 Introduction

Topic modeling has been a popular text analysis method [Blei et al., 2003]. In topic models, it is assumed that a document is generated by a mixture of topics, each of which is a distribution over words in the vocabulary. By fitting the models, we can represent each document through the learned topics as well as understand the topics in the corpus through the most probable words of each topic. Classical topic models such as Probabilistic Latent Semantic Analysis (PLSA) [Hofmann, 1999] and Latent Dirichlet Allocation (LDA) [Blei et al., 2003] have shown impressive success in modeling text documents.

Despite the success of the above two topic models, they cannot directly incorporate metadata such as the author or the posting time of a document to improve the quality of the learned topics. To tackle this problem, many augmented topic models have been developed (e.g. [Rosen-Zvi et al., 2004; Wang and McCallum, 2006; Mcauliffe and Blei, 2008]). Depending on the nature of the metadata, different models make different assumptions about the relations between the metadata and the underlying topic mixture of each document and/or the word distributions of topics.

Generally, most of these models rely on the assumption that documents with the same attribute values (e.g. same authors or same publishing time) tend to have similar topic distributions. This assumption can be captured by establishing a dependency between the topic distributions of documents and the metadata, where the metadata can be either categorical (e.g. [Rosen-Zvi et al., 2004]) or numerical (e.g. [Wang and McCallum, 2006]). However, metadata may not always be in the form of categorical or numerical attribute values. For example, given documents A, B and C, one may point out that A is more similar to B than to C. Presumably, this kind of relative similarity can also help topic modeling; document A's topic distribution should be closer to B's than to C's.

In many scenarios, relative similarities may be easier to obtain than categorical or numerical attributes. For example, to an online user with a particular information need, it is easier to ask her to compare two Web pages and point out which one is more relevant than to ask her to score each Web page. Given a set of research papers, it might be easier to identify similar papers than to assign categorical labels to the papers. Even for documents with categorical or numerical attributes, sometimes it may also be meaningful to consider relative similarities derived from the attribute values. For example, a document written by a 10-year-old is more similar to a document written by a 12-year-old than by a 20-year-old. The value of the absolute age difference is not so important; we generally would not consider the difference between a 10-year-old and a 20-year-old to be 5 times that of the difference between a 10-year-old and a 12-year-old. Instead, the relative difference or similarity is more useful.

In this paper, we study topic modeling on documents with this kind of relative similarities. Our goal is to explore a general model that can utilize such constraints without manipulating the graphical structure of the classical topic models. The intuition is to facilitate the collaboration between topic models and the constraints. Specifically, we first transform the constraints into a loss function, and then design an objective function that combines the log likelihood of the corpus with the loss function. Essentially, the loss function acts as a regularizer for the log likelihood of text, ensuring that the parameters that minimize the overall objective function balance between fitting the text and satisfying the relative similarity-based constraints. To fit our model, we use the Gibbs-EM algorithm, an algorithm that alternates between collapsed Gibbs sampling and gradient descent.

We evaluate our model with two datasets, 20 newsgroups and TDT2. Experimental results show that our model outperforms LDA in terms of topic coherence. When we use the learned topics for document classification, our model also achieves higher accuracy than other baselines including supervised LDA [Mcauliffe and Blei, 2008].

In summary, the main contributions of this paper are the following:

• We identify an unexplored type of metadata, which we call relative similarities, for topic modeling. We point out that relative similarities can also be derived from traditional categorical and numerical metadata.
• We propose a general model that combines LDA with relative similarity-based constraints (Section 3).
• We provide an efficient inference algorithm to fit the proposed model (Section 4).
• With two standard datasets, we show that our model is able to learn more meaningful topics than LDA (Section 5).

2 RelatedWork

Our work is mostly related to topic modeling with additional document metadata. We review two general approaches to such topic modeling.

2.1 Augmented Topic Models

The first approach to modeling document metadata is through modifying the structure of the graphical model. There are mainly two ways to incorporate metadata into the graphical model. One way is to generate the metadata from the topic distributions of each document. In such models, typically a topic is associated with not only a word distribution but also a distribution over different values of an attribute [Wang and McCallum, 2006; Mcauliffe and Blei, 2008; Qiu et al., 2013; Liao et al., 2014]. For example, in [Mcauliffe and Blei, 2008] the authors proposed a general supervised LDA model for scenarios where each document has a response variable. The response variable is assumed to be generated from a Gaussian distribution, the mean of which is determined by the topic assignment of the words in the document through a generalized linear model. This supervised LDA model can be used for predicting response variables such as star ratings of reviews and scores of student essays.

Another approach assumes that the topic distribution of each document is a mixture of metadata-specific topic distributions [Rosen-Zvi et al., 2004; McCallum et al., 2005; Eisenstein et al., 2010]. A typical example of this approach is the author-topic model [Rosen-Zvi et al., 2004]. Here to sample the topic of a word, first one of the authors of the document is chosen, and then a topic is sampled from that author's topic distribution. This approach generally only works for metadata with categorical values.

All the models above assume either categorical or numerical type of metadata. For our work, we focus on metadata in the form of relative similarities. It is not easy to modify standard graphical models to incorporate this kind of metadata.

2.2 Topic Modeling with Regularization

Another line of literature related to our work is topic modeling with regularization terms [Cai et al., 2008; Huh and Fienberg, 2010; Tang et al., 2013; McAuley and Leskovec, 2013; Andrzejewski et al., 2011; Mei et al., 2014]. Here the idea is to turn additional information about the documents into constraints or a loss function that do not necessarily follow a generative model. For example, in [Cai et al., 2008] and [Huh and Fienberg, 2010], regularization terms were used to capture the manifold structures of documents. In [Tang et al., 2013], the authors added a regularization term that pushes context-specific topic distributions close to the consensus topic distributions. In [McAuley and Leskovec, 2013], rating data were incorporated into the model and rating prediction errors became the additional loss function to regularize standard LDA. Recently, some researchers have also proposed to incorporate domain knowledge in the form of First-Order Logic (FOL) to standard LDA using a regularization framework [Andrzejewski et al., 2011; Mei et al., 2014]. While FOL rules are more expressive in representing knowledge, they require the analysts writing the rules to have background in FOL. In comparison, relative similarities as we use in this paper are generally easier to obtain.

In our work, we borrow the general idea of using a regularization term to incorporate additional knowledge. However, the type of metadata we model is very different from the work discussed above.

3 Model

We address the problem of topic modeling on documents where relative similarities are given. In this section, we first formulate the constraints derived from relative similarities. We then briefly review Latent Dirichlet Allocation (LDA) and propose our model, which combines LDA with relative similarities.

3.1 Constraints

We want to model documents where relative similarities are known for some documents if not all. Such relative similarities can come from human judges under a particular application setting or automatically derived from other data. First of all, we assume that we are given a set of documents denoted as D. We further assume that there is a distance function dist(di, dj) defined for any pair of di, dj ∈ D. To formally formulate the relative similarities, we assume that we are given a set of T triplets as follows:

where di, d+i , d-i ∈ D, and di is more similar to d+i than to d-i . In other words,

Borrowing the idea from max-margin methods, we further rewrite the constraints as follows:

where C, a positive constant, is a margin to ensure that dist(di, d-i ) is sufficiently larger than dist(di, d+i ).

Given the definitions above, our goal is to minimize a loss function defined below:

where

The next question is how to define the distance function dist. As we will see, the distance function will be based on the topic distributions learned by LDA.

3.2 Latent Dirichlet Allocation

Latent Dirichlet Allocation (LDA) [Blei et al., 2003] is a well-developed and widely used topic model. Evolved from Latent Semantic Analysis (PLSA) [Hofmann, 1999], LDA defines a proper Bayesian model which overcomes the overfitting problem in PLSA.

Given a document set D where each document d ∈ D contains Nd words {wd,1, wd,2, . . . , wd,Nd }, we assume that there exist K topics, each associated with a multinomial word distribution ϕk. Each document has a topic distribution θd in the K-dimensional topic space. Each word in a document has a hidden topic label drawn from the document's topic distribution. Formally, the generative process of LDA is described as follows:

• For each topic k = 1, . . . ,K, draw ϕk ∼ Dir(β)
• For each document d ∈ D
• Draw θd ∼ Dir(α)
• For each word wd,n, n = 1, . . . , Nd
• ⋄ Draw zd,n ∼ Multi(θd)
• ⋄ Drawwd,n ∼Multi(ϕzd,n )

Here α and β are parameters of the Dirichlet priors.

The parameters of LDA can be learned in several ways including variational methods and Gibbs sampling.

3.3 The RegularizedModel

In this subsection, we present our proposed model which combines LDA with the constraints defined in Section 3.1. Our motivation is to learn better topics by incorporating these constraints.

First of all, without considering the constraints and with only standard LDA, our objective is to find θ and ϕ that maximize the following objective function:

To link this objective function with the constraints presented in Section 3.1, we can simply add the two terms together:

where η is a constant to balance the two terms.

Now recall that we need to define the distance function dist, and this should be related to our model parameters, i.e. θ and

ϕ. Since ϕ is not document-specific, we use just θ to define dist. Intuitively, if two documents have similar θd, then their distance should be smaller. There are several choices we can consider. One is the Euclidean distance, where each θd is treated as a k-dimensional vector and the standard Euclidean distance can be computed between them. In this paper, we experiment with squared Euclidean distance. Another choice is KL-divergence, defined as follows:

However, because KL-divergence is not symmetric, i.e. generally DKL(θ||θ′ ) ̸= DKL(θ′ ||θ), here we consider the symmetric KL-divergence instead:

However, Eqn (6) is a constrained optimization problem because both θ and ϕ are probability distributions. To transform the objective function into an unconstrained optimization problem, we first define the following transformation function for θd,k:

We then change the Dirichlet prior on θd into a Gaussian prior on λd, that is, each λd,k follows a Gaussian distribution with a zero mean and a variance of σ2 . Next we leave out ϕ from our objective function and try to estimate it later based on the hidden variables z (explained in the next section). Our modified objective function becomes the following:

Note that the loss Li(di, d+i , d-i ) is also a function of λ.

4 Model Fitting with Gibbs-EM

To optimize the objective function given in Eqn (8), we adopt the Gibbs-EM algorithm [Wallach, 2006]. Recall that we have defined hidden variables z that represent topic assignment. With the hidden variables, the objective function can be optimized in the following way. During E-step, we fix the parameter λ(t) learned in the tth iteration and obtain the conditional distribution of the hidden variables p(z|w, λ(t) , β). During the M-step, we solve the following optimization problem:

where Eq[f] is the expected value of f with respect to the distribution q, and

With Gibbs-EM, instead of evaluating the exact conditional distribution p(z|w, λ(t) , β), we use Gibbs sampling to approximate it.

4.1 E-step

In the E-step, we use Gibbs sampling to sample the hidden topic variables z for all words w by fixing λ(t) . To simplify the discussion, we will use θ when referring to topic distributions and λ otherwise. The deterministic relation between them is given in Eqn (7). To perform Gibbs sampling, we need to compute the probability of assigning a topic zd,n to a specific word wd,n given all the other topic assignment to all the other words:

where -(d, n) indicates that zd,n or wd,n is excluded. By using the conjugacy property of Dirichlet and multinomial distributions, the Gibbs updating rule of our model can be represented as follows:

where nk,v denotes the number of times word v is assigned to topic k.

As we pointed out in the previous section, we do not directly estimate ϕ by optimizing the objective function. But with Gibbs sampling, ϕk,v can be estimated as follows:

Algorithm 1 Gibbs-EM for our model.

Input:

D documents, # topics K, size of the vocabulary V , regularization parameter η, margin C, max # EM iterations nEM, # Gibbs sampling iterations nGS, max # gradient descent in each M-step nGD.

Output:

λd,k and ϕk,v, d = 1, ..,D; k = 1, ..,K; v = 1, .., V 1: Randomly initialize z and λ 2: t ← 0 3: while (t < nEM) do 4: E-step: 5: Sample zd,n as in Eqn (10) with nGS iterations 6: M-step: 7: n← 0 8: while (n < nGD) do 9: Compute the objective function L′ (λ) as in Eqn (9) 10: Set the learning rate ξ 11: for (d = 1 to D) do 12: for (k = 1 to K) do 13: Compute the partial derivative ∂L′ (λ) ∂λd,k 14: λd,k (t) (n+1) ← λd,k (t) (n) + ξ ∂L′ (λ) ∂λd,k 15: end for 16: end for 17: n ← n + 1 18: end while 19: t ← t + 1 20: end while 21: Compute each ϕk,v as in Eqn (11)

4.2 M-step

In the M-step, we use the last sample of z(t) obtained from the previous E-step and use gradient descent to learn λ(t+1) :

By computing the first-order patrial derivatives of the objective function in Eqn (12) with respect to each λd,k, we can use gradient descent to optimize the objective function. The model fitting algorithm is summarized in Algorithm 1.

5 Experiments

In this section, we present the experiments to evaluate our model. We first describe our datasets. We then conduct experiments both quantitatively and qualitatively.

5.1 Datasets

We use two widely used text corpora, 20 newspapers 1 and TDT2 [Cai et al., 2008].

The 20 newsgroups text corpus is a collection of approximately 20,000 newsgroup documents, partitioned evenly across 20 different newsgroups. We used a preprocessed version of this dataset 2 , where the documents are divided into a training set and a test set. Among the documents in the training set, we randomly selected 100 documents from each category and removed stop words and very short documents (documents with fewer than 3 words), thus leaving us with 1,997 documents with 14,538 distinct words.

The TDT2 corpus consists of 11,201 documents which are classified into 96 categories. Only the largest 20 categories were kept, and those documents appearing in more than one category were removed. We also randomly sampled 100 documents from each category as the strategy for the 20 newsgroup dataset. Finally, there are 1,998 documents with 12,166 distinct words left.

5.2 Experimental Setup

In our experiments, we performed 200 runs of Gibbs-EM. In each run, we ran 100 iterations of Gibbs sampling and another 10 iterations of gradient descent. We set the Dirichlet prior β = 0.1, the variance of Gaussian prior σ = 1. We also fixed the number of topics to be 20 (same as the number of categories in each dataset). Note that we do not tune this parameter since our goal is not to find the optimal number of topics.

To automatically obtain the triplet constraints for our model, we sampled a set of triplets from the documents in the training set according to their ground truth category labels. Specifically, we generated a triplet instance by randomly sampling two documents in the same category and one document from another different category. In our experiments, we generated 100K, 50K and 10K triplet instancnes (about 1%, 0.5%

1 http://qwone.com/∼jason/20Newsgroups/

2 http://www.cad.zju.edu.cn/home/dengcai/Data/TextData.html

and 0.1% of all the triplet instances, respectively) from the training set of each dataset. Experiments were run on a machine with 4 cores and 4GB of memory.

5.3 Quantitative Evaluation

In this subsection, we give quantitative evaluation of our model on topic coherence and document classification. We evaluate our model with different number of sampled triplets (i.e. 100K, 50K and 10K) against other baselines. Specifically, the methods used in our experiments are:

• DRS-KL. Our model with the symmetric KL-divergence distance metric.
• DRS-SE. Our model with squared Euclidean distance as the distance function.
• LDA. The standard LDA model.
• sLDA. The supervised LDA model [Mcauliffe and Blei, 2008]. This is a strong baseline where metadata is also used. Here we treat the category labels of all the training documents as the response values. This baseline is used for comparison for the classification task as well as computational costs presented later.

Note that for DRS-KL and DRS-SE, we tune the regularization parameter η and margin C, and report the results with the best performance. To test the robustness of our model, we used 5-fold cross validation for all methods. We should emphasize that we sampled triplet instances only from the training documents, i.e. no metadata from the test documents is used. This ensures the fairness of the comparison of our model and the baselines.

Topic Coherence

In this experiment, we want to compare the performance of different topic models. Previous studies usually utilized perplexity (likelihood on held-out data) as the metric. However, such metric cannot measure the coherence of learned topics. Chang et al. [Chang et al., 2009] found that perplexity is not always a good indicator of topic coherence [Mimno et al., 2011]. To tackle this problem, we explore another metric to measure the quality of learned topics. Specifically, to measure the semantic coherence of topics, we use the point-wise mutual information (PMI) [Newman et al., 2010]. PMI measures the co-occurrence of a number of words, which is defined as:

where w are the top-N words of a topic, p(wi,wj) is the probability that words wi and wj co-occur in the same document, while p(wi) is the probability that word wi appears in a document. In order to compute PMI, we need a larger dataset. In our setting, we used 9,394 documents of TDT2 and 19,997 documents of 20 newsgroups to compute the PMI scores. N is set to 10 in our analysis.

The PMI scores of all candidate methods are presented in Table 1. From the results we can see that our model achieves higher PMI scores compared with the LDA model in all settings. So we can conclude that our model is more successful in learning coherence topics in both corpora. In comparison, LDA does not show such capabilities because it does not capture the constraints of relative similarities among documents.

Document Classification

With topic modeling, each document can be represented by its topic distribution. In this subsection, we investigate the use of hidden topics learned by different topic models for document classification.

We use the topic distributions of documents as features and train a RBF kernel Support Vector Machine (SVM) [Chang and Lin, 2011]. Table 2 shows the classification accuracy with 5-fold cross validation on both datasets.

The results reveal a number of points:

1. Compared with LDA, sLDA performs better. This is because sLDA makes use of the categorical information of the training documents, and thus learns topics that are more discriminative for the categories. Our method also consistently outperforms LDA in all settings. This shows that our way of using the metadata in the training documents is also effective.
2. The comparison between our method and sLDA is mixed, but generally when we use more triplets (100K) and when we use the symmetric KL-divergence distance, our method is more likely to outperform sLDA. Note that our method relies on relative document similarities and sLDA needs document labels. Moreover, in sLDA, the labels of all training documents are used, while in our model, only a small set of sampled labels are used. Hypothetically, in scenarios where only relative document similarities are available, we would not be able to apply sLDA but our method can still be used.

Computational Costs

In this subsection, we empirically compare the computational costs of our method and sLDA. The version of sLDA we used was implemented in C++ 3 and our method was implemented in Java. Table 3 shows the results. We can see that when the number of triplets used is relatively small, our method takes similar amount of time as sLDA, and when the number of triplets increases to 100K, our method may take up to 4 times the computational cost of sLDA. Note that our method is not meant to outperform sLDA in terms of computational efficiency. The advantage of our method is its special way of dealing with relative similarities, which sLDA cannot handle. Therefore, the computational costs in Table 3 show that our method can handle special kinds of metadata, i.e. relative similarities, and achieve good accuracy, all with reasonable computational costs compared with sLDA.

3 http://www.cs.cmu.edu/∼chongw/slda/

5.4 Qualitative Evaluation

In this subsection, we show the hidden topics learned by our model. For each dataset, we randomly choose four topics and show the top 10 words of each topic. Tables 4 and 5 show the top words generated by our model with 100K triplets on 20 newsgroups dataset and TDT2 dataset, respectively.

We can see from both tables that the discovered topics are generally meaningful. For example, from the top words like "gun," "control" and "crime," it is easy to justify that Topic 1 in Table 4 is about "gun control"; Top topic words like "tobacco," "smoking" and "tax" demonstrate that Topic 4 in Table 5 is about "tobacco control".

6 Conclusions

In this paper, we perform topic modeling where relative similarities among documents are given. We formulate the constraints as a loss function and propose a general probabilistic model that combines LDA with such constraints. Our model treats the constraints as a regularizer of the log likelihood of text. Extensive experiments are conducted on two real world datasets, in which the empirical results show that our model not only learns meaningful topics, but also outperforms the baselines in terms of topic coherence and a document classification task.

The constraints we captured in this work are commonly used in the field of Distance Metric Learning (DML) [Gao et al., 2014]. An interesting direction of future work is to combine the theory of DML with our model to better model documents with such constraints.

Acknowledgments

This work was done during Jianguang Du's visit to Singapore Management University. Dandan Song is the corresponding author. This work was partially supported by the National Program on Key Basic Research Project (973 Program, Grant No. 2013CB329600), National Natural Science Foundation of China (NSFC, Grant Nos. 61472040 and 60873237), and Beijing Higher Education Young Elite Teacher Project (Grant No. YETP1198).