1
$\begingroup$

How is conditional independence used for making probabilistic inference in Bayes networks easier or more efficient?

For example, given the following Bayes network:

enter image description here

Let's say I want to compute P(E=true | B=true, G=true), assuming all the variables here are boolean. Using d-separation, I can see that E given B,G is conditionally independent of A,C,D,G. How can I exploit the conditional independence to compute the above probability, using enumeration, for example?

$\endgroup$
3
  • $\begingroup$ Are you looking for the belief propagation algorithm? en.wikipedia.org/wiki/Belief_propagation $\endgroup$
    – R Hahn
    Jan 15, 2016 at 21:31
  • $\begingroup$ @RHahn: belief propagation is helpful when the network is already "simple" (a polytree). What I am looking for is how to make a given network "simpler" using conditional independence to ease (a potentially inefficient) computation, rather than how to efficiently compute probabilities on simple networks. $\endgroup$ Jan 15, 2016 at 21:41
  • $\begingroup$ Okay, that is helpful context for your question. $\endgroup$
    – R Hahn
    Jan 15, 2016 at 21:51

1 Answer 1

1
$\begingroup$

Naively (following your "using enumeration" comment), computing $P(E=\text{true}| B=\text{true}, G=\text{true})$ requires evaluating your joint probability distribution at all values where $B$ and $G$ are true, which is $2^6$ lookups since you have to vary over all possible values of 6 boolean variables: $A, C, D, E, H, I$.

The most straightforward way to exploit conditional independence is to condition on more stuff to reduce the number of lookups. As you note, $E$ is independent of $A, C, D$ conditional on $B, G$, so we have $$ P(e| b, g) = P(e| b, g, a, c, d) $$ where you can take $a, c, d$ to be whatever constant values you like (e.g. all true). Here I'm using the shorthand "$c$" to mean "$C=c$", and similarly for the other letters. Naively evaluating the right hand side requires only $2^3$ lookups, since you only have to vary over possible values of $E, H, I$.

In this example you can do better because the conditional joint distribution $P(E, H, I| b,g,a,c,d)$ "inherits" a Bayes network structure which is a tree, so you can compute marginals with belief propagation: $$ \boxed{E_{|B=b}} \to \boxed{H} \to \boxed{I_{|B=b, A=a}} $$ In general you can't expect to get a polytree, but this trick of conditioning on all variables conditionally independent of the node of interest might still induce a simpler network where it's easier to compute marginals.

In this example, computing $P(E=\text{true}|A=\text{true}, I=\text{true})$ seems like it'd be pretty annoying.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.