Skip to content

14 Bayes Nets Independence

  • so far: bayes nets encode a joint distribution
  • next: how to answer a series of queries about that distribution
  • last time
    • first assembled BNs using an intuitive notion of conditional dependence as causality
    • then saw that the key property is conditional independences
  • main goal: answer queries about conditional independence and influence
  • today: how to answer numerical queries (inference)

Probabilities in BNs

  • bayes nets implicitly encode joint distributions
  • as a product of local conditional distributions
  • to see what probability a BN gives to a full assignment, multiply all the relevant conditionals together
    • \(P(x_1, x_2, x_3, \dots, x_n) = \prod_{i=1}^{n} P(x_i | \text{parents}(X_i))\)
  • Example
    • \(P(+cavity, +catch, -toothache) = P(+cavity)P(+catch|+cavity) \cdot P(-toothache|+cavity, +catch)\)
  • toothache is conditionally independent from catch. this holds specifically for this bayes net we have put together. we could have drawn an entirely different net that we would need to compute and identify.

we talked about how to represent them, but now we can talk about what conditional independence really means

for bayes nets we don't actually have to do that, we can just condition on the parent nodes of each \(X_i\) on the graph

\(P(x_i | x_1, x_2, x_3, \dots) = P(x_1, \text{parents}(X_i))\)

  • beyond the above chain rule → bayes net conditional independence assumptions
  • often additional conditional independences
  • they can be read off the graph
  • important for modeling: understand assumptions made when choosing a bayes net representation

for example, we can always write down the bayes net distribution. so we can write down this model as such:

\(P(x) \cdot P(y|x) \cdot P(z|x, y) \cdot P(w|x, y, z)\)

  • so \(x\) has no parents
  • \(y\)'s parent is \(x\)
  • \(z\)'s parents are \(y\) and \(x\)
  • \(w\)'s parents are \(x\), \(y\), and \(z\)

This is equal to

\(P(x) \cdot P(y|x) \cdot P(z|y) \cdot P(w|z)\)

This is really nice, so we can use the above as a simpler, smaller computation we can use.

What if we want to be able to answer a statement,

  • Important question about a BN
  • Are two nodes independent given certain conditions?
  • If yes, can we prove their independence?
  • If no, can we prove it with a counter example?

\(\forall x, y, z: P(x, y | z) = P(x|z) \cdot P(y|z)\)

let's look at another example

ok before we go to the example

Causal chain

  • this config is a causal chain
X: Low Pressure  -->  Y: Rain  -->  Z: Traffic

Guaranteed \(X\) independent of \(Z\)? NO!

  • one example set of CPTs for which \(X\) is not independent of \(Z\) is sufficient to show this independence is not guaranteed
  • example
  • low pressure causes rain causes traffic
  • high pressure causes no rain causes no traffic
  • in numbers:
    • \(P(+y | +x) = 1\), \(P(-y | -x) = 1\)
    • \(P(+z | +y) = 1\), \(P(-z | -y) = 1\)

Are \(X\) and \(Z\) guaranteed to be independent given \(Y\)?

\(P(z|x, y) = \frac{P(x, y, z)}{P(x, y)}\)

prob of the node given its parents, we can expand this joint distribution

\(P(z|x, y) = \frac{P(x)P(y|x)P(z|y)}{P(x)P(y|x)}\)

cancel

\(P(z|x, y) = P(z|y)\)

therefore \(X\) is conditionally independent of \(Z\) given \(Y\)

Common cause

another base case: common cause

              Y: Project Due
                 /      \
                v        v
   X: Ed Forum busy    Z: OH Full

if ed is busy then i probably think that office hours is busy

\(P(x, y, z) = P(y)P(x|y)P(z|y)\)

Guaranteed \(X\) independent of \(Z\)? NO!

What about the conditional independence statement? Are \(X\) and \(Z\) independent given \(Y\)? - We can use the bayes net formula to expand the numerator, to expand the denominator and reduce → \(P(z|y)\), which means \(X\) is independent

Common effect (v-structure)

   X: Raining        Y: Ballgame
        \               /
         v             v
          Z: Traffic

Are \(X\) and \(Y\) independent? - yes, ballgame and rain cause traffic but they are not correlated - still need to prove they must be (try it!)

Are \(X\) and \(Y\) independent given \(Z\)? - NO! Seeing traffic puts the rain and ballgame in competition as an explanation.

