next up previous
Next: Parametrization: Choice of Distributions Up: Hidden Markov Models Previous: Hidden Markov Models

Hidden State

 

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.


next up previous
Next: Parametrization: Choice of Distributions Up: Hidden Markov Models Previous: Hidden Markov Models

Yoshua Bengio
Tue Oct 7 08:34:36 EDT 1997