# Forward, Backward and Viterbi Algorithms

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.