Bag of biterms modeling for short texts
Anh Phan Tuan Bach Tran Thien Nguyen Huu Linh Ngo Van Khoat Than
cs.LG stat.ML














Anh Phan Tuan1   tuananhlfc@gmail.com    
           

Bach Tran2            tranxuanbach1412@gmail.com     
           

Thien Nguyen Huu3            thien@cs.uoregon.edu     
           

Ngo Van Linh4   linhnv@soict.hust.edu.vn    
           

Khoat Than 5             khoattq@soict.hust.edu.vn     
          
         
1,2,4,5  School of Information & Communication Technology, Hanoi University of Science and Technology, No. 1, Dai Co Viet road, Hanoi, Vietnam 

3  Department of Computer and Information Science, University of Oregon




Bag of biterms modeling for short texts[This paper is an extension version of the PAKDD2016 Long Presentation paper “Mai, K., Mai, S., Nguyen, A., Van Linh, N.,& Than, K. (2016). Enabling Hierarchical Dirichlet Processes to Work Better for Short Texts at Large Scale. In Advances in Knowledge Discovery and Data Mining (pp. 431-442). Springer International Publishing.]

    Anh Phan Tuan Bach Tran Thien Nguyen Huu Linh Ngo Van Khoat Than

    Received: date / Accepted: date
==================================================================================================================================================================================================================================================================================================================================================================================




Analyzing texts from social media encounters many challenges due to their unique characteristics of shortness, massiveness, and dynamic. Short texts do not provide enough context information, causing the failure of the traditional statistical models. Furthermore, many applications often face with massive and dynamic short texts, causing various computational challenges to the current batch learning algorithms. This paper presents a novel framework, namely Bag of Biterms Modeling (BBM), for modeling massive, dynamic, and short text collections. BBM comprises of two main ingredients: (1) the concept of Bag of Biterms (BoB) for representing documents, and (2) a simple way to help statistical models to include BoB. Our framework can be easily deployed for a large class of probabilistic models, and we demonstrate its usefulness with two well-known models: Latent Dirichlet Allocation (LDA) and Hierarchical Dirichlet Process (HDP). By exploiting both terms (words) and biterms (pairs of words), the major advantages of BBM are: (1) it enhances the length of the documents and makes the context more coherent by emphasizing the word connotation and co-occurrence via Bag of Biterms, (2) it inherits inference and learning algorithms from the primitive to make it straightforward to design online and streaming algorithms for short texts. Extensive experiments suggest that BBM outperforms several state-of-the-art models. We also point out that the BoB representation performs better than the traditional representations (e.g, Bag of Words, tf-idf) even for normal texts.








§ INTRODUCTION
	
In recent years, short texts have emerged as a dominant source of text data, being used in the major activities on the web such as search queries, tweets, tags, messages and social network posts. It is therefore crucial for us to be able to automatically analyze such large amount of short texts and gain valuable knowledge from it. Conventional topic modeling techniques such as pLSA <cit.>, LDA <cit.>, and HDP <cit.> are the natural considerations to perform such analysis as they have been demonstrated as the successful techniques for text analysis with the usual long documents. Unfortunately, the direct application of those topic modeling techniques causes various issues for short texts due to their unique characteristics of being short, informal, massive and dynamic. A typical issue concerns the shortness of the texts. In particular, the conventional topic models exploit the word co-occurrence information in the same topics to identify the main topics of documents; however, the word co-occurrences are very infrequent (data sparsity) for short texts. This has led to the poor performance of topic models for short texts despite the fact that the text collection might be large <cit.>. The challenges caused by short texts can also be found in the other prior studies <cit.>.

In order to alleviate the problem of data sparsity for short texts, three major heuristic strategies have been proposed, i.e, (1) the strategy <cit.> that employs external resources or human knowledge to overcome the challenge of lacking information, (2) the strategy <cit.> that modifies input data to enhance the word co-occurrence information and then simply pass the new input to the conventional topic models, and (3) the strategy <cit.> that develops new probabilistic topic models better suited for with short texts. Obviously, the first strategy is an effective approach to enrich short texts. Unfortunately, to the best of our knowledge, all existing works only focus on batch learning, and as a consequence cannot be considered as conventional methods to deal with short texts that are massive and dynamic in practice. Regarding the second strategy, the popular technique is to combine multiple documents into a single one. This technique is simple and beneficial as it artificially increases the length of the input documents and enhances the word co-occurrence information. However, a fatal issue of this strategy is that it has to know the metadata of the data source in advance to guide the combination process. Consequently, the second strategy is also not universal as it cannot be used for all scenarios in practice (especially the ones without metadata). Finally, the third strategy, i.e, developing new statistical models, seems to be the most flexible approach among the three aforementioned strategies to deal with the statistical issues in data very well. However, designing better models is not always an easy effort for different application domains. 

In this paper, we propose a hybrid strategy to address the sparsity problem of short texts combining the second and the third strategies mentioned above (i.e, both modifying the input data and developing new topic models for short texts). Our work also demonstrates the massive and dynamic challenges of short texts (which make batch learning inefficient) by focusing on the online and streaming methods. In particular, we present a framework for short texts with two major ingredients. First, BBM represents each document from corpus by Bag of biterms (BoB). A BoB is a bag that contains both terms and biterms appearing in a text snippet. A biterm, in turn, is a pair of terms in the text <cit.>. The employment of both terms and biterms in BoB offers several benefits for short text, i.e, (i) it naturally lengthens the document representation and thus helps to reduce the negative effects of shortness <cit.>, (ii) it helps to emphasize the co-occurrence of words by directly including the biterms in the modeling, and (iii) it also draws attention to connotations of the terms themselves, rather than just focusing on the word co-occurence revealed by biterms.


Second, BBM explitcitly models both terms and biterms in BoB. On one side, the framework inherits the way to encode each term in documents from the previous models. On the other side, we utilize the assumption that the two words in a biterm share the same topic and then model each word seperately. Therefore, BBM is essentially different from the previous works that have only attempted to lengthen the input documents (i.e, via external resources or multiple document aggregation) at the preprocessing step. The advantages of BBM include: (i) it does not assume the availability of any additional information or resources (e.g, the metadata information to guide the document aggregation in the previous methods), thus being applicable to a wide ranges of existing topic models (base models) to enable them to work well with short texts, (ii) the specific models built on BBM inherit the full advantages of the base models (e.g, easily designing online and streaming algorithms as in <cit.> and exploiting human knowledge in streaming environment as in <cit.>).



We conduct extensive experiments to demonstrate the benefits of the proposed framework. First, we demonstrate the advantages of BoB over the traditional schema to represent documents (i.e, Bag of Words, tf-idf) in both the supervised and unsupervised learning scenarios. Second, we find that the implementations of BBM outperform the premitives even when BoB representation is applied. Finally, BBM exceeds the state-of-the-art performance for short texts <cit.> in both online and streaming settings. 


The rest of the paper is organized as follows. Section <ref> briefly reviews the previous approaches to deal with short texts and the background necessary for this paper. Section <ref> introduces the mechanism of BBM framework via the concept of BoB representation and the way to include BoB in statistical models. Section <ref> presents two particular case studies when applying BBM to probabilistic models. Section <ref> describes the experiments and the evaluation results of the proposed techniques. Finally, some conclusions are made in Section <ref>.


§ RELATED WORK AND BACKGROUND



 §.§ Topic models on Short Texts

Due to the importance of short texts, much research effort has been spent on developing analysis methods for this kind of text. In this section, we focus on the methods that are employed in the previous research for topic models. These methods can be classified into three major groups as mentioned in Section <ref>.

The first strategy exploits the external resources or human knowledge to deal with short texts. Among a variety of external resources, perhaps Wikipedia is the most conventional resource in the prior research. The content from Wikipedia is often used to generate additional information/text to augment the short text input <cit.>. More recently, word embeddings have been widely adopted as an effective external knowledge to assist the models for short texts. In particular, the embedding-based topic model (ETM) in <cit.> builds word embeddings from external sources to generate semantic knowledge about the documents on which the aggregation decisions for the documents with short texts are relied. Afterward, ETM utilizes a Markov random field regularized model to extract latent topics from the generated pseudo documents. In <cit.>, the authors present the word  embedding informed focused topic model (WEI-FTM) that employs word embeddings as a prior knowledge for the distributions of the topics. While LDA considers each topic as a distribution over all words, WEI-FTM allows each topic to focus on fewer words. Finally, the GPU Dirichlet Multinomial Mixture (GPU-DMM) method in <cit.> exploits the general semantic word relations during the topic inference process. These semantic relations are learned from external resources, and then incorporated into the generalized Polya urn (GPU) model <cit.> in the sampling process. A common weakness of these strategies is that there would be no guarantee about the correlation between the universal corpus and the short text corpora since most of the short texts are produced from social networks with informal contents and noises. Moreover, they cannot work when data arrives continuously. Our work shows that BBM can also exploit word embeddings as a prior to improve experimental results in streaming environment.

In the second strategy to handle short texts, the input data is modified in rational ways whose results are fed into conventional topic models to induce topics. Specifically, Weng et al. <cit.>, Hong et al. <cit.> and Mehrotra et al. <cit.> aggregate tweets that share the users, the words and the hashtags respectively. In <cit.>, the authors postulate that each short text snippet is sampled from an unobserved long pseudo-document. Based on this idea, the self-aggregation based topic model (SATM) <cit.> is proposed to generate a set of D regular-sized documents and then use each document to obtain a few short texts for topic models. <cit.> presents a novel word co-occurrence network to construct pseudo documents. This network is called the biterm pseudo document topic model (BPDTM) and exploits the triangle relations among words (i.e, three words are semantically close if every two of them co-occur in the corpus). Finally, in <cit.>, the authors identify similar components (e.g. words or bi-grams) from external corpora to enrich the original short text documents. These methods share the same issue that the aggregating strategies cannot be applied to a wide range of datasets since they need to know the metadata of data sources (e.g, the hashtags, users etc.). Therefore, these methods might be only applicable for specific datasets but unsuitable for others. In addition, even if the aggregating strategies are reasonable, it is likely that the generated pseudo documents become more ambiguous due to the noises or ambivalent words. In this work, we also attempt to modify the input text to generate a new representation of the short texts. However, instead of explicitly aggregating the text snippets at the preprocessing step with metadata and feeding the new pseudo documents into the topic models, we generate additional clues based on only the words of the short text input and directly model those clues in the modeling step. This helps the proposed method avoid the metadata (thus being applicable to a wide range of datasets) and better exploit the additional clues via deeper modeling and analysis.

Finally, in the third strategy, new probabilistic topic models with better modeling mechanisms are proposed to circumvent the problems of short texts. The co-occurring document topic model (COTM) in <cit.> assumes that each document has a probability distribution over two set of topics (i.e, the formal topics and the informal topics). A switch variable is then introduced to determine the set of topics to which the text snippet belongs. The pseudo-document-based topic model (PTM) and the sparsity-enhanced PTM model (SPTM) in <cit.>, on the other hand, consider each short text as belonging to one and only one pseudo document, and then utilize the self-aggregation topic model (SATM) <cit.> to generate these pseudo documents. Although these new models obtain better results than the conventional topic models, almost all of the current proposed models cannot be applied directly to raw input data. They have to use some heuristic methods to enrich the input data before the new modeling technique can be applied. Consequently, these models still have the limitation of the first and the second strategies to some extent.  Perhaps the most related study to our work in this paper is <cit.> that also employs biterms in the novel biterm topic model (BTM), currently a strong baseline for analyzing short texts. In BTM, the model generates all pairs of words (called biterms) for each document and aggregate the biterms of all the documents into one collection. This is then followed by modeling the generative process for this collection. One problem of BTM is that aggregating all the documents in a corpus can make the context ambiguous, especially when the corpus involves a mixture of topics. Furthermore, this approach does not model the generative process for each document explicitly. The authors instead use a heuristic to infer the topic proportions for each document, causing the potential inconsistency between the training phase and the inference phase. In contrast, our proposed framework ameliorates the word co-occurence information by keeping the bag of biterms (BoB) within each document. We would then explicitly model the generative process for each document in the corpus using both the words and the biterms in the documents.

N-gram is also a popular representation method to enrich context information [31-33] for documents.  Some topic models such as bigram topic model [33] and topical N-grams [31] employ bigram to achieve better performance.  However, N-gram seems to be only suitable for long texts. There are some reasons why topic models using N-gram might not be effective to deal with short texts. First, since the frequency of N-grams in short-text corpus is small (i.e., almost bigrams occur in one or two documents), it is difficult for these models to learn hidden topics. Second, they do not utilize efficiently co-occurrence in short texts because they just model consecutive words. A short snippet often includes a topic and therefore all co-occurring words in this snippet should be paired to gain better understanding. Finally, they do not use both unigram and bigram to enrich the representation of short text.  While bigram topic model [33] only learns hidden topics on bigram, topical N-grams [31] uses a mechanism to model either unigram or bigram at a time.



 §.§ Background

Latent Dirichlet Allocation (LDA) <cit.> and Hierarchical Dirichlet Process (HDP)<cit.> are the most popular topic models for regular texts.  However, they cannot deal with short texts <cit.>. This subsection briefly describe them, serving as the base models for BBM in the next two case studies.


  §.§.§ Overview of Latent Dirichlet Allocation (LDA).



Suppose that the dataset contains D documents and K topics, and each document contain N words. A hyperparameter α contributes the distribution of topic mixture θ, and β is the topic distribution over V words of the vocabulary. The graphical representation of LDA is shown in Figure <ref>. The generative process of LDA is as follows: 


  * Draw topics β_k∼Dirichlet(η) for k ∈ [1, K]

  * For each document d ∈ [1,D]:
	
		
  * Draw topic proportions θ_d∼Dirichlet(α)
		
  * For each word w_dn∈{1,...,N_d}: 
		
			
  * Draw topic assignment z_dn∼Multinomial(θ_d)
			
  * Draw word w_dn∼Multinomial(β_z_dn)
		
	


There are several effective algorithms to enable LDA deal with massive and dynamic data, i.e, the online LDA  <cit.>, the streaming variation bayes (SVB) <cit.>, and the method to exploit human knowledge in streaming environment <cit.>. 



  §.§.§ Overview of Hierarchical Dirichlet Process (HDP).



While LDA is a powerful tool for discovering latent structures in texts, the fixed number of topics (K) makes it less flexible to handle the dynamic data. This has led to the development of Hierarchical Dirichlet Process (HDP) (shown in Figure <ref>) <cit.>, a nonparametric variant of LDA that allows the number of topics K to be countably infinite. In this paper, we follow <cit.> to use the stick-breaking construction to have a closed-form coordinate ascent variational inference. The generative process of HDP is:




  * Draw an infinite number of topics, β_k ∼Dirichlet(η) for k ∈{ 1,2,3,...}

  * Draw corpus breaking proportions, v_k ∼Beta(1, ω) for  k ∈{ 1,2,3,...}

  * For each document d:
		
			
  * Draw document-level topic indices, c_d,i∼Multinomial(σ(v)) for  i ∈{ 1,2,3,...}
			
  * Draw document breaking proportions, π_d,i∼Beta(1, α) for  i ∈{ 1,2,3,...}
			
  * For each word w_n:
			
				
  * Draw topic assignment z_d,n∼Multinomial(σ(π_d))
				
  * Draw word w_n∼Multinomial(β_c_d, z_d,n) 
			
		


Approximating the posterior distributions of latent variables in HDP is based on the idea of mean-field variational inference or Gibbs sampling. The details to perform inference and learning for online HDP are described in <cit.>.


  §.§.§ Representing documents by Bag of words (BoW)

Bag of words has been the conventional representation of documents in text mining. In this representation, the order of the words in a document is often ignored (i.e, the exchangeability of words) and a score is often associated with a word using some weighting mechanism (e.g., tf-idf). PLSA <cit.>, LDA <cit.>  and HDP <cit.> are among the typical statistical models that employ BoW as their standard representation for evaluation and comparison. However, despite the successes in analyzing regular texts, BoW exhibits many limitations in modeling short texts that have been the motivations to devise new models/methods to process this kind of text (as reviewed in Section <ref>). In the following section, we present bag of biterms, a novel document representation to overcome the limitations of BoW for topic models with short texts.


§ BAG OF BITERMS MODELING (BBM) FRAMEWORK

