Document Open Access Logo

Uncertainty Reasoning for Probabilistic Petri Nets via Bayesian Networks

Authors Rebecca Bernemann, Benjamin Cabrera, Reiko Heckel, Barbara König

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.38.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Rebecca Bernemann
  • University of Duisburg-Essen, Germany
Benjamin Cabrera
  • University of Duisburg-Essen, Germany
Reiko Heckel
  • University of Leicester, UK
Barbara König
  • University of Duisburg-Essen, Germany

Funding

This work was supported by the Deutsche Forschungsgemeinschaft (DFG) under grant GRK 2167, Research Training Group "User-Centred Social Media".

Cite AsGet BibTex

Rebecca Bernemann, Benjamin Cabrera, Reiko Heckel, and Barbara König. Uncertainty Reasoning for Probabilistic Petri Nets via Bayesian Networks. 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. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.38

Abstract

This paper exploits extended Bayesian networks for uncertainty reasoning on Petri nets, where firing of transitions is probabilistic. In particular, Bayesian networks are used as symbolic representations of probability distributions, modelling the observer’s knowledge about the tokens in the net. The observer can study the net by monitoring successful and failed steps. An update mechanism for Bayesian nets is enabled by relaxing some of their restrictions, leading to modular Bayesian nets that can conveniently be represented and modified. As for every symbolic representation, the question is how to derive information - in this case marginal probability distributions - from a modular Bayesian net. We show how to do this by generalizing the known method of variable elimination. The approach is illustrated by examples about the spreading of diseases (SIR model) and information diffusion in social networks. We have implemented our approach and provide runtime results.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Bayesian networks
  • Software and its engineering → Petri nets
Keywords
  • uncertainty reasoning
  • probabilistic knowledge
  • Petri nets
  • Bayesian networks

Metrics

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

Related Versions

