# Chinese Restaurant Process

I want to implement Chinese Restaurant Process representation of Dirichlet Process for random partitions. The problem setup is as follows:

I have some data (customers) which I have to randomly group (assign table). According to CRP,

• First customer C1 will always choose first empty table i.e. T1
• Second customer C2 will choose T1 with probability

$P(T1) = c / (n - 1 + α)$

and C2 will choose T2 with probability

$P(T2) = α / (n - 1 + α)$

where $c$ is number of customer sitting at existing table and $n$ is total number of customers.

My 3 questions are:

1. Choosing New Table

• How to decide that C2 will choose which table? Should C2 choose table with greater probability from $P(T1)$ and $P(T2)$?

2. Same Probability value for Existing & New Table

For instance, C2 have chosen T2, whereas at this stage $P(T1)$ and $P(T2)$ are same as:

$P(T1) = 1/(2 + α)$ and
$P(T2) = 1/(2 + α)$ Now

• How to decide C3 will choose which table?

3. Choosing from more than 1 Existing Tables

For another instance, if there have been assigned $3$ tables yet and $4th$ table will be new table, as we have a single new table probability value and several existing tables probability values, then

• How to decide that next customer choose which table from existing $3$ tables?
• @Anony-Mousse Questions are related to group assignment concept of Chinese Restaurant Process – maliks Mar 16 '16 at 9:17
• If it is harder to get answer of this question at Cross Validated, then where else? – maliks Mar 16 '16 at 9:51
• Also you need to have more patience. It may take a week or even a month to get a good answer from volunteers. – Has QUIT--Anony-Mousse Mar 16 '16 at 10:01
• @Anony-Mousse May be I'm not getting your point but what I think, we should know the answers to these questions (at least Question No. 1 and Question No. 3) before we calculate probabilities. Can you please answer those questions, if its crystal clear to you what I guess? – maliks Mar 16 '16 at 10:55

You need to be very precise about what $c$ and $n$ are.

Let $c_i$ be the number of customers at table $i$.

Let $n$ be the customer number, i.e. $n-1$ clients are already seated at all tables.

Let $k$ be the current number of tables.

Then randomly choose a table using this probabilities: $$P(T_i) = \begin{cases} c_i / (n - 1 + \alpha) & \text{ for }i\leq k \\ \alpha / (n - 1 + \alpha) & \text{ for } i = k +1 \\ 0 & \text{otherwise} \end{cases}$$ This is a total distribution, because $$\sum_i P(T_i) = \frac{\sum c_i + \alpha}{n - 1 + \alpha} = \frac{n -1 + \alpha}{n - 1 + \alpha} = 1$$ Therefore, you can draw a random number such that exactly one of these cases happens; i.e. the customer chooses exactly one table.

If $n=1$, $k=0$, then the probability of choosing the first (new) table is $\alpha/\alpha=1$.

Just reading this in a book only gets you halfway. What you need to learn is to work out such details yourself. The way to figure out these things is where you learn, not by looking at the final result.

This is not a clustering algorithm. It is a random stochastic process to simulate certain data distributions. But it is not based on any data. It is a theoretical model to back certain considerations. Judging from your earlier questions, it appears as if you were mislead to believe this could be easily used to cluster some text data?

• @Anony--Thanks a lot! But following many CRP explanations, it has been used as clustering as considering tables as clusters and customers as cluster members. i.e. group assignment to customers – maliks Mar 22 '16 at 11:47
• Using a theoretical model does not mean it has been simulated literally, because then it would assign randomly. And you probably don't want random clusters. What people do is use such as process to optimize parameters for the actual clustering, e.g. the number of clusters. You would use the CRP to estimate the number of tables, and the data to estimate alpha in return; then iterate this again and again to optimize these parameters for your actual clustering. It is a so called prior. But again, you need much more than CRP, unless you want random clusters. – Has QUIT--Anony-Mousse Mar 22 '16 at 12:10
• @Anony--As we will have two probability values for i<=k and for i=k+1, so how will we decide that instance will go to which side? Will it be decided on behalf of greater probability value? – maliks Mar 30 '16 at 7:05
• You have k+1 probability values, not 2. They sum to 1, and that allows you to draw the table as a random variable from this distribution. – Has QUIT--Anony-Mousse Mar 30 '16 at 7:41
• @Anony--Right you mean that, for instance if we have 6 probability values (i.e. 6 existing tables also referred as k) then we choose randomly from these 6 probabilities to draw a table for new customer. Am I right? – maliks Mar 30 '16 at 7:46