This section introduces the mechanism of BBM and describes several properties of the framework. BBM includes two main components: the Bag of Biterms (BoB) for representing documents and the way to model BoB in statistical models. 	


 §.§ Representing documents by Bag of biterms (BoB)



  §.§.§ Definitions



The following two definitions about biterms and bag of biterms (BoB) are necessary for our coming discussion.

Given a corpus, a biterm is defined as a pair of words that co-occur in some documents in the corpus. For example, assume that there are two words “character" and “story" in some documents. The set of biterms for these documents would then includes two pairs of words: (“character", “story") and (“story", “character"). The definition of biterms can also be extended to cover the single terms in the document by considering each term as a biterm with two similar words (e.g., (“character", “character") and (“story”, “story”)). This is the main reason for the name bag of biterms since each element in the bag can be seen as a biterm.  



Given a document d containing n distinct words {w_1,w_2, … ,w_n} with the respective frequencies {f_1,f_2, … , f_n }. For BoB, d is represented by a set of n terms w_i and n(n-1) biterms w̃_k = (w_i, w_j) (i, j ∈{1,2, …,n }, j ≠ i) with the respective frequencies as follows:


  * The frequency of w_i is f_i

  * The frequency of w̃_k = (w_i, w_j) is min(f_i, f_j) 


 For example, assume that d has three distinct words {w_1,w_2,w_3} with the respective frequencies of {2,2,4}. In BoB, this document is represented by a BoB including {w_1, w_2 , w_3, w̃_1 = (w_1, w_2), w̃_2 = (w_1, w_3), w̃_3 = (w_2, w_1), w̃_4 = (w_2, w_3), w̃_5 = (w_3, w_1), w̃_6 = (w_3, w_2)}. The respective set of frequencies is {2, 2, 4, 2, 2, 2, 2, 2, 2}. 
 Note that we choose the function min to compute the biterm frequencies instead of the other functions such as max or mean. Our intuition is that the biterm (w_i, w_j) is not as important as the original terms/words w_i and w_j so its weight should not exceed the weights of the original terms/words.

The definition of BoB above is based on the underlying document representation of BoW with terms/words as the basic units/features and frequencies as their weights. In general, we can extend this definition of BoB to span other underlying document representations or weighting schemas (e.g, tf-idf). The main idea is to employ the concept of features in the document representations, replace the words/terms with the feature values, and replace the term frequencies with the feature weights. More concretely, given a document d represented by n features with the feature values of {k_1, k_2, …, k_n} and the respective feature weights of {v_1, v_2, …, v_n }, the BoB representation of d with this underlying representation would then involve the set of biterms {b_ij=(k_i, k_j): i = 1,2, …,n, j=1,2, …, n} and the respective set of weights {v_ij=min(v_i, v_j): i = 1,2, …,n, j=1,2, …, n}. 

Essentially, BoB can be seen as a method to transform the input data representations that preserves the format of the underlying representation. This property allows BoB to be applicable to any topic models that can work with the underlying representations, thus making BoB a model-independent representation for topic models. In addition, BoB is a context-independent representation as it only uses the terms and biterms appearing in corpus. Different from most of the current methods to modify the input representation for short texts, BoB does not require any additional information (e.g., metadata or relevant external sources) to perform its transformation. Consequently, BoB can be used as a general approach for various types of short-text datasets. 



  §.§.§ Benefits of BoB for document representation

 

Although we presented BoB as an ingredient of BBM, it might also be regarded as a novel method for text representation. BoB gains various advantages over some conventional representation methods, especially in the context of short texts. In Section <ref>, we compare efficiency of BoB to the performance of BoW when applying to both supervised and unsupervised learning algorithms. However, the obvious drawback of using BoB as a text representation method is constructing vocabulary. In theory, the number of possible terms and biterms might be up to V_b = V(V-1)/2 + V= V(V+1)/2 where V is the number of distinct words in the corpus which might be up to several hundreds of thousands. This makes BoB cost much time and memory in some applications that require the computation of vectors with dimensionality being equal to the vocabulary size. One possible solution for this issue is to restrict the number of biterms in the models using some threshold for the frequencies of the biterms in the whole corpus. The experiments show how threshold number attenuate the impact of vocabulary size. Otherwise, we can explicitly model BoB in the modeling process to avoid this problem, as we present in the next phase of BBM framework. In what follows we address some benefits when using BoB in topic models instead of conventional representation schemes. 
First, BoB reduces the negative effects of shortness of short texts. In particular, the length of the document representations in BoB is much longer than that in BoW or the underlying representation due to the addition of the biterms b_ij. In a recent research <cit.>, the authors show that the document length is an important factor in such statistical models as LDA. When the document length is extremely short, the topic models are expected to have poor performance no matter how large the input corpus is. This fact is also supported by the experiments in <cit.> that improve the lengths of the short texts by aggregating short documents in rational ways, yielding better performance for the topic models. 

Second, BoB helps to emphasize the co-occurrence of words by treating the co-occurred words as units (e.g, the biterms b_ij with the words w_i and w_j in the documents). This co-occurrence modeling has been shown to be beneficial in the previous research as it helps to improve the performance of the topic models for short texts <cit.>.


Third, BoB can be seen as a kind of enrichment to the original document in a rational way. In particular, the biterms (w_i,w_i) can be treated as the original word w_i while the biterms (w_i,w_j) with i ≠ j are the additional “ingredients“. In a short document, the context is often ambiguous and unclear due to the lack of information. The additional ingredients (i.e, the biterms) from BoB would reinforce the context, making it clearer.








 §.§ Modeling Bag of Biterms (BoB)


In this section, we explore how BBM explicitly models BoB in the modeling process. Figure <ref> illustrates the distinction of modeling process between BoW (left) and BoB (right). The key idea is to use additional latent variables to generate the biterms explicitly besides the variables to generate terms in the primitive models. The generation of terms would then follow the mechanisms in the primitive topic models (i.e, LDA, HDP, etc.). In BBM, each biterm is generated by dividing it into two distinct words to be generated in the similar way as in the term part. The appealing point here is that despite separating the biterms into two terms, we only use one variable z̃_dm to denote the topic assignment of the biterms w̃_dm as well as their  two corresponding terms w̃_dm^(1) and w̃_dm^(2). Intuitively, this implies our assumption that the two words in a biterm share the same topic. For medium and long documents, this assumption might suffers from overfitting (we can avoid this problem by using bigrams instead of biterms in regular texts). However, for short text datasets, each document usually contains only one sentence with short length, leading to the tendency of the two top words to share the same topic. Since we are generating the two words of a biterm separately, it is unnecessary to construct a large vocabulary for biterms like in BoB. Consequently, the limitation on time and memory of BoB is diminished in BBM. In the next section, we will show two implementation of BBM in two probabilistic models: LDA and HDP, and we provide the generative process as well as learning algorithm of these case studies. 



 §.§ BBM Remark

We present several advantages of BBM and explain the main reasons why it is good.
First, BBM inherits all of the advantages of the BoB representation as well as eliminates its drawbacks of requiring much time and memory. As we have described, BBM explores the topic distribution of both terms and biterms during the learning process via the BoB representation. Therefore, it possesses all the benefits of BoB such as increasing the documents length, emphasizing the word co-occurence and enriching the context of the original documents (i.e, in Section <ref>). In addition, as BBM generates each biterm by dividing it into two distinct terms, we can avoid the expensive computation that involves the large vocabulary for BoB, leading to the overall reduction of time and memory.

Second, BBM is a general framework that can be incorporated with any topic models to generate a new branch of models based on BBM. The topic models in this incorporation with BBM are called the primitive (base) topic models. In BBM, the inference for the hidden variables of the word and biterm parts can be simply done in a very similar way to those in the the premitive models. Moreover, it is straightforward to develop online and streaming algorithms based on the previous work <cit.>, and exploit human knowledge <cit.> in the streaming environments.

Finally, BBM not only exploits the full advantages of BTM <cit.> but also overcomes its inherent disadvantages. By encoding the documents separately, the topic of each word in a document is not affected by the topic distribution of the other documents in BBM. It therefore avoids the problem of context ambiguity that BTM encounters when aggregating all the documents in a corpus. Moreover, it guarantees the model cohesion between the training and test phrases. 



§ BBM IN TOPIC MODELS

