Augment-and-Conquer Negative Binomial Processes

Mingyuan Zhou, Lawrence Carin

Introduction

There has been increasing interest in count modeling using the Poisson process, geometric process and recently the negative binomial (NB) process . Notably, it has been independently shown in and that the NB process, originally constructed for count analysis, can be naturally applied for mixture modeling of grouped data $\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{J}$ , where each group $\boldsymbol{x}_{j}=\{x_{ji}\}_{i=1,N_{j}}$ . For a territory long occupied by the hierarchical Dirichlet process (HDP) and related models, the inference of which may require substantial bookkeeping and suffer from slow convergence , the discovery of the NB process for mixture modeling can be significant. As the seemingly distinct problems of count and mixture modeling are united under the NB process framework, new opportunities emerge for better data fitting, more efficient inference and more flexible model constructions. However, neither nor explore the properties of the NB distribution deep enough to achieve fully tractable closed-form inference. Of particular concern is the NB dispersion parameter, which was simply fixed or empirically set , or inferred with a Metropolis-Hastings algorithm . Under these limitations, both papers fail to reveal the connections of the NB process to the HDP, and thus may lead to false assessments on comparing their modeling abilities.

We perform joint count and mixture modeling under the NB process framework, using completely random measures that are simple to construct and amenable for posterior computation. We propose to augment-and-conquer the NB process: by “augmenting” a NB process into both the gamma-Poisson and compound Poisson representations, we “conquer” the unification of count and mixture modeling, the analysis of fundamental model properties, and the derivation of efficient Gibbs sampling inference. We make two additional contributions: 1) we construct a gamma-NB process, analyze its properties and show how its normalization leads to the HDP, highlighting its unique theoretical, structural and computational advantages relative to the HDP. 2) We show that a variety of NB processes can be constructed with distinct model properties, for which the shared random measure can be selected from completely random measures such as the gamma, beta, and beta-Bernoulli processes; we compare their performance on topic modeling, a typical example for mixture modeling of grouped data, and show the importance of inferring both the NB dispersion and probability parameters, which respectively govern the overdispersion level and the variance-to-mean ratio in count modeling.

Before introducing the NB process, we first illustrate how the seemingly distinct problems of count and mixture modeling can be united under the Poisson process. Denote $\Omega$ as a measure space and for each Borel set $A\subset\Omega$ , denote $X_{j}(A)$ as a count random variable describing the number of observations in $\boldsymbol{x}_{j}$ that reside within $A$ . Given grouped data $\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{J}$ , for any measurable disjoint partition $A_{1},\cdots,A_{Q}$ of $\Omega$ , we aim to jointly model the count random variables $\{X_{j}(A_{q})\}$ . A natural choice would be to define a Poisson process $X_{j}\sim\mbox{PP}(G)$ , with a shared completely random measure $G$ on $\Omega$ , such that $X_{j}(A)\sim\mbox{Pois}\big{(}G(A)\big{)}$ for each $A\subset\Omega$ . Denote $G(\Omega)=\sum_{q=1}^{Q}G(A_{q})$ and $\widetilde{G}=G/G(\Omega)$ . Following Lemma 4.1 of , the joint distributions of $X_{j}(\Omega),X_{j}(A_{1}),\cdots,X_{j}(A_{Q})$ are equivalent under the following two expressions:

Thus the Poisson process provides not only a way to generate independent counts from each $A_{q}$ , but also a mechanism for mixture modeling, which allocates the observations into any measurable disjoint partition $\{A_{q}\}_{1,Q}$ of $\Omega$ , conditioning on $X_{j}(\Omega)$ and the normalized mean measure $\widetilde{G}$ .

