Document Open Access Logo

Equivalence of Hidden Markov Models with Continuous Observations

Authors Oscar Darwin , Stefan Kiefer

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.43.pdf
  • Filesize: 457 kB
  • 14 pages

Document Identifiers

Author Details

Oscar Darwin
  • Department of Computer Science, Oxford University, UK
Stefan Kiefer
  • Department of Computer Science, Oxford University, UK

Funding

  • Darwin, Oscar: Darwin is supported by a Royal Society Enhancement Award.
  • Kiefer, Stefan: Kiefer is supported by a Royal Society University Research Fellowship.

Acknowledgements

he authors would like to thank anonymous reviewers for their helpful comments and Nikhil Balaji for useful discussions on polynomial identity testing.

Cite As Get BibTex

Oscar Darwin and Stefan Kiefer. Equivalence of Hidden Markov Models with Continuous Observations. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.43

Abstract

We consider Hidden Markov Models that emit sequences of observations that are drawn from continuous distributions. For example, such a model may emit a sequence of numbers, each of which is drawn from a uniform distribution, but the support of the uniform distribution depends on the state of the Hidden Markov Model. Such models generalise the more common version where each observation is drawn from a finite alphabet. We prove that one can determine in polynomial time whether two Hidden Markov Models with continuous observations are equivalent.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Stochastic processes
  • Theory of computation → Logic and verification
Keywords
  • Markov chains
  • equivalence
  • probabilistic systems
  • verification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P. Ailliot, C. Thompson, and P. Thomson. Space-time modelling of precipitation by using a hidden Markov model and censored Gaussian distributions. Journal of the Royal Statistical Society, 58(3):405-426, 2009. Google Scholar
  2. M. Alexandersson, S. Cawley, and L. Pachter. SLAM: Cross-species gene finding and alignment with a generalized pair hidden Markov model. Genome Research, 13:469-502, 2003. Google Scholar
  3. M.S. Alvim, M.E. Andrés, C. Palamidessi, and P. van Rossum. Safe equivalences for security properties. In Theoretical Computer Science, pages 55-70. Springer, 2010. Google Scholar
  4. C. Baier, B. Haverkort, H. Hermanns, and J.-P. Katoen. Model-checking algorithms for continuous-time Markov chains. IEEE Transactions on Software Engineering, 29(6):524-541, 2003. Google Scholar
  5. M.S. Bauer, R. Chadha, and M. Viswanathan. Modular verification of protocol equivalence in the presence of randomness. In Computer Security - ESORICS 2017, pages 187-205. Springer, 2017. Google Scholar
  6. B.A. Braun, S. Jana, and D. Boneh. Robust and efficient elimination of cache and timing side channels, 2015. URL: http://arxiv.org/abs/1506.00189.
  7. F.-S. Chen, C.-M. Fu, and C.-L. Huang. Hand gesture recognition using a real-time tracking method and hidden Markov models. Image and Vision Computing, 21(8):745-758, 2003. Google Scholar
  8. T. Chen, M. Diciolla, M.Z. Kwiatkowska, and A. Mereacre. Time-bounded verification of CTMCs against real-time specifications. In Proceedings of Formal Modeling and Analysis of Timed Systems (FORMATS), volume 6919 of LNCS, pages 26-42. Springer, 2011. Google Scholar
  9. G.A. Churchill. Stochastic models for heterogeneous DNA sequences. Bulletin of Mathematical Biology, 51(1):79-94, 1989. Google Scholar
  10. C. Cortes, M. Mohri, and A. Rastogi. L_p distance and equivalence of probabilistic automata. International Journal of Foundations of Computer Science, 18(04):761-779, 2007. Google Scholar
  11. M.S. Crouse, R.D. Nowak, and R.G. Baraniuk. Wavelet-based statistical signal processing using hidden Markov models. IEEE Transactions on Signal Processing, 46(4):886-902, April 1998. Google Scholar
  12. Oscar Darwin and Stefan Kiefer. Equivalence of hidden markov models with continuous observations. Technical report, arXiv.org, 2020. Available at http://arxiv.org/abs/2009.12978. Google Scholar
  13. C. Dehnert, S. Junges, J.-P. Katoen, and M. Volk. A Storm is coming: A modern probabilistic model checker. In Proceedings of Computer Aided Verification (CAV), pages 592-600. Springer, 2017. Google Scholar
  14. R. Durbin. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998. Google Scholar
  15. S.R. Eddy. What is a hidden Markov model? Nature Biotechnology, 22(10):1315-1316, October 2004. Google Scholar
  16. W.K. Grassmann. Finding transient solutions in Markovian event systems through randomization. In Numerical solution of Markov chains, pages 357-371, 1991. Google Scholar
  17. H. Hermanns, J. Krčál, and J. Křetínský. Probabilistic bisimulation: Naturally on distributions. In CONCUR 2014 - Concurrency Theory, pages 249-265. Springer, 2014. Google Scholar
  18. S. Kiefer, A.S. Murawski, J. Ouaknine, B. Wachter, and J. Worrell. Language equivalence for probabilistic automata. In Proceedings of the 23rd International Conference on Computer Aided Verification (CAV), volume 6806 of LNCS, pages 526-540. Springer, 2011. Google Scholar
  19. A. Krogh, B. Larsson, G. von Heijne, and E.L.L. Sonnhammer. Predicting transmembrane protein topology with a hidden Markov model: Application to complete genomes. Journal of Molecular Biology, 305(3):567-580, 2001. Google Scholar
  20. M. Kwiatkowska, G. Norman, and D. Parker. PRISM 4.0: Verification of probabilistic real-time systems. In Proceedings of Computer Aided Verification (CAV), volume 6806 of LNCS, pages 585-591. Springer, 2011. Google Scholar
  21. A. Paz. Introduction to Probabilistic Automata (Computer Science and Applied Mathematics). Academic Press, Inc., Orlando, FL, USA, 1971. Google Scholar
  22. L.R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-286, 1989. Google Scholar
  23. M.P. Schützenberger. On the definition of a family of automata. Information and Control, 4(2):245-270, 1961. Google Scholar
  24. W.-G. Tzeng. A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput., 21(2):216-227, April 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact