Mealy and Moore HMMs

Objective

CMPy provides two hidden Markov model classes: MealyHMM and MooreHMM. This tutorial demonstrates how to build these machines from their defining matrices.

Nomenclature

In transducer automata theory, there are two celebrity model types, known as Mealy and Moore machines. Mealy machines emit output symbols which depend on the current state and input symbol. In contrast, Moore machines emit outputs which depend only on the current state—the role of input symbols is soley to determine the next state of the machine.

In applying computational mechanics to time-series, the traditional model has been a stochastic generator (not a recognizer or transducer) known as an \epsilon-machine. \epsilon-Machines are a particular type of hidden Markov model whose state dynamic is such that the next state \AlternateState_{t+1} is jointly determined by the current state \AlternateState_t and the current output symbol \MeasSymbol_t.

The coupling between the current state and output symbol reminds us of the coupling between the current state and input symbol for Mealy transducers. For this reason, we have adopted the name MealyHMM, but really, this is just a fancy way of saying that we are working with HMMs which emit symbols while on the edges. We might also call these machines edge-emitting HMMs.

It turns out that there is another type of HMM which emits symbols while in the current state. There exists a dynamic over the states such that the next state is determined solely by the current state. The independence between the current state and output symbol reminds us of the independence between the current state and input symbol for Moore transducers. For this reason, we have adopted the name MooreHMM, but this too is just a fancy way of referring to an HMM which emits symbols while in the current state. Simiarly, we might use the phrase state-emitting HMMs.

MealyHMM

The dynamic for MealyHMM is determined by the labeled transition matrices T^{(x)} for all \meassymbol \in \MeasAlphabet. If we have these matrices defined, there are a number of ways to automatically build a MealyHMM in CMPy. First, let’s define some matrices:

import numpy as np

T0 = np.array([[.5, 0],[0,0]])
T1 = np.array([[0, .5],[1,0]])

Now, we can use the from_matrices function to construct a machine:

from cmpy.machines import from_matrices
ltm = [('0', T0), ('1', T1)]
m = from_matrices(ltm)

The docstring for from_matrices shows us that the style parameter defaults to the value 0, and this is why we get a MealyHMM. We can make this explicit, name the nodes of the machine, and change our input format just slightly:

ltm = {'0': T0, '1': T1}
m = from_matrices(ltm, nodes=['A', 'B'], style=0)
m.draw()
../_images/even.png

The from_matrices() function is a friendly wrapper around various conversion functions. Note that we input the matrices as a dictionary this time—so it tries to be nice to input too.

MooreHMM

MooreHMM objects can be created from their defining matrices as well, a node-transition matrix and an emission matrix:

ntm = np.array([[0,1],[1,0]])
em = np.array([[1,0],[0,1]])
m = from_matrices((ntm, em), nodes=['A', 'B'], symbols=['0', '1'], style=3)
m.draw()
../_images/period1.png