depth first search

I needed to apply the Viterbi algorithm for a recent homework. The problem set suggested using the HiddenMarkov CRAN package. Here’s the help page for the dthmm function:

dthmm              package:HiddenMarkov              R Documentation

Discrete Time HMM Object

Description:

Creates a discrete time hidden Markov model object with class
'"dthmm"'.

Usage:

dthmm(x, Pi, delta, distn, pm, pn = NULL, discrete = NULL,
nonstat = TRUE)

Arguments:

x: is a vector of length n containing the observed process.
Alternatively, 'x' could be specified as 'NULL', meaning that
the data will be added later (e.g. simulated).

Pi: is the m times m transition probability matrix of the
homogeneous hidden Markov chain.

delta: is the marginal probability distribution of the m hidden
states at the first time point.

distn: is a character string with the distribution name, e.g.
'"norm"' or '"pois"'. If the distribution is specified as
'"wxyz"' then a distribution function called '"pwxyz"' should
be available, in the standard R format (e.g. 'pnorm' or
'ppois').

pm: is a list object containing the (Markov dependent) parameter
values associated with the distribution of the observed
process (see below).

pn: is a list object containing the observation dependent
parameter values associated with the distribution of the
observed process (see below).

discrete: is logical, and is 'TRUE' if 'distn' is a discrete
distribution. Set automatically for distributions already
contained in the package.

nonstat: is logical, 'TRUE' if the homogeneous Markov chain is assumed
to be non-stationary, default. See "Details" below.

It’s okay. I don’t understand it either.

What I remember from lecture is that for discrete time HMMs you need a matrix of transition probabilities (the probability of a next state given the current state) and a matrix of emission probabilities (given a particular state, the probability of seeing a particular observation).

Ideally, I’d like an example of how to do just that — specify two matrices and a starting state and generate a whole bunch of HMM samples. Try as I might, I couldn’t figure out how to do that using the R function above. I’m sure it is possible, it just doesn’t seem to be obvious.

Now consider the MATLAB documentation.

Setting Up the Model and Generating Data

This section shows how to set up a hidden Markov model and use it
to generate data. First, create the transition and emission
matrices by entering the following commands.

TRANS = [.9 .1; .05 .95;];

EMIS = [1/6, 1/6, 1/6, 1/6, 1/6, 1/6;...
7/12, 1/12, 1/12, 1/12, 1/12, 1/12];

Next, generate a random sequence of emissions from the model,
seq, of length 1000, using the function hmmgenerate. You can also
return the corresponding random sequence of states in the model
as the second output, states.  [seq, states] = hmmgenerate(1000,
TRANS, EMIS);

Note In generating the sequences seq and states, hmmgenerate
begins with the model in state i0 = 1 at step 0. The model then
makes a transition to state i1 at step 1, and returns i1 as the
first entry in states.  Computing the Most Likely Sequence of
States

Suppose you know the transition and emission matrices, TRANS and
EMIS. If you observe a sequence, seq, of emissions, how can you
compute the most likely sequence of states that generated the
sequence? The function hmmviterbi uses the Viterbi algorithm to
compute the most likely sequence of states that the model would
go through to generate the given sequence of emissions.
likelystates = hmmviterbi(seq, TRANS, EMIS);

likelystates is a sequence of the same length as seq.

You’ll notice that the functions take precisely the arguments you would expect, nothing more, nothing less. Moreover, the documentation takes you through setting up an HMM in exactly the same way as HMMs are normally taught.

Perhaps the MATLAB functionality is more limited that the R functionality, but I think there is something to be said for making the easy case easy, which R clearly doesn’t. I’m not always a fan of MATLAB, but the platforms competitive advantage seems to be the simplicity of the interface to a number of complex algorithms. This allows the average academic to quickly make use of a lot of powerful building blocks, building blocks that are not nearly so easy to use in other languages.