The Discrete Infinite Logistic Normal Distribution

Introduction

The hierarchical Dirichlet process (HDP) has emerged as a powerful Bayesian nonparametric prior for grouped data (Teh et al., 2006), particularly in its role in Bayesian nonparametric mixed-membership models. In an HDP mixed-membership model, each group of data is modeled with a mixture where the mixture proportions are group-specific and the mixture components are shared across the data. While finite models require the number of mixture components to be fixed in advance, the HDP model allows the data to determine how many components are needed. And that number is variable: With an HDP model, new data can induce new components.

The HDP mixed-membership model has been widely applied to probabilistic topic modeling, where hierarchical Bayesian models are used to analyze large corpora of documents in the service of exploring, searching, and making predictions about them (Blei, Ng and Jordan, 2003; Erosheva, Fienberg and Lafferty, 2004; Griffiths and Steyvers, 2004; Blei and Lafferty, 2007, 2009). In topic modeling, documents are grouped data—each document is a group of observed words—and we analyze the documents with a mixed-membership model. Conditioned on a collection, the posterior expectation of the mixture components are called “topics” because they tend to resemble the themes that pervade the documents; the posterior expectation of the mixture proportions identify how each document exhibits the topics. Bayesian nonparametric topic modeling uses an HDP to try to solve the model selection problem; the the number of topics is determined by the data and new documents can exhibit new topics.

For example, consider using a topic model to analyze 10,000 articles from Wikipedia. (This is a data set that we will return to.) At the corpus level, the posterior of one component might place high probability on terms associated with elections; another might place high probability on terms associated with the military. At the document level, articles that discuss both subjects will have posterior proportions that place weight on both topics. The posterior of these quantities over the whole corpus can be used to organize and summarize Wikipedia in a way that is not otherwise readily available.

Though powerful, the HDP mixed-membership model is limited in that it does not explicitly model the correlations between the mixing proportions of any two components. For example, the HDP topic model cannot capture that the presence of the election topic in a document is more positively correlated with the presence of the military topic than it is a topic about mathematics. Capturing such patterns, i.e., representing that one topic might often co-occur with another, can provide richer exploratory variables to summarize the data and further improve prediction.

To address this, we developed the discrete infinite logistic normal distribution (DILN, pronounced “Dylan”), a Bayesian nonparametric prior for mixed-membership models (Paisley, Wang and Blei, 2011).In this paper we expand on the ideas of Paisley, Wang and Blei (2011), which is a short conference paper. We report on new data analysis, we describe a model of the latent component locations that allows for variational inference, we improve the variational inference algorithm (see Section 3.4), and we expand it to scale up to very large data sets. As with the HDP, DILN generates discrete probability distributions on an infinite set of components, where the same components are shared across groups but have differently probabilities within each group. Unlike the HDP, DILN also models the correlation structure between the probabilities of the components.

Figure 1 illustrates the DILN posterior for 10,000 articles from Wikipedia. The corpus is described by a set of topics—each topic is a distribution over words and is visualized by listing the most probable words—and the topics exhibit a correlation structure. For example, topic 3 (“party, election, vote”) is correlated with topic 12 (“constitution, parliament, council”) and topic 25 (“coup, army, military”). It is negatively correlated with topic 20 (“food, meat, drink”).

In DILN, each component is associated with a parameter (e.g., a topical distribution over terms) and a location in a latent space. For group-level distributions (e.g., document-specific distributions over topics), the correlation between component weights is determined by a kernel function of latent locations of these components. Since the correlation between occurrences is a posterior correlation, i.e., one that emerges from the data, the locations of the components are also latent. For example, we do not enforce a priori what the topics are and how they are correlated—this structure comes from the posterior analysis of the text.

We formulate two equivalent representations of DILN. We first formulate it as an HDP scaled by a Gaussian process (Rasmussen and Williams, 2006). This gives an intuitive picture of how the correlation between component weights enters the distribution and makes clear the relationship between DILN and the HDP. We then formulate DILN as a member of the normalized gamma family of random probability distributions. This lets us characterize the a priori correlation structure of the component proportions.

