Indian buffet process explained

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 x K binary matrix indicating the presence or absence of a latent feature. The IBP places the following prior on Z :p(Z) = (\alpha ^{K ^{+}})/(\prod ^{N} _{i =1} K ^{(i)} _{1} !) \exp\{ - \alpha H _{N\}\prod} ^{K ^{+}} ^{k =1} ((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 ^{(i)} _{1} 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 Poisson (\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 Poisson (\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.

\operatorname{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.