Hidden Markov models

  Hidden Markov models (HMMs) are a well-developed technology for classification of multivariate data that have been used extensively in speech recognition, handwriting recognition and even sign recognition. They have been applied for decades. Due to space considerations, an in-depth analysis of HMMs isn't possible. The interested reader may wish to have a look at [RJ86].

HMMs consist of states, possible transitions between states (and the probability of those transitions being taken) and a probability that in a particular state, a particular observation is made. An observation can be anything of interest. For example, it could be a frame in our definition, or it could be a symbol of some kind. HMMs are termed hidden because the state of the HMM can not, in general, be known by looking at the observations. They are Markov in the sense that the probability of observing an output depends only on the current state and not on previous states. By looking at the observations, using an algorithm known as the Viterbi Algorithm, an estimate of the probability that a particular instance or stream observed was generated by that HMM can be computed. We can have one HMM for every class we are interested in, then compute the probability of the particular stream we saw being generated by each of the HMMs, then choose the most probable one.

  
Figure 2.1: A simple HMM where the only observations are j, k, or l

For example, consider figure 2.1. This is a very simple hidden Markov model, with three states. At each timestep, a j, k, or l is observed. We can work out the probability that the sequence [j,j,k,l] was generated by this HMM by considering the most probable state transitions that would generate this output, and computing the probability that it would occur (which is the probability of each output times the probability of the transitions). In this case, the most probable sequence of state transitions (given we start in state 1) is: [1,2,3,3]. The probability of this is . If we had other HMMs, we could compare the probability for each, and choose the HMM that produced the highest probability for the given observed sequence. If we had trained each HMM to have an appropriate set of parameters for a particular class, then by choosing the HMM which generated the observations with the highest probability, we would also know the class.

Note that observations can be very complex, and need not be as simple as a single letter j, k or l. In general, people who use HMMs model multivariate streams by representing each frame as an observation. The probability of a particular frame is estimated by using a Gaussian mixture over the channels.

The Baum-Welch reestimation algorithm provides a way for the probabilities of both transitions and of observations within states to be estimated from training data.

HMMs have proved to be very effective in practice, producing high levels of classification accuracy, but they fail to meet several of the goals discussed in section 1.1, namely:

• The structure of the HMM is not always obvious. Some domain knowledge is required to construct the states and transitions that an HMM can take. In addition, there is trial and error involved, and there are sometimes complex tradeoffs that have to be made between model complexity and difficulty of learning, which results in inelegant additions to HMMs like ``state-tying'' (where two states are ``tied'' by forcing them to have the same output probability distributions).
• They do not produce comprehensible results. In fact, in some cases, considerable effort goes into deciding what the appropriate number of states, transitions and form of probability distributions should be. The distribution and transition probabilities do not provide an intuitive descriptions of what has been learnt.
• They do not have fast learning curves. This is usually because there are a large number of parameters that must be set. For example, consider the HMM in figure 2.1. Even with such a trivial HMM, there are approximately fifteen parameters that need to be set. It is not atypical to see speech recognition systems that have upwards of 200 parameters per state, and twenty states per word.
• They do not automatically cope with multiple variations within the same class. For example, consider the word either. Depending on where you are from, you may pronounce that as ee-thur or ai-thur. Yet both are from the same class. This would have to be explicitly denoted to the HMM classification system, either through an HMM with a complex set of state transitions or two separate HMMs.