Stochastic Sampling Algorithms: Probabilistic Logic Sampling

From DSL

The probabilistic logic sampling algorithm is described in (Henrion 1988). This algorithm should be credited as the first algorithm applying stochastic sampling to belief updating in Bayesian networks.

Essentially, the algorithm is based on forward (i.e., according to the weak ordering implied by the directed graph) generation of instantiations of nodes guided by their probability. If a generated instantiation of an evidence node is different from its observed value, then the entire sample is discarded. This makes the algorithm very inefficient if the prior probability of evidence is low. The algorithm is very efficient in cases when no evidence has been observed or the evidence is very likely.