Compressed Inference for Probabilistic Sequential Models

Gungor Polatkan, Oncel Tuzel
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:675-684, 2011.

Abstract

Hidden Markov models (HMMs) and conditional random fields (CRFs) are two popular techniques for modeling sequential data. Inference algorithms designed over CRFs and HMMs allow estimation of the state sequence given the observations. In several applications, estimation of the state sequence is not the end goal; instead the goal is to compute some function of it. In such scenarios, estimating the state sequence by conventional inference techniques, followed by computing the functional mapping from the estimate is not necessarily optimal. A more formal approach is to directly infer the final outcome from the observations. In particular, we consider the specific instantiation of the problem where the goal is to find the state trajectories without exact transition points and derive a novel polynomial time inference algorithm that outperforms vanilla inference techniques. We show that this particular problem arises commonly in many disparate applications and present experiments on three of them: (1) Toy robot tracking; (2) Single stroke character recognition; (3) Handwritten word recognition.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-polatkan11a, title = {Compressed Inference for Probabilistic Sequential Models}, author = {Polatkan, Gungor and Tuzel, Oncel}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {675--684}, 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/polatkan11a/polatkan11a.pdf}, url = {https://proceedings.mlr.press/r9/polatkan11a.html}, abstract = {Hidden Markov models (HMMs) and conditional random fields (CRFs) are two popular techniques for modeling sequential data. Inference algorithms designed over CRFs and HMMs allow estimation of the state sequence given the observations. In several applications, estimation of the state sequence is not the end goal; instead the goal is to compute some function of it. In such scenarios, estimating the state sequence by conventional inference techniques, followed by computing the functional mapping from the estimate is not necessarily optimal. A more formal approach is to directly infer the final outcome from the observations. In particular, we consider the specific instantiation of the problem where the goal is to find the state trajectories without exact transition points and derive a novel polynomial time inference algorithm that outperforms vanilla inference techniques. We show that this particular problem arises commonly in many disparate applications and present experiments on three of them: (1) Toy robot tracking; (2) Single stroke character recognition; (3) Handwritten word recognition.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Compressed Inference for Probabilistic Sequential Models %A Gungor Polatkan %A Oncel Tuzel %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-polatkan11a %I PMLR %P 675--684 %U https://proceedings.mlr.press/r9/polatkan11a.html %V R9 %X Hidden Markov models (HMMs) and conditional random fields (CRFs) are two popular techniques for modeling sequential data. Inference algorithms designed over CRFs and HMMs allow estimation of the state sequence given the observations. In several applications, estimation of the state sequence is not the end goal; instead the goal is to compute some function of it. In such scenarios, estimating the state sequence by conventional inference techniques, followed by computing the functional mapping from the estimate is not necessarily optimal. A more formal approach is to directly infer the final outcome from the observations. In particular, we consider the specific instantiation of the problem where the goal is to find the state trajectories without exact transition points and derive a novel polynomial time inference algorithm that outperforms vanilla inference techniques. We show that this particular problem arises commonly in many disparate applications and present experiments on three of them: (1) Toy robot tracking; (2) Single stroke character recognition; (3) Handwritten word recognition. %Z Reissued by PMLR on 04 October 2026.
APA
Polatkan, G. & Tuzel, O.. (2011). Compressed Inference for Probabilistic Sequential Models. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:675-684 Available from https://proceedings.mlr.press/r9/polatkan11a.html. Reissued by PMLR on 04 October 2026.

Related Material