What is the difference between DP and CRP?
The Chinese Restaurant Process (CRP) is a distribution over partitions of integers. The connection to the Dirichlet Process (DP) exists thanks to De Finetti's theorem.
De Finetti's theorem: Suppose we have a random process $(\theta_1,\ldots,\theta_N)$ that is infinitely exchangeable, then the joint probability $p(\theta_1,\ldots,\theta_N)$ has a representation as a mixture:
$$p(\theta_1,\ldots,\theta_N)=\int dP(G) \prod_{i=1}^N G(\theta_i)$$
for some random variable $G$.
The exchangeability property means that we don't care about either the indices of the tables (we don't name the tables) and we don't care about the order of the customers at a particular table. The partition of customers into different sets is the only structure we are interested in. This means that given a partition we do not need to know the particular assignments of customers to the tables, we only need to know the number of customers at each table.
De Finetti's theorem does not help in finding the distribution $G$. It only states that it should exist.
The Dirichlet process is a prior over distributions. Informally, you thrown in a probability distribution and when you sample from it, out you will get probability distribution after probability distribution.
The connection between both can be established by proving that if $G$ is sampled from a Dirichlet Process, the equation in De Finetti's theorem holds for this particular $G$.
If
$$G \sim DP(\alpha, H)$$
then
$$p(\{\theta_{(z=0)_0},\ldots, \theta_{(z=0)_{n_0}}\},\ldots,\{\theta_{(z=k)_0},\ldots, \theta_{(z=k)_{n_k}}\}) = \frac{\alpha^k \Gamma(\alpha)}{\Gamma(\alpha+n)} \prod_{i=0}^k \Gamma(n_i)$$
Note that $p(\theta_1, \ldots, \theta_N)$ is described by a CRP through probabilities for particular partitions. Here $z=i$ denotes a table index $i$. And $n_i$ is the number of customers at table $i$. For completeness sake, remember that the $DP$ is:
$$\{G(A_1),\ldots,G(A_k)\} \sim Dirichlet(\alpha H(A_1), \ldots, \alpha H(A_k))$$
I think that it is clear from this exposition is that the connection is there, but should not be considered trivial. Note also that I did not describe the CRP in the sense of a conditional distribution over incoming individual customers. This would add yet another conceptual step between the CRP and DP. My advice: feel free about being uncomfortable with understanding directly their relationship and start playing around with describing joint and marginal distributions till you reproduce the connection. The CRP is obtained by marginalizing out $G$ from the DP.
For the connection between the joint probability and the sequential description of the CRP, see [1].
What if exchangeability does not hold?
If exchangeability does not hold we do not speak anymore about the DP or the CRP, but about the Dependent Dirichlet Process and the Dependent Chinese Restaurant Process. And naturally, the connection between them gets lost!
See [2] for details. The Dependent CRP describes which customer wants to sit with which (single) other customer. By clustering all customer-customer relationships we can an assignment over tables. The Dependent CRP is not marginally invariant: the probability of a partition when removing a customer is also depending on that very customer. In contrary, the Dependent DP is often defined by this very marginal: $G_t \sim DP(\alpha, H)$. Here $H$ is for example a Dirichlet distribution itself or any distribution that causes $G_t$ and $G_{t'}$ to be related.
There are many other generalizations possible, some of them will admit a representation over partitions as well as over distributions, such as the Chinese Restaurant Process with two parameters with the Pitman-Yor Process, or the Indian Buffet Process with the Beta Process [3]. Some of them won't.
- [1]: A Tutorial on Bayesian Nonparametric Models (2011) Gershman and Blei
- [2]: Distance Dependent Chinese Restaurant Processes (2011) Blei and Frazier
- [3]: Hierarchical Beta Processes and the Indian Buffet Process (2007) Thibaux and Jordan
