# Figueiredo and Jain's Gaussian mixture EM convergence criterion

I have implemented and been playing around Figueiredo & Jain 's trainer in this paper http://www.lx.it.pt/~mtf/IEEE_TPAMI_2002.pdf for Gaussian mixture. Fig. 2 in the paper depicts the full algorithm. For convenience, I put a screenshot here:

1. From repeat to until is the component-wise EM integrated with the MML scheme. The inequality in yellow determines the convergence, about which the paper only says in Section 5.2 paragraph 2 that "Convergence of CEM$$^2$$ was shown in [11] https://hal.inria.fr/inria-00072916/document with the help of...". The citation [11] proves that component-wise EM (without any exotic criterion like MML) results in a sequence of monotonically decreasing modified log-likelihood $$\{\Lambda_t\}$$ (Section 5) from each round of updating all mixture components. The convergence can be checked by evaluating $$\Lambda_{t-1}-\Lambda_{t}<\epsilon|\Lambda_{t-1}|$$ where $$t$$ denotes the iteration. Here we know $$\Lambda_{t-1}-\Lambda_{t}$$ is always positive because of the monotonicity of $$\{\Lambda_t\}$$.

I am having trouble understanding why Figueiredo & Jain can use the same convergence criterion without proof. The formulation of their loss function is much different from $$\Lambda_t$$. More importantly, from numeric experiments I found it is totally possible that $$\mathcal{L}[\hat{\boldsymbol{\theta}}(t-1),\mathcal{Y}]-\mathcal{L}[\hat{\boldsymbol{\theta}}(t),\mathcal{Y}]<0$$ and the difference is non-negligible. In this scenario, the algorithm would break the loop while in fact the mixture model has not "really" converged in a traditional sense.

So, I can take the absolute value of the yellow part, then each component-wise EM will "really" converge. The final model can be different but the differences are usually not significant.

Has anybody programmed Figueiredo & Jain's algorithm and faced similar problems? I really want to confirm my observations and correctness of my implementation.

2. The second question is minor, as shown in the green box. Each time we erase the least probable component, shouldn't we re-normalize $$\{\hat{\alpha}_m\}_{m=1}^{k_{\max}}$$? In the for loop $$\{\hat{\alpha}_m\}_{m=1}^{k_{\max}}$$ are normalized in each round, so I feel a normalization at the green box would make it consistent. Again, I found it does not affect the final model too much.

Thank you very much!

Update 20190828: I found github user abriosi implemented GMM-MML in Python here: https://github.com/abriosi/gmm-mml/blob/master/gmm_mml/gmm_mml.py. At line 217, he took the absolute difference in loss as the convergence criterion, which seems more appropriate. He also normalized $$\{\hat{\alpha}_m\}_{m=1}^{k_{\max}}$$ at the green box (line 243 in his code).

Update 20190829: thanks to Goncalo Abreu (github user abriosi)'s reference, Professor Mario answered the question.

Update 20190904: read FJ's source code thoroughly. Difference between the source code and the pseudo code is substantial. Edited the pseudo code below:

Two major differences. In Line 8, the source code updates the mixture weights differently with much cheaper computational costs. In Line 19, the absolute error between the plain log-likelihoods of the current and the last iteration determines CEM$$^2$$'s convergence. The paper was using the MML cost function. The MML cost function (Line 20) is also slightly different.

The trainer seems not as good as the paper claimed. For the 4D iris data set, using the paper's random initialization setup, more than 30% of the time it outputs a model having more or fewer than 3 mixture components.

The Matlab source code sometimes halts due to numeric precision issue during matrix operation.

Unsure how much of these changes would contradict the theoretical context embellished by the paper.