Updating Probabilistic Knowledge on Condition/Event Nets using Bayesian Networks

Authors Benjamin Cabrera, Tobias Heindel, Reiko Heckel, Barbara König



PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2018.27.pdf
  • Filesize: 1.06 MB
  • 17 pages

Document Identifiers

Author Details

Benjamin Cabrera
  • University of Duisburg-Essen, Germany
Tobias Heindel
  • University of Hawaii, USA
Reiko Heckel
  • University of Leicester, UK
Barbara König
  • University of Duisburg-Essen, Germany

Cite AsGet BibTex

Benjamin Cabrera, Tobias Heindel, Reiko Heckel, and Barbara König. Updating Probabilistic Knowledge on Condition/Event Nets using Bayesian Networks. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CONCUR.2018.27

Abstract

The paper extends Bayesian networks (BNs) by a mechanism for dynamic changes to the probability distributions represented by BNs. One application scenario is the process of knowledge acquisition of an observer interacting with a system. In particular, the paper considers condition/event nets where the observer's knowledge about the current marking is a probability distribution over markings. The observer can interact with the net to deduce information about the marking by requesting certain transitions to fire and observing their success or failure. Aiming for an efficient implementation of dynamic changes to probability distributions of BNs, we consider a modular form of networks that form the arrows of a free PROP with a commutative comonoid structure, also known as term graphs. The algebraic structure of such PROPs supplies us with a compositional semantics that functorially maps BNs to their underlying probability distribution and, in particular, it provides a convenient means to describe structural updates of networks.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Bayesian networks
  • Software and its engineering → Petri nets
Keywords
  • Petri nets
  • Bayesian networks
  • Probabilistic databases
  • Condition/Event nets
  • Probabilistic knowledge
  • Dynamic probability distributions

Metrics

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

References

  1. L. Antova, C. Koch, and D. Olteanu. 10 ̂(10 ̂6) worlds and beyond: efficient representation and processing of incomplete information. VLDB Journal, 18(1021), 2009. Google Scholar
  2. R. Bruni, F. Gadducci, and U. Montanari. Normal forms for algebras of connections. Theoretical Computer Science, 286(2):247-292, 2002. Google Scholar
  3. B. Cabrera, T. Heindel, R. Heckel, and B. König. Updating probabilistic knowledge on Condition/Event nets using Bayesian networks, 2018. arXiv:1807.02566. URL: http://arxiv.org/abs/1807.02566.
  4. A.Y.W. Cheuk and C. Boutilier. Structured arc reversal and simulation of dynamic probabilistic networks. In Proc. of UAI '97 (Uncertainty in Artificial Intelligence), pages 72-79, 1997. Google Scholar
  5. B. Coecke and A. Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. Google Scholar
  6. G.F. Cooper. The computational complexity of probabilistic inference using Bayesian belief networks. Artif. Intell., 42(2-3):393-405, 1990. URL: http://dx.doi.org/10.1016/0004-3702(90)90060-D.
  7. A. Corradini and F. Gadducci. An algebraic presentation of term graphs, via gs-monoidal categories. Appl. Categor. Struct., 7:299-331, 1999. Google Scholar
  8. M.L. Damiani. Location privacy models in mobile applications: conceptual view and research directions. GeoInformatica, 18(4):819-842, 2014. URL: http://dx.doi.org/10.1007/s10707-014-0205-7.
  9. J. Desel and J. Esparza. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995. Google Scholar
  10. C. Dwork. Differential privacy: A survey of results. In Proc. of TAMC '08 (Theory and Applications of Models of Computation), pages 1-19. Springer, 2008. LNCS 4978. Google Scholar
  11. M. Fiore and M. Devesas Campos. The algebra of directed acyclic graphs. In Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky, pages 37-51. Springer, 2013. LNCS 7860. Google Scholar
  12. B. Fong. Causal theories: A categorical perspective on Bayesian networks. Master’s thesis, University of Oxford, 2012. arXiv:1301.6201. Google Scholar
  13. B. Fong and D. I Spivak. Seven Sketches in Compositionality: An Invitation to Applied Category Theory. ArXiv e-prints, 2018. URL: http://arxiv.org/abs/1803.05316.
  14. N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian network classifiers. Machine Learning, 29:131-163, 1997. Google Scholar
  15. N. Friedman and M. Goldszmidt. Sequential update of bayesian network structure. In Dan Geiger and Prakash Shenoy, editors, Proc. of UAI '97 (Uncertainty in Artificial Intelligence), pages 165-174, 1997. Google Scholar
  16. B. Jacobs and F. Zanasi. A predicate/state transformer semantics for Bayesian learning. In Proc. of MFPS, volume 325 of ENTCS, pages 185-200, 2016. Google Scholar
  17. 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
  18. 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
  19. C. Barry Jay. Languages for monoidal categories. Journal of Pure and Applied Algebra, 59(1):61-85, 1989. Google Scholar
  20. S. MacLane. Categorical algebra. Bull. Amer. Math. Soc., 71(1):40-106, 1965. Google Scholar
  21. K. Murphy. Dynamic Bayesian Networks: Representation, Inference and Learning. PhD thesis, UC Berkeley, Computer Science Division, 2002. Google Scholar
  22. 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
  23. J. Pearl. A probabilistic calculus of actions. In R. Lopez de Mantaras and D. Poole, editors, Proc. of UAI '94 (Uncertainty in Artificial Intelligence), 1994. Google Scholar
  24. J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000. Google Scholar
  25. 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
  26. W. Reisig. Petri Nets: An Introduction. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, Germany, 1985. Google Scholar
  27. P. Selinger. A survey of graphical languages for monoidal categories. In Bob Coecke, editor, New Structures for Physics, pages 289-355. Springer, 2011. Google Scholar
  28. D. Suciu, D. Olteanu, C. Ré, and C. Koch. Probabilistic Databases. Morgan &Claypool Publishers, 2011. Google Scholar
  29. W.M.P. van der Aalst. Markings in perpetual free-choice nets are fully characterized by their enabled transitions. In Proc. of PN '18 (Petri Nets), pages 315-336. Springer, 2018. LNCS 10877. Google Scholar
  30. F. Zanasi. Interacting Hopf Algebras - the theory of linear systems. PhD thesis, ENS Lyon, 2015. 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