CL-HMM Library

Simple Hidden Markov Model library for ANSI Common Lisp. Main structures and basic algorithms implemented. Performance speed comparable to C code. It's licensed under LGPL.

Features

Discrete observation densities
Exponential state duration densities
Homogeneous HMMs. First order
Tied emission parameters
Simple model definition
Finite and infinite HMMs
Forward/Backward scaled, Viterbi in log
Baum-Welch for multiple labeled sequences, with normalized noise
Alphabet symbols of any kind
Begin state/s modeled in the initial state distribution. Not explicit begin/end states
ANSI Common Lisp Compliant
Comparable efficiency to GHMM written in C (1x to 2x slower)

Download

The latest stable version is the v0.2

Installation

Dependencies

CL-HMM depends on the following systems. Download them, and load them with asdf.

Actual Installation

Download the latest stable version of CL-HMM and load it with asdf, (asdf:operate 'asdf:load-op :cl-hmm)

Tutorial

Here is given a shallow introduction to the basic procedures. Please refer to the Documentation and to the documentation of each function, for an extended review of these and the whole CL-HMM.

Defining a Model

Suppose an unfair casino that uses a fair die and a biased one. We can model the casino in two ways.

Complete definition


(make-hmm-simple
   2 6 '(1 2 3 4 5 6) ;no of states, no of symbols, alphabet
   '(((:fair #\F) ;definition of the states and their associated labels
      (:biased #\B))
     (0.5 0.5) ;initial probabilities
     ((0.65 0.35) (0.45 0.55)) ;transition probabilities
     ((0.2 0.05 0.05 0.25 0.35 0.1) (0.4 0.2 0.05 0.05 0.15 0.15))) ;emission probabilities
   :alphabet-type 'fixnum ;optional, type of the alphabet
   :model-spec :complete)) ;type of definition

As it's seen, we define all probabilities in list forms. The syntax for the definition of each state is ([name|(group-name index)] [label]). For example (:fair #\F) is the fair state. If for instance two or more stated had the same optional group-name (requiring then a distinguished index), they would share the emission probabilities, which is more useful in the relevant definition.

Relevant definition


(make-hmm-simple
   2 6 '(1 2 3 4 5 6)  
   '((:fair #\F 
      .95 (:@ .95 :> .05) (1/6 1/6 1/6 1/6 1/6 1/6)) 
     (:biased #\B
      .05 (:fair .15 :@ .85) (5/10 1/10 1/10 1/10 1/10 1/10))
    :name :unfair-dice :alphabet-type 'fixnum :model-spec :relevant)

We only have to specify the actual connexions. Notice the use of the shortcuts, :@ to indicate a loop to itself, and :> to indicate a transition to the next defined state.

Random Model

We can use the method (make-random-hmm-simple no-states no-emisions) to generate random models. Check the key parameters to adjust the creation.

Generate Random Observations

Given a model HMM we can generate random observations running it with (hmm-run HMM observation-length). Three values are returned, the observation, the labels of the followed path, and the actual followed path of states.

Forward, Backward, and Viterbi

For the scaled and log-version algorithms:


(forward-scl HMM coded-observation) -> log_probability & alpha matrix & scale
(backward-scl HMM coded-observation scale) -> beta matrix ;scale is the output scale of forward-scl
(viterbi-log HMM coded-observation) -> log_probability & path

The observation must be firstly coded with (cbook)

Training a Model, Baum-Welch

(baum-welch-scl HMM coded-observations)

The observations must be firstly coded with (cbook) or (cbook-list)

Author

CL-HMM is written and maintained by Juan Miguel Cejuela (jmcejuela .a.t. gmail . com) All your feedback is welcome.