| Copyright | (c) Donnacha Oisín Kidney 2021 |
|---|---|
| Maintainer | mail@doisinkidney.com |
| Stability | experimental |
| Portability | non-portable |
| Safe Haskell | None |
| Language | Haskell2010 |
MonusWeightedSearch.Examples.Viterbi
Description
An implementation of the Viterbi algorithm using the Heap monad.
This algorithm follows almost exactly the example given on Wikipedia.
This actually implements the lazy Viterbi algorithm, since the heap prioritises likely results.
Documentation
>>>import Data.Bifunctor (first)>>>:set -XTypeApplications
type Viterbi = Heap Prob Source #
A heap of probabilities; similar to a probability monad, but prioritises likely outcomes.
The possible observations.
start :: Viterbi States Source #
Then initial states (i.e. the estimated fever rate in the population).
trans :: States -> Viterbi States Source #
The transition function: how likely is a healthy person to be healthy on the following day? How likely is someone with a fever today to have one tomorrow?
emit :: States -> Viterbi Obs Source #
Given the hidden state, what is the likelihood of the various observations.
iterateM :: Monad m => Int -> (a -> m a) -> m a -> m [a] Source #
iterateM n f xf to x n times, collecting the results.
likely :: [Obs] -> (Prob, [States]) Source #
Given a sequence of observations, what is the most likely sequence of hidden states?
For instance, if you observe normal, then cold, then dizzy, the underlying states are most likely to be healthy, then healthy, then fever, with probability 0.01512.
>>>first (realToFrac @_ @Double) (likely [Normal,Cold,Dizzy])(1.512e-2,[Healthy,Healthy,Fever])