An incremental Gaussian mixture model 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".
 A: [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).
