Temporal Parallelization of Inference in Hidden Markov Models

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)

Authors

Date

2021-08-12

Department

Department of Electrical Engineering and Automation

Major/Subject

Mcode

Degree programme

Language

en

Pages

13

Series

IEEE Transactions on Signal Processing, Volume 69, pp. 4875-4887

Abstract

This paper presents algorithms for the parallelization of inference in hidden Markov models (HMMs). In particular, we propose a parallel forward-backward type of filtering and smoothing algorithm as well as a parallel Viterbi-type maximum-a-posteriori (MAP) algorithm. We define associative elements and operators to pose these inference problems as all-prefix-sums computations and parallelize them using the parallel-scan algorithm. 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 graphics processing unit (GPU).

Description

Funding Information: Manuscript received February 10, 2021; revised June 4, 2021 and July 26, 2021; accepted August 4, 2021. Date of publication August 12, 2021; date of current version September 3, 2021. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. N. Dobigeon. This work was supported by Academy of Finland. (Corresponding author: Syeda Sakira Hassan.) Syeda Sakira Hassan and Simo Särkkä are with the Department of Electrical Engineering and Automation, Aalto University, 02150 Espoo, Finland (e-mail: syeda.s.hassan@aalto.fi; simo.sarkka@aalto.fi). Publisher Copyright: © 1991-2012 IEEE.

Keywords

Parallel forward-backward algorithm, parallel max-product algorithm, parallel sum-product algorithm, parallel Viterbi algorithm

Other note

DOI

10.1109/TSP.2021.3103338

Citation

Hassan, S S, Särkkä, S & García-Fernández, Á 2021, 'Temporal Parallelization of Inference in Hidden Markov Models', IEEE Transactions on Signal Processing, vol. 69, 9512397, pp. 4875-4887. https://doi.org/10.1109/TSP.2021.3103338

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202109229331

Collections

[article-cris] Sähkötekniikan korkeakoulu / ELEC