Infinite latent feature models and the Indian buffet process

Thomas L. Griffiths, Zoubin GhahramaniNeurIPS 2005 · OpenReview

Introduction

This seminal paper introduces the Indian Buffet Process (IBP), a stochastic process that defines a probability distribution over sparse binary matrices with a finite number of rows and an infinite number of columns. It provides a principled Bayesian framework for "infinite" latent feature models, allowing the number of features used to represent a dataset to be learned directly from the data itself rather than fixed in advance.

The Dimensionality Bottleneck

In unsupervised learning, we often try to represent objects using latent (hidden) variables. Traditional mixture models (like K-means or standard Gaussian Mixture Models) assume each object belongs to exactly one category. However, many objects are better described by multiple overlapping features. For example, a person might be simultaneously "tall," "wearing glasses," and "carrying a bag."

The primary bottleneck in these latent feature models is dimensionality: how many features are enough? Usually, researchers treat this as a model selection problem, testing different fixed values of $K$ (the number of features). This paper proposes a nonparametric Bayesian alternative: assume the true number of features is unbounded, but any finite set of observed objects only manifests a small, sparse subset of those features.

The Indian Buffet Process

The authors derive the IBP by starting with a finite model and taking the limit as the number of features $K$ goes to infinity. To make the mathematics intuitive, they propose a culinary metaphor.

The Culinary Metaphor

Imagine an Indian buffet with an infinite number of dishes (representing latent features):

  1. The First Customer: Enters the buffet and helps themselves to a number of dishes sampled from a $\text{Poisson}(\alpha)$ distribution.
  2. Subsequent Customers ($i$-th):
  3. For each dish already sampled by previous customers, the $i$-th customer tries it with probability $m_k / i$, where $m_k$ is the number of previous people who ate that dish. This creates a "popularity" effect, where commonly used features are more likely to be adopted by new observations.
  4. After trying existing dishes, the customer tries a new set of previously unsampled dishes. The number of new dishes is sampled from a $\text{Poisson}(\alpha/i)$ distribution.

Mathematical Contribution

A key mathematical hurdle in infinite models is ensuring that the probability distribution is well-behaved regardless of the order in which data is observed.

A binary matrix and its left-ordered form (lof).

The authors prove exchangeability—that the order of customers doesn't change the probability of the final "menu" (the binary matrix $\mathbf{Z}$). They achieve this by defining distributions over equivalence classes of matrices, often represented using a left-ordered form (lof), which groups matrices that are identical up to a permutation of their columns.

Furthermore, they derive a Gibbs sampler (a type of Markov Chain Monte Carlo algorithm) that allows researchers to actually compute the posterior distribution of features given observed data.

Experimental Validation

The paper demonstrates the model using a controlled image dataset consisting of 100 images (each $240 \times 320$ pixels). Each image contains between zero and four specific objects: a $20 bill, a Klein bottle, a prehistoric handaxe, and a cellular phone. The goal is for the model to "blindly" discover that these four distinct objects are the underlying latent features that compose the images.

Key Results

  • Feature Discovery: The model successfully identified the four underlying objects. The posterior mean of the weights clearly showed the visual forms of the $20 bill, the handaxe, the bottle, and the phone.
  • Dimensionality Learning: Although the model started with no knowledge of $K$, the MCMC algorithm stabilized at approximately seven latent features. Four of these were the primary objects, while the remaining three captured slight variations in object location or lighting.
  • Convergence: Trace plots showed that the model parameters (such as $\alpha$, noise levels, and the number of active features) stabilized after roughly 100 iterations, demonstrating that the inference algorithm is practical for real-world use.

Key Insights and Future Directions

The IBP represents a natural extension of nonparametric Bayesian methods. While the well-known Chinese Restaurant Process (CRP) is used for infinite mixture models (mapping one object to one class), the IBP is the natural extension for infinite feature models (mapping one object to many features).

The process naturally results in sparse matrices. Even though there are infinite possible features, the number of features possessed by any single object, and the total number of features across $N$ objects, remains finite. The parameter $\alpha$ effectively "penalizes" adding unnecessary features unless the data strongly supports them.

Limitations and Future Work: * Computational Complexity: Gibbs sampling for infinite models can be computationally expensive as the number of objects $N$ grows very large. * Linear Assumptions: The specific application in the paper uses a linear-Gaussian model (where images are sums of features). The authors note that the IBP could be paired with more complex, non-linear likelihood functions. * Binary Constraints: This specific process deals with the presence or absence of features. Future work could extend this to features with discrete or continuous values to represent "how much" of a feature is present.

Summary updated

Abstract

We define a probability distribution over equivalence classes of binary matrices with a finite number of rows and an unbounded number of columns. This distribution is suitable for use as a prior in probabilistic models that represent objects using a potentially infinite array of features. We identify a simple generative process that results in the same distribution over equivalence classes, which we call the Indian buffet process. We illustrate the use of this distribution as a prior in an infinite latent feature model, deriving a Markov chain Monte Carlo algorithm for inference in this model and applying the algorithm to an image dataset.
BibTeX
@inproceedings{griffiths2005infinite,
  author = {Thomas L. Griffiths and Zoubin Ghahramani},
  title = {{Infinite latent feature models and the Indian buffet process}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
  url = {https://openreview.net/forum?id=oLgr18GKhs5},
}
Figure