On Maximum a Posteriori Estimation of Hidden Markov Processes

Armen Allahverdyan, Aram Galstyan
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:1-9, 2009.

Abstract

We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a finite range of sufficiently low noise levels, the solution is uniquely related to the observed sequence, while the accuracy degrades linearly with increasing the noise strength. For intermediate noise values, the accuracy is nearly noise-independent, but now there are exponentially many solutions to the estimation problem, which is reflected in non-zero ground-state entropy for the Ising model. Finally, for even larger noise intensities, the number of solutions reduces again, but the accuracy is poor. It is shown that these regimes are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-allahverdyan09a, title = {On Maximum a Posteriori Estimation of Hidden {M}arkov Processes}, author = {Allahverdyan, Armen and Galstyan, Aram}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {1--9}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/allahverdyan09a/allahverdyan09a.pdf}, url = {https://proceedings.mlr.press/r7/allahverdyan09a.html}, abstract = {We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a finite range of sufficiently low noise levels, the solution is uniquely related to the observed sequence, while the accuracy degrades linearly with increasing the noise strength. For intermediate noise values, the accuracy is nearly noise-independent, but now there are exponentially many solutions to the estimation problem, which is reflected in non-zero ground-state entropy for the Ising model. Finally, for even larger noise intensities, the number of solutions reduces again, but the accuracy is poor. It is shown that these regimes are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T On Maximum a Posteriori Estimation of Hidden Markov Processes %A Armen Allahverdyan %A Aram Galstyan %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-allahverdyan09a %I PMLR %P 1--9 %U https://proceedings.mlr.press/r7/allahverdyan09a.html %V R7 %X We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a finite range of sufficiently low noise levels, the solution is uniquely related to the observed sequence, while the accuracy degrades linearly with increasing the noise strength. For intermediate noise values, the accuracy is nearly noise-independent, but now there are exponentially many solutions to the estimation problem, which is reflected in non-zero ground-state entropy for the Ising model. Finally, for even larger noise intensities, the number of solutions reduces again, but the accuracy is poor. It is shown that these regimes are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions. %Z Reissued by PMLR on 04 October 2026.
APA
Allahverdyan, A. & Galstyan, A.. (2009). On Maximum a Posteriori Estimation of Hidden Markov Processes. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:1-9 Available from https://proceedings.mlr.press/r7/allahverdyan09a.html. Reissued by PMLR on 04 October 2026.

Related Material