Open Domain Short Text Conceptualization: A Generative + Descriptive Modeling Approach

1 Introduction

Short text conceptualization is a task to map a piece of short text to a large set of open domain concepts with different granularities. 1 Since short texts are usually lack of context, mapping short texts to concepts can help better make sense of text data, extend the texts with categorical or topical information, and facilitate many applications. For example, it has been verified very useful for word/phrase similarity/relatedness measure [Gabrilovich and Markovitch, 2007; Li et al., 2013; Agrawal et al., 2014], short text categorization [Gabrilovich and Markovitch, 2006; Wang et al., 2014], Twitter messages clustering [Song et al., 2011], search relevance measurement [Egozi et al., 2011; Song et al., 2014], search log mining [Hua et al., 2013], advertising keywords semantic matching [Liu et al., 2012; Kim et al., 2013], and dataless text classification by label understanding [Chang et al., 2008; Song and Roth, 2014; 2015].

1 In this paper, we focus on the explicit concept mapping approaches. For more comparisons of explicit and latent semantic analysis for text representation, please refer to [Huang et al., 2012; Song and Roth, 2014] for more details.

Typical concept mapping methodologies include the so called probabilistic conceptualization [Song et al., 2011] and explicit semantic analysis (ESA) [Gabrilovich and Markovitch, 2009]. We first briefly review the two models as follows.

Probabilistic conceptualization: Given a set of terms (words or multiple-word expressions) E = {e1, . . . , eM} in a short text 2 , probabilistic conceptualization tries to find the concepts associated with scores that can best describe the terms. Suppose we have a general and open domain concept set C = {c1, . . . , cT}. In probabilistic conceptualization, it makes the naive Bayes assumption of the conditional probabilities and uses

as the score associated with ct. Here, P(em|ct) = n(em,ct) n(ct) where n(em, ct) is the co-occurrence frequency of concept ct and term em in the sentences used by information extraction, and n(ct) is the overall number of concept ct. Moreover, P(ct) = n(ct) ∑t n(ct) is normalized by the number of all the concepts in C. The basic assumption behind this model is that given each concept ct, all the observed terms em ∈ E are conditionally independent. Then it uses the probability P(ct|E) to rank the concepts and selects the concepts with the largest probabilities to represent the text containing the terms in E. However, this has a major drawback:

• Naive Bayes will quickly boost the concepts co-occurred with all the observed terms in the short text due to the multiplication term ∏Mm=1 P(em|ct), and dismiss the concepts partially matching the terms. In particular, in some extreme cases, only the general and vague concepts, e.g., topic or thing, can be retrieved co-occurring with all the terms, whereas, the partially matched concepts would be more specific and descriptive to represent the text.

Explicit semantic analysis (ESA): ESA simply combines the weighted concepts of each term in a short text. We use em = (em,1, ..., em,T ) ∈ RT+ to represent the concept vector of the term em. For example, we can set em,t = f(n(em, ct)) as a function of the co-occurrence of the term em and ct. In the original ESA, it uses TF-IDF (term frequency-inverse document frequency) score of em shown in the t-th Wikipedia page, which is denoted as a concept ct. We use a vector c = (c1, ..., cT ) ∈ RT+ to denote the concept proportion that can describe the whole short text containing E = {e1, . . . , eM}. Then ESA recalls the concepts with scores as this:

2 Parsing short text to be words or multi-word expressions can be non-trivial [Song et al., 2014]. We ignore this since it is not the focus of this paper.

where wm is the weight associated to em, e.g., the TF-IDF score of em in the short text. The benefit of using this representation is that the values in the concept vectors em are not restricted to the co-occurrence frequencies, but can be arbitrarily tuned. However, it is still not without problems:

• The resulting concept vectors can be noisy. For example, for the text "microsoft unveils office for apple's ipad," we all know that in this context "apple" should not be a fruit. However, simply adding em will also introduce fruit as a concept to describe the text. The backend intuition of this computation is that it assumes that there is only one term cluster in the short text, and uses the (weighted) mean of concept vectors, which is the center of the terms in concept vector space, to represent the text, regardless the sense of the word. Particularly, sense disambiguation is more serious for short texts such as tweets and search queries, since with more words, the impact of the ambiguous concepts will be reduced as less significant.

