# Dirichlet Processes for clustering: how to deal with labels?

Q: What is the standard way to cluster data using a Dirichlet Process?

When using Gibbs sampling clusters appear and dissapear during the sampling. Besides, we have a identifiability problem since the posterior distribution is invariant to cluster relabelings. Thus, we can not say which is the cluster of a user but rather that two users are in the same cluster (that is $p(c_i=c_j)$).

Can we summarize the class assignments so that, if $c_i$ is the cluster assignment of point $i$, we now not only that $c_i=c_j$ but that $c_i=c_j=c_j=...=c_z$?

These are the alternatives I found and why I think they are incomplete or misguided.

(1) DP-GMM + Gibbs sampling + pairs-based confusion matrix

To use a Dirichlet Process Gaussian Mixture Model (DP-GMM) for a clustering I implemented this paper where the authors propose a DP-GMM for density estimation using Gibbs sampling.

To explore the clustering performance, they say:

Since the number of components change over the [MCMC] chain, one would need to form a confusion matrix showing the frequency of each data pair being assigned to the same component for the entire chain, see Fig. 6.

Cons: This is not a real "complete" clustering but a pair-wise clustering. The figure looks that nice because we know the real clusters and arrange the matrix accordingly.

(2) DP-GMM + Gibbs sampling + sample until nothing changes

I have been searching and I found some people claiming to do clustering based on Dirichlet Process using a Gibbs sampler. For instance, this post considers that the chain converges when there are no more changes either in the number of clusters or in the means, and therefore gets the summaries from there.

Cons: I'm not sure this is allowed since, if I'm not wrong:

• (a) there might be label switchings during the MCMC.

• (b) even in the stationary distribution the sampler can create some cluster from time to time.

(3) DP-GMM + Gibbs sampling + choose sample with most likely partition

In this paper, the authors say:

After a “burn-in” period, unbiased samples from the posterior distribution of the IGMM can be drawn from the Gibbs sampler. A hard clustering can be found by drawing many such samples and using the sample with the highest joint likelihood of the class indicator variables. We use a modified IGMM implementation written by M. Mandel.

Cons: Unless this is a Collapsed Gibbs Sampler where we only sample the assignments, we can compute $p(\mathbf{c} | \theta)$ but not the marginal $p(\mathbf{c})$. (Would it be a good practice instead to get the state with highest $p(\mathbf{c}, \theta)$?)

(4) DP-GMM with Variatonal Inference:

I've seen that some libraries use variational inference. I don't know Variational Inference very much but I guess that you don't have identifiability problems there. However, I would like to stick to MCMC methods (if possible).

• In approach 3 (the posterior mode), your complaint about $p(\mathbf{c})$ being unavailable doesn't make much sense to me. It seems more like a complaint about MCMC in general than about this particular problem. – shadowtalker Feb 2 '15 at 7:41
• Yes, exactly, I mean MCMC does not give us access to $p(\mathbf{c})$ and therefore we can't pretend we can pick it up from a given state in the chain. – alberto Feb 2 '15 at 12:38
• that's by design. In fact, it goes beyond MCMC: it's a built-in feature of any Bayesian model. If anything, you're encountering a problem because you're trying to do something unnatural, something that we are obsessed with doing: cramming a distributional estimate into a point estimate – shadowtalker Feb 2 '15 at 15:13
• There are reasons for not wanting to do something like this in the first place - there are various senses in which the Dirichlet process mixture model can't consistently estimate the number of clusters (and hence can't do a good job of recovering a "true" clustering of the data). There was a recent paper at NIPS on this topic. – guy Apr 10 '15 at 5:17
• See here. I think they propose instead to put a Poisson prior on the number of components (and derive some sort of restaurant process to implement it), but I'm not sure if this is the paper they do it. – guy Apr 10 '15 at 16:56

My tentative answer would be to treat $\mathbf{c}$ as a parameter so that $p(\mathbf{c},\theta)$ is simply the posterior mode. This is what I suspect Niekum and Barto did (the paper referenced in option 3). The reason they were vague about whether they used $p(\mathbf{c}, \theta)$ or $p(\mathbf{c}|\theta)$ is that one is proportional to the other.

The reason I say this answer is "tentative" is that I'm not sure if designating a value as a "parameter" is just a matter of semantics, or if there's a more technical/theoretical definition that one of the PhD-holding users here would be able to elucidate.

• You are right, $p(\mathbf{c,\theta}) = p(\mathbf{c |\theta}) p (\theta)$. Yet, this option may give good results in practice but I'd say it has no theoretical guarantees that the state you picked it is not a local optimum w.r.t $p(\mathbf{c})$ rather than the true posterior mode. Besides, we would be abandonning all hope of getting the true posterior of p(\mathbf{c}. Anyway, if there is no other way and it has to be a point estimator... so be it. – alberto Feb 2 '15 at 12:57
• @alberto again, that has nothing to do with this model and everything to do with Bayesian statistics. See here: groups.google.com/forum/m/#!topic/stan-users/qH-2Mq219gs . And if you're worried about multiple modes, see here: groups.google.com/forum/m/#topic/stan-users/RsVo9NUn0yM and here: stats.stackexchange.com/q/3328/36229 – shadowtalker Feb 2 '15 at 15:20

I just wanted to share some resources on the topic, hoping that some of them could be helpful in answering this question. There are many tutorials on Dirichlet processes (DP), including some on using DP for clustering. They range from "gentle", like this presentation tutorial, to more advanced, like this presentation tutorial. The latter is an updated version of the same tutorial, presented by Yee Whye Teh at MLSS'07. You can watch the video of that talk with synchronized slides here. Speaking about videos, you can watch another interesting and relevant talk with slides by Tom Griffith here. In terms of the paper-formatted tutorials, this tutorial is a nice and pretty popular one.

Finally, I would like to share a couple of related papers. This paper on hierarchical DP seems to be important and relevant. The same applies to this paper by Radford Neal. If you are interested in topic modeling, latent Dirichlet allocation (LDA) should most likely be on your radar as well. In that case, this very recent paper presents a novel and much improved LDA approach. In regard to topic modeling domain, I would recommend to read research papers by David Blei and his collaborators. This paper is an introductory one, the rest you can find on his research publications page. I realize that some of the materials that I've recommended might be too basic for you, but I thought that by including everything that I ran across on the topic, I'd increase chances for you to find the answer.

• I understand what you're trying to do here, but it really doesn't address the question. – shadowtalker Feb 2 '15 at 7:02
• @ssdecontrol: If you understand what I'm trying to do here (which is helping the OP in discovering the answer and learning a thing or two), then what is the point of your comment? I've never claimed that my answer is the answer, but expressed hope that it is helpful, which is ultimately up to the OP to decide. If you have a better answer, I'm sure that it will be appreciated by the OP and the community. – Aleksandr Blekh Feb 2 '15 at 7:43
• Yup, I totally understand. That's a lot of what I do on here as well. But the question is asking about the right way to pick out cluster labels from MCMC results and I don't think this addresses that question at all. – shadowtalker Feb 2 '15 at 7:51
• @AleksandrBlekh I would agree with ssdecontrol that it is a little bit off-topic since OP seems to know the "basics" and asks a specific question. – Tim Feb 2 '15 at 8:21
• @AleksandrBlekh I appreciate your post, a least it makes a good summary for an introduction to DP. I do know the basics (intermediate level, let's say), but at least your references made me go back to LDA and realize that they tiptoe around the issue since their labels often don't switch. – alberto Feb 2 '15 at 12:29