Abstract
The implementation of collapsed Gibbs samplers for non-parametric Bayesian models is non-trivial, requiring considerable book-keeping. Goldwater et al. (2006a) presented an approximation which significantly reduces the storage and computation overhead, but we show here that their formulation was incorrect and, even after correction, is grossly inaccurate. We present an alternative formulation which is exact and can be computed easily. However this approach does not work for hierarchical models, for which case we present an efficient data structure which has a better space complexity than the naive approach.
Introduction
In unsupervised natural language processing (NLP), Nonparametric Bayesian models like the Dirichlet Process (DP) are essential for handling unknown numbers of categories, such as topic types or word clusters. Implementing these models typically involves collapsed Gibbs sampling, often conceptualized through the Chinese Restaurant Process (CRP). In this metaphor, word tokens are "customers" seated at "tables" (clusters), and each table serves a "dish" (a word type).
A major challenge in these implementations is bookkeeping. To calculate conditional probabilities, one must track the number of tables serving each dish. Naive implementations track every customer-to-table assignment, leading to significant memory overhead. While previous influential work (Goldwater et al., 2006a) proposed an approximation based on expected counts to mitigate this, this paper demonstrates that the approximation is mathematically flawed and performs poorly in the sparse data regimes typical of NLP.
Methods: Beyond Naive Bookkeeping
The authors propose two distinct improvements depending on the model's complexity.
Simple (Non-Hierarchical) Models
For standard DPs, the authors derive an exact $O(1)$ formula for the expected number of tables. By leveraging the relationship between harmonic numbers and the Digamma function ($\psi$), they provide a method to calculate these counts precisely and instantaneously, rendering the flawed previous approximations obsolete.
Hierarchical Models (HDPs)
In hierarchical models, the base distribution is dynamic, making closed-form approximations inaccurate. Instead of approximating, the authors introduce a novel data structure: the Histogram of Table Occupancy.
Since customers at the same table are exchangeable, the specific assignment of a customer to a table is irrelevant. The histogram method stores only the distribution of table sizes for each word type (e.g., "two tables with one customer, one table with five customers"). This captures all necessary information for exact sampling while maintaining a much smaller memory footprint than naive tracking.
Key Results
The primary contribution is the identification and correction of the error in the widely used "Antoniak approximation" (GGJ06). The authors show that the previous formula omitted a crucial factor, leading to significant divergence from actual values.
As shown in the empirical evaluation using the Wall Street Journal (WSJ) corpus, the Digamma-based formula perfectly aligns with the expected number of tables. In contrast, the previous approximation diverges sharply as word frequency ($n_w$) increases, particularly in the sparse settings (small concentration parameter $\alpha$) favored in NLP research.
Discussion and Conclusion
The "Histogram" method establishes a new "gold standard" for HDP implementations. It offers a "middle way" that is more memory-efficient than naive tracking without sacrificing the accuracy lost in previous approximations. While this work solves the bookkeeping problem for HDPs and Pitman-Yor processes, a truly $O(1)$ closed-form approximation for hierarchical models remains elusive. Future research may yet uncover an exact $O(1)$ method that does not require the dynamic memory management of the histogram approach.
Summary updated