BN: Independence

D-Separation

A node is conditionally independent of all its ancestor nodes in the graph given all of its parents.

Causal Chains

Figure 1 is a configuration of three nodes known as a causal chain.

$$P(x,y,z)=P(z\mid y)P(y\mid x)P(x)$$

X and Z are not guaranteed to be independent.

However, we can make the statement that $X\perp \perp Z\mid Y$.

$$\begin{array}{rl}P(X\mid Z,y)& =\frac{P(X,Z,y)}{P(Z,y)}=\frac{P(Z\mid y)P(y\mid X)P(X)}{\sum _{x}P(X,y,Z)}=\frac{P(Z\mid y)P(y\mid X)P(X)}{P(Z\mid y)\sum _{x}P(y\mid x)P(x)}\\ & =\frac{P(y\mid X)P(X)}{\sum _{x}P(y\mid x)P(x)}=\frac{P(y\mid X)P(X)}{P(y)}=P(X\mid y)\end{array}$$

例子

未观察中间节点：

• 你有一个朋友 $Y$, 他受你的情绪 $X$ 影响（如果你开心, 他也开心）, 同时他也会影响他家里的宠物 $Z$ (他开心时宠物也高兴)。
• 如果你不知道朋友 $Y$ 的情绪, 你只能猜测你自己的情绪可能通过朋友影响到了宠物。因此, $X$ 和 $Z$ 之间有一种关联。

观察中间节点：

• 现在, 你知道了朋友 $Y$ 的情绪。无论你如何情绪, 你只需要看朋友的情绪来判断宠物的状态。因此, 知道了 $Y$ 之后, $X$ 和 $Z$ 之间就没有直接关系了。

Common Cause

$$P(x,y,z)=P(x\mid y)P(z\mid y)P(y)$$

X is not guaranteed to be independent of Z.

$X\perp \perp Z\mid Y$: X and Z are independent if Y is observed.

$$P(X\mid Z,y)=\frac{P(X,Z,y)}{P(Z,y)}=\frac{P(X\mid y)P(Z\mid y)P(y)}{P(Z\mid y)P(y)}=P(X\mid y)$$

例子

• 假设 $Y$ 是天气, $X$ 是人们是否带伞, $Z$ 是地面是否湿滑。天气影响人们是否带伞（如果天气预报下雨, 人们会带伞), 也影响地面是否湿滑（如果下雨, 地面会湿滑)。
• 如果你不知道天气（未观察 $Y$ ), 你可能会发现带伞和地面湿滑之间有某种关联（因为它们都受天气影响)。
• 但如果你知道天气情况 (观察 $Y$ ), 比如知道今天下雨, 那么带伞和地面湿滑的关系就变得独立了 (知道了天气, 你不需要通过看地面来判断是否需要带伞)。

Common Effect

$$P(x,y,z)=P(y\mid x,z)P(x)P(z)$$

In the configuration shown in Figure 5, X and Z are independent: $X\perp \perp Z$

However, they are not necessarily independent when conditioned on Y.

Example:

$$\begin{array}{rl}& P(X=\text{ true })=P(X=\text{ false })=0.5\\ & P(Z=\text{ true })=P(Z=\text{ false })=0.5\end{array}$$

and $Y$ is determined by whether $X$ and $Z$ have the same value:

$$P(Y\mid X,Z)=\{\begin{array}{ll}1& \text{ if }X=Z\text{ and }Y=\text{ true }\\ 1& \text{ if }X\ne Z\text{ and }Y=\text{ false }\\ 0& \text{ else }\end{array}$$

Then X and Z are independent if Y is unobserved. But if Y is observed, then knowing X tells you about Z. So X and Z are not conditionally independent given Y.

This same logic applies when conditioning on descendants of Y in the graph. If one of Y’s descendant nodes is observed, as in Figure 7, X and Z are not guaranteed to be independent.

General Case, and D-Separation

We formulate the problem as follows:

Problem

Given a Bayes Net $G$, two nodes $X$ and $Y$, and a (possibly empty) set of observed nodes $\{Z_1,\dots ,Z_k\}$, must the following statement be true: $X\perp \perp Y\mid \{Z_1,\dots ,Z_k\}$?

D-Separation(Directed Separation): If a set of variables $Z_1,\dots ,Z_k$ d-separates $X$ and $Y$, then $X\perp \perp Y\mid \{Z_1,\dots ,Z_k\}$. in all possible distributions that can be encoded by the Bayes Net.

D-Separation Algorithm

1. Shade all observed nodes $\{Z_1,\dots ,Z_k\}$ in the graph.
2. Enumerate all undirected paths from $X$ to $Y$.
3. For each path:
   1. Decompose the path into triples (segments of 3 nodes).
   2. If all triples are active, this path is active and d-connects $X$ to $Y$.
4. If no path d-connects $X$ and $Y$, then $X$ and $Y$ are d-separated, so they are conditionally independent given $\{Z_1,\dots ,Z_k\}$

Any path in a graph from X to Y can be decomposed into a set of 3 consecutive nodes and 2 edges - each of which is called a triple.

A triple is active or inactive depending on whether or not the middle node is observed.

Examples