Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Consider the log likelihood of a mixture of Gaussians:

$$l(S_n; \theta) = \sum^n_{t=1}\log f(x^{(t)}|\theta) = \sum^n_{t=1}\log\left\{\sum^k_{i=1}p_i f(x^{(t)}|\mu^{(i)}, \sigma^2_i)\right\}$$

I was wondering why it was computationally hard to maximize that equation directly? I was looking for either a clear solid intuition on why it should be obvious that its hard or maybe a more rigorous explanation of why its hard. Is this problem NP-complete or do we just not know how to solve it yet? Is this the reason we resort to use the EM (expectation-maximization) algorithm?


Notation:

$S_n$ = training data.

$x^{(t)}$ = data point.

$\theta$ = the set of parameters specifying the Gaussian, theirs means, standard deviations and the probability of generating a point from each cluster/class/Gaussian.

$p_i$ = the probability of generating a point from cluster/class/Gaussian i.

share|improve this question

2 Answers 2

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.

share|improve this answer
1  
Regarding the second point: k-means can be viewed as a special case of GMMs (more precisely, a limit case where the variances are taken to zero). If we can reduce k-means to the fitting of a GMM, the latter must be an NP-hard problem as well. –  Lucas Dec 20 at 17:31
    
@Lucas: Here is a Cross Validated link to your remark. –  Xi'an Dec 20 at 18:14

In addition to juampa's points, let me signal those difficulties:

  • The function $l(\theta|S_n)$ is unbounded, so the true maximum is $+\infty$ and corresponds to $\hat\mu^{(i)}=x_1$ (for instance) and $\hat\sigma_i=0$. A true maximiser should therefore end up with this solution, which is not useful for estimation purposes.
  • Even without considering the $k^n$ terms in the decomposition of the product of sums as a sum of products in $l(\theta|S_n)$, the function to be maximised in $\theta$ is highly multi-modal (in addition to being non-convex) hence a challenge for numerical methods. EM acknowledges the difficulty by converging to a local mode or saddle point and requiring multiple runs. As shown on the image below

taken from my book.

An additional remark: without calling the EM algorithm, one may use a standard optimisation algorithm (like Newton-Raphson) one parameter at a time, that is, iterate

  • find $\theta_1^\prime=\arg\max_{\theta_1} l(\theta|S_n)$
  • find $\theta_2^\prime=\arg\max_{\theta_2} l(\theta_1^\prime,\theta_{-1}|S_n)$
  • ...
  • find $\theta_v^\prime=\arg\max_{\theta_v} l(\theta_{-v}^\prime,\theta_v|S_n)$

if there are $v$ parameters and each step should increase the value of the target function $l(\theta|S_n)$, but this scheme will at best end up in the same mode as the EM algorithm.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.