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:

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
Author: Alexandra Laflamme
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)
Location: Sections 1-3
Author: Ross Shachter

Supplemental resources (the following are optional, but you may find them useful)

-Free-

Baye's Ball Rules: Tips for Remembering the Rules
Author: Colorado Reed
A Short Course on Graphical Models
Location: slide 22
Author: Mark Paskin
Other notes:
  • slide 22 provides a "cheat sheet" for the Bayes ball rules

-Paid-

See also