Parallel Sampling of HDPs using Sub-Cluster Splits

Jason Chang, John W. Fisher IiiNeurIPS 2014

Overview

Hierarchical Dirichlet Processes (HDPs) are considered the "gold standard" for discovering latent groups or topics across collections of documents. However, they face a major hurdle: inference speed. Researchers typically have to choose between Variational Inference (which is fast and parallelizable but lacks theoretical guarantees of finding the true posterior) and Markov Chain Monte Carlo (MCMC) methods (which provide theoretical guarantees but are notoriously slow and prone to getting stuck in local optima).

This paper introduces a parallel MCMC sampling algorithm for HDPs that significantly accelerates convergence using "sub-cluster" split and merge moves. By proposing global moves that reassign data across all topics simultaneously, the authors successfully scale HDP inference to massive datasets (up to 100 million words). Furthermore, they demonstrate that traditional cross-validation metrics can be dangerously misleading when judging model convergence.

Methodology: Scaling HDP Inference

Previous attempts to fix MCMC with "split-merge" moves were either not parallelizable or only worked for simpler models like the standard Dirichlet Process. The authors build on the "DP Sub-Cluster" algorithm, adapting it for the more complex, overlapping hierarchy of the HDP.

Graphical models comparing standard HDP approaches with the Augmented DA Model.

Their approach relies on four main pillars:

1. Restricted Parallel Sampling

The algorithm uses a version of the HDP where the number of topics is temporarily fixed. This allows different processors to sample document-specific topics in parallel without interfering with each other, achieving near-linear speedups as more processors are added.

2. Sub-Cluster Augmentation

For every active topic, the algorithm maintains two "sub-topics" (left and right). These act as a "proposing ground." If the data in a topic starts naturally splitting into these two sub-topics over time, the algorithm uses this as a strong hint to propose a formal split.

Visualization of topics (solid lines) and sub-topics (dashed lines) capturing potential data splits.

3. Global Split/Merge Moves

This is the paper's most critical innovation. In standard DPs, "local" moves (splitting one cluster) are often sufficient. In HDPs, however, topics overlap significantly across documents. The authors found that to break out of poor local optima, you must propose global moves—reassigning data across all topics at once.

4. Deferred Metropolis-Hastings (MH)

To maintain computational efficiency, the algorithm only proposes splits for topics where the sub-clusters have already "burned in" (reached a stable state). This saves valuable computational cycles that would otherwise be wasted on premature split proposals.

Key Insights

  • The "Global" Necessity: Because HDP topics share a global base distribution, a local split in one document often requires adjustments in others. The authors show that without global moves, the sampler frequently fails to reach the correct number of topics.
  • The Cross-Validation Trap: A major discovery in the paper is that held-out likelihood (cross-validation) is a poor indicator of MCMC convergence. The authors observed cases where the likelihood score looked stable, suggesting convergence, but the number of inferred topics was still wildly incorrect. To truly judge convergence, one must look at joint statistics (likelihood and topic count).

Datasets and Results

The authors evaluated their method across a range of scales, from a 200-document synthetic toy dataset to the massive NYTimes Articles dataset containing 100 million words in 300K documents—roughly 400x larger than what previous HDP split-merge samplers could handle.

  • Convergence Speed: On the standard Associated Press (AP) benchmark, the proposed Sub-Cluster method converged to the correct number of topics (~20) much faster than standard Direct Assignment (DA) or Finite Symmetric Dirichlet (FSD) samplers, which often stalled at 100+ topics.
  • Massive Scaling: While no algorithm fully "converged" within 28 hours on the 100M-word NYTimes dataset, the Sub-Cluster method was the only one clearly trending toward a stable, high-likelihood solution. Competing methods had yet to even begin pruning unnecessary topics.
  • Qualitative Clarity: Confusion matrices demonstrated that the Sub-Cluster method produced much more distinguishable topics compared to other methods, which often left many topics redundant or easily confused.

Limitations and Future Work

While highly effective, the approach has a few limitations:

  • Approximation in Hastings Ratios: To make global merges computationally feasible, the authors used an approximation for the reverse split probability. While backed by intuition, it adds complexity to the theoretical analysis.
  • Small Topic Struggle: The Sub-Cluster method occasionally struggles to create very small, niche topics because it prioritizes large, impactful moves. Alternating between this method and a simpler sampler (like FSD) might offer a "best of both worlds" strategy.
  • Implementation Complexity: Implementing parallel global moves with auxiliary sub-cluster variables is significantly more complex than writing a standard Gibbs sampler.

Summary updated

BibTeX
@inproceedings{chang2014parallel,
  author = {Jason Chang and John W. Fisher III},
  title = {{Parallel Sampling of HDPs using Sub-Cluster Splits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure