Bayes Ball
(1.2 hours to learn)
Summary
D-separation gives a way of determining conditional independence properties of a Bayes net from the graphical representation, but unfortunately the definition itself doesn't give a practical algorithm. Bayes ball is an efficient algorithm for computing d-separation by passing simple messages between nodes of the graph. The name "Bayes Ball" stems from the idea of balls bouncing around a directed graph, where if a ball cannot bounce between two nodes then they are [conditionally] independent.
Context
This concept has the prerequisites:
- d-separation (Bayes Ball is an efficient way of computing d-separation.)
Goals
- Memorize the ten Bayes' ball "bouncing rules" (noting symmetries makes this easy).
- You should be able to prove the validity of the bouncing rules using the definition of conditional probability.
- Understand how "marking" the nodes depending on the direction the ball is traveling when visiting the node leads to a linear-time algorithm for determining the [conditional] independencies in a Bayes net.
Core resources (read/watch one of the following)
-Free-
→ Scribe notes for "Computational Inference" course (2006)
Location:
Sections 2: Bayes Ball algorithm
Other notes:
- these notes do not explicitly discuss the dynamic programming aspect of the algorithm
→ Bayes-ball: rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams)
Supplemental resources (the following are optional, but you may find them useful)
-Free-
→ Baye's Ball Rules: Tips for Remembering the Rules
→ A Short Course on Graphical Models
Location:
slide 22
Other notes:
- slide 22 provides a "cheat sheet" for the Bayes ball rules
-Paid-
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location:
Section 10.5.1, pages 324-326
→ Probabilistic Graphical Models: Principles and Techniques
A very comprehensive textbook for a graduate-level course on probabilistic AI.
Location:
Section 3.3.3, pages 74-76
See also
- Bayes ball is an example of Bayes ball can be used as a preprocessing step in inference to determine which variables are relevant to a conditional probability query.