8
$\begingroup$

I am trying to implement and learn a Dirichlet Process to cluster my data (or as machine learning people speak, estimate the density).

I read a lot of paper in the topic and sort of got the idea. But I am still confused; here are a series of question,

1) What is the different between Chinese Restaurant Model and DP ? 2) What is the different between Infinite Mixture Models and DP ?

To fully understand everything, I have implemented Chinese Restaurant Model, Polya Urn model and Stick-breaking; But it seems, implementing DP from scratch is a hard thing to do ! I can read and write python, R, Matlab.

1) Is there any code you recommend to read and improve to fully understand/work/develop DP ? 2) Based on my research, codes, for Dirichlet Process were not easy to read ! really long, lengthy (probably since the efficiency were more important that clarity). 3) However, there is more code on Infinite Mixture Model than Dirichlet Process. If these two methods are not far from each other can I use IMM ?! Basically, I want to build up my new model, and I don't want to re-invent a wheel.

I appreciate your comments

  • UPDATE since a lot of people have recommended Edwin Chen's tutorial on "Infinite Mixture Model with Non-parametric Bayes and the DP"; This tutorial has a misleading title; It only covers various representation of DP, specificity, CPR, stick-breaking, Polya-Urn Model; and at the end he is using a Mixture Model from scikit and make a couple of histogram on each cluster;
$\endgroup$
  • $\begingroup$ I don't understand what is misleading w.r.t. Chen's title. He uses a DP-GMM from scikit, yes. $\endgroup$ – Anne van Rossum Dec 27 '15 at 21:12
  • $\begingroup$ Yee Whye Teh's page: stats.ox.ac.uk/~teh/npbayes.html has several good tutorials in addition to a matlab implementation of a collapsed Gibbs sampler for the Dirichlet Process Mixture Model (DPMM). $\endgroup$ – Vadim Smolyakov Mar 5 '16 at 21:38
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Coud you elaborate more on what $\theta_{\left(z=i\right)_{n_{i}}}$ are and how that equation $\frac{\alpha^{k}\Gamma \left(\alpha\right)}{\Gamma \left(\alpha + n\right)}\prod_{i=0}^{k}\Gamma \left(n_{i}\right)$ is derived? $\endgroup$ – Daeyoung Lim Mar 15 '16 at 11:27
  • $\begingroup$ Those are the $n_i$ parameters of cluster $i$. The derivation you can find on math.stackexchange.com/questions/709959/… and can be obtained by integrating the compound N-categorical-dirichlet distribution. Extension to a process you can read on my blog at annevanrossum.com/blog/2015/03/03/sampling-of-dirichlet-process. It uses Neal's tech paper and I think it's the most detailed derivation that you will be able to find online. $\endgroup$ – Anne van Rossum Mar 19 '16 at 18:19
2
$\begingroup$

1) What is the different between Chinese Restaurant Model and DP?

None. CRP is a particular representation of DP. Depending on your problem you might want to use one representation over another (CRP, Stick-breaking, etc).

2) What is the different between Infinite Mixture Models and DP?

DP is just used as a prior for the Infinite Mixture Model. This is why Infinite Gaussian Mixture Models are also called DP-GMM. Actually the first paper on the subject is "The Infinite Gaussian Mixture Model" (Rasmussen, 1999)

3) Implementations

I am actually trying to implement Rasmussen's paper for a multivariate case in Python. (he uses Gibbs sampling, which is simpler than Variational Inference approximations). In the meanwhile, I found:

$\endgroup$
1
$\begingroup$

I am struggling with the same thing. Through this forum I found some pointers:

http://scikit-learn.org/stable/modules/generated/sklearn.mixture.DPGMM.html

http://statistical-research.com/dirichlet-process-infinite-mixture-models-and-clustering/

The first is scikit-learn's implementation of an infinite mixture of multivariate Gaussians (don't be put off by the n_components parameter, though I am not sure why it's there actually...).

The latter contains some code in R and models things in a K-means kind of fashion (I get the impression), but without specifying K (of course ;-) ).

If you find any other useful packages/descriptions, please post them!

Tom

$\endgroup$
  • $\begingroup$ thank you do the reply. I looked into your second link and to me he hasn't used DP in his example. It is some sort of k-means, anyhow. Let's keep this post update by putting useful packages/descriptions. $\endgroup$ – user4581 May 7 '14 at 0:01
  • $\begingroup$ I was thinking exactly the same thing. In the code though, he does refer to dirichletClusters, so I thought maybe I was wrong. But I don't see the DP in it either... $\endgroup$ – Tom May 7 '14 at 7:24
  • $\begingroup$ Check out this video lecture by Teh himself: videolectures.net/mlss09uk_teh_nbm At about minute 43 there are some equations that I think are really helpful! $\endgroup$ – Tom May 7 '14 at 15:45
  • $\begingroup$ to update you, there is R package, called DIRECT. has a very clear implementation of DP ! I started to read the code and educate myself ! I recommend you to have a look $\endgroup$ – user4581 May 13 '14 at 18:39
0
$\begingroup$

A very understandable code by Jacob Eisenstein is available for Matlab at https://github.com/jacobeisenstein/DPMM. It is based on the Dissertation "Graphical Models for Visual Object Recognition and Tracking" by E.B. Sudderth.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.