Run Forward Backward and Viterbi Algorithms on defined HMMs

Why have such a model?

Usually the data points we encounter in datasets like MNIST, PASCAL etc are assumed to independent and identically distributed. This allows us to apply likelihood function across the data points to model probability distribution. But there are examples of data instances for which making this assumption would clearly be wrong, more specifically time series data points. Time series data is sequential in nature and not all examples of sequential data are time series, some examples for this kind of dataset are accoustic features in speech, sequence of characters, sequence of nucleotide base pairs in a DNA strand etc.

Overview of Markov Models

To exploit the sequential patterns that occur in the data, we need a way to model the correlations between the observations. Markov models use the product rule to express the joint distribution for a sequence of observations,

Assuming that the current observation only depends on the previous observation, a first-order Markov Chain, and using d-separation property to reduce the above equation we get,

We can also create higher orders of markov models in a similar manner.

Overview of Hidden Markov Model

Hidden Markov Models (HMM) are an extension of a mixture model, where there are various discrete multinomial latent variables that could be responsible for generating a particular observation in a sequence. The choice of picking a mixture component or hidden state for a particular observation depends on the choice of component for the previous observation. The transition probabilities are defined by this transition from previous hidden state to the current hidden state based on the observation denoted by A, and emission probabilities are defined by the conditional distribution of the observed variables for each latent variable denoted by B. HMMs in general are not susceptible to local warping and variability in generations, making it an excellent choice for speech recognition, handwriting generation etc.

Forward Backward (Baum-Welch) Algorithm

This algorithm capable of determining the probability of emitting a sequence of observation given the parameters (z,x,A,B) of a HMM, using a two stage message passing system. It is used when we know the sequence of observation but don't know the sequence of hidden states that generates the sequence of observation in question. Let us represent the sequence of observation with X and parameters using theta,

The time complexity of calculating the posterior with just one pass will be for a given sequence of T observations. The complexity can be reduced to , using dynamic programming,

After completing this step, we backtrack through our trellis using the following function,

Viterbi Algorithm

For finding the most probable sequence of hidden states, we use max-sum algorithm known as Viterbi algorithm for HMMs. It searches the space of paths (possible sequences) efficiently with a computational cost that grows linearly with the length of chain. We again use the variables z to represent the hidden states, x to represent the observed sequence, n as the number of hidden states, and T as the length of the observed sequence. Our objective is to find the states that maximize the conditional proabbility of states given sequence of observation,

This can again be solved by the means of dynamic programming, as the current state in a HMM only depends on the previous state. We define a function to represent the maximum joint probability of getting an intermediate observation of the sequence and hidden state as follows:

We can see from the final formula that the last two probability terms are nothing but the transition probability and the emission probabilities. The runtime complexity comes down to be using dynamic algorithm.

References

1. Rabiner LR (February 1989). "A tutorial on hidden Markov models and selected applications in speech recognition". Proceedings of the IEEE. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. doi:10.1109/5.18626. (Describes the forward algorithm and Viterbi algorithm for HMMs).
2. Blasiak, S.; Rangwala, H. (2011). "A Hidden Markov Model Variant for Sequence Classification". IJCAI Proceedings-International Joint Conference on Artificial Intelligence.
3. Christopher M. Bishop "Pattern Classification and Machine Learning" 13.2