Parallel Learning of Sequential Graphical Models

Overview

The number of cores in a single chip keeps on increasing recent years, yet there is no good framework for machine learning to take advantage of multi-core computation. How much speedup could we obtain for a more general class of learning algorithms, especially for machine learning algorithms on graphical models?

In this project, we plan to investigate how much parallelism we could exploit in machine learning algorithms on graphical models with multi-core processors. We will focus on the inference algorithms for both Bayesian Network and Markov Random Fields. We will also investigate the learning algorithms in graphical models, such as Expectation-Maximization algorithm and Markov Chain Monte Carlo algorithms.

The goal is to design and implement efficient parallel learning algorithm for sequential graphical models, such as hidden Markov models (HMM) and linear dynamical systems (LDS). LDS (or Kalman filters) is very useful in motion capture, visual tracking, speech recognition, quantitative studies of financial markets, network intrusion detection, forecasting, etc.

This project is originated from a course project of 15740 Computer Architecture. If you are interested, you can find the project page here (sorry, ONLY visible within CMU).

FUNDING ACKNOWLEDGEMENTS:
This material is based upon work supported by the National Science Foundation under Grants No. IIS-0326322. The data used in this project was obtained from mocap.cs.cmu.edu supported by NSF EIA-0196217. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, or other funding parties.

People

Christos Faloutsos - professor from CSD
Todd C. Mowry - professor from CSD
Lei Li - PhD student from CSD
Wenjie Fu - PhD student from CSD
Fan Guo - PhD student from CSD
Bin Fu - PhD student from CSD

Publication

1. Lei Li, Wenjie Fu, Fan Guo, Todd C. Mowry, and Christos Faloutsos. Cut-And-Stitch: Efficient Parallel Learning of Linear Dynamical Systems on SMPs. ACM KDD ?8, Las Vegas, Nevada, USA, 2008. [pdf] [BiBTeX]

* Errata: There was a typo in Equation 37, page 4 in the original kdd version. The software source code is correct.

2.Lei Li, Bin Fu, Christos Faloutsos. Efficient Parallel Learning of Hidden Markov Chain Models on SMPs, IEICE Transactions on Information and Systems. Volume E93.D(6), pp. 1330-1342.

Download

Dataset (please gently acknowledge us in your resulting work)

o processed motion capture dataset [Download]

Presentation: [PPT] [Poster]
Software: c++ source code [Download] (running on fedora 7, or gcc 4.2.0 above)

Contact

Suggestions or any comments are welcome. Please email Lei Li at CLICK HERE@cs.cmu.edu (Spam blocking provided by the reCAPTCHA Project).