Temporal Parallelization of Inference in Hidden Markov Models
This work addresses a computational bottleneck for researchers and practitioners using HMMs in applications like signal processing or bioinformatics, but it is incremental as it builds on existing parallel-scan techniques.
The paper tackles the computational inefficiency of inference in hidden Markov models (HMMs) over long time horizons by proposing parallel algorithms for filtering, smoothing, and MAP estimation, achieving improved performance on a GPU compared to classical methods.
This paper presents algorithms for parallelization of inference in hidden Markov models (HMMs). In particular, we propose parallel backward-forward type of filtering and smoothing algorithm as well as parallel Viterbi-type maximum-a-posteriori (MAP) algorithm. We define associative elements and operators to pose these inference problems as parallel-prefix-sum computations in sum-product and max-product algorithms and parallelize them using parallel-scan algorithms. The advantage of the proposed algorithms is that they are computationally efficient in HMM inference problems with long time horizons. We empirically compare the performance of the proposed methods to classical methods on a highly parallel graphical processing unit (GPU).