Chinese Restaurant Process
Jump to navigation
Jump to search
A Chinese Restaurant Process is a discrete-time stochastic process whose value at any positive-integer time [math]\displaystyle{ n }[/math] is a partition [math]\displaystyle{ B_n }[/math] of the set [math]\displaystyle{ \{1, 2, 3, ..., n\} }[/math] whose probability distribution is determined as follows:
At time n = 1, the trivial partition { {1} } is obtained with probability 1. At time n + 1 the element n + 1 is either:
- added to one of the blocks of the partition Bn, where each block is chosen with probability |b|/(n + 1) where |b| is the size of the block, or
- added to the partition Bn as a new singleton block, with probability 1/(n + 1).
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Chinese_restaurant_process Retrieved:2014-5-14.
- In probability theory, the Chinese restaurant process is a discrete-time stochastic process, whose value at any positive-integer time n is a partition Bn of the set {1, 2, 3, ..., n} whose probability distribution is determined as follows. At time n = 1, the trivial partition { {1} } is obtained with probability 1. At time n + 1 the element n + 1 is either:
- added to one of the blocks of the partition Bn, where each block is chosen with probability |b|/(n + 1) where |b| is the size of the block, or
- added to the partition Bn as a new singleton block, with probability 1/(n + 1).
- The random partition so generated is exchangeable in the sense that relabeling {1, ..., n} does not change the distribution of the partition, and it is consistent in the sense that the law of the partition of n − 1 obtained by removing the element n from the random partition at time n is the same as the law of the random partition at time n − 1.
- In probability theory, the Chinese restaurant process is a discrete-time stochastic process, whose value at any positive-integer time n is a partition Bn of the set {1, 2, 3, ..., n} whose probability distribution is determined as follows. At time n = 1, the trivial partition { {1} } is obtained with probability 1. At time n + 1 the element n + 1 is either:
2008
- (Ahmed & Xing, 2008) ⇒ A. Ahmed and Eric Xing. (2008). “Dynamic Non-parametric Mixture Models and the Recurrent Chinese Restaurant Process: With Applications to Evolutionary Clustering.” In: Proceedings of SDM.
2006
- (Teh et al., 2006) ⇒ Yee Whye Teh, Michael I. Jordan, Matthew J. Beal, and David M. Blei. (2006). “Hierarchical Dirichlet Processes.” In: Journal of the American Statistical Association, 101(476). doi:10.1198/016214506000000302
- QUOTE: Given our desire to tie the mixture models in the various groups, we consider a hierarchical model, specifically one in which the base measure for the child Dirichlet processes is itself distributed according to a Dirichlet process. Such a base measure being discrete, the child Dirichlet processes necessarily share atoms. Thus, as desired, the mixture models in the different groups necessarily share mixture components. We discuss representations of hierarchical Dirichlet processes in terms of a stick-breaking process, and a generalization of the Chinese restaurant process that we refer to as the “Chinese restaurant franchise.”