As we discussed, BBM can be applied to a large class of probabilistic models. In what follows, we show how to deploy BBM for the two conventional topic models: Latent Dirichlet Allocation (LDA) and Hierarchical Dirichlet Process (HDP).  


 §.§ Case study: Latent Dirichlet Allocation



We start by introducing a case study/implementation of BBM following the scheme of the LDA model, called LDA-B . The key idea is that we explicitly make a distinction between words and biterms during learning. The generative process is comparable to LDA, except that we generate N_d words and M_d biterms in document d.

The notations in the graphical models and the parameter inference equations are as follow. D is the number of documents while K is the number of topics. For each document d, the total number of words and biterms are N_d and M_d respectively. θ is the topic-document distribution, β is the word-topic distribution, z_dn is the topic assignment for the word w_dn, and z̃_dm is the topic assignment for the biterm w̃_dm. We use a tilde symbol to denote the biterm version of that variable. Finally, w̃_dm^(1) and w̃_dm^(2) are the first and second word of the biterm w̃_dm respectively.

Figure <ref> show the graphical representation of LDA-B. The generative process for LDA-B is as follow:


  * Draw topics β_k∼Dirichlet(η) for k ∈ [1, K]

  * For each document d ∈ [1,D]:
	
		
  * Draw topic proportions θ_d∼Dirichlet(α)
		
  * For each word w_dn∈{1,...,N_d}: 
		
			
  * Draw topic assignment z_dn∼Multinomial(θ_d)
			
  * Draw word w_dn∼Multinomial(β_z_dn)
		
		
  * For each biterm w̃_dm∈{1,...,M_d}:
		
			
  * Draw topic assignment z̃_dm∼Multinomial(θ_d)
			
  * Draw two words w̃_dm^(1), w̃_dm^(2)∼Multinomial(β_z̃_dm)
		
	


Based on the procedure above, our goal is to compute the posterior distribution. However, as this computation is intractable, we need to approximate it by a sampling or inference algorithms. In this work, we follow the mechanism of the primitive LDA <cit.> to perform the inference for both the term part and the biterm part of LDA-B. In particular, we choose the mean-field variational inference algorithm for this purpose. The details to compute the variational inference is shown in Appendix <ref>. The approximating distribution q_D takes the following form:

    q_D (β, θ, z |λ, γ, ϕ)     = ∏_k=1^K q_D(β_k |λ_k). ∏_d=1^D p(θ_d |γ_d) 
        . ∏_d=1^D∏_n=1^N_d q_D(z_dn|ϕ_d, w_dn). ∏_d=1^D∏_m=1^M_dq_D (z̃_dm|ϕ̃_d, w̃_dm)




where q_D(β_k |λ_k) = Dirichlet_V (β_k |λ_k), q_D (θ_d |γ_d) = Dirichlet_K (θ_d |γ_d), and q_D(z_dn|ϕ_dn) = Multinomial_K (z_dn|ϕ_dn), q_D (z̃_dm|ϕ̃_dm) = Multinomial_K (z̃_dm|ϕ̃_dm). The subscripts on the Dirichlet and Multinomial denote the dimensions of distributions. Here we summarize the updating rules for the following variational parameters: λ indicates the topic distribution over words, γ is the topic proportion in each document, ϕ and ϕ̃ describe the assignment of each word and each biterm (in each document) to a topic respectively. The approximation of the lower bound for q_D is described in Appendix <ref>. 

First, the update for γ is:

    γ_d, k = α_k + ∑_n=1^N_dϕ_d,n,k + ∑_m=1^M_dϕ̃_d,m,k



Then, the update for λ is:

    λ_k, v←η_k, v + ∑_d=1^D f(v, ϕ, ϕ̃)

where, 

    f(v, ϕ, ϕ̃) =  ∑_n=1^N_d I{ w_dn = v}ϕ_d,n,k +  ∑_m=1^M_d[ I{w̃^(1)_dm = v } + I{w̃^(2)_dm = v }] ϕ̃_d,m,k


Next, we write the update for ϕ:

    ϕ_d, n, k∝ exp { E_q[logθ_d, k] + E_q[logβ_k,w_dn] }


Finally, the update for ϕ̃ can be written by:

    ϕ̃_d, m, k∝ exp { E_q[logθ_d, k] + E_q[logβ_k,w_dm^(1)] + E_q[logβ_k,w_dm^(2)] }




Based on the inference of LDA-B, we can extend the previous works in <cit.> to fit LDA-B in the online and streaming environment. The resulting algorithms is presented in Algorithm <ref>, <ref>, <ref>, <ref>. Algorithm <ref> shows a variational Bayes procedure which takes the global parameter λ to infer the topic distributions of the terms (ϕ) and the biterms (ϕ̃) of the document d. Stochastic variational inference (SVI) <cit.> is an algorithm which enables LDA for online environment. We develop SVI to fit the LDA-B model as shown in Algorithm <ref>. A worthy note is that SVI uses two parameters, τ and κ, to determine the learning rate ρ_t at the iteration t: ρ_t = (τ + t)^-κ. Algorithm <ref> presents the streaming algorithm (also called SVB-B) created by exploiting Streaming Variational Bayes (SVB) <cit.> as a base framework fitting LDA-B to the streaming environment. SVB-B is straightforward LDA-B except that SVB-B updates the local parameters for each minibatch of documents as they arrive and then updates the current estimate of λ for each document d in the minibatch. Finally, Algorithm <ref> introduces the streaming algorithm (called KPS-B) developed from the Keeping Priors in Streaming (KPS) <cit.> framework and the model LDA-B. KPS-B is similar to SVB-B except that it exploits human knowledge as a prior and keep it for each update. Therefore, the only distinction between Algorithm <ref> and Algorithm <ref> is that KPS-B keeps the impact of the prior η on each minibatch instead of forgetting it as in SVB-B. 


 §.§ Case study: Hierarchical Dirichlet Process


Similar to LDA-B, this section describes HDP-B, a case study/implementation of BBM following the scheme of the HDP-B model. Figure <ref> shows the graphical representation of HDP-B. The generative process of HDP-B is as follow:


  * Draw an infinite number of topics, β_k ∼Dirichlet(η) for k ∈{ 1,2,3,...}

  * Draw corpus breaking proportions, v_k ∼Beta(1, ω) for  k ∈{ 1,2,3,...}

  * For each document d:
		
			
  * Draw document-level topic indices, c_d,i∼Multinomial(σ(v)) for  i ∈{ 1,2,3,...}
			
  * Draw document breaking proportions, π_d,i∼Beta(1, α) for  i ∈{ 1,2,3,...}
			
  * For each word w_dn:
			
				
  * Draw topic assignment z_dn∼Multinomial(σ(π_d))
				
  * Draw word w_dn∼Multinomial(β_c_d, z_dn) 
			

			
  * For each biterm w̃_dm:
			
				
  * Draw topic assignment z̃_dm∼Multinomial(σ(π_d))
				
  * Draw two words w̃_dm^(1), w̃_dm^(2)∼Multinomial(β_c_d, z̃_dm) 
			
		


Following the procedure for LDA-B, we apply mean-field variational inference to approximate the posterior distribution for HDP-B. The approximation for the biterm part of HDP-B is very similar to that of LDA-B. Likewise, the approximation for the word part is following the approximation in HDP (<cit.>) directly. We show the online learning algorithm for HDP-B in Algorithm <ref>. The relevant information of parameters and expectations for each update are found in <cit.>.







§ EXPERIMENTAL EVALUATION


