Chinese restaurant process

Short description: Discrete-time stochastic process

For other uses, see Chinese restaurant (disambiguation).

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 m ≤ n 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,[1] where it was attributed to Jim Pitman (who additionally credits Lester Dubins).[2]

An equivalent partition process was published a year earlier by Fred Hoppe,[3] 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.

## Contents

* 1 Formal definition
* 1.1 Alternative definition
* 2 Distribution of the number of tables
* 3 Two-parameter generalization
* 3.1 Derivation
* 3.2 Expected number of tables
* 3.3 The Dirichlet-categorical model
* 3.3.1 Relationship between Dirichlet-categorical and one-parameter CRP
* 3.4 Stick-breaking process
* 4 The Indian buffet process
* 5 Applications
* 6 See also
* 7 References
* 8 External links

## Formal definition

For any positive integer n, let 𝒫n denote the set of all partitions of the set {1,2,3,...,n}≜[n]. The Chinese restaurant process takes values in the infinite Cartesian product ∏n≥1𝒫n.

The value of the process at time n is a partition Bn of the set [n], whose probability distribution is determined as follows. At time n=1, the trivial partition B1={{1}} is obtained (with probability one). At time n+1 the element "n+1" is either:

1. added to one of the blocks of the partition Bn, where each block is chosen with probability |b|/(n+1) where |b| is the size of the block (i.e. number of elements), or
2. added to the partition Bn as a new singleton block, with probability 1/(n+1).

The random partition so generated has some special properties. It is exchangeable in the sense that relabeling {1,...,n} does not change the distribution of the partition, and it is consistent in the sense that the law of the partition of [n−1] obtained by removing the element n from the random partition Bn is the same as the law of the random partition Bn−1.

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

Pr⁡(Bn=B)=∏b∈B(|b|−1)!n!,B∈𝒫n

where b is a block in the partition B and |b| is the size of b.

The definition can be generalized by introducing a parameter θ>0 which modifies the probability of the new customer sitting at a new table to θn+θ and correspondingly modifies the probability of them sitting at a table of size |b| to |b|n+θ. The vanilla process introduced above can be recovered by setting θ=1. Intuitively, θ 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.[4] Customer n+1 chooses to sit at the same table as any one of the n seated customers with probability 1n+θ, or chooses to sit at a new, unoccupied table with probability θn+θ. Notice that in this formulation, the customer chooses a table without having to count table occupancies
we don't need |b|.

## Distribution of the number of tables

Chinese restaurant tableParameters|

θ>0

n∈{1,2,…}

|

Support|  k∈{1,2,…,n}
pmf|  Γ(θ)Γ(n+θ)|s(n,k)|θk
Mean|  θ(ψ(θ+n)−ψ(θ))
(see digamma function)

The Chinese restaurant table distribution (CRT) is the probability distribution on the number of tables in the Chinese restaurant process.[5] It can be understood as the sum of n independent Bernoulli random variables, each with a different parameter:

K=∑i=1nbibi∼Bernoulli⁡(θi−1+θ)

The probability mass function of K is given by [6]

f(k)=Γ(θ)Γ(n+θ)|s(n,k)|θk,k=1,…,n,

where s denotes Stirling numbers of the first kind.

## Two-parameter generalization

This construction can be generalized to a model with two parameters, θ & α,[2][7] commonly called the strength (or concentration) and discount parameters respectively. At time n+1, the next customer to arrive finds |B| occupied tables and decides to sit at an empty table with probability

θ+|B|αn+θ,

or at an occupied table b of size |b| with probability

|b|−αn+θ.

In order for the construction to define a valid probability measure it is necessary to suppose that either α<0 and θ=−Lα for some L∈{1,2,,...}; or that 0≤α<1 and θ>−α.

Under this model the probability assigned to any particular partition B of [n], can be expressed in the general case (for any values of θ,α that satisfy the above-mentioned constraints) in terms of the Pochhammer k-symbol, as

Pr⁡(Bn=B∣θ,α)=(θ+α)|B|−1,α(θ+1)n−1,1∏b∈B(1−α)|b|−1,1

where, the Pochhammer k-symbol is defined as follows: by convention, (a)0,k=1, and for m>0

(a)m,k=∏i=0m−1(a+ik)={amif k=0,km(ak)m‾if k>0,|k|m(a|k|)m_if k<0

where xm‾=∏i=0m−1(x+i) is the rising factorial and xm_=∏i=0m−1(x−i) is the falling factorial. It is worth noting that for the parameter setting where α<0 and θ=−Lα, then (θ+α)|B|−1,α=(|α|(L−1))|B|−1,α, which evaluates to zero whenever |B|>L, so that L is an upper bound on the number of blocks in the partition; see the subsection on the Dirichlet-categorical model below for more details.

For the case when θ>0 and 0<α<1, the partition probability can be rewritten in terms of the Gamma function as

Pr⁡(Bn=B∣θ,α)=Γ(θ)Γ(θ+n)α|B|Γ(θ/α+|B|)Γ(θ/α)∏b∈BΓ(|b|−α)Γ(1−α).

In the one-parameter case, where α is zero, and θ>0 this simplifies to

Pr⁡(Bn=B∣θ)=Γ(θ)θ|B|Γ(θ+n)∏b∈BΓ(|b|).

Or, when θ is zero, and 0<α<1

Pr⁡(Bn=B∣α)=α|B|−1Γ(|B|)Γ(n)∏b∈BΓ(|b|−α)Γ(1−α).

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.

If α=0, the probability distribution of the random partition of the integer n thus generated is the Ewens distribution with parameter θ, used in population genetics and the unified neutral theory of biodiversity.

File:Chinese Restaurant Process for DP(0.5,H).webm

### Derivation

Here is one way to derive this partition probability. Let Ci be the random block into which the number i is added, for i=1,2,3,.... Then

Pr⁡(Ci=c∣C1,…,Ci−1)={θ+|B|αθ+i−1if c∈new block,|b|−αθ+i−1if c∈b;

The probability that Bn is any particular partition of the set {1,...,n} is the product of these probabilities as i runs from 1 to n. Now consider the size of block b: it increases by one each time we add one element into it. When the last element in block b is to be added in, the block size is |b|−1. For example, consider this sequence of choices: (generate a new block b)(join b)(join b)(join b). In the end, block b has 4 elements and the product of the numerators in the above equation gets θ⋅1⋅2⋅3. Following this logic, we obtain Pr⁡(Bn=B) as above.

### Expected number of tables

For the one parameter case, with α=0 and 0<θ<∞, the number of tables is distributed according to the chinese restaurant table distribution. The expected value of this random variable, given that there are n seated customers, is[9]

∑k=1nθθ+k−1=θ⋅(Ψ(θ+n)−Ψ(θ))

where Ψ(θ) is the digamma function. For the two-parameter case, for α≠0, the expected number of occupied tables is[7]

(θ+α)n‾α(θ+1)n−1‾−θα,

where xm‾ is the rising factorial (as defined above).

### The Dirichlet-categorical model

For the parameter choice α<0 and θ=−Lα, where L∈{1,2,3,…}, the two-parameter Chinese restaurant process is equivalent to the Dirichlet-categorical model, which is a hierarchical model that can be defined as follows. Notice that for this parameter setting, the probability of occupying a new table, when there are already L occupied tables, is zero; so that the number of occupied tables is upper bounded by L. If we choose to identify tables with labels that take values in {1,2,…,L}, then to generate a random partition of the set [n]={1,2,…,n}, the hierarchical model first draws a categorical label distribution, 𝐩=(p1,p2,…,pL) from the symmetric Dirichlet distribution, with concentration parameter γ=−α>0. Then, independently for each of the n customers, the table label is drawn from the categorical 𝐩. Since the Dirichlet distribution is conjugate to the categorical, the hidden variable 𝐩 can be marginalized out to obtain the posterior predictive distribution for the next label state, ℓn+1, given n previous labels

P(ℓn+1=i∣ℓ1,…,ℓn)=γ+|bi|Lγ+n

where |bi|≥0 is the number of customers that are already seated at table i. With α=−γ and θ=Lγ, this agrees with the above general formula, |bi|−αn+θ, for the probability of sitting at an occupied table when |bi|≥1. The probability for sitting at any of the L−|B| unoccupied tables, also agrees with the general formula and is given by

∑i:|bi|=0P(ℓn+1=i∣ℓ1,…,ℓn)=(L−|B|)γn+Lγ=θ+|B|αn+θ

The marginal probability for the labels is given by

P(ℓ1,…,ℓn)=P(ℓ1)∏t=1n−1P(ℓt+1∣ℓ1,…,ℓt)=∏i=1Lγ|bi|‾(Lγ)n‾

where P(ℓ1)=1L and xm‾=∏i=0m−1(x+i) is the rising factorial. In general, there are however multiple label states that all correspond to the same partition. For a given partition, B, which has |B|≤L blocks, the number of label states that all correspond to this partition is given by the falling factorial, L|B|_=∏i=0|B|−1(L−i). Taking this into account, the probability for the partition is

Pr(Bn=B∣γ,L)=L|B|_∏i=1Lγ|bi|‾(Lγ)n‾

which can be verified to agree with the general version of the partition probability that is given above in terms of the Pochhammer k-symbol. Notice again, that if B is outside of the support, i.e. |B|>L, the falling factorial, L|B|_ evaluates to zero as it should. (Practical implementations that evaluate the log probability for partitions via log⁡L|B|_=log⁡|Γ(L+1)|−log⁡|Γ(L+1−|B|)| will return −∞, whenever |B|>L, as required.)

#### Relationship between Dirichlet-categorical and one-parameter CRP

Consider on the one hand, the one-parameter Chinese restaurant process, with α=0 and θ>0, which we denote CRP(α=0,θ); and on the other hand the Dirichlet-categorical model with L a positive integer and where we choose γ=θL, which as shown above, is equivalent to CRP(α=−θL,θ). This shows that the Dirichlet-categorical model can be made arbitrarily close to CRP(0,θ), by making L large.

### Stick-breaking process

The two-parameter Chinese restaurant process can equivalently be defined in terms of a stick-breaking process.[10] For the case where 0≤α<1 and θ>−α, the stick breaking process can be described as a hierarchical model, much like the above Dirichlet-categorical model, except that there is an infinite number of label states. The table labels are drawn independently from the infinite categorical distribution 𝐩=(p1,p2,…), the components of which are sampled using stick breaking: start with a stick of length 1 and randomly break it in two, the length of the left half is p1 and the right half is broken again recursively to give p2,p3,…. More precisely, the left fraction, fk, of the k-th break is sampled from the beta distribution:

fk∼B(1−α,θ+kα),for k≥1 and 0≤α<1

The categorical probabilities are:

pk=fk∏i=1k−1(1−fk),where the empty product evaluates to one.

For the parameter settings α<0 and θ=−αL, where L is a positive integer, and where the categorical is finite: 𝐩=(p1,…,pL), we can sample 𝐩 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:

fk∼B(−α,θ+kα),for 1≤k≤L−1 and α<0

and fL=1.

## 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.[11]

## 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,[12] biodiversity modelling, and image reconstruction [13][14]

## See also

* Ewens sampling formula
* Preferential attachment
* Hilbert's paradox of the Grand Hotel

## References

1. ↑ Aldous, D. J. (1985). "Exchangeability and related topics". École d'Été de Probabilités de Saint-Flour XIII — 1983. Lecture Notes in Mathematics. 1117. pp. 1–198. doi:10.1007/BFb0099421. ISBN 978-3-540-15203-3. The restaurant process is described on page 92.
2. ↑ 2.0 2.1 Pitman, Jim (1995). "Exchangeable and Partially Exchangeable Random Partitions". Probability Theory and Related Fields 102 (2): 145-158. doi:10.1007/BF01213386.
3. ↑ Hoppe, Fred M. (1984). "Pólya-like urns and the Ewens' sampling formula". Journal of Mathematical Biology 20: 91-94.
4. ↑ Blei, David M.; Frazier, Peter I. (2011). "Distance Dependent Chinese Restaurant Processes". Journal of Machine Learning Research 12: 2461–2488. https://www.jmlr.org/papers/volume12/blei11a/blei11a.pdf.
5. ↑ Zhou, Mingyuan; Carin, Lawrence (2012). "Negative Binomial Process Count and Mixture Modeling". IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2): 307–20. doi:10.1109/TPAMI.2013.211. PMID 26353243. Bibcode: 2012arXiv1209.3442Z.
6. ↑ Antoniak, Charles E (1974). "Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems". The Annals of Statistics 2 (6): 1152–1174. doi:10.1214/aos/1176342871.
7. ↑ 7.0 7.1 Pitman, Jim (2006). Combinatorial Stochastic Processes. 1875. Berlin: Springer-Verlag. ISBN 9783540309901. http://works.bepress.com/jim_pitman/1/. Retrieved 2011-05-11.
8. ↑ "Dirichlet Process and Dirichlet Distribution -- Polya Restaurant Scheme and Chinese Restaurant Process". http://topicmodels.west.uni-koblenz.de/ckling/tmt/crp.html?parameters=0.5&dp=1#.
9. ↑ Xinhua Zhang, "A Very Gentle Note on the Construction of Dirichlet Process", September 2008, The Australian National University, Canberra. Online: http://users.cecs.anu.edu.au/~xzhang/pubDoc/notes/dirichlet_process.pdf
10. ↑ Ishwaran, Hemant; James, Lancelot F. (2001). "Gibbs Sampling Methods for Stick-Breaking Priors". Journal of the American Statistical Association 96 (453): 161–173. ISSN 0162-1459. https://www.jstor.org/stable/2670356.
11. ↑ Griffiths, T.L. and Ghahramani, Z. (2005) Infinite Latent Feature Models and the Indian Buffet Process . Gatsby Unit Technical Report GCNU-TR-2005-001.
12. ↑ Qin, Zhaohui S (2006). "Clustering microarray gene expression data using weighted Chinese restaurant process". Bioinformatics 22 (16): 1988–1997. doi:10.1093/bioinformatics/btl284. PMID 16766561.
13. ↑ White, J. T.; Ghosal, S. (2011). "Bayesian smoothing of photon-limited images with applications in astronomy". Journal of the Royal Statistical Society, Series B (Statistical Methodology) 73 (4): 579–599. doi:10.1111/j.1467-9868.2011.00776.x. http://www4.stat.ncsu.edu/~ghoshal/papers/Denoising Method.pdf.
14. ↑ Li, M.; Ghosal, S. (2014). "Bayesian multiscale smoothing of Gaussian noised images". Bayesian Analysis 9 (3): 733–758. doi:10.1214/14-ba871. http://projecteuclid.org/download/pdfview_1/euclid.ba/1409921112.

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

* v
* t
* e

Stochastic processes

Discrete time|

* Bernoulli process
* Branching process
* Chinese restaurant process
* Galton–Watson process
* Independent and identically distributed random variables
* Markov chain
* Moran process
* Random walk
* Loop-erased
* Self-avoiding
* Biased
* Maximal entropy

Continuous time|

* Bessel process
* Birth–death process
* Brownian motion
* Bridge
* Excursion
* Fractional
* Geometric
* Meander
* Cauchy process
* Contact process
* Continuous-time random walk
* Cox process
* Diffusion process
* Empirical process
* Feller process
* Fleming–Viot process
* Gamma process
* Geometric process
* Hunt process
* Interacting particle systems
* Itô diffusion
* Itô process
* Jump diffusion
* Jump process
* Lévy process
* Local time
* Markov additive process
* McKean–Vlasov process
* Ornstein–Uhlenbeck process
* Poisson process
* Compound
* Non-homogeneous
* Point process
* Schramm–Loewner evolution
* Semimartingale
* Sigma-martingale
* Stable process
* Superprocess
* Telegraph process
* Variance gamma process
* Wiener process
* Wiener sausage

Both|

* Branching process
* Galves–Löcherbach model
* Gaussian process
* Hidden Markov model (HMM)
* Markov process
* Martingale
* Differences
* Local
* Sub-
* Super-
* Random dynamical system
* Regenerative process
* Renewal process
* Stochastic chains with memory of variable length
* White noise

Fields and other|

* Dirichlet process
* Gaussian random field
* Gibbs measure
* Hopfield model
* Ising model
* Potts model
* Boolean network
* Markov random field
* Percolation
* Pitman–Yor process
* Point process
* Cox
* Poisson
* Random field
* Random graph

Time series models|

* Autoregressive conditional heteroskedasticity (ARCH) model
* Autoregressive integrated moving average (ARIMA) model
* Autoregressive (AR) model
* Autoregressive–moving-average (ARMA) model
* Generalized autoregressive conditional heteroskedasticity (GARCH) model
* Moving-average (MA) model

Financial models|

* Black–Derman–Toy
* Black–Karasinski
* Black–Scholes
* Chen
* Constant elasticity of variance (CEV)
* Cox–Ingersoll–Ross (CIR)
* Garman–Kohlhagen
* Heath–Jarrow–Morton (HJM)
* Heston
* Ho–Lee
* Hull–White
* LIBOR market
* Rendleman–Bartter
* SABR volatility
* Vašíček
* Wilkie

Actuarial models|

* Bühlmann
* Cramér–Lundberg
* Risk process
* Sparre–Anderson

Queueing models|

* Bulk
* Fluid
* Generalized queueing network
* M/G/1
* M/M/1
* M/M/c

Properties|

* Càdlàg paths
* Continuous
* Continuous paths
* Ergodic
* Exchangeable
* Feller-continuous
* Gauss–Markov
* Markov
* Mixing
* Piecewise deterministic
* Predictable
* Progressively measurable
* Self-similar
* Stationary
* Time-reversible

Limit theorems|

* Central limit theorem
* Donsker's theorem
* Doob's martingale convergence theorems
* Ergodic theorem
* Fisher–Tippett–Gnedenko theorem
* Large deviation principle
* Law of large numbers (weak/strong)
* Law of the iterated logarithm
* Maximal ergodic theorem
* Sanov's theorem

Inequalities|

* Burkholder–Davis–Gundy
* Doob's martingale
* Kunita–Watanabe

Tools|

* Cameron–Martin formula
* Convergence of random variables
* Doléans-Dade exponential
* Doob decomposition theorem
* Doob–Meyer decomposition theorem
* Doob's optional stopping theorem
* Dynkin's formula
* Feynman–Kac formula
* Filtration
* Girsanov theorem
* Infinitesimal generator
* Itô integral
* Itô's lemma
* Karhunen–Loève_theorem
* Kolmogorov continuity theorem
* Kolmogorov extension theorem
* Lévy–Prokhorov metric
* Malliavin calculus
* Martingale representation theorem
* Optional stopping theorem
* Prokhorov's theorem
* Quadratic variation
* Reflection principle
* Skorokhod integral
* Skorokhod's representation theorem
* Skorokhod space
* Snell envelope
* Stochastic differential equation
* Tanaka
* Stopping time
* Stratonovich integral
* Uniform integrability
* Usual hypotheses
* Wiener space
* Classical
* Abstract

Disciplines|

* Actuarial mathematics
* Econometrics
* Ergodic theory
* Extreme value theory (EVT)
* Large deviations theory
* Mathematical finance
* Mathematical statistics
* Probability theory
* Queueing theory
* Renewal theory
* Ruin theory
* Statistics
* System on Chip design
* Stochastic analysis
* Time series analysis
* Machine learning

* List of topics
* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Chinese restaurant process. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Chinese_restaurant_process&oldid=3979716"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template