Indian buffet process

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Indian buffet process" – news · newspapers · books · scholar · JSTOR (June 2017)

|

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

[edit]

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

p ( Z ) = α K + ∏ i = 1 N K 1 ( i ) ! exp ⁡ { − α H N } ∏ k = 1 K + ( N − m k ) ! ( m k − 1 ) ! N ! {\displaystyle 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 {\displaystyle {K}} is the number of non-zero columns in  Z {\displaystyle Z} ,  m k {\displaystyle m_{k}} is the number of ones in column  k {\displaystyle k} of  Z {\displaystyle Z} ,  H N {\displaystyle H_{N}} is the  N {\displaystyle N} -th harmonic number, and  K 1 ( i ) {\displaystyle K_{1}^{(i)}} is the number of new dishes sampled by the  i {\displaystyle i} -th customer. The parameter  α {\displaystyle \alpha } controls the expected number of features present in each observation.

In the Indian buffet process, the rows of  Z {\displaystyle Z} correspond to customers and the columns correspond to dishes in an infinitely long buffet. The first customer takes the first  P o i s s o n ( α ) {\displaystyle \mathrm {Poisson} (\alpha )} dishes. The  i {\displaystyle i} -th customer then takes dishes that have been previously sampled with probability  m k / i {\displaystyle m_{k}/i} , where  m k {\displaystyle m_{k}} is the number of people who have already sampled dish  k {\displaystyle k} . He also takes  P o i s s o n ( α / i ) {\displaystyle \mathrm {Poisson} (\alpha /i)} new dishes. Therefore,  z n k {\displaystyle z_{nk}} is one if customer  n {\displaystyle n} tried the  k {\displaystyle 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.  lof ⁡ ( Z ) {\displaystyle \operatorname {lof} (Z)} is obtained by ordering the columns of the binary matrix  Z {\displaystyle 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

[edit]

* Chinese restaurant process

## References

[edit]

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