Abstract
Bayesian networks (BNs) are a probabilistic graphical model widely used for representing expert knowledge and reasoning under uncertainty. Traditionally, they are based on directed acyclic graphs that capture dependencies between random variables. However, directed cycles can naturally arise when cross-dependencies between random variables exist, e.g., for modeling feedback loops. Existing methods to deal with such cross-dependencies usually rely on reductions to BNs without cycles. These approaches are fragile to generalize, since their justifications are intermingled with additional knowledge about the application context. In this paper, we present a foundational study regarding semantics for cyclic BNs that are generic and conservatively extend the cycle-free setting. First, we propose constraint-based semantics that specify requirements for full joint distributions over a BN to be consistent with the local conditional probabilities and independencies. Second, two kinds of limit semantics that formalize infinite unfolding approaches are introduced and shown to be computable by a Markov chain construction.
This work was partially supported by the DFG in projects TRR 248 (CPEC, see https://perspicuous-computing.science, project ID 389792660) and EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy), and the Key-Area Research and Development Program Grant 2018B010107004 of Guangdong Province.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We use Boolean random variables for simplicity of representation, an extension of the proposed semantics over random variables with arbitrary finite state spaces is certainly possible.
- 2.
A path is simple if no node occurs twice in the path. “Undirected” in this context means that edges in either direction can occur along the path.
- 3.
Recall that we may view distributions as vectors which allows us to equate distributions over different but isomorphic domains.
References
Aguessy, F., Bettan, O., Blanc, G., Conan, V., Debar, H.: Bayesian attack model for dynamic risk assessment. CoRR (2016)
Castellano-Quero, M., Fernández-Madrigal, J.A., García-Cerezo, A.: Improving bayesian inference efficiency for sensory anomaly detection and recovery in mobile robots. Expert Systems with Applications 163 (2021)
Castillo, E., Gutiérrez, J.M., Hadi, A.S.: Modeling probabilistic networks of discrete and continuous variables. Journal of Multivariate Analysis 64(1), 48–65 (1998)
Doynikova, E., Kotenko, I.: Enhancement of probabilistic attack graphs for accurate cyber security monitoring. In: 2017 IEEE SmartWorld/SCALCOM/UIC/ ATC/CBDCom/IOP/SCI. pp. 1–6 (2017)
Forré, P., Mooij, J.M.: Markov properties for graphical models with cycles and latent variables (2017)
Geiger, D., Verma, T., Pearl, J.: d-separation: From theorems to algorithms. In: Machine Intelligence and Pattern Recognition, vol. 10, pp. 139–148. Elsevier (1990)
Halpern, J.Y.: Axiomatizing causal reasoning. J. Artif. Int. Res. 12, 317–337 (2000)
Han, S.H.: A top-down iteration algorithm for monte carlo method for probability estimation of a fault tree with circular logic. NET 50(6), 854–859 (2018)
Jaeger, M.: Complex probabilistic modeling with recursive relational bayesian networks. Ann. Math. Artif. Intell. 32(1-4), 179–220 (2001)
Jensen, F., Nielsen, T.: Bayesian Network and Decision Graphs. Springer (2007)
Jensen, F.V., Andersen, S.K., Kjærulff, U., Andreassen, S.: Munin – on the case for probabilities in medical expert systems – a practical exercise. In: AIME 87. pp. 149–160. Springer Berlin Heidelberg (1987)
Kemeny, J., Snell, J.: Finite Markov chains. University series in undergraduate mathematics, VanNostrand, New York, repr edn (1969)
Kłopotek, M.A.: Cyclic Bayesian network: Markov process approach. Studia Informatica: systems and information technology 1(7), 47–55 (2006)
Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. Adaptive Computation and Machine Learning, MIT Press (2009)
Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society. Series B (Methodological) 50(2), 157–224 (1988)
Liu, Y., Man, H.: Network vulnerability assessment using Bayesian networks. In: Data Mining, Intrusion Detection, Information Assurance, and Data Networks Security. vol. 5812, pp. 61–71. SPIE (2005)
Matthews, I., Mace, J., Soudjani, S., van Moorsel, A.: Cyclic bayesian attack graphs: A systematic computational approach (2020)
Motzek, A.: Indirect Causes, Dependencies and Causality in Bayesian Networks. Ph.D. thesis, University of Lübeck (2017)
Murphy, K.P.: Dynamic Bayesian Networks: Representation, Inference and Learning. Ph.D. thesis, University of California, Berkeley (2002)
Neal, R.M.: On deducing conditional independence from d-separation in causal graphs with feedback. Journal of Artificial Intelligence Research 12, 87–91 (2000)
Ou, X., Govindavajhala, S., Appel, A.W.: Mulval: A logic-based network security analyzer. In: Proceedings of the 14th Conference on USENIX Security Symposium- Volume 14. p. 8. SSYM’05, USENIX Association, USA (2005)
Pearl, J.: Fusion, Propagation, and Structuring in Belief Networks, pp. 366–413. Morgan Kaufmann Publishers Inc. (1990)
Pearl, J.: Causality: Models, Reasoning and Inference. CUP (2009)
Pearl, J., Dechter, R.: Identifying independencies in causal graphs with feedback. In: Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence. pp. 420–426. UAI’96, Morgan Kaufmann Publishers Inc. (1996)
Poole, D., Crowley, M.: Cyclic causal models with discrete variables: Markov chain equilibrium semantics and sample ordering. In: IJCAI International Joint Conference on Artificial Intelligence (2013)
Robert F. Nease, J., Owens, D.K.: Use of influence diagrams to structure medical decisions. Medical Decision Making 17(3), 263–275 (1997)
Singhal, A., Ou, X.: Security Risk Analysis of Enterprise Networks Using Probabilistic Attack Graphs, pp. 53–73. Springer International Publishing, Cham (2017)
Spirtes, P.: Conditional independence in directed cyclic graphical models for feedback. Tech. Rep. CMU-PHIL-53, Carnegie Mellon University (1994)
Spirtes, P.: Directed cyclic graphical representations of feedback models. In: Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. pp. 491–498. UAI’95, Morgan Kaufmann Publishers Inc. (1995)
Tulupyev, A.L., Nikolenko, S.I.: Directed cycles in bayesian belief networks: Probabilistic semantics and consistency checking complexity. In: MICAI 2005: Advances in Artificial Intelligence. pp. 214–223. Springer Berlin Heidelberg (2005)
Wang, L., Islam, T., Long, T., Singhal, A., Jajodia, S.: An attack graph-based probabilistic security metric. In: Data and Applications Security XXII. pp. 283–296. Springer Berlin Heidelberg (2008)
Wiecek, W., Bois, F.Y., Gayraud, G.: Structure learning of bayesian networks involving cyclic structures (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Baier, C., Dubslaff, C., Hermanns, H., Käfer, N. (2022). On the Foundations of Cycles in Bayesian Networks. In: Raskin, JF., Chatterjee, K., Doyen, L., Majumdar, R. (eds) Principles of Systems Design. Lecture Notes in Computer Science, vol 13660. Springer, Cham. https://doi.org/10.1007/978-3-031-22337-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-031-22337-2_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22336-5
Online ISBN: 978-3-031-22337-2
eBook Packages: Computer ScienceComputer Science (R0)