# Hidden Markov Model

# 2.1 Implementation

The Wikipedia page gives an imperative implementation in pseudo-code and a detailed worked example:

https://en.wikipedia.org/wiki/Viterbi_algorithm

I ported it to Haskell, with the sparse transition matrix represented as a Map of Maps storing log-probabilities (otherwise probabilities get too small and underflow to 0).

I needed to transpose the matrix from my constructed “prefix -> suffix” order, as the algorithm needs to find the most probable path ending at each given suffix.

I also returned the computed log-probability, a value of -Infinity means there was no match at all and the returned path will be garbage (occurs with probability 0).

# 2.2 Partial Observations

One use case I have in mind is generating sequences that are fixed at particular points, but are otherwise unconstrained.

A partial / unconstrained / uninformative observation has an equal probability connection to every internal state.

It seems exact probabilities are not strictly necessary, so giving them all the same arbitrary weight works ok (I used probability 1).

# 2.3 List Of Matches

Haskell’s lazy evaluation makes it straightforward to extend the algorithm to return all matching sequences sorted by probability (most likely first), from which you can take as many as needed.

Instead of storing the most likely previous state at each state at each time step, store a list of (log-probability, path prefix) pairs, with the invariant that they are sorted in descending order. I stored the paths in reverse order to benefit from lazy sharing of tails, and correct that as a post-processing step.

Then the key operation is merging a list of sorted lists, which can be done by folding over the outer list with a pairwise merge.

# 3.1 Fever

See the Wikipedia page linked above.

My experiment with two observed dizzy days spaced apart showed that 10 days would persist a fever but at 11 days apart it would collapse into two single fever days with a healthy period between.

# 3.2 Text

The internal state is 3 sequential characters of text (trigrams).

The observation of a state is the middle character of the three with probability 1, all other characters having probability 0.

The transition matrix is constructed from a long input text sequence (I tested with the Adventures of Sherlock Holmes by Arthur Conan Doyle from Project Gutenberg).