Local Topic Discovery via Boosted Ensemble of Nonnegative Matrix Factorization

1 Introduction

Until recently, the main focus of the two major topic modeling approaches-i.e., probabilistic and matrix factorization methods-has been to find a given number of bases or probability distributions, which we call topics, over the dictionary so that they can explain a given set of documents. Most of the existing topic modeling methods focus on generating global topics to explain the majority of a given document corpus. However, such topics do not often provide meaningful information and are sometimes even redundant with each other when multiple similar topics are dominant in the corpus.

For instance, Fig. 1 shows the sample topics generated by existing algorithms and our proposed method called LEnsNMF, using Twitter dataset collected from New York City. Clearly, the keywords found by the baseline methods are shown to be general but not informative-see words, such as 'lol,' 'wow,' 'great,' and 'hahah.' On the contrary, our method, which attempts to discover local topics returns specific and insightful keywords, e.g., 'ireland,' 'survive,' and

1 This paper is an abridged version of an already published paper [Suh et al., 2016], invited to IJCAI'17 Sister Conferences track for a broader audience.

'hurricane sandi'-which devastated New York City in 2012. Searching for 'ireland hurricane sandy' on the web, we discovered the local news that the Ireland football team visited New York in June 2013 to support a community hit by Hurricane Sandy. Moreover, 'hurricane sandi' were not found in any of the 100 topics (ten keywords each) generated by any existing methods, showing that a local topic discovery approach does not only enhance topic quality but also allows the discovery of potentially meaningful topics that would otherwise be left undiscovered.

In response, this paper proposes a local ensemble model of nonnegative matrix factorization (NMF) [Lee and Seung, 1999]. Although NMF has been used previously in the ensemble framework in machine learning applications, including clustering [Greene et al., 2008], classification [Wu et al., 2015], and bioinformatics [Yang et al., 2014], most of these existing ensemble methods primarily focus on aggregating the outputs from multiple individual models constructed independently with some variations on input matrices and other parameter settings. Thus, they are not applicable in topic modeling where we focus on the learned bases themselves. Furthermore, none of them have tackled the idea of constructing an ensemble of NMF models based on a gradient boosting framework, which grants a clear novelty of our work. TFIDF is also known to work reasonably well for what our approach aims to achieve, i.e., down-weighting general, redundant words and up-weighting infrequent, specific words in a document corpus. However, TF-IDF can distort the semantic coherence of each topic, and thus it is not used much in the context of topic modeling.

Overall, the main contributions of this paper are as follows:

• A novel ensemble of nonnegative matrix factorization method based on a gradient boosting framework.
• An extensive quantitative analysis with various document datasets, showing the superiority of our method.

2 NMF for Topic Modeling

Given a nonnegative matrix X ∈ Rm×n + , and an integer k ≪ min (m, n), nonnegative matrix factorization (NMF) [Lee and Seung, 1999] finds a lower-rank approximation given by

where W ∈ Rm×k + and H ∈ Rk×n + are nonnegative factors. NMF is typically formulated in terms of the Frobenius norm as

where '≥' applies to every element of the given matrix in the left-hand side. In topic modeling, xi ∈ Rm×1 + , the i-th column of X, corresponds to the bag-of-words representation of document i with respect to m keywords. k denotes the number of topics. wl ∈ Rm×1 + , the l-th nonnegative column vector of W, represents the l-th topic as a weighted combination of m keywords. The i-th column vector of H, hi ∈ Rk×1 + , represents document i as a weighted combination of k topics.

3 L-EnsNMF for Local Topic Modeling

We propose our gradient-boosted local ensemble NMF approach called L-EnsNMF. 2 As shown in Fig. 2, L-EnsNMF iteratively performs three steps, residual update, anchor sampling, and local weighting. In this ensemble model, an individual learner corresponds to NMF. That is, given a nonnegative matrix X ∈ Rm×n + , we learn an additive model ˆX(q) with q products W (i)H(i) :

where W (i) ∈ Rm×ks + , H(i) ∈ Rks×n + and q is the number of individual learners. In other words, the i-th stage represents a local NMF model discovering the i-th set of ks local topics. To achieve this approximation, we use the Frobenius normbased objective function as follows:

Residual Update. L-EnsNMF solves this problem in a forward stage-wise manner [Hastie et al., 2009], which iteratively adds a new local model to better approximate X, fitting the i-th local NMF, W (i)H(i) , with rank ks to the localized residual, i.e., the unexplained portion from previously learned i - 1 local models. To this end, we define the (non-localized) nonnegative residual matrix at stage i as

2 The code is available at https://github.com/ sanghosuh/lens_nmf-matlab

where [·]+ is an operator that converts every negative element in the matrix to zero.

Anchor Sampling. Next, we use P (i) r and P (i) c to assign higher weights to those rows or columns less explained (large residuals) by previous stages. Let us define the probability distributions P (i) r and P (i) c over row indices, x's, and over column indices, y's, respectively, as

