Performance of smooting vs viterbi algorithm with HMMs

Question

To experiment, I implemented a discrete HMM; the transition matrix and emission model are randomly, uniformly generated. Then, a sequence of random states and emissions are produced by the HMM. Then I run smoothing (forward-backward algorithm) to identify the most likely states at each time. Finally I run the viterbi algorithm to identify the most likely sequence.

Because I know the true sequence of states, I can compare how well the two algorithms predict the actual sequence. With #states = 2, #emission types = 2, and sequenceLength=100, viterbi gets about 60% of the states correct, while smoothing gets about 73% correct.

Does this make sense? My prior was that viterbi would get more correct than smoothing, but I'm relatively uncertain. Also, it seems disappointing that viterbi is only 10% better than random guessing. I'm wondering if there's a bug in my implementation.

Any confirmation one way or the other would be greatly appreciated.

Answer 1

Viterbi is not necessarily always better than smoothing. Viterbi returns the MAP estimate, but for some region in the input space, there might be too high of uncertainty that it is better to go with the "reject option". This is mentioned in Kevin Murphy's "Machine Learning: a probabilistic perspective" section 17.4.1, and I quote:

It is not surprising that smoothing makes fewer errors than Viterbi, since the optimal way to minimize bit-error rate is to threshold the posterior marginal.

I can't say I completely understand this issue with Viterbi, but wanted to share nontheless i