Chinese restaurant process
(45 minutes to learn)
Summary
The Chinese Restaurant Process (CRP) is a predictive rule that descripes a probability distribution on an unbounded partition (clustering). The CRP is as follows: imagine a chinese restaurant with a countably infinite number of tables, the first customer (datum) walks into a restaurant and sits at a table (cluster), the second customer walks into the restaurant and sits at the first customers table with probability 1/2 and chooses a new table with probability 1/2, the nth customer chooses a previous table with probability proportional to the number of customers at that table and chooses his own table with the remaining probability. Defining the probability from this predictive rule yields a probability distribution on an unbounded clustering.
Context
This concept has the prerequisites:
- Dirichlet distribution (The Chinese restaurant process is the infinite limit of the Dirichlet-multinomial distribution.)
- multinomial distribution (The Chinese restaurant process is the infinite limit of the Dirichlet-multinomial distribution.)
- gamma function (The PMF for the IBP includes the gamma distribution.)
Core resources (read/watch one of the following)
-Free-
→ A tutorial on Bayesian nonparametric models (2012)
Supplemental resources (the following are optional, but you may find them useful)
-Free-
→ Bayesian Nonparametrics (2011)
→ Graphical Models for Visual Object Recognition and Tracking (2006)
Erik Sudderth's Ph.D. thesis, which includes readable overviews of a variety of topics.
Location:
S.2.5.2,
Other notes:
- best read after learning about the Dirichlet Process
See also
- The CRP is often used for Bayesian clustering models .