We can use two operations to illustrate the results of probabilistic conceptualization and ESA: intersection used by probabilistic conceptualization and union used by ESA. In Table 1 we see that intersection of concepts for "obama" and "real-estate policy" will get topic, thing, issue, etc., while union of the concepts for "apple" and "microsoft" will have concepts such as fruit but not correct to represent their meaning. Thus, intersection of different concept sets will sharpen the meaning of the representation, while union will broaden the meaning. When the terms in a short text are related, intersecting the concepts can help us disambiguate them. However, when the terms are not related, intersection will get only very general or vague concepts.

Given the above analysis that both approaches are with modeling shortcomings for short text conceptualization, in this paper we propose an approach that can incorporate both intersection and union operations. The contributions of this paper can be summarized as follows.

• We show how existing conceptualization approaches can be reformulated as descriptive, generative and discriminative models in a framework. This is the first attempt to unify different short text conceptualization methods.
• We introduce a generative + descriptive modeling approach under the framework for short text conceptualization and demonstrate its effectiveness using a news title data set and a Twitter message data set in the experiments.

2 Descriptive, Generative, and Discriminative Modeling

To summarize from the modeling perspective, analogous to the image conceptualization frameworks discussed in [Zhu, 2003], we also introduce and analyze three ways to perform short text conceptualization as: descriptive, generative and discriminative models. In the descriptive and generative models, we consider to model the probability P(e1, ..., eM|c). In the discriminative model, we consider directly modeling the probability P (c|e1, ..., eM).

Descriptive Model (Causal Markov Model): The probabilistic conceptualization can be regard as a simple causal Markov model, since it imposes the partial order of the probabilities of concept-term relationship. We first assume the conditional independency of em given c: P(e1, ..., eM|c) = ΠMm P(em|c). Then we define P(em|c) ∝ ΠTt P(em,t|P(em|ct)) = ΠTt P(em|ct)em,t as a multinomial distribution where P(em|ct) is calculated based on the evidence of co-occurrence in knowledge base (explained under Eq. (1)). We define em,t = 1 if for this trial ct is selected as the description of the short text and em,t′ = 0 for t′ ̸= t. Now we can factorize P(e1, ..., eM|c) as:

By incorporating the prior P(c) ≜ ∏Tt=1 P(ct), we can re-write the posterior of c:

Then selecting the top k concepts using Eq. (1) among all the T concepts can be considered as the maximum a posterior (MAP) estimation of this posterior in Eq. (4). This illustrates what probabilistic conceptualization really optimizes. Thus, if one of the probability P(em|ct) equals to zero, then the whole probability P(c|e1, ..., eM) equals to zero. Even if a smoothing technique can be applied [Song et al., 2011], the probability mass P (c|e1, ..., eM) could be too small to be reasonable in this case.

Generative Model: ESA can be regarded as a generative model since it uses the concept-term relationship as the evidence of generated features of terms, and estimates the latent concept distribution which generates the features. If we formulate the probability P(e1, ..., eM|c) as:

where P(em|c) is assumed to be a Gaussian distribution centered by the underlying concept distribution c. Then c = 1M ∑Mm=1 em is the maximum likelihood estimate with the probability P(e1, ..., eM|c). Here P(em|c) is more flexible and not necessarily to be factorized as ΠTt P(em|ct). For example, em,t (t = 1, ..., T) in the concept vector em can be the co-occurrence frequency of concept ct and term em in the same sentence or same document. We can also define em,t ≜ P(ct|em) which is the typicality of a concept ct to describe the term em, or P(em|ct), which is the typicality of how much a term em can instantiate the concept ct.

The formulation in Eq. (5) also explains why explicit semantic analysis assumes that there is only one cluster of the terms observed in the short text. A natural way to extend this is to perform clustering by assuming there are multiple clusters of concept vectors. However, there is still problem if we do not consider the concept intersection problem inside term clusters, since the computation of a cluster center is the average of all the vectors to represent the terms inside the cluster. In this case, the ambiguous concepts will still show up in the final representation.

Discriminative Model: Yet another way for conceptualization is to classify the short text onto a predefined taxonomy or ontology. Classification can be regarded as the discriminative model which wants to estimate c by directly modeling the probability P(c|e1, ..., eM). For example, we can learn (or simply find) a set of projection vectors wt, t = 1, ..., T, to project the observed text to maximize P(ct|wt, e1, ..., eM) = 1Z f(wt, g(e1, ..., eM)), where the concept vector is considered as a feature vector to generate the representation of the short text. A typical g(e1, ..., eM) can be 1M ∑Mi=m em (more representations can be found in [Song and Roth, 2014]). Since discriminative model is costly when the number of concepts is large (e.g., millions of concepts) and thus is not the focus of this paper, we do not expand this direction and leave for further development and comparison.

We can see that both the simple descriptive and generative approaches factorize the probability as ∏Mm=1 P(em|c), which do not consider the relationships between em's. In the following section we introduce a generative + descriptive model that tries to jointly model P(e1, ..., eM|c) to incorporate the relationships between terms with more descriptive power.

3 Generative + Descriptive Conceptualization

In this section, we introduce our generative + descriptive conceptualization model. We incorporate the term relationships into the generative model, and formulate it as a Markov random field (MRF). Then we regard conceptualization as the latent variable inference problem of the MRF model.

3.1 Graphical Model

Since terms can be used to disambiguate each other if they have relationships, we want to break the i.i.d. assumption used by the above descriptive or generative models which factorize the conditional joint probability as ∏Mm=1 P(em|c).

We introduce a graph built on the terms E = {e1, . . . , eM} and introduce an energy function for each maximal cliques in the graph.

Intuitively, if a short text contains both "apple" and "microsoft," then the importance of concept "company" will be larger and the concept "fruit" is not an appropriate concept to describe both terms. We introduce the probability of P(concept vector of {apple,microsoft}|c) to remove the ambiguity. Particularly, we represent the feature of tth concept related to "apple" and "microsoft" as ¯ I0(eapple,t) · ¯ I0(emicrosoft,t) · (eapple,t + emicrosoft,t), where ¯ I0(x) = 1 if x ̸= 0 and ¯ I0(x) = 0 if x = 0. In this case, only their common concepts are considered. The common concept detection for related terms then corresponds to the intersection mechanism.

Formally, to introduce the relationship between observed terms in a generative model, we build an undirected graph to describe them, and factorize the joint probability based on its maximal cliques. An example graphical model is shown in Figure 1(a). If we have parsed terms e1, . . . , eM in a short text, and detected the relationships between e1, e2, and e3, then in the graphical model, we have a maximal clique: {e1, e2, e3}. In this case, instead of mapping the single terms to concepts, we map the cliques to concepts. We also denote α = (α1, ..., αT ) ∈ RT+ as the hyperparameter of the prior of the concept distribution c. In the following, we first show how to formulate the concept vectors em's, and then show how to parameterize the joint probability PΦ(α, c, {em}Mm=1 , {πm}Mm=1 ).

Concept Vector for Each Term

We use Probase [Wu et al., 2012] here as the knowledge base to demonstrate the conceptualization framework. Probase uses an automatic and iterative procedure to extract concept knowledge from 1.68 billion Web pages [Wu et al., 2012]. It contains 2.36 millions of open domain concepts, and provides around 14 millions relationships with two kinds of important knowledge related to concepts: concept-attribute co-occurrence and concept-instance co-occurrence. 3 When we detect a term em in a short text, we introduce a type indicator πm to indicate whether em is an attribute (πm = 0) or an instance (πm = 1). Then the concept vector em ∈ ZT+ representing em is defined as:

