Regularizing Flat Latent Variables with Hierarchical Structures

1 Introduction

Probabilistic topic models, such as PLSA [Hofmann, 1999] and LDA [Blei et al., 2003b], have been widely used to automatically uncover the latent topics in unlabeled data sets, especially in text corpora. In general, a topic model is to describe documents as mixtures over a small number of "flat" hidden topics, each of which is independent and represented as a distribution over words. But the "flat" topics tend to be fused or junky, especially when the topic number becomes large [Chuang et al., 2013]. To address the relationships among topics, in the literature of topic modeling, a lot of attempts have been made to incorporate the relationship information into topic modeling process [Andrzejewski et al., 2009; Blei and Lafferty, 2006; Li and McCallum, 2006; Blei et al., 2003a].

One way is to model and infer the pairwise relationships among topics [Blei and Lafferty, 2006; He et al., 2012]. For instance, CTM [Blei and Lafferty, 2006] uses logistic normal distribution with a covariance matrix to model the pairwise relationships between topics. Similarly SLFA [He et al., 2012] tries to discover the pairwise relationships between latent topics through Sparse Gaussian Graphical Model's precision matrix. Another way is to directly model and infer the optimal hierarchically structured topics, such as hierarchical LDA (hLDA) [Blei et al., 2003a] and pachinko allocation model (PAM) [Li and McCallum, 2006]. In hLDA, topics are organized over a tree. Each document is assigned a path through the tree, and each word of the document is sampled from a mixture over topics in the path. PAM uses directed acyclic graph (DAG) to represent topic hierarchies. Each node in the inner layer is a distribution over all nodes on the next level and each of nodes in the leaf layer is a distribution over words.

In this paper, instead of directly modeling the pairwise relationships or hierarchical structures among topics, we use the stratified relationships in topics to regularize the flat topics after capturing the topic structures with a hierarchical clustering method. The hierarchical structure of topics does represent more natural relationships among topics than the pairwise one. By incorporating the stratified relationships that exist among topics into the modeling process, we would be able to uncover more cohesive and meaningful topics. To this end, we develop a stratified topic model (STM), where the hierarchical structure of topics is captured by a tree. Each layer of the tree forms a mixture over different numbers of topics to generate all tokens in a corpus and hierarchical relationships play as constraints during the overall learning process. Along this line, two theoretically sound and practical inference methods are proposed to solve the conceptually nonconjugate model and a heuristic algorithm is developed to construct the tree structure of topics. Finally, we conduct extensive experiments with two real-world data sets. Results based on different evaluation metrics demonstrate that our model could outperform classical topic model methods.

2 RelatedWork

Traditional probabilistic topic models such as PLSA [Hofmann, 1999] and LDA [Blei et al., 2003b] aim to automatically reduce unlabeled data sets into linear combinations of "flat" latent topics, which are essentially independent from each other. These models have been widely used in many research and applied domains such as natural language processing, information retrieval and computer vision [Foulds and Smyth, 2013; Tang et al., 2013; Gao et al., 2011; Berg et al., 2004]. Moreover, many more extensions and adjustments have been proposed to take into account external information or aspects for better modeling different data sets, such as author-topic model [Rosen-Zvi et al., 2004], DiscLDA [Lacoste-Julien et al., 2008], MG-LDA [Titov and McDonald, 2008], et al. For instance, in addition to the relationships among documents, topics and words, author-topic model [Rosen-Zvi et al., 2004] explores the relationship between authors and them as well.

Many works have attempted to directly model the pairwise relationships among topics, such as CTM[Blei and Lafferty, 2006], SLFA[He et al., 2012]. By capturing the correlation between two topics, this type of models usually lead to better fitting on many data sets. Meanwhile, hierarchical topic modeling techniques aim to directly uncover hierarchical structures that exist in topics. These techniques such as hLDA[Blei et al., 2003a], PAM [Li and McCallum, 2006], HDP [Teh et al., 2006], and hPAM [Mimno et al., 2007] focus on inferring the optimal hierarchical topic structures. Different from all the above approaches, our new model STM uses a hierarchical clustering method to capture hierarchial structures of topics and leverage the stratified relationships among original "flat" topics to regularize flat variables during the learning process.

3 Stratified Topic Model

Our stratified topic model (STM) essentially consists of threestep modeling. First, we train the initial model by assuming no hierarchical structure exists and learn a group of topics. Then a heuristic hierarchical clustering method is applied to construct a stratified topic tree based on topic-word samples. Finally, we refit data by regularizing the initial topics with the built topic tree and learn more cohesive and meaningful topics.

3.1 Notations and Definitions

Given a corpus with M documents and V unique words, probabilistic topic modeling techniques aim to uncover the K latent topics, each of which is represented as a distribution φk over all words. Each document di with Ni words is associated with a latent topic distribution θi, which often has a prior distribution with parameters α in Bayesian models. And each word wij is considered to be drawn from a mixture over all latent topics.

In STM, the flat topics are organized into a LT -level stratified topic tree (STT) T , which can be defined as a rose (nonbinary) tree associated with a set of tree-consistent partitions over the observed words [Blundell et al., 2010]. Different from the tree structures in hLDA and PAM, each layer l of T forms a mixture over the Kl latent topics to generate all the words in the document di. And this stratified topic tree defines the hierarchical relationships among topic distributions at different layers. The topic proportion of topic k at layer l, θl [k] equals to the sum over the topic proportions of all its leaves. Figure 1 shows an example of the hierarchical relationships of topic distributions defined by a three-level STT.

To describe the hierarchical structure, we use Par(l, k) to denote the parent topic at layer l for leaf topic k and Leaf(l, k) to denote the leaf topic set for topic k at layer l. For example, in the three-level STT shown at Figure 1, P ar(1, 5) = 2 and Leaf (2, 2) = {7, 8, 9, 10}.

3.2 Graphical Model and Generative Process

With the fixed hidden Stratified Topic Tree T and the initial model hyper-parameters, α and β, as shown in Figure 2, the Stratified Topic Model try to maximize the joint generating likelihood of all the words in document di in different tree layers. In other words, each word is sampled LT times.

The dependency and model assumptions are illustrated in following generative process:

1. For each tree layer l ∈ {0, ...,LT -1} a. For each topic k ∈ {1, ...,Kl }
2. For each document i ∈ {1, ...,M} draw the topic distribution: θi ∼ Dir(.|α)
3. draw the topic-word distribution:φlk ∼ Dir(.|βl )
4. For each tree layer l ∈ {0, ...,LT -1}
5. For each position j ∈ {1, ...,Ni} draw a topic assignment: zl ij ∼Mult(θli ) draw a word: wij ∼ Mult(φlzl ij )

In the above process, θli [k] = ∑t∈Leaf(l,k) θi[t].

We would like to emphasize that the φhigh at high layer is similar but still different than the combination of the φlow at low level due to the constraints of Stratified Topic Tree. Each layer of the model forms a separate "perspective" of the observed words. By integrating the information from different perspectives, words can be better explained and predicted.

3.3 Inference Methods

The stratified topic model is not a conventional conjugate probabilistic model. The posterior distribution of θi conditional on the stratified samples is not tractable due to the noclose-form integration over sum of multi variables. In the following paragraphs, we will introduce two methods to infer the parameters of our model: EM for MAP and Relaxed Variational Inference Approximation.

EM for MAP

In the standard EM framework, the object function is maximized iteratively with respect to hidden variables and model parameters. As for STM, in E step, the posterior probability of hidden variable zij for each term wij in layer l can be calculated as:

In M step, the parameters (φ, θ) are updated using the MAP estimation ( ˆ φmap, ˆ θmap). Specifically, We define

where I(.) is the indicator function. Also, for simplicity, we use the dot to denote sum over an index, e.g. nl..v = ∑Mi ∑Kl k nlikv . Then the MAP estimation of φlk is:

To formulize the MAP estimation of θi, we define a statistic:

where k ∈ {1, ..., K0 }. And τ l ik is defined as:

which is the coefficient of allocating the statistic nli{Par(l,k)}. at layer l to the kth leaf layer node.

We show in Appendix A that the MAP estimation of θi is:

As a classic probabilistic topic model, PLSA is considered to be the MAP-estimated LDA model under a uniform dirichlet prior [Girolami and Kab´an, 2003]. Similarly, it is easy to find that our STM with MAP estimation is exactly the stratified extension of PLSA.

Relaxed Variational Inference Approximation

The key idea underlying variational inference is to approximate the posterior distributions of hidden variables using a family of distributions with free parameters via minimizing the Kullback-Leibler divergence[Jordan et al., 1999]. In this paper, as shown in Figure 3, we introduce the factorized variational distribution for hidden variables (θi, zli ) in each document di as

where θi subjects to K0 -dimensional Dirichlet distribution Dir(.|γi) and zl ij subjects to Kl -dimensional multinomial distribution Mult(ηl ij ).

In variational inference, minizing the KL divergence between the variational posterior distribution and the true posterior distribution is equivalent to maxmizing the lower bound with respect to free parameters. By applying the Jensen's inequality, the log-likelihood is bounded as

In variational EM approach, The lower bound is maximized iteratively with respect to variational parameters {γ, η} (E step) and model parameters {α, β} (M step). In E step, similar to derivation in [Blei et al., 2003b], we obtain the updating equation for ηl ij :

By approximating the trigamma function by Ψ′ (x) ≈ cx , the updating rule for γik is:γik = N (LT-1) ik (9)

where N (LT-1) ik is the statistic defined at Equation (4). In other words, the posterior distribution is approximated by the Dirichlet distribution whose expectation equals to the MAP estimation. In M step, the model parameters {α, β} have exactly the same updating rules as those of LDA.

3.4 Stratified Topic Tree

Instead of inferring the tree structure, parameters and hidden variables simultaneously, in STM, the hierarchical topic structure is obtained separately after the initial model is learned. Then the problem to construct a proper topic tree can be regarded as a hierarchical clustering problem over a group of topic-word samples. Although many existing hierarchical clustering techniques can be applied, in this paper, we propose to construct the stratified topic tree using Common Alpha Similarity.

Considering a set of samples of word v over K topics {n.1v, n.2v, ..., n.Kv}, we can define the generative process for these samples. Samples come from a K-dimensional multinomial distribution parameterized on θ and θ comes from Dirichlet prior with parameter common α. Then the joint probability of these samples is:

where Nv = ∑k n.kv.

By assuming the samples of the words are independent, the joint probability of all the samples is the product of probability of per-word samples. Then to measure the similarity between topics, we use the Common Alpha Similarity defined as:

It is not hard to find that topics with more similar samples would result in a larger common alpha (as shown in Figure 4). To figure the maximum-likelihood estimation of parameters in Dirichlet-multinomial (Polya) distribution, [Minka, 2000] came up with a fix point iteration for the K-dimensional parameter. As for the common alpha, by using the same bounds, we can derive the similar fix point iteration:

where Ψ(.) is the digamma function. We use Alpha({k1, ..., kn}) to denote the Common Alpha Similarity of topic set {k1, ..., kn}.

We define a ratio and use it as a criterion for our hierarchical clustering as:

To construct a stratified topic tree, we set a series of ratio λ expectations, one for each layer of the tree. Then following the typical hierarchical clustering scheme, we merge two clusters with the largest Common Alpha Similarity score Alpha({Leaves(Ti)∪Leaves(Tj)}) into a new cluster until the ratio λ is smaller than the expected value for each layer.

3.5 Algorithm

As discussed before, the algorithm consists of 3 steps of modeling:

1. Training the initial STM by assuming that no hierarchical structure exists. Evidently, STM actually degrades into LDA based on this assumption.
2. Building the Stratified Topic Tree using the topic-word samples obtained in the first step. Although we use the Common Alpha Similarity in this paper, a variety of similarity metrics can be utilized to explore the hierarchical structure, which make our STM extensible and flexible in different scenarios.
3. Retraining STMwith the constructed stratified topic tree in the second step. Since we build the STT based on topic-word samples, to make sure the consistent model is built, we use the topic-word samples to estimate the initial model parameters {φl } (Equation 14) before the EM optimization iterations as:

4 Experimental Results

4.1 Experimental Setup

Two real-world data sets are used to evaluate the performance of different algorithms: 20 Newsgroups 1 and Encyclopedia Articles 2 . The 20 Newsgroups data set has be manually labelled in a hierarchical way. All documents are almost evenly partitioned into 20 different groups, each corresponding to a different topic. These 20 different groups have been further organized into 6 different larger clusters. Thus there is a twolayer hierarchy among all documents. The Encyclopedia Articles include a small subset of Grolier encyclopedia articles. There are approximately 3, 1000 articles. But there is no labelling information available for this data set.

Typical preprocessing steps are taken for both data sets: 1) remove punctuations, stopwords and words that have occurred less than 10 times in the whole corpus; 2) stem the words; 3) remove those documents containing less than 10 terms; 4) 40% of documents are selected and used as the testing set. As for 20 Newsgroups data set, it has been already partitioned into training set (60% of documents) and testing set (40% of documents) based on the time. For Encyclopedia Articles data set, we randomly select 40% of documents for testing and use the rest for training. Some statistical characteristics of these data sets are summarized in Table 1.

While STM explores and leverages hierarchical structures, the outputs of STM are still "flat" yet regularized topics. Thus, in our experiments, we compare STM model with LDA via MAP estimation (PLSA), and LDA via VB estimation. We also compare STM with CTM and HDP 3 , which have the same output as STM. As for MAP algorithms, including LDAMAP and STMMAP , the hyper parameters are fixed as α = 1.1 and β = 1.01 as many previous works did. And we set 200 EM iterations with random initialization for each model. As for HDP, we set up 10000 iterations to train the model and extra 1000 iterations to estimate the topic distribution. As for Variational algorithms, including LDAVB, STMVB and CTM, all models are fitted using initial hyper parameters α = 0.1 and β = 0.01 with random initialization. And we exhaustively run 100 variational EM iterations or until the relative change of lower bound being less than 10-5 to ensure the convergence. We find that 2-level STM is sufficient enough to model both data sets, thus in the following experiments the number of layers of stratified topic tree is fixed as LT = 2. Finally, the stratified topic tree is built by empirically setting the parameter λ as λ = 1.3.

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

3 We use the available implementation at http://www.cs.columbia.edu/∼blei/topicmodeling.html

2 http://www.cs.nyu.edu/∼roweis/data.html

4.2 Predictive Perplexity

Perplexity, which is equivalent to the inverse of the geometric mean per-word likelihood in algebra, is a conventional metric for evaluating the performance of topic models. Different calculation strategies have been proposed [Wallach et al., 2009]. In this paper, we follow the testing framework of [Wang and Blei, 2013], [Asuncion et al., 2009] and [Blei and Lafferty, 2007], which splits each held-out document into two halves (w1,w2), estimates the document topic distribution with the first half and measures the predictive perplexity using the second half. Also words in each document are randomly shuffled before splitting to get rid of the sequential dependence among tokens. The predictive perplexity is measured using the second half of words as

where Ni2 is the word count of the second half of document.

In Figure 5 and Figure 6, we show the comparisons of predictive perplexity among four algorithms with 20 Newsgroups data set and Encyclopedia data set. As can be seen, STM via MAP or Variational Inference could outperform LDA via MAP or variational inference over different numbers of topics. In other words, STM could better predict the remaining words in documents than LDA, which empirically testifies that using stratified relationships to regularize flat topics is effective for modeling a corpus. In fact, we also got the results of CTM on both data sets. It turns out that CTM consistently underperforms LDA with respect to the predictive perplexity. For instance, the predictive perplexity of CTM is 2274.03 when the topic number is 100 on 20 Newsgroups data set. In addition, as shown in Figure 6 and Figure 6, STMwith variational inference leads to better performance than STM with MAP because MAP estimation may lead to the typical overfitting. And we can observe the similar comparison trend between two inference methods of LDA from Figures 5 and 6.

4.3 Classification

As a way of dimension reduction, each document could be represented by a lower-dimensional feature vector p(θi|wi) after topic modelling. An interesting and practical task is to conduct classification based on the learned topics. Specifically, after we train all topic models with the training set of 20 Newsgroups data, the trained models are used to infer the topic distribution of documents in both training and testing set. To make the comparison fair, in STM, we only use the inferred topic distributions at the leaf layer to train a classifier. Thus all topic models transfer each document to a feature vector (i.e., a distribution over topics) with the same dimension. We train two widely used classifier, i.e., logistic regression and SVM in the software LIBLINEAR 4 , with the lower-dimensional feature vectors of training set and evaluate the classification accuracy with the lower-dimensional feature vectors of testing set.

As shown in Figure 7, we can see that STM could outperform LDA for classification, especially when the topic number becomes larger. The results suggest that STM can better preserve the latent feature information for classification than LDA. We also conduct the classification task with CTM and HDP in a similar way. But the classification performance via CTM and HDP is worse than that of LDA on 20 Newsgroups data. For instance, CTM leads to 69.40% accuracy on the testing set when the topic number is 100 and HDP leads to only 67.59% with 174 topics. In addition, we observe similar comparison trends among these algorithms with SVM classifier, but we omit the results due to the limit of space.

4 http://www.csie.ntu.edu.tw/∼cjlin/liblinear/

4.4 Clustering

As we described in the classification task, each document in the training and testing sets is represented by a lowerdimensional feature vector with the same dimension via individual topic model. Since we do not really need a testing set for clustering task, we merge the training and testing sets together and then conduct clustering over the whole data set. Particularly we use the CLUTO 5 to cluster the merged set into 20 clusters. Figure 8 shows the clustering performance using vcluster in CLUTO with cosine similarity and partitional clustering algorithm. From the results we can find that compared to other models, STM leads to better purity score, which means STM can effectively preserve the feature information that is useful for clustering task.

4.5 Additional Experiments

One interesting question about STM is how to set the number of middle-layer topics. In this experiment, we fix the leaf topic number as 100, retrain the 2-level STM with a series of middle topic numbers, and measure the perplexity of each learned model on the 20 Newsgroups data set. From the results shown in Figure 9 we can find that there are generally two local minimums: one locating around 8 and the other one locating around 23. The result is very consistent with the known two-level hierarchical labeling (i.e., 20 small groups and 6 big clusters) of 20 Newsgroups data. The results indicates that our model can effectively capture the useful hierarchical structure information.

5 Conclusions

In this paper, we investigated the problem of leveraging hierarchical structures for better topic modeling. Instead of directly modeling and inferring hierarchical structured topics, we applied a hierarchical clustering method to capture the stratified relationships among flat topics. These relationships were incorporated into the learning process, which is essentially to regularize flat latent variables. We developed two inference methods, i.e., EM for MAP and relaxed variational inference approximation, to solve our model. As shown in our experiments, in addition to better model fitting, STM could also uncover more cohesive and meaningful topics that can help us better explore the semantics of a large corpus and get more robust clustering and classification results.

5 http://glaros.dtc.umn.edu/gkhome/cluto/cluto/overview

Acknowledgements

This research was supported in part by National Institutes of Health under Grant 1R21AA023975-01 and National Center for International Joint Research on E-Business Information Processing under Grant 2013B01035.

A MAP Estimation of θi

with the constraint ∑K0 k=1 θik = 1. To solve the problem, we add the Lagrange multipliers. Then the gradient with respect to θik is:

Set the derivatives to zero and we get a group of equations. Considering that {k1, ..., kn} share the same parent node at layer 1, we can derive proportion equation:

where N l ik is defined at Equation 4. Then the equations can be simplified as:

By recursively applying this process, we finally get the MAP estimation for θi: ˆ θik ∝ N LT-1 ik