This section evaluates the effectiveness of the BoB representation and the BBM framework with different premitive topic models on four large scale datasets. In particular, we compare the performance of the representations BoB and BoW in two tasks: the unsupervised topic modeling with LDA <cit.> and HDP <cit.>; and text classification with Support Vector Machines (SVM) <cit.>. In addition, we investigate the performance of BoB for the normal texts to see if BoB can be a general method for different kind of texts (i.e, both short and and usual long texts). Regarding BBM, we compare it with the base topic models to demonstrate its effectiveness for short texts. First, we compare HDP-B with the primitive HDP using both the BoB and BoW representations. Second, we evaluate the performance of LDA-B in the context of online and streaming environment.
Datasets: We use 4 large scale short-text datasets in this work. Apart from the standard short-text dataset  TMNtitle[<http://acube.di.unipi.it/TMNdataset>], we employ three other large collections of short texts that have been crawled on the Web. These three datasets are: Yahoo Questions[<https://answers.yahoo.com/>], Tweets[<http://twitter.com/>] and Nytimes Titles[<http://www.nytimes.com/>]. The details about the crawling process are described in <cit.>. We summarize several important points of the four datasets in Table <ref>. These datasets went through a preprocessing pipeline that includes tokenizing, stemming, removing stopwords, removing low-frequency words (i.e, appearing in less than 3 documents), and removing extremely short documents (less than 3 words).

Performance measure: The common performance measure to evaluate topic models is Log Predictive Probability (LPP) that measures the predictiveness and generalization of a learned model to new data. The procedure to compute this measure is introduced in <cit.>. For each dataset, we randomly divide it into two parts D_train and D_test. We only hold documents whose length is greater than 4 and randomly divide it into two parts (𝐰_1,𝐰_2) with ratio 4:1 (4 : 1 is chosen to make sure that 𝐰_2 has at least 1 term). We do inference for 𝐰_1 and estimate the probability of 𝐰_2 given 𝐰_1. In the case of BoB, we first need to convert the topic-over-biterms (distributions over biterms) to topic-over-words (distributions over words) whose conversion formula is described in Appendix <ref>. Based on these notations, LPP is computed as follows:


    LPP(𝒟_test) = ∑_d ∈𝒟_testLPP(d)/|𝒟_test|

where |𝒟_test| is the number of documents in 𝒟_test, and LPP(d) for each document d in the test set is computed by:

    LPP(d) = ∑_w ∈𝐰_2log p(w |𝐰_1, 𝒟_train)/|𝐰_2|

Here, |𝐰_2| is the number of words in 𝐰_2 and:

    p(w |𝐰_1, 𝒟_train)    ≈ p(w|π̂)
       = ∑_k^Kp(w | z = k)p(z=k |π̂) = ∑_k^Kϕ_kwπ̂_k




 §.§ Evaluation of BoB representation

In this section, we compare BoB to BoW in two tasks: topic modeling and classification. In each task, we choose different biterm thresholds to make sure that the number of generated biterms is not too large. A biterm threshold <cit.> is defined as the least value of the number of documents containing a specific biterm.  Consequently, a biterm would be removed if the number of documents containing it is less than the biterm threshold.



  §.§.§ BoB in topic modeling


Baseline Methods: We use the BoW representation as the baseline to compare with BoB due to the widespread of the application of BoW in topic modeling. 
Models in use: In order to evaluate the performance of the new representation, we run the online HDP and online LDA[We use the source code of Online LDA and Online HDP from <https://github.com/Blei-Lab>] over each dataset with various settings for each representation (i.e, BoW and BoB). At time t, the fast noisy estimates of gradient is computed by subsampling a small set of documents (called minibatch). Based on such noisy estimates, the intermediate global parameters are calculated, followed by the last step to update the global parameters with a decreasing learning rate schedule ρ_t ← (τ + t)^-κ  (κ is forgetting rate and τ is the delay).
Settings: The parameters (τ,κ) in both Online LDA and Online HDP form a grid: τ∈{1,20, 40, 60, 80, 100}, κ∈{0.6, 0.7, 0.8, 0.9}. For each combination of (τ, κ), we fix the minibatch size of 5000 for three datasets Yahoo Questions, Tweets and Nytimes Titles. For TMNtitle, the batchsize is set to 500 due to the minor size of dataset. For online HDP, we set the truncation for corpus K=100, truncation for document T = 20, η =0.01, α_0 = 1.0, and ω = 1.0. For online LDA, the number of topics K is set to 100 for the 3 datasets Yahoo, Tweets, Nytimes Titles and K=50 for TMN title. The biterm thresholds for different datasets are shown in Table <ref>.






Experimental Results: Figure <ref> and Figure <ref> show the averages (the line) and the range of 24 LPPs associated with the 24 combinations of (τ, κ) on four datasets (respectively).

Considering the online HDP model in Figure <ref>, we see that the predictive capability of online HDP with both BoB and BoW is improved in accordance with the increase of the number of learned documents for all the datasets. In every experimental scenario, the models with BoB always outperforms those with BoW significantly. In addition, we see that BoB always has better starting points than BoW across all the datasets and topic models. This implies that the models with BoW would require less training documents to converge than the models with BoW. These results overall suggest that BoB is more effective than BoW in modeling short texts with online HDP.

For the online LDA in Figure <ref>, the performance of BoB and BoW with the Tweets and Yahoo Questions datasets increase along with the number of documents being learned. Whereas, for the Nytimes Titles and textitTMNtitle, the two figures for BoB and BoW reach a peak and then decrease slightly. However, the predictive capacity of BoB always outperforms BoW for all the 24 LPPs. In addition, BoB also has better starting points than BoW, which is similar to the result of Online HDP.




  §.§.§ Evaluating BoB in supervised methods: text classification with SVM

In this part, we compare the performance of BoB and BoW in the text classification task using Support Vector Machine (SVM) <cit.>. We consider two types of weighting schemas for the terms/biterms in the documents: tf (term frequency) and tf-idf (term frequency-inverse document frequency). We also carry out the experiments that employ BoB for normal-text datasets to see the potential of BoB as a general representation for text analysis. For tf, we normalize the frequency vectors by dividing the frequencies of word/term by the length of the document. 
We use the following formula to compute tf-idf weight for BoW: 


    weight(w,d) = tf(w,d)log(N/df(w))

where w is a word in the document d, N is the corpus size, tf(w,d) is the frequency of w in d, and df(w) is the number of documents containing w in the corpus. 
For BoB, as described in Section <ref>, the tf-idf weight of biterm (w_i, w_j) is computed by weight (w_i, w_j) = min(weight (w_i), weight (w_j)).
Datasets:  For short-text datasets, we use the datasets Yahoo Questions and Nytimes Titles while the two popular datasets 20Newsgroup and Ohscal are chosen for the case of normal texts. The detailed information about  these two normal-text datasets is shown in Table  <ref>.
 

  * 20Newsgroup[<http://qwone.com/ jason/20Newsgroups/>]- example of medium texts: collection of about 20000 messages taken from 20 Usenet newsgroups. 

  *  Ohscal[<http://glaros.dtc.umn.edu/gkhome/fetch/sw/cluto/datasets.tar.gz>] - example of long texts: is subset of OHSUMED[<http://davis.wpi.edu/xmdv/datasets/ohsumed.html>]-collections of medical abstracts from MEDLINE[<https://www.medline.com>] database. 


For each dataset, we randomly divide it into five equal parts and report the accuracy of the models using 5-fold cross validation. For the SVM model, we employ the linear SVM implemented in the LIBLINEAR[<https://www.csie.ntu.edu.tw/ cjlin/libsvm/>] toolkit.

 






Settings:  For BoB, we examine different vocabulary sizes V_b regulated by changing the biterm threshold. This help to see the influence of V_b on the classifiers. Due to the large size of vocabulary in normal texts, we use high biterm thresholds to make the implementation of BoB more practical. The changing schedule of V_b is described in Table <ref> (for short texts) and Table <ref> (for normal texts). The statistics about the average lengths of the BoB document representation with respect to different biterm thresholds are described in Table <ref>.










Experimental result:

Figure <ref> and Figure <ref> show the results of classification on the 2 short-text datasets Yahoo Questions and Nytimes Titles respectively. In general, the accuracy of BoB is always higher than the accuracy of BoW for both weighting schemas tf and tf-idf. This further demonstrates the effectiveness of BoB for the problem of short text classification. We also see that the weighting schema tf-idf has better accuracy than tf in both BoB and BoW, suggesting that the global information from corpus (i.e, the document frequency) provides useful evidences for the SVM classifiers.

Figure <ref> and Figure <ref> report the classification performance on the 2 normal-text datasets for both BoB and BoW. The observation for the Ohscal dataset is very similar to the short text datasets in that BoB significantly outperforms BoW with both tf and tf-idf form for any value of biterm thresholds. Moreover, the smaller the biterm threshold is, the more biterms are kept, and the better the classification performance of BoB is. For 20Newsgroup, BoB only outperforms BoW with the weighing schema tf and is only comparable to BoW with tf-idf. Note that the average length of documents in 20Newsgroup (79.97) is greater than that of Ohscal (i.e, 60.42). These evidences suggest that BoB performs better than BoW for short and medium texts, and performs at least as well as BoW for long texts.

Execution time in BoB and BoW.
Table <ref> and <ref> report the training time for 4 datasets in classification task. For Yahoo Questions and Nytimes Titles (short text collections), execution time might not be a critical issue when we set high biterm threshold. For example, as threshold is 30, the execution time of BoB is not much higher than BoW while the performance of BoB outperforms BoW. For Ohscal (medium text collection) and 20Newsgroup (long text collection), there is a trade-off between accuracy and execution time when applying BoB. However, the models can be trained only once in practice and BoB is still a practical representation in the test time. 

Comparing Biterm with Bigram 

Bigram is a common representation method which also models two words co-occurring in a document. However, the difference between bigrams and biterms is that bigram captures the word order to capture the meaning of texts. In this part, we evaluate Bag of Biterm and Bag of Bigram when using with SVM. We conduct experiments on the two datasets: TMNTitle (short-text), and 20Newsgroup (normal-text). 

Table <ref> and Table <ref> show the size of bigram vocabulary and the number of empty docs respectively when we use different thresholds. Reminding that a bigram would be removed if the number of documents containing it is less than the the corresponding threshold. As we can see, there are many documents which are removed completely with the setting threshold equals one. Furthermore, Table <ref> shows the statistics about document frequency of bigrams, i.e., the number of bigrams appears in exactly n documents (n is the frequency). For TMNTitle (short-text data), most of the bigrams just appear in one or two documents, while in 20Newsgroup (normal-text data), there are many bigrams appearing in at least 10 docs. This shows that bigramprovide very little context information for dealing with short texts.







Figure <ref> and <ref> show the classification performance with the tf and tf-idf settings. We choose the bigram threshold setting which gains the best performance for the bigram models, i.e., threshold equals two. The performance of Bigram is worse than those of BoB in both datasets. The reason might be that bigram does not contain much co-occurrence information in short texts which is very important in topic models.









 §.§ Evaluation of BBM

In this section, we evaluate the performance of BBM on two tasks: (1) we compare HDP-B with the base HDP model with both the BoB and BoW representations, and (2) we investigate the effectiveness of LDA-B in the two contexts of online and streaming data.



  §.§.§ Evaluation of online HDP-B

In order to evaluate the effectiveness of BBM, this section compares (online) HDP-B with the primitive HDP when either BoB or BoW is used as the representation.

Baseline methods: We use the online HDP as the implementation of the base topic model HDP in this section. Online HDP is a standard method in the online environment that has been improved significantly with the BoB representation (i.e, Section <ref>).

Settings: The parameters are chosen according to those in <cit.>. In particular, the learning rate parameters τ and κ form a grid: τ∈{1, 20, 40, 60, 80, 100}, κ∈{0.6, 0.7, 0.8, 0.9}. The result is averaged over the values of the 24 LPPs associated with the 24 settings. 

Experimental Result:

The performance of the models is shown in Figure <ref>. From this figure, we can see that the online HDP-B and online HDP with the BoB representations always performs substantially better than the online HDP that utilizes BoW as the representation. Comparing online HDP-B and online HDP with the BoB representation, we see that online HDP-B is comparable to online HDP over the Tweet and NYtimes datasets, and perform much better than online HDP over the Yahoo and TMNtitle datasets when the model receives more data (i.e, the batch size increases). Note that BBM is also an efficient method for short texts due to its mechanism to reduce the size of the vocabulary for BoB, as discussed in Section <ref>. Such efficiency and effectiveness make BBM a practical method for short texts.




                                                                                                                                                                                                                                                                 


  §.§.§ Evaluation of online LDA-B

In what follows, we demonstrate the advantages of LDA-B over Biterm Topic Model (BTM) <cit.>, a state of the art model for short texts in online settings. Furthermore, we also compare the online LDA-B (OLDA-B) with the primitive which uses BoW and BoB as text representation methods. The learning algorithm for OLDA-B is described in Algorithm <ref>.
Baseline methods:


  * OBTM (Online BTM): the state-of-the-art framework for short texts that models biterms directly in the whole corpus. 

  * OLDA (Online LDA): the standard online method that is derived by applying Stochastic Variational Inference (SVI) to LDA model.

Settings: We set the number of topics K equal to 100 for Tweet, NYtimes and Yahoo, while K=50 for TMNtitle. The learning rate parameters τ and κ form a grid: τ∈{1, 20, 40, 60, 80, 100}, κ∈{0.6, 0.7, 0.8, 0.9}. The result is averaged over the values of the 24 LPPs associated with the 24 settings. The parameters for Online BTM are the best values in <cit.>
Experimental Result
The results are shown in Figure <ref>. We find that OLDA-B consistently higher than the all the baseline methods. When the batch size increases (more data is provided), the performance of OLDA-B is improved dramatically while OBTM and OLDA with BoB only have insignificant increases or remains stable. An explanation for this phenomenon is that when much more data arrives (in OBTM), the assumption of aggregating all documents into a single one makes the corpus ambiguous, and possibly affects the performance. In contrast, BBM infers and extracts latent topics at the document level, thus improving the performance when more data is received. 


  §.§.§ Evaluation of streaming LDA-B

In this part, we demonstrate the advantages of LDA-B in the context of streaming data. 
Baseline methods:
 

  * SVB (Streaming Variational Bayes)<cit.> a framework that enables LDA  to work in the streaming environment.

  * KPS (Keeping priors in Streaming Learning)<cit.> a streaming framework that incorporates the prior knowledge induced from word embedding.

These methods will function as the baselines for the proposed BBM method in this section.
BBM models for the streaming data: We consider the following two applications of BBM to the domain of streaming data, i.e, SVB-B and KPS-B. SVB-B (as in Algorithm 3) is a streaming method that is derived by applying the SVB framework <cit.> on the LDA-B model. KPS-B (as in Algorithm 4) is derived in a similar way except that the SVB framework is replaced by the KPS framework <cit.> in the process. We will compare these methods with the baselines to evaluate the effecitiveness of BBM.
Prior in use: For KPS and KPS-B, we use word embeddings as a prior knowledge. In particular, we employ the word embeddings provided by Pennington et al. (2014)[<https://nlp.stanford.edu/projects/glove/>] that was trained on 6 billion tokens of the whole Wikipedia 2014 and Gigaword 5 corpus . In KPS and KPS-B, the dimensionality of word embeddings is equal to the number of topics K, with K=100 for Tweet, NYtimes and Yahoo datasets, and K=50 for TMNtitle. We also normalize the word embeddings by the softmax function to guarantee all the dimensions are non-negative.

Settings: In these experiments, the number of topics K is set to 100 for Tweet, NYtimes and Yahoo datasets, whereas K=50 for TMNtitle. For SVB and SVB-B, the parameters are inherited from the best ones for SVB in <cit.>. In particular, both α and η are set to 0.01. For KPS and KPS-B, α is also set to 0.01, and η is set by the word embeddings.

Experimental Result

Figure <ref> shows the performance of the models for the streaming data on the four short text datasets. It is clear from the figure that that both SVB-B and KPS-B performs significantly better than all the baseline models. Furthermore, we see that when more data is provided (i.e, the batch size increases), the performance of SVB-B and KPS-B is improved dramatically while KPS only has an insignificant improvement at the beginning and remains stable afterward. It shows that BBM can improve the primitive significantly in the context of streaming. In addition, comparing SVB-B and KPS-B, we see that KPS-B almost always performs better than SVB-B, except for Twitter. One reason is that the prior might not be relevant to the corpus of social networks like Twitter. Nevertheless, it indicates that exploiting human knowledge for BBM can help to improve the performance of the models. 





Parameter sensitivity
Finally, we investigate the effects two parameters when their values are varied, i.e, the number of topics K and the batch size. Figure <ref> and <ref> show the predictive accuracy of SVB-B when regulating these two parameters. Note that in Figure <ref>, the batch size is in the range of {2500, 5000, 7500, 10000} for three datasets: NYtimes, Yahoo and Tweet, and {250, 500, 750, 1000} for TMNtitle due to the minor size of the dataset. As we can see from Figure <ref>, in general, the higher values of K yield better performance for the models than the lower values. The performance gaps between different values of K are large except for the case of the NYtimes dataset whose accuracy seems stable for different numbers of topics. One possible reason is that words used in NYtimes are often formal and restricted in a limited range of topics. In contrast, the other datasets come from social media that often involve informal texts, leading to the extended numbers of topics K.  Regarding the batch size, Figure <ref> shows that the accuracy over the four datasets is relatively stable when the batch size changes.



§ CONCLUSION & FUTURE WORKS


In this paper, we present a new representation for short text documents, called bag of biterms (BoB) and a framework for Modeling Bag of Biterms (BBM). The extensive experiments demonstrate many advantages of BoB over the traditional bag of words (BoW) representation, making BoB more suitable for short texts. In particular, BoB helps to reduce the negative effects of shortness and reinforce the context of the documents. These properties enable BoB to work well with unsupervised topic models such as LDA, HDP and supervised classification methods such as SVM for text classification. However, BoB has limitations on time and memory due to the size of the biterm vocabulary. The proposed BBM technique help to overcome these limitations by eliminating the need for the biterm vocabulary and modeling the two words of a biterm separately in the model. We introduce two implementation of BBM based on the primitive topic models LDA and HDP. The experimental results show that these  models perform substantially better than the base topic models over several short text datasets. Besides, we conduct experiments on the streaming environment that further demonstrate the benefits of BBM for the streaming data. In particular, the performance of the current streaming frameworks for topic models is improved when BBM is employed as the topic model in these frameworks. In the future, we plan to seek the applications of BBM in more domains and to investigate techniques to combine BBM with other text analysis methods beyond topic models.



This research is supported by Vingroup Innovation Foundation (VINIF) in project code VINIF.2019.DA18, and by the Office of Naval Research Global (ONRG) under Award Number N62909-18-1-2072, and  Air Force Office of Scientific Research (AFOSR), Asian Office of Aerospace Research & Development (AOARD) under Award Number 17IOA031.








ieeetr






§ SUPPLEMENTARY EXPERIMENTAL RESULT





To strengthen the experimental result in Section <ref>, we conduct some experiments with another evaluation metrics besides Log Predictive Probability (LPP), i.e., Normalized Pointwise Mutual Information (NPMI) <cit.>. We evaluate the NMI of the two models, Online HDP-B and Online LDA-B, compared with their base models using BoW and BoB. The settings and model in use are exactly the same as those in Section <ref>. We adopt the four datasets: Tweet, NYtimes, Yahoo, and TMNTitle.

Normalized Pointwise Mutual Information (NPMI): a standard metric to measure the association between a pair of discrete outcomes x and y, defined as:


    NPMI(w_i) = ∑_j^N-1logP(w_i, w_j)/P(w_i) P(w_j)/-log P(w_i, w_j)




Figure <ref> and Figure <ref> show the evaluation of these models by NPMI. Figure <ref> confirms that OHDP-B performs better than HDP in almost all of the cases. Figure <ref> shows that OLDA-B achieves better result than the other three models, while OBTM ranks behind only OLDA-B in NYtimes, Yahoo. Also, in most of the cases in both the two figures, the results of using BoW show that this representation is not suitable with short text datasets.  


§ CONVERSION OF TOPIC-OVER-BITERMS (DISTRIBUTION OVER BITERMS) TO TOPIC-OVER-WORDS (DISTRIBUTION OVER WORDS)

In BoB, after we finish training the model, we obtain topics that are multinomial distributions over biterms. We would like to convert these topic-over-biterms to the topics-over-words (i.e, distribution over words). Assume that ϕ_k is a distribution over biterms of topic k.
The procedure to perform this conversion is as follows: 

p(w_i | z=k)  = ∑_j=1^Vp(w_i,w_j | z=k) 
 = ∑_j=1^Vp(b_ij| z=k)
= ∑_j=1^Vϕ_kb_ij,

where V is the vocabulary size in BoW and b_ij is the biterm created from the pair (w_i,w_j).
As discussed in Section <ref>, in the implementation of BoB, we can merge b_ij and b_ji into b_ij with i<j. Because of the identical occurrence in every document, after finishing the training process, the value of p(b_ij| z=k) will be expectedly the same as p(b_ji| z=k). Therefore, in grouping these biterms into one, the conversion version of this implementation is:
p(w_i| z=k)  =  ∑_j=1^Vp(b_ij| z=k) = ϕ_kb_ii + 1/2∑_b: biterms contain  w_iϕ_kb



§ PARAMETERS INFERENCE FOR LDA-B



 §.§ Lower bound function

The log likelihood is bounded by the lower bound induced from the Jensen inequality:

    L = log P (β, θ, z, z̃|λ, γ, ϕ)  ≥ E_q [ log P(β, θ, z, z̃, w |η, α] - E_q [log q (β, θ, z, z̃|γ, λ, ϕ) ]


This lower bound can be written as follow:

    L    = ∑_k=1^K E_q[ log P (β_k |η_k) ] + ∑_d=1^D E_q[ log P (θ_d |α) ] +  ∑_d=1^D∑_n=1^N_d E_q[ log P (z_dn|θ_d) ] 
       + ∑_d=1^D∑_m=1^M_d E_q[ log P (z̃_dm|θ_d) ] + ∑_d=1^D∑_n=1^N_d E_q[ log P (w_dn| z_dn) ] 
       +  ∑_d=1^D∑_m=1^M_d E_q[ log P (w̃^(1)_dm, w̃^(2)_dm|z̃_dm) ]  - ∑_k=1^K E_q[ log q (β_k |λ_k) ] - ∑_d=1^D E_q[ log q (θ_d |γ_d) ] 
       - ∑_d=1^D∑_n=1^N_d E_q[ log q (z_dn|ϕ_dn) ]  - ∑_d=1^D∑_m=1^M_d E_q[ log q (z̃_dm|ϕ̃_dm)) ]

Where w̃^(1)_dm and w̃^(2)_dm denoted as the first word and second word of biterm w̃_dm. z̃_dm is the topic assignment of w̃_dm.
We can expand this equation as follows:

    E_q[ log P (β_k |η_k) ]    = logΓ( ∑_v=1^Vη_kv) - ∑_v=1^Vlog (η_kv) + ∑_v=1^V (η_kv - 1) E_q[ logβ_kv] 
       = logΓ( ∑_v=1^Vη_kv) - ∑_v=1^Vlog (η_kv) + ∑_v=1^V (η_kv - 1) ( ψ (λ_kv) - ψ(∑_u=1^Vλ_ku) ) 
     E_q[ log P (θ_d |α) ]    = logΓ( ∑_k=1^Kα_k) - ∑_k=1^Klog (α_k) + ∑_k=1^K (α_k - 1) E_q[ logθ_dk] 
       = logΓ( ∑_k=1^Kα_k) - ∑_k=1^Klog (α_k) + ∑_k=1^K (α_k - 1) ( ψ (γ_dk) - ψ(∑_j=1^Kγ_dj) ) 
      E_q[ log P (z_dn|θ_d) ]    = ∑_k=1^Kϕ_dnk E_q [logθ_dk]  = ∑_k=1^Kϕ_dnk( ψ (γ_dk) - ψ(∑_j=1^Kγ_dj) ) 
      E_q[ log P (z_dn|θ_d) ]    = ∑_k=1^Kϕ_dnk E_q [logθ_dk]  = ∑_k=1^Kϕ_dnk( ψ (γ_dk) - ψ(∑_j=1^Kγ_dj) ) 
     E_q[ log P (z̃_dm|θ_d) ]    = ∑_k=1^Kϕ̃_dmk E_q [logθ_dk] = ∑_k=1^Kϕ̃_dmk( ψ (γ_dk) - ψ(∑_j=1^Kγ_dj) ) 
     E_q [log P(w_dn|β_z_dn)]    = ∑_v=1^V I{ w_dn = v } E_q [logβ_z_dn,v ] =  ∑_v=1^V I{ w_dn = v }∑_k=1^K ϕ_dnk E_q [logβ_kv ] 
       = ∑_v=1^V ∑_k=1^K I{ w_dn = v }ϕ_dnk( ψ (λ_kv) - ψ(∑_u=1^Vλ_ku) )


    E_q[ log P (w̃^(1)_dm, w̃^(2)_dm|z̃_dm) ]    = E_q[ log P (w̃^(1)_dm|z̃_dm) ] + E_q[ log P (w̃^(2)_dm|z̃_dm) ] 
       = ∑_v=1^V ∑_k=1^K I{w̃^(1)_dm = v }ϕ̃_dmk( ψ (λ_kv) - ψ(∑_u=1^Vλ_ku) ) 
       + ∑_v=1^V ∑_k=1^K I{w̃^(2)_dm = v }ϕ̃_dmk( ψ (λ_kv) - ψ(∑_u=1^Vλ_ku) )


    E_q[ log P (β_k |λ_k) ]    = logΓ( ∑_v=1^Vλ_kv) - ∑_v=1^Vlog (λ_kv) + ∑_v=1^V (λ_kv - 1) E_q[ logβ_kv] 
       = logΓ( ∑_v=1^Vλ_kv) - ∑_v=1^Vlog (λ_kv) + ∑_v=1^V (λ_kv - 1) ( ψ (λ_kv) - ψ(∑_u=1^Vλ_ku) )


    E_q[ log P (θ_d |γ_d) ]    = logΓ( ∑_k=1^Kγ_dk) - ∑_k=1^Klog (γ_dk) + ∑_k=1^K (γ_dk - 1) E_q[ logθ_dk] 
       = logΓ( ∑_k=1^Kγ_dk) - ∑_k=1^Klog (γ_dk) + ∑_k=1^K (γ_dk - 1) ( ψ (γ_dk) - ψ(∑_j=1^Kγ_dj) ) 
     E_q[ log P (z_dn|ϕ_dn) ]    = ∑_k=1^Kϕ_dnklogϕ_dnk
     E_q[ log P (z̃_dm|ϕ̃_dm) ]    = ∑_k=1^Kϕ̃_dmklogϕ̃_dmk

Now, we can maximize the lower bound function in each dimension of the variational parameters. 


 §.§ Variation parameter λ

Choose a topic index k. Fix γ, ϕ and each λ_j for j ≠ k. We rewrite the lower bound as follow: 

    L(λ_k)    = ∑_v=1^V (η_kv - 1) ( ψ(λ_kv) - ψ( ∑_u=1^V λ_ku) ) 
        + ∑_d=1^D ∑_n=1^N_d∑_v=1^V I{w_dn = v}ϕ_dnk( ψ(λ_kv) - ψ( ∑_u=1^V λ_ku) ) 
       +  ∑_d=1^D ∑_m=1^M_d∑_b=1^Ṽ I{w̃_dm = b}ϕ̃_dmk( ψ(λ_kv) - ψ( ∑_u=1^V λ_ku) ) 
       - logΓ( ∑_v=1^V λ_kv) + ∑_v=1^V logΓ (λ_kv)- ∑_v=1^V (λ_kv - 1) ( ψ(λ_kv) - ψ( ∑_u=1^V λ_ku) ) + const


The partial derivative of L(λ_k) with respect to λ_k is:

    ∂/∂λ_kv L(λ_k)    = - ( ψ (λ_kv) - ψ( ∑_u=1^Vλ_ku) ) + ( ψ_1 (λ_kv) - ψ_1 ( ∑_u=1^V λ_ku) ) 
        . ( η_kv - λ_kv + ∑_d=1^D∑_n=1^N_d I { w_dn = v }ϕ_dnk + ∑_d=1^D∑_m=1^M_d( I {w̃_dm^(1) = v } + I{w̃_dm^(2) = v})   ϕ̃_dmk) 
       + ψ (λ_kv) - ψ( ∑_u=1^V λ_ku) + ψ_1 ( ∑_u=1^V λ_ku) 
         . ( η_kv - λ_kv + ∑_d=1^D∑_n=1^N_d I { w_dn = v }ϕ_dnk + ∑_d=1^D∑_m=1^M_d( I {w̃_dm^(1) = v } + I{w̃_dm^(2) = v})   ϕ̃_dmk)


Set the derivative of L(λ_k) to zero, we obtain:

    λ_k, v←η_k, v + ∑_d=1^D ∑_n=1^N_d I{w̃^(1)_dn = v }ϕ_dnk  + ∑_d=1^D ∑_m=1^M_d[ I{w̃^(1)_dm = v } + I{w̃^(2)_dm = v }] ϕ̃_dmk




 §.§ Variation parameter γ

Choose a document d,  fix λ, ϕ and each γ_c for c ≠ d. We rewrite the lower bound as follow:

    L(γ_d)    = ∑_k=1^K (α_k - 1) ( ψ(γ_dk) - ψ( ∑_j=1^K γ_dj) ) 
       + ( ∑_n=1^N_d∑_k=1^K ϕ_dnk + ∑_m=1^M_d∑_k=1^K ϕ̃_dmk) ( ψ(γ_dk) - ψ( ∑_j=1^K γ_dj) ) 
        - logΓ( ∑_k=1^K γ_dk) +  ∑_k=1^K logΓ(γ_dk) +  ∑_k=1^K (γ_dk - 1 ) ( ψ(γ_dk) - ψ( ∑_j=1^K γ_dj) ) + const
       = ∑_k=1^K ( α_k - γ_dk + ∑_n=1^N_dϕ_dnk + ∑_m=1^M_dϕ̃_dmk) ( ψ(γ_dk) - ψ( ∑_j=1^K γ_dj) ) 
       - logΓ( ∑_k=1^K γ_dk) +  ∑_k=1^K logΓ(γ_dk) + const


The partial derivative of L(γ_d) with respect to γ_d is:

    ∂/∂γ_dk L(γ_d)    = ψ_1 (γ_dk) ( α_k - γ_dk + ∑_n=1^N_dϕ_dnk + ∑_m=1^M_dϕ̃_dmk) 
        - ψ_1 (∑_j=1^Kγ_dj) ∑_j=1^K( α_j - γ_dj + ∑_n=1^N_dϕ_dnj + ∑_m=1^M_dϕ̃_dmj)


Set the derivative of L(γ_d) to zero, we obtain:

    γ_d, k = α_k + ∑_n=1^N_dϕ_dnk + ∑_m=1^M_dϕ̃_dmk



 §.§ Variation parameter ϕ

Fixing λ, γ, ϕ̃ and ϕ_cu for (c,u) ≠ (d,v). We rewrite the lower bound as follow:

    L(ϕ_dn) = ∑_k=1^K n_dnϕ_dnk( - logϕ_dnk + ψ (γ_dk) - ψ( ∑_j=1^K γ_dj) + ψ (λ_kw_dn) - ψ( ∑_u=1^V λ_ku)   ) + const


The partial derivative of L(ϕ_dv) with respect to ϕ_dv is:

    ∂/∂ϕ_dnk L(ϕ_dn) = n_dn( - logϕ_dnk + ψ (γ_dk) - ψ( ∑_j=1^K γ_dj) + ψ (λ_kw_dn) - ψ( ∑_u=1^V λ_ku) - 1  )


Using the Lagrange multipliers method with constraint ∑_k=1^K ϕ_dnk = 1, we obtain:

    ϕ_dnk∝ exp { E_q [logθ_d, k] + E_q[logβ_k,w_dn] }




 §.§ Variation parameter ϕ̃

Fixing λ, γ, ϕ and ϕ̃_cu for (c,u) ≠ (d,b). We rewrite the lower bound as follow:

    L(ϕ̃_db) = ∑_k=1^K m_dbϕ̃_d,b,k( - logϕ̃_d,b,k + ψ (γ_dk) - ψ( ∑_j=1^K γ_dj) + ψ (λ_kv) - ψ( ∑_b=1^V_bλ_kb)   ) + const


The partial derivative of L(ϕ̃_db) with respect to ϕ̃_db is:

    ∂/∂ϕ̃_dbk L(ϕ̃_db) = m_db( - logϕ̃_d,b,k + ψ (γ_dk) - ψ( ∑_j=1^K γ_dj) + ψ (λ_kv) - ψ( ∑_b=1^V_bλ_kb) - 1  )


Using the Lagrange multipliers method with constraint ∑_k=1^K ϕ̃_dmk = 1, we obtain:

    ϕ̃_d, m, k∝ exp { E_q[logθ_d, k] + E_q[log β_k,w_dm^(1)] + E_q[logβ_k,w_dm^(2)] }

Here we donote w̃_dm^(1) and w̃_dm^(2) as the first word and second word of biterm w̃_dm respectively.

