Sparse Parallel Training of Hierarchical D irichlet Process Topic Models (2020)

Abstract: To scale non-parametric extensions of probabilistic topic models such as Latent Dirichlet allocation to larger data sets, practitioners rely increasingly on parallel and distributed systems. In this work, we study data-parallel training for the hierarchical Dirichlet process (HDP) topic model. Based upon a representation of certain conditional distributions within an HDP, we propose a doubly sparse data-parallel sampler for the HDP topic model. This sampler utilizes all available sources of sparsity found in natural language - an important way to make computation efficient. We benchmark our method on a well-known corpus (PubMed) with 8m documents and 768m tokens, using a single multi-core machine in under four days.

## introduction topic models are a widely-used class of methods that allow practitioners to identify latent semantic themes in large bodies of text in an unsupervised manner. they are particularly attractive in areas such as history @xcite , sociology @xcite , and political science @xcite , where a desire for careful control of structure and prior information incorporated into the model motivates one to adopt a bayesian approach to learning. in these areas, large corpora such as newspaper archives are becoming increasingly available @xcite , and models such as latent dirichlet allocation (lda) @xcite and its nonparametric extensions @xcite @xcite are widely used by practitioners. moreover, these models are emerging as a component of data-efficient language models @xcite . training topic models efficiently entails two requirements. in this work, we focus on the hierarchical dirichlet process (hdp) topic model of @xcite , which we review in section 2. this model is a simple non-trivial extension of lda to the nonparametric setting. this parallel implementation provides a blueprint for designing massively parallel training algorithms in more complicated settings, such as nonparametric dynamic topic models @xcite and tree-based extensions @xcite . parallel approaches to training hdps have been previously introduced by a number of authors, including @xcite , @xcite , @xcite , @xcite and @xcite . these techniques suit various settings: some are designed to explicitly incorporate sparsity present in natural language and other discrete spaces, while others are intended for hdpbased continuous mixture models. @xcite have pointed out that some methods can suffer from load-balancing issues, which limit their parallelism and scalability. the largest benchmark of parallel hdp training performed to our awareness is by @xcite on the 100m-token nytimes corpora. throughout this work, we focus on markov chain monte carlo (mcmc) methods-empirically, their scalability is comparable to variational methods @xcite , and, subject to convergence, they yield the correct posterior. our contributions are as follows. we propose an augmented representation of the hdp for which the topic indicators can be sampled in parallel over documents. we prove that, under this representation, the global topic distribution ψ is conditionally conjugate given an auxiliary parameter l. we develop symbol description symbol description v vocabulary size ψ : 1 × ∞ global distribution over topics d total number of documents θ : d × ∞ document-topic probabilities n total number of tokens θ d : 1 × ∞ topic probabilities for document d v(i) word type for token i m : d × ∞ document-topic sufficient statistic d(i) document for token i φ : ∞ × v topic-word probabilities w i,d global topic draw indicator for w i,d n : ∞ × v topic-word sufficient statistic z i,d topic indicator for token i in d l : 1 × ∞ global topic latent sufficient statistic k * index for implicitly-represented topics α, β, γ prior concentration for θ d , φ k , ψ ## partially collapsed gibbs sampling for hierarchical dirichlet processes the hierarchical dirichlet process topic model @xcite begins with a global distribution ψ over topics. documents are assumed exchangeable-for each document d, the associated topic distribution θ d follows a dirichlet process centered at ψ. each topic is associated with a distribution of tokens φ k . within each document, tokens are assumed exchangeable (bag of words) and assigned to topic indicators z i,d . for given data, we observe the tokens w i,d . we thus arrive at the gem representation of a hdp, given by equation ( 19 ) of @xcite as ## performance results to study performance of the partially collapsed sampler-algorithm 2-we implemented it in java using the open-source mallet foot_0 (mccallum, 2002) topic modeling framework. we ran it on the ap, cgcbib, neurips, and pubmed corpora, 1 which are summarized in to assess algorithm 2 in a small-scale setting, we compare it to the widely-studied sparse fully collapsed direct assignment sampler of @xcite , which is not parallel. we ran 100 000 iterations of both methods on ap and cgcbib. we selected these corpora because they were among the larger corpora on which it was feasible to run our direct assignment reference implementation within one week. trace plots for the log marginal likelihood for z given ψ and the number of active topics, i.e., those topics assigned at least one token, can be seen in figure 1(a , d ) and figure 1(b , e ), respectively. the direct assignment algorithm converges slower, but achieves a slightly better local optimum in terms of marginal log-likelihood, compared to our method. this fact indicates that the direct assignment method may stabilize around a different local optimum, and may represent a potential limitation of the partially collapsed sampler in settings where non-parallel methods are practical. to better understand the distributional differences between the algorithms, we examined the number of tokens per topic, which can be seen in figure 1(c , f ). the partially collapsed sampler is seen to assign more tokens to smaller topics, indicating that it stabilizes around a local optimum with slightly broader semantic themes. to visualize the effect this has on the topics, we examined the most common words for each topic. since the algorithms generate too many topics to make full examination practical, we instead compute a quantile summary with five topics per quantile. the quantile is computed by ranking all topics by the number of tokens, choosing the five closest topics to the 100%, 75%, 50%, 25%, and 5% quantiles in the ranking, and computing their top words. this approach gives a representative view of the algorithm's output for large, medium, and small topics. results may be seen in appendix d and appendix c-we find the direct assignment and partially collapsed samplers to be mostly comparable, with substantial overlap in top words for common topics. next, we assess algorithm 2 in a more demanding setting and compare against previous parallel state-of-the-art. there are various scalable samplers available for the hdp. for a fair comparison, we restrict ourselves to those samplers designed for topic models and explicitly incorporate sparsity of natural language in their construction. among these, we selected the parallel subcluster splitmerge algorithm of @xcite as our baseline because it was used in the largest-scale benchmark of the hdp topic model performed to date to our awareness, and shows comparable performance to other methods @xcite . the subcluster split-merge algorithm is designed to converge with fewer iterations, but is more costly to run per iteration. thus, we used a fixed computational budget of 24 hours of wall-clock time for both algorithms. computation was performed on a system with a 4-core 8-thread cpu and 8gb ram. results can be seen in figure 1 (g)-note that the subcluster split-merge algorithm is parametrized using sub-topic indicators and sub-topic probabilities, so its numerical log-likelihood values are not directly comparable to ours and should be interpreted purely to assess convergence. algorithm 2 stabilizes much faster with respect to both the number of active topics in figure 1 (g), and marginal log-likelihood in figure 1(h ). the subcluster splitmerge algorithm adds new topics one-at-a-time, whereas our algorithm can create multiple new topics per iteration-we hypothesize this difference leads to faster convergence for algorithm 2. in figure 1 (i), we observe that the amount of computing time per iteration increases substantially for the subcluster split-merge method as it adds more topics. for algorithm 2, this stays approximately constant for its entire runtime. to evaluate the topics produced by the algorithms, we again examined the most common words for each topic via a quantile summary, given in appendix e. we find the subcluster split-merge algorithm appears to generate topics with slightly more semantic overlap compared to algorithm 2, but otherwise produces comparable output. finally, to assess scalability, we ran 25 000 iterations of algorithm 2 on pubmed, which contains 768m tokens. to our knowledge, this dataset is an order of magnitude larger than any datasets used in previous mcmc-based approaches for the hdp. computation was performed on a compute node with 2x10-core cpus with 20 threads and 64gb of ram. the marginal likelihood and number of active topics are given in figure 1 (j) and figure 1(k) . to evaluate the topics discovered by the algorithm, we examined their most common wordsthese may be seen in full in appendix f. we observe that the semantic themes present in the topics vary according to how many tokens they have: topics with more tokens appear to be broader, whereas topics with fewer tokens appear to be more specific. this behavior illustrates a key difference between the hdp and methods like lda, which do not contain a learned global topic distribution ψ in their formulation. we suspect the effect is particularly pronounced on pubmed compared to cgcbib and neurips due to its large number of tokens. ## discussion in this work, we introduce the parallel partially collapsed gibbs sampler-algorithm 1-for the hdp topic model, which converges to the correct target distribution. we propose a doubly sparse approximate sampler-algorithm 2-which allows the hdp to be implemented with per-token sampling complexity of o min k (m) these improvements allow us to train the hdp on larger corpora. the data-parallel nature of our approach means that the amount of available parallelism increases with data size. this parallelism avoids load-balancing-related scalability limitations pointed out by @xcite . nonparametric topic models are less straightforward to evaluate empirically than ordinary topic models. in particular, we found topic coherence scores @xcite to be strongly affected by the number of active topics k, which causes preference for models with fewer topics and more the hdp posterior is a heavily multimodal target for which full posterior exploration is known to be difficult @xcite @xcite , and sampling schemes are generally used more in the spirit of optimization than traditional mcmc. these issues are mirrored in other approaches, such as variational inference. there, restrictive meanfield factorization assumptions are often required, which reduces the quality of discovered topics. we view map-based analogs of ideas presented here as a promising direction, since these may allow additional flexibility that may enable faster training. many of the ideas in this work, such as the binomial trick, are generic and apply to any topic model structurally similar to the hdp's gem representation @xcite given in section 2. for example, one could consider an informative prior for ψ in lieu of gem(γ), potentially improving convergence and topic quality, or developing parallel schemes for other nonparametric topic models such as pitman-yor models @xcite , tree-based models @xcite , embedded topic models @xcite , as well as nonparametric topic models used within data-efficient language models @xcite in future work.