Indian buffet process


In the mathematical theory of probability, the Indian buffet process 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 be an binary matrix indicating the presence or absence of a latent feature. The IBP places the following prior on :
where is the number of non-zero columns in, is the number of ones in column of, is the Nth harmonic number, and is the number of occurrences of the non-zero binary vector among the columns in. The parameter controls the expected number of features present in each observation.
In the Indian buffet process, the rows of correspond to customers and the columns correspond to dishes in an infinitely long buffet. The first customer takes the first dishes. The -th customer then takes dishes that have been previously sampled with probability, where is the number of people who have already sampled dish. He also takes new dishes. Therefore, is one if customer tried the -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. is obtained by ordering the columns of the binary matrix from left to right by the magnitude of the binary number expressed by that column, taking the first row as the most significant bit.