Indian buffet process

In the mathematical theory of probability, the Indian buffet process (IBP) is a stochastic process defining a probability distribution over sparse binary matrices with a finite number of rows and an infinite number of columns. This distribution is suitable to use as a prior for models with potentially infinite number of features. The form of the prior ensures that only a finite number of features will be present in any finite set of observations but more features may appear as more data points are observed.

Indian buffet process prior

Let $Z$ be an $N\times K$ binary matrix indicating the presence or absence of a latent feature. The IBP places the following prior on $Z$:

$p(Z)=\frac{{\alpha }^{K^{+}}}{\prod _{i=1}^N{K}_1^{(i)}!}\exp \{-\alpha H_N\}\prod _{k=1}^{K^{+}}\frac{(N-m_k)!(m_k-1)!}{N!}$

where $K$ is the number of non-zero columns in $Z$, $m_k$ is the number of ones in column $k$ of $Z$, $H_N$ is the $N$-th harmonic number, and $K_1^{(i)}$ is the number of new dishes sampled by the $i$-th customer. The parameter $\alpha$ controls the expected number of features present in each observation.

In the Indian buffet process, the rows of $Z$ correspond to customers and the columns correspond to dishes in an infinitely long buffet. The first customer takes the first $\mathrm{P}\mathrm{o}\mathrm{i}\mathrm{s}\mathrm{s}\mathrm{o}\mathrm{n}(\alpha )$ dishes. The $i$-th customer then takes dishes that have been previously sampled with probability $m_k/i$, where $m_k$ is the number of people who have already sampled dish $k$. He also takes $\mathrm{P}\mathrm{o}\mathrm{i}\mathrm{s}\mathrm{s}\mathrm{o}\mathrm{n}(\alpha /i)$ new dishes. Therefore, $z_{nk}$ is one if customer $n$ tried the $k$-th dish and zero otherwise.

This process is infinitely exchangeable for an equivalence class of binary matrices defined by a left-ordered many-to-one function. $\mathrm{lof}(Z)$ is obtained by ordering the columns of the binary matrix $Z$ from left to right by the magnitude of the binary number expressed by that column, taking the first row as the most significant bit.

See also

• Chinese restaurant process

References

• T.L. Griffiths and Z. Ghahramani The Indian Buffet Process: An Introduction and Review, Journal of Machine Learning Research, pp. 1185–1224, 2011.