
Theory and Algorithms for Bayesian Networks 115
Algorithm 4.5 Logic Sampling Algorithm
1. Order the variables in X according to the topological partial order-
ing implied by G, say X
(1)
≺ X
(2)
≺ . . . ≺ X
(p)
.
2. Set n
E
= 0 and n
E,q
= 0.
3. For a suitably large number of samples x = (x
1
, . . . , x
p
):
(a) generate x
(i)
, i = 1, . . . , p from X
(i)
| Π
X
(i)
taking advantage of
the fact that, thanks to the topological ordering, by the time
we are considering X
i
we have already generated the values of
all its parents Π
X
(i)
;
(b) if x includes E, set n
E
= n
E
+ 1;
(c) if x includes both Q = q and E, set n
E,q
= n
E,q
+ 1.
4. Estimate Pr(Q | E, G, Θ) with n
E,q
/n
E
.
of the query ...