Feb 20, 2022

Actual d-separation without tears

If you want to skip the backstory and jump right to the rules to follow to determine whether nodes in a DAG are independent, go to The Find.

⏪ Prelude

I recently had to do a homework on Bayesian Networks and determine whether pairs of nodes were conditionally independent to a set of nodes. Prior to this homework, in an introductory course, I had heard the terms d-separation and d-connection thrown around and knew they had something to do with independence. Perhaps because it was introductory course, I hadn’t bothered actually looking into what they meant back then. So, as I often do, I set about trying to find info - outside course notes - that would untangle the link between d-connection and blocked paths .

After a bit of digging, I stumbled upon an online website that seemed to be, from its title, the ultimate won’t-waste-your-time and succinct resource: D-separation without tears.

Unfortunately, before I even had the chance to shed any tears, I realized that the resource wasn’t all that concise. So I continued my search, slogging, plodding and plowing until, at last, I found two sets of slides that had all I needed to write the meat of this post. Check out the References section to find the links to them.

📖 The Find

Here’s a condensed summary of the important information I dug up. It assumes that the reader knows what nodes, edges and conditional independence are.

Definition 1. A path is a sequence of distinct edges connecting two nodes.

Remark 1. For concision, paths are often represented as sequences of nodes, instead of sequences of edges.

Definition 2. Let be a path. A node is said to be a collider in the path if it has two incoming edges in .
Definition 3. Let be a path. A node is said to be a non-collider in the path if it is not a collider in the path.
Network Graph 1

Example 1. In the graph just above,

  • is a collider in the path because it has two incoming edges and .
  • is a collider in the path because it has two incoming edges and .
  • is not a collider (it is a non-collider) in the path .
  • and are paths between and but is not.
Definition 4. A path between two nodes is said to be blocked by a set of nodes if at least one the following conditions is satisfied:
  1. there is a collider in the path such that neither the collider nor any of its descendants is in .
  2. there is a non-collider in the path that belongs to .
Example 2. Let . In Network Graph 1 , the path between and is blocked by because is a non-collider in the path that belongs to , which satisfies condition 2.

Example 3. Let . In Network Graph 1, the path is not blocked by because neither condition 2 can be met, since is empty, nor can condition 1 be met, since none of the nodes in the path is a collider.

Now that you’ve hopefully understood the first four definitions, you’re ready to apply the rule to determine whether nodes are conditionally independent.

Theorem 1. Given three sets of nodes, , , , if all paths from any node of to any node of are blocked by , then .

Remark 2. The theorem implies that testing for conditional dependence, that is , only requires that one path be “not” blocked.

Remark 3. If there is no set of nodes conditioned on, then in the theorem.

The only piece of the puzzle left is to understand d-separation and d-connection. Here are their definitions.

Definition 5. Let and be two nodes and , a set of nodes. and are said to be d-separated given if and only if all paths between and are blocked by . Equivalently, in this case, by Theorem 1, .
Definition 6. Let and be two nodes and, , a set of nodes. and are said to be d-connected given if a path between and is not blocked by . Equivalently, in this case, by Theorem 1, .

🏋️ Exercises

The following exercises have to do with the network graph below. Please note that to make the notation lighter, I drop the curly braces surrounding sets.

Network Graph 2

📑 References

  1. https://dtai.cs.kuleuven.be/education/ai/Exercises/Session8/Solutions/solution.pdf
  2. https://www.cs.ubc.ca/~schmidtm/Courses/540-W16/L13.pdf
© 2022 ileumas.com Built with ❤️ using Astro