# 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 .