References

  1. Rebecca Bernemann, Benjamin Cabrera, Reiko Heckel, and Barbara König. Uncertainty reasoning for probabilistic petri nets via Bayesian networks, 2020. arXiv:2009.14817. URL: https://arxiv.org/abs/2009.14817.
  2. H.L. Bodlaender and A.M.C.A. Koster. Treewidth computations I. Upper bounds. Technical Report UU-CS-2008-032, Department of Information and Computing Sciences, Utrecht University, September 2008. Google Scholar
  3. R. Bruni, H. C. Melgratti, and U. Montanari. Bayesian network semantics for Petri nets. Theoretical Computer Science, 807:95-113, 2020. Google Scholar
  4. B. Cabrera. Analyzing and Modeling Complex Networks - Patterns, Paths and Probabilities. PhD thesis, Universität Duisburg-Essen, 2019. Google Scholar
  5. B. Cabrera, T. Heindel, R. Heckel, and B. König. Updating probabilistic knowledge on Condition/Event nets using Bayesian networks. In Proc. of CONCUR '18, volume 118 of LIPIcs, pages 27:1-27:17. Schloss Dagstuhl - Leibniz Center for Informatics, 2018. URL: http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=9565.
  6. J. Cardoso, R. Valette, and D. Dubois. Fuzzy Petri nets: An overview. In Proc. of 13th Triennal World Congress, 1996. Google Scholar
  7. A. Chantawibul and P. Sobociński. Towards compositional graph theory. In Proc. of MFPS XXXI. Elsevier, 2015. ENTCS 319. Google Scholar
  8. E. Charniak. Bayesian networks without tears. AI magazine, 12(4):50-50, 1991. Google Scholar
  9. M. Chiachio, J. Chiachio, D. Prescott, and J.D. Andrews. A new paradigm for uncertain knowledge representation by plausible Petri nets. Information Sciences, 453:323-345, 2018. Google Scholar
  10. B. Coecke and A. Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. Google Scholar
  11. A. Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, 1992. Google Scholar
  12. B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic, A Language-Theoretic Approach. Cambridge University Press, June 2012. Google Scholar
  13. A. Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2011. Google Scholar
  14. R. Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113:41-85, 1999. Google Scholar
  15. J. Desel and J. Esparza. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995. Google Scholar
  16. B. Fong. Causal theories: A categorical perspective on Bayesian networks. Master’s thesis, University of Oxford, 2012. arXiv:1301.6201. Google Scholar
  17. N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian network classifiers. Machine Learning, 29:131-163, 1997. Google Scholar
  18. C.M. Grinstead and J.L. Snell. Introduction to probability. American Mathematical Soc., 2012. Google Scholar
  19. J.Y. Halpern. Reasoning about Uncertainty. MIT Press, second edition edition, 2017. Google Scholar
  20. H. Hermanns, J. Meyer-Kayser, and M. Siegle. Multi-terminal binary decision diagrams to represent and analyse continuous-time markov chains. In Proc. of NSMC '99 (International Workshop on the Numerical Solution of Markov Chains), pages 188-207, 1999. Google Scholar
  21. B. Jacobs, A. Kissinger, and F. Zanasi. Causal inference by string diagram surgery. In Proc. of FOSSACS '19, pages 313-329. Springer, 2019. LNCS 11425. Google Scholar
  22. B. Jacobs and F. Zanasi. A formal semantics of influence in Bayesian reasoning. In Proc. of MFCS, volume 83 of LIPIcs, pages 21:1-21:14, 2017. Google Scholar
  23. I. Jarkass and M. Rombaut. Dealing with uncertainty on the initial state of a Petri net. In Proc. of UAI '98 (Uncertainty in Artificial Intelligence), pages 289-295, 1998. Google Scholar
  24. M.J. Keeling and K.T.D. Eames. Networks and epidemic models. Journal of the Royal Society Interface, 2(4):295-307, 2005. Google Scholar
  25. M. Kuchárik and Z. Balogh. Modeling of uncertainty with Petri nets. In Proc. of ACIIDS '19 (Asian Conference on Intelligent Information and Database Systems), pages 499-509. Springer, 2019. LNAI 11431. Google Scholar
  26. J.H.P. Kwisthout, H.L. Bodlaender, and L.C. Van Der Gaag. The necessity of bounded treewidth for efficient inference in Bayesian networks. In Proc. of ECAI '10 (European Conference on Artificial Intelligence), volume 215 of Frontiers in Artificial Intelligence and Applications, pages 237-242. IOS Press, 2010. Google Scholar
  27. J. Lee, K.F.R. Liu, and W. Chiang. Modeling uncertainty reasoning with possibilistic Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 33(2):214-224, 2003. Google Scholar
  28. V. Lepar and P.P. Shenoy. A comparison of Lauritzen-Spiegelhalter, Hugin, and Shenoy-Shafer architectures for computing marginals of probability distributions. In G.F. Cooper and S. Moral, editors, Proc. of UAI '98 (Uncertainty in Artificial Intelligence), pages 328-337, 1998. URL: http://arxiv.org/abs/1301.7394.
  29. M. Ajmone Marsan. Stochastic Petri nets: an elementary introduction. In Proc. of the European Workshop on Applications and Theory in Petri Nets, volume 424 of Lecture Notes in Computer Science, pages 1-29. Springer, 1990. Google Scholar
  30. K. Murphy. Dynamic Bayesian Networks: Representation, Inference and Learning. PhD thesis, UC Berkeley, Computer Science Division, 2002. Google Scholar
  31. J. Pearl. Bayesian networks: A model of self-activated memory for evidential reasoning. In Proc. of the 7th Conference of the Cognitive Science Society, pages 329-334, 1985. UCLA Technical Report CSD-850017. Google Scholar
  32. 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
  33. W. Reisig. Petri Nets: An Introduction. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, Germany, 1985. Google Scholar
  34. Z. Suraj. Generalised fuzzy Petri nets for approximate reasoning in decision support systems. In Proc. of CS&P '12 (International Workshop on Concurrency, Specification and Programming), volume 928 of CEUR Workshop Proceedings, pages 370-381. CEUR-WS.org, 2012. Google Scholar
  35. A. Tolver. An introduction to Markov chains. Department of Mathematical Sciences, University of Copenhagen, November 2016. Google Scholar
  36. W. Wiegerinck, W. Burgers, and B. Kappen. Bayesian networks, introduction and practical applications. In Handbook on Neural Information Processing, pages 401-431. Springer, 2013. 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 Imprint Privacy Contact