Particle Filter Rejuvenation and Latent Dirichlet Allocation

We extend a popular model, latent Dirichlet allocation (LDA), to unbounded streams of documents. In order for inference to be practical in this setting it must use constant space asymptotically and run in pseudo-linear time, perhaps $O\left(n\right)$ or $O\left(n\log n\right)$.

Canini et al. (2009) presented a method for LDA inference based on particle filters, where a sample set of models is updated online with each new token observed from a stream. In general, these models should be regularly resampled and rejuvenated using Markov Chain Monte Carlo (MCMC) steps over the history in order to improve the efficiency of the particle filter [10]. The particle filter of Canini et al. (2009) rejuvenates over independent draws from the history by storing all past observations and states. This algorithm thus has linear storage complexity and is not an online learning algorithm in a strict sense [6].

In the current work we propose using reservoir sampling in the rejuvenation step to reduce the storage complexity of the particle filter to $O\left(1\right)$. This improvement is practically useful in the large-data setting and is also scientifically interesting in that it recovers some of the cognitive plausibility which originally motivated Börschinger and Johnson (2012). However, in experiments on the dataset studied by Canini et al. (2009), we show that rejuvenation does not benefit the particle filter’s performance. Rather, performance is dominated by the effects of random initialization (a problem for which we provide a correction while abiding by the same constraints as Canini et al. (2009)). This result re-opens the question of whether rejuvenation is of practical importance in online learning for static Bayesian models.

For a sequence of $N$ words collected into documents of varying length, we denote the $j$-th word as $w_j$, and the document it occurs in as $d_i$. LDA [3] “explains” the occurrence of each word by postulating that a document was generated by repeatedly: (1) sampling a topic $z$ from ${\theta }^{\left(d\right)}$, the document-specific mixture of $T$ topics, and (2) sampling a word $w$ from ${\varphi }^{\left(z\right)}$, the probability distribution the $z$-th topic defines over the vocabulary.

The goal is to infer $\theta$ and $\varphi$, under the model:

Computing $\varphi$ and $\theta$ exactly is generally intractable, motivating methods for approximate inference such as variational Bayesian inference [3], expectation propagation [17], and collapsed Gibbs sampling [11].

A limitation of these techniques is they require multiple passes over the data to obtain good samples of $\varphi$ and $\theta$. This requirement makes them impractical when the corpus is too large to fit directly into memory and in particular when the corpus grows without bound. This motivates online learning techniques, including sampling-based methods [2, 7] and stochastic variational inference [12, 15, 13]. However, where these approaches generally assume the ability to draw independent samples from the full dataset, we consider the case when it is infeasible to access arbitrary elements from the history. The one existing algorithm that can be directly applied under this constraint, to our knowledge, is the streaming variational Bayes framework [4] in which the posterior is recursively updated as new data arrives using a variational approximation.

[t]

Particle filters are a family of sequential Monte Carlo (SMC) sampling algorithms designed to estimate the posterior distribution of a system with dynamic state [8]. A particle filter approximates the posterior by a weighted sample of points, or particles, from the state space. The particle cloud is updated recursively for each new observation using importance sampling (an approach called sequential importance sampling).

Canini et al. (2009) apply this approach to LDA after analytically integrating out $\varphi$ and $\theta$, obtaining a Rao-Blackwellized particle filter [9] that estimates the collapsed posterior $𝐏(𝐳\mid 𝐰)$. In this setting, the $P$ particles are samples of the topic assignment vector ${𝐳}^{\left(p\right)}$, and they are propagated forward in state space one token at a time. In general, the larger $P$ is, the more accurately we approximate the posterior; for small $P$, the approximation of the tails of the posterior will be particularly poor [19]. However, a larger value of $P$ increases the runtime and storage requirements of the algorithm.

We now describe the Rao-Blackwellized particle filter for LDA in detail (pseudocode is given in Algorithm 3). At the moment token $i$ is observed, the particles form a discrete approximation of the posterior up to the $\left(i-1\right)$-th word:

where $I_{𝐳}\left({𝐳}^{\prime }\right)$ is the indicator function, evaluating to 1 if $𝐳={𝐳}^{\prime }$ and 0 otherwise. Now each particle $p$ is propagated forward by drawing a topic $z_i^{\left(p\right)}$ from the conditional posterior distribution $𝐏(z_i^{\left(p\right)}\mid {𝐳}_{i-1}^{\left(p\right)},{𝐰}_i)$ and scaling the particle weight by $𝐏(w_i\mid {𝐳}_{i-1}^{\left(p\right)},{𝐰}_{i-1})$. The particle cloud now approximates the posterior up to the $i$-th word:

Dropping the superscript $\left(p\right)$ for notational convenience, the conditional posterior used in the propagation step is given by

where $n_{z_i,i\backslash i}^{\left(w_i\right)}$ is the number of times word $w_i$ has been assigned topic $z_i$ so far, $n_{z_i,i\backslash i}^{(\cdot )}$ is the number of times any word has been assigned topic $z_i$, $n_{z_i,i\backslash i}^{\left(d_i\right)}$ is the number of times topic $z_i$ has been assigned to any word in document $d_i$, and $n_{\cdot ,i\backslash i}^{\left(d_i\right)}$ is the number of words observed in document $d_i$. The particle weights are scaled as

where $Q$ is the proposal distribution for the particle state transition; in our case,

minimizing the variance of the importance weights conditioned on ${𝐰}_i$ and ${𝐳}_{i-1}$ [9].

Over time the particle weights tend to diverge. To combat this inefficiency, after every state transition we estimate the effective sample size (ESS) of the particle weights as ${\parallel {\omega }_i\parallel }_2^{-2}$ [14] and resample the particles when that estimate drops below a prespecified threshold. Several resampling strategies have been proposed [9]; we perform multinomial resampling as in Pitt and Shephard (1999) and Ahmed et al. (2011), treating the weights as unnormalized probability masses on the particles.

After resampling we are likely to have several copies of the same particle, yielding a degenerate approximation to the posterior. To reintroduce diversity to the particle cloud we take MCMC steps over a sequence of states from the history [9, 10]. We call the indices of these states the rejuvenation sequence, denoted $ℛ\left(i\right)$ [7]. The transition probability for a state $j\in ℛ\left(i\right)$ is given by

where subscript $N\backslash j$ denotes counts up to token $N$, excluding those for token $j$.

The rejuvenation sequence can be chosen by the practitioner. Choosing a long sequence (large $\left|ℛ\left(i\right)\right|$) may result in a more accurate posterior approximation but also increases runtime and storage requirements. The tokens in $ℛ\left(i\right)$ may be chosen uniformly at random from the history or under a biased scheme that favors recent observations. The particle filter studied empirically by Canini et al. (2009) stored the entire history, incurring linear storage complexity in the size of the stream. Ahmed et al. (2011) instead sampled ten documents from the most recent 1000, achieving constant storage complexity at the cost of a recency bias. If we want to fit a model to a long non-i.i.d. stream, we require an unbiased rejuvenation sequence as well as sub-linear storage complexity.

Reservoir sampling is a widely-used family of algorithms for choosing an array (“reservoir”) of $k$ items. The most common example, presented in Vitter (1985) as Algorithm R, chooses $k$ elements of a stream such that each possible subset of $k$ elements is equiprobable. This effects sampling $k$ items uniformly without replacement, using runtime $O\left(n\right)$ (constant per update) and storage $O\left(k\right)$.

To ensure constant space over an unbounded stream, we draw the rejuvenation sequence $ℛ\left(i\right)$ uniformly from a reservoir. As each token of the training data is ingested by the particle filter, we decide to insert that token into the reservoir, or not, independent of the other tokens in the current document. Thus, at the end of step $i$ of the particle filter, each of the $i$ tokens seen so far in the training sequence has an equal probability of being in the reservoir, hence being selected for rejuvenation.

