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?


$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.


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.

  • 4
    $\begingroup$ 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. $\endgroup$
    – Lucas
    Commented Dec 20, 2014 at 17:31
  • 1
    $\begingroup$ @Lucas: Here is a Cross Validated link to your remark. $\endgroup$
    – Xi'an
    Commented Dec 20, 2014 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.

  • $\begingroup$ OK, L is unbounded if variance is 0. But if we exclude them from possible parameters (so we assume all variance > 0), then L shoudn't be so high whenever infinitesimal chosen variance (because of other points). Am I right? Then, for this possible set of parameters, L would be bounded, and this will imply that EM algorithm converges (increasing bounded sequence). $\endgroup$
    – ahstat
    Commented May 6, 2018 at 3:52
  • 1
    $\begingroup$ @ahstat: assuming the variances are strictly positive does not prevent EM to converge to a degenerate solution if started close enough. $\endgroup$
    – Xi'an
    Commented May 6, 2018 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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