The central computational problem for DILN is approximate posterior inference. Given a corpus, we want to compute the posterior distribution of the topics, per-document topic proportions, and the latent locations of the topics. Using normalized the gamma construction of a random measure, we derive a variational inference algorithm (Jordan et al., 1999) to approximate the full posterior of a DILN mixed-membership model. (Moreover, this variational algorithm can be modified into a new posterior inference algorithm for HDP mixed-membership models.) We use variational inference to analyze several collections of documents, each on the order of thousands of articles, determining the number of topics based on the data and identifying an explicit correlation structure among the discovered topics. On four corpora (collected from Wikipedia, Science, The New York Times, and The Huffington Post), we demonstrate that DILN provides a better predictive model and an effective new method for summarizing and exploring text data. (Again, see Figure 1 and also Figures 4, 5 and 6.)

Variational inference turns the problem of approximating the posterior into an optimization problem. Recent research has used stochastic optimization to scale variational inference up to very large data sets (Hoffman, Blei and Bach, 2010; Armagan and Dunson, 2011), including our own research on HDP mixed-membership models (Wang, Paisley and Blei, 2011). We used the same strategy here to develop a scalable inference algorithm for DILN. This further expands the scope of stochastic variational inference to models (like DILN) whose latent variables do not enjoy pair-wise conjugacy. Using stochastic inference, we analyzed 352,549 thousand articles from Nature magazine, a corpus which would be computationally expensive with our previous variational algorithm.

The parametric model most closely related to DILN is the correlated topic model (CTM) (Blei and Lafferty, 2007). The CTM is a mixed-membership model that allows topic occurrences to exhibit correlation. The CTM replaces the Dirichlet prior over topic proportions, which assumes near independence of the components, with a logistic normal prior (Aitchison, 1982). Logistic normal vectors are generated by exponentiating a multivariate Gaussian vector and normalizing to form a probability vector. The covariance matrix of the multivariate Gaussian distribution provides a means for capturing correlation structure between topic probabilities. Our goal in developing DILN was to form a Bayesian nonparametric variant of this kind of model.

The natural nonparametric extension of the logistic normal is a normalized exponentiated Gaussian process (Lenk, 1988; Rasmussen and Williams, 2006). However, this cannot function as a prior for nonparametric correlated topic modeling. The key property of the HDP (and DILN) is that the same set of components are shared among the groups. This sharing arises because the group-level distributions on the infinite topic space are discrete probability measures over the same set of atoms. Using the model of Lenk (1988) in a hierarchical setting does not provide such distributions. The “infinite CTM” is therefore not a viable alternative to the HDP.

In the Bayesian nonparametric literature, another related line of work focuses on dependent probability distributions where the dependence is defined on predictors observed for each data point. MacEachern (1999) introduced dependent Dirichlet processes (DDPs), which allow data-dependent variation in the atoms of the mixture, and have been applied to spatial modeling (Gelfand, Kottas and MacEachern, 2005; Rao and Teh, 2009). Other dependent priors allow the mixing weights themselves to vary with predictors (Griffin and Steel, 2006; Duan, Guindani and Gelfand, 2007; Dunson and Park, 2008; Ren et al., 2011). Still other methods consider the weighting of multiple DP mixture models using spatial information (Muller, Quintana and Rosner, 2004; Dunson, Pillai and Park, 2007).

These methods all use the spatial dependence between observations to construct observation-specific probability distributions. Thus they condition on known locations (often geospatial) for the data. In contrast, the latent locations of each component in DILN do not directly interact with the data, but with each other. That is, the correlations induced by these latent locations influence the mixing weights for a data group prior to producing its observations in the generative process. Unlike DDP models, our observations are not equipped with locations and do not a priori influence component probabilities. The modeling ideas behind DILN and behind DDPs are separate, though it is possible to develop dependent DILN models, just as dependent HDP models have been developed (MacEachern, 1999).

This paper is organized as follows. In Section 2 we review the HDP and discuss its representation as a normalized gamma process. In Section 3 we present the discrete infinite logistic normal distribution, first as a scaling of an HDP with an exponentiated Gaussian process and then using a normalized gamma construction. In Section 4 we use this gamma construction to derive a mean-field variational inference algorithm for approximate posterior inference of DILN topic models, and we extend this algorithm to the stochastic variational inference setting. Finally, in Section 5 we provide an empirical study of the DILN topic model on five text corpora.

Background: The Hierarchical Dirichlet Process

The discrete infinite logistic normal (DILN) prior for mixed-membership models is an extension of the hierarchical Dirichlet process (HDP) (Teh et al., 2006). In this section, we review the HDP and reformulate it as a normalized gamma process.

The Dirichlet process (Ferguson, 1973) is useful as a Bayesian nonparametric prior for mixture models since it generates distributions on infinite parameter spaces that are almost surely discrete (Blackwell and MacQueen, 1973; Sethuraman, 1994). Given a space $\Omega$ with a corresponding Borel $\sigma$-algebra $\mathcal{B}$ and base measure $\alpha G_{0}$, where $\alpha>0$ and $G_{0}$ is a probability measure, Ferguson (1973) proved the existence of a process $G$ on $(\Omega,\mathcal{B})$ such that for all measurable partitions $\{B_{1},\dots,B_{K}\}$ of $\Omega$,

This is called a Dirichlet process and is denoted $G\sim\textrm{DP}(\alpha G_{0})$. Sethuraman (1994) gave a proof of the almost sure (a.s.) discreteness of $G$ by way of a stick-breaking representation (Ishwaran and James, 2001); we will review this stick-breaking construction later. Blackwell and MacQueen (1973) gave an earlier proof of this discreteness using Pólya urn schemes. The discreteness of $G$ allows us to write it as

where each atom $\eta_{k}$ is generated i.i.d. from the base distribution $G_{0}$, and the atoms are given random probabilities $p_{k}$ whose distribution depends on a scaling parameter $\alpha>0$ such that smaller values of $\alpha$ lead to distributions that place more mass on fewer atoms. The DP is most commonly used as a prior for a mixture model, where $G_{0}$ is a distribution on a model parameter, $G\sim\textrm{DP}(\alpha G_{0})$ and each data point is drawn from a distribution family indexed by a parameter drawn from $G$ (Ferguson, 1983; Lo, 1984).

When the base measure $G_{0}$ is non-atomic, multiple draws from the DP prior place their probability mass on an a.s. disjoint set of atoms. That is, for $G_{1},G_{2}\stackrel{{\scriptstyle iid}}{{\sim}}\textrm{DP}(\alpha G_{0})$, an atom $\eta_{k}$ in $G_{1}$ will a.s. not appear in $G_{2}$, i.e., $G_{1}(\{\eta_{k}\})>0\implies G_{2}(\{\eta_{k}\})=0$ a.s. The goal of mixed-membership modeling is to use all groups of data to learn a shared set of atoms. The hierarchical Dirichlet process (Teh et al., 2006) was introduced to allow multiple Dirichlet processes to share the same atoms. The HDP is a prior for a collection of random distributions $(G_{1},\dots,G_{M})$. Each $G_{m}$ is i.i.d. DP distributed with a base probability measure that is also a Dirichlet process,

The hierarchical structure of the HDP ensures that each $G_{m}$ has probability mass distributed across a shared set of atoms, which results from the a.s. discreteness of the second-level base measure $\beta G$. Therefore, the same subset of atoms will be used by all groups of data, but with different probability distributions on these atoms for each group.

Where the DP allows us to define a mixture model, the HDP allows us to define a mixed-membership model. Given an HDP $(G_{1},\dots,G_{M})$, each $G_{m}$ generates its associated group of data from a mixture model,

2 The HDP as a normalized gamma process

The DP has several representations, including a gamma process representation (Ferguson, 1973) and a stick-breaking representation (Sethuraman, 1994). In constructing HDPs, we will take advantage of each of these representations at different levels of the hierarchy.

We construct the top-level DP using stick-breaking (Sethuraman, 1994),

The gamma process representation of the DP is discussed by Ferguson (1973), Kingman (1993) and Ishwaran and Zarepour (2002), but it has not been applied to the HDP. In DILN we will mirror this type of construction of the HDP—a stick-breaking construction for the top-level DP and a gamma process construction for the second-level DPs. This will let us better articulate model properties and also make inference easier.

The Discrete Infinite Logistic Normal Distribution

The HDP prior has the hidden assumption that the presence of one atom in a group is not a priori correlated with the presence of another atom (aside from the negative correlation imposed by the probability simplex). At the group level the HDP cannot model correlation structure between the components’ probability mass. To see this, note that the gamma process used to construct each group-level distribution is an example of a completely random measure (Kingman, 1993). That is, the unnormalized masses $(Z_{1}^{(m)},Z_{2}^{(m)},\dots)$ of the atoms $(\eta_{1},\eta_{2},\dots)$ of $G_{m}$ are independently drawn, and for all partitions $\{B_{1},\dots,B_{K}\}$ of $\Omega$ and given $S_{m}:=\sum_{j}Z_{j}^{(m)}$, the scaled random variables $S_{m}G_{m}(B_{1}),\dots,S_{m}G_{m}(B_{K})$ are independent. Thus, no correlation between per-group probabilities can be built into the HDP.

We introduced the discrete infinite logistic normal (DILN) as a modification of the HDP that can express such correlations (Paisley, Wang and Blei, 2011). The idea is that each atom lives in a latent location, and the correlation between atom probabilities is determined by their relative locations in the latent space. When analyzing data, modeling these correlations can improve the predictive distribution and provide more information about the underlying latent structure. DILN has two equivalent representations; we first describe it as a scaled HDP, with scaling determined by an exponentiated Gaussian process (Rasmussen and Williams, 2006). We then show how DILN fits naturally within the family of normalized gamma constructions of discrete probability distributions in a way similar to the discussion in Section 2.2 for the HDP.

In the second level of the process, the model uses both the probability measure $G$ and the locations of the atoms to construct group-level probability distributions. This occurs in two steps. In the first step, we independently draw a Dirichlet process and a Gaussian process using the measure and atoms of $G$,

The second step is to form each group-level distribution by scaling the probabilities of each second-level Dirichlet process by the exponentiated values of its corresponding Gaussian process,

2 A normalized gamma construction of DILN

We now turn to a normalized gamma construction of DILN. We show that the DILN prior uses the second parameter of the gamma distribution in the normalized gamma construction of the HDP to model the covariance structure among the components of $G_{m}$. This representation facilitates approximate posterior inference described in Section 4, and helps clarify the covariance properties of the group-level distributions over atoms.

We use a stick-breaking construction of the top-level Dirichlet process (Equation 7),

We pattern the group-level distributions after the gamma process construction of the second-level DP in the HDP,

with $p_{k}:=V_{k}\prod_{j=1}^{k-1}(1-V_{j})$. Here, DILN differs from the HDP in that it uses the second parameter of the gamma distribution. In the appendix, we give a proof that the normalizing constant is almost surely finite.

For the topic model, drawing an observation proceeds as for the HDP. We use a latent indicator variable $C_{n}^{(m)}$, which selects the index of the atom used by observation $X_{n}^{(m)}$. This indicator variable gives a useful hidden-data representation of the process for inference in mixture models (Escobar and West, 1995),

where the discrete distribution is on word index values $\{1,\dots,V\}$. We note that this discrete distribution is one of many possible data generating distributions, and changing this distribution and $G_{0}$ will allow for DILN to be used in a variety of other mixed-membership modeling applications (Erosheva, Fienberg and Joutard, 2007; Airoldi et al., 2008; Pritchard, Stephens and Donnelly, 2000). Figure 2 shows the graphical model of the DILN topic model.

3 The covariance structure of DILN

Observe that the covariance is similar to the unnormalized logistic normal (Aitchison, 1982), but with the additional term $\beta^{2}p_{i}p_{j}$. In general, these $p_{i}$ terms show how sparsity is enforced by the top-level DP, since both the expectation and variance terms go to zero exponentially fast as $i$ increases.

These values can also be calculated with the top-level Dirichlet process integrated out using the tower property of conditional expectation. They are

The values of the expectations in Equation (14) are

Note that some covariance remains when $k_{ij}=0$, since the conditional independence induced by $\boldsymbol{p}$ is no longer present. The available covariance structure depends on the kernel. For example, when a Gaussian kernel is used, a structured negative covariance is not achievable since $k_{ij}\geq 0$. We next discuss one possible kernel function, which we will use in our inference algorithm and experiments.

4 Learning the kernel for DILN

With this in mind, we use the following construction of the Gaussian process $W_{m}$,

Variational Inference for DILN

In Bayesian nonparametric mixed-membership modeling, the central computational problem is posterior inference. However, computing the exact posterior is intractable. For HDP-based models, researchers have developed several approximate methods (Teh et al., 2006; Liang et al., 2007; Teh, Kurihara and Welling, 2009; Wang, Paisley and Blei, 2011).

In this paper, we derive a mean-field variational inference algorithm (Jordan et al., 1999; Wainwright and Jordan, 2008) to approximate the posterior of a DILN mixed-membership model. We focus on topic modeling but note that our algorithm can be applied (with a little modification) to any DILN mixed-membership model. In addition, since the HDP is an instance of DILN, this algorithm also provides an inference method for HDP mixed-membership models.

We select the following variational distributions for each latent variable,

We will find a locally optimal solution of this function using coordinate ascent, as detailed in the next section.

Note that we truncate the number of components at $T$ in the top-level Dirichlet process (Blei and Jordan, 2005). Kurihara, Welling and Vlassis (2006) show how infinite-dimensional objective functions can be defined for variational inference, but the conditions for this are not met by DILN. The truncation level $T$ should be set larger than the total number of topics expected to be used by the data. A value of $T$ that is set too small is easy to diagnose: the approximate posterior will use all $T$ topics. Setting $T$ large enough, the variational approximation will prefer a corpus-wide distribution on topics that is sparse. We contrast this with the CTM and other finite topic models, which fit a pre-specified number of topics to the data and potentially overfit if that number is too large.

We use coordinate ascent to optimize this function, iterating between two steps. In the first step we optimize the document-level parameters for each document; in the second step we optimize the corpus-level parameters. Algorithm 1 summarizes this general inference structure.

For each document, we iterate between updating the variational distribution of per-word topic indicators $C_{n}^{(m)}$, unnormalized weights $Z_{k}^{(m)}$, and document locations $\hat{u}_{m}$.

The variational distribution on the topic index for word $X_{n}^{(m)}$ is multinomial with parameter $\phi$. For $k=1,\dots,T$ topics

Since $\phi_{n}^{(m)}=\phi_{n^{\prime}}^{(m)}$ when $X_{n}^{(m)}=X_{n^{\prime}}^{(m)}$, we only need to compute this update once for each unique word occurring in document $m$.

This variational gamma distribution has parameters $a_{k}^{(m)}$ and $b_{k}^{(m)}$. Let $N_{m}$ be the number of observations (e.g., words) in group $m$. After introducing an auxiliary parameter $\xi_{m}$ for each group-level distribution (discussed below), the updates are

We update the location of the $m\mbox{th}$ document using gradient ascent, which takes the general form $\hat{u}_{m}^{\prime}=\hat{u}_{m}+\rho\nabla_{\hat{u}_{m}}\mathcal{L}$. We take several steps in updating this value within an iteration. For step $s$ we update $\hat{u}_{m}$ as

We let the step size $\rho$ be a function of step number $s$, and (for example) set it to $\rho_{s}=\frac{1}{T}(3+s)^{-1}$ for $s=1,\dots,20$. We use $1/T$ to give a per-topic average, which helps to stabilize the magnitude of the gradient by removing its dependence on truncation level $T$, while $(3+s)^{-1}$ shrinks the step size. For each iteration, we reset $s=1$.

Corpus-level parameters

After optimizing the variational parameters for each document, we turn to the corpus-level parameters. In the coordinate ascent algorithm, we update each corpus-level parameter once before returning to the document-level parameters.

The variational distribution for the topic parameters is Dirichlet with parameter vector $\gamma_{k}$. For each of $d=1,\dots,D$ vocabulary words

where $\gamma_{0}$ is the parameter for the base distribution $\eta_{k}\sim{\rm Dirichlet}(\gamma_{0})$. Statistics needed for this term can be updated in unison with updates to $q(C_{n}^{(m)})$ for faster inference.

For $k=1,\dots,T-1$, the $q$ distribution for each $V_{k}$ is a delta function, $\delta_{\hat{V}_{k}}$. The truncation of the top-level DP results in $V_{T}:=1$. We use steepest ascent to jointly optimize $\hat{V}_{1},\dots,\hat{V}_{T-1}$. The gradient of each element is

We observed similar performance using Newton’s method in our experiments.

As with $\hat{u}_{m}$, we let the step size $\rho$ be a function of step number $s$, and set it to $\rho_{s}=\frac{1}{M}(3+s)^{-1}$.

In our empirical study we set $\tau_{1}=1$ and $\tau_{2}=10^{-3}$.

We set $\kappa_{1}=1$ and $\kappa_{2}=10^{-3}$.

2 Stochastic variational inference

The algorithm of Section 4.1 can be called a batch algorithm because it updates all document-level parameters in one “batch” before updating the global parameters. A potential drawback of this batch inference approach for DILN (as well as potential Monte Carlo sampling algorithms) is that the per-iteration running time increases with an increasing number of groups. For many modeling applications, the algorithm may be impractical for large-scale problems.

One solution to the large-scale data problem is to sub-sample a manageable number of groups from the larger collection, and assume that this provides a good statistical representation of the entire data set. Indeed, this is the hope with batch inference, which views the data set as a representative sample from the larger, unseen population. However, in this scenario information contained in the available data set may be lost. Stochastic variational inference methods (Hoffman, Blei and Bach, 2010; Wang, Paisley and Blei, 2011; Sato, 2001) aim for the best of both worlds, allowing one to fit global parameters for massive collections of data in less time than it takes to solve problems of moderate size in the batch setting.

The idea behind stochastic variational inference is to perform stochastic optimization of the variational objective function in Equation (21). In topic modeling, we can construe this objective function as a sum over per-document terms and then obtain noisy estimates of the gradients by evaluating them on sets of documents sampled from the full corpus. By following these noisy estimates of the gradient with a decreasing step size, we are guaranteed convergence to a local optimum of the variational objective function (Robbins and Monro, 1951; Sato, 2001; Hoffman, Blei and Bach, 2010).

Algorithmically, this gives an advantage over the optimization algorithm of Section 4.1 for large-scale machine learning. The bottleneck of that algorithm is the variational “E step,” where the document-level variational parameters are optimized for all documents using the current settings of the corpus-level variational parameters (i.e., the topics and their locations, and $\alpha$, $\beta$). This computation may be wasteful, especially in the first several iterations, where the initial topics likely do not represent the corpus well. In contrast, the structure of a stochastic variational inference algorithm is to repeatedly subsample documents, analyze them, and then use them to update the corpus-level variational parameters. When the data set is massive, these corpus-level parameters can converge before seeing any document a second time.

In our experiments, we select the form $\rho_{t}=(\zeta+t)^{-\kappa}$ with $\kappa\in(0.5,1]$ and $\zeta>0$.

The stochastic algorithm selects a subset of documents at step $t$, coded by a set of index values $B_{t}$, and optimizes the document-level parameters for these documents while holding all corpus-level parameters fixed. These parameters are the word indicators $C_{k}^{(m)}$, the unnormalized topic weights $Z_{k}^{(m)}$ and the document locations $u_{k}$. (See Section 4.1 for discussion on inference for these variables.) Given the values of the document-level variational parameters for documents indexed by $B_{t}$, we now describe the corpus-level updates in the stochastic inference algorithm. Algorithm 2 summarizes this general inference structure.

In this case, premultiplying the gradient by the inverse Fisher information cancels the Fisher information in the gradient and thus removes the cross-dependencies between the components of $\gamma_{k}$. We use preconditioning to simplify the computation, rather than to speed up optimization. See Hoffman, Blei and Bach (2010), Wang, Paisley and Blei (2011) and Sato (2001) for details.

3 A new variational inference algorithm for the HDP

The variational inference algorithm above relates closely to one that can be derived for the HDP using the normalized gamma process representation of Section 2.2. The difference lies in the update for the topic weight $q(Z_{k}^{(m)})$ in Equation (4.1). In both algorithms, the update for its variational parameter $a_{k}^{(m)}$ contains the prior from the top-level DP, and the expected number of words in document $m$ drawn from topic $k$. The variational parameter $b^{(m)}$ distinguishes DILN from the HDP.

4 MCMC inference

Markov chain Monte Carlo (MCMC, Robert and Casella, 2004) sampling is a more common strategy for approximate posterior inference in Bayesian nonparametric models, and for the hierarchical Dirichlet process in particular. In MCMC methods, samples are drawn from a carefully designed Markov chain, whose stationary distribution is the target posterior of the model parameters. MCMC is convenient for the many Bayesian nonparametric models that are amenable to Gibbs sampling, where the Markov chain iteratively samples from the conditional distribution of each latent variable given all of the other latent variables and the observations.

However, Gibbs sampling is not an option for DILN because the Gaussian process component does not have a closed-form full conditional distribution. One possible sampling algorithm for DILN inference would use Metropolis-Hastings (Hastings, 1970), where samples are drawn from a proposal distribution and then accepted or rejected. Designing a good proposal distribution is the main problem in designing Metropolis-Hastings algorithms, and in DILN this problem is more difficult than usual because the hidden variables are highly correlated.

