Question 1

Consider the following belief net:

$\includegraphics{ah-multi-bel-net}$

Consider the query: $P(G|F=true,H=false)$ . For the elimination ordering, $B,D,E,A,C$ give all of factors created in VE. For each factor created, specify which factors were removed, and what variable was summed out. You do not need to consider any numerical values.

Solution:

Var Eliminated	Factors Removed	Factor Created
$B$	$P(C\|B) P(B\|A)$	$f_1(A,C)$
$D$	$P(D\|C) P(E\|D,G)$	$f_2(C,E,G)$
$E$	$P(f\|E,A) P(\neg h\|E)) f_2(C,E,G)$	$f_3(A,C,G)$
$A$	$P(A) f_1(A,C) f_3(A,C,G)$	$f_4(C,G)$
$C$	$P(G\|C) f_4(C,G)$	$f_5(G)$

Consider using recursive conditioning for the same query, assuming that the variable were split in the order $G,C,A,E,D,B$ . What values are used from the cache in this computation? Do any of the assignments disconnect the graph? If so, which ones?

Solution:

From the previous part we see that the factorization is:

	$\displaystyle P(G,f,\neg h) =\sum _ C P(G\|C) \sum _ A P(A)$	$\displaystyle \left(\sum _ B P(C\|B)P(B\|A)\right)$
	$\displaystyle$	$\displaystyle \left(\sum _ E (f\|EA)P(\neg h\|E) \sum _ D P(D\|C) P(E\|D,G)\right)$

The cached values stored after summing out $D$ for one value of $A$ can be used for the other value of $A$ , as the factors do not depend on $A$ . However they will not be used for other values of $C$ , $E$ or $G$ as the values in the factors depend on these variables.

The cached value stored after summing out $B$ can be used for the other value of $G$ , but not for other values of $C$ or $A$ .

After assigning $G$ , $C$ and $A$ the factors containing $\{ P(C=v_1|B),P(B|A=v_2)\}$ are disconnected from the other factors.

	$\displaystyle P(G,f,\neg h) =\sum _ C P(G\|C) \sum _ A P(A)$	$\displaystyle \left(\sum _ B P(C\|B)P(B\|A)\right)$
	$\displaystyle$	$\displaystyle \left(\sum _ E (f\|EA)P(\neg h\|E) \sum _ D P(D\|C) P(E\|D,G)\right)$