Computational Molecular Biology, aka Algorithms for Computational Biology
Hidden Markov Model Module Guide
This module is intended to teach essentially everything there is to know about the most basic type of hidden Markov model (HMM). Specifically, you should be able to:
- Determine the strengths and weaknesses of an HMM as a model of a given situation.
- For a given situation, sketch the state diagram of an HMM model and describe the characteristics of reasonable parameter values.
- Implement the Viterbi algorithm for HMM decoding.
- Implement posterior decoding.
- Implement the Baum-Welch algorithm for unsupervised parameter estimation.
- Read, understand, and correct errors in correctness proofs for the above algorithms.
- Explain limitations of HMMs and associated algorithms and reference methods for enhancing them.
The source for the material in this module is largely the first few
sections
of “A
tutorial on Hidden Markov Models…” by Rabiner. HMMs are
also covered, using a different notation in Chapter 3 of Biological
Sequence Analysis, by Durbin et
al. (see Notation
guide). Relevant sections of both are worth
reading. Durbin & Eddy is a good (and inexpensive) book to have on
your shelf.
There are optional online lectures in mathematicalmonk's youtube
series on machine learning, chapter 14 (ML 14.1 through ML 14.12). He
starts with Markov models and Markov chains before getting to HMMs. He
tends to talk really slow so I listen to them at 2X playback speed.
Day 0
In class
- This is the last day of the previous module.
Before the next class
Day 1
In class
- Discussion: HMM programming project and other applications. Independence properties of HMMs.
Before the next class
- Carefully read Sections 2.2-2.3 of the course notes.
- Do exercises 2.1 and 2.2 in the HMM course notes and turn them
at the beginning of the next class.
- Optional The notes are loosely based on Sections I and II (pages
257-261) of Rabiner, which you may also want to read. Especially if
you can't get the at-home exercise.
- Optional mathematicalmonk online lectures ML 14.4 - 14.5.
Before class on Day 4
Day 2
In class
- Discussion: Mechanics of the Viterbi decoding algorithm.
- Discussion: Correctness of the Viterbi algorithm.
- In-class exercise on using HMMs to model stochastic processes
Before the next class
- Carefully read Sections 3 and 4 of the course notes.
- Do Exercises 2.3-2.5 in the HMM course notes. Turn them in at
the beginning of next class.
- Optional Read Section III.B of Rabiner (but you
might want to read Section III.A first).
- Optional mathematicalmonk online lectures ML 14.11 - 14.12.
Day 3
In class
- Collect and answer questions on previous homework
- Discussion: The Forward algorithm and Posterior Decoding
- Workshop Viterbi Programming Assignment 1
Before the next class
- Do Exercises 3.1 and 4.1 in the HMM course notes. Turn them in at the next class.
- Carefully read Sections 5 and 6 of the course notes.
- Complete and turn in the Viterbi programming assignment.
- Optional mathematicalmonk online lectures ML 14.6 - 14.9.
Day 4
In class
- DUE TODAY: Viterbi programming assignment
- Collect and answer questions on previous homework
- Discussion: HMM parameter estimation from labeled and unlabeled data.
Before the next class
- Do all parts of Exercise 4.2 in the HMM course notes. Turn them
in at the next class. Do this before you start implementing the
posterior decoding algorithm as it will help you with the posterior
decoding.
Before class on Day 6
Day 5
In class
- Collect and answer questions on the homework
- Workshop posterior decoding assignment
Before the next class
- Complete and turn in the posterior decoding assignment.
- Optional mathematicalmonk online lectures ML 14.10
Day 6
In class
- Discuss TBA article illustrating application of HMMs.
Before the next class
- Complete and turn in Exercise 6.1 from the HMM course notes.
- See Day 0 of the next module for additional required preparation