Markov Models

Models

A model is an abstract representation of reality.

Consider model airplanes. Some model airplanes look very much like a small version of a real airplane, but do not fly well at all. Other model airplanes (e.g., a paper airplane) do not look very much like airplanes at all, but fly very well. These two kinds of models represent different features of the airplane; the first represents its outward appearance, while the second represents its aerodynamic properties (in part). Thus what type of model is appropriate to use depends upon the intended purpose.

Mathematical models represent a system, and are used to make predictions about that system.

Parameters

Every model consists of a structure, along with parameters that must be defined for the model to be meaningful. The structure of the model defines dependencies among the various parts of the model. Parameters are values -- often, but not necessarily numerical values -- that are required by the model. Parameters may be fixed, in which case the constitute assumptions of the model, or they may be variable. If they are variable,

Markov Process

A Markov process is a process that is capable of being in more than one state, can make transitions among those states, and in which the states available and transition probabilities depend only upon what state the system is currently in. In other words, there is no memory in a Markov process.

Markov Chain

A Markov Chain is a statistical model of a system that moves sequentially from one state to another

The probabilities of transition from one state to another are dependent only on the current state (not on previous states)

Generally modeled as a stochastic process

A Markov chain can be described by a transition matrix

Hidden Markov Models (HMMs)

A hidden Markov model models a Markov process, but assumes that there is uncertainty in what state the system is in at any given time.

A common metaphor is to think of the HMM as if the Markov Model were a mechanism hidden behind a curtain. The observer doesn't have any knowledge of how the mechanim is operating, and only knows what is going on behind the curtain from periodic reports that are emitted by the mechanism.

Emission probabilities

Three basic problems for HMMs [per Jack Ferguson (IDA), ex Rabiner (1989)]

There are three fundamental types of problems to which HMMs can be applied:

Problem type 1 (event evaluation): given a model and a sequence of events, estimate the probability that the HMM would give rise to the observed events.

Problem type 2 (path optimization): given a series of events and a model, find the "optimal" set of model states (i.e., the optimal path through that model). This often means finding the set of model states that best correspond to the observed series.

Problem type 3 (parameter extimation): given a model and empirical observations, find the model parameters that best fit the observations.

Probability vs. likelihood

The term probability is used to refer to the relative odds of an event occurring in a case where all possible outcomes can be accounted for. By contrast, the term likelihood is used to refer to the odds of an event occuring when it is not possible (or not practical) to account for all possible outcomes. Thus the sum of the probabilities of all possible outcomes will always be 1, while likelihood is often interpreted in a relative sense, i.e., one event may be considered to be more likely than another even when there is a third possible outcome of unknown likelihood.

HMMs and hypothesis testing

HMMs can be used to test hypotheses. To perform hypothesis testing it is essential to be able to relate the data (the empirical observations) to the hypothesis to be tested:

The model is accepted as a set of a priori assumption. These assumption make it possible to calculate a numeric value for the hypothesis given the data. Thus the relative likelihood of two different hypotheses can be calculated given the same model and data.

A single hypothesis and model could correspond to many different specific datasets. For example, molecular phylogenies for two different genes might have identical tree topologies (hypotheses) and models (model of sequence evolution and parameters), but completely different gene sequences (data). For this reason it is frequently convenient to approach this as a problem of type 1 (above), and calculate the likelihood that a given DNA sequence (the data) would be observed given the hypothesis being tested (a tree topology) and a model (of sequence evolution). This is often written L(hypothesis) = L (data|model)

What makes this a powerful way of thinking about things is that it is possible to move components among these different elements. One can move part of the model into the hypothesis and test it, and if new data become available, then elements of the hypothesis or the model can be moved into the data, etc. Thus one can estimate parameters of sequence evolution if one accepts a phylogenetic tree as an a priori assumption, etc.

HMMs provide a very flexible context in which a variety of biological processes and datatypes may be modeled.

Examples

Rabiner, L. R. 1989. A Tutorial on Hidden Markov-Models and Selected Applications in Speech Recognition. Proceedings of the Ieee 77: 257-286.

Edwards, A. W. F. 1992. Likelihood, Expanded Edition. Johns Hopkins Press, Baltimore, MD.