Hidden Markov Model
By Jia Li , The Pennsylvania State University


Introduction
  • In a nutshell, HMM is a probabilistic observation of a Markov chain (MC).

  • Instead of seeing the state of a MC at any time, you observe a random variable obeying a distribution (continuous or discrete) determined by the state.

  • Slides for an introduction.

  • Baum-Welch Algorithm

Generalized HMMs

Applications
  • Speech recognition
  • Image segmentation, classification (categorization), annotation. Face recognition.
  • Biological sequence analysis. Profiling protein sequences, extracting DNA segments with different evolutionary rates, etc.
  • More ...

Example
  • Suppose each day at State College is categorized into either a cold day or a warm day. Model the days by a Markov chain with state space {cold, warm} (Obviously, this is a naive assumption especially at State College).
  • Li goes to lunch at either Hub or a fast food restaurant in the downtown. If it's a cold day, she goes to Hub with probability 0.7 and downtown with probability 0.3. If it's a warm day, she goes to downtown with probability 0.5. Her decision each day depends only on that day's weather condition.
  • Consider the sequence of random variables each recording where Li goes to lunch every day. There are only two possible values for these random variables: {Hub, Downtown}.
  • The sequence of lunch places is an HMM.

Quiz for fun
  • The Markov chain for State College's weather condition is as follows: (1) It is of first order and time invariant; (2) If today is cold, the probability it will be cold tomorrow is 0.8, if today is warm, the probability it will be cold tomorrow is 0.5.
  • Consider Monday to Friday. Suppose Monday is a cold day.
  • What is the probability that the lunch places of Li in this week is {Hub, Hub, Downtown, Hub, Downtown}?
  • Suppose you are told that the lunch place sequence in a week is {Hub, Hub, Downtown, Hub, Downtown} and Monday is a cold day.
    What is the probability that Wednesday is a warm day?
    Please assume you don't live in State College, or if you live there, you don't pay any attention to the weather, and you don't use the Internet to find out.
  • Again, the lunch places in a week is given, {Hub, Hub, Downtown, Hub, Downtown}.
    What is the most likely sequence of weather conditions in this week?
    What is the probability that Saturday is a warm day?

References
  • L. E. Baum and T. Petrie, "Statistical inference for probabilistic functions of finte state Markov chains," Annls of Mathematical Statistics , 37:1554-1563, 1966.
  • L. E. Baum, T. Petrie, G. Soules, and N. Weiss, "A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains," Annals of Mathematical Statistics , 41(1):164-171, 1970.
  • S. Young, J. Jansen, J. Odell, D. Ollason, and P. Woodland, HTK - Hidden Markov Model Toolkit, Cambridge University, 1995.
  • J. Li, A. Najmi, R. M. Gray, ``Image classification by a two dimensional hidden Markov model,'' IEEE Transactions on Signal Processing , 48(2):517-33, February 2000. [2-D HMM]   (download)
  • J. Li, R. M. Gray, R. A. Olshen, ``Multiresolution image classification by hierarchical modeling with two dimensional hidden Markov models,'' IEEE Transactions on Information Theory , 46(5):1826-41, August 2000. [2-D MHMM]   (download)
  • J. Li, W. Miller, ``Significance of inter-species matches when evolutionary rate varies,'' Journal of Computational Biology , 10(3-4):537-554, 2003. [HMMMO]   (download)
  • J. Li, J. Z. Wang, ``Studying digital imagery of ancient paintings by mixtures of stochastic models,'' IEEE Transactions on Image Processing, 12(3):340-353, 2004. [Mixture of 2-D MHMMs]   (download)


Learn more by Wikipedia

Please contact Jia Li if you have comments or suggestions on the page.

Updated in March 2006