Chinese restaurant process
(45 minutes to learn)
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.
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)
→ A tutorial on Bayesian nonparametric models (2012)
Location: S 2.2
Supplemental resources (the following are optional, but you may find them useful)
→ Bayesian Nonparametrics (2011)
Location: part 2, from 10:00
→ Graphical Models for Visual Object Recognition and Tracking (2006)
Erik Sudderth's Ph.D. thesis, which includes readable overviews of a variety of topics.
- best read after learning about the Dirichlet Process
- The CRP is often used for Bayesian clustering models .
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation