Indian Buffet Processes with Power-law Behavior

Yee Whye Teh, Dilan GörürNeurIPS 2009 · OpenReview

In the world of Bayesian nonparametrics, the Indian Buffet Process (IBP) is a foundational tool for "featural models"—models that describe objects (like images or documents) using an unbounded set of latent features. However, the standard IBP has a notable limitation: it does not naturally capture the "power-law" distributions ubiquitous in real-world data, such as the frequency of words in a book or the popularity of social media tags.

In this paper, researchers introduce a three-parameter generalization of the IBP that brings power-law behavior to featural modeling. By proposing the stable-beta process—a generalization of the beta process—the authors enable the IBP to exhibit power-law growth in features, better capturing the "heavy-tailed" nature of empirical data and improving performance in downstream tasks like document classification.

The Problem: Logarithmic vs. Polynomial Growth

Standard nonparametric models often assume that the number of unique features grows logarithmically with the number of observations. While mathematically convenient, this assumption frequently contradicts reality. In linguistics, for example, Zipf’s Law dictates that a few words are extremely common, while a massive "long tail" of rare words makes up a significant portion of the vocabulary.

In the realm of clustering, the Pitman-Yor process solved a similar issue by adding a "discount" parameter to the Dirichlet process, yielding power-law clusters. This paper seeks the equivalent mechanism for featural models. The objective is to design a model where the number of features grows polynomially ($O(n^\sigma)$) rather than logarithmically, allowing for a much richer representation of rare, long-tail features.

Methods: The Stable-Beta Process

To achieve power-law dynamics, the authors generalize the underlying "de Finetti measure" of the IBP.

  1. The Stable-beta Process (SBP): They define a new Completely Random Measure (CRM) called the stable-beta process. This introduces a third parameter, $\sigma \in (0, 1)$ (the stability exponent), alongside the traditional $\alpha$ (mass) and $c$ (concentration).
  2. The Generalized IBP: By integrating out the SBP, they derive a modified set of rules for the classic "Indian Buffet" analogy:
  3. Customer 1 tries a Poisson($\alpha$) number of dishes.
  4. Customer $n+1$ tries a previously sampled dish $k$ with probability $\frac{m_k - \sigma}{n + c}$ (where $m_k$ is the number of people who previously tried it).
  5. Customer $n+1$ then tries a Poisson number of new dishes, where the rate is controlled by a formula involving Gamma functions that ensures power-law growth.
  6. Stick-breaking Construction: The authors also provide a stick-breaking representation for the process, which is essential for building practical inference algorithms.

Key Insights and Ideas

  • The Power of the Discount: The term $(m_k - \sigma)$ is the theoretical secret sauce. By subtracting a small constant $\sigma$ from the popularity count, the model effectively "taxes" popular features. This makes room for a steady stream of new, rare features to enter the buffet.
  • Polynomial Growth: In a standard IBP ($\sigma=0$), the number of features $K$ grows as $O(\log n)$. In this power-law version, $K$ grows as $O(n^\sigma)$. This represents a fundamental shift in how the model scales with data.
Mean number of features (dishes) grows polynomially with the number of observations (customers) for $\sigma > 0$, compared to logarithmic growth when $\sigma = 0$.
  • Bridge to Pitman-Yor: The authors demonstrate that the stable-beta process has deep mathematical links to the Pitman-Yor process, effectively unifying power-law theory across both clustering (mutually exclusive assignments) and featural models (overlapping assignments).

Empirical Results

The primary evaluation is performed on the 20newsgroups dataset, a standard benchmark for text mining. The authors treat each newsgroup as a separate corpus to test how well the model captures word occurrence patterns.

  • Superior Data Fit: When fitting the 20newsgroups data, the stable-beta process (SBP) matched the actual power-law statistics of the word distributions far better than the standard beta process (BP).
The Stable-beta Process (SBP) closely matches the empirical power-law distribution of word frequencies in real data, whereas the standard Beta Process (BP) falls short.
  • Improved Classification: In document categorization tasks, the SBP consistently outperformed the BP. For example, using a 20/20/60 split (train/validation/test), the SBP achieved a top-1 accuracy of 79.9% compared to the BP's 78.7%.
  • Empirical Evidence of $\sigma$: The Maximum Likelihood estimate for the stability exponent $\sigma$ on the newsgroup data was approximately 0.47. This strongly confirms that real-world text follows a power-law distribution that the standard IBP cannot capture.

Limitations and Future Work

While the SBP provides a significant representational advantage, it introduces new challenges:

  • Computational Complexity: The "inverse Lévy measure" method for stick-breaking requires numerical integration, which is computationally expensive and relies on iterative solvers.
  • Hierarchical Challenges: Defining a "Hierarchical Stable-beta Process" is difficult when dealing with atomic base distributions, remaining an open research question for topic modeling applications.
  • Inference Efficiency: The paper focuses on the model's theoretical properties and basic ML estimation. Developing more efficient Markov Chain Monte Carlo (MCMC) or Variational Inference schemes specifically tailored for the SBP is a natural next step for scaling the model to massive datasets.

Summary updated

Abstract

The Indian buffet process (IBP) is an exchangeable distribution over binary matrices used in Bayesian nonparametric featural models. In this paper we propose a three-parameter generalization of the IBP exhibiting power-law behavior. We achieve this by generalizing the beta process (the de Finetti measure of the IBP) to the \emph{stable-beta process} and deriving the IBP corresponding to it. We find interesting relationships between the stable-beta process and the Pitman-Yor process (another stochastic process used in Bayesian nonparametric models with interesting power-law properties). We show that our power-law IBP is a good model for word occurrences in documents with improved performance over the normal IBP.
BibTeX
@inproceedings{teh2009indian,
  author = {Yee Whye Teh and Dilan Görür},
  title = {{Indian Buffet Processes with Power-law Behavior}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=BJ49IvbdZS},
}
Figure