Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams)

Abstract

One of the benefits of belief networks and influence diagrams is that so much knowledge is captured in the graphical structure. In particular, statements of conditional irrelevance (or independence) can be verified in time linear in the size of the graph. To resolve a particular inference query or decision problem, only some of the possible states and probability distributions must be specified, the "requisite information." This paper presents a new, simple, and efficient "Bayes-ball" algorithm which is well-suited to both new students of belief networks and state of the art implementations. The Bayes-ball algorithm determines irrelevant sets and requisite information more efficiently than existing methods, and is linear in the size of the graph for belief networks and influence diagrams.

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

References in corpus (3)

• Identifying Independencies in Causal Graphs with Feedback
• Computational Advantages of Relevance Reasoning in Bayesian Belief Networks
• A Graph-Theoretic Analysis of Information Value

Cited by in corpus (17)

• Bayesian Logic Programs
• Efficient Value of Information Computation
• Unconstrained Influence Diagrams
• Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective
• Evaluating Influence Diagrams using LIMIDs
• Evaluating influence diagrams with decision circuits
• Application of Bayesian graphs to SN Ia data analysis and compression
• A Survey on Document-level Neural Machine Translation: Methods and Evaluation
• Understanding Agent Incentives using Causal Influence Diagrams. Part I: Single Action Settings
• Pivotal Pruning of Trade-offs in QPNs
• Probabilistic Warnings in National Security Crises: Pearl Harbor Revisited
• Inductive-bias-driven Reinforcement Learning For Efficient Schedules in Heterogeneous Clusters
• Dynamic programming in in uence diagrams with decision circuits
• Learning Distributional Programs for Relational Autocompletion
• Generalized Permutohedra from Probabilistic Graphical Models
• Identifying the Relevant Nodes Without Learning the Model
• Bayes Networks for Supporting Query Processing Over Incomplete Autonomous Databases