Variational Inference for the Nested Chinese Restaurant Process

Chong Wang, David M. BleiNeurIPS 2009 · OpenReview

Introduction

Learning hierarchical structures—such as a taxonomy of topics in a text corpus or a hierarchy of features in images—is a classic challenge in machine learning. The Nested Chinese Restaurant Process (nCRP) is a powerful non-parametric Bayesian model designed for exactly this purpose. It allows data to be organized into a tree of infinite depth and branching factor without requiring researchers to pre-specify the tree's exact shape.

However, computing the posterior distribution (the probability of a specific tree structure given the data) for the nCRP is mathematically intractable. Historically, researchers have relied almost exclusively on Markov Chain Monte Carlo (MCMC) methods, such as Gibbs sampling, to approximate this. While flexible, MCMC is notoriously slow to converge, difficult to scale to massive datasets, and hard to evaluate for convergence.

This paper introduces a Variational Inference (VI) framework for the nCRP. By replacing slow MCMC sampling with a faster, optimization-based approach, the authors provide a scalable way to learn both the parameters and the combinatorial structure of infinite trees.

Methods: Bridging nCRP and Variational Inference

The authors bridge the gap between the nCRP and Variational Inference through three key innovations:

1. Tree-Based Stick-Breaking

To utilize VI, a functional representation of the model is required. The authors derived a novel stick-breaking construction specifically for the nCRP.

Tree-based stick-breaking construction

Imagine a "stick" representing total probability. At the root of the tree, a piece is broken off for the current node, and the remainder is recursively broken for its children. This elegant construction allows the infinite tree to be represented by a collection of Beta-distributed random variables, making it amenable to variational methods.

2. Variational Objective

They define a simplified "variational distribution" and use coordinate ascent to minimize the Kullback-Leibler (KL) divergence between this proxy distribution and the true, complex posterior.

3. Dynamic Structure Discovery

Unlike standard VI, which typically operates on a fixed set of parameters, this algorithm actively searches the combinatorial space of trees. The authors implement four heuristic operations to dynamically refine the tree structure during optimization:

  • Grow: Adds new paths to accommodate unexplained data.
  • Prune: Removes paths with negligible probability assignments.
  • Merge: Combines paths that produce nearly identical posterior distributions.
  • Split: (Specifically for continuous data) Divides a node to better capture data variance.

Experimental Results

The authors evaluated their variational approach on both discrete text data (Hierarchical Topic Modeling) and continuous image data (Hierarchical Component Analysis).

Competitive Accuracy and Efficiency

On text datasets (including abstracts from JACM, Psychological Review, and PNAS), the variational approach achieved test-set likelihoods that were highly competitive with traditional Gibbs sampling. This proves that the variational approximation does not sacrifice significant model quality. Furthermore, the VI approach proved highly efficient. For instance, the Hierarchical Component Analysis (HCA) models for handwritten digits—including the complex structure learning phase—ran in under two minutes, representing a massive speedup over typical MCMC runtimes.

Interpretability and Intuitive Taxonomies

The dynamic structure discovery heuristics ("Grow" and "Merge") successfully discovered intuitive, readable taxonomies from the data.

Example of a learned topic hierarchy

As seen in the learned hierarchies, the model naturally groups related concepts (e.g., separating networking topics from logic programming or complexity theory), demonstrating that the optimization process finds semantically meaningful structures.

Generalization Beyond Text

The paper also demonstrates that the nCRP is not limited to text. By swapping the base distribution (e.g., from Dirichlet to Gaussian), the same hierarchical framework performs Hierarchical Component Analysis (HCA) on continuous data. In experiments with UCI Handwritten Digits, the HCA model achieved significantly lower reconstruction errors on test data compared to standard Principal Component Analysis (PCA).

Limitations and Future Work

While a significant step forward, the approach has limitations. Like all coordinate ascent methods, the algorithm is susceptible to getting stuck in local optima, which the authors mitigate using multiple restarts and careful initialization. Additionally, while the "Prune" and "Merge" heuristics keep the tree size manageable, they can theoretically decrease the variational lower bound, though this effect was negligible in practice. Finally, scaling this combinatorial search to much deeper hierarchies (beyond the depth of $L=3$ used in the text experiments) remains an exciting open area for future exploration.

Summary updated

Abstract

The nested Chinese restaurant process (nCRP) is a powerful nonparametric Bayesian model for learning tree-based hierarchies from data. Since its posterior distribution is intractable, current inference methods have all relied on MCMC sampling. In this paper, we develop an alternative inference technique based on variational methods. To employ variational methods, we derive a tree-based stick-breaking construction of the nCRP mixture model, and a novel variational algorithm that efficiently explores a posterior over a large set of combinatorial structures. We demonstrate the use of this approach for text and hand written digits modeling, where we show we can adapt the nCRP to continuous data as well.
BibTeX
@inproceedings{wang2009variational,
  author = {Chong Wang and David M. Blei},
  title = {{Variational Inference for the Nested Chinese Restaurant Process}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=SkZfZDbdbS},
}
Figure