MA490 Pattern Recognition

… using Hidden Markov Modeling

Update (2017): HMMs are currently being displaced by Deep Learning in many applications.

What is an HMM?

Hidden Markov Models (HMMs) are probability-based, pattern recognition algorithms.

Why do HMMs work well in practice?

HMMs have a simple, but rich structure which enables them to be designed to take advantages of a particular application’s special properties. HMM algorithms can be shown to be optimal, i.e. best in class. (Compared to Deep Learning (RNN’s), HMM’s have a more limited capacity to learn and do not  scale as well to large data sets.)

Example (Dishonest Casino)

The figure below is a diagram of a simple HMM modelling a dishonest casino dealer. The dealer switches secretly between fair and unfair dice. The fair and unfair die rolls are hidden states.

The only observable quantities are the die rolls and . For example, consider the die rolls:

4, 3, 5, 7, 8, 9, 6, 6, 6, 6, 3, 4, 5, 6, 6, 2, 5, 3, 4, 6, 1, 2, 1

Using only the above sequence of die rolls, an HMM attempts to determine which rolls were done using a fair dice and which were done using an unfair dice.

What do I need to know to take this course?

Either MA223 Statistics or MA381 Probability provides sufficient background. All the other concepts needed will be developed in the course.

How will my grade be computed?

The goal of the course is to foster creativity and innovation. There will be no tests. Short quizzes/lessons will test comprehension of elementary concepts. A significant portion of the course will involve working on individual or group projects chosen by students.

• 30% Homework
• 30% Quizzes/Lessons
• 30% Project
• 10% Class Participation

Past Student Projects

Biology

• Stochastic Context-Free Grammars and tRNA Folding,
  by Michael Ewing, Mike Simon and Phil Smith.
• Using HMMs to Predict Secondary Structure in Proteins
  by Charles McAnany

Robotics

• Mobile Robot Localization using Kalman Filters,
  by Jon Klein and Trenton Tabor.
• Textured Image Segmentation Using Wavelet-Domain Hidden Markov Trees, by Jay Groven and Alex Van Brunt.
• Matching Pixels in Rectified Stereo Images Using Hidden Markov Models, by Adam Thomas and Matthew Stachawski.

Chemical Engineering

• Determination of Process States with Hidden Markov Models,
  by Joe Kelly.

Economics

• Structural Macroeconomics Analysis of the Business Cycle Using Hidden Markov Models with Continuous Emitted Symbols, by Nicholas McKinney.
• Exploring the Connections Between Economic Indicators,
  by Aaron Knox.
• Class Distinctions of a Simplified Economic Model,
  by David McGinnis, David Loughry and Greg Jackson.

Data Mining

• Paragraph Keyword Acquisition,
  by Bryan Shell.
• Chronological Typewriting Analysis,
  by Troy Reilly.
• Sentence Structure Validator
  by Devin Banks.
• Using N-Gram Similarity Metrics for Relation Clustering
  by Stephen Mayhew and Nicholas Kamper.

Music

• Smart DJ,
  by Peter Witon.
• Classification of Music by Genre
  by Matthew Oelschlaegar, Mathew Mercer, Arada Tugay and Zachary Stewart.
• Genre Classification by Chord Progression
  by Michael Eaton and Samuel Kim

Astronomy

• Exoplanet Detection via HMM Analysis
  by Jon Drobny. (Weaver Grant Award)

Image Processing

• Food Image Processing, An Approach using Markov Modeling
  by Rob Wagner and Alex Petitjean.
• Where’s Waldo (Facial Recognition)
  Chris Gropp and Nicole Richardson.

Security

• The Application of HMMs in Security
  by Nathan Catt and Alex Jacoby
• Acoustic Crytanalysis of Keyboard Emissions through HMMs
  by Ross Hansen and Elias White.
• Detecting Collusion in Multiplayer Games
  by Dong Lee and Alec Manke.