We evaluate our particle filter on three datasets studied in Canini et al. (2009): diff3, rel3, and sim3. Each of these datasets is a collection of posts under three categories from the 20 Newsgroups dataset.¹¹diff3: {rec.sport.baseball, sci.space, alt.atheism}; rel3: talk.politics.{misc, guns, mideast}; and sim3: comp.{graphics, os.ms-windows.misc, windows.x}. We use a 60% training/40% testing split of this data that is available online.²²http://qwone.com/~jason/20Newsgroups/20news-bydate.tar.gz

We preprocess the data by splitting each line on non-alphabet characters, converting the resulting tokens to lower-case, and filtering out any tokens that appear in a list of common English stop words. In addition, we remove the header of every file and filter every line that does not contain a non-trailing space (which removes embedded ASCII-encoded attachments). Finally, we shuffle the order of the documents. After these steps, we compute the vocabulary for each dataset as the set of all non-singleton types in the training data augmented with a special out-of-vocabulary symbol.

During training we report the out-of-sample NMI, calculated by holding the word proportions $\varphi$ fixed, running five sweeps of collapsed Gibbs sampling on the test set, and computing the topic for each document as the topic assigned to the most tokens in that document. Two Gibbs sweeps have been shown to yield good performance in practice [23]; we increase the number of sweeps to five after inspecting the stability on our dataset. The variance of the particle filter is often large, so for each experiment we perform 30 runs and plot the mean NMI inside bands spanning one sample standard deviation in either direction.

Motivated by a desire for cognitive plausibility, Börschinger and Johnson (2011) used a particle filter to learn Bayesian word segmentation models, following the work of Canini et al. (2009). They later showed that rejuvenation improved performance [6], but this impaired cognitive plausibility by necessitating storage of all previous states and observations. We attempted to correct this by drawing the rejuvenation sequence from a reservoir, but our results indicate that the particle filter for LDA on our dataset is highly sensitive to initialization and not influenced by rejuvenation.

In the experiments of Börschinger and Johnson (2012), the particle cloud appears to be resampled once per utterance with a large rejuvenation sequence;⁴⁴ The ESS threshold is $P$; the rejuvenation sequence is 100 or 1600 utterances, almost one sixth of the training data. each particle takes many more rejuvenation MCMC steps than new state transitions and thus resembles a batch MCMC sampler. In our experiments resampling is done on the order of once per document, leading to less than one rejuvenation step per transition. Future work should carefully note this ratio: sampling history much more often than new states improves performance but contradicts the intuition behind particle filters.

We have also shown that tuning the initial model using in-sample NMI or held-out perplexity can improve mean NMI and reduce variance. Perplexity (or likelihood) is often used to estimate model performance in LDA [3, 11, 22, 12], and does not compare the inferred model against gold-standard labels, yet it appears to be a good proxy for NMI in our experiment. Thus, if initialization continues to be crucial to performance, at least we may have the flexibility of initializing without gold-standard labels.

We have focused on NMI as our evaluation metric for comparison with Canini et al. (2009). However, evaluation of topic models is a subject of considerable debate [22, 23, 18, 16] and it may be informative to investigate the effects of initialization and rejuvenation using other metrics such as perplexity or semantic coherence.

We have proposed reservoir sampling for reducing the storage complexity of a particle filter from linear to constant. This work was motivated as an expected improvement on the model of Canini et al. (2009). However, in the process of establishing an empirical baseline we discovered that rejuvenation does not play a significant role in the experiments of Canini et al. (2009). Moreover, we found that performance of the particle filter was strongly affected by the random initialization of the model, and suggested a simple approach to reduce the variability therein without using additional data. In conclusion, it is now an open question whether—and if so, under what assumptions—rejuvenation benefits particle filters for LDA and similar static Bayesian models.