(1.2 hours to learn)
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.
This concept has the prerequisites:
- 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)
→ Scribe notes for "Computational Inference" course (2006)
Location: Sections 2: Bayes Ball algorithm
- 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)
Location: Sections 1-3
Supplemental resources (the following are optional, but you may find them useful)
→ Baye's Ball Rules: Tips for Remembering the Rules
→ A Short Course on Graphical Models
Location: slide 22
- slide 22 provides a "cheat sheet" for the Bayes ball rules
→ 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
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation