The forward, backward, and Viterbi algorithms have all been implemented in the hidden-markov-music.hmm namespace, whose most current version is always documented here. See here for the source code, or standalone jar.

The three algorithms are implemented in

To test the validity of these functions, they were tested against examples from Oliver C. Ibe’s Markov Processes for Stochastic Modeling, and produced consistent results. I also tested them against some extreme models I designed, which gave sensible results.

For example, I made a fully deterministic model, where all probabilities are 0.0 or 1.0. I constructed two observation sequences O, one which is certain to be observed, and another which is impossible to observe. Both the forward and backward approaches gave P[O|λ] = 1.0 for the certain observation sequence, and P[O|λ] = 0.0 for the impossible one. The Viterbi algorithm gave the correct state sequence for the possible observations, with likelihood 1.0, and a repetition of one state for the impossible observations, with likelihood 0.0. The latter was an interesting result, as any state sequence would be equally invalid, but that may be due to the fact that my implementation only returns one state sequence if more than one share equal likelihood.

As another example, I made a model with a 50/50 initial probability of starting in one of two states, but all subsequent states are deterministic. The two possible observation sequences gave P[O|λ] = 0.5, and the Viterbi path returned the correct state sequence for each with likelihood 0.5. I was surprised the likelihood was not 1.0, since the observations were known, but my intuition was wrong.