To complete the model, we may place a gamma process prior on the shared measure as $G\sim\mbox{GaP}(c,G_{0})$ , with concentration parameter $c$ and base measure $G_{0}$ , such that $G(A)\sim\mbox{Gamma}(G_{0}(A),1/c)$ for each $A\subset\Omega$ , where $G_{0}$ can be continuous, discrete or a combination of both. Note that $\widetilde{G}=G/G(\Omega)$ now becomes a Dirichlet process (DP) as $\widetilde{G}\sim\mbox{DP}(\gamma_{0},\widetilde{G}_{0})$ , where $\gamma_{0}=G_{0}(\Omega)$ and $\widetilde{G}_{0}=G_{0}/\gamma_{0}$ . The normalized gamma representation of the DP is discussed in and has been used to construct the group-level DPs for an HDP . The Poisson processhas an equal-dispersion assumption for count modeling. As shown in (2), the construction of Poisson processes with a shared gamma process mean measure implies the same mixture proportions across groups, which is essentially the same as the DP when used for mixture modeling when the total counts $\{X_{j}(\Omega)\}_{j}$ are not treated as random variables. This motivates us to consider adding an additional layer or using a different distribution other than the Poisson to model the counts. As shown below, the NB distribution is an ideal candidate, not only because it allows overdispersion, but also because it can be augmented into both a gamma-Poisson and a compound Poisson representations.

Augment-and-Conquer the Negative Binomial Distribution

The NB distribution $m\sim\mbox{NB}(r,p)$ has the probability mass function (PMF) $f_{M}(m)=\frac{\Gamma(r+m)}{m!\Gamma(r)}(1-p)^{r}p^{m}$ . It has a mean $\mu={rp}/(1-p)$ smaller than the variance $\sigma^{2}={rp}/{(1-p)^{2}}=\mu+r^{-1}\mu^{2}$ , with the variance-to-mean ratio (VMR) as $(1-p)^{-1}$ and the overdispersion level (ODL, the coefficient of the quadratic term in $\sigma^{2}$ ) as $r^{-1}$ . It has been widely investigated and applied to numerous scientific studies . The NB distribution can be augmented into a gamma-Poisson construction as $m\sim\mbox{Pois}(\lambda),~{}\lambda\sim\mbox{Gamma}\left(r,{p}/{(1-p)}\right)$ , where the gamma distribution is parameterized by its shape $r$ and scale $p/(1-p)$ . It can also be augmented under a compound Poisson representation as $m=\sum_{{t}=1}^{l}u_{{t}},~{}u_{{t}}\sim\mbox{Log}(p),~{}l\sim\mbox{Pois}(-r\ln(1-p))$ , where $u\sim\mbox{Log}(p)$ is the logarithmic distribution with probability-generating function (PGF) $C_{U}(z)={\ln(1-pz)}/{\ln(1-p)},~{}~{}|z|<{p^{-1}}.$ In a slight abuse of notation, but for added conciseness, in the following discussion we use $m\sim\sum_{t=1}^{l}\mbox{Log}(p)$ to denote $m=\sum_{{t}=1}^{l}u_{{t}},~{}u_{{t}}\sim\mbox{Log}(p)$ .

The inference of the NB dispersion parameter $r$ has long been a challenge . In this paper, we first place a gamma prior on it as $r\sim\mbox{Gamma}(r_{1},1/c_{1})$ . We then use Lemma 2.1 (below) to infer a latent count $l$ for each $m\sim\mbox{NB}(r,p)$ conditioning on $m$ and $r$ . Since $l\sim\mbox{Pois}(-r\ln(1-p))$ by construction, we can use the gamma Poisson conjugacy to update $r$ . Using Lemma 2.2 (below), we can further infer an augmented latent count $l^{\prime}$ for each $l$ , and then use these latent counts to update $r_{1}$ , assuming $r_{1}\sim\mbox{Gamma}(r_{2},1/c_{2})$ . Using Lemmas 2.1 and 2.2, we can continue this process repeatedly, suggesting that we may build a NB process to model data that have subgroups within groups. The conditional posterior of the latent count $l$ was first derived by us but was not given an analytical form . Below we explicitly derive the PMF of $l$ , shown in (3), and find that it exactly represents the distribution of the random number of tables occupied by $m$ customers in a Chinese restaurant process with concentration parameter $r$ . We denote $l\sim\mbox{CRT}(m,r)$ as a Chinese restaurant table (CRT) count random variable with such a PMF and as proved in the supplementary material, we can sample it as $l=\sum_{n=1}^{m}b_{n},~{}b_{n}\sim\mbox{Bernoulli}\left({r}/(n-1+r)\right)$ .

Both the gamma-Poisson and compound-Poisson augmentations of the NB distribution and Lemmas 2.1 and 2.2 are key ingredients of this paper. We will show that these augment-and-concur methods not only unite count and mixture modeling and provide efficient inference, but also, as shown in Section 3, let us examine the posteriors to understand fundamental properties of the NB processes, clearly revealing connections to previous nonparametric Bayesian mixture models.

