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:

Core resources (read/watch one of the following)

-Free-

A tutorial on Bayesian nonparametric models (2012)
Location: S 2.2

Supplemental resources (the following are optional, but you may find them useful)

-Free-

Bayesian Nonparametrics (2011)
Location: part 2, from 10:00
Author: Yee Whye Teh
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,
Author: Erik Sudderth
Other notes:
  • best read after learning about the Dirichlet Process

See also