the Indian Buffet Process: An Introduction and Review

The Indian Buffet Process (IBP) is one of Bayesian nonparametric models, which is a prior measure on an infinite binary matrix. Unlike the Dirichlet process(DP), where each atom has negative correlation, IBP assumes each atom is independent.

Introduction

IBP is often used in factor analysis as a prior of infinite factors.

IBP can be viewed as an extension of DP, where we drop the constraint [math]\displaystyle{ \sum_{i=1}^{\inf}{\pi_i}=1 }[/math].

Because we drop the constraint, it does not naturally use IBP as a prior of mixture models.

Representations

Like DP, IBP has several representations.

the limiting of finite distribution on sparse binary feature matrices

We have N data points and K features and the possession of feature k by data point i is indicated by a binary variable [math]\displaystyle{ z_{ik} }[/math] The generative process of the binary feature matrix is defined as below:

• for each feature k
  • for each data point i

• • • [math]\displaystyle{ \pi_k }[/math] ~ [math]\displaystyle{ Beta(\frac{\alpha}{K},1) }[/math]

• • • [math]\displaystyle{ z_{ik} }[/math] ~ [math]\displaystyle{ Bernoulli(\pi_k) }[/math]

where [math]\displaystyle{ \alpha }[/math] is a hyper-parameter, which is similar to the parameter defined in DP. When K goes into infinite, such generative process will become IBP.

stick breaking construction

• For each feature k
  • [math]\displaystyle{ \mu_k }[/math] ~ [math]\displaystyle{ Beta(\alpha,1) }[/math]
  • [math]\displaystyle{ \pi_{k}=\prod_{l=1}^{k}(\mu_l) }[/math]
  • For each data point i
    • [math]\displaystyle{ z_{ik} }[/math] ~ [math]\displaystyle{ Bernoulli(\pi_k) }[/math]

the Indian buffet metaphor

N customers enter a restaurant one after another. Each customer encounters a buffet consisting of infinitely many dishes arranged in a line. The first customer starts at the left of the buffet and takes a serving from each dishes, stopping after a [math]\displaystyle{ Poisson(\alpha) }[/math] number of dishes as his plate becomes overburdened.

The ith customer moves along the buffet,sampling dishes in proportion to their popularity, serving himself with probability [math]\displaystyle{ \frac{m_k}{i} }[/math], where m_k is the number of previous customers who have sampled a dish. Having reached the end of all previous sampled dishes, the ith customer then tries a [math]\displaystyle{ Poisson(\frac{\alpha}{i}) }[/math] number of new dishes.

Inference

Like DP, we can use MCMC sampling framework based on sticking breaking construction and the Indian buffet metaphor to stimulate random samples from IBP.

Application

Due to the fact of IBP that each atom in IBP is independent, IBP can be used as a building block to construct a hierarchical mixture model.

In the Indian Buffet Process compound Dirichlet process model (IBPCDP), the authors proposed to use IBP to select independent weight and then to use DP to normalize these weights. The model is closed related to hierarchical Dirichlet process(HDP), where the top level and down level are both drawn from DP.

References

Williamson, Sinead, et al. "The IBP compound Dirichlet process and its application to focused topic modeling." (2010).

Griffiths, Thomas L., and Zoubin Ghahramani. "The Indian Buffet Process: An Introduction and Review." Journal of Machine Learning Research 12 (2011): 1185-1224.