Denote $s(m,j)$ as Stirling numbers of the first kind . Augment $m\sim\emph{\mbox{NB}}(r,p)$ under the compound Poisson representation as $m\sim\sum_{{t}=1}^{l}\emph{\mbox{Log}}(p),~{}l\sim\emph{\mbox{Pois}}(-r\ln(1-p))$ , then the conditional posterior of $l$ has PMF

Denote $w_{j}\sim\sum_{{t}=1}^{j}\mbox{Log}(p)$ , $j=1,\cdots,m$ . Since $w_{j}$ is the summation of $j$ iid $\mbox{Log}(p)$ random variables, the PGF of $w_{j}$ becomes $C_{W_{j}}(z)=C_{U}^{j}(z)=\left[{\ln(1-pz)}/{\ln(1-p)}\right]^{j},~{}|z|<{p^{-1}}$ . Using the property that $[\ln(1+x)]^{j}=j!\sum_{n=j}^{\infty}\frac{s(n,j)x^{n}}{n!}$ , we have $\mbox{Pr}(w_{j}=m)={C_{W_{j}}^{(m)}(0)}/{m!}=(-1)^{m}p^{j}j!s(m,j)/(m![\ln(1-p)]^{j}).$ Thus for $0\leq j\leq m$ , we have $\mbox{Pr}(L=j|m,r)\propto\mbox{Pr}(w_{j}=m)\mbox{Pois}(j;-r\ln(1-p))\propto|s(m,j)|r^{j}.$ Denote $S_{r}(m)=\sum_{j=0}^{m}|s(m,j)|r^{j}$ , we have $S_{r}(m)=(m-1+r)S_{r}(m-1)=\cdots=\prod_{n=1}^{m-1}(r+n)S_{r}(1)=\prod_{n=0}^{m-1}(r+n)=\frac{\Gamma(m+r)}{\Gamma(r)}$ . ∎

Let $m\sim\emph{\mbox{NB}}(r,p),~{}r\sim\emph{\mbox{Gamma}}(r_{1},1/c_{1})$ , denote $p^{\prime}=\frac{-\ln(1-p)}{c_{1}-\ln(1-p)}$ , then $m$ can also be generated from a compound distribution as

Augmenting $m$ leads to $m\sim\sum_{{t}=1}^{l}{\mbox{Log}}(p),~{}l\sim{\mbox{Pois}}(-r\ln(1-p))$ . Marginalizing out $r$ leads to $l\sim{\mbox{NB}}\left(r_{1},p^{\prime}\right)$ . Augmenting $l$ using its compound Poisson representation leads to (4). ∎

Gamma-Negative Binomial Process

We explore sharing the NB dispersion across groups while the probability parameters are group dependent. We define a NB process $X\sim\mbox{NBP}(G,p)$ as $X(A)\sim\mbox{NB}(G(A),p)$ for each $A\subset\Omega$ and construct a gamma-NB process for joint count and mixture modeling as $X_{j}\sim\mbox{NBP}(G,p_{j}),~{}G\sim\mbox{GaP}(c,G_{0})$ , which can be augmented as a gamma-gamma-Poisson process as

In the above PP( $\cdot$ ) and GaP( $\cdot$ ) represent the Poisson and gamma processes, respectively, as defined in Section 1.1. Using Lemma 2.2, the gamma-NB process can also be augmented as

These three augmentations allow us to derive a sequence of closed-form update equations for inference with the gamma-NB process. Using the gamma Poisson conjugacy on (5), for each $A\subset\Omega$ , we have $\Lambda_{j}(A)|G,X_{j},p_{j}\sim\mbox{Gamma}\left(G(A)+X_{j}(A),p_{j}\right)$ , thus the conditional posterior of $\Lambda_{j}$ is

Define $T\sim\mbox{CRTP}(X,G)$ as a CRT process that $T(A)=\sum_{\omega\in A}T(\omega),~{}T(\omega)\sim\mbox{CRT}(X(\omega),G(\omega))$ for each $A\subset\Omega$ . Applying Lemma 2.1 on (6) and (7), we have

If $G_{0}$ is a continuous base measure and $\gamma_{0}=G_{0}(\Omega)$ is finite, we have $G_{0}(\omega)\rightarrow 0$ $\forall~{}\omega\in\Omega$ and thus

which is equal to $K^{+}$ , the total number of used discrete atoms; if $G_{0}$ is discrete as $G_{0}=\sum_{k=1}^{K}\frac{\gamma_{0}}{K}\delta_{\omega_{k}}$ , then $L^{\prime}(\omega_{k})=\mbox{CRT}(L(\omega_{k}),\frac{\gamma_{0}}{K})\geq 1$ if $\sum_{j}X_{j}(\omega_{k})>0$ , thus $L^{\prime}(\Omega)\geq K^{+}$ . In either case, let $\gamma_{0}\sim{\mbox{Gamma}}(e_{0},1/f_{0})$ , with the gamma Poisson conjugacy on (6) and (7), we have

Since the data $\{x_{ji}\}_{i}$ are exchangeable within group $j$ , the predictive distribution of a point $X_{ji}$ , conditioning on $X_{j}^{-i}=\{X_{jn}\}_{n:n\neq i}$ and $G$ , with $\Lambda_{j}$ marginalized out, can be expressed as

Using the equivalence between (1) and (2) and normalizing all the gamma processes in (5), denoting $\widetilde{\Lambda}_{j}={\Lambda_{j}}/\Lambda_{j}(\Omega)$ , $\alpha=G(\Omega)$ , $\widetilde{G}=G/\alpha$ , $\gamma_{0}=G_{0}(\Omega)$ and $\widetilde{G}_{0}=G_{0}/\gamma_{0}$ , we can re-express (5) as

which is an HDP . Thus the normalized gamma-NB process leads to an HDP, yet we cannot return from the HDP to the gamma-NB process without modeling $X_{j}(\Omega)$ and $\Lambda_{j}(\Omega)$ as random variables. Theoretically, they are distinct in that the gamma-NB process is a completely random measure, assigning independent random variables into any disjoint Borel sets $\{A_{q}\}_{1,Q}$ of $\Omega$ ; whereas the HDP is not. Practically, the gamma-NB process can exploit conjugacy to achieve analytical conditional posteriors for all latent parameters. The inference of the HDP is a major challenge and it is usually solved through alternative constructions such as the Chinese restaurant franchise (CRF) and stick-breaking representations . In particular, without analytical conditional posteriors, the inference of concentration parameters $\alpha$ and $\gamma_{0}$ is nontrivial and they are often simply fixed . Under the CRF metaphor $\alpha$ governs the random number of tables occupied by customers in each restaurant independently; further, if the base probability measure $\widetilde{G}_{0}$ is continuous, $\gamma_{0}$ governs the random number of dishes selected by tables of all restaurants. One may apply the data augmentation method of to sample $\alpha$ and $\gamma_{0}$ .However, if $\widetilde{G}_{0}$ is discrete as $\widetilde{G}_{0}=\sum_{k=1}^{K}\frac{1}{K}\delta_{\omega_{k}}$ , which is of practical value and becomes a continuous base measure as $K\rightarrow\infty$ , then using the method of to sample $\gamma_{0}$ is only approximately correct, which may result in a biased estimate in practice, especially if $K$ is not large enough. By contrast, in the gamma-NB process, the shared gamma process $G$ can be analytically updated with (12) and $G(\Omega)$ plays the role of $\alpha$ in the HDP, which is readily available as

and as in (11), regardless of whether the base measure is continuous, the total mass $\gamma_{0}$ has an analytical gamma posterior whose shape parameter is governed by $L^{\prime}(\Omega)$ , with $L^{\prime}(\Omega)=K^{+}$ if $G_{0}$ is continuous and finite and $L^{\prime}(\Omega)\geq K^{+}$ if $G_{0}=\sum_{k=1}^{K}\frac{\gamma_{0}}{K}\delta_{\omega_{k}}$ . Equation (15) also intuitively shows how the NB probability parameters $\{p_{j}\}$ govern the variations among $\{\widetilde{\Lambda}_{j}\}$ in the gamma-NB process. In the HDP, $p_{j}$ is not explicitly modeled, and since its value becomes irrelevant when taking the normalized constructions in (14), it is usually treated as a nuisance parameter and perceived as $p_{j}=0.5$ when needed for interpretation purpose. Fixing $p_{j}=0.5$ is also considered in to construct an HDP, whose group-level DPs are normalized from gamma processes with the scale parameters as $\frac{p_{j}}{1-p_{j}}=1$ ; it is also shown in that improved performance can be obtained for topic modeling by learning the scale parameters with a log Gaussian process prior. However, no analytical conditional posteriors are provided and Gibbs sampling is not considered as a viable option .

