Dear Anselmo,

As you probably know, the EM algorithm has the property to increase the likelihood for each step. But that does not imply convergence. As an alternative to convergence to a local maximum, the sequence may approach the boundary of the parameter space, where the likelihood may be infinite. If the likelihood goes to infinity, the EM algorithm will typically be fast.

However, there are alternative interpretations of what you say you experienced. It is frequently the case that the likelihood has a ridge shape. The first few EM iterations quickly climb up the ridge, but later iterations slowly move along the ridge towards a more or less distant maximum, that is only slightly higher than where you entered the ridge. Characteristic of this situation is that the difference between successive points is changing very slowly in direction and decreasing very slowly in length. Perhaps your approximate E-step contributes to the problem, if you have the ridge form.

Unless you have already done so, you should experiment with different starting points, including points far away in the direction of your iterations, in order to understand the form of the (log) likelihood surface. Note also that the interpretation of an (almost) flat ridge is lack of parameter identifiability: there is a function of your parameters that data do not yield (almost) any information about.

When you have made further investigations of your situation, please report your experiences.

Best wishes,

Rolf Sundberg

Stockholm University

(EM experiences since 1970)

Dear Anselmo,

As you probably know, the EM algorithm has the property to increase the likelihood for each step. But that does not imply convergence. As an alternative to convergence to a local maximum, the sequence may approach the boundary of the parameter space, where the likelihood may be infinite. If the likelihood goes to infinity, the EM algorithm will typically be fast.

However, there are alternative interpretations of what you say you experienced. It is frequently the case that the likelihood has a ridge shape. The first few EM iterations quickly climb up the ridge, but later iterations slowly move along the ridge towards a more or less distant maximum, that is only slightly higher than where you entered the ridge. Characteristic of this situation is that the difference between successive points is changing very slowly in direction and decreasing very slowly in length. Perhaps your approximate E-step contributes to the problem, if you have the ridge form.

Unless you have already done so, you should experiment with different starting points, including points far away in the direction of your iterations, in order to understand the form of the (log) likelihood surface. Note also that the interpretation of an (almost) flat ridge is lack of parameter identifiability: there is a function of your parameters that data do not yield (almost) any information about.

When you have made further investigations of your situation, please report your experiences.

Best wishes,

Rolf Sundberg

Stockholm University

(EM experiences since 1970)

Dear Rolf, I really appreciate your reply! Parameter identifiability is in fact an issue in the problem I am approaching. There are theoretical conditions under which identifiability is guarateed, but I must admit I did not verified them carefully in the particular instance I am testing. I have tried multiple starts, and the problem kept ocurring. What I found strange is that the first EM iteration is significantly closer to the real parameter values, in comparison to the starting point, and then from the second iteration onwards, the solution slowly moves away from the real values. This matches your description of a flat ridge...

I will report as soon as I have new results.

Best regards

Anselmo

Universidade Federal do Ceará (Brazil)

(newcomer in the realm of EM algorithm)

Dear Anselmo,

I'm having the same situation regarding a flat ridge ! have you found a way to decide what is the best parameters for EM ? I have no knowledge about the sequences that I work on so, it is not easy to judge if the log likelihood is getting converged or it has a lack of parameter identifiability !

can you tell me please. 

thanks 

Amirah 

PhD researcher 

Dear Amirah Alharbi, I changed my approach and used Bayesian statistics. You can overcome issues with lack of identifiability by specifying prior distributions. It works like a "regularization" to the problem.

Anselmo, concerning a Bayesian solution: if your likelihood has a ridge it means your data cannot say which parameter values along the ridge are most likely. If you have some safe prior information, for example in the form of a prior distribution for the parameters, this might resolve the situation, but you must keep in mind that the resulting solution is precisely as good as your prior information, so if the prior is not quite realistic, the solution need not be any good. It is often difficult to formulate reasonable priors for multidimensional parameters, and different priors will yield different solutions, since data do not help more than pointing to the ridge.

Amirah, if there is a maximum (but you do not know), and you make a big enough jump along the ridge (i.e. in the direction of your sequence) to form a new starting point you should get a new sequence going in the opposite direction. But even so, if the ridge is quite flat you have essentially a lack of identifiability, even though it need not be exact.

You are right, dear Rolf. In the problem I approached in my doctorate research, the parameters to be estimated are related by an underdetermined linear system of equations. The resulting probabilistic model has unindentifiable parameters. The likelihood carries information about the parameters, but it is not sufficient to uniquely define an estimator according to maximum likelihood principle. (the likelihood function may not be strictly concave). This is independent of the sample size. In this case, the influence of the prior on the posterior never vanishes, regardless of the amount of data one has.

Dear Rolf Sundberg , thanks for your reply.

since you are an expert with the EM from 1970 , I really need and appreciate your help please !

I could not understand what do you mean by " you should get a new sequence going in the opposite direction. "?

In my case there are around 365 sequences and I got a good jump where the training start.

1- so, to solve the flat ridge can I stop earlier the search space ? I mean rather makes the tolerance change between models 1e-8 just make it 1e-6 ?

2- is there a way to determine the source behind the lack of identifiablility ?

3- another problem I face is that, I got two best log likelihood in HMMs lets say with 4 hidden states and with 8 hidden states what should I do in this case ? should I select the model with 4 hidden states or 8 hidden states since they both have highest log likelihood ?

sorry for log questions

thanks again

Amirah Alharbi

I know the reason because Q should decrease in some case!

See my paper https://arxiv.org/abs/1810.11227 with title : From the EM Algorithm to the CM-EM Algorithm for Global Convergence of Mixture Models.