1
$\begingroup$

Question 1:

Suppose that data is modelled by a mixture of K probability distributions which are actually Gaussians. $P(x_i|\theta_j)$ is the probability density of the j'th cluster, for which the parameters that we want to learn are $\theta_j = \{\mu_j, \sigma_j\}$. The probability that data-point $x_i$ belongs to cluster $c_j$ (i.e. to the j'th mixture) is $P(x_i \in c_j | x_i, \theta_j) = \frac{P(x_i|\theta_j)}{\sum_l P(x_i|\theta_l)}$. Thus the algorithm consists of take some initial values for the parameters of each mixture $\theta_j$ (how do we choose this initial parameter values ?). Then we repeat the flowing two steps many times:

  • Compute $P(x_i \in c_j | x_i, \theta_j)$ for each data-point i = 0,..,N, in a mixture j = 1,..,K. Thus we will get a matrix M of N x K.
  • Optimize the parameters $\theta_j$ of each cluster j. (how do we optimize/update them ? does this mean just trying with other parameter values ?)

I'm confused on how to choose the parameters of each cluster and how to optimize/update them (the second step).

So if I understand, we should repeat the following code algorithm until convergence:

X = {x1, ..., xn} set of data-points
M = {m1, ..., mk} set of k means choosen randomly from X
S = {s1, ..., sk} set of k covariance matrix, each si is choosen to be the identity matrix

for i from 1 to n
{
    for j from 1 to k
    {
        compute Pij = pdf(xi | mj, sj) / SUM_l pfd(xi | ml, sl)
    }
}

for i from 1 to n
{
    for j from 1 to k
    {
        mj = mj + (Pij * xi) / SUM_l Plj // update the mean
    }
}

Question 2:

Is there an incremental version of a Gaussian mixture model which is incremental (the data-points are processed sequentially)? That is, without "repeating" the 2 steps of the EM algorithm "until convergence".

$\endgroup$
  • 1
    $\begingroup$ hi you post seems interesting but i'm confused by the presentation. It seems you have a model and a sequential sampling scheme of the data. What is you need to estimate? Could write things mathematically? $\endgroup$ – julien stirnemann Oct 8 '12 at 10:40
1
$\begingroup$

[Updated with the extra question 1]

Question 1

Note that in EM typically the clusters are modeled not just by a mean and a variance, but by a mean vector and a covariance matrix. Initial parameter values are usually to use the identity matrix as covariance matrix, and a random vector as initial mean. Similar to k-means, it does pay off to carefully choose initial values (e.g. by running on a sample first, or e.g. k-means++). You can use k-means++ to obtain initial centers for EM!

For updating, you assign objects "fuzzy" to all the clusters, relative to their densities (i.e. normalize by the density sum, so the assignments always total to 1 for each object!), then you compute the weighted average and weighted covariance matrix for each cluster. It's actually really simple. You might even want to avoid keeping the NxK matrix in memory.

Look up "estimating multivariate gaussian mixture" for details.

Question 2

Well, you can obviously do this incrementally. The means (and thus the covariances) can be updated online quite well.

However:

  • the results probably will not be as good, unless you have good starting points. So it makes sense to at least do these iterations on a reasonably sized initial sample.
  • computing the inverse matrix is a fairly expensive operation that you do not want to do once per element

So at least you should do a batch-window type of approach (to reduce the number of matrix inversions you need to compute; i'm not aware of an incremental update to the inverse matrix); maybe repeating on each batch until convergence (to improve quality).

$\endgroup$
  • $\begingroup$ I've updated my question. Before talking about doing it incrementally, I'm a little confused on how to do it iteratively. Can you please see my first question, and tell me if it makes sense, and how to update the parameter values after each step ? $\endgroup$ – shn Oct 8 '12 at 14:59
  • $\begingroup$ I've updated the reply. $\endgroup$ – Has QUIT--Anony-Mousse Oct 8 '12 at 15:21
  • $\begingroup$ The center of each cluster is a mean vector, ok, but is this the parameter $\mu_j$ that we are talking about when we talk about the probability density $P(x_i|\theta_j)$ ? I thought that we are talking about the mean distance of data-points to the cluster center, and this is what I called $\mu_j$, so it seems that I did not understood well. I was trying to estimate the parameters $\theta_j = \{\mu_j, \sigma_j\}$ that are "the mean distance" of data-points of the gaussian mixture j to the center of this mixture, and "the corresponding variance" of distances to the center. $\endgroup$ – shn Oct 8 '12 at 15:51
  • $\begingroup$ and now I realize through your answer that it is actually a multivariate gaussian over the dimensions of the data-points. I'll try later to reformulate my question then. $\endgroup$ – shn Oct 8 '12 at 15:52
  • $\begingroup$ $\mu$ is a mean vector, and $\sigma$ (often written as $\Sigma$) is the covariance matrix, which on the diagonal has the regular variances, obviously. $\endgroup$ – Has QUIT--Anony-Mousse Oct 8 '12 at 16:22

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.