Hidden Markov Models in GPGPU (HMM CUDA)

HMM Diagram

December 5, 2011

I finally finished my graduate studies at Virginia Tech. The good news: I got my degree! The bad news: my 1.5 years of research is probably sitting on the VT servers gathering virtual dust. In hopes that it might help someone, I’ve published my thesis on the Internet for anyone interested in programming Hidden Markov Model (HMM) algorithms with CUDA:

http://scholar.lib.vt.edu/theses/available/etd-12082011-204951/

Hidden Markov Models have been used for some time in pattern recognition, such as handwriting and speech analysis, but they have seen limited use in cognitive radio for things like spectrum sensing and signal analysis.

CPUs, especially small ones found in mobile devices like cell phones, cannot keep up with the demand for most HMM algorithms. Graphic processing units (GPUs), on the other hand, offer the ability to perform Single Instruction, Multiple Data (SIMD) operations on large scale data. GPGPU seemed like a natural fit for HMMs.

I created C and CUDA implementations for three of the main HMM algorithms: the Forward Algorithm, the Viterbi Algorithm, and the Baum-Welch Algorithm. From my experiments, graphics cards can surpass CPUs in execution time only when many states or many models are used simultaneously. The Forward and Baum-Welch algorithms (with a large number of states) saw a huge increase in execution speed when moved to a GPU. The Viterbi, however, only saw a marginal increase in speed.

If you’re interested in my HMM CUDA implementation, check out my project on Google Code:

https://code.google.com/p/hmm-cuda/

7 Responses

  1. Hi Shawn,
    I would like some help in the area of installing the cuda kit et al in the ubuntu 12.04 platform. We tried out with the 5.5 version, its a no go till now. The system is fitted with a quadro 600 nvidia device.
    Using synaptics manager we installed the drivers. We tried out the bumblebee stable release, but the display resolutions was all messed up showing a poor resolution etc.
    I would like to use and IDE for parallel programming development.

    Would you be able to help. Is it possible to atleast send me the installation instructions that you followed while installing CUDA in Ubuntu.

    Thanks

  2. Shawn,

    I am currently researching the possibility of using HMM for a stock portfolio risk minimization project in Hadoop and was wondering if you would see any potential issues with your approaches to solve this problem. If not, would you have a recommendation as to which one of the algorithms you implemented would be more appropriate for this type of architecture? Thanks in advance for your help.

    1. Hi Juan,

      Sounds like a cool project. I am assuming that you want to do some pattern recognition on the stock market looking for trends. HMMs would be a good fit for something like that (please keep in mind that HMMs are just one way to analyze trends – there are lots of pattern recognition tools out there). So, if you want to use HMMs, you will need to construct and train a mathematical model using the Baum-Welch Algorithm. This model will be the pattern that you are looking for (e.g. a sudden downward trend in the market). You then need to use the Forward Algorithm to compare the model to past and current trends in the market. This comparison will output a number that states the probability that the analyzed trend will produce the mathematical model (i.e. it is a measure of how closely the analyzed trend matches the model). You can set a threshold so that if the Forward Algorithm’s output matches or exceeds that threshold, you can say that a pattern has been matched (you have determined that a risky trend in the stock market has occurred).

      I hope that all makes sense! It was a long-winded crash course in pattern recognition. Good luck with the project!

      [Edit] If you have access to MATLAB, I highly recommend the HMM Toolbox: http://www.cs.ubc.ca/~murphyk/Software/HMM/hmm.html

      1. Thanks a lot for your help, Shawn! I do have Matlab but part of the requirements is to use Hadoop and I have to build my own code so ML-ready frameworks are not an option 🙁

        I will check out the resources you provided and let you know how it works out.

Leave a Reply