Bayesian Nonparametric Models on Decomposable Graphs.

Francois Caron, Arnaud DoucetNeurIPS 2009 · OpenReview

Abstract

Bayesian nonparametric (BNP) models, such as the Chinese Restaurant Process (CRP) and the Indian Buffet Process (IBP), have become standard tools for clustering and latent feature modeling. However, their reliance on the assumption of exchangeability—where the order of data points is irrelevant—limits their applicability to data with inherent structural dependencies. This paper proposes a novel extension of these models to decomposable graphs. By leveraging the Markov properties of these graphs, the authors introduce a framework that supports "local exchangeability." This approach allows for the direct encoding of spatial, temporal, or relational dependencies into the prior distribution, offering a flexible and computationally efficient alternative to traditional hierarchical models.

Introduction: The Challenge of Exchangeability

In standard BNP models, every data point is assumed to be equally related to every other data point. While this simplifies mathematics, it often fails to reflect reality. For instance, in a video stream, consecutive frames are naturally more correlated than distant ones. Similarly, in spatial data, proximity often implies a higher likelihood of belonging to the same cluster.

Existing solutions, like the Hierarchical Dirichlet Process (HDP), address this by introducing complex hierarchies. However, these can be rigid and difficult to scale. This research explores a more direct path: using graph theory to define dependencies. By representing data points as nodes in a graph, we can specify exactly which points should influence each other's latent assignments.

The Framework: Decomposable Graphs and Local Exchangeability

The authors focus on decomposable graphs, which are characterized by their ability to be partitioned into a sequence of cliques (fully connected subgraphs) and separators (the intersections between cliques). This structure is mathematically advantageous because it allows a joint probability distribution over the entire graph to be expressed as a product of marginal distributions over its cliques, normalized by the distributions over the separators.

The key innovation is ensuring that these marginal distributions are consistent. If each clique marginally follows a standard CRP or IBP, and the separators are consistent, the resulting joint distribution is a well-defined Markov distribution. This allows the model to maintain "local exchangeability" within cliques while allowing global structure to emerge through the graph's topology.

The Chinese Wedding Party Process

To make the inference process intuitive, the authors introduce the Chinese Wedding Party Process (CWPP). In a standard CRP, a new guest enters a restaurant and chooses a table based on the total number of people already seated there. In the CWPP, the "restaurant" is structured by the graph.

The Chinese Wedding Party Process (CWPP) on a decomposable graph.

When a guest (data point) arrives, they belong to specific "cliques" (social circles). They choose a table not based on the global population, but based on the number of people they already know from their specific cliques who are already seated. This metaphor perfectly captures how local dependencies drive the clustering process in this new framework.

Applications: From Hierarchies to Time-Series

The flexibility of this graph-based approach allows it to subsume or improve upon existing models:

  • HDP Alternative: The authors demonstrate that the HDP can be represented as a specific type of decomposable graph. By adjusting the graph structure, researchers can create models where the number of clusters scales differently, providing more control over the model's "growth" as data increases.
  • Temporal IBP: By arranging cliques in a chain, the model can represent time-varying latent features. This is particularly efficient because the computational complexity of the inference algorithm depends on the size of the "lag" (the separators between time steps) rather than the total history of the dataset.

Experimental Results

The model was tested on several synthetic tasks to verify its properties. In a time-varying matrix factorization experiment, the authors generated a sequence of 200 binary images based on four shifting latent features.

Recovery of time-varying latent features in synthetic image data.

As shown in the results, the model successfully recovered the true latent features and tracked their presence over time. Notably, the Bayesian prior allowed the model to quickly identify and discard "spurious" features (noise) as more data points were processed. Furthermore, the use of Sequential Monte Carlo (SMC) methods ensured that the inference remained efficient even as the sequence grew, avoiding the matrix inversion bottlenecks common in other temporal models.

Conclusion and Future Directions

This paper provides a powerful new toolkit for Bayesian nonparametrics by bridging the gap between flexible priors and structured dependencies. By using decomposable graphs, the authors achieve a balance between mathematical tractability and modeling realism.

The primary limitation of the current work is the requirement that the graph structure be known in advance. Future research aims to treat the graph itself as a latent variable, allowing the model to "learn" the dependency structure directly from the data. Additionally, extending these concepts to non-decomposable (loopy) graphs remains an open and challenging frontier.

Summary updated

Abstract

Over recent years Dirichlet processes and the associated Chinese restaurant process (CRP) have found many applications in clustering while the Indian buffet process (IBP) is increasingly used to describe latent feature models. In the clustering case, we associate to each data point a latent allocation variable. These latent variables can share the same value and this induces a partition of the data set. The CRP is a prior distribution on such partitions. In latent feature models, we associate to each data point a potentially infinite number of binary latent variables indicating the possession of some features and the IBP is a prior distribution on the associated infinite binary matrix. These prior distributions are attractive because they ensure exchangeability (over samples). We propose here extensions of these models to decomposable graphs. These models have appealing properties and can be easily learned using Monte Carlo techniques.
BibTeX
@inproceedings{caron2009bayesian,
  author = {Francois Caron and Arnaud Doucet},
  title = {{Bayesian Nonparametric Models on Decomposable Graphs.}},
  booktitle = {NeurIPS},
  year = {2009},
  url = {https://openreview.net/forum?id=8VdVifU5aAA},
}
Figure