A Stick-Breaking Construction of the Beta Process

John W. Paisley, Aimee K. Zaas, Christopher W. Woods, Geoffrey S. Ginsburg, Lawrence CarinICML 2010 · OpenReview

Overview

This paper introduces the first fully Bayesian "stick-breaking" construction for the Beta Process, a popular prior for latent factor models. By leveraging a lesser-known property of the Beta distribution, the authors provide a constructive way to represent the process as an infinite sum of weights. This breakthrough enables more direct inference and a clearer understanding of how features are shared across data points.

The Problem: Feature Allocation vs. Clustering

In Bayesian nonparametrics, the Dirichlet Process (DP) is the gold standard for clustering. It has a famous "stick-breaking" representation (Sethuraman, 1994) that makes it intuitive: you break off pieces of a unit-length stick to define the probabilities of belonging to mutually exclusive clusters.

The Beta Process (BP) is the DP's counterpart for "feature allocation"—a scenario where each data point can possess multiple latent features simultaneously (similar to the Indian Buffet Process). While the BP is highly expressive, it lacked a straightforward, constructive stick-breaking representation for the general case. Previous methods either relied on marginalization (which obscures the underlying process) or complex inverse Lévy methods that were notoriously difficult to implement. The authors aim to bridge this gap, providing a constructive definition that is as useful for the Beta Process as Sethuraman’s was for the Dirichlet Process.

Methodology

The core innovation is a novel way to "break the stick" to generate the atoms of a Beta Process.

  1. The Beta Distribution Trick: The authors utilize a mathematical property showing that even a single Beta-distributed random variable can be represented as an infinite stick-breaking process.
  2. The Construction: They define the Beta Process as an infinite collection of these constructions, organized into "rounds" ($i=1, 2, \dots$). In each round, a Poisson-distributed number of new atoms are created. The weight of an atom in round $i$ is determined by taking the $i$-th "break" from an atom-specific stick.
  3. Stochastic Decay: Because the weights are products of many $(1-V)$ terms, they stochastically decrease as the round number $i$ increases. This natural decay allows for practical computational truncation.
  4. Inference via Monte Carlo Integration: To handle the infinite-dimensional nature of the model, the authors derive a Gibbs sampling procedure. They use Monte Carlo integration to integrate out the stick-breaking variables ($V$), significantly reducing the number of parameters the sampler needs to track.

Key Insights

  • Vertical vs. Horizontal View: The derivation relies on a matrix of random variables. Looking "horizontally" across the matrix constructs individual Beta variables; looking "vertically" down the matrix constructs the Beta Process. This dual perspective is the central "aha moment" of the paper.
  • Round-Based Organization: By introducing a latent "round-indicator" variable ($d_k$), the authors turn an abstract infinite sum into a manageable sequence that a computer can sample.

Applications and Results

The authors evaluated their construction on three distinct types of data, demonstrating both its mathematical correctness and practical utility:

1. Synthetic Data (Parameter Recovery)

To verify the inference procedure, the model was tested on synthetic data. The inferred values for hyperparameters $\alpha$ (controlling weight decay) and $\gamma$ (controlling the number of atoms) centered tightly around their true values, proving the mathematical correctness of the construction.

2. MNIST Handwritten Digits

The model was applied as a latent factor model to decompose images of the digits 3, 5, and 8 into constituent strokes and features. It successfully learned distinct "parts" of the digits. For example, it identified specific stroke features (like a top bar) that have a high probability of appearing in a '5' but a low probability in an '8'.

Latent factors learned from MNIST digits 3, 5, and 8, showing specific stroke features and their probabilities.

3. Time-Evolving Gene Expression Data

In a "viral challenge" dataset, 17 volunteers were infected with Influenza A, and 12,023 genes were tracked over 16 time points. The model identified a small set of discriminative genes (e.g., RSAD2, IFI27, and IFI44L) whose expression levels spiked around the 45th hour—before volunteers actually showed clinical symptoms. This aligns perfectly with known biological literature on early immune responses.

Factor loadings over time for symptomatic vs. asymptomatic individuals in the viral challenge dataset, highlighting early immune response genes.

Limitations and Future Work

  • Computational Intensity: The inference relies on heavy Monte Carlo integration ($S=100,000$ samples in some experiments). While accurate, this is computationally expensive compared to simpler marginalized versions of the Indian Buffet Process.
  • Scaling: While analyzing 12,000 genes is a solid benchmark, the average time per iteration (approximately 2 minutes for the gene data) suggests that further optimizations or variational approximations will be necessary for truly "big data" applications.
  • Relationship to IBP: The authors note that for the specific case of $\alpha=1$, their construction should be equivalent to existing Indian Buffet Process constructions, but they leave the formal proof of this equality for future work.

Summary updated

Abstract

We present and derive a new stick-breaking construction of the beta process. The construction is closely related to a special case of the stick-breaking construction of the Dirichlet process (Sethuraman, 1994) applied to the beta distribution. We derive an inference procedure that relies on Monte Carlo integration to reduce the number of parameters to be inferred, and present results on synthetic data, the MNIST handwritten digits data set and a time-evolving gene expression data set.
BibTeX
@inproceedings{paisley2010stick,
  author = {John W. Paisley and Aimee K. Zaas and Christopher W. Woods and Geoffrey S. Ginsburg and Lawrence Carin},
  title = {{A Stick-Breaking Construction of the Beta Process}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=rJ-vWs-_WH},
}

Loading related content...

Figure