One problem with Markov models of order k is that they quickly
become intractable for large k. For example,
for a multinomial state variable
, the number of
required parameters for representing the transition probabilities
is
. This necessarily restricts one to using a small
value of k. However, most observed sequential data
of interest do not satisfy the Markov assumption
for k small. As stated above, it may however be that
the sequential data to be modeled warrants the hypothesis that
at time t, past data in the sequence can be summarized
concisely by a state variable.
This is precisely the idea behind
Hidden Markov Models: we do not assume that the observed process
is Markovian, but instead introduce another process
that
has this property. We therefore have two processes:
is Markovian
but not observed, and
is observed and easy to model when
is given.
HMMs are generally taken to be of order 1 because an HMM of order 1 can
emulate an HMM of any higher order by increasing the number
of values that the state variable can take.
In simple terms, the state variable
summarizes
all the relevant past values of the observed and hidden variables
when one tries to predict the value of the observed
variable
, or of the next state
.
Figure 2: Probabilistic graphical model representing
the independence assumptions of a Hidden Markov Model (order 1).
The state sequence is
, and the output
(or observation) sequence is
.
Let us consider a simple ``fantasy economy''
example illustrating the concept
of hidden Markov models. Suppose that the economy of
a country is controlled by a hidden demon which can be
in either one of two states:
happy, or
unhappy. When
the demon is in the happy state, we generally observe
increases in the value of stock shares. When it is in the
unhappy state, we generally observe decreases in
their value. Furthermore, that demon tends to remain happy
for several months before switching from one state
to the next. More precisely, each month, it randomly decides to
change state or remain in the current state with a
probability that depends only on the current state.
When we are given a sequence
of binary observations
representing the increase or decrease in stock prices,
we may want to know with what probability
the current state is happiness or unhappiness. The parameters
of the model could be the transition probabilities from
one state to the next, and the probabilities of stock prices
increases or decreases associated to each state (i.e., the emission
probabilities). After these parameters are estimated,
we can answer questions such as, what is the most likely
sequence of states, given the observations
?
(the Viterbi algorithm answers that question), or
what is the probability of the current state given
the past sequence of observations, or more generally,
what is the state probability at a particular time step given a
certain sequence of observations? Another interesting
question we could answer is: what is the probability of increase
in stock price for next month? Of course, these answers
would only be as good as our estimation of the parameters
(which depends on the number of observations)
and correctness of the model (are there really only
two states? is the direction of price change sufficient
to characterize the demon's behavior? etc...).
In many applications in which the state variable is a
discrete variable, all the state sequences are forced
to start from a common initial state (i.e.,
is 1 for this value of the state and 0 for the other values)
and end in a common final state, and many
transition probabilities are forced to have the value 0,
using prior knowledge to structure the model. In the
speech recognition literature, one often talks of states
to mean the different values of the state random variable,
and of a transition between two states (for which
the transition probability is non-zero). To represent
the structure imposed by the choice of zero on non-zero
transition probabilities (i.e., the existence of transitions),
one talks of the topology of an HMM. Such a topology
is represented in a graph such as the one of Figure 3,
in which nodes represent values of the state variable
(i.e., states), and arcs represent transitions
(i.e., with non-zero probability). Such a graph should
not be confused with the probabilistic graphical models
introduced earlier, in which each node represents a
random variable.
Figure 3: Example of a left-to-right topology for an HMM which may be
used in a speech recognition system to represent the distribution of acoustic
sequences associated with of a unit of speech (e.g., phoneme, word). Note
this is NOT the representation of a probabilistic graphical model: a
node represents a value of the discrete state variable
, and an arc
represents a transition with non-zero probability between two values of the
state variable. The oval in this picture corresponds to a symbolic meaning
(e.g., a particular word) associated to the group of states within the oval.
In a common variant of the above model, the emissions are not dependent only on the current state but also on the previous state (i.e., on the transitions):
In any case, the computation of the joint probability
is
therefore straightforward (done in time O(T)). However,
is not
observed, and we are really interested in representing the distribution
. Simply marginalizing the joint distribution yields an exponential
number of terms (here when
is discrete):
where the sum is taken over all the possible values of the sequence
of states
.
In the case of discrete states, there is fortunately an efficient
recursive way to compute the above sum, based on a factorization
of the probabilities that
takes advantage of the Markov property of order 1. The recursion
is not on
itself but on
, i.e., the
probability of observing a certain subsequence while the state takes a
particular value at the end of that subsequence:
where we used the two Markov assumptions (on the observed
variable and on the state) respectively to obtain the second
and last equation above. The recursion can be initialized with
, using the initial
state probabilities
. This recursion is true
whether the model is homogeneous or not (and the probabilities
can be conditioned on other variables). This recursion is
central to many algorithms for HMMs, and is often
called the forward phase. It allows to compute
the likelihood function
,
where
are parameters of the model which can be
tuned in order to maximize the likelihood over the
training sequences
, indexed by the sequence number p,
and with
the length of the p-th sequence.
The computational cost of this recursion is O(T m)
when T is the length of a sequence and m is
the number of non-zero transition probabilities
at each time step, i.e.,
(where n is the number of
values that the state variable
can take).
Note that in many applications
because prior knowledge imposes a structure on
the HMM, in the form of zero probability for
most transitions.
Once
is obtained, one can readily compute
the likelihood
for each sequence as follows:
Note that we sometimes drop the indexing of probabilities
on the parameters
unless the context
would make that notation ambiguous.