5
$\begingroup$

How can I get the log likelihood or the probability value from the forward algorithm for an observed sequence?

For example, when I executed the forward algorithm in R on a sequence of length 3 for a trained Hidden Markov Model of 3 states, it gave me the probability values for each observed symbol on each state:

$$ \begin{matrix} ~ &O1 & O2 & O3 \\ S1 & -143.2 & -500.0 & -231.5 \\ S2 & -212.2 & -231.4 & -200.0 \\ S3 & -112.4 & -115.6 & -118.5 \end{matrix} $$

In the above matrix, rows are states and columns are observed symbols.

Now how do I calculate the final log likelihood value from this matrix?

$\endgroup$
1
  • $\begingroup$ I know it is late, hope this helps you or anyone else ... Calculate the log likelihood for each sequence .. $\endgroup$
    – user49830
    Jul 9, 2014 at 23:28

1 Answer 1

2
$\begingroup$

When employing the forward algorithm, the overall log-likelihood of the data given the model, P(O|Model), is the logsumexp of the forward log-likelihoods values for the final observation column (alternatively the sum over the probabilities, if you're not working in log-likelihood space).

In your example, the overall log-likelihood would:

$$ \begin{array}{rcl} logsumexp([-231.5, -200, -118.5]) &=& -118.5 + log(e^{(-231.5 - -118.5)} + e^{(-200 - -118.5)} + e^{(-118.5 - -118.5)})\\ &=& -200.0 \end{array} $$

Note, in this calculation I use the logsumexp trick ($logsumexp(x_1, ..., x_n) = x^* + log(exp(x_1 - x^*) + ... + exp(x_n - x^*))$ to prevent overflow/underflow issues.

Let me go just a bit deeper into why this is the case. The forward algorithm starts by computing the log-likelihood for the first observations (column O1) as the sum of the log start probabilities and the log-probability of each datum given each state. Then, the forward algorithm recursively computes the log probability of each state of each sequence as the logsumexp over the log-likelihood + log of the probability of transitioning from each state to the target state + the log-likelihood of the data given target state (or if you're not in log space, then it computes the sum over the product of these three components). Thus, the forward algorithm efficiently sums over all the probabilities of all possible paths to each state for each observation in each sequence. The end result is that the log-likelihood values in the final observation columns represent the likelihood over all possible paths through the HMM. To compute the overall log-likelihood we essentially take this one step further and compute the logsumexp over the final log-likelihoods (i.e., we sum the probabilities over the final states, each of which represent the sum of all possible paths through the hmm).

I realize external linking is discouraged, but page 7 of this guide provides more context and details: https://web.stanford.edu/~jurafsky/slp3/A.pdf.

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to the site. We are trying to build a permanent repository of high-quality statistical information in the form of questions & answers. Thus, we're wary of link-only answers, due to linkrot. Can you expand on this? $\endgroup$ Jul 22, 2019 at 18:57
  • $\begingroup$ Hello, Chris. Welcome to CV! … I don't see a question mark, so I'm not sure about what the question is. Can you help me here? $\endgroup$ Jul 22, 2019 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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