Friday, November 13, 2009

Hidden Markov Models (2)

A couple of weeks ago I put up an introductory post about HMMs, and promised more. I got distracted for a bit, but now I'm ready to work on it again. Before we start, let's talk a little more generally about what they are about.

Here is Andrey Markov.

Working from back to front, an HMM is

• a model
• that forms a Markov "chain"
• where the model is hidden

The Markov "property" is that we have a chain of "states" of the model and a parallel set of observations. Any particular set of observations is linear, and for each of these there is a corresponding state. The next state to be visited depends only on the current state (or a small number of recent states). And it's hidden---we don't observe the state of the model directly.

This is very cryptic, how about a concrete example?

The weather has a long history in HMM explanations (according to Dave Swofford's slides that I learned so much from, he heard about it from from some people named Rune Lyngsø (I'm guessing: this guy) via Bjarne Knudsen (bio on this page)). To get our feet wet, let's play a game called "weather by telephone."

Imagine that you and your mother live in different places, but you are a dutiful son. You call every day and she tells you about her activities. She does one of three things:

• walk
• shop at the indoor mall next door
• play scrabble.

She hates to talk about the weather, but she tells you what she's done today, and you try to guess the weather. The observed values are the chain of walk-shop-scrabble. The HMM is the weather, which we suppose has two states: sun and rain. You have to guess the state.

The model has probabilities for emission and transition. For example, if it's sunny the probability is very high that your mom will walk, whereas if it's rainy, she's most likely to stay home and play scrabble. Also, one sunny day may be more likely to be followed by another sunny day, rather than change states. We have states with transition probabilities connecting them, and for any given current state, it emits an observation drawn from a number of possible choices governed by emission probabilities that are state-specific.

Now that you're all comfortable with this analogy, I'm going to switch things around in a later post---the weather will be observed and depend on some underlying hidden state. But in the meantime, you can go back to the first post and see whether this makes sense to you in terms of the model for a functional transcription factor binding site, and the observed sequence in a particular candidate site.

No comments: