Compute a probability given a Bayesian network using variable elimination

Question

Having the following Bayesian Network:

A -> B, A -> C, B -> D, B -> F, C -> F, C -> G

$$\begin{array}{l} A&\to&B&\to& D\\\downarrow &&\downarrow \\ C&\to&F\\\downarrow\\G \end{array}$$

I have to compute this $P(+d, +f, \neg g)$.

How can I do it using variable elimination?

Answer 1

On this network, variable elimination will not result in a lot of simplification because of the connected structure (that is, not many variables will disappear when we do the elimination).

We consider the joint distribution $$P(A,B,C,D,F,G) = P(A)P(B|A)P(C|A)P(D|B)P(G|C)P(F|B,C).$$

We are looking for the marginal distribution $P(D,F,G)$; for instance, we can eliminate the variables in the order $A$, $B$, $C$, to obtain the required marginal (other orderings are of course possible and will result in slightly different computations).

First, we eliminate $A$. We pick out all the factors containing $A$ and we replace them with the factor obtained by summing over $A$: $$f_1(B,C) = \sum_a P(a)P(B|a)P(C|a) = P(+a)P(B|+a)P(C|+a) + P(\neg a)P(B|\neg a)P(C|\neg a).$$ The resulting factor after one variable elimination is a function of all the variables that were not eliminated.

Replacing the parts of the joint with this new factor will result in the elimination of $A$ from the joint $$P(B,C,D,F,G) = f_1(B,C)P(D|B)P(G|C)P(F|B,C).$$

We continue with our protocol and remove $B$. We pick out all the parts containing $B$ and we compute the factor by summing over $B$: $$f_2(C,D,F) = f_1(+b,C)P(D|+b)P(F|+b,C) + f_1(\neg b,C)P(D|\neg b)P(F|\neg b,C);$$ note that the factor is now function of three variables.

After the elimination, the marginal distribution is $$P(C,D,F,G) = f_2(C,D,F)P(G|C)P(F|C).$$

Finally, we eliminate $C$ from this distribution to obtain the required marginal $$P(D,F,G) = \sum_c f_2(c,D,F)P(G|c)P(F|c) = f_2(+c,D,F)P(G|+c)P(F|+c) + f_2(\neg c, D, F)P(G|\neg c)P(F|\neg c).$$

Plug in $D=+d$, $F=+f$, and $G=\neg g$, and you get the required probability.

Answer 2

First, factorise the probability in accordance with the DAG. Next associate so that you sum over $c,b,a$ in that order.

$$\begin{align}\mathsf P({^+}d,{^+}f,{^\lnot}g)&=\sum\limits_{a,b,c}\mathsf P(a)\mathsf P(b\mid a)\mathsf P({^+}d\mid b)\mathsf P(c\mid a)\mathsf P(^{\lnot} g\mid c)\mathsf P({^+}f\mid b,c)\\[1ex]&=\sum\limits_c\mathsf P({^\lnot}g\mid c)\left(\sum\limits_b\mathsf P(^{+}d\mid b)\mathsf P({^+}f\mid b, c)\left(\sum\limits_a\mathsf P(c\mid a)\mathsf P(b\mid a)\mathsf P(a)\right)\right)\end{align}$$

And that's pretty much it. The factors for "eliminating" $a,b,c$ are:

• $\mathsf P(b,c)=\sum\limits_a \mathsf P(c\mid a)\mathsf P(b\mid a)\mathsf P(a)$
• $\mathsf P(c,{^+}d,{^+}f)=\sum\limits_b\mathsf P({^+}d\mid b)\mathsf P({^+}f\mid b,c)\mathsf P(b,c)$
• $\mathsf P({^+}d,{^+}f,{^\lnot}g)= \sum\limits_c \mathsf P({^\lnot}g\mid c)\mathsf P(c,{^+}d,{^+}f)$