Tag-Weighted Topic Model for Mining Semi-Structured Documents

1 Introduction

Large collections of text with kinds of metadata appears in many Web applications. The documents with both text data and document metadata (tags, which can be viewed as features of the corresponding document) are called the SemiStructured Data. How to characterize the semi-structured document data becomes an important issue addressed in many area, such as information retrieval, artificial intelligence and machine learning. The tags can be more important than the text data in document mining. For example, IMDB, the world's most popular and authoritative source for movie, TV

∗ Corresponding author

and celebrity content. Each movie has lots of tags, e.g., director, writers, stars, country, language and so on, and a storyline as text data. Given a movie with a tag "Dick Martin", we may have an opinion that it has a higher probability to be a comedy, without read all its storyline or watch it.

In past decade, topic models have been used to be a powerful method of management of document corpus, such as latent Dirichlet allocation (LDA) [Blei et al., 2003], which assigns topics to corpora and generates topic distributions over words given corpus. However, as an unsupervised method, only the words in the documents are modeled in LDA. Thus, LDA could only treat the tags as word features rather than a new kind of information for document modeling. Researchers have proposed approaches to deal with tags or labels [Mimno and McCallum, 2008; Ramage et al., 2009; 2011]. However, there are still two main problems. Firstly, in a document, the importance of the tags can be different in terms of document modeling. For instance, in the domain of scientific paper modeling, there are three authors in a specific paper, which can be three tags of the paper. In most cases, the first author would make more contribution than the third author. In fact, different authors have different background. Therefore the weights of the authors can affect the formation of the topic distribution of the document. Secondly, tags in a corpus are diverse and evolving. For a news story in NYTimes, the tags set contains various types, such as reporters and category, and both have an impact on topics assignment with different weights. It is clear that how to take advantage of all the available tags is a challenge when sundry tags are involved.

In this work, we focus on document collections where documents are tagged. We propose a tag-weighted topic model (TWTM) to represent the text data and the various tags with weights to evaluate the importance of the tags. Besides, TWTM also infers the topic distributions of tags. The weights of observed tags in document, which we infer from data set, give us an opportunity to provide a method to rank the tags. Compared to LDA, TWTM can conduct document modeling with lower perplexity, and construct more discriminant features for classification.

The proposed TWTM has three principal contributions.

1. It is a novel topic modeling method to model the semistructured data, not only generating the topic distributions over words, but also infering topic distributions of

tags.

1. TWTM automatically infers a topic distribution for each individual document directly, with a function of tagweighted topic assignment.
2. Instead of constructing a new model for new tags in the corpus, TWTM provides a framework to model a variety of tags, which shows the extensibility of the model.

The rest of the paper is organized as follows. In Section 2, we first analyze and discuss related works. In Section 3, we first introduce basic notation and terminology, present a novel topic model, and give the method of learning and inference. In Section 4, we present the experimental results on three domains to show the performance of the proposed method in document modeling and text classification. We conclude and discuss further research directions in Section 5.

2 RelatedWorks

There are many topic models proposed and shown to be useful on document analyzing, such as in [Petterson et al., 2010; Hofmann, 1999; Blei et al., 2003; Blei and McAuliffe, 2007; Boyd-Graber and Blei, 2010; Chang and Blei, 2009], which have been applied to many areas, including document clustering and classification [Cai et al., 2008], and information retrieval [Wei and Croft, 2006]. They are extended to many other topic models for different situation of applications in analyzing text data [Iwata et al., 2009; Lacoste-Julien et al., 2008; Zhu et al., 2009]. However, most of these models only consider the textual information while ignore humanprovided tag information.

