Chinese restaurant process#Two-parameter generalization

For any positive integer $n$, let $\backslash mathcal\{P\}\_\{n\}$ denote the set of all partitions of the set $\backslash \{\; 1,\; 2,\; 3,...,\; n\; \backslash \}\; \backslash triangleq\; [n]$. The Chinese restaurant process takes values in the infinite Cartesian product $\backslash prod\_\{n\; \backslash geq\; 1\}\; \backslash mathcal\{P\}\_\{n\}$.

The value of the process at time $n$ is a partition $B\_n$ of the set $[n]$, whose probability distribution is determined as follows. At time $n=1$, the trivial partition $B\_1\; =\; \backslash \{\; \backslash \{\; 1\; \backslash \}\; \backslash \}$ 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 $B\_n$, 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 $B\_n$ 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 $\backslash \{\; 1,...,\; n\; \backslash \}$ 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 $B\_n$ is the same as the law of the random partition $B\_\{n-1\}$.

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

: $$

\Pr(B_n = B) = \frac{\prod_{b\in B} (|b| -1)!}{n!}, \qquad B \in \mathcal{P}_{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 $\backslash theta>0$ which modifies the probability of the new customer sitting at a new table to $\backslash frac\{\backslash theta\}\{n+\backslash theta\}$ and correspondingly modifies the probability of them sitting at a table of size $|b|$ to $\backslash frac$

An equivalent, but subtly different way to define the Chinese restaurant process, is to let new customers choose companions rather than tables.{{cite journal |last1=Blei |first1=David M. |last2=Frazier |first2=Peter I. |title=Distance Dependent Chinese Restaurant Processes |journal=Journal of Machine Learning Research |date=2011 |volume=12 |pages=2461–2488 |url=https://www.jmlr.org/papers/volume12/blei11a/blei11a.pdf}} Customer $n+1$ chooses to sit at the same table as any one of the $n$ seated customers with probability $\backslash frac\{1\}\{n+\backslash theta\}$, or chooses to sit at a new, unoccupied table with probability $\backslash frac\{\backslash theta\}\{n+\backslash theta\}$. Notice that in this formulation, the customer chooses a table without having to count table occupancies---we don't need $|b|$.

{{Probability distribution|

name =Chinese restaurant table|

type =mass|

parameters =$\backslash theta\; >\; 0$

$n\; \backslash in\; \backslash \{1,2,\backslash ldots\; \backslash \}$|

support =$k\; \backslash in\; \backslash \{1,2,\backslash ldots,n\backslash \}$|

pdf =$\backslash frac\{\backslash Gamma(\backslash theta)\}\{\backslash Gamma(n+\backslash theta)\}\; |s(n,k)|\; \backslash theta^\{k\}$|

mean =$\backslash theta\; (\backslash psi(\backslash theta+n)-\backslash psi(\backslash theta))$
(see digamma function)|

}}

The Chinese restaurant table distribution (CRT) is the probability distribution on the number of tables in the Chinese restaurant process.{{Cite journal | title=Negative Binomial Process Count and Mixture Modeling| arxiv=1209.3442| last1=Zhou| first1=Mingyuan| last2=Carin| first2=Lawrence| journal=IEEE Transactions on Pattern Analysis and Machine Intelligence| year=2012| volume=37| issue=2| pages=307–20| doi=10.1109/TPAMI.2013.211| pmid=26353243| bibcode=2012arXiv1209.3442Z| s2cid=1937045}} It can be understood as the sum of $n$ independent Bernoulli random variables, each with a different parameter:

:$$

\begin{align}

K & = \sum_{i=1}^n b_i \\[4pt]

b_i & \sim \operatorname{Bernoulli} \left( \frac \theta {i-1+\theta}\right)

\end{align}

The probability mass function of $K$ is given by {{cite journal | last1 = Antoniak | first1 = Charles E | year = 1974| title = Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems | journal = The Annals of Statistics| volume = 2 | issue = 6 | pages = 1152–1174 | doi = 10.1214/aos/1176342871 | doi-access = free }}

:$$

f(k) = \frac{\Gamma(\theta)}{\Gamma(n+\theta)} |s(n,k)| \theta^k, \quad k=1,\dots,n,

where $s$ denotes Stirling numbers of the first kind.

This construction can be generalized to a model with two parameters, $\backslash theta$ & $\backslash alpha$,{{cite journal

|first=Jim |last=Pitman

|title=Exchangeable and Partially Exchangeable Random Partitions

|journal=Probability Theory and Related Fields

|volume=102 |issue=2 |pages=145–158

|year=1995

|mr=1337249 |doi=10.1007/BF01213386

|s2cid=16849229

|doi-access=free}}{{cite book|last=Pitman|first=Jim|title=Combinatorial Stochastic Processes|volume=1875|url=http://works.bepress.com/jim_pitman/1/|publisher=Springer-Verlag|year=2006|location=Berlin|isbn=9783540309901|access-date=2011-05-11|archive-date=2012-09-25|archive-url=https://web.archive.org/web/20120925082105/http://works.bepress.com/jim_pitman/1/|url-status=dead}} 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

: $$

\frac{\theta + |B| \alpha}{n + \theta},

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

: $$

\frac

\end{cases}

where $x^\{\backslash overline\; m\}=\backslash prod\_\{i=0\}^\{m-1\}(x+i)$ is the rising factorial and $x^\{\backslash underline\; m\}=\backslash prod\_\{i=0\}^\{m-1\}(x-i)$ is the falling factorial. It is worth noting that for the parameter setting where and $\backslash theta\; =\; -L\backslash alpha$, then $(\backslash theta\; +\; \backslash alpha)\_$

In the one-parameter case, where $\backslash alpha$ is zero, and $\backslash theta>0$ this simplifies to

:$$

\Pr(B_n = B\mid\theta) = \frac{\Gamma(\theta)\,\theta^

Or, when $\backslash theta$ is zero, and

:$$

\Pr(B_n = B\mid\alpha) =\frac{\alpha^{|B|-1}\,\Gamma(|B|) }{{\Gamma(n)}}\prod_{b\in B} \frac{\Gamma(|b|-\alpha)}{\Gamma(1-\alpha)}.

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 $\backslash alpha=0$, the probability distribution of the random partition of the integer $n$ thus generated is the Ewens distribution with parameter $\backslash theta$, used in population genetics and the unified neutral theory of biodiversity.

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

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

:$$

\Pr(C_i = c\mid C_1,\ldots,C_{i-1})

= \begin{cases}

\dfrac{\theta + |B| \alpha }{\theta + i -1} & \text{if }c \in \text{new block}, \\ \\

\dfrac{|b| - \alpha }{\theta + i - 1} & \text{if }c\in b;

\end{cases}

The probability that $B\_n$ is any particular partition of the set $\backslash \{\; 1,...,n\; \backslash \}$ 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 $\backslash theta\backslash cdot\; 1\backslash cdot\; 2\backslash cdot\; 3$. Following this logic, we obtain $\backslash Pr(B\_n\; =\; B)$ as above.

For the one parameter case, with $\backslash alpha=0$ and , 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, isXinhua 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 {{webarchive |url=https://web.archive.org/web/20110411124712/http://users.cecs.anu.edu.au/~xzhang/pubDoc/notes/dirichlet_process.pdf |date=April 11, 2011 }}

:$$

\begin{align}

\sum_{k=1}^n \frac \theta {\theta+k-1} = \theta \cdot (\Psi(\theta+n) - \Psi(\theta))

\end{align}

where $\backslash Psi(\backslash theta)$ is the digamma function. For the two-parameter case, for $\backslash alpha\backslash ne0$, the expected number of occupied tables is

:$$

\begin{align}

\frac{(\theta+\alpha)^{\overline n}}{\alpha (\theta+1)^{\overline{n-1}}} - \frac \theta \alpha,

\end{align}

where $x^\{\backslash overline\; m\}$ is the rising factorial (as defined above).

For the parameter choice and $\backslash theta=-L\backslash alpha$, where $L\backslash in\backslash \{1,2,3,\backslash ldots\backslash \}$, 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 $\backslash \{1,2,\backslash ldots,L\backslash \}$, then to generate a random partition of the set $[n]=\backslash \{1,2,\backslash ldots,n\backslash \}$, the hierarchical model first draws a categorical label distribution, $\backslash mathbf\; p=(p\_1,p\_2,\backslash ldots,p\_L)$ from the symmetric Dirichlet distribution, with concentration parameter $\backslash gamma=-\backslash alpha>0$. Then, independently for each of the $n$ customers, the table label is drawn from the categorical $\backslash mathbf\; p$. Since the Dirichlet distribution is conjugate to the categorical, the hidden variable $\backslash mathbf\; p$ can be marginalized out to obtain the posterior predictive distribution for the next label state, $\backslash ell\_\{n+1\}$, given $n$ previous labels

:$$

P(\ell_{n+1}=i\mid \ell_1,\ldots,\ell_n) = \frac{\gamma+ \left| {b_i} \right| }{L\gamma+n}

where $\backslash left|\{b\_i\}\backslash right|\backslash ge0$ is the number of customers that are already seated at table $i$. With $\backslash alpha=-\backslash gamma$ and $\backslash theta=L\backslash gamma$, this agrees with the above general formula, $\backslash frac$

where $P(\backslash ell\_1)=\backslash frac1L$ and $x^\{\backslash overline\; m\}=\backslash prod\_\{i=0\}^\{m-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 $\backslash left|B\backslash right|\backslash le\; L$ blocks, the number of label states that all correspond to this partition is given by the falling factorial, $L^\{\backslash underline\{\backslash left|B\backslash right|\}\; \}=\backslash prod\_\{i=0\}^\{\backslash left|B\backslash right|-1\}(L-i)$. Taking this into account, the probability for the partition is

:$$

\text{Pr}(B_n=B\mid\gamma,L)

=

L^{\underline{\left|B\right|}}\,\frac{\prod_{i=1}^L\gamma^{\overline{\left|{b_i}\right|} }}{(L\gamma)^{\overline 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^\{\backslash underline$

Consider on the one hand, the one-parameter Chinese restaurant process, with $\backslash alpha=0$ and $\backslash theta>0$, which we denote $\backslash text\{CRP\}(\backslash alpha=0,\backslash theta)$; and on the other hand the Dirichlet-categorical model with $L$ a positive integer and where we choose $\backslash gamma=\backslash frac\{\backslash theta\}\{L\}$, which as shown above, is equivalent to $\backslash text\{CRP\}(\backslash alpha=-\backslash frac\{\backslash theta\}\{L\},\backslash theta)$. This shows that the Dirichlet-categorical model can be made arbitrarily close to $\backslash text\{CRP\}(0,\backslash theta)$, by making $L$ large.

The two-parameter Chinese restaurant process can equivalently be defined in terms of a stick-breaking process.{{Cite journal |last=Ishwaran |first=Hemant |last2=James |first2=Lancelot F. |date=2001 |title=Gibbs Sampling Methods for Stick-Breaking Priors |url=https://www.jstor.org/stable/2670356 |journal=Journal of the American Statistical Association |volume=96 |issue=453 |pages=161–173 |issn=0162-1459}} For the case where and $\backslash theta>-\backslash alpha$, 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 $\backslash mathbf\; p=(p\_1,p\_2,\backslash ldots)$, 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 $p\_1$ and the right half is broken again recursively to give $p\_2,p\_3,\backslash ldots$. More precisely, the left fraction, $f\_k$, of the $k$-th break is sampled from the beta distribution:

:$$

f_k\sim B(1-\alpha,\theta+k\alpha),\; \text{for }k\ge1\text{ and }0\le\alpha<1

The categorical probabilities are:

:$$

p_k=f_k\prod_{i=1}^{k-1}(1-f_k),\;\text{where the empty product evaluates to one.}

For the parameter settings and $\backslash theta=-\backslash alpha\; L$, where $L$ is a positive integer, and where the categorical is finite: $\backslash mathbf\; p=(p\_1,\backslash ldots,\; p\_L)$, we can sample $\backslash mathbf\; p$ 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:

:$$

f_k \sim B(-\alpha, \theta+k\alpha),\;\text{for }1\le k\le L-1\text{ and }\alpha<0

and $f\_L=1$.

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.Griffiths, T.L. and Ghahramani, Z. (2005) [http://learning.eng.cam.ac.uk/zoubin/papers/ibptr.pdf Infinite Latent Feature Models and the Indian Buffet Process] {{Webarchive|url=https://web.archive.org/web/20081031153937/http://learning.eng.cam.ac.uk/zoubin/papers/ibptr.pdf |date=2008-10-31 }}. Gatsby Unit Technical Report GCNU-TR-2005-001.

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,{{cite journal | last1 = Qin | first1 = Zhaohui S | year = 2006 | title = Clustering microarray gene expression data using weighted Chinese restaurant process | journal = Bioinformatics | volume = 22 | issue = 16| pages = 1988–1997 | doi=10.1093/bioinformatics/btl284| pmid = 16766561 | doi-access = }} biodiversity modelling, and image reconstruction {{cite journal | last1 = White | first1 = J. T. | last2 = Ghosal | first2 = S. | year = 2011 | title = Bayesian smoothing of photon-limited images with applications in astronomy | url = http://www4.stat.ncsu.edu/%7Eghoshal/papers/Denoising%20Method.pdf | journal = Journal of the Royal Statistical Society, Series B (Statistical Methodology) | volume = 73 | issue = 4| pages = 579–599 | doi=10.1111/j.1467-9868.2011.00776.x| citeseerx = 10.1.1.308.7922 | s2cid = 2342134 }}{{cite journal | last1 = Li | first1 = M. | last2 = Ghosal | first2 = S. | year = 2014 | title = Bayesian multiscale smoothing of Gaussian noised images | url = http://projecteuclid.org/download/pdfview_1/euclid.ba/1409921112 | journal = Bayesian Analysis | volume = 9 | issue = 3| pages = 733–758 | doi=10.1214/14-ba871| doi-access = free }}

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

• [https://web.archive.org/web/20190327085650/https://pdfs.semanticscholar.org/775e/5727f5df0cb9bf834af2ea2548a696c27a38.pdf 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/

{{Stochastic processes}}

{{DEFAULTSORT:Chinese Restaurant Process}}

Category:Stochastic processes

Category:Nonparametric Bayesian statistics