Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working on a problem that I've cast as an HMM, except that unlike the "traditional" case where the transition probabilities $a(i,j) = p(s_i = j \,|\, s_{i-1}=i)$, emission probabilities $b(j,o) = p(o_i | s_i = j)$ and initial probabilities $\pi(j) = p(s_0 = j)$ are all just independent numbers, in my case they are (relatively complicated) functions of a set of common parameters. I'm reasonably sure that this means I can't rely on Baum-Welch to find the optimal parameters (because Baum-Welch assumes that the three sets of probabilities can be optimized independently), and I've tried my hand at directly optimizing the likelihood by just computing the likelihood using the forward algorithm. However, this has proved slow (my sequence is extremely long) and somewhat unreliable (the likelihood surface is a bit weird looking). A friend suggested that both of those problems could be solved if I used an EM algorithm (using forward-backward probabilities in the E-step and numerically optimizing in the M-step).

However, I'm having a hell of a time figuring out exactly what the Q function should be. I believe it is $$ Q(\theta\,|\, \theta^{t}) = \sum_j\log(\pi(j))p(s_0 = j \,|\, x, \theta^{t}) \\+ \sum_t\left[\sum_{i,j} \log(a(i,j))p(s_t = j, s_{t-1} = i \,|\, x, \theta^{t}) \right]\\+\sum_t\left[\sum_j\log(b(j,o))p(s_t = j \,|\, x, \theta^{t}) \right]. $$ However, it's not clear to me that this will make life any easier, as it still looks like it's $O(nm^2)$, where $n$ is the length of the sequence and $m$ is the number of hidden states, time to evaluate. And that's in addition to forward-backward run to calculate all the posterior probabilities necessary during the E step.

So I feel like I must be doing something wrong or else missing the point of using the EM algorithm rather than directly optimizing the likelihood in this problem.

share|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.