monus-weighted-search-0.2.0.0: Efficient search weighted by an ordered monoid with monus.
Copyright(c) Donnacha Oisín Kidney 2021
Maintainermail@doisinkidney.com
Stabilityexperimental
Portabilitynon-portable
Safe HaskellNone
LanguageHaskell2010

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.

Synopsis

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.

data Obs Source #

The possible observations.

Constructors

Normal 
Cold 
Dizzy 

Instances

Instances details
Eq Obs Source # 
Instance details

Defined in MonusWeightedSearch.Examples.Viterbi

Methods

(==) :: Obs -> Obs -> Bool #

(/=) :: Obs -> Obs -> Bool #

Show Obs Source # 
Instance details

Defined in MonusWeightedSearch.Examples.Viterbi

Methods

showsPrec :: Int -> Obs -> ShowS #

show :: Obs -> String #

showList :: [Obs] -> ShowS #

data States Source #

The possible hidden states.

Constructors

Healthy 
Fever 

Instances

Instances details
Eq States Source # 
Instance details

Defined in MonusWeightedSearch.Examples.Viterbi

Methods

(==) :: States -> States -> Bool #

(/=) :: States -> States -> Bool #

Show States Source # 
Instance details

Defined in MonusWeightedSearch.Examples.Viterbi

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 x applies f 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])