Recently, slice sampling has been applied to sampling of infinite mixture models by turning the problem into a finite sampling problem (Griffin and Walker, 2010; Kalli, Griffin and Walker, 2011). These methods apply when the mixture weights are either from a simple stick-breaking prior or a normalized random measures that can be simulated from a Poisson process. Neither of these settings applies to DILN because the second-level DP is a product of a DP and an exponentiated GP. Furthermore, it is not clear how to extend slice sampling methods to hierarchical models like the HDP or DILN.

Variational methods mitigate all these issues by using optimization to approximate the posterior. Our algorithm sacrifices the theoretical (and eventual) convergence to the full posterior in favor of a simpler distribution that is fit to minimize its KL-divergence to the posterior. Though we must address issues of local minima in the objective, we do not need to develop complicated proposal distributions or solve the difficult problem of assessing convergence of a high-dimensional Markov chain to its stationary distribution.Note our evaluation method of Section 5 does not use the divergence of the variational approximation and the true posterior. Rather, we measure the corresponding approximation to the predictive distribution. On a pilot study of batch inference, we found that MCMC inference (with its approximate predictive distribution) did not produce distinguishable results from variational inference. Furthermore, variational inference is ideally suited to the stochastic optimization setting, allowing for approximate inference with very large data sets.

Empirical study

We evaluate the DILN topic model with both batch and stochastic inference. For batch inference, we compare with the HDP and correlated topic model (CTM) on four text corpora: The Huffington Post, The New York Times, Science and Wikipedia. We divide each corpus into five training and testing groups selected from a larger set of documents (see Table 1).

For stochastic inference, we use the Nature corpus to assess performance. This corpus contains 352,549 documents spanning 1869-2003; we used a vocabulary of 4,253 words. We compare stochastic DILN with a stochastic HDP algorithm and with online LDA (Hoffman, Blei and Bach, 2010).

Before discussing the experimental setup and results, we discuss our method for evaluating performance. We evaluate the approximate posterior of all models by measuring its predictive ability on held-out documents. Following Asuncion et al. (2009), we randomly partition each test document into two halves and evaluate the conditional distribution of the second half given the first half and the training data. Operationally, we use the first half of each document to find estimates of document-specific topic proportions and then evaluate how well these combine with the fitted topics to predict the second half of the document.

Since the integral in Equation (40) is intractable, we sample i.i.d. values from the factorized distributions $Q({Z_{1:T}})$ and $Q(\eta_{1:T})$ for approximation. We note that the information regarding the document’s correlation structure can be found in $Q({Z_{1:T}})$.

We then use this approximation of the marginal likelihood to compute the average per-word perplexity for the second half of the test document,

2 Experimental setup and results

We trained all models using variational inference; for the CTM, this is the algorithm given in Blei and Lafferty (2007); for the HDP, we use the inference method from Section 4. For DILN, we use a latent space with $d=20$ and set the location variance parameter $c=1/20$. For DILN and the HDP, we truncate the top-level stick-breaking construction at $T=200$ components. For the CTM, we consider $K\in\{20,50,150\}$ topics. In our experiments, both DILN and HDP used significantly fewer topics than the truncation level, indicating that the truncation level was set high enough. The CTM is not sparse in this sense.

We initialize all models in the same way; to initialize the variational parameters of the topic Dirichlet, we first cluster the empirical word distributions of each document with three iterations of k-means using the $L_{1}$ distance measure. We then reorder these topics by their usage according to the indicators produced by k-means. We scale these k-means centroids and add a small constant plus noise to smooth the initialization. The other parameters are initialized to values that favor a uniform distribution on these topics. Variational inference is terminated when the fractional change in the lower bound of Equation (21) falls below $10^{-3}$. We run each algorithm using five different topic Dirichlet hyperparameter settings: $\gamma_{0}\in\{0.1,0.25,0.5,0.75,1.0\}$.

Figure 3 contains testing results for the four corpora. In general, DILN outperforms both the HDP and CTM. Given that the inference algorithms for DILN and the HDP are only different in the one term discussed in Section 4.3, this demonstrates that the latent location space models a correlation structure that helps in predicting words. Computation time for DILN and the HDP was comparable, both requiring on the order of one minute per iteration. Depending on the truncation level, the CTM was slightly to significantly faster than both DILN and the HDP.