In the above equations, higher probability values are assigned to those rows or columns with larger values in residual matrix R(i) . That is, a higher probability indicates that the corresponding row or column is less explained up to the previous stage. As illustrated in Fig. 2(b), we sample from this probability distribution a single row ar and a column ac, which we call an anchor point, which corresponds to a particular keyword and a document that were not yet sufficiently explained in previous stages, respectively.

Local Weighting. We then apply local weighting on the residual matrix R(i) to obtain its localized version R(i) L . Given a local residual matrix R(i) L at stage i, we obtain the term-by-topic matrix ˆW (i) and the topic-by-document matrix ˆH(i) by solving

Here, the localized residual matrix R(i) L is formed as

where diagonal matrices D(i) r ∈ Rm×m + and D(i) c ∈ Rn×n + perform row- and column-wise scaling, respectively, as shown in Fig. 2(c).

The diagonal entries of D(i) r and D(i) c are computed based on the similarity of each row and column to the anchor row ar and column ac, respectively. Specifically, given the selected ar and ac, we use the cosine similarity to compute the l-th diagonal entry of D(i) r (l, l) and the s-th diagonal entry of

D(i)

c (s, s), respectively, as

After formulating the localized residual matrix as described above, we use R(i) L (Eq. (9)) as an input matrix for NMF and obtain W (i) and H(i) , as in Eq. (8). When computing the residual matrix in the next stage using W (i) and H(i) , as shown in Eq. (5), however, it may end up removing only the fraction of the residuals, which can be significantly smaller than the unweighted residuals since all the weights are less than or equal to 1. To adjust this shrinking effect caused by local weighting, we recompute H(i) using the given W (i) and the non-weighted residual matrix R(i) , i.e.,

In this manner, our approach still maintains the localized topics W (i) from R(i) L while properly subtracting the full portions explained by these topics fromR(i) for the next stage.

Fast Rank-2. In addition to the novel local weighting scheme, we apply a recently proposed, highly efficient NMF algorithm based on an active-set method [Kuang and Park, 2013] for a small rank value.

4 Experiments

We selected the following five real-world document datasets: 1) Reuters-21578 (Reuters), 3 2) 20 Newsgroups (20News), 4 3) Enron, 5 4) IEEE-Vis (VisPub), 6 and 5) Twitter, as summarized in Table 1.

Using these datasets, we compared our L-EnsNMF against various state-of-the-art methods, including standard NMF (StdNMF) [Kim et al., 2014], 7 sparse NMF (SprsNMF) [Kim and Park, 2007], 8 orthogonal NMF (OrthNMF) [Ding et al., 2006], 9 and latent Dirichlet allocation (LDA) [Blei et al., 2003]. 10 In most of these methods, we used default parameter values provided by the corresponding software library.

All the experiments were conducted using MATLAB 8.5 (R2015a) on a desktop computer with dual Intel Xeon E52687W processors.

4.1 Quantitative Analysis

Total Document Coverage. This measure computes how many documents (out of the entire document set) can be explained by a given set of topics. Here, a document is said to be "explained" if there exists a topic such that at least a certain number of keywords among its most representative keywords are found in that document. In Table 2, our method is shown to be the best or the second best method for all the different numbers of topics.

3 https://kdd.ics.uci.edu/databases/ reuters21578/reuters21578.html

4 http://qwone.com/˜jason/20Newsgroups/

5 https://www.cs.cmu.edu/˜./enron/

6 http://www.vispubdata.org/site/vispubdata/ 7 https://github.com/kimjingu/

nonnegfac-matlab

8 http://www.cc.gatech.edu/˜hpark/software/ nmf_bpas.zip

9 http://davian.korea.ac.kr/myfiles/list/ Codes/orthonmf.zip

10 http://psiexp.ss.uci.edu/research/ programs_data/toolbox.htm

Topic Coherence. Fig. 3 shows how the topic coherence values change as the stages proceed in our ensemble model. One can see that the topic coherence is constantly improved as the stages proceed, which generates topics with much better quality than other methods. This supports our claim that the gradient boosting-based ensemble framework for NMF works well in topic modeling applications and that the topics generated in later stages in this framework have significant advantages than those generated by other existing methods.

Computing Times. We measured the running time of different methods by changing the total number of topics, k, from 2 to 50. In the case of our ensemble NMF method, we fixed ks as 2 while changing q from 1 to 25. As shown in Fig. 4, our method runs fastest, and more importantly, it scales better than other methods with respect to k since its computational complexity, i.e., ks, stays constant at 2 regardless of the total number of topics.

5 FutureWork

We plan to expand our work to an interactive topic discovery system [Choo et al., 2013; Kim et al., 2017] by flexibly steering the local weighting process in a user-driven manner so that the subsequent topics can properly reflect a user's subjective interest and task goals.

Acknowledgments. This work was supported in part by the National Science Foundation grants IIS-1707498, IIS-1619028, IIS1646881 and by Basic Science Research Program through the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2016R1C1B2015924). Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of funding agencies.