In probability theory, the Chinese restaurant process is a discrete-time stochastic process, analogous to seating customers at tables in a restaurant. Imagine a restaurant with an infinite number of circular tables, each with infinite capacity. Customer 1 sits at the first table. The next customer either sits at the same table as customer 1, or the next table. This continues, with each customer choosing to either sit at an occupied table with a probability proportional to the number of customers already there (i.e., they are more likely to sit at a table with many customers than few), or an unoccupied table. At time n, the n customers have been partitioned among mn tables (or blocks of the partition). The results of this process are exchangeable, meaning the order in which the customers sit does not affect the probability of the final distribution. This property greatly simplifies a number of problems in population genetics, linguistic analysis, and image recognition.

The restaurant analogy first appeared in a 1985 write-up by David Aldous, where it was attributed to Jim Pitman (who additionally credits Lester Dubins).

An equivalent partition process was published a year earlier by Fred Hoppe, using an "urn scheme" akin to Pólya's urn. In comparison with Hoppe's urn model, the Chinese restaurant process has the advantage that it naturally lends itself to describing random permutations via their cycle structure, in addition to describing random partitions.

Formal definition

.

" is either:

1. is the size of the block (i.e. number of elements), or

2. .

The random partition so generated has some special properties. It is exchangeable does not change the distribution of the partition, and it is consistent.

The probability assigned to any particular partition (ignoring the order in which customers sit around any particular table) is

.

can be interpreted as the effective number of customers sitting at the first empty table.

Alternative definition

An equivalent, but subtly different way to define the Chinese restaurant process, is to let new customers choose companions rather than tables..

Distribution of the number of tables

The Chinese restaurant table distribution (CRT) is the probability distribution on the number of tables in the Chinese restaurant process. independent Bernoulli random variables, each with a different parameter:

is given by

denotes Stirling numbers of the first kind.

Two-parameter generalization

, commonly called the strength (or concentration) and discount occupied tables and decides to sit at an empty table with probability

with probability

In order for the construction to define a valid probability measure.

that satisfy the above-mentioned constraints) in terms of the Pochhammer k-symbol, as

is the rising factorial is the falling factorial is an upper bound on the number of blocks in the partition; see the subsection on the Dirichlet-categorical model below for more details.

, the partition probability can be rewritten in terms of the Gamma function as

this simplifies to

As before, the probability assigned to any particular partition depends only on the block sizes, so as before the random partition is exchangeable in the sense described above. The consistency property still holds, as before, by construction.

, the probability distribution of the random partition of the integer thus generated is the Ewens distribution, used in population genetics and the unified neutral theory of biodiversity.

Derivation

. Then

as above.

Expected number of tables

, the number of tables is distributed according to the chinese restaurant table distribution seated customers, is

is the digamma function, the expected number of occupied tables is

is the rising factorial (as defined above).

The Dirichlet-categorical model

, the two-parameter Chinese restaurant process is equivalent to the Dirichlet-categorical model. If we choose to identify tables with labels, the hierarchical model first draws a categorical label distribution from the symmetric Dirichlet distribution. Since the Dirichlet distribution is conjugate can be marginalized out to obtain the posterior predictive distribution previous labels

unoccupied tables, also agrees with the general formula and is given by

The marginal probability for the labels is given by

is the rising factorial. In general, there are however multiple label states that all correspond to the same blocks, the number of label states that all correspond to this partition is given by the falling factorial. Taking this into account, the probability for the partition is

, as required.)

Relationship between Dirichlet-categorical and one-parameter CRP

large.

Stick-breaking process

The two-parameter Chinese restaurant process can equivalently be defined in terms of a stick-breaking process., the stick breaking process can be described as a hierarchical model, much like the above Dirichlet-categorical model, the components of which are sampled using stick breaking-th break is sampled from the beta distribution:

The categorical probabilities are:

from an ordinary Dirchlet distribution as explained above, but it can also be sampled with a truncated stick-breaking recipe, where the formula for sampling the fractions is modified to:

.

The Indian buffet process

It is possible to adapt the model such that each data point is no longer uniquely associated with a class (i.e., we are no longer constructing a partition), but may be associated with any combination of the classes. This strains the restaurant-tables analogy and so is instead likened to a process in which a series of diners samples from some subset of an infinite selection of dishes on offer at a buffet. The probability that a particular diner samples a particular dish is proportional to the popularity of the dish among diners so far, and in addition the diner may sample from the untested dishes. This has been named the Indian buffet process and can be used to infer latent features in data.

Applications

The Chinese restaurant process is closely connected to Dirichlet processes and Pólya's urn scheme, and therefore useful in applications of Bayesian statistics including nonparametric Bayesian methods. The Generalized Chinese Restaurant Process is closely related to Pitman–Yor process. These processes have been used in many applications, including modeling text, clustering biological microarray data, biodiversity modelling, and image reconstruction

See also

• Ewens sampling formula

• Preferential attachment

• Hilbert's paradox of the Grand Hotel

References

External links

• Introduction to the Dirichlet Distribution and Related Processes by Frigyik, Kapila and Gupta

A talk by Michael I. Jordan on the CRP:

• http://videolectures.net/icml05_jordan_dpcrp/