2 Augment-and-conquer inference for joint count and mixture modeling

where marginally we have $n_{jk}\sim\mbox{NB}(r_{k},p_{j})$ . Using the equivalence between (1) and (2), we can equivalently express $N_{j}$ and $n_{jk}$ in the above model as $N_{j}\sim\mbox{Pois}\left(\lambda_{j}\right),~{}[n_{j1},\cdots,n_{jK}]\sim\mbox{Mult}\left(N_{j};{\lambda_{j1}}/{\lambda_{j}},\cdots,{\lambda_{jK}}/{\lambda_{j}}\right)$ , where $\lambda_{j}=\sum_{k=1}^{K}\lambda_{jk}$ . Since the data $\{x_{ji}\}_{i=1,N_{j}}$ are fully exchangeable, rather than drawing $[n_{j1},\cdots,n_{jK}]$ once, we may equivalently draw the index

for each $x_{ji}$ and then let $n_{jk}=\sum_{i=1}^{N_{j}}\delta(z_{ji}=k)$ . This provides further insights on how the seemingly disjoint problems of count and mixture modeling are united under the NB process framework. Following (8)-(12), the block Gibbs sampling is straightforward to write as

which has similar computational complexity as that of the direct assignment block Gibbs sampling of the CRF-HDP . If $g_{0}(\omega)$ is conjugate to the likelihood $F(x;\omega)$ , then the posterior $p(\omega|-)$ would be analytical. Note that when $K\rightarrow\infty$ , we have $(l^{\prime}_{k}|-)=\delta(\sum_{j}l_{jk}>0)=\delta(\sum_{j}n_{jk}>0)$ .

Using (1) and (2) and normalizing the gamma distributions, (16) can be re-expressed as

which loses the count modeling ability and becomes a finite representation of the HDP, the inference of which is not conjugate and has to be solved under alternative representations . This also implies that by using the Dirichlet process as the foundation, traditional mixture modeling may discard useful count information from the beginning.

The Negative Binomial Process Family and Related Algorithms

The gamma-NB process shares the NB dispersion across groups. Since the NB distribution has two adjustable parameters, we may explore alternative ideas, with the NB probability measure shared across groups as in , or with both the dispersion and probability measures shared as in . These constructions are distinct from both the gamma-NB process and HDP in that $\Lambda_{j}$ has space dependent scales, and thus its normalization $\widetilde{\Lambda}_{j}={\Lambda_{j}}/\Lambda_{j}(\Omega)$ no longer follows a Dirichlet process.

It is natural to let the probability measure be drawn from a beta process , which can be defined by its Lévy measure on a product space $\times\Omega$ as $\nu(dpd\omega)=cp^{-1}(1-p)^{c-1}dpB_{0}(d\omega).$ A draw from the beta process $B\sim\mbox{BP}(c,B_{0})$ with concentration parameter $c$ and base measure $B_{0}$ can be expressed as $B=\sum_{k=1}^{\infty}p_{k}\delta_{\omega_{k}}.$ A beta-NB process can be constructed by letting $X_{j}\sim\mbox{NBP}(r_{j},B)$ , with a random draw expressed as $X_{j}=\sum_{k=1}^{\infty}n_{jk}\delta_{\omega_{k}},~{}n_{jk}\sim\mbox{NB}(r_{j},p_{k}).$ Under this construction, the NB probability measure is shared and the NB dispersion parameters are group dependent. As in , we may also consider a marked-beta-NBWe may also consider a beta marked-gamma-NB process, whose performance is found to be very similar. process that both the NB probability and dispersion measures are shared, in which each point of the beta process is marked with an independent gamma random variable. Thus a draw from the marked-beta process becomes $(R,B)=\sum_{k=1}^{\infty}(r_{k},p_{k})\delta_{\omega_{k}}$ , and the NB process $X_{j}\sim\mbox{NBP}(R,B)$ becomes $X_{j}=\sum_{k=1}^{\infty}n_{jk}\delta_{\omega_{k}},~{}n_{jk}\sim\mbox{NB}(r_{k},p_{k}).$ Since the beta and NB processes are conjugate, the posterior of $B$ is tractable, as shown in . If it is believed that there are excessive number of zeros, governed by a process other than the NB process, we may introduce a zero inflated NB process as $X_{j}\sim\mbox{NBP}(RZ_{j},p_{j})$ , where $Z_{j}\sim\mbox{BeP}(B)$ is drawn from the Bernoulli process and $(R,B)=\sum_{k=1}^{\infty}(r_{k},\pi_{k})\delta_{\omega_{k}}$ is drawn from a marked-beta process, thus $n_{jk}\sim\mbox{NB}(r_{k}b_{jk},p_{j}),~{}b_{jk}=\mbox{Bernoulli}(\pi_{k})$ . This construction can be linked to the model in with appropriate normalization, with advantages that there is no need to fix $p_{j}=0.5$ and the inference is fully tractable. The zero inflated construction can also be linked to models for real valued data using the Indian buffet process (IBP) or beta-Bernoulli process spike-and-slab prior .

