Posterior probability vs. Viterbi algorithm

Question

I was working through HMM R package and used posterior as well as Viterbi algorithm:

R> hmm = initHMM(c("A","B"), c("L","R"), transProbs=matrix(c(.8,.2,.2,.8),2),
+       emissionProbs=matrix(c(.6,.4,.4,.6),2))

R> observations = c("L","L","R","R")

# Calculate posterior probablities of the states
R> posterior = posterior(hmm,observations)
R> print(posterior)
      index
states         1       2       3         4
     A 0.6037344 0.56639 0.43361 0.3962656
     B 0.3962656 0.43361 0.56639 0.6037344



R> viterbi = viterbi(hmm,observations)
R> print(viterbi)
[1] "A" "A" "A" "A"

So in the above example if I would consider posterior results and take sequence of hidden states according to highest probability at each position, then I would get

"A" "A" "B" "B"

but the Viterbi algorithm tells me that the sequence is

"A" "A" "A" "A"

My question is which sequence should I trust and why?

Answer 1

First note that with the specified hidden Markov model the "B" "B" "B" "B" state sequence has the same conditional probability as the "A" "A" "A" "A" sequence given the emissions and the implementation just happens to pick one arbitrarily over the other. However, introducing a small asymmetry in the emission probabilities the A-sequence will be the unique result from the Viterbi algorithm without changing the substance of the question.

The Viterbi algorithm computes the most probably sequence of states from the specified HMM given the emissions. If the states are $X_1, X_2, X_3, X_4$ then the probability $$P(X_1 = A, X_2 = A, X_3 = A, X_4 = A \mid Y_1 = L, Y_2 = L, Y_3 = R, Y_4 = R)$$ is the largest amongst all probabilities of state sequences given the emissions.

The posterior function computes the marginal conditional distributions $$X_i \mid Y_1 = L, Y_2 = L, Y_3 = R, Y_4 = R$$ for $i = 1, 2, 3, 4$.

The two computations provide two different pieces of information about the state distribution. If you sample state sequences from the conditional distribution of states given the emissions, the sequence "A" "A" "A" "A" is the most frequently observed state sequence $-$ this is what the Viterbi algorithm tells us. However, if you look at the fourth state $X_4$, say, this state will take the value "B" in just above 60% of the cases.

It is generally not possible to just paste together the most probable states from the marginal conditional distributions to a sequence and claim that the resulting sequence has merits as a sequence. If some transitions (when there are at least 3 states) have probability 0 the resulting sequence can have probability 0 and will thus never be observed.

Even though the Viterbi algorithm computes the most probable sequence I would still hesitate to say that one can "trust" the sequence. It usually still has a very small probability by itself, and it is generally difficult to say if it has any value as a representation of the "typical" state sequence given the emissions. The state sequence space is for general HMMs a large discrete set, and the distribution can be "multimodal", which is not revealed by the most probable sequence. In cases where the state sequence is of primary interest the Viterbi algorithm has some merits, but if the model is used as an intermediate step for imputation of state variables before a downstream analysis, I would recommend, if possible, to avoid the hard imputation and work with the conditional distribution of states given emissions as provided by the model. For instance through simulations.

Answer 2

Viterbi gives most likely sequence, posterior (Forward-Backward) gives most likely state at each position. Which one you choose depends on what kind of errors you prefer -- if you care about the number of sequences you get correctly, then Viterbi algorithm is preferable, if it's the number of individual state errors, then, Forward-Backward is better.