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.