Friday, 19 October 2012

Introduction to Hidden Markov Models

A Markov model is called ‘hidden’ when you don’t always know the current state that the system is in.

Just to remind ourselves; when I say ‘state’ I’m talking about the current value of the randomly changing variable being modeled as a Markov process. If the variable is ‘weather’, the states are things like ‘rainy’, ‘sunny’, ‘cloudy’, etc. This set of weather states is a Markov process, but NOT a hidden one, because we can know what the weather is like by looking outside.

state = 'angry deity'

What systems have states that you can’t see?

The classic example is a person talking. When you’re listening to someone speak, you can hear the sounds they are making, but you can’t be completely certain what words those sounds correspond to. Why not? Well, they might misspeak accidentally, or you might mishear them because there was noise in the background, or you might misinterpret them because of a grammatical ambiguity.

This is exactly the sort of thing that happens when people don't understand HMMs.

In this example, the system’s states are the words the person intends to say. What you observe, called the system’s ‘outputs’ are the sounds you are hearing. The two do not always match up, so it’s as if the states (words) are partially hidden from you. However, if we know:

  •  the transition probabilities of the underlying states, and
  •  the likelihood of each state producing each output

… then we can make some good estimates about what kind of underlying states the system went through given a particular list of outputs. We can even do things like find out which series of states is the most likely using the Viterbi formula.

So, what’s the difference between a Markov model and a hidden Markov model? A Markov model is part of a hidden Markov model; its set of underlying states is always a Markov process. Hidden Markov models just have the extra property that the current state in the Markov process isn’t known for certain, so we have to guess it based on outputs of the system that are known for certain.

Next Post: The Viterbi Formula!

No comments:

Post a Comment