We compare stochastic DILN with stochastic HDP and online LDA using 352,549 documents from Nature. As for batch inference, we can obtain a stochastic inference algorithm for the HDP as a special case of stochastic DILN. In DILN, we again use a latent space of $d=20$ dimensions for the component locations and set the location variance parameter to $c=1/20$. We truncate the models at $200$ topics, and we evaluate performance for $K\in\{25,75,125\}$ topics with stochastic inference for LDA (Hoffman, Blei and Bach, 2010). As we discussed in Section 4.2, we use a step sequence of $\rho_{t}=(\zeta+t)^{-\kappa}$. We set $\zeta=25$, and run the algorithm for $\kappa\in\{0.6,0.75,0.9\}$. We explored various batch sizes, running the algorithm for $|B_{t}|\in\{250,750,1250\}$. Following Hoffman, Blei and Bach (2010), we set the topic Dirichlet hyperparameters to $\gamma_{0}=0.01$.

For testing, we held out $10,000$ randomly selected documents from the corpus. We measure the performance of the stochastic models after every $10$th batch. Within each batch, we run several iterations of local variational inference to find document-specific parameters. We update corpus-level parameters when the change in the average per-document topic distributions falls below a threshold. On average, roughly ten document-level iterations were run for each corpus-level update.

Figure 8 illustrates the results. In this figure, we show the per-word held-out perplexity as a function of the number of documents seen by the algorithm. From these plots we see that a slower decay in the step size improves performance. Especially for DILN, we see that performance improves significantly as the decay $\kappa$ decreases, since more information is being used from later documents in finding a maximum of the variational objective function. Slower decays are helpful because more parameters are being fitted by DILN than by the HDP and LDA. We observed that as $\kappa$ increases a less detailed correlation structure was found; this accounts for the decrease in performance.

We also compare stochastic and batch inference for DILN to show how stochastic inference can significantly speed up the inference process, while still giving results as good as batch inference. We again use the Nature corpus. For stochastic inference, we use a subset of size $|B_{t}|=1000$ and a step of $(1+t)^{-0.75}$. For batch inference, we use a randomly selected subset of documents, performing experiments on corpus size $M\in\{25000,50000,100000\}$. All algorithms used the same test set and testing procedure, as discussed in Section 5.1. All experiments were run on the same computer to allow for fair time comparisons.

In Figure 12, we plot the held-out per-word log likelihood as a function of time. We measured performance every tenth iteration to construct each curve. The stochastic inference curve represents roughly six passes through the entire corpus. For batch inference, we see that performance improves significantly as the sub-sampled batch size increases. However, this improvement is paid for with an increasing runtime. Stochastic inference is much faster, but still performs as well as batch in predicting test documents.

Discussion

We have presented the discrete infinite logistic normal distribution, a Bayesian nonparametric prior for mixed-membership models. DILN overcomes the hidden assumptions of the HDP and explicitly models correlation structure between the mixing weights at the group level. We showed how using the second parameter of the gamma process representation of the hierarchical Dirichlet process achieves this by varying per-component according to an exponentiated Gaussian process. This Gaussian process is defined on latent component locations added to the hierarchical structure of the HDP.

Using batch variational Bayesian inference, we showed an improvement in predictive ability over the HDP and the CTM in a topic modeling application. Furthermore, we showed how this algorithm can be modified to obtain a new variational inference algorithm for HDPs based on the gamma process. We then extended the model to the stochastic inference setting, which allows for fast analysis of much larger corpora.

DILN can be useful in other modeling frameworks. For example, hidden Markov models can be viewed as a collection of mixture models that are defined over a shared set of parameters, where state transitions follow a Markov transition rule. Teh et al. (2006) showed how the HDP can be applied to the HMM to allow for infinite state support, thus creating a nonparametric hidden Markov model, where the number of underlying states is inferred. DILN can be adapted to this problem as well, in this case modeling correlations between state transition probabilities.

Appendix

2 Variational inference for normalized gamma measures

We have dropped the group index $m$ for clarity. A new term $\xi$ is introduced into the model as an auxiliary parameter. Changing this parameter changes the tightness of the lower bound, and in fact, it can be removed by permanently tightening it,

Under a factorized $Q$ distribution, the variational lower bound at nodes $Z_{1:T}$ is

Rather than calculate for a specific $q$ distribution on $Z_{k}$, we use the procedure discussed by Winn and Bishop (2005) for finding the optimal form and parameterization of a given $q$: We exponentiate the variational lower bound in Equation (47) with all expectations involving the parameter of interest not taken. For $Z_{k}$, this gives

References