To show how the NB processes can be diversely constructed and to make connections to previous parametric and nonparametric mixture models, we show in Table 1 a variety of NB processes, which differ on how the dispersion and probability measures are shared. For a deeper understanding on how the counts are modeled, we also show in Table 1 both the VMR and ODL implied by these settings. We consider topic modeling of a document corpus, a typical example of mixture modeling of grouped data, where each a-bag-of-words document constitutes a group, each word is an exchangeable group member, and $F(x_{ji};\omega_{k})$ is simply the probability of word $x_{ji}$ in topic $\omega_{k}$ .

We consider six differently constructed NB processes in Table 1: (i) Related to latent Dirichlet allocation (LDA) and Dirichlet Poisson factor analysis (Dir-PFA) , the NB-LDA is also a parametric topic model that requires tuning the number of topics. However, it uses a document dependent $r_{j}$ and $p_{j}$ to automatically learn the smoothing of the gamma distributed topic weights, and it lets $r_{j}\sim\mbox{Gamma}(\gamma_{0},1/c),~{}\gamma_{0}\sim\mbox{Gamma}(e_{0},1/f_{0})$ to share statistical strength between documents, with closed-form Gibbs sampling inference. Thus even the most basic parametric LDA topic model can be improved under the NB count modeling framework. (ii) The NB-HDP model is related to the HDP , and since $p_{j}$ is an irrelevant parameter in the HDP due to normalization, we set it in the NB-HDP as 0.5, the usually perceived value before normalization. The NB-HDP model is comparable to the DILN-HDP that constructs the group-level DPs with normalized gamma processes, whose scale parameters are also set as one. (iii) The NB-FTM model introduces an additionalbeta-Bernoulli process under the NB process framework to explicitly model zero counts. It is the same as the sparse-gamma-gamma-PFA (S $\gamma\Gamma$ -PFA) in and is comparable to the focused topic model (FTM) , which is constructed from the IBP compound DP. Nevertheless, they apply about the same likelihoods and priors for inference. The Zero-Inflated-NB process improves over them by allowing $p_{j}$ to be inferred, which generally yields better data fitting. (iv) The Gamma-NB process explores the idea that the dispersion measure is shared across groups, and it improves over the NB-HDP by allowing the learning of $p_{j}$ . It reduces to the HDP by normalizing both the group-level and the shared gamma processes. (v) The Beta-NB process explores sharing the probability measure across groups, and it improves over the beta negative binomial process (BNBP) proposed in , allowing inference of $r_{j}$ . (vi) The Marked-Beta-NB process is comparable to the BNBP proposed in , with the distinction that it allows analytical update of $r_{k}$ . The constructions and inference of various NB processes and related algorithms in Table 1 all follow the formulas in (16) and (3.2), respectively, with additional details presented in the supplementary material.

Example Results

Figure 1 compares the performance of various algorithms. The Marked-Beta-NB process has the best performance, closely followed by the Gamma-NB process, CRF-HDP and Beta-NB process. With an appropriate $K$ , the parametric NB-LDA may outperform the nonparametric NB-HDP and NB-FTM as the training data percentage increases, somewhat unexpected but very intuitive results, showing that even by learning both the NB dispersion and probability parameters $r_{j}$ and $p_{j}$ in a document dependent manner, we may get better data fitting than using nonparametric models that share the NB dispersion parameters $r_{k}$ across documents, but fix the NB probability parameters.

