Abstract
This paper presents an algorithm to parallelise the Viterbi algorithm along the temporal dimension to compute the maximum a posteriori (MAP) trajectory estimate of a hidden Markov model. We reformulate the MAP estimation problem as an optimal control problem. The proposed algorithm uses a parallelisation algorithm developed for optimal control problems that first performs a backward value function pass and then a forward trajectory recovery pass. The parallel Viterbi algorithm then corresponds to a specialised backward optimal control problem with a forward value function pass and backward MAP-trajectory recovery pass. The algorithm is empirically tested by running numerical simulations on a multi-core central processing unit (CPU) and a graphics processing unit (GPU).
| Original language | English |
|---|---|
| Title of host publication | 31st European Signal Processing Conference, EUSIPCO 2023 - Proceedings |
| Publisher | European Association For Signal and Image Processing |
| Pages | 2018-2022 |
| Number of pages | 5 |
| ISBN (Electronic) | 978-94-645936-0-0 |
| DOIs | |
| Publication status | Published - 1 Nov 2023 |
| MoE publication type | A4 Conference publication |
| Event | European Signal Processing Conference - Helsinki, Finland Duration: 4 Sept 2023 → 8 Sept 2023 Conference number: 31 https://eusipco2023.org/ |
Publication series
| Name | European Signal Processing Conference |
|---|---|
| ISSN (Print) | 2219-5491 |
Conference
| Conference | European Signal Processing Conference |
|---|---|
| Abbreviated title | EUSIPCO |
| Country/Territory | Finland |
| City | Helsinki |
| Period | 04/09/2023 → 08/09/2023 |
| Internet address |
Keywords
- hidden Markov model
- maximum a posteriori estimation
- temporal parallelisation
- Viterbi algorithm