Can someone give a simple guide of Dirichlet process clustering?

Question

I am trying to understand the Dirichlet process and Dirichlet process clustering, but because of my lack of knowledge of stochastic process theory and measure theory, I cannot understand what the Dirichlet process is exactly. I know what the Dirichlet distribution is, but I cannot move forward.

Can someone give me a naive introduction of the Dirichlet process and clustering?

Basically I am confused about:

• the difference between (Dirichlet) distribution and (Dirichlet) process,

• how Poly's url or stick breaking emphasis Dirichlet process,

• and most importantly how Gibbs sampling based clustering of Dirichlet mixture model utilizing Dirichlet process works.

Answer 1

What is the difference between (Dirichlet) distribution and (Dirichlet) process?

The difference between a Dirichlet distribution and a Dirichlet process is perhaps easier to understand when you understand the difference between a Gaussian distribution and a Gaussian process. A Gaussian distribution pertains to the possible realizations of a single random variable. A Gaussian process constitutes a set of random variables in which this set is ordered. Often, this ordering is in time, but it doesn't need to be. We can draw a set of observations directly from the Gaussian process, or equivalently we can draw observations from a multivariate normal distribution (every linear combination of its components is normally distributed).

The Dirichlet distribution is a multivariate generalization of the beta distribution. It can be used to define probabilities for entities that sum up to 1. One of these entities that comes into mind are probabilities themselves of course. :-) Parallel to the Gaussian process, the Dirichlet process can be seen as a set of random variables. In this case nothing is said about ordering, but there is something said about a partition of a subset of these random variables. We can draw observations directly from a Dirichlet process, or equivalently we can draw observations from a (of course multivariate) Dirichlet distribution (every linear combination of its components is not a Dirichlet distribution though [1]).

How is Pólya's urn or stick breaking related to the Dirichlet process? Suppose, we have drawn many observations from a Dirichlet process. We subsequently study the distribution of these observations. As you probably know, the incredible feat of the Dirichlet Process is to pick the same value from a continuous range of all possible values time after time (governed by the alpha parameter). The frequencies with which different values are repeatedly picked can be obtained by multiple means. The Chinese Restaurant Process is just one of the manners. The Pólya's urn strategy with colored balls that you duplicate and put back and where you pick a random new color if you pick a black ball is exactly the same as the CRP. The stick-breaking process is different though. It doesn't say anything about the "values" (colors) of each piece of the stick that you break in a generative fashion. The only thing after all the breaking is the number of balls of the same color, the distribution (of the colors).

How to do Gibbs sampling? The Dirichlet process has a very interesting property. In the analog of the CRP, you can take a random customer out and "act as if" this is the first customer. In Gibbs sampling you calculate all the time the conditional of one of the random variables in a multivariate distribution given all the others, so if there is a closed-form formulation of this procedure, Gibbs sampling is very natural. The exchangeability property is worth to explore. Try for example to calculate the probability that two totally random customers (e.g. the first and the last) sit at the same table with alpha=1. Gibbs sampling on the level of the customers though, is not so smart, because - if you recall the restaurant - there are a lot of customers at the same table. So, it would be nice if you can update directly an entire table. Implementation details like this always refer to Neal's technical report which I also recommend [2].

[1] On the distribution of linear combinations of the components of a Dirichlet random vector (2000) Provost, Cheong

[2] Markov Chain Sampling Methods for Dirichlet Process Mixture Models (1998) Neal

Answer 2

These are two great tutorials,

"Introduction to the Dirichlet Distribution and Related Processes"

"A Very Gentle Note on the Construction of Dirichlet Process"

specially the first one, with a reference to a very succinct tutorial on measure theory. I would start with the first one, because it starts by introducing the Dirichlet distribution and sampling, and then moves one to the continuous case, the Dirichlet process. It helped me a lot to understand it.

The tutorial address the first two questions. The sampling schemes are derived in detail. The Dirichlet process is a generalization of the Dirichlet distribution.

The Dirichlet distribution is a distribution over the distributions modelling discrete events from a given number of categories. In other words, you can model densities of probability of categorical variables with a Dirichlet distribution. The Dirichlet process allows you to model distributions over continuous variables.