4.7 Article

Exploiting locality in high-dimensional Factorial hidden Markov models

Journal

JOURNAL OF MACHINE LEARNING RESEARCH
Volume 23, Issue -, Pages -

Publisher

MICROTOME PUBL

Keywords

Factorial hidden Markov models; filtering; smoothing; EM algorithm; high-dimensions

Funding

  1. Alan Turing Institute

Ask authors/readers for more resources

This paper proposes algorithms for approximate filtering and smoothing in high-dimensional Factorial hidden Markov models. The approximation involves discarding likelihood factors based on a notion of locality in a factor graph associated with the emission distribution, thus avoiding the high computational cost of exact filtering and smoothing. The paper proves that the approximation accuracy is dimension-free, meaning that it does not degrade as the overall dimension of the model increases. The paper also analyzes the error introduced by localizing the likelihood function in a Bayes' rule update, and demonstrates the application of the new algorithms on synthetic examples and a London Underground passenger flow problem.
We propose algorithms for approximate filtering and smoothing in high-dimensional Factorial hidden Markov models. The approximation involves discarding, in a principled way, likelihood factors according to a notion of locality in a factor graph associated with the emission distribution. This allows the exponential-in-dimension cost of exact filtering and smoothing to be avoided. We prove that the approximation accuracy, measured in a local total variation norm, is dimension-free in the sense that as the overall dimension of the model increases the error bounds we derive do not necessarily degrade. A key step in the analysis is to quantify the error introduced by localizing the likelihood function in a Bayes' rule update. The factorial structure of the likelihood function which we exploit arises naturally when data have known spatial or network structure. We demonstrate the new algorithms on synthetic examples and a London Underground passenger flow problem, where the factor graph is effectively given by the train network.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available