Document Open Access Logo

On the Metric-Based Approximate Minimization of Markov Chains

Authors Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, Radu Mardare

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.104.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Giovanni Bacci
Giorgio Bacci
Kim G. Larsen
Radu Mardare

Cite As Get BibTex

Giovanni Bacci, Giorgio Bacci, Kim G. Larsen, and Radu Mardare. On the Metric-Based Approximate Minimization of Markov Chains. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 104:1-104:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.104

Abstract

We address the behavioral metric-based approximate minimization problem of Markov Chains (MCs), i.e., given a finite MC and a positive integer k, we are interested in finding a k-state MC of minimal distance to the original. By considering as metric the bisimilarity distance of Desharnais at al., we show that optimal approximations always exist; show that the problem can be solved as a bilinear program; and prove that its threshold problem is in PSPACE and NP-hard. Finally, we present an approach inspired by expectation maximization techniques that provides suboptimal solutions. Experiments suggest that our method gives a practical approach that outperforms the bilinear program implementation run on state-of-the-art bilinear solvers.

Subject Classification

Keywords
  • Behavioral distances
  • Probabilistic Models
  • Automata Minimization

Metrics

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

References

  1. Eric Allender, Peter Burgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis. SIAM Journal on Computing, 38(5):1987-2006, 2009. URL: http://dx.doi.org/10.1137/070697926.
  2. Rajeev Alur, Costas Courcoubetis, Nicolas Halbwachs, David L. Dill, and Howard Wong-Toi. Minimization of timed transition systems. In CONCUR, volume 630 of Lecture Notes in Computer Science, pages 340-354. Springer, 1992. URL: http://dx.doi.org/10.1007/BFb0084802.
  3. Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, and Radu Mardare. Converging from Branching to Linear Metrics on Markov Chains. In ICTAC, volume 9399 of LNCS, pages 349-367. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25150-9_21.
  4. Christel Baier. Polynomial time algorithms for testing probabilistic bisimulation and simulation. In CAV, volume 1102 of Lecture Notes in Computer Science, pages 50-61. Springer, 1996. URL: http://dx.doi.org/10.1007/3-540-61474-5_57.
  5. Christel Baier and Joost-Pieter Katoen. Principles of Model Checking. MIT Press, 2008. Google Scholar
  6. Borja Balle, Prakash Panangaden, and Doina Precup. A canonical form for weighted automata and applications to approximate minimization. In LICS, pages 701-712. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.70.
  7. Michael Benedikt, Rastislav Lenhardt, and James Worrell. LTL Model Checking of Interval Markov Chains. In TACAS, volume 7795 of Lecture Notes in Computer Science, pages 32-46. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-36742-7_3.
  8. Stefan Blom and Simona Orzan. A distributed algorithm for strong bisimulation reduction of state spaces. International Journal on Software Tools for Technology Transfer, 7(1):74-86, 2005. URL: http://dx.doi.org/10.1007/s10009-004-0159-4.
  9. John F. Canny. Some Algebraic and Geometric Computations in PSPACE. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC'88), pages 460-467. ACM, 1988. URL: http://dx.doi.org/10.1145/62212.62257.
  10. Di Chen, Franck van Breugel, and James Worrell. On the Complexity of Computing Probabilistic Bisimilarity. In FoSSaCS, volume 7213 of LNCS, pages 437-451. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-28729-9_29.
  11. Taolue Chen and Stefan Kiefer. On the Total Variation Distance of Labelled Markov Chains. In CSL-LICS`14, pages 33:1-33:10. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603099.
  12. Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for Labeled Markov Systems. In CONCUR, volume 1664 of LNCS, pages 258-273. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-48320-9_19.
  13. Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labelled Markov processes. Theoretical Compututer Science, 318(3):323-354, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2003.09.013.
  14. Kousha Etessami and Mihalis Yannakakis. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM, 56(1):1:1-1:66, 2009. URL: http://dx.doi.org/10.1145/1462153.1462154.
  15. Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov Decision Processes. In UAI, pages 162-169. AUAI Press, 2004. Google Scholar
  16. Giuliana Franceschinis and Richard R. Muntz. Bounds for quasi-lumpable markov chains. Perform. Eval., 20(1-3):223-243, 1994. URL: http://dx.doi.org/10.1016/0166-5316(94)90015-9.
  17. John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189-196. Academic Press, 1971. URL: http://dx.doi.org/10.1016/B978-0-12-417750-5.50022-1.
  18. Chi-Chang Jou and Scott A.Smolka. Equivalences, congruences, and complete axiomatizations for probabilistic processes. In CONCUR'90 Theories of Concurrency: Unification and Extension, volume 458 of LNCS, pages 367-383, 1990. URL: http://dx.doi.org/10.1007/BFb0039071.
  19. Paris C. Kanellakis and Scott A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. In Proceedings of the 2nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 228-240. ACM, 1983. URL: http://dx.doi.org/10.1145/800221.806724.
  20. Paris C. Kanellakis and Scott A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. Information and Computation, 86(1):43-68, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90025-D.
  21. Michal Ko1cmcvara and Michael Stingl. PENBMI 2.0. http://www.penopt.com/penbmi.html. Accessed: 2016-08-28.
  22. Michal Ko1cmcvara and Michael Stingl. PENNON: A code for convex nonlinear and semidefinite programming. Optimization Methods and Software, 18(3):317-333, 2003. URL: http://dx.doi.org/10.1080/1055678031000098773.
  23. Kim Guldstrand Larsen and Arne Skou. Bisimulation through probabilistic testing. Information and Computation, 94(1):1-28, 1991. Google Scholar
  24. David Lee and Mihalis Yannakakis. Online minimization of transition systems (extended abstract). In Annual ACM Symposium on Theory of Computing, pages 264-274. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129738.
  25. Geoffrey J. McLachlan and Thriyambakam Krishnan. The EM Algorithm and Extensions. Wiley-Interscience, 2 edition, 2008. Google Scholar
  26. Robin Milner. A Calculus of Communicating Systems, volume 92 of Lecture Notes in Computer Science. Springer, 1980. URL: http://dx.doi.org/10.1007/3-540-10235-3.
  27. Edward F. Moore. Gedanken Experiments on Sequential Machines. In Automata Studies, pages 129-153. Princeton University, 1956. Google Scholar
  28. Franck van Breugel and James Worrell. Towards Quantitative Verification of Probabilistic Transition Systems. In ICALP, volume 2076 of LNCS, pages 421-432, 2001. Google Scholar
  29. Franck van Breugel and James Worrell. Approximating and computing behavioural distances in probabilistic transition systems. Theoretical Computer Science, 360(3):373-385, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.05.021.
  30. Mihali Yannakakis and David Lee. An efficient algorithm for minimizing real-time transition systems. Formal Methods in System Design, 11(2):113-136, 1997. URL: http://dx.doi.org/10.1023/A:1008621829508.
  31. Shipei Zhang and Scott A. Smolka. Towards efficient parallelization of equivalence checking algorithms. In FORTE, volume C-10 of IFIP Transactions, pages 121-135. North-Holland, 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