A temporally abstracted Viterbi algorithm

Shaunak Chatterjee, Stuart Russell
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:124-132, 2011.

Abstract

Hierarchical problem abstraction, when applicable, may offer exponential reductions in computational complexity. Previous work on coarse-to-fine dynamic programming (CFDP) has demonstrated this possibility using state abstraction to speed up the Viterbi algorithm. In this paper, we show how to apply temporal abstraction to the Viterbi problem. Our algorithm uses bounds derived from analysis of coarse timescales to prune large parts of the state trellis at finer timescales. We demonstrate improvements of several orders of magnitude over the standard Viterbi algorithm, as well as significant speedups over CFDP, for problems whose state variables evolve at widely differing rates.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-chatterjee11a, title = {A temporally abstracted {V}iterbi algorithm}, author = {Chatterjee, Shaunak and Russell, Stuart}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {124--132}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/chatterjee11a/chatterjee11a.pdf}, url = {https://proceedings.mlr.press/r9/chatterjee11a.html}, abstract = {Hierarchical problem abstraction, when applicable, may offer exponential reductions in computational complexity. Previous work on coarse-to-fine dynamic programming (CFDP) has demonstrated this possibility using state abstraction to speed up the Viterbi algorithm. In this paper, we show how to apply temporal abstraction to the Viterbi problem. Our algorithm uses bounds derived from analysis of coarse timescales to prune large parts of the state trellis at finer timescales. We demonstrate improvements of several orders of magnitude over the standard Viterbi algorithm, as well as significant speedups over CFDP, for problems whose state variables evolve at widely differing rates.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A temporally abstracted Viterbi algorithm %A Shaunak Chatterjee %A Stuart Russell %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-chatterjee11a %I PMLR %P 124--132 %U https://proceedings.mlr.press/r9/chatterjee11a.html %V R9 %X Hierarchical problem abstraction, when applicable, may offer exponential reductions in computational complexity. Previous work on coarse-to-fine dynamic programming (CFDP) has demonstrated this possibility using state abstraction to speed up the Viterbi algorithm. In this paper, we show how to apply temporal abstraction to the Viterbi problem. Our algorithm uses bounds derived from analysis of coarse timescales to prune large parts of the state trellis at finer timescales. We demonstrate improvements of several orders of magnitude over the standard Viterbi algorithm, as well as significant speedups over CFDP, for problems whose state variables evolve at widely differing rates. %Z Reissued by PMLR on 04 October 2026.
APA
Chatterjee, S. & Russell, S.. (2011). A temporally abstracted Viterbi algorithm. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:124-132 Available from https://proceedings.mlr.press/r9/chatterjee11a.html. Reissued by PMLR on 04 October 2026.

Related Material