Several models have been proposed to take advantage of tags or labels, such as Labeled LDA [Ramage et al., 2009], DMR [Mimno and McCallum, 2008] and PLDA [Ramage et al., 2011], or modeling relationships among several variables, such as Author-Topic Model [Rosen-Zvi et al., 2004]. Labeled LDA [Ramage et al., 2009] get the topic distribution for a document through picking out the several hyperparameter components that correspond to its labels, and draw the topic components by the new hyperparameter. Thus, it is hard to infer the topic distribution of labels, that is very useful for text classification in some web applications. And in Author Topic Model, it obtains the topic distributions of authors, without gives the importance between the given authors in a document. DMR [Mimno and McCallum, 2008] is a Dirichlet-multinomial regression topic model that includes a log-linear prior on document-topic distributions that is a function of given features of the document. However, there is a lack of the information of the tag weights in DMR as well as Author-Topic Model [Rosen-Zvi et al., 2004]. PLDA [Ramage et al., 2011] provides another way of modeling the labels' text data, that assumes the generation of words of topics assignment is limited by only one of the given labels, and estimates an appropriate size for each per-label topic set automatically using Dirichlet process.TMBP [Deng et al., 2011] and cFTM [Chen et al., 2012] give methods to make use of the contextual information of documents to model the topic assignment. TMBP is a topic model with biased propagation to leveraging contextual information, the authors and venue.

However, predefining the weights of the author and venue information on word assignment limits the usefulness in many real applications, and cFTMwith the strict assumption of either author or venue be chosen for one word topic assignment lack of scalability when there are various types of contextual information.

3 TWTMModel and Algorithms

In this section, we will mathematically define the tagweighted topic model (TWTM), and discuss the learning and inference methods. In this model, just like the latent Dirichlet allocation (LDA) [Blei et al., 2003], we treat the words of document as arising form a set of latent topics.

3.1 TWTM

We formally define the following terms. Consider a semistructured corpus, a collection of M documents. We define the corpus D = {(w 1 , t 1 ), . . . , (w M , t M )}, where each 2-tuple (w d , t d ) denotes a document, the bag-of-word representation w d = (w d 1 , . . . , w d N ), t d = (t d 1 , . . . , t d L ) is the document tag vector, each element of which being a binary tag indicator, and L is the size of the tag set in the corpus D. For the convenience of the inference in this paper, t d is expanded to a l d × L matrix T d , where l d is the number of tags in document d. For each row number i ∈ {1, . . . , l d } in T d , T d i· is a binary vector, where T d i j = 1 if and only if the i-th tag of the document d 1 is the j-th tag of the tag set in the corpus D. In this paper, we wish to find a probabilistic model for the corpus D that assigns high likelihood to the documents in the corpus and other documents alike utilizing the given tag information.

In the past topic models, each document d is typically characterized by a distribution over topics, θ d , and each topic k is represented by ψk, over words in a vocabulary. Take LDA [Blei et al., 2003] for an example, the generative process of topic distribution of document d is assumed as follows.

where α is the hyperparameter. In LDA, the topic distribution θ d is drawn from a hyperparameter, α without considering the tags' information. However, the human-provided tag information is useful to impact on the formation of θ d .

In this paper, we use ϑ d to denote the topic distribution of document d, controlled by observed tags, as shown in Figure 1. And, let θ represent a L × K topic distribution matrix over the tag set, where L is the size of the tag set in corpus D, and K is the number of topics. Let ψ represent a K × V distribution matrix over words in the dictionary, where V is the number of words in the dictionary of D.

Similar to LDA, TWTMmodels the document d as a mixture of underlying topics and generates each word from one topic. While the topic proportions ϑ d of document d in TWTM is a mixture of tags' (given/specified) topic distributions, not restrict to be defined only over a hyperparameter in LDA. Meanwhile, the novel method we propose to model the topic proportions ϑ d is different from neither cFTM nor Labeled LDA, or other topic models, such as PLDA and DMR.

1 Note that we can sort the tags of the document d by the index of the tag set of the corpus D.

The generative process for TWTM is given in the following procedure:

1. For each topic k ∈ {1, . . . , K}, draw ψk ∼ Dir(β) , where β is a V dimensional prior vector of ψ.
2. For each tag t ∈ {1, . . . , L}, draw θt ∼ Dir(α), where α is a K dimensional prior vector of θ.
3. For each document d:
4. (a) For each l ∈ {1, . . . , L}, draw t d l ∼ Bernoulli(ηl ).
5. (b) Generate T d by t d .
6. (c) Draw ε d ∼ Dir(T d × π).
7. (d) Generate ϑ d = (ε d ) T × (T d × θ) .
8. (e) For each word wdi:
9. Draw zdi ∼Mult(ϑ d ) .
10. Draw wdi ∼Mult(ψzdi ) .

In this process, Dir(·) designates a Dirichlet distribution, Mult(·) is a multinomial distribution, and π is a L × 1 column vector, a Dirichlet prior.

Note that ε d indicates the weight vector of the observed tags in constituting the topic proportions of document d. Furthermore, ε d is drawn from a Dirichlet prior that is result of the matrix multiplication of T d ×π. Clearly, the result of T d ×π will be a (l d × 1) vector of which the dimension is depended on the number of observed tags in document d.

In Step 3, for one document d, we first generate the document's tags t d l using a Bernoulli coin toss with a prior probability ηl, as shown in (a). Then, after draw out the ε d , we generate the ϑ d through ε d , T d and θ, that will be discussed in section 2.3. The remaining part of the generative process is just familiar with the traditional LDA model [Blei et al., 2003].

As shown above, TWTM assumes a novel way to model the topic proportions of semi-structured document by document-special tags and text data. The main key which discussed in this paper is the tag's weight topic assignment, which provides an effective and directly method to infer the weight of tags.

3.2 Tag-Weighted Topic Assignment

As we expect that all the observed tags in document d make contributions to infer the topic distribution ϑ d of the document, and meanwhile, it is expected that different tags works corresponding to their weights. For example, a blog with tags of an author, blog's date, blog category and blog's url. Clearly, compared to other tags, the author plays the most important role in constituting the topic components of this blog.

The function of how to leverage the tag information or contextual for modeling topic distribution of document is defined as follows:

where f (·) is the way of making use of the tag information. Topic models with tag information or contextual in the past are take advantage of different f (·). In TWTM, we assume that ϑ d is made up by all the observed tags with their own weight. Figure 1 shows that how TWTM works in probabilistic graphical model. As is shown in Figure 1, ϑ d is controlled by two sides, the topic distributions over tags θ, and the weights of the given tags of document d.

It is important to distinguish TWTM from the AuthorTopic Model [Rosen-Zvi et al., 2004]. In the author-topic model, words w is chose by the distribution only from one of the given tags, while in TWTM, for word w, all the observed tags in the document would make the contributions.

The f (·) in the proposed model is assumed as this, for document d,

where the linear multiplication of (ε d ) T , T d and θ maintains the condition of ∑K k ϑ d k = 1 without normalization of ϑ d , since that ε d and θ satisfies∑l d

Firstly, we pick out the topic distributions of the given tags in document d by T d × θ, for T d is a l d × L matrix and θ is a L × K matrix. Here we define

where the Θ d is a l d ×K topic distribution matrix of given tags in d as sub-components of θ.

Secondly, ε d is the weight vector of observed tags in d, and each dimension of ε d represents the weight or importance associated to the corresponding tag. So, ϑ d is mixed by Θ d with corresponding weight values.

With ϑ d , TWTM generates all the words of document d with the assumption of bag-of-words, which is familiar with the LDA. It is worth to note that the generative process in PLDA [Ramage et al., 2011] is just different from the TWTM model, where the assumption of topic assignment for d in PLDA is that the word generated by choosing only one of the observed tags' index, while TWTM assumes the topic distribution of d obtained by weighted average of all the observed tags' topic distributions.

3.3 Model Learning and Inference

In topic models, the key inferential problem that we need to solve is that of computing the posterior distribution of the hidden variables given a document d. Given a document d, we can easily get the posterior distribution of the latent variables in the proposed model, as:

In Eq. (1), integrating over ε and summing out z, we easily obtain the marginal distribution of d:

However, this posterior distribution of the hidden variables ε and z is intractable to compute in general. A variety of algorithms have been used to estimate the parameters of topic models, such as Monte Carlo Markov chain(MCMC) sampling techniques [Andrieu et al., 2003; Griffiths and Steyvers, 2004], variational methods [Attias, 1999] and others methods [Asuncion et al., 2009; Sato and Nakagawa, 2012]. For sampling methods, actually, because of the nonconjugacy of the function of tag-weighted topic assignment, we have to appeal to a tailored solution of MCMC [Blei and Lafferty, 2005]. Such a technique will impede the requirement of convergence properties and speed, especially when the corpus comprise millions of words. Thus, we make use of meanfield variational EM algorithm [Bishop and Nasrabadi, 2007] to efficiently obtain an approximation of this posterior distribution of the latent variables in the TWTMmodel. In meanfield variational inference, we minimize the KL divergence between the variational posterior probability and the true posterior probability through by maximizing the evidence lower bound (ELBO) L(·) [Blei and McAuliffe, 2007]. For a single document d, we obtain the L(·) using Jensen's inequality:

where ξ is a l d -dimensional Dirichlet parameter vector and γ is 1×K vector, which are variational parameters of variational distribution, and H(q) indicates the entropy of the variational distribution:

Here the exception is taken with respect to a variational distribution q(ε d , z1:N), and we choose the following fully factorized distribution,

The dimension of parameter ξ is changed for different documents.

The way of tag-weighted topic assignment leads to difficulty in computing the expected log probability of a topic assignment:

To preserve the lower bound on the log probability, we upper bound the log normalizer using Jensen's inequality again:

where the expression of θ (i) , i ∈ {1, · · · , l d }, means the i-th tag's topic assignment vector, corresponding to the i-th row of Θ d . Note that the expectation of Dirichlet random variable is E[ε d i ] = ξj/∑l d j ξj. Thus, for document d,

Then, we maximize the lower bound L(ξ, γ; η, π, θ, ψ) with respect to the variational parameters ξ and γ, using a variational expectation-maximization(EM) procedure.

In particular, by computing the derivatives of the L(·) and setting them equal to zero, we obtain the following update equations:

where v wi denotes the index of wi in dictionary.

The ξj, j ∈ {1, · · · , l d }, in document d needs to be extended to t d l · ξ d l , l ∈ {1, · · · , L} for convenient to simplify L[θ].

ξi can be implemented using gradient descent method, by taking the derivative of the terms:

where Ψ(·) denotes the digamma function, the first derivative of the log of the Gamma function.

For document d, the terms that involve the Dirichlet π:

where (T d × π)i = ∑l d i ∑L l πlT d il . We can also use gradient descent method by taking derivatives of Eq. (6) with respect to πl on the whole corpus to find the estimation of π. Because each document's tags-set is observed, the Bernoulli prior η is unused included for model completeness. For a given corpus, the ηi is estimated by adding up the number of i-th tag which appears in all documents.

We show the variational expectation-maximization(EM) procedure of TWTM as follows. At the beginning, TWTM initializes the parameter π ,θ and ψ, with the constraint of ∑K k θl equals 1 and ∑V i ψk equals 1. In the E-step, for each document d, we update the variational parameter ξ and γ with Eqs. (5) and (2) to maximize the L(ξ, γ; η, π, θ, ψ). In the Mstep, π ,θ and ψ are updated as in Eqs. (6), (4), and (3). We repeatedly the update steps until the convergence condition of likelihood is satisfied or maximum number of iterations is reached.

4 Experimental Results

In the experiments of this work, we used three semistructured corpora. The first one consists of technical papers of the Digital Bibliography and Library Project (DBLP) dataset 2 , which is a collection of bibliographic information on major computer science journals and proceedings. In this paper, we use a subset of DBLP that contains abstracts of D=8,212 papers, with W=34,967 words in the vocabulary and L=1,893 unique tags. The tags we used in DBLP include authors, time, and keywords. The second corpus is The New York Times 3 news stories in March 2011, which is made up of D=4,307 stories, in which we treat 31 days of March 2011 as tags. And the last document collection is the data from Internet Movie Database (IMDB) 4 . The dataset includes 12,091 movie storylines, 52,274 words after removing stop words, and 3,654 tags which contain directors, stars, time, and movie keywords. And these movies belong to 29 genres.

4.1 Document Modeling

In order to evaluate the generalization capability of the model, we use the perplexity score that described in [Blei et al., 2003]. We trained three latent variable models including LDA [Blei et al., 2003], CTM [Blei and Lafferty, 2005] and our TWTM, on two corpora, a paper collection in DBLP and a set of movie documents in IMDB, to compare the generalization performance of the three models. In both datasets, we removed the stop words and conducted experiments using 5-fold cross-validation. Figure 2 presents the results on the DBLP dataset. The perplexity of TWTM is larger than or similar to LDA and CTM, when the number of topics T ≤ 100; when T increases, both CTM and LDA are running into serious over-fitting, while the trend of TWTM keeps going down and the perplexity is significantly lower than those of the baselines. Figure 3 demonstrates the perplexity results on the IMDB data. Clearly, TWTM excels both CTM and LDA significantly and consistently. Figures 2 and 3 show that TWTM works very well in semi-structured document modeling.

2 http://www.informatik.uni-trier.de/ ley/db/

3 http://www.nytimes.com

4 http://www.imdb.com

4.2 Examples of Tag-Topic Distributions

In the preceding section we demonstrated the performance of TWTM on the learning of tags' distribution by process the New York Times' full text. We treated the 31 days in March 2011 as the tags set of the news corpus, and set the number of topics K = 100. Each topic is illustrated with the top 20 words most likely to be generated conditioned on the topic from the matrix of ψ. We found one topic about the Japan earthquake happened in March 11, 2011. The keyword representation of the topic is shown in Figure 4.

Figure 5 shows that the topic we selected has the different value between the tags, the 31 days. The results shows that at the label of "Mar. 11" the value reaches maximum and there is another extreme value appeared at "Mar. 30". The date of Mar. 11 is when the earthquake happened with the highest value, and at the date of Mar. 30, there are some other news about Japan Nuclear leak , for the example of first detected the radioactive elements plutonium.

The capability of inferring the distributions of tags is obtained directly through the proposed model TWTM. And furthermore, there is no need to distinguish between the different types of labels so as to make use of all the tags observed in the document.

4.3 Classification Performance Comparison

The next experiment is to test the classification performance utilizing feature sets generated by TWTW and other baselines. For the base classifier, we use LIBSVM [Chang and Lin, 2011] with Gaussian kernel and the default parameters. For the purpose of comparison, we trained three SVMs on tf-idf word features, features induced by a 100-topic LDA model, and features generated by a TWTM model with the same number of topics, respectively. Since the TWTM method uses the tag information, we append the tag vector t d to both the tf-idf and LDA feature sets.

In these experiments, we conducted multi-class classification experiments using the IMDB dataset, which contains 29 genres. We calculated the evaluation metrics recall@1 and recall@3 with the provided class tags of movies' genres, using 5-fold cross-validation.

We report the movie classification performance of the different methods in Figure 6, where we see that there is significant improvement in classification performance when using LDA and TWTM comparing with tf-idf, and TWTM outperforms LDA in terms of both recall@1 and recall@3.

5 Conclusions

With the tag-weighted topic model proposed in the paper, we provide and analyze a probabilistic approach for mining semistructured documents. This model provides significantly improved predictive capability in terms of perplexity compared to the other topic models, such as LDA and CTM. Besides, TWTM was shown to be able to obtain the topics distribution of tags in the corpus, which is very useful for text classification, clustering and other data mining applications. Meanwhile, TWTM proposes a novel framework of processing the tagged text with a high extensibility, and uses a novel function of tag-weighted topic assignment of documents. The primary benefit of the tag-weighted topic model is that it allows one to incorporate different types of tags in modeling documents, and provides a general framework for multi-tags modeling at not only the level of tags but also the level of documents. It helps provide different approaches in classification, clustering, recommendation, and so on. In the future, we plan to apply TWTM to different practical areas, especially the problems of the large-scale document modeling.

Acknowledgments

We thank the anonymous reviewers for helpful comments. This work was supported by National Natural Science Foundation of China (61003140 and 61033010).