It is also interesting to compare the Gamma-NB and NB-HDP. From a mixture-modeling viewpoint, fixing $p_{j}=0.5$ is natural as $p_{j}$ becomes irrelevant after normalization. However, from a count modeling viewpoint, this would make a restrictive assumption that each count vector $\{n_{jk}\}_{k=1,K}$ has the same VMR of 2, and the experimental results in Figure 1 confirm the importance of learning $p_{j}$ together with $r_{k}$ . It is also interesting to examine (15), which can be viewed as the concentration parameter $\alpha$ in the HDP, allowing the adjustment of $p_{j}$ would allow a more flexible model assumption on the amount of variations between the topic proportions, and thus potentially better data fitting.

Conclusions

We propose a variety of negative binomial (NB) processes to jointly model counts across groups, which can be naturally applied for mixture modeling of grouped data. The proposed NB processes are completely random measures that they assign independent random variables to disjoint Borel sets of the measure space, as opposed to the hierarchical Dirichlet process (HDP) whose measures on disjoint Borel sets are negatively correlated. We discover augment-and-conquer inference methods that by “augmenting” a NB process into both the gamma-Poisson and compound Poisson representations, we are able to “conquer” the unification of count and mixture modeling, the analysis of fundamental model properties and the derivation of efficient Gibbs sampling inference. We demonstrate that the gamma-NB process, which shares the NB dispersion measure across groups, can be normalized to produce the HDP and we show in detail its theoretical, structural and computational advantages over the HDP. We examine the distinct sharing mechanisms and model properties of various NB processes, with connections to existing algorithms, with experimental results on topic modeling showing the importance of modeling both the NB dispersion and probability parameters.

The research reported here was supported by ARO, DOE, NGA, and ONR, and by DARPA under the MSEE and HIST programs.

References

Appendix A Generating a CRT random variable

A CRT random variable $l\sim\emph{\mbox{CRT}}(m,r)$ can be generated with the summation of independent Bernoulli random variables as

Since $l$ is the summation of independent Bernoulli random variables, its PGF becomes

Thus we have $f_{L}(l|m,r)=\frac{C^{(l)}_{L}(0)}{l!}={\frac{\Gamma(r)}{\Gamma(m+r)}}|s(m,l)|r^{l},~{}~{}l=0,1,\cdots,m.$ ∎

Appendix B Dir-PFA and LDA

The Dirichlet Poisson factor analysis (Dir-PFA) model is constructed as

where $\eta$ is the Dirichlet smoothing parameter for the topic’s distribution over the vocabulary, $n_{jk}=\sum_{i=1}^{N_{j}}\delta({z_{ji}=k})$ , and the data likelihood $F(x_{ji};\omega_{k})$ in topic modeling is $\omega_{v_{ji}k}$ , the probability of the $i$ th word in $j$ th document under topic $\omega_{k}$ .

The Dir-PFA has the same block Gibbs sampling as LDA , expressed as

Appendix C CRF-HDP

Under the CRF metaphor, denote $n_{jk}$ as the number of customers eating dish $k$ in restaurant $j$ and $l_{jk}$ as the number of tables serving dish $k$ in restaurant $j$ , the direct assignment block Gibbs sampling can be expressed as

When $K\rightarrow\infty$ , the concentration parameter $\gamma_{0}$ can be sampled as

where $K^{+}$ is the number of used atoms. Since it is infeasible in practice to let $K\rightarrow\infty$ , directly using this method to sample $\gamma_{0}$ is only approximately correct, which may result in a biased estimate especially if $K$ is not set large enough. Thus in the experiments, $\gamma_{0}$ is not sampled and is fixed as one. Note that for implementation convenience, it is also common to fix the concentration parameter $\alpha$ as one . We find through experiments that learning this parameter usually results in obviously lower per-word perplexity for held out words, thus we allow the learning of $\alpha$ using the data augmentation method proposed in , which is modified from the one proposed in .

Appendix D NB-LDA

Note that letting $r_{j}\sim\mbox{Gamma}(\gamma_{0},1/c),~{}\gamma_{0}\sim\mbox{Gamma}(e_{0},1/f_{0})$ allows different documents to share statistical strength for inferring their NB dispersion parameters.