4
$\begingroup$

Let $\mathcal{Y} = (\mathbf{y}_1, \dots, \mathbf{y}_N)$ be data observed, such that each $\mathbf{y}_i \in \mathbb{R}^2$. Now conditional on unobserved cluster centres (means) $\mathcal{X} = (\mathbf{x}_1, \dots, \mathbf{x}_K)$, where $K >>0, K \in [1,\infty)$ is also unknown, we have

$$L(\mathcal{Y}|\mathcal{X}, \mathcal{C}, \Sigma,K) = \prod_{i =1}^N \prod_{j=1}^K [\mathcal{N}_2(\mathbf{y}_i;\mathbf{x}_j,\Sigma)]^{\mathcal{C}_{ij}},$$ where $\Sigma$ is a known covariance matrix and $\mathcal{C}_{ij} = 1$ if observation $i$ belongs to cluster $j$ and is zero otherwise.

Now, denote the number of observations per cluster as $S_1, \dots S_K$. We have that $S_j = \sum_{i =1}^{N} \mathcal{C}_{ij}$ for each $j = 1, \dots, K.$ The distribution of each $S_j$ follows $S_j \sim p(S)$ independently and identically, and while it is not multinomial, it is known.

I would like to infer $K$ and $\mathcal{X}$ given the above set-up. Since $K$ in this application is typically quite large (and can be infinite), I was hoping to use some theory in Bayesian nonparametrics, specifically from Dirichlet mixture models. However, since I do not have a typical Gaussian Mixture Model, I am unsure how to set this up.

Any help or pointers to specific papers which outline the theory that I need would be very kindly appreciated. Thanks!

$\endgroup$
  • $\begingroup$ You mention that you need to infer $X$ -- which is unobserved. How do you have a distribution conditioned on an unobserved variable? Usually when there is $P(Y \mid X = x)$, you are estimating a conditional distribution based on an observed variable $X = x$, where $x$ is an instance of the random variable $X$. $\endgroup$ – kedarps Jun 8 '19 at 12:58
  • $\begingroup$ Your question confuses me a little. E.g. take a random sample $Y_i \sim \mathcal{N}(\mu,1)$ iid $i =1, \dots, n$, with $\mu$ unknown. Then the likelihood of $y_1, \dots, y_n$ given $\mu$ is $L(y_1, \dots, y_n| \mu) = \prod_i \mathcal{N}(y_i|\mu)$. To infer $\mu$ in Bayesian setting, note that from Bayes' theorem $f(\mu|y_1, \dots, y_n) \propto L(y_1, \dots, y_n| \mu) \pi(\mu)$, where $\pi(\mu)$ denotes some prior over $\mu$. Taking the MAP value of this posterior gives an estimate for $\mu$. Above, I have described my likelihood. Priors can be chosen to make sampling from posteriors easier. $\endgroup$ – user202654 Jun 9 '19 at 22:43
  • $\begingroup$ In the above eqn. is X referring to the mean? $\endgroup$ – kedarps Jun 9 '19 at 22:47
  • $\begingroup$ Yes, I'll change my question if this is unclear. $\endgroup$ – user202654 Jun 9 '19 at 22:48
  • $\begingroup$ Thanks. I will try to answer your question. $\endgroup$ – kedarps Jun 9 '19 at 23:13
3
$\begingroup$

Chinese restaurant process

Let's define this problem using the Chinese Restaurant Process (CRP) formulation of the Dirichlet Process (DP), which can be summarized as follows (from Gershman et al., emphasis mine):

Imagine a restaurant with an infinite number of tables, and imagine a sequence of customers entering the restaurant and sitting down. The first customer enters and sits at the first table. The second customer enters and sits at the first table with probability $\frac{1}{1+\alpha}$, and the second table with probability $\frac{\alpha}{1+\alpha}$, where $\alpha$ is a positive real. When the $n^{th}$ customer enters the restaurant, she sits at each of the occupied tables with probability proportional to the number of previous customers sitting there, and at the next unoccupied table with probability proportional to $\alpha$.

Using the following analogy, one can formulate an infinite-GMM problem:

  • infinite number of tables $\equiv$ infinite number of clusters i.e. unknown number of clusters.
  • customers sitting at a table $\equiv$ observations belonging to a cluster.
  • table parameters $\equiv$ cluster parameters i.e. mean $x_k$, covariance $\Sigma$.

Infinite-GMM

Now that we have a background on CRP, lets look at the data generation process using infinite-GMM with a CRP prior:

  1. First we need to choose a cluster assignment, $z_i$ for each observation, $y_i$. Using a Chinese restaurant process, we assume that there are currently $K$ clusters, but we also have a probability to assign an observation to a new cluster $K+1$. This way we do not need to fix $K$ a priori,

$$ \begin{equation}\tag{1}\label{eqn1} P(z_i=k\mid \alpha) = \begin{cases} \frac{S_k}{S+\alpha-1} & , k \in [1, K]\\ \frac{\alpha}{S+\alpha-1} & , k = k_{new}=K+1\\ \end{cases} \end{equation} $$

  1. Given a cluster assignment, we can generate an observation from the corresponding Gaussian with parameters: $y_i \sim \mathcal{N}(x_k, \Sigma)$

where, $S_k$ are the number of observations assigned to the $k^{th}$ cluster, exclusing the $i^{th}$ observation, and $S$ are the total number of observations.

Implementation

The infinite-GMM problem can be solved using a Gibbs sampler, which alternatively samples $z_i$ and the model parameters $\mu_k, \Sigma$. Here are some resources for that:

  • Yee Whye Teh's MATLAB implementation of infinite-GMM is here.
  • More details on the Math can be found here
$\endgroup$
  • $\begingroup$ Thanks so much for your time and effort into this response! :) I'll take a look at your formulation. Btw, I'm assuming that $S = \sum_{k = 1}^{K+1} S_k$? $\endgroup$ – user202654 Jun 10 '19 at 16:28
  • $\begingroup$ Yes. $S$ is the total number of observations and $S_k$ are the observations assigned to the $k^{th}$ cluster. $\endgroup$ – kedarps Jun 10 '19 at 16:38

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.