We denote A ∈ ZT×V + is the concept-attribute co-occurrence matrix, where V is the number of distinctive instances and attributes in the knowledge base. The (t, v)-th entry At,v is an integer representing the co-occurrence count of concept t and attribute v, and A·,em is the em's column of A. Similarly, B ∈ ZT×V + is the concept-instance co-occurrence matrix.

Ideally, the graphical model is a mixture model and {πm}Mm=1 should be regarded as hidden variables. We need to apply the expectation-maximization (EM) algorithm to infer {πm}Mm=1 and combine A·,em and B·,em to generate em. However, considering that there are only less than 0.1% terms in Probase which can act as both instances and attributes, it is not worth using EM in most of the cases. We therefore use the following heuristic rules to determine a term's concept vector: (i) attribute seldom appears alone: if a term is not related to any other terms, it is invariably an instance; (ii) mutually exclusive: if a term acts as an attribute in a sentence, then it cannot act as an instance simultaneously. Then we compute {πm}Mm=1 in advance and simply treat them as observed variables. In the following sub-section, we will show how to determine the relationships between terms.

3 The data are available at http://probase.msra.cn/.

Clique Detection

We define r(i-i) (ei, ej) to measure the strength of the instance-instance relationship, which is defined as the cosine similarity between two vectors B·,ei and B·,ej :

instance-attribute relationship r(i-a) (ei, ej) is similarly defined by using B·,ei and A·,ej . Note that other metrics or data sources to compute the term relatedness can be applied [Gabrilovich and Markovitch, 2007; Li et al., 2013; Huang et al., 2012]. Here we only use this simplest implementation to demonstrate the framework. Given a tolerance τ, an edge between ei and ej is introduced if

otherwise ei and ej are not linked. For example, if both "apple" and "microsoft" appear in the short text, we will build an edge between them since the similarity is large. Another example is if "population" co-occurs with "new york city," then population is regarded as an attribute since the concept vector for attribute "population" (concepts are country, city, location, region, etc.) has much larger similarity than the concept vector of instance "population" (concepts are geographical data, data, information, etc.) with the concept vector of "new york city."

Factorization

Suppose there are K maximal cliques, which cannot be extended by including any one more adjacent em representing em. Let Ik be the set of indices of those terms in the k-th maximal clique, and Ek = {em, πm}m∈Ik . Then Ek∪{c} is a maximal clique of the moralized graph [Koller and Friedman, 2009]. We factorize the joint distribution as:

where Z is the partition function. We denote f(Ek) ∈ ZT+ be the feature vector of the clique which has a multinomial distribution parameterized by c and ft(Ek) is the tth entry of f(Ek). Then the factor φ(Ek, c) is defined as

where ft(Ek) = (∏i∈Ik ¯ I0(ei,t))·(∑j∈Ik ej,t), and ¯ I0(x) = 1 if x ̸= 0; ¯ I0(x) = 0 if x = 0. The feature function ft(Ek) sums the co-occurrence counts only if the related terms (i.e., in the same clique) all have this concept t; otherwise this concept is discarded. For example, if "apple" and "microsoft" appear together, concepts such as "fruit" will be filtered out.

Finally, we define a Dirichlet prior distribution parameterized by α for the multinomial distribution parameter c, i.e.,

which is a conjugate prior of multinomial distribution. If we have no prior knowledge of which concepts are more important, we can use symmetric α, i.e., all entries of α are equal.

3.2 Latent Variable Inference: Conceptualization

Given the factorized joint probability distribution PΦ(α, c, {em}Mm=1 , {πm}Mm=1 ), we want to infer the latent variable c by the MAP estimation. Since c is modeled as a multinomial distribution to generate the concept vectors for the maximal cliques, we can then use the inferred concept distribution to describe short text. We can also call this procedure as a probabilistic conceptualization.

Given Eqs. (8), (9) and (10), the posteriori of c over the factors Φ = {φ(α, c)}⋃{φ(Ek, c)}Kk=1 can be rewritten as

Given {πm}Mm=1 and α fixed, and {em}Mm=1 determined, we maximize Eq. (11) w.r.t. c, and the solution is:

As a special case of (12), when the terms are (assumed) independent, the solution is copt t = (αt - 1 + ∑Mm=1 em,t)/∑Tt=1 (αt - 1 + ∑Mm=1 em,t), ∀ t = 1, . . . T. The solution copt has the following explanations. If some terms are related with each other, only their mutual concepts are summed. If all the terms are independent, the concept distribution is proportional to the sum of the co-occurrence count of the concept and each term plus the prior. This results in a similar solution as ESA. While ESA uses the maximium likelihood estimation, which relates to P(e1, ..., eM|c), our solution uses MAP estimation, which relates to P(c|α, e1, ..., eM).

3.3 Hyperparameter Estimation: Corpus Adaptation

The Dirichlet prior of concept distribution c is parameterized by α. Larger αt indicates that concept t is more important for all the short texts in a corpus. If the corpus is general, we can use symmetric α. When the corpus is of several specific topics such as "technology" and "business," some concepts such as "IT," "company" and "industry" are more common than the others. In this situation it is necessary to strengthen the important concepts by setting the corresponding entries of α large. For this reason, we provide a maximum likelihood estimation method for learning the hyperparameter α based on a corpus.

By integrating out c in PΦ(α, c, {em}Mm=1 , {πm}Mm=1 ), the resulting distribution over α is

As shown in Fig. 1(b), consider we are given N short texts; the m-th term parsed from the n-th text is denoted as e(n) m (e(n) m as its concept vector), and πm(n) , E (n) k are similarly defined. Suppose the texts are i.i.d. with a common parameter α, the log likelihood function of the N texts is

The hyperparameter α can be learned on the corpus of the N texts by the following fixed-point iteration:

for t = 1, · · · , T, where Ψ(x) = d log(Γ(x))/dx is the digamma function. The resulting α∗ maximizes the log likelihood function (14). The proof is shown in [Minka, 2003].

4 Experiments

In this section, we show experiments on two short text data sets to compare our method with existing conceptualization methods.

News Title: We extract news titles from a news corpus containing about one million articles searched from Web pages. The news articles have been classified into topics. We select six topics, i.e., company, disease, entertainment, food, politician, and sports, to evaluate different approaches. We randomly select 3,000 news articles in each topic, and only keep the title field. We call this data set the News Title Data Set. The average word count of the 18,000 news titles is 7.96.

Twitter: In this data set, the 4,542 tweets are in three categories: company (1,205), country (1,747), and device (1,590). The data in company category includes tweets about microsoft, google, apple, etc. The data in country category includes tweets about china, india, usa, japan, isreal, canada, etc. The data in device category includes tweets about kindle, iphone, xbox, etc. The average length of the Tweets is 13.36 words. Tweets are more noisy than news titles. For example, the tweets "Win an Amazon Kindle 3G Wireless from @FreeLunched Quick and easy registration at http://bit.ly/9fBuw4" and "Conker, Live and Reloaded - XBox game #xbox" have no overlapped terms, but they should be grouped together in this problem.

4.1 Methods and Settings

