# 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.