Generalizing

lets try to generalize these?

  • given any BN, are two variables independent given evidence?

Reachability

  • recipe: shade evidence nodes, look for paths in the resulting graph
  • attempt 1: if two nodes are connected by an undirected path not blocked by a shaded node, they are conditionally independent

inference flows from one node to the other

Let's see if \(L\) is independent of \(T\) given \(R\)?

path from \(L\) to \(T\) is \([L, R, T]\)

look at all the triplets. the fact that it's raining blocks the influence from the information about the tire pressure from tracking. this was the first base case — the causal chain. we see that they are no longer correlated. we can use this to tell us whether variables are independent or dependent.

  • almost works but not quite
  • Where does it break?
  • Answer: the V structure at \(T\) doesn't count as a link in a path unless active.

D-separation

  • question: are \(X\) and \(Y\) conditionally independent given evidence variables \(Z\)?
  • yes if \(X\) and \(Y\) are "d-separated" by \(Z\)
  • consider all (undirected paths) from \(X\) to \(Y\)
  • no active paths: independence!
  • a path in an active triplet is active
  • causal chain \(A \to B \to C\) where \(B\) is observed (either direction)
  • common cause \(A \leftarrow B \to C\) where \(B\) is unobserved
  • common effect (aka v-structure)
  • \(A \to B \leftarrow C\) where \(B\), or one of its descendants, is observed
  • all it takes to block a path is a single inactive segment
  • note: these triples are all active (and similar for the other cases)

Examples

lets do some examples

L -> R
R -> T
R -> D
B -> T
T -> T'

can we say that \(L\) and \(T'\) are conditionally independent?

the triplet is \(L \to R \to T\) what about another triplet on the way?

triplet \(R \to T \to T'\)

If you have a path with multiple triplets, it means the entire path will stop. the entire thing is the conditional.

\(L \perp B\)?

Looking for a path from \(L\) to \(B\) - \(L \to R \to T\) active path - \(R \to T \leftarrow B\) inactive path

The trick is to find the singular inactive path; if we can identify it quickly, then if we find the 1, we can determine it is conditionally independent. YES!

\(L \perp B \mid T\)? No, because \(T\) makes the second one active, so info is being passed - \(L \to R \to T\) active - \(R \to T \leftarrow B\) is active given \(T\)

Given \(T\), we have a path from \(L\) to \(B\). We can look at this.

Still looking at all the paths from \(L\) to \(B\)?

\(L \perp B \mid T, R\)?

We have these triples.

\(L \to R \to T\) So this path becomes active because we are conditioning at \(T'\)

Another example

if we have - \(R\): Raining - \(T\): Traffic - \(D\): Roof Drips - \(S\): I'm Sad

R -> T
R -> D
T -> S
D -> S
  • \(T \perp D\)? No
  • \(T \perp D \mid R\)? Yes

all the independencies:

query paths active? independent?
\(R \perp T\) direct edge — No (adjacent)
\(R \perp D\) direct edge — No (adjacent)
\(T \perp S\) direct edge — No (adjacent)
\(D \perp S\) direct edge — No (adjacent)
\(R \perp S\) \(R \to T \to S\), \(R \to D \to S\) both active No
\(R \perp S \mid T\) \(R \to D \to S\) still open active No
\(R \perp S \mid D\) \(R \to T \to S\) still open active No
\(R \perp S \mid T, D\) both chains blocked none active Yes
\(T \perp D\) \(T \leftarrow R \to D\) open, \(T \to S \leftarrow D\) blocked one active No
\(T \perp D \mid R\) common cause blocked, v-structure still blocked none active Yes
\(T \perp D \mid S\) common cause open, v-structure now active active No
\(T \perp D \mid R, S\) common cause blocked, v-structure active active No

Summary

just in summary:

these bayes nets compute the joint distribution — they make it smaller and more compact and efficient. they encode distributions. we want to take a bayes net and be able to compute what those independencies are from the graph.

there might be other conditional independencies that exist; unless you are able to run the d-separation algo on all of them you may not catch them. but in practice, we will learn how to use that information to do inference on these graphs. on tomorrow's units on bayes nets we are going to use these to learn more about it. ask more questions if not.

next up: probabilistic inference.

learning bayes nets from data is the last bit.

bye