We first use each method to obtain concepts (or topics) of each short text in the two data sets. Then we use the concepts (or topics) as features and run spherical K-means clustering [Dhillon and Modha, 2001] to evaluate each method. To evaluate our method, we mainly compare it with the bag-of-words approach weighted by TF-IDF scores [Salton and McGill, 1983], LDA [Blei et al., 2003], probabilistic conceptualization (Song et al. 's approach [Song et al., 2011]), and ESA [Gabrilovich and Markovitch, 2007], since these approaches are most related to ours.

TF-IDF: TF-IDF represents each text data as bag-of-words. A high weight will be given by a high term frequency in the given document and a low document frequency of the term in the whole text corpus. TF-IDF tends to filter out common terms. For our test data sets, we first remove about 400 stop words such as "the," "of," "good," etc. Then we compute TF-IDF of the words in each document based on the given test corpus and use the TF-IDF scores as features for clustering. TF-IDF is employed as a baseline of the clustering experiments.

LDA: We use Gibbs sampling inference of LDA [Blei et al., 2003] which is implemented by Mallet [McCallum, 2002] in this experiment. Two different methods are used for training the topics.

• 1 We train LDA and test on the same short text data. Since the two corpora are all of short texts, LDA works with extremely sparse data. We set the topic number to be the cluster number or twice the cluster number and report the better of the two. This method is denoted as "LDA #1."
• 2 For the news data, we also train the LDA model on long texts (the main body of the news) and test it on the

short texts. We use the body field of the news articles corresponding to the titles for training. Each article has several hundreds of words. The topic number is set to be 10 or 20, and we report the better of the two. This method is denoted as "LDA #2."

ESA: We import the Wikipedia articles from the Wikipedia dump. 4 To improve ESA, we preprocess the Wikipedia articles with the following rules. First, we remove the articles less than 100 words and remove the articles less than 10 links. Then we remove all the category pages and disambiguation pages. Moreover, we move the content to the right redirection pages. Finally we obtain about one millions Wikipedia articles for indexing. We compute TF-IDF weights for word concept pairs as presented in [Gabrilovich and Markovitch, 2007]. Top 1,000, 2,000, and top 10,000 concepts are used as features for clustering, and we report the best.

Probabilistic Conceptualization (Probabilistic Concept.): We implement the method [Song et al., 2011] and the top 100, 200 and 400 concepts are used for clustering respectively, and we report the best.

Generative + Descriptive Conceptualization (G+D Concept.): We compute the concept distribution c for each text, and use top 400 concepts in the clustering experiments.

4.2 Clustering Results

We use spherical K-means clustering on the concept (or topic) vectors generated by each method. The spherical K-means clustering results also depend on initialization (especially when the data vectors are of high dimension). In this experiment, we randomly initialize K-means and repeat clustering five times to report the result with the lowest objective function value. All the numbers reported is based on 10 random trials (each trail is based on five random initialization).

The clustering results for news title data are shown in Table 2. The normalized mutual information (NMI) [Strehl and Ghosh, 2002] scores are presented. In general, the larger the NMI scores are, the better the clustering results are. We report the results of pairwise category clustering here to check the more detailed information. From the results we can see that, LDA #1 performs worst because it is trained on very sparse short texts, where there is no enough statistical information to infer word topics. LDA #2 is better, but it still underperforms the three knowledge based methods. We can also train LDA on a very large corpus, e.g., Wikipedia, and can expect much better results. However, training LDA on very large data set is much slower than the knowledge extraction procedures used by ESA and Probase. Sometimes ESA performs best, however, it does not show significant improvement over our method. Contrarily, for the problems ESA does not perform well, i.e., "Company vs. Entertainment" and "Entertainment vs. Sport," our method works very well. Moreover, we can see that our method significantly outperforms Song et al. 's conceptualization method.

4 http://en.wikipedia.org/wiki/Wikipedia:Database download

For the Twitter data, since we are not able to find appropriate long texts, LDA #2 is not performed. The clustering results are shown in Table 3. We can see that the results are consistent with the news title data set. Our method performs the best and shows improvement over the compared methods.

5 Conclusions

We have unified descriptive, generative, and discriminative text conceptualization in a Bayesian perspective, and discussed the advantages and problems respectively. To solve the problems, we proposed a generative + descriptive solution to short text conceptualization. The model incorporates both union and intersection operations of the concept sets for the terms detected in the short text, and results in better conceptual descriptions. We use one news title data set and one Twitter message data set to demonstrate that clustering on our conceptualization results can outperform the state-of-the-art conceptualization and topic modeling approaches.

Acknowledgments

The authors would thank Professor Dan Roth and the anonymous reviewers for the helpful comments and suggestions to improve this paper. This work is partially supported by the Multimodal Information Access & Synthesis Center at UIUC, part of CCICADA, a DHS Science and Technology Center of Excellence, by the Army Research Laboratory (ARL) under agreement W911NF-09-2-0053, and by DARPA under agreement number FA8750-13-2-0008. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied by these agencies or the U.S. Government.