gaussian mixture distributionmachine learning
A somewhat soft question – I'm training a Gaussian mixture model (with the EM algorithm) on data of size $N$ ($N$ is typically between 4 and 64).
How much samples do I need? obviously it depends on the data, but is there a thumb rule?
Also, is there a method to assess whether the model is trained properly? I can look at the log-likelihood function and see its convergence, but what about its value? can that serve as an 'estimation' of some sort to the success of the training?
Thanks.
First, GMM is a particular algorithm for clustering, where you try to find the optimal labelling of your $n$ observations. Having $k$ possible classes, it means that there are $k^n$ possible labellings of your training data. This becomes already huge for moderate values of $k$ and $n$.
Second, the functional you are trying to minimize is not convex, and together with the size of your problem, makes it very hard. I only know that k-means (GMM can be seen as a soft version of kmeans) is NP-hard. But I am not aware of whether it has been proved for GMM as well.
To see that the problem is not convex, consider the one dimensional case: $$ L = \log \left(e^{-({x}/{\sigma_{1}})^2} + e^{-({x}/{\sigma_{2}})^2}\right) $$ and check that you cannot guarantee that $\frac{d^2L}{dx^2} > 0$ for all x.
Having a non-convex problem means that you can get stuck in local minima. In general, you do not have the strong warranties you have in convex optimization, and searching for a solution is also much harder.
The EM algorithm is really just an iterative approximation to true Maximum Likelihood Estimation. Even if implemented correctly,
In practice, one often runs the EM procedure several times, with different starting conditions, to avoid mistaking a local optimum for a global one.
I think this is a good opportunity to highlight a passage by the late great MacKay, who uses this particular corner case to attack the principle of MLE in general:
KABOOM!
Soft K-means can blow up. Put one cluster exactly on one data point and let its variance go to zero - you can obtain an arbitrarily large likelihood! Maximum likelihood methods can break down by fi nding highly tuned models that fit part of the data perfectly. This phenomenon is known as over fitting. The reason we are not interested in these solutions with enormous likelihood is this: sure, these parameter-settings may have enormous posterior probability density, but the density is large over only a very small volume of parameter space. So the probability mass associated with these likelihood spikes is usually tiny.
We conclude that maximum likelihood methods are not a satisfactory general solution to data-modelling problems: the likelihood may be in finitely large at certain parameter settings. Even if the likelihood does not have in finitely large spikes, the maximum of the likelihood is often unrepresentative, in high dimensional problems.
Even in low-dimensional problems, maximum likelihood solutions can be unrepresentative. As you may know from basic statistics, the maximum likelihood estimator (22.15) for a Gaussian's standard deviation is a biased estimator, a topic that we'll take up in Chapter 24.
(Note that what he calls "soft k-means" is just EM.)
Best Answer
The number of data points needed will depend on the dimensionality of the data, the number of mixture components, and whether you use any constraints/priors (e.g. shared covariance matrix, diagonal covariance matrix, regularized covariance matrices, etc.). It will also depend on the data itself, so it's hard to give an exact number.
As a lower bound, consider a Gaussian mixture model with $d$ dimensions and $p$ mixture components, each with a separate covariance matrix. For each component, you'll have to estimate a mean vector ($d$ elements) and covariance matrix ($d \cdot (d+1)/2$ independent elements, because it's a symmetric matrix). You'll also have to estimate the $p$ mixture weights. So, your total number of parameters is $p \cdot (d^2/2 + 3d/2 + 1)$. You will certainly need more data points than parameters. Several times more.
To see the effect of constraints, consider that using a shared covariance matrix will reduce the number of covariance matrix parameters by a factor $p$ (because you only need to estimate a single matrix instead of $p$ of them). Or, a diagonal covariance matrix will have $d$ independent elements instead of $d \cdot (d+1)/2$. Using a low-dimensional mixture model (e.g. mixture of factor analyzers) will similarly reduce the number of parameters. The issue of regularized covariance matrices and other types of priors is more subtle. All of these methods will reduce the number of samples needed by reducing the flexibility of the model.
The danger of using the likelihood of the training data as a goodness-of-fit criterion is overfitting. It's possible that the model could learn to fit random structure in your training set that isn't representative of the underlying distribution from which the data were drawn. In this case, the model could perform poorly on future data drawn from the same distribution. What to do depends on your goal. If you want to compare multiple models to